Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / lists.c @ 6b3f1a54

History | View | Annotate | Download (3.61 KB)

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
}