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 struct list_elem *
  14 list_begin (struct list *list)
  15 {
  16   return list->head.next;
  17 }
  18
  19 struct list_elem *
  20 list_end (struct list *list)
  21 {
  22   return &list->tail;
  23 }
  24
  25 static inline bool
  26 is_head (struct list_elem *elem)
  27 {
  28   return elem != NULL && elem->prev == NULL && elem->next != NULL;
  29 }
  30
  31 static inline bool
  32 is_real (struct list_elem *elem)
  33 {
  34   return elem != NULL && elem->prev != NULL && elem->next != NULL;
  35 }
  36
  37 static inline bool
  38 is_tail (struct list_elem *elem)
  39 {
  40   return elem != NULL && elem->prev != NULL && elem->next == NULL;
  41 }
  42
  43 struct list_elem *
  44 list_next (struct list_elem *elem)
  45 {
  46   ASSERT (is_real (elem));
  47   return elem->next;
  48 }
  49
  50 struct list_elem *
  51 list_prev (struct list_elem *elem)
  52 {
  53   ASSERT (is_real (elem) || is_tail (elem));
  54   return elem->prev;
  55 }
  56
  57 void
  58 list_insert (struct list_elem *before, struct 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 (struct list_elem *target,
  71              struct list_elem *first, struct 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, struct list_elem *elem)
  94 {
  95   list_insert (list_begin (list), elem);
  96 }
  97
  98 void
  99 list_push_back (struct list *list, struct list_elem *elem)
 100 {
 101   list_insert (list_end (list), elem);
 102 }
 103
 104 static struct list_elem *
 105 remove_item (struct 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 (struct list_elem *elem)
 115 {
 116   remove_item (elem);
 117 }
 118
 119 struct list_elem *
 120 list_pop_front (struct list *list)
 121 {
 122   return remove_item (list_front (list));
 123 }
 124
 125 struct list_elem *
 126 list_pop_back (struct list *list)
 127 {
 128   return remove_item (list_back (list));
 129 }
 130
 131 struct list_elem *
 132 list_front (struct list *list)
 133 {
 134   return list_begin (list);
 135 }
 136
 137 struct 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   struct 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   struct list_elem *e;
 164   struct list_elem te;
 165
 166   for (e = &list->head; e != NULL; e = e->prev)
 167     {
 168       struct list_elem *tep = e->prev;
 169       e->prev = e->next;
 170       e->next = tep;
 171     }
 172
 173   te = list->head;
 174   list->head = list->tail;
 175   list->tail = te;
 176 }
 177
 178 void
 179 list_merge (struct list *al, struct list *bl,
 180             list_less_func *less, void *aux)
 181 {
 182   struct list_elem *a;
 183
 184   ASSERT (al != NULL);
 185   ASSERT (bl != NULL);
 186   ASSERT (less != NULL);
 187
 188   a = list_begin (al);
 189   while (a != list_end (al))
 190     {
 191       struct list_elem *b = list_begin (bl);
 192       if (less (b, a, aux))
 193         {
 194           list_splice (a, b, list_next (b));
 195           if (list_empty (bl))
 196             break;
 197         }
 198       else
 199         a = list_next (a);
 200     }
 201   list_splice (list_end (al), list_begin (bl), list_end (bl));
 202 }
 203
 204 void
 205 list_sort (struct list *list,
 206            list_less_func *less, void *aux)
 207 {
 208   struct list tmp;
 209   struct list_elem *middle, *last;
 210
 211   ASSERT (list != NULL);
 212   ASSERT (less != NULL);
 213
 214   /* Empty and 1-element lists are already sorted. */
 215   if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
 216     return;
 217
 218   /* Find middle of LIST.  (We're not interested in the end of
 219      the list but it's incidentally needed.) */
 220   middle = list_begin (list);
 221   last = list_next (middle);
 222   while (last != list_end (list) && list_next (last) != list_end (list))
 223     {
 224       middle = list_next (middle);
 225       last = list_next (list_next (last));
 226     }
 227
 228   /* Extract first half of LIST into a temporary list. */
 229   list_init (&tmp);
 230   list_splice (list_begin (&tmp), list_begin (list), middle);
 231
 232   /* Sort each half-list and merge the result. */
 233   list_sort (&tmp, less, aux);
 234   list_sort (list, less, aux);
 235   list_merge (list, &tmp, less, aux);
 236 }
 237
 238 void
 239 list_insert_ordered (struct list *list, struct list_elem *elem,
 240                      list_less_func *less, void *aux)
 241 {
 242   struct list_elem *e;
 243
 244   ASSERT (list != NULL);
 245   ASSERT (elem != NULL);
 246   ASSERT (less != NULL);
 247
 248   for (e = list_begin (list); e != list_end (list); e = list_next (e))
 249     if (less (elem, e, aux))
 250       break;
 251   return list_insert (e, elem);
 252 }
 253
 254 void
 255 list_unique (struct list *list,
 256              list_less_func *less, void *aux)
 257 {
 258   struct list_elem *elem, *next;
 259
 260   ASSERT (list != NULL);
 261   ASSERT (less != NULL);
 262   if (list_empty (list))
 263     return;
 264
 265   elem = list_begin (list);
 266   while ((next = list_next (elem)) != list_end (list))
 267     if (!less (elem, next, aux) && !less (next, elem, aux))
 268       list_remove (next);
 269     else
 270       elem = next;
 271 }