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 (struct 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 (struct 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 (struct 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 struct 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 struct list_elem *
  79 list_next (struct 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 struct 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 struct 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 struct list_elem *
 110 list_prev (struct 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 struct 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 struct 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 struct 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 (struct list_elem *before, struct 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 (struct list_elem *before,
 182              struct list_elem *first, struct 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, struct 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, struct 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 struct list_elem *
 222 list_remove (struct 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 struct list_elem *
 233 list_pop_front (struct list *list)
 234 {
 235   struct 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 struct list_elem *
 243 list_pop_back (struct list *list)
 244 {
 245   struct 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 struct 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 struct 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   struct 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 `struct list_elem *'s that A and B point to. */
 289 static void
 290 swap (struct list_elem **a, struct list_elem **b)
 291 {
 292   struct 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       struct 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   struct 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       struct 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 /* Returns the middle element in LIST, that is, the N/2'th
 343    element (rounding down) in a N-element list.
 344    Given an empty list, returns the list tail. */
 345 static struct list_elem *
 346 middle_of_list (struct list *list)
 347 {
 348   struct list_elem *middle, *last;
 349
 350   middle = last = list_begin (list);
 351   while (last != list_end (list) && list_next (last) != list_end (list))
 352     {
 353       middle = list_next (middle);
 354       last = list_next (list_next (last));
 355     }
 356   return middle;
 357 }
 358
 359 /* Sorts LIST according to LESS given auxiliary data AUX.
 360    Runs in O(n lg n) time in the number of elements in LIST. */
 361 void
 362 list_sort (struct list *list,
 363            list_less_func *less, void *aux)
 364 {
 365   /* Find the middle of the list. */
 366   struct list_elem *middle = middle_of_list (list);
 367   if (middle != list_begin (list))
 368     {
 369       /* Extract first half of LIST into a temporary list. */
 370       struct list tmp;
 371       list_init (&tmp);
 372       list_splice (list_begin (&tmp), list_begin (list), middle);
 373
 374       /* Sort each half-list and merge the result. */
 375       list_sort (&tmp, less, aux);
 376       list_sort (list, less, aux);
 377       list_merge (list, &tmp, less, aux);
 378     }
 379   else
 380     {
 381       /* The middle is at the beginning of the list.
 382          This only happens in empty lists and 1-element lists.
 383          Because such lists are already sorted, we have nothing
 384          to do. */
 385     }
 386 }
 387
 388 /* Inserts ELEM in the proper position in LIST, which must be
 389    sorted according to LESS given auxiliary data AUX.
 390    Runs in O(n) average case in the number of elements in LIST. */
 391 void
 392 list_insert_ordered (struct list *list, struct list_elem *elem,
 393                      list_less_func *less, void *aux)
 394 {
 395   struct list_elem *e;
 396
 397   ASSERT (list != NULL);
 398   ASSERT (elem != NULL);
 399   ASSERT (less != NULL);
 400
 401   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 402     if (less (elem, e, aux))
 403       break;
 404   return list_insert (e, elem);
 405 }
 406
 407 /* Iterates through LIST and removes all but the first in each
 408    set of adjacent elements that are equal according to LESS
 409    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 410    elements from LIST are appended to DUPLICATES. */
 411 void
 412 list_unique (struct list *list, struct list *duplicates,
 413              list_less_func *less, void *aux)
 414 {
 415   struct list_elem *elem, *next;
 416
 417   ASSERT (list != NULL);
 418   ASSERT (less != NULL);
 419   if (list_empty (list))
 420     return;
 421
 422   elem = list_begin (list);
 423   while ((next = list_next (elem)) != list_end (list))
 424     if (!less (elem, next, aux) && !less (next, elem, aux))
 425       {
 426         list_remove (next);
 427         if (duplicates != NULL)
 428           list_push_back (duplicates, next);
 429       }
 430     else
 431       elem = next;
 432 }
 433
 434 /* Returns the element in LIST with the largest value according
 435    to LESS given auxiliary data AUX.  If there is more than one
 436    maximum, returns the one that appears earlier in the list.  If
 437    the list is empty, returns its tail. */
 438 struct list_elem *
 439 list_max (struct list *list, list_less_func *less, void *aux)
 440 {
 441   struct list_elem *max = list_begin (list);
 442   if (max != list_end (list))
 443     {
 444       struct list_elem *e;
 445
 446       for (e = list_next (max); e != list_end (list); e = list_next (e))
 447         if (less (max, e, aux))
 448           max = e;
 449     }
 450   return max;
 451 }
 452
 453 /* Returns the element in LIST with the smallest value according
 454    to LESS given auxiliary data AUX.  If there is more than one
 455    minimum, returns the one that appears earlier in the list.  If
 456    the list is empty, returns its tail. */
 457 struct list_elem *
 458 list_min (struct list *list, list_less_func *less, void *aux)
 459 {
 460   struct list_elem *min = list_begin (list);
 461   if (min != list_end (list))
 462     {
 463       struct list_elem *e;
 464
 465       for (e = list_next (min); e != list_end (list); e = list_next (e))
 466         if (less (e, min, aux))
 467           min = e;
 468     }
 469   return min;
 470 }