pintos-os.org Git - pintos-anon/blob - src/lib/list.c

   1 #include "list.h"
   2 #include "debug.h"
   3
   4 void
   5 list_init (struct list *list)
   6 {
   7   list->head.prev = NULL;
   8   list->head.next = &list->tail;
   9   list->tail.prev = &list->head;
  10   list->tail.next = NULL;
  11 }
  12
  13 list_elem *
  14 list_begin (struct list *list)
  15 {
  16   return list->head.next;
  17 }
  18
  19 list_elem *
  20 list_end (struct list *list)
  21 {
  22   return &list->tail;
  23 }
  24
  25 static inline bool
  26 is_head (list_elem *elem)
  27 {
  28   return elem != NULL && elem->prev == NULL && elem->next != NULL;
  29 }
  30
  31 static inline bool
  32 is_real (list_elem *elem)
  33 {
  34   return elem != NULL && elem->prev != NULL && elem->next != NULL;
  35 }
  36
  37 static inline bool
  38 is_tail (list_elem *elem)
  39 {
  40   return elem != NULL && elem->prev != NULL && elem->next == NULL;
  41 }
  42
  43 list_elem *
  44 list_next (list_elem *elem)
  45 {
  46   ASSERT (is_real (elem));
  47   return elem->next;
  48 }
  49
  50 list_elem *
  51 list_prev (list_elem *elem)
  52 {
  53   ASSERT (is_real (elem) || is_tail (elem));
  54   return elem->prev;
  55 }
  56
  57 void
  58 list_insert (list_elem *before, list_elem *elem)
  59 {
  60   ASSERT (is_real (before) || is_tail (before));
  61   ASSERT (elem != NULL);
  62
  63   elem->prev = before->prev;
  64   elem->next = before;
  65   before->prev->next = elem;
  66   before->prev = elem;
  67 }
  68
  69 void
  70 list_splice (list_elem *target,
  71              list_elem *first, list_elem *last)
  72 {
  73   ASSERT (is_real (target) || is_tail (target));
  74   if (first == last)
  75     return;
  76   last = list_prev (last);
  77
  78   ASSERT (is_real (first));
  79   ASSERT (is_real (last));
  80
  81   /* Cleanly remove FIRST...LAST from its current list. */
  82   first->prev->next = last->next;
  83   last->next->prev = first->prev;
  84
  85   /* Splice FIRST...LAST into new list. */
  86   first->prev = target->prev;
  87   last->next = target;
  88   target->prev->next = first;
  89   target->prev = last;
  90 }
  91
  92 void
  93 list_push_front (struct list *list, list_elem *elem)
  94 {
  95   list_insert (list_begin (list), elem);
  96 }
  97
  98 void
  99 list_push_back (struct list *list, list_elem *elem)
 100 {
 101   list_insert (list_end (list), elem);
 102 }
 103
 104 static list_elem *
 105 remove_item (list_elem *elem)
 106 {
 107   ASSERT (is_real (elem));
 108   elem->prev->next = elem->next;
 109   elem->next->prev = elem->prev;
 110   return elem;
 111 }
 112
 113 void
 114 list_remove (list_elem *elem)
 115 {
 116   remove_item (elem);
 117 }
 118
 119 list_elem *
 120 list_pop_front (struct list *list)
 121 {
 122   return remove_item (list_front (list));
 123 }
 124
 125 list_elem *
 126 list_pop_back (struct list *list)
 127 {
 128   return remove_item (list_back (list));
 129 }
 130
 131 list_elem *
 132 list_front (struct list *list)
 133 {
 134   return list_begin (list);
 135 }
 136
 137 list_elem *
 138 list_back (struct list *list)
 139 {
 140   return list_prev (list_end (list));
 141 }
 142
 143 size_t
 144 list_size (struct list *list)
 145 {
 146   list_elem *elem;
 147   size_t cnt = 0;
 148
 149   for (elem = list_begin (list); elem != list_end (list); elem = elem->next)
 150     cnt++;
 151   return cnt;
 152 }
 153
 154 bool
 155 list_empty (struct list *list)
 156 {
 157   return list_begin (list) == list_end (list);
 158 }
 159
 160 void
 161 list_reverse (struct list *list)
 162 {
 163   list_elem te, *e;
 164
 165   for (e = &list->head; e != NULL; e = e->prev)
 166     {
 167       list_elem *tep = e->prev;
 168       e->prev = e->next;
 169       e->next = tep;
 170     }
 171
 172   te = list->head;
 173   list->head = list->tail;
 174   list->tail = te;
 175 }
 176
 177 void
 178 list_merge (struct list *al, struct list *bl,
 179             list_less_func *less, void *aux)
 180 {
 181   list_elem *a;
 182
 183   ASSERT (al != NULL);
 184   ASSERT (bl != NULL);
 185   ASSERT (less != NULL);
 186
 187   a = list_begin (al);
 188   while (a != list_end (al))
 189     {
 190       list_elem *b = list_begin (bl);
 191       if (less (b, a, aux))
 192         {
 193           list_splice (a, b, list_next (b));
 194           if (list_empty (bl))
 195             break;
 196         }
 197       else
 198         a = list_next (a);
 199     }
 200   list_splice (list_end (al), list_begin (bl), list_end (bl));
 201 }
 202
 203 void
 204 list_sort (struct list *list,
 205            list_less_func *less, void *aux)
 206 {
 207   struct list tmp;
 208   list_elem *middle, *last;
 209
 210   ASSERT (list != NULL);
 211   ASSERT (less != NULL);
 212
 213   /* Empty and 1-element lists are already sorted. */
 214   if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
 215     return;
 216
 217   /* Find middle of LIST.  (We're not interested in the end of
 218      the list but it's incidentally needed.) */
 219   middle = list_begin (list);
 220   last = list_next (middle);
 221   while (last != list_end (list) && list_next (last) != list_end (list))
 222     {
 223       middle = list_next (middle);
 224       last = list_next (list_next (last));
 225     }
 226
 227   /* Extract first half of LIST into a temporary list. */
 228   list_init (&tmp);
 229   list_splice (list_begin (&tmp), list_begin (list), middle);
 230
 231   /* Sort each half-list and merge the result. */
 232   list_sort (&tmp, less, aux);
 233   list_sort (list, less, aux);
 234   list_merge (list, &tmp, less, aux);
 235 }
 236
 237 void
 238 list_insert_ordered (struct list *list, list_elem *elem,
 239                      list_less_func *less, void *aux)
 240 {
 241   list_elem *e;
 242
 243   ASSERT (list != NULL);
 244   ASSERT (elem != NULL);
 245   ASSERT (less != NULL);
 246
 247   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 248     if (less (elem, e, aux))
 249       break;
 250   return list_insert (e, elem);
 251 }
 252
 253 void
 254 list_unique (struct list *list,
 255              list_less_func *less, void *aux)
 256 {
 257   list_elem *elem, *next;
 258
 259   ASSERT (list != NULL);
 260   ASSERT (less != NULL);
 261   if (list_empty (list))
 262     return;
 263
 264   elem = list_begin (list);
 265   while ((next = list_next (elem)) != list_end (list))
 266     if (!less (elem, next, aux) && !less (next, elem, aux))
 267       list_remove (next);
 268     else
 269       elem = next;
 270 }