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 = (node *) &l->null;
  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 = (node *) &l->head;
  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.
  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 }
 102
 103 /**
 104  * rem2_node - remove a node from a list, with cleanup
 105  * @n: node to be removed
 106  *
 107  * Removes a node @n from the list it's linked in and resets its pointers to NULL.
 108  * Useful if you want to distinguish between linked and unlinked nodes.
 109  */
 110 LIST_INLINE void
 111 rem2_node(node *n)
 112 {
 113   node *z = n->prev;
 114   node *x = n->next;
 115
 116   z->next = x;
 117   x->prev = z;
 118   n->next = NULL;
 119   n->prev = NULL;
 120 }
 121
 122 /**
 123  * replace_node - replace a node in a list with another one
 124  * @old: node to be removed
 125  * @new: node to be inserted
 126  *
 127  * Replaces node @old in the list it's linked in with node @new.  Node
 128  * @old may be a copy of the original node, which is not accessed
 129  * through the list. The function could be called with @old == @new,
 130  * which just fixes neighbors' pointers in the case that the node
 131  * was reallocated.
 132  */
 133 LIST_INLINE void
 134 replace_node(node *old, node *new)
 135 {
 136   old->next->prev = new;
 137   old->prev->next = new;
 138
 139   new->prev = old->prev;
 140   new->next = old->next;
 141 }
 142
 143 /**
 144  * init_list - create an empty list
 145  * @l: list
 146  *
 147  * init_list() takes a &list structure and initializes its
 148  * fields, so that it represents an empty list.
 149  */
 150 LIST_INLINE void
 151 init_list(list *l)
 152 {
 153   l->head = (node *) &l->null;
 154   l->null = NULL;
 155   l->tail = (node *) &l->head;
 156 }
 157
 158 /**
 159  * add_tail_list - concatenate two lists
 160  * @to: destination list
 161  * @l: source list
 162  *
 163  * This function appends all elements of the list @l to
 164  * the list @to in constant time.
 165  */
 166 LIST_INLINE void
 167 add_tail_list(list *to, list *l)
 168 {
 169   node *p = to->tail;
 170   node *q = l->head;
 171
 172   p->next = q;
 173   q->prev = p;
 174   q = l->tail;
 175   q->next = (node *) &to->null;
 176   to->tail = q;
 177 }