pintos-os.org Git - pintos-anon/blob - src/lib/kernel/list.c

   1 #include "list.h"
   2 #include "../debug.h"
   3
   4 /* Our doubly linked lists have two header elements: the "head"
   5    just before the first element and the "tail" just after the
   6    last element.  The `prev' link of the front header is null, as
   7    is the `next' link of the back header.  Their other two links
   8    point toward each other via the interior elements of the list.
   9
  10    An empty list looks like this:
  11
  12                       +------+     +------+
  13                   <---| head |<--->| tail |--->
  14                       +------+     +------+
  15
  16    A list with two elements in it looks like this:
  17
  18         +------+     +-------+     +-------+     +------+
  19     <---| head |<--->|   1   |<--->|   2   |<--->| tail |<--->
  20         +------+     +-------+     +-------+     +------+
  21
  22    The symmetry of this arrangement eliminates lots of special
  23    cases in list processing.  For example, take a look at
  24    list_remove(): it takes only two pointer assignments and no
  25    conditionals.  That's a lot simpler than the code would be
  26    without header elements.
  27
  28    (Because only one of the pointers in each header element is used,
  29    we could in fact combine them into a single header element
  30    without sacrificing this simplicity.  But using two separate
  31    elements allows us to do a little bit of checking on some
  32    operations, which can be valuable.) */
  33
  34 /* Returns true if ELEM is a head, false otherwise. */
  35 static inline bool
  36 is_head (list_elem *elem)
  37 {
  38   return elem != NULL && elem->prev == NULL && elem->next != NULL;
  39 }
  40
  41 /* Returns true if ELEM is an interior element,
  42    false otherwise. */
  43 static inline bool
  44 is_interior (list_elem *elem)
  45 {
  46   return elem != NULL && elem->prev != NULL && elem->next != NULL;
  47 }
  48
  49 /* Returns true if ELEM is a tail, false otherwise. */
  50 static inline bool
  51 is_tail (list_elem *elem)
  52 {
  53   return elem != NULL && elem->prev != NULL && elem->next == NULL;
  54 }
  55
  56 /* Initializes LIST as an empty list. */
  57 void
  58 list_init (struct list *list)
  59 {
  60   ASSERT (list != NULL);
  61   list->head.prev = NULL;
  62   list->head.next = &list->tail;
  63   list->tail.prev = &list->head;
  64   list->tail.next = NULL;
  65 }
  66
  67 /* Returns the beginning of LIST.  */
  68 list_elem *
  69 list_begin (struct list *list)
  70 {
  71   ASSERT (list != NULL);
  72   return list->head.next;
  73 }
  74
  75 /* Returns the element after ELEM in its list.  If ELEM is the
  76    last element in its list, returns the list tail.  Results are
  77    undefined if ELEM is itself a list tail. */
  78 list_elem *
  79 list_next (list_elem *elem)
  80 {
  81   ASSERT (is_head (elem) || is_interior (elem));
  82   return elem->next;
  83 }
  84
  85 /* Returns LIST's tail.
  86
  87    list_end() is often used in iterating through a list from
  88    front to back.  See the big comment at the top of list.h for
  89    an example. */
  90 list_elem *
  91 list_end (struct list *list)
  92 {
  93   ASSERT (list != NULL);
  94   return &list->tail;
  95 }
  96
  97 /* Returns the LIST's reverse beginning, for iterating through
  98    LIST in reverse order, from back to front. */
  99 list_elem *
 100 list_rbegin (struct list *list)
 101 {
 102   ASSERT (list != NULL);
 103   return list->tail.prev;
 104 }
 105
 106 /* Returns the element before ELEM in its list.  If ELEM is the
 107    first element in its list, returns the list head.  Results are
 108    undefined if ELEM is itself a list head. */
 109 list_elem *
 110 list_prev (list_elem *elem)
 111 {
 112   ASSERT (is_interior (elem) || is_tail (elem));
 113   return elem->prev;
 114 }
 115
 116 /* Returns LIST's head.
 117
 118    list_rend() is often used in iterating through a list in
 119    reverse order, from back to front.  Here's typical usage,
 120    following the example from the top of list.h:
 121
 122       for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
 123            e = list_prev (e))
 124         {
 125           struct foo *f = list_entry (e, struct foo, elem);
 126           ...do something with f...
 127         }
 128 */
 129 list_elem *
 130 list_rend (struct list *list)
 131 {
 132   ASSERT (list != NULL);
 133   return &list->head;
 134 }
 135
 136 /* Return's LIST's head.
 137
 138    list_head() can be used for an alternate style of iterating
 139    through a list, e.g.:
 140
 141       e = list_head (&list);
 142       while ((e = list_next (e)) != list_end (&list))
 143         {
 144           ...
 145         }
 146 */
 147 list_elem *
 148 list_head (struct list *list)
 149 {
 150   ASSERT (list != NULL);
 151   return &list->head;
 152 }
 153
 154 /* Return's LIST's tail. */
 155 list_elem *
 156 list_tail (struct list *list)
 157 {
 158   ASSERT (list != NULL);
 159   return &list->tail;
 160 }
 161
 162 /* Inserts ELEM just before BEFORE, which may be either an
 163    interior element or a tail.  The latter case is equivalent to
 164    list_push_back(). */
 165 void
 166 list_insert (list_elem *before, list_elem *elem)
 167 {
 168   ASSERT (is_interior (before) || is_tail (before));
 169   ASSERT (elem != NULL);
 170
 171   elem->prev = before->prev;
 172   elem->next = before;
 173   before->prev->next = elem;
 174   before->prev = elem;
 175 }
 176
 177 /* Removes elements FIRST though LAST (exclusive) from their
 178    current list, then inserts them just before BEFORE, which may
 179    be either an interior element or a tail. */
 180 void
 181 list_splice (list_elem *before,
 182              list_elem *first, list_elem *last)
 183 {
 184   ASSERT (is_interior (before) || is_tail (before));
 185   if (first == last)
 186     return;
 187   last = list_prev (last);
 188
 189   ASSERT (is_interior (first));
 190   ASSERT (is_interior (last));
 191
 192   /* Cleanly remove FIRST...LAST from its current list. */
 193   first->prev->next = last->next;
 194   last->next->prev = first->prev;
 195
 196   /* Splice FIRST...LAST into new list. */
 197   first->prev = before->prev;
 198   last->next = before;
 199   before->prev->next = first;
 200   before->prev = last;
 201 }
 202
 203 /* Inserts ELEM at the beginning of LIST, so that it becomes the
 204    front in LIST. */
 205 void
 206 list_push_front (struct list *list, list_elem *elem)
 207 {
 208   list_insert (list_begin (list), elem);
 209 }
 210
 211 /* Inserts ELEM at the end of LIST, so that it becomes the
 212    back in LIST. */
 213 void
 214 list_push_back (struct list *list, list_elem *elem)
 215 {
 216   list_insert (list_end (list), elem);
 217 }
 218
 219 /* Removes ELEM from its list and returns the element that
 220    followed it.  Undefined behavior if ELEM is not in a list.  */
 221 list_elem *
 222 list_remove (list_elem *elem)
 223 {
 224   ASSERT (is_interior (elem));
 225   elem->prev->next = elem->next;
 226   elem->next->prev = elem->prev;
 227   return elem->next;
 228 }
 229
 230 /* Removes the front element from LIST and returns it.
 231    Undefined behavior if LIST is empty before removal. */
 232 list_elem *
 233 list_pop_front (struct list *list)
 234 {
 235   list_elem *front = list_front (list);
 236   list_remove (front);
 237   return front;
 238 }
 239
 240 /* Removes the back element from LIST and returns it.
 241    Undefined behavior if LIST is empty before removal. */
 242 list_elem *
 243 list_pop_back (struct list *list)
 244 {
 245   list_elem *back = list_back (list);
 246   list_remove (back);
 247   return back;
 248 }
 249
 250 /* Returns the front element in LIST.
 251    Undefined behavior if LIST is empty. */
 252 list_elem *
 253 list_front (struct list *list)
 254 {
 255   ASSERT (!list_empty (list));
 256   return list->head.next;
 257 }
 258
 259 /* Returns the back element in LIST.
 260    Undefined behavior if LIST is empty. */
 261 list_elem *
 262 list_back (struct list *list)
 263 {
 264   ASSERT (!list_empty (list));
 265   return list->tail.prev;
 266 }
 267
 268 /* Returns the number of elements in LIST.
 269    Runs in O(n) in the number of elements. */
 270 size_t
 271 list_size (struct list *list)
 272 {
 273   list_elem *e;
 274   size_t cnt = 0;
 275
 276   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 277     cnt++;
 278   return cnt;
 279 }
 280
 281 /* Returns true if LIST is empty, false otherwise. */
 282 bool
 283 list_empty (struct list *list)
 284 {
 285   return list_begin (list) == list_end (list);
 286 }
 287
 288 /* Swaps the `list_elem *'s that A and B point to. */
 289 static void
 290 swap (list_elem **a, list_elem **b)
 291 {
 292   list_elem *t = *a;
 293   *a = *b;
 294   *b = t;
 295 }
 296
 297 /* Reverses the order of LIST. */
 298 void
 299 list_reverse (struct list *list)
 300 {
 301   if (!list_empty (list))
 302     {
 303       list_elem *e;
 304
 305       for (e = list_begin (list); e != list_end (list); e = e->prev)
 306         swap (&e->prev, &e->next);
 307       swap (&list->head.next, &list->tail.prev);
 308       swap (&list->head.next->prev, &list->tail.prev->next);
 309     }
 310 }
 311
 312 /* Merges lists AL and BL, which must each be sorted according to
 313    LESS given auxiliary data AUX, by inserting each element of BL
 314    at the proper place in AL to preserve the ordering.
 315    Runs in O(n) in the combined length of AL and BL. */
 316 void
 317 list_merge (struct list *al, struct list *bl,
 318             list_less_func *less, void *aux)
 319 {
 320   list_elem *a;
 321
 322   ASSERT (al != NULL);
 323   ASSERT (bl != NULL);
 324   ASSERT (less != NULL);
 325
 326   a = list_begin (al);
 327   while (a != list_end (al))
 328     {
 329       list_elem *b = list_begin (bl);
 330       if (less (b, a, aux))
 331         {
 332           list_splice (a, b, list_next (b));
 333           if (list_empty (bl))
 334             break;
 335         }
 336       else
 337         a = list_next (a);
 338     }
 339   list_splice (list_end (al), list_begin (bl), list_end (bl));
 340 }
 341
 342 /* Sorts LIST according to LESS given auxiliary data AUX.
 343    Runs in O(n lg n) in the number of elements in LIST. */
 344 void
 345 list_sort (struct list *list,
 346            list_less_func *less, void *aux)
 347 {
 348   struct list tmp;
 349   list_elem *middle, *last;
 350
 351   ASSERT (list != NULL);
 352   ASSERT (less != NULL);
 353
 354   /* Empty and 1-element lists are already sorted. */
 355   if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
 356     return;
 357
 358   /* Find middle of LIST.  (We're not interested in the end of
 359      the list but it's incidentally needed.) */
 360   middle = last = list_begin (list);
 361   while (last != list_end (list) && list_next (last) != list_end (list))
 362     {
 363       middle = list_next (middle);
 364       last = list_next (list_next (last));
 365     }
 366
 367   /* Extract first half of LIST into a temporary list. */
 368   list_init (&tmp);
 369   list_splice (list_begin (&tmp), list_begin (list), middle);
 370
 371   /* Sort each half-list and merge the result. */
 372   list_sort (&tmp, less, aux);
 373   list_sort (list, less, aux);
 374   list_merge (list, &tmp, less, aux);
 375 }
 376
 377 /* Inserts ELEM in the proper position in LIST, which must be
 378    sorted according to LESS given auxiliary data AUX.
 379    Runs in O(n) average case in the number of elements in LIST. */
 380 void
 381 list_insert_ordered (struct list *list, list_elem *elem,
 382                      list_less_func *less, void *aux)
 383 {
 384   list_elem *e;
 385
 386   ASSERT (list != NULL);
 387   ASSERT (elem != NULL);
 388   ASSERT (less != NULL);
 389
 390   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 391     if (less (elem, e, aux))
 392       break;
 393   return list_insert (e, elem);
 394 }
 395
 396 /* Iterates through LIST and removes all but the first in each
 397    set of adjacent elements that are equal according to LESS
 398    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 399    elements from LIST are appended to DUPLICATES. */
 400 void
 401 list_unique (struct list *list, struct list *duplicates,
 402              list_less_func *less, void *aux)
 403 {
 404   list_elem *elem, *next;
 405
 406   ASSERT (list != NULL);
 407   ASSERT (less != NULL);
 408   if (list_empty (list))
 409     return;
 410
 411   elem = list_begin (list);
 412   while ((next = list_next (elem)) != list_end (list))
 413     if (!less (elem, next, aux) && !less (next, elem, aux))
 414       {
 415         list_remove (next);
 416         if (duplicates != NULL)
 417           list_push_back (duplicates, next);
 418       }
 419     else
 420       elem = next;
 421 }