]>
Commit | Line | Data |
---|---|---|
58ef912c MM |
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 | ||
7722938d MM |
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 | ||
58ef912c MM |
27 | #define _BIRD_LISTS_C_ |
28 | ||
1feea03e MM |
29 | #include "nest/bird.h" |
30 | #include "lib/lists.h" | |
58ef912c | 31 | |
7722938d MM |
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 | */ | |
58ef912c MM |
39 | LIST_INLINE void |
40 | add_tail(list *l, node *n) | |
41 | { | |
42 | node *z = l->tail; | |
43 | ||
54bb032d | 44 | n->next = &l->tail_node; |
58ef912c MM |
45 | n->prev = z; |
46 | z->next = n; | |
47 | l->tail = n; | |
48 | } | |
49 | ||
7722938d MM |
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 | */ | |
58ef912c MM |
57 | LIST_INLINE void |
58 | add_head(list *l, node *n) | |
59 | { | |
60 | node *z = l->head; | |
61 | ||
62 | n->next = z; | |
54bb032d | 63 | n->prev = &l->head_node; |
58ef912c MM |
64 | z->prev = n; |
65 | l->head = n; | |
66 | } | |
67 | ||
7722938d MM |
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 | */ | |
58ef912c MM |
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 | ||
7722938d MM |
87 | /** |
88 | * rem_node - remove a node from a list | |
89 | * @n: node to be removed | |
90 | * | |
665b8e52 | 91 | * Removes a node @n from the list it's linked in. Afterwards, node @n is cleared. |
7722938d | 92 | */ |
58ef912c MM |
93 | LIST_INLINE void |
94 | rem_node(node *n) | |
95 | { | |
96 | node *z = n->prev; | |
97 | node *x = n->next; | |
98 | ||
6a8d3f1c OZ |
99 | z->next = x; |
100 | x->prev = z; | |
101 | n->next = NULL; | |
102 | n->prev = NULL; | |
103 | } | |
104 | ||
bf139664 OZ |
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 | ||
7722938d MM |
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 | */ | |
58ef912c MM |
133 | LIST_INLINE void |
134 | init_list(list *l) | |
135 | { | |
54bb032d | 136 | l->head = &l->tail_node; |
58ef912c | 137 | l->null = NULL; |
54bb032d | 138 | l->tail = &l->head_node; |
58ef912c MM |
139 | } |
140 | ||
7722938d MM |
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 | */ | |
58ef912c MM |
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; | |
54bb032d | 158 | q->next = &to->tail_node; |
58ef912c MM |
159 | to->tail = q; |
160 | } | |
d15b0b0a OZ |
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 | } |