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