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 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 list_elem *
 110 list_prev (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 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 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 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 (list_elem *before, 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 (list_elem *before,
 182              list_elem *first, 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, 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, list_elem *elem)
 215 {
 216   list_insert (list_end (list), elem);
 217 }
 218
 219 /* Removes ELEM from its list.  Undefined behavior if ELEM is not
 220    in a list. */
 221 list_elem *
 222 list_remove (list_elem *elem)
 223 {
 224   ASSERT (is_interior (elem));
 225   elem->prev->next = elem->next;
 226   elem->next->prev = elem->prev;
 227   return elem;
 228 }
 229
 230 /* Removes the front element from LIST and returns it.
 231    Undefined behavior if LIST is empty before removal. */
 232 list_elem *
 233 list_pop_front (struct list *list)
 234 {
 235   ASSERT (list != NULL);
 236   return list_remove (list_front (list));
 237 }
 238
 239 /* Removes the back element from LIST and returns it.
 240    Undefined behavior if LIST is empty before removal. */
 241 list_elem *
 242 list_pop_back (struct list *list)
 243 {
 244   ASSERT (list != NULL);
 245   return list_remove (list_back (list));
 246 }
 247
 248 /* Returns the front element in LIST.
 249    Undefined behavior if LIST is empty. */
 250 list_elem *
 251 list_front (struct list *list)
 252 {
 253   ASSERT (!list_empty (list));
 254   return list->head.next;
 255 }
 256
 257 /* Returns the back element in LIST.
 258    Undefined behavior if LIST is empty. */
 259 list_elem *
 260 list_back (struct list *list)
 261 {
 262   ASSERT (!list_empty (list));
 263   return list->tail.prev;
 264 }
 265
 266 /* Returns the number of elements in LIST.
 267    Runs in O(n) in the number of elements. */
 268 size_t
 269 list_size (struct list *list)
 270 {
 271   list_elem *e;
 272   size_t cnt = 0;
 273
 274   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 275     cnt++;
 276   return cnt;
 277 }
 278
 279 /* Returns true if LIST is empty, false otherwise. */
 280 bool
 281 list_empty (struct list *list)
 282 {
 283   return list_begin (list) == list_end (list);
 284 }
 285
 286 /* Reverses the order of LIST. */
 287 void
 288 list_reverse (struct list *list)
 289 {
 290   list_elem te, *e;
 291
 292   /* Swap the prev and next pointers in each element of LIST. */
 293   for (e = &list->head; e != NULL; e = e->prev)
 294     {
 295       list_elem *tep = e->prev;
 296       e->prev = e->next;
 297       e->next = tep;
 298     }
 299
 300   /* Swap the head and tail. */
 301   te = list->head;
 302   list->head = list->tail;
 303   list->tail = te;
 304 }
 305
 306 /* Merges lists AL and BL, which must each be sorted according to
 307    LESS given auxiliary data AUX, by inserting each element of BL
 308    at the proper place in AL to preserve the ordering.
 309    Runs in O(n) in the combined length of AL and BL. */
 310 void
 311 list_merge (struct list *al, struct list *bl,
 312             list_less_func *less, void *aux)
 313 {
 314   list_elem *a;
 315
 316   ASSERT (al != NULL);
 317   ASSERT (bl != NULL);
 318   ASSERT (less != NULL);
 319
 320   a = list_begin (al);
 321   while (a != list_end (al))
 322     {
 323       list_elem *b = list_begin (bl);
 324       if (less (b, a, aux))
 325         {
 326           list_splice (a, b, list_next (b));
 327           if (list_empty (bl))
 328             break;
 329         }
 330       else
 331         a = list_next (a);
 332     }
 333   list_splice (list_end (al), list_begin (bl), list_end (bl));
 334 }
 335
 336 /* Sorts LIST according to LESS given auxiliary data AUX.
 337    Runs in O(n lg n) in the number of elements in LIST. */
 338 void
 339 list_sort (struct list *list,
 340            list_less_func *less, void *aux)
 341 {
 342   struct list tmp;
 343   list_elem *middle, *last;
 344
 345   ASSERT (list != NULL);
 346   ASSERT (less != NULL);
 347
 348   /* Empty and 1-element lists are already sorted. */
 349   if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
 350     return;
 351
 352   /* Find middle of LIST.  (We're not interested in the end of
 353      the list but it's incidentally needed.) */
 354   middle = list_begin (list);
 355   last = list_next (middle);
 356   while (last != list_end (list) && list_next (last) != list_end (list))
 357     {
 358       middle = list_next (middle);
 359       last = list_next (list_next (last));
 360     }
 361
 362   /* Extract first half of LIST into a temporary list. */
 363   list_init (&tmp);
 364   list_splice (list_begin (&tmp), list_begin (list), middle);
 365
 366   /* Sort each half-list and merge the result. */
 367   list_sort (&tmp, less, aux);
 368   list_sort (list, less, aux);
 369   list_merge (list, &tmp, less, aux);
 370 }
 371
 372 /* Inserts ELEM in the proper position in LIST, which must be
 373    sorted according to LESS given auxiliary data AUX.
 374    Runs in O(n) average case in the number of elements in LIST. */
 375 void
 376 list_insert_ordered (struct list *list, list_elem *elem,
 377                      list_less_func *less, void *aux)
 378 {
 379   list_elem *e;
 380
 381   ASSERT (list != NULL);
 382   ASSERT (elem != NULL);
 383   ASSERT (less != NULL);
 384
 385   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 386     if (less (elem, e, aux))
 387       break;
 388   return list_insert (e, elem);
 389 }
 390
 391 /* Iterates through LIST and removes all but the first in each
 392    set of adjacent elements that are equal according to LESS
 393    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 394    elements from LIST are appended to DUPLICATES. */
 395 void
 396 list_unique (struct list *list, struct list *duplicates,
 397              list_less_func *less, void *aux)
 398 {
 399   list_elem *elem, *next;
 400
 401   ASSERT (list != NULL);
 402   ASSERT (less != NULL);
 403   if (list_empty (list))
 404     return;
 405
 406   elem = list_begin (list);
 407   while ((next = list_next (elem)) != list_end (list))
 408     if (!less (elem, next, aux) && !less (next, elem, aux))
 409       {
 410         list_remove (next);
 411         if (duplicates != NULL)
 412           list_push_back (duplicates, next);
 413       }
 414     else
 415       elem = next;
 416 }