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
 225    A list element must be treated very carefully after removing
 226    it from its list.  Calling list_next() or list_prev() on ELEM
 227    will return the item that was previously before or after ELEM,
 228    but, e.g., list_prev(list_next(ELEM)) is no longer ELEM!
 229
 230    The list_remove() return value provides a convenient way to
 231    iterate and remove elements from a list:
 232
 233    for (e = list_begin (&list); e != list_end (&list); e = list_remove (e))
 234      {
 235        ...do something with e...
 236      }
 237
 238    If you need to free() elements of the list then you need to be
 239    more conservative.  Here's an alternate strategy that works
 240    even in that case:
 241
 242    while (!list_empty (&list))
 243      {
 244        struct list_elem *e = list_pop_front (&list);
 245        ...do something with e...
 246      }
 247 */
 248 struct list_elem *
 249 list_remove (struct list_elem *elem)
 250 {
 251   ASSERT (is_interior (elem));
 252   elem->prev->next = elem->next;
 253   elem->next->prev = elem->prev;
 254   return elem->next;
 255 }
 256
 257 /* Removes the front element from LIST and returns it.
 258    Undefined behavior if LIST is empty before removal. */
 259 struct list_elem *
 260 list_pop_front (struct list *list)
 261 {
 262   struct list_elem *front = list_front (list);
 263   list_remove (front);
 264   return front;
 265 }
 266
 267 /* Removes the back element from LIST and returns it.
 268    Undefined behavior if LIST is empty before removal. */
 269 struct list_elem *
 270 list_pop_back (struct list *list)
 271 {
 272   struct list_elem *back = list_back (list);
 273   list_remove (back);
 274   return back;
 275 }
 276
 277 /* Returns the front element in LIST.
 278    Undefined behavior if LIST is empty. */
 279 struct list_elem *
 280 list_front (struct list *list)
 281 {
 282   ASSERT (!list_empty (list));
 283   return list->head.next;
 284 }
 285
 286 /* Returns the back element in LIST.
 287    Undefined behavior if LIST is empty. */
 288 struct list_elem *
 289 list_back (struct list *list)
 290 {
 291   ASSERT (!list_empty (list));
 292   return list->tail.prev;
 293 }
 294
 295 /* Returns the number of elements in LIST.
 296    Runs in O(n) in the number of elements. */
 297 size_t
 298 list_size (struct list *list)
 299 {
 300   struct list_elem *e;
 301   size_t cnt = 0;
 302
 303   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 304     cnt++;
 305   return cnt;
 306 }
 307
 308 /* Returns true if LIST is empty, false otherwise. */
 309 bool
 310 list_empty (struct list *list)
 311 {
 312   return list_begin (list) == list_end (list);
 313 }
 314
 315 /* Swaps the `struct list_elem *'s that A and B point to. */
 316 static void
 317 swap (struct list_elem **a, struct list_elem **b)
 318 {
 319   struct list_elem *t = *a;
 320   *a = *b;
 321   *b = t;
 322 }
 323
 324 /* Reverses the order of LIST. */
 325 void
 326 list_reverse (struct list *list)
 327 {
 328   if (!list_empty (list))
 329     {
 330       struct list_elem *e;
 331
 332       for (e = list_begin (list); e != list_end (list); e = e->prev)
 333         swap (&e->prev, &e->next);
 334       swap (&list->head.next, &list->tail.prev);
 335       swap (&list->head.next->prev, &list->tail.prev->next);
 336     }
 337 }
 338
 339 /* Returns true only if the list elements A through B (exclusive)
 340    are in order according to LESS given auxiliary data AUX. */
 341 static bool
 342 is_sorted (struct list_elem *a, struct list_elem *b,
 343            list_less_func *less, void *aux)
 344 {
 345   if (a != b)
 346     while ((a = list_next (a)) != b)
 347       if (less (a, list_prev (a), aux))
 348         return false;
 349   return true;
 350 }
 351
 352 /* Finds a run, starting at A and ending not after B, of list
 353    elements that are in nondecreasing order according to LESS
 354    given auxiliary data AUX.  Returns the (exclusive) end of the
 355    run.
 356    A through B (exclusive) must form a non-empty range. */
 357 static struct list_elem *
 358 find_end_of_run (struct list_elem *a, struct list_elem *b,
 359                  list_less_func *less, void *aux)
 360 {
 361   ASSERT (a != NULL);
 362   ASSERT (b != NULL);
 363   ASSERT (less != NULL);
 364   ASSERT (a != b);
 365
 366   do
 367     {
 368       a = list_next (a);
 369     }
 370   while (a != b && !less (a, list_prev (a), aux));
 371   return a;
 372 }
 373
 374 /* Merges A0 through A1B0 (exclusive) with A1B0 through B1
 375    (exclusive) to form a combined range also ending at B1
 376    (exclusive).  Both input ranges must be nonempty and sorted in
 377    nondecreasing order according to LESS given auxiliary data
 378    AUX.  The output range will be sorted the same way. */
 379 static void
 380 inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
 381                struct list_elem *b1,
 382                list_less_func *less, void *aux)
 383 {
 384   ASSERT (a0 != NULL);
 385   ASSERT (a1b0 != NULL);
 386   ASSERT (b1 != NULL);
 387   ASSERT (less != NULL);
 388   ASSERT (is_sorted (a0, a1b0, less, aux));
 389   ASSERT (is_sorted (a1b0, b1, less, aux));
 390
 391   while (a0 != a1b0 && a1b0 != b1)
 392     if (!less (a1b0, a0, aux))
 393       a0 = list_next (a0);
 394     else
 395       {
 396         a1b0 = list_next (a1b0);
 397         list_splice (a0, list_prev (a1b0), a1b0);
 398       }
 399 }
 400
 401 /* Sorts LIST according to LESS given auxiliary data AUX, using a
 402    natural iterative merge sort that runs in O(n lg n) time and
 403    O(1) space in the number of elements in LIST. */
 404 void
 405 list_sort (struct list *list, list_less_func *less, void *aux)
 406 {
 407   size_t output_run_cnt;        /* Number of runs output in current pass. */
 408
 409   ASSERT (list != NULL);
 410   ASSERT (less != NULL);
 411
 412   /* Pass over the list repeatedly, merging adjacent runs of
 413      nondecreasing elements, until only one run is left. */
 414   do
 415     {
 416       struct list_elem *a0;     /* Start of first run. */
 417       struct list_elem *a1b0;   /* End of first run, start of second. */
 418       struct list_elem *b1;     /* End of second run. */
 419
 420       output_run_cnt = 0;
 421       for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
 422         {
 423           /* Each iteration produces one output run. */
 424           output_run_cnt++;
 425
 426           /* Locate two adjacent runs of nondecreasing elements
 427              A0...A1B0 and A1B0...B1. */
 428           a1b0 = find_end_of_run (a0, list_end (list), less, aux);
 429           if (a1b0 == list_end (list))
 430             break;
 431           b1 = find_end_of_run (a1b0, list_end (list), less, aux);
 432
 433           /* Merge the runs. */
 434           inplace_merge (a0, a1b0, b1, less, aux);
 435         }
 436     }
 437   while (output_run_cnt > 1);
 438
 439   ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
 440 }
 441
 442 /* Inserts ELEM in the proper position in LIST, which must be
 443    sorted according to LESS given auxiliary data AUX.
 444    Runs in O(n) average case in the number of elements in LIST. */
 445 void
 446 list_insert_ordered (struct list *list, struct list_elem *elem,
 447                      list_less_func *less, void *aux)
 448 {
 449   struct list_elem *e;
 450
 451   ASSERT (list != NULL);
 452   ASSERT (elem != NULL);
 453   ASSERT (less != NULL);
 454
 455   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 456     if (less (elem, e, aux))
 457       break;
 458   return list_insert (e, elem);
 459 }
 460
 461 /* Iterates through LIST and removes all but the first in each
 462    set of adjacent elements that are equal according to LESS
 463    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 464    elements from LIST are appended to DUPLICATES. */
 465 void
 466 list_unique (struct list *list, struct list *duplicates,
 467              list_less_func *less, void *aux)
 468 {
 469   struct list_elem *elem, *next;
 470
 471   ASSERT (list != NULL);
 472   ASSERT (less != NULL);
 473   if (list_empty (list))
 474     return;
 475
 476   elem = list_begin (list);
 477   while ((next = list_next (elem)) != list_end (list))
 478     if (!less (elem, next, aux) && !less (next, elem, aux))
 479       {
 480         list_remove (next);
 481         if (duplicates != NULL)
 482           list_push_back (duplicates, next);
 483       }
 484     else
 485       elem = next;
 486 }
 487
 488 /* Returns the element in LIST with the largest value according
 489    to LESS given auxiliary data AUX.  If there is more than one
 490    maximum, returns the one that appears earlier in the list.  If
 491    the list is empty, returns its tail. */
 492 struct list_elem *
 493 list_max (struct list *list, list_less_func *less, void *aux)
 494 {
 495   struct list_elem *max = list_begin (list);
 496   if (max != list_end (list))
 497     {
 498       struct list_elem *e;
 499
 500       for (e = list_next (max); e != list_end (list); e = list_next (e))
 501         if (less (max, e, aux))
 502           max = e;
 503     }
 504   return max;
 505 }
 506
 507 /* Returns the element in LIST with the smallest value according
 508    to LESS given auxiliary data AUX.  If there is more than one
 509    minimum, returns the one that appears earlier in the list.  If
 510    the list is empty, returns its tail. */
 511 struct list_elem *
 512 list_min (struct list *list, list_less_func *less, void *aux)
 513 {
 514   struct list_elem *min = list_begin (list);
 515   if (min != list_end (list))
 516     {
 517       struct list_elem *e;
 518
 519       for (e = list_next (min); e != list_end (list); e = list_next (e))
 520         if (less (e, min, aux))
 521           min = e;
 522     }
 523   return min;
 524 }