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 /**
  33  * add_tail - append a node to a list
  34  * @l: linked list
  35  * @n: list node
  36  *
  37  * add_tail() takes a node @n and appends it at the end of the list @l.
  38  */
  39 LIST_INLINE void
  40 add_tail(list *l, node *n)
  41 {
  42   node *z = l->tail;
  43
  44   n->next = &l->tail_node;
  45   n->prev = z;
  46   z->next = n;
  47   l->tail = n;
  48 }
  49
  50 /**
  51  * add_head - prepend a node to a list
  52  * @l: linked list
  53  * @n: list node
  54  *
  55  * add_head() takes a node @n and prepends it at the start of the list @l.
  56  */
  57 LIST_INLINE void
  58 add_head(list *l, node *n)
  59 {
  60   node *z = l->head;
  61
  62   n->next = z;
  63   n->prev = &l->head_node;
  64   z->prev = n;
  65   l->head = n;
  66 }
  67
  68 /**
  69  * insert_node - insert a node to a list
  70  * @n: a new list node
  71  * @after: a node of a list
  72  *
  73  * Inserts a node @n to a linked list after an already inserted
  74  * node @after.
  75  */
  76 LIST_INLINE void
  77 insert_node(node *n, node *after)
  78 {
  79   node *z = after->next;
  80
  81   n->next = z;
  82   n->prev = after;
  83   after->next = n;
  84   z->prev = n;
  85 }
  86
  87 /**
  88  * rem_node - remove a node from a list
  89  * @n: node to be removed
  90  *
  91  * Removes a node @n from the list it's linked in. Afterwards, node @n is cleared.
  92  */
  93 LIST_INLINE void
  94 rem_node(node *n)
  95 {
  96   node *z = n->prev;
  97   node *x = n->next;
  98
  99   z->next = x;
 100   x->prev = z;
 101   n->next = NULL;
 102   n->prev = NULL;
 103 }
 104
 105 /**
 106  * replace_node - replace a node in a list with another one
 107  * @old: node to be removed
 108  * @new: node to be inserted
 109  *
 110  * Replaces node @old in the list it's linked in with node @new.  Node
 111  * @old may be a copy of the original node, which is not accessed
 112  * through the list. The function could be called with @old == @new,
 113  * which just fixes neighbors' pointers in the case that the node
 114  * was reallocated.
 115  */
 116 LIST_INLINE void
 117 replace_node(node *old, node *new)
 118 {
 119   old->next->prev = new;
 120   old->prev->next = new;
 121
 122   new->prev = old->prev;
 123   new->next = old->next;
 124 }
 125
 126 /**
 127  * init_list - create an empty list
 128  * @l: list
 129  *
 130  * init_list() takes a &list structure and initializes its
 131  * fields, so that it represents an empty list.
 132  */
 133 LIST_INLINE void
 134 init_list(list *l)
 135 {
 136   l->head = &l->tail_node;
 137   l->null = NULL;
 138   l->tail = &l->head_node;
 139 }
 140
 141 /**
 142  * add_tail_list - concatenate two lists
 143  * @to: destination list
 144  * @l: source list
 145  *
 146  * This function appends all elements of the list @l to
 147  * the list @to in constant time.
 148  */
 149 LIST_INLINE void
 150 add_tail_list(list *to, list *l)
 151 {
 152   node *p = to->tail;
 153   node *q = l->head;
 154
 155   p->next = q;
 156   q->prev = p;
 157   q = l->tail;
 158   q->next = &to->tail_node;
 159   to->tail = q;
 160 }
 161
 162 LIST_INLINE uint
 163 list_length(list *l)
 164 {
 165   uint len = 0;
 166   node *n;
 167
 168   WALK_LIST(n, *l)
 169     len++;
 170
 171   return len;
 172 }