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 /* Returns true only if the list elements A through B (exclusive)
 313    are in order according to LESS given auxiliary data AUX. */
 314 static bool
 315 is_sorted (struct list_elem *a, struct list_elem *b,
 316            list_less_func *less, void *aux)
 317 {
 318   if (a != b)
 319     while ((a = list_next (a)) != b)
 320       if (less (a, list_prev (a), aux))
 321         return false;
 322   return true;
 323 }
 324
 325 /* Finds a run, starting at A and ending not after B, of list
 326    elements that are in nondecreasing order according to LESS
 327    given auxiliary data AUX.  Returns the (exclusive) end of the
 328    run.
 329    A through B (exclusive) must form a non-empty range. */
 330 static struct list_elem *
 331 find_end_of_run (struct list_elem *a, struct list_elem *b,
 332                  list_less_func *less, void *aux)
 333 {
 334   ASSERT (a != NULL);
 335   ASSERT (b != NULL);
 336   ASSERT (less != NULL);
 337   ASSERT (a != b);
 338
 339   do
 340     {
 341       a = list_next (a);
 342     }
 343   while (a != b && !less (a, list_prev (a), aux));
 344   return a;
 345 }
 346
 347 /* Merges A0 through A1B0 (exclusive) with A1B0 through B1
 348    (exclusive) to form a combined range also ending at B1
 349    (exclusive).  Both input ranges must be nonempty and sorted in
 350    nondecreasing order according to LESS given auxiliary data
 351    AUX.  The output range will be sorted the same way. */
 352 static void
 353 inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
 354                struct list_elem *b1,
 355                list_less_func *less, void *aux)
 356 {
 357   ASSERT (a0 != NULL);
 358   ASSERT (a1b0 != NULL);
 359   ASSERT (b1 != NULL);
 360   ASSERT (less != NULL);
 361   ASSERT (is_sorted (a0, a1b0, less, aux));
 362   ASSERT (is_sorted (a1b0, b1, less, aux));
 363
 364   while (a0 != a1b0 && a1b0 != b1)
 365     if (!less (a1b0, a0, aux))
 366       a0 = list_next (a0);
 367     else
 368       {
 369         a1b0 = list_next (a1b0);
 370         list_splice (a0, list_prev (a1b0), a1b0);
 371       }
 372 }
 373
 374 /* Sorts LIST according to LESS given auxiliary data AUX, using a
 375    natural iterative merge sort that runs in O(n lg n) time and
 376    O(1) space in the number of elements in LIST. */
 377 void
 378 list_sort (struct list *list, list_less_func *less, void *aux)
 379 {
 380   size_t output_run_cnt;        /* Number of runs output in current pass. */
 381
 382   ASSERT (list != NULL);
 383   ASSERT (less != NULL);
 384
 385   /* Pass over the list repeatedly, merging adjacent runs of
 386      nondecreasing elements, until only one run is left. */
 387   do
 388     {
 389       struct list_elem *a0;     /* Start of first run. */
 390       struct list_elem *a1b0;   /* End of first run, start of second. */
 391       struct list_elem *b1;     /* End of second run. */
 392
 393       output_run_cnt = 0;
 394       for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
 395         {
 396           /* Each iteration produces one output run. */
 397           output_run_cnt++;
 398
 399           /* Locate two adjacent runs of nondecreasing elements
 400              A0...A1B0 and A1B0...B1. */
 401           a1b0 = find_end_of_run (a0, list_end (list), less, aux);
 402           if (a1b0 == list_end (list))
 403             break;
 404           b1 = find_end_of_run (a1b0, list_end (list), less, aux);
 405
 406           /* Merge the runs. */
 407           inplace_merge (a0, a1b0, b1, less, aux);
 408         }
 409     }
 410   while (output_run_cnt > 1);
 411
 412   ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
 413 }
 414
 415 /* Inserts ELEM in the proper position in LIST, which must be
 416    sorted according to LESS given auxiliary data AUX.
 417    Runs in O(n) average case in the number of elements in LIST. */
 418 void
 419 list_insert_ordered (struct list *list, struct list_elem *elem,
 420                      list_less_func *less, void *aux)
 421 {
 422   struct list_elem *e;
 423
 424   ASSERT (list != NULL);
 425   ASSERT (elem != NULL);
 426   ASSERT (less != NULL);
 427
 428   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 429     if (less (elem, e, aux))
 430       break;
 431   return list_insert (e, elem);
 432 }
 433
 434 /* Iterates through LIST and removes all but the first in each
 435    set of adjacent elements that are equal according to LESS
 436    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 437    elements from LIST are appended to DUPLICATES. */
 438 void
 439 list_unique (struct list *list, struct list *duplicates,
 440              list_less_func *less, void *aux)
 441 {
 442   struct list_elem *elem, *next;
 443
 444   ASSERT (list != NULL);
 445   ASSERT (less != NULL);
 446   if (list_empty (list))
 447     return;
 448
 449   elem = list_begin (list);
 450   while ((next = list_next (elem)) != list_end (list))
 451     if (!less (elem, next, aux) && !less (next, elem, aux))
 452       {
 453         list_remove (next);
 454         if (duplicates != NULL)
 455           list_push_back (duplicates, next);
 456       }
 457     else
 458       elem = next;
 459 }
 460
 461 /* Returns the element in LIST with the largest value according
 462    to LESS given auxiliary data AUX.  If there is more than one
 463    maximum, returns the one that appears earlier in the list.  If
 464    the list is empty, returns its tail. */
 465 struct list_elem *
 466 list_max (struct list *list, list_less_func *less, void *aux)
 467 {
 468   struct list_elem *max = list_begin (list);
 469   if (max != list_end (list))
 470     {
 471       struct list_elem *e;
 472
 473       for (e = list_next (max); e != list_end (list); e = list_next (e))
 474         if (less (max, e, aux))
 475           max = e;
 476     }
 477   return max;
 478 }
 479
 480 /* Returns the element in LIST with the smallest value according
 481    to LESS given auxiliary data AUX.  If there is more than one
 482    minimum, returns the one that appears earlier in the list.  If
 483    the list is empty, returns its tail. */
 484 struct list_elem *
 485 list_min (struct list *list, list_less_func *less, void *aux)
 486 {
 487   struct list_elem *min = list_begin (list);
 488   if (min != list_end (list))
 489     {
 490       struct list_elem *e;
 491
 492       for (e = list_next (min); e != list_end (list); e = list_next (e))
 493         if (less (e, min, aux))
 494           min = e;
 495     }
 496   return min;
 497 }