1 /*
2 * BIRD Library -- Linked Lists
3 *
4 * (c) 1998 Martin Mares <mj@ucw.cz>
5 * (c) 2015, 2020-2021 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
6 *
7 * Can be freely distributed and used under the terms of the GNU GPL.
8 */
9
10 /**
11 * DOC: Linked lists
12 *
13 * The BIRD library provides a set of functions for operating on linked
14 * lists. The lists are internally represented as standard doubly linked
15 * lists with synthetic head and tail which makes all the basic operations
16 * run in constant time and contain no extra end-of-list checks. Each list
17 * is described by a &list structure, nodes can have any format as long
18 * as they start with a &node structure. If you want your nodes to belong
19 * to multiple lists at once, you can embed multiple &node structures in them
20 * and use the SKIP_BACK() macro to calculate a pointer to the start of the
21 * structure from a &node pointer, but beware of obscurity.
22 *
23 * There also exist safe linked lists (&slist, &snode and all functions
24 * being prefixed with |s_|) which support asynchronous walking very
25 * similar to that used in the &fib structure.
26 */
27
28 #include <assert.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32 #include "contrib/ucw/lists.h"
33 #include "contrib/mempattern.h"
34
35 /**
36 * add_tail - append a node to a list
37 * \p l: linked list
38 * \p n: list node
39 *
40 * add_tail() takes a node \p n and appends it at the end of the list \p l.
41 */
42 void
add_tail(list_t * l,node_t * n)43 add_tail(list_t *l, node_t *n)
44 {
45 node_t *z = &l->tail;
46
47 n->next = z;
48 n->prev = z->prev;
49 z->prev->next = n;
50 z->prev = n;
51 assert(z->next == NULL);
52 }
53
54 /**
55 * add_head - prepend a node to a list
56 * \p l: linked list
57 * \p n: list node
58 *
59 * add_head() takes a node \p n and prepends it at the start of the list \p l.
60 */
61 void
add_head(list_t * l,node_t * n)62 add_head(list_t *l, node_t *n)
63 {
64 node_t *z = &l->head;
65
66 n->next = z->next;
67 n->prev = z;
68 z->next->prev = n;
69 z->next = n;
70 assert(z->prev == NULL);
71 }
72
73 /**
74 * insert_node - insert a node to a list
75 * \p n: a new list node
76 * \p after: a node of a list
77 *
78 * Inserts a node \p n to a linked list after an already inserted
79 * node \p after.
80 */
81 void
insert_node(node_t * n,node_t * after)82 insert_node(node_t *n, node_t *after)
83 {
84 node_t *z = after->next;
85
86 n->next = z;
87 n->prev = after;
88 after->next = n;
89 z->prev = n;
90 }
91
92 /**
93 * rem_node - remove a node from a list
94 * \p n: node to be removed
95 *
96 * Removes a node \p n from the list it's linked in.
97 */
98 void
rem_node(node_t * n)99 rem_node(node_t *n)
100 {
101 node_t *z = n->prev;
102 node_t *x = n->next;
103
104 z->next = x;
105 x->prev = z;
106 n->prev = 0;
107 n->next = 0;
108 }
109
110 /**
111 * init_list - create an empty list
112 * \p l: list
113 *
114 * init_list() takes a &list structure and initializes its
115 * fields, so that it represents an empty list.
116 */
117 void
init_list(list_t * l)118 init_list(list_t *l)
119 {
120 l->head.next = &l->tail;
121 l->head.prev = NULL;
122 l->tail.next = NULL;
123 l->tail.prev = &l->head;
124 }
125
126 /**
127 * add_tail_list - concatenate two lists
128 * \p to: destination list
129 * \p l: source list
130 *
131 * This function appends all elements of the list \p l to
132 * the list \p to in constant time.
133 */
134 void
add_tail_list(list_t * to,list_t * l)135 add_tail_list(list_t *to, list_t *l)
136 {
137 node_t *p = to->tail.prev;
138 node_t *q = l->head.next;
139
140 p->next = q;
141 q->prev = p;
142 to->tail.prev = l->tail.prev;
143 }
144
145 /**
146 * list_dup - duplicate list
147 * \p to: destination list
148 * \p l: source list
149 *
150 * This function duplicates all elements of the list \p l to
151 * the list \p to in linear time.
152 *
153 * This function only works with a homogenous item size.
154 */
list_dup(list_t * dst,list_t * src,size_t itemsz)155 void list_dup(list_t *dst, list_t *src, size_t itemsz)
156 {
157 node_t *n;
158 WALK_LIST(n, *src) {
159 node_t *i = malloc(itemsz);
160 memcpy(i, n, itemsz);
161 add_tail(dst, i);
162 }
163 }
164
165 /**
166 * list_size - gets number of nodes
167 * \p l: list
168 *
169 * This function counts nodes in list \p l and returns this number.
170 */
list_size(const list_t * l)171 size_t list_size(const list_t *l)
172 {
173 size_t count = 0;
174
175 node_t *n;
176 WALK_LIST(n, *l) {
177 count++;
178 }
179
180 return count;
181 }
182
183 /**
184 * ptrlist_add - add pointer to pointer list
185 * \p to: destination list
186 * \p val: added pointer
187 * \p mm: memory context
188 */
ptrlist_add(list_t * to,void * val,knot_mm_t * mm)189 ptrnode_t *ptrlist_add(list_t *to, void *val, knot_mm_t *mm)
190 {
191 ptrnode_t *node = mm_alloc(mm , sizeof(ptrnode_t));
192 if (node == NULL) {
193 return NULL;
194 } else {
195 node->d = val;
196 }
197 add_tail(to, &node->n);
198 return node;
199 }
200
201 /**
202 * ptrlist_free - free all nodes in pointer list
203 * \p list: list nodes
204 * \p mm: memory context
205 */
ptrlist_free(list_t * list,knot_mm_t * mm)206 void ptrlist_free(list_t *list, knot_mm_t *mm)
207 {
208 node_t *n, *nxt;
209 WALK_LIST_DELSAFE(n, nxt, *list) {
210 mm_free(mm, n);
211 }
212 init_list(list);
213 }
214
215 /**
216 * ptrlist_rem - remove pointer node
217 * \p val: pointer to remove
218 * \p mm: memory context
219 */
ptrlist_rem(ptrnode_t * node,knot_mm_t * mm)220 void ptrlist_rem(ptrnode_t *node, knot_mm_t *mm)
221 {
222 rem_node(&node->n);
223 mm_free(mm, node);
224 }
225
226 /**
227 * ptrlist_deep_free - free all nodes incl referenced data
228 * \p list: list nodes
229 * \p mm: memory context
230 */
ptrlist_deep_free(list_t * l,knot_mm_t * mm)231 void ptrlist_deep_free(list_t *l, knot_mm_t *mm)
232 {
233 ptrnode_t *n;
234 WALK_LIST(n, *l) {
235 mm_free(mm, n->d);
236 }
237 ptrlist_free(l, mm);
238 }
239
ptrlist_free_custom(list_t * l,knot_mm_t * mm,ptrlist_free_cb free_cb)240 void ptrlist_free_custom(list_t *l, knot_mm_t *mm, ptrlist_free_cb free_cb)
241 {
242 ptrnode_t *n;
243 WALK_LIST(n, *l) {
244 free_cb(n->d);
245 }
246 ptrlist_free(l, mm);
247 }
248