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 /* 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_head (elem) || 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 /* Swaps the `list_elem *'s that A and B point to. */
 287 static void
 288 swap (list_elem **a, list_elem **b)
 289 {
 290   list_elem *t = *a;
 291   *a = *b;
 292   *b = t;
 293 }
 294
 295 /* Reverses the order of LIST. */
 296 void
 297 list_reverse (struct list *list)
 298 {
 299   if (!list_empty (list))
 300     {
 301       list_elem *e;
 302
 303       for (e = list_begin (list); e != list_end (list); e = e->prev)
 304         swap (&e->prev, &e->next);
 305       swap (&list->head.next, &list->tail.prev);
 306       swap (&list->head.next->prev, &list->tail.prev->next);
 307     }
 308 }
 309
 310 /* Merges lists AL and BL, which must each be sorted according to
 311    LESS given auxiliary data AUX, by inserting each element of BL
 312    at the proper place in AL to preserve the ordering.
 313    Runs in O(n) in the combined length of AL and BL. */
 314 void
 315 list_merge (struct list *al, struct list *bl,
 316             list_less_func *less, void *aux)
 317 {
 318   list_elem *a;
 319
 320   ASSERT (al != NULL);
 321   ASSERT (bl != NULL);
 322   ASSERT (less != NULL);
 323
 324   a = list_begin (al);
 325   while (a != list_end (al))
 326     {
 327       list_elem *b = list_begin (bl);
 328       if (less (b, a, aux))
 329         {
 330           list_splice (a, b, list_next (b));
 331           if (list_empty (bl))
 332             break;
 333         }
 334       else
 335         a = list_next (a);
 336     }
 337   list_splice (list_end (al), list_begin (bl), list_end (bl));
 338 }
 339
 340 /* Sorts LIST according to LESS given auxiliary data AUX.
 341    Runs in O(n lg n) in the number of elements in LIST. */
 342 void
 343 list_sort (struct list *list,
 344            list_less_func *less, void *aux)
 345 {
 346   struct list tmp;
 347   list_elem *middle, *last;
 348
 349   ASSERT (list != NULL);
 350   ASSERT (less != NULL);
 351
 352   /* Empty and 1-element lists are already sorted. */
 353   if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
 354     return;
 355
 356   /* Find middle of LIST.  (We're not interested in the end of
 357      the list but it's incidentally needed.) */
 358   middle = last = list_begin (list);
 359   while (last != list_end (list) && list_next (last) != list_end (list))
 360     {
 361       middle = list_next (middle);
 362       last = list_next (list_next (last));
 363     }
 364
 365   /* Extract first half of LIST into a temporary list. */
 366   list_init (&tmp);
 367   list_splice (list_begin (&tmp), list_begin (list), middle);
 368
 369   /* Sort each half-list and merge the result. */
 370   list_sort (&tmp, less, aux);
 371   list_sort (list, less, aux);
 372   list_merge (list, &tmp, less, aux);
 373 }
 374
 375 /* Inserts ELEM in the proper position in LIST, which must be
 376    sorted according to LESS given auxiliary data AUX.
 377    Runs in O(n) average case in the number of elements in LIST. */
 378 void
 379 list_insert_ordered (struct list *list, list_elem *elem,
 380                      list_less_func *less, void *aux)
 381 {
 382   list_elem *e;
 383
 384   ASSERT (list != NULL);
 385   ASSERT (elem != NULL);
 386   ASSERT (less != NULL);
 387
 388   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 389     if (less (elem, e, aux))
 390       break;
 391   return list_insert (e, elem);
 392 }
 393
 394 /* Iterates through LIST and removes all but the first in each
 395    set of adjacent elements that are equal according to LESS
 396    given auxiliary data AUX.  If DUPLICATES is non-null, then the
 397    elements from LIST are appended to DUPLICATES. */
 398 void
 399 list_unique (struct list *list, struct list *duplicates,
 400              list_less_func *less, void *aux)
 401 {
 402   list_elem *elem, *next;
 403
 404   ASSERT (list != NULL);
 405   ASSERT (less != NULL);
 406   if (list_empty (list))
 407     return;
 408
 409   elem = list_begin (list);
 410   while ((next = list_next (elem)) != list_end (list))
 411     if (!less (elem, next, aux) && !less (next, elem, aux))
 412       {
 413         list_remove (next);
 414         if (duplicates != NULL)
 415           list_push_back (duplicates, next);
 416       }
 417     else
 418       elem = next;
 419 }