lib/list.c

   1 #include "list.h"
   2 #include <assert.h>
   3
   4 /* Initializes 'list' as an empty list. */
   5 void
   6 list_init(struct list *list)
   7 {
   8     list->next = list->prev = list;
   9 }
  10
  11 /* Inserts 'elem' just before 'before'. */
  12 void
  13 list_insert(struct list *before, struct list *elem)
  14 {
  15   elem->prev = before->prev;
  16   elem->next = before;
  17   before->prev->next = elem;
  18   before->prev = elem;
  19 }
  20
  21 /* Removes elements 'first' though 'last' (exclusive) from their current list,
  22    then inserts them just before 'before'. */
  23 void
  24 list_splice(struct list *before, struct list *first, struct list *last)
  25 {
  26   if (first == last)
  27     return;
  28   last = last->prev;
  29
  30   /* Cleanly remove 'first'...'last' from its current list. */
  31   first->prev->next = last->next;
  32   last->next->prev = first->prev;
  33
  34   /* Splice 'first'...'last' into new list. */
  35   first->prev = before->prev;
  36   last->next = before;
  37   before->prev->next = first;
  38   before->prev = last;
  39 }
  40
  41 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
  42    'list'. */
  43 void
  44 list_push_front(struct list *list, struct list *elem)
  45 {
  46   list_insert(list->next, elem);
  47 }
  48
  49 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
  50  * 'list'. */
  51 void
  52 list_push_back(struct list *list, struct list *elem)
  53 {
  54   list_insert(list, elem);
  55 }
  56
  57 /* Removes 'elem' from its list and returns the element that followed it.
  58    Undefined behavior if 'elem' is not in a list. */
  59 struct list *
  60 list_remove(struct list *elem)
  61 {
  62   elem->prev->next = elem->next;
  63   elem->next->prev = elem->prev;
  64   return elem->next;
  65 }
  66
  67 /* Removes the front element from 'list' and returns it.  Undefined behavior if
  68    'list' is empty before removal. */
  69 struct list *
  70 list_pop_front(struct list *list)
  71 {
  72   struct list *front = list->next;
  73   list_remove(front);
  74   return front;
  75 }
  76
  77 /* Removes the back element from 'list' and returns it.
  78    Undefined behavior if 'list' is empty before removal. */
  79 struct list *
  80 list_pop_back(struct list *list)
  81 {
  82   struct list *back = list->prev;
  83   list_remove(back);
  84   return back;
  85 }
  86
  87 /* Returns the front element in 'list'.
  88    Undefined behavior if 'list' is empty. */
  89 struct list *
  90 list_front(struct list *list)
  91 {
  92   assert(!list_is_empty(list));
  93   return list->next;
  94 }
  95
  96 /* Returns the back element in 'list'.
  97    Undefined behavior if 'list' is empty. */
  98 struct list *
  99 list_back(struct list *list)
 100 {
 101   assert(!list_is_empty(list));
 102   return list->prev;
 103 }
 104
 105 /* Returns the number of elements in 'list'.
 106    Runs in O(n) in the number of elements. */
 107 size_t
 108 list_size(const struct list *list)
 109 {
 110   const struct list *e;
 111   size_t cnt = 0;
 112
 113   for (e = list->next; e != list; e = e->next)
 114     cnt++;
 115   return cnt;
 116 }
 117
 118 /* Returns true if 'list' is empty, false otherwise. */
 119 bool
 120 list_is_empty(const struct list *list)
 121 {
 122   return list->next == list;
 123 }