lib/lists.c

   1 /*
   2  *      BIRD Library -- Linked Lists
   3  *
   4  *      (c) 1998 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 /**
  10  * DOC: Linked lists
  11  *
  12  * The BIRD library provides a set of functions for operating on linked
  13  * lists. The lists are internally represented as standard doubly linked
  14  * lists with synthetic head and tail which makes all the basic operations
  15  * run in constant time and contain no extra end-of-list checks. Each list
  16  * is described by a &list structure, nodes can have any format as long
  17  * as they start with a &node structure. If you want your nodes to belong
  18  * to multiple lists at once, you can embed multiple &node structures in them
  19  * and use the SKIP_BACK() macro to calculate a pointer to the start of the
  20  * structure from a &node pointer, but beware of obscurity.
  21  *
  22  * There also exist safe linked lists (&slist, &snode and all functions
  23  * being prefixed with |s_|) which support asynchronous walking very
  24  * similar to that used in the &fib structure.
  25  */
  26
  27 #define _BIRD_LISTS_C_
  28
  29 #include "nest/bird.h"
  30 #include "lib/lists.h"
  31
  32 LIST_INLINE int
  33 check_list(list *l, node *n)
  34 {
  35   if (!l)
  36   {
  37     ASSERT_DIE(n);
  38     ASSERT_DIE(n->prev);
  39
  40     do { n = n->prev; } while (n->prev);
  41
  42     l = SKIP_BACK(list, head_node, n);
  43   }
  44
  45   int seen = 0;
  46
  47   ASSERT_DIE(l->null == NULL);
  48   ASSERT_DIE(l->head != NULL);
  49   ASSERT_DIE(l->tail != NULL);
  50
  51   node *prev = &l->head_node, *cur = l->head, *next = l->head->next;
  52   while (next)
  53   {
  54     if (cur == n)
  55       seen++;
  56     ASSERT_DIE(cur->prev == prev);
  57     prev = cur;
  58     cur = next;
  59     next = next->next;
  60   }
  61
  62   ASSERT_DIE(cur == &(l->tail_node));
  63   ASSERT_DIE(!n || (seen == 1));
  64
  65   return 1;
  66 }
  67
  68 /**
  69  * add_tail - append a node to a list
  70  * @l: linked list
  71  * @n: list node
  72  *
  73  * add_tail() takes a node @n and appends it at the end of the list @l.
  74  */
  75 LIST_INLINE void
  76 add_tail(list *l, node *n)
  77 {
  78   EXPENSIVE_CHECK(check_list(l, NULL));
  79   ASSUME(n->prev == NULL);
  80   ASSUME(n->next == NULL);
  81
  82   node *z = l->tail;
  83
  84   n->next = &l->tail_node;
  85   n->prev = z;
  86   z->next = n;
  87   l->tail = n;
  88 }
  89
  90 /**
  91  * add_head - prepend a node to a list
  92  * @l: linked list
  93  * @n: list node
  94  *
  95  * add_head() takes a node @n and prepends it at the start of the list @l.
  96  */
  97 LIST_INLINE void
  98 add_head(list *l, node *n)
  99 {
 100   EXPENSIVE_CHECK(check_list(l, NULL));
 101   ASSUME(n->prev == NULL);
 102   ASSUME(n->next == NULL);
 103
 104   node *z = l->head;
 105
 106   n->next = z;
 107   n->prev = &l->head_node;
 108   z->prev = n;
 109   l->head = n;
 110 }
 111
 112 /**
 113  * insert_node - insert a node to a list
 114  * @n: a new list node
 115  * @after: a node of a list
 116  *
 117  * Inserts a node @n to a linked list after an already inserted
 118  * node @after.
 119  */
 120 LIST_INLINE void
 121 insert_node(node *n, node *after)
 122 {
 123   EXPENSIVE_CHECK(check_list(l, after));
 124   ASSUME(n->prev == NULL);
 125   ASSUME(n->next == NULL);
 126
 127   node *z = after->next;
 128
 129   n->next = z;
 130   n->prev = after;
 131   after->next = n;
 132   z->prev = n;
 133 }
 134
 135 /**
 136  * rem_node - remove a node from a list
 137  * @n: node to be removed
 138  *
 139  * Removes a node @n from the list it's linked in. Afterwards, node @n is cleared.
 140  */
 141 LIST_INLINE void
 142 rem_node(node *n)
 143 {
 144   EXPENSIVE_CHECK(check_list(NULL, n));
 145
 146   node *z = n->prev;
 147   node *x = n->next;
 148
 149   z->next = x;
 150   x->prev = z;
 151   n->next = NULL;
 152   n->prev = NULL;
 153 }
 154
 155 /**
 156  * update_node - update node after calling realloc on it
 157  * @n: node to be updated
 158  *
 159  * Fixes neighbor pointers.
 160  */
 161 LIST_INLINE void
 162 update_node(node *n)
 163 {
 164   ASSUME(n->next->prev == n->prev->next);
 165
 166   n->next->prev = n;
 167   n->prev->next = n;
 168
 169   EXPENSIVE_CHECK(check_list(NULL, n));
 170 }
 171
 172 /**
 173  * init_list - create an empty list
 174  * @l: list
 175  *
 176  * init_list() takes a &list structure and initializes its
 177  * fields, so that it represents an empty list.
 178  */
 179 LIST_INLINE void
 180 init_list(list *l)
 181 {
 182   l->head = &l->tail_node;
 183   l->null = NULL;
 184   l->tail = &l->head_node;
 185 }
 186
 187 /**
 188  * add_tail_list - concatenate two lists
 189  * @to: destination list
 190  * @l: source list
 191  *
 192  * This function appends all elements of the list @l to
 193  * the list @to in constant time.
 194  */
 195 LIST_INLINE void
 196 add_tail_list(list *to, list *l)
 197 {
 198   EXPENSIVE_CHECK(check_list(to, NULL));
 199   EXPENSIVE_CHECK(check_list(l, NULL));
 200
 201   node *p = to->tail;
 202   node *q = l->head;
 203
 204   p->next = q;
 205   q->prev = p;
 206   q = l->tail;
 207   q->next = &to->tail_node;
 208   to->tail = q;
 209
 210   EXPENSIVE_CHECK(check_list(to, NULL));
 211 }
 212
 213 LIST_INLINE uint
 214 list_length(list *l)
 215 {
 216   uint len = 0;
 217   node *n;
 218
 219   EXPENSIVE_CHECK(check_list(l, NULL));
 220
 221   WALK_LIST(n, *l)
 222     len++;
 223
 224   return len;
 225 }