pintos-os.org Git - pintos-anon/blob - src/lib/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 (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 (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 (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 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 list_elem *
  79 list_next (list_elem *elem)
  80 {
  81   ASSERT (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 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 list_elem *
 100 list_rbegin (struct list *list)
 101 {
 102   ASSERT (list != NULL);
 103   return list->tail.prev;
 104 }
 105
 106 /* Returns LIST's head.
 107
 108    list_rend() is often used in iterating through a list in
 109    reverse order, from back to front.  Here's typical usage,
 110    following the example from the top of list.h:
 111
 112       for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
 113            e = list_prev (e))
 114         {
 115           struct foo *f = list_entry (e, struct foo, elem);
 116           ...do something with f...
 117         }
 118 */
 119 list_elem *
 120 list_rend (struct list *list)
 121 {
 122   ASSERT (list != NULL);
 123   return &list->head;
 124 }
 125
 126 /* Returns the element before ELEM in its list.  If ELEM is the
 127    first element in its list, returns the list head.  Results are
 128    undefined if ELEM is itself a list head. */
 129 list_elem *
 130 list_prev (list_elem *elem)
 131 {
 132   ASSERT (is_interior (elem) || is_tail (elem));
 133   return elem->prev;
 134 }
 135
 136 /* Inserts ELEM just before BEFORE, which may be either an
 137    interior element or a tail.  The latter case is equivalent to
 138    list_push_back(). */
 139 void
 140 list_insert (list_elem *before, list_elem *elem)
 141 {
 142   ASSERT (is_interior (before) || is_tail (before));
 143   ASSERT (elem != NULL);
 144
 145   elem->prev = before->prev;
 146   elem->next = before;
 147   before->prev->next = elem;
 148   before->prev = elem;
 149 }
 150
 151 /* Removes elements FIRST though LAST (exclusive) from their
 152    current list, then inserts them just before BEFORE, which may
 153    be either an interior element or a tail. */
 154 void
 155 list_splice (list_elem *before,
 156              list_elem *first, list_elem *last)
 157 {
 158   ASSERT (is_interior (before) || is_tail (before));
 159   if (first == last)
 160     return;
 161   last = list_prev (last);
 162
 163   ASSERT (is_interior (first));
 164   ASSERT (is_interior (last));
 165
 166   /* Cleanly remove FIRST...LAST from its current list. */
 167   first->prev->next = last->next;
 168   last->next->prev = first->prev;
 169
 170   /* Splice FIRST...LAST into new list. */
 171   first->prev = before->prev;
 172   last->next = before;
 173   before->prev->next = first;
 174   before->prev = last;
 175 }
 176
 177 /* Inserts ELEM at the beginning of LIST, so that it becomes the
 178    front in LIST. */
 179 void
 180 list_push_front (struct list *list, list_elem *elem)
 181 {
 182   list_insert (list_begin (list), elem);
 183 }
 184
 185 /* Inserts ELEM at the end of LIST, so that it becomes the
 186    back in LIST. */
 187 void
 188 list_push_back (struct list *list, list_elem *elem)
 189 {
 190   list_insert (list_end (list), elem);
 191 }
 192
 193 /* Removes ELEM from its list.  Undefined behavior if ELEM is not
 194    in a list. */
 195 list_elem *
 196 list_remove (list_elem *elem)
 197 {
 198   ASSERT (is_interior (elem));
 199   elem->prev->next = elem->next;
 200   elem->next->prev = elem->prev;
 201   return elem;
 202 }
 203
 204 /* Removes the front element from LIST and returns it.
 205    Undefined behavior if LIST is empty before removal. */
 206 list_elem *
 207 list_pop_front (struct list *list)
 208 {
 209   ASSERT (list != NULL);
 210   return list_remove (list_front (list));
 211 }
 212
 213 /* Removes the back element from LIST and returns it.
 214    Undefined behavior if LIST is empty before removal. */
 215 list_elem *
 216 list_pop_back (struct list *list)
 217 {
 218   ASSERT (list != NULL);
 219   return list_remove (list_back (list));
 220 }
 221
 222 /* Returns the front element in LIST.
 223    Undefined behavior if LIST is empty. */
 224 list_elem *
 225 list_front (struct list *list)
 226 {
 227   ASSERT (!list_empty (list));
 228   return list->head.next;
 229 }
 230
 231 /* Returns the back element in LIST.
 232    Undefined behavior if LIST is empty. */
 233 list_elem *
 234 list_back (struct list *list)
 235 {
 236   ASSERT (!list_empty (list));
 237   return list->tail.prev;
 238 }
 239
 240 /* Returns the number of elements in LIST.
 241    Runs in O(n) in the number of elements. */
 242 size_t
 243 list_size (struct list *list)
 244 {
 245   list_elem *e;
 246   size_t cnt = 0;
 247
 248   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 249     cnt++;
 250   return cnt;
 251 }
 252
 253 /* Returns true if LIST is empty, false otherwise. */
 254 bool
 255 list_empty (struct list *list)
 256 {
 257   return list_begin (list) == list_end (list);
 258 }
 259
 260 /* Reverses the order of LIST. */
 261 void
 262 list_reverse (struct list *list)
 263 {
 264   list_elem te, *e;
 265
 266   /* Swap the prev and next pointers in each element of LIST. */
 267   for (e = &list->head; e != NULL; e = e->prev)
 268     {
 269       list_elem *tep = e->prev;
 270       e->prev = e->next;
 271       e->next = tep;
 272     }
 273
 274   /* Swap the head and tail. */
 275   te = list->head;
 276   list->head = list->tail;
 277   list->tail = te;
 278 }
 279
 280 /* Merges lists AL and BL, which must each be sorted according to
 281    LESS given auxiliary data AUX, by inserting each element of BL
 282    at the proper place in AL to preserve the ordering.
 283    Runs in O(n) in the combined length of AL and BL. */
 284 void
 285 list_merge (struct list *al, struct list *bl,
 286             list_less_func *less, void *aux)
 287 {
 288   list_elem *a;
 289
 290   ASSERT (al != NULL);
 291   ASSERT (bl != NULL);
 292   ASSERT (less != NULL);
 293
 294   a = list_begin (al);
 295   while (a != list_end (al))
 296     {
 297       list_elem *b = list_begin (bl);
 298       if (less (b, a, aux))
 299         {
 300           list_splice (a, b, list_next (b));
 301           if (list_empty (bl))
 302             break;
 303         }
 304       else
 305         a = list_next (a);
 306     }
 307   list_splice (list_end (al), list_begin (bl), list_end (bl));
 308 }
 309
 310 /* Sorts LIST according to LESS given auxiliary data AUX.
 311    Runs in O(n lg n) in the number of elements in LIST. */
 312 void
 313 list_sort (struct list *list,
 314            list_less_func *less, void *aux)
 315 {
 316   struct list tmp;
 317   list_elem *middle, *last;
 318
 319   ASSERT (list != NULL);
 320   ASSERT (less != NULL);
 321
 322   /* Empty and 1-element lists are already sorted. */
 323   if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
 324     return;
 325
 326   /* Find middle of LIST.  (We're not interested in the end of
 327      the list but it's incidentally needed.) */
 328   middle = list_begin (list);
 329   last = list_next (middle);
 330   while (last != list_end (list) && list_next (last) != list_end (list))
 331     {
 332       middle = list_next (middle);
 333       last = list_next (list_next (last));
 334     }
 335
 336   /* Extract first half of LIST into a temporary list. */
 337   list_init (&tmp);
 338   list_splice (list_begin (&tmp), list_begin (list), middle);
 339
 340   /* Sort each half-list and merge the result. */
 341   list_sort (&tmp, less, aux);
 342   list_sort (list, less, aux);
 343   list_merge (list, &tmp, less, aux);
 344 }
 345
 346 /* Inserts ELEM in the proper position in LIST, which must be
 347    sorted according to LESS given auxiliary data AUX.
 348    Runs in O(n) average case in the number of elements in LIST. */
 349 void
 350 list_insert_ordered (struct list *list, list_elem *elem,
 351                      list_less_func *less, void *aux)
 352 {
 353   list_elem *e;
 354
 355   ASSERT (list != NULL);
 356   ASSERT (elem != NULL);
 357   ASSERT (less != NULL);
 358
 359   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 360     if (less (elem, e, aux))
 361       break;
 362   return list_insert (e, elem);
 363 }
 364
 365 /* Iterates through LIST and removes all but the first in each
 366    set of adjacent elements that are equal according to LESS
 367    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 368    elements from LIST are appended to DUPLICATES. */
 369 void
 370 list_unique (struct list *list, struct list *duplicates,
 371              list_less_func *less, void *aux)
 372 {
 373   list_elem *elem, *next;
 374
 375   ASSERT (list != NULL);
 376   ASSERT (less != NULL);
 377   if (list_empty (list))
 378     return;
 379
 380   elem = list_begin (list);
 381   while ((next = list_next (elem)) != list_end (list))
 382     if (!less (elem, next, aux) && !less (next, elem, aux))
 383       {
 384         list_remove (next);
 385         if (duplicates != NULL)
 386           list_push_back (duplicates, next);
 387       }
 388     else
 389       elem = next;
 390 }