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 static bool is_sorted (struct list_elem *a, struct list_elem *b,
  35                        list_less_func *less, void *aux) UNUSED;
  36
  37 /* Returns true if ELEM is a head, false otherwise. */
  38 static inline bool
  39 is_head (struct list_elem *elem)
  40 {
  41   return elem != NULL && elem->prev == NULL && elem->next != NULL;
  42 }
  43
  44 /* Returns true if ELEM is an interior element,
  45    false otherwise. */
  46 static inline bool
  47 is_interior (struct list_elem *elem)
  48 {
  49   return elem != NULL && elem->prev != NULL && elem->next != NULL;
  50 }
  51
  52 /* Returns true if ELEM is a tail, false otherwise. */
  53 static inline bool
  54 is_tail (struct list_elem *elem)
  55 {
  56   return elem != NULL && elem->prev != NULL && elem->next == NULL;
  57 }
  58
  59 /* Initializes LIST as an empty list. */
  60 void
  61 list_init (struct list *list)
  62 {
  63   ASSERT (list != NULL);
  64   list->head.prev = NULL;
  65   list->head.next = &list->tail;
  66   list->tail.prev = &list->head;
  67   list->tail.next = NULL;
  68 }
  69
  70 /* Returns the beginning of LIST.  */
  71 struct list_elem *
  72 list_begin (struct list *list)
  73 {
  74   ASSERT (list != NULL);
  75   return list->head.next;
  76 }
  77
  78 /* Returns the element after ELEM in its list.  If ELEM is the
  79    last element in its list, returns the list tail.  Results are
  80    undefined if ELEM is itself a list tail. */
  81 struct list_elem *
  82 list_next (struct list_elem *elem)
  83 {
  84   ASSERT (is_head (elem) || is_interior (elem));
  85   return elem->next;
  86 }
  87
  88 /* Returns LIST's tail.
  89
  90    list_end() is often used in iterating through a list from
  91    front to back.  See the big comment at the top of list.h for
  92    an example. */
  93 struct list_elem *
  94 list_end (struct list *list)
  95 {
  96   ASSERT (list != NULL);
  97   return &list->tail;
  98 }
  99
 100 /* Returns the LIST's reverse beginning, for iterating through
 101    LIST in reverse order, from back to front. */
 102 struct list_elem *
 103 list_rbegin (struct list *list)
 104 {
 105   ASSERT (list != NULL);
 106   return list->tail.prev;
 107 }
 108
 109 /* Returns the element before ELEM in its list.  If ELEM is the
 110    first element in its list, returns the list head.  Results are
 111    undefined if ELEM is itself a list head. */
 112 struct list_elem *
 113 list_prev (struct list_elem *elem)
 114 {
 115   ASSERT (is_interior (elem) || is_tail (elem));
 116   return elem->prev;
 117 }
 118
 119 /* Returns LIST's head.
 120
 121    list_rend() is often used in iterating through a list in
 122    reverse order, from back to front.  Here's typical usage,
 123    following the example from the top of list.h:
 124
 125       for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
 126            e = list_prev (e))
 127         {
 128           struct foo *f = list_entry (e, struct foo, elem);
 129           ...do something with f...
 130         }
 131 */
 132 struct list_elem *
 133 list_rend (struct list *list)
 134 {
 135   ASSERT (list != NULL);
 136   return &list->head;
 137 }
 138
 139 /* Return's LIST's head.
 140
 141    list_head() can be used for an alternate style of iterating
 142    through a list, e.g.:
 143
 144       e = list_head (&list);
 145       while ((e = list_next (e)) != list_end (&list))
 146         {
 147           ...
 148         }
 149 */
 150 struct list_elem *
 151 list_head (struct list *list)
 152 {
 153   ASSERT (list != NULL);
 154   return &list->head;
 155 }
 156
 157 /* Return's LIST's tail. */
 158 struct list_elem *
 159 list_tail (struct list *list)
 160 {
 161   ASSERT (list != NULL);
 162   return &list->tail;
 163 }
 164
 165 /* Inserts ELEM just before BEFORE, which may be either an
 166    interior element or a tail.  The latter case is equivalent to
 167    list_push_back(). */
 168 void
 169 list_insert (struct list_elem *before, struct list_elem *elem)
 170 {
 171   ASSERT (is_interior (before) || is_tail (before));
 172   ASSERT (elem != NULL);
 173
 174   elem->prev = before->prev;
 175   elem->next = before;
 176   before->prev->next = elem;
 177   before->prev = elem;
 178 }
 179
 180 /* Removes elements FIRST though LAST (exclusive) from their
 181    current list, then inserts them just before BEFORE, which may
 182    be either an interior element or a tail. */
 183 void
 184 list_splice (struct list_elem *before,
 185              struct list_elem *first, struct list_elem *last)
 186 {
 187   ASSERT (is_interior (before) || is_tail (before));
 188   if (first == last)
 189     return;
 190   last = list_prev (last);
 191
 192   ASSERT (is_interior (first));
 193   ASSERT (is_interior (last));
 194
 195   /* Cleanly remove FIRST...LAST from its current list. */
 196   first->prev->next = last->next;
 197   last->next->prev = first->prev;
 198
 199   /* Splice FIRST...LAST into new list. */
 200   first->prev = before->prev;
 201   last->next = before;
 202   before->prev->next = first;
 203   before->prev = last;
 204 }
 205
 206 /* Inserts ELEM at the beginning of LIST, so that it becomes the
 207    front in LIST. */
 208 void
 209 list_push_front (struct list *list, struct list_elem *elem)
 210 {
 211   list_insert (list_begin (list), elem);
 212 }
 213
 214 /* Inserts ELEM at the end of LIST, so that it becomes the
 215    back in LIST. */
 216 void
 217 list_push_back (struct list *list, struct list_elem *elem)
 218 {
 219   list_insert (list_end (list), elem);
 220 }
 221
 222 /* Removes ELEM from its list and returns the element that
 223    followed it.  Undefined behavior if ELEM is not in a list.  */
 224 struct list_elem *
 225 list_remove (struct list_elem *elem)
 226 {
 227   ASSERT (is_interior (elem));
 228   elem->prev->next = elem->next;
 229   elem->next->prev = elem->prev;
 230   return elem->next;
 231 }
 232
 233 /* Removes the front element from LIST and returns it.
 234    Undefined behavior if LIST is empty before removal. */
 235 struct list_elem *
 236 list_pop_front (struct list *list)
 237 {
 238   struct list_elem *front = list_front (list);
 239   list_remove (front);
 240   return front;
 241 }
 242
 243 /* Removes the back element from LIST and returns it.
 244    Undefined behavior if LIST is empty before removal. */
 245 struct list_elem *
 246 list_pop_back (struct list *list)
 247 {
 248   struct list_elem *back = list_back (list);
 249   list_remove (back);
 250   return back;
 251 }
 252
 253 /* Returns the front element in LIST.
 254    Undefined behavior if LIST is empty. */
 255 struct list_elem *
 256 list_front (struct list *list)
 257 {
 258   ASSERT (!list_empty (list));
 259   return list->head.next;
 260 }
 261
 262 /* Returns the back element in LIST.
 263    Undefined behavior if LIST is empty. */
 264 struct list_elem *
 265 list_back (struct list *list)
 266 {
 267   ASSERT (!list_empty (list));
 268   return list->tail.prev;
 269 }
 270
 271 /* Returns the number of elements in LIST.
 272    Runs in O(n) in the number of elements. */
 273 size_t
 274 list_size (struct list *list)
 275 {
 276   struct list_elem *e;
 277   size_t cnt = 0;
 278
 279   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 280     cnt++;
 281   return cnt;
 282 }
 283
 284 /* Returns true if LIST is empty, false otherwise. */
 285 bool
 286 list_empty (struct list *list)
 287 {
 288   return list_begin (list) == list_end (list);
 289 }
 290
 291 /* Swaps the `struct list_elem *'s that A and B point to. */
 292 static void
 293 swap (struct list_elem **a, struct list_elem **b)
 294 {
 295   struct list_elem *t = *a;
 296   *a = *b;
 297   *b = t;
 298 }
 299
 300 /* Reverses the order of LIST. */
 301 void
 302 list_reverse (struct list *list)
 303 {
 304   if (!list_empty (list))
 305     {
 306       struct list_elem *e;
 307
 308       for (e = list_begin (list); e != list_end (list); e = e->prev)
 309         swap (&e->prev, &e->next);
 310       swap (&list->head.next, &list->tail.prev);
 311       swap (&list->head.next->prev, &list->tail.prev->next);
 312     }
 313 }
 314
 315 /* Returns true only if the list elements A through B (exclusive)
 316    are in order according to LESS given auxiliary data AUX. */
 317 static bool
 318 is_sorted (struct list_elem *a, struct list_elem *b,
 319            list_less_func *less, void *aux)
 320 {
 321   if (a != b)
 322     while ((a = list_next (a)) != b)
 323       if (less (a, list_prev (a), aux))
 324         return false;
 325   return true;
 326 }
 327
 328 /* Finds a run, starting at A and ending not after B, of list
 329    elements that are in nondecreasing order according to LESS
 330    given auxiliary data AUX.  Returns the (exclusive) end of the
 331    run.
 332    A through B (exclusive) must form a non-empty range. */
 333 static struct list_elem *
 334 find_end_of_run (struct list_elem *a, struct list_elem *b,
 335                  list_less_func *less, void *aux)
 336 {
 337   ASSERT (a != NULL);
 338   ASSERT (b != NULL);
 339   ASSERT (less != NULL);
 340   ASSERT (a != b);
 341
 342   do
 343     {
 344       a = list_next (a);
 345     }
 346   while (a != b && !less (a, list_prev (a), aux));
 347   return a;
 348 }
 349
 350 /* Merges A0 through A1B0 (exclusive) with A1B0 through B1
 351    (exclusive) to form a combined range also ending at B1
 352    (exclusive).  Both input ranges must be nonempty and sorted in
 353    nondecreasing order according to LESS given auxiliary data
 354    AUX.  The output range will be sorted the same way. */
 355 static void
 356 inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
 357                struct list_elem *b1,
 358                list_less_func *less, void *aux)
 359 {
 360   ASSERT (a0 != NULL);
 361   ASSERT (a1b0 != NULL);
 362   ASSERT (b1 != NULL);
 363   ASSERT (less != NULL);
 364   ASSERT (is_sorted (a0, a1b0, less, aux));
 365   ASSERT (is_sorted (a1b0, b1, less, aux));
 366
 367   while (a0 != a1b0 && a1b0 != b1)
 368     if (!less (a1b0, a0, aux))
 369       a0 = list_next (a0);
 370     else
 371       {
 372         a1b0 = list_next (a1b0);
 373         list_splice (a0, list_prev (a1b0), a1b0);
 374       }
 375 }
 376
 377 /* Sorts LIST according to LESS given auxiliary data AUX, using a
 378    natural iterative merge sort that runs in O(n lg n) time and
 379    O(1) space in the number of elements in LIST. */
 380 void
 381 list_sort (struct list *list, list_less_func *less, void *aux)
 382 {
 383   size_t output_run_cnt;        /* Number of runs output in current pass. */
 384
 385   ASSERT (list != NULL);
 386   ASSERT (less != NULL);
 387
 388   /* Pass over the list repeatedly, merging adjacent runs of
 389      nondecreasing elements, until only one run is left. */
 390   do
 391     {
 392       struct list_elem *a0;     /* Start of first run. */
 393       struct list_elem *a1b0;   /* End of first run, start of second. */
 394       struct list_elem *b1;     /* End of second run. */
 395
 396       output_run_cnt = 0;
 397       for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
 398         {
 399           /* Each iteration produces one output run. */
 400           output_run_cnt++;
 401
 402           /* Locate two adjacent runs of nondecreasing elements
 403              A0...A1B0 and A1B0...B1. */
 404           a1b0 = find_end_of_run (a0, list_end (list), less, aux);
 405           if (a1b0 == list_end (list))
 406             break;
 407           b1 = find_end_of_run (a1b0, list_end (list), less, aux);
 408
 409           /* Merge the runs. */
 410           inplace_merge (a0, a1b0, b1, less, aux);
 411         }
 412     }
 413   while (output_run_cnt > 1);
 414
 415   ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
 416 }
 417
 418 /* Inserts ELEM in the proper position in LIST, which must be
 419    sorted according to LESS given auxiliary data AUX.
 420    Runs in O(n) average case in the number of elements in LIST. */
 421 void
 422 list_insert_ordered (struct list *list, struct list_elem *elem,
 423                      list_less_func *less, void *aux)
 424 {
 425   struct list_elem *e;
 426
 427   ASSERT (list != NULL);
 428   ASSERT (elem != NULL);
 429   ASSERT (less != NULL);
 430
 431   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 432     if (less (elem, e, aux))
 433       break;
 434   return list_insert (e, elem);
 435 }
 436
 437 /* Iterates through LIST and removes all but the first in each
 438    set of adjacent elements that are equal according to LESS
 439    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 440    elements from LIST are appended to DUPLICATES. */
 441 void
 442 list_unique (struct list *list, struct list *duplicates,
 443              list_less_func *less, void *aux)
 444 {
 445   struct list_elem *elem, *next;
 446
 447   ASSERT (list != NULL);
 448   ASSERT (less != NULL);
 449   if (list_empty (list))
 450     return;
 451
 452   elem = list_begin (list);
 453   while ((next = list_next (elem)) != list_end (list))
 454     if (!less (elem, next, aux) && !less (next, elem, aux))
 455       {
 456         list_remove (next);
 457         if (duplicates != NULL)
 458           list_push_back (duplicates, next);
 459       }
 460     else
 461       elem = next;
 462 }
 463
 464 /* Returns the element in LIST with the largest value according
 465    to LESS given auxiliary data AUX.  If there is more than one
 466    maximum, returns the one that appears earlier in the list.  If
 467    the list is empty, returns its tail. */
 468 struct list_elem *
 469 list_max (struct list *list, list_less_func *less, void *aux)
 470 {
 471   struct list_elem *max = list_begin (list);
 472   if (max != list_end (list))
 473     {
 474       struct list_elem *e;
 475
 476       for (e = list_next (max); e != list_end (list); e = list_next (e))
 477         if (less (max, e, aux))
 478           max = e;
 479     }
 480   return max;
 481 }
 482
 483 /* Returns the element in LIST with the smallest value according
 484    to LESS given auxiliary data AUX.  If there is more than one
 485    minimum, returns the one that appears earlier in the list.  If
 486    the list is empty, returns its tail. */
 487 struct list_elem *
 488 list_min (struct list *list, list_less_func *less, void *aux)
 489 {
 490   struct list_elem *min = list_begin (list);
 491   if (min != list_end (list))
 492     {
 493       struct list_elem *e;
 494
 495       for (e = list_next (min); e != list_end (list); e = list_next (e))
 496         if (less (e, min, aux))
 497           min = e;
 498     }
 499   return min;
 500 }