lists.c 3.61 KB
Newer Older
1 2 3 4 5 6 7 8
/*
 *	BIRD Library -- Linked Lists
 *
 *	(c) 1998 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

Martin Mareš's avatar
Martin Mareš committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
/**
 * DOC: Linked lists
 *
 * The BIRD library provides a set of functions for operating on linked
 * lists. The lists are internally represented as standard doubly linked
 * lists with synthetic head and tail which makes all the basic operations
 * run in constant time and contain no extra end-of-list checks. Each list
 * is described by a &list structure, nodes can have any format as long
 * as they start with a &node structure. If you want your nodes to belong
 * to multiple lists at once, you can embed multiple &node structures in them
 * and use the SKIP_BACK() macro to calculate a pointer to the start of the
 * structure from a &node pointer, but beware of obscurity.
 *
 * There also exist safe linked lists (&slist, &snode and all functions
 * being prefixed with |s_|) which support asynchronous walking very
 * similar to that used in the &fib structure.
 */

27 28
#define _BIRD_LISTS_C_

29 30
#include "nest/bird.h"
#include "lib/lists.h"
31

Martin Mareš's avatar
Martin Mareš committed
32 33 34 35 36 37 38
/**
 * add_tail - append a node to a list
 * @l: linked list
 * @n: list node
 *
 * add_tail() takes a node @n and appends it at the end of the list @l.
 */
39 40 41 42 43
LIST_INLINE void
add_tail(list *l, node *n)
{
  node *z = l->tail;

44
  n->next = &l->tail_node;
45 46 47 48 49
  n->prev = z;
  z->next = n;
  l->tail = n;
}

Martin Mareš's avatar
Martin Mareš committed
50 51 52 53 54 55 56
/**
 * add_head - prepend a node to a list
 * @l: linked list
 * @n: list node
 *
 * add_head() takes a node @n and prepends it at the start of the list @l.
 */
57 58 59 60 61 62
LIST_INLINE void
add_head(list *l, node *n)
{
  node *z = l->head;

  n->next = z;
63
  n->prev = &l->head_node;
64 65 66 67
  z->prev = n;
  l->head = n;
}

Martin Mareš's avatar
Martin Mareš committed
68 69 70 71 72 73 74 75
/**
 * insert_node - insert a node to a list
 * @n: a new list node
 * @after: a node of a list
 *
 * Inserts a node @n to a linked list after an already inserted
 * node @after.
 */
76 77 78 79 80 81 82 83 84 85 86
LIST_INLINE void
insert_node(node *n, node *after)
{
  node *z = after->next;

  n->next = z;
  n->prev = after;
  after->next = n;
  z->prev = n;
}

Martin Mareš's avatar
Martin Mareš committed
87 88 89 90
/**
 * rem_node - remove a node from a list
 * @n: node to be removed
 *
91
 * Removes a node @n from the list it's linked in. Afterwards, node @n is cleared.
Martin Mareš's avatar
Martin Mareš committed
92
 */
93 94 95 96 97 98
LIST_INLINE void
rem_node(node *n)
{
  node *z = n->prev;
  node *x = n->next;

99 100 101 102 103 104
  z->next = x;
  x->prev = z;
  n->next = NULL;
  n->prev = NULL;
}

105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
/**
 * replace_node - replace a node in a list with another one
 * @old: node to be removed
 * @new: node to be inserted
 *
 * Replaces node @old in the list it's linked in with node @new.  Node
 * @old may be a copy of the original node, which is not accessed
 * through the list. The function could be called with @old == @new,
 * which just fixes neighbors' pointers in the case that the node
 * was reallocated.
 */
LIST_INLINE void
replace_node(node *old, node *new)
{
  old->next->prev = new;
  old->prev->next = new;

  new->prev = old->prev;
  new->next = old->next;
}

Martin Mareš's avatar
Martin Mareš committed
126 127 128 129 130 131 132
/**
 * init_list - create an empty list
 * @l: list
 *
 * init_list() takes a &list structure and initializes its
 * fields, so that it represents an empty list.
 */
133 134 135
LIST_INLINE void
init_list(list *l)
{
136
  l->head = &l->tail_node;
137
  l->null = NULL;
138
  l->tail = &l->head_node;
139 140
}

Martin Mareš's avatar
Martin Mareš committed
141 142 143 144 145 146 147 148
/**
 * add_tail_list - concatenate two lists
 * @to: destination list
 * @l: source list
 *
 * This function appends all elements of the list @l to
 * the list @to in constant time.
 */
149 150 151 152 153 154 155 156 157
LIST_INLINE void
add_tail_list(list *to, list *l)
{
  node *p = to->tail;
  node *q = l->head;

  p->next = q;
  q->prev = p;
  q = l->tail;
158
  q->next = &to->tail_node;
159 160
  to->tail = q;
}
Ondřej Zajíček's avatar
Ondřej Zajíček committed
161 162 163 164 165 166 167 168 169 170 171 172

LIST_INLINE uint
list_length(list *l)
{
  uint len = 0;
  node *n;

  WALK_LIST(n, *l)
    len++;

  return len;
}