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  * init_list - create an empty list
 105  * @l: list
 106  *
 107  * init_list() takes a &list structure and initializes its
 108  * fields, so that it represents an empty list.
 109  */
 110 LIST_INLINE void
 111 init_list(list *l)
 112 {
 113   l->head = (node *) &l->null;
 114   l->null = NULL;
 115   l->tail = (node *) &l->head;
 116 }
 117
 118 /**
 119  * add_tail_list - concatenate two lists
 120  * @to: destination list
 121  * @l: source list
 122  *
 123  * This function appends all elements of the list @l to
 124  * the list @to in constant time.
 125  */
 126 LIST_INLINE void
 127 add_tail_list(list *to, list *l)
 128 {
 129   node *p = to->tail;
 130   node *q = l->head;
 131
 132   p->next = q;
 133   q->prev = p;
 134   q = l->tail;
 135   q->next = (node *) &to->null;
 136   to->tail = q;
 137 }