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 /* Puts 'elem' in the position currently occupied by 'position'.
  58  * Afterward, 'position' is not part of a list. */
  59 void
  60 list_replace(struct list *element, const struct list *position)
  61 {
  62     element->next = position->next;
  63     element->next->prev = element;
  64     element->prev = position->prev;
  65     element->prev->next = element;
  66 }
  67
  68 /* Removes 'elem' from its list and returns the element that followed it.
  69    Undefined behavior if 'elem' is not in a list. */
  70 struct list *
  71 list_remove(struct list *elem)
  72 {
  73   elem->prev->next = elem->next;
  74   elem->next->prev = elem->prev;
  75   return elem->next;
  76 }
  77
  78 /* Removes the front element from 'list' and returns it.  Undefined behavior if
  79    'list' is empty before removal. */
  80 struct list *
  81 list_pop_front(struct list *list)
  82 {
  83   struct list *front = list->next;
  84   list_remove(front);
  85   return front;
  86 }
  87
  88 /* Removes the back element from 'list' and returns it.
  89    Undefined behavior if 'list' is empty before removal. */
  90 struct list *
  91 list_pop_back(struct list *list)
  92 {
  93   struct list *back = list->prev;
  94   list_remove(back);
  95   return back;
  96 }
  97
  98 /* Returns the front element in 'list'.
  99    Undefined behavior if 'list' is empty. */
 100 struct list *
 101 list_front(struct list *list)
 102 {
 103   assert(!list_is_empty(list));
 104   return list->next;
 105 }
 106
 107 /* Returns the back element in 'list'.
 108    Undefined behavior if 'list' is empty. */
 109 struct list *
 110 list_back(struct list *list)
 111 {
 112   assert(!list_is_empty(list));
 113   return list->prev;
 114 }
 115
 116 /* Returns the number of elements in 'list'.
 117    Runs in O(n) in the number of elements. */
 118 size_t
 119 list_size(const struct list *list)
 120 {
 121   const struct list *e;
 122   size_t cnt = 0;
 123
 124   for (e = list->next; e != list; e = e->next)
 125     cnt++;
 126   return cnt;
 127 }
 128
 129 /* Returns true if 'list' is empty, false otherwise. */
 130 bool
 131 list_is_empty(const struct list *list)
 132 {
 133   return list->next == list;
 134 }