Branch data Line data Source code
1 : : /* Licensed under BSD-MIT - see LICENSE file for details */
2 : : #ifndef CCAN_LIST_H
3 : : #define CCAN_LIST_H
4 : : //#define CCAN_LIST_DEBUG 1
5 : : #include <stdbool.h>
6 : : #include <assert.h>
7 : : #include <ccan/str/str.h>
8 : : #include <ccan/container_of/container_of.h>
9 : : #include <ccan/check_type/check_type.h>
10 : :
11 : : /**
12 : : * struct list_node - an entry in a doubly-linked list
13 : : * @next: next entry (self if empty)
14 : : * @prev: previous entry (self if empty)
15 : : *
16 : : * This is used as an entry in a linked list.
17 : : * Example:
18 : : * struct child {
19 : : * const char *name;
20 : : * // Linked list of all us children.
21 : : * struct list_node list;
22 : : * };
23 : : */
24 : : struct list_node
25 : : {
26 : : struct list_node *next, *prev;
27 : : };
28 : :
29 : : /**
30 : : * struct list_head - the head of a doubly-linked list
31 : : * @h: the list_head (containing next and prev pointers)
32 : : *
33 : : * This is used as the head of a linked list.
34 : : * Example:
35 : : * struct parent {
36 : : * const char *name;
37 : : * struct list_head children;
38 : : * unsigned int num_children;
39 : : * };
40 : : */
41 : : struct list_head
42 : : {
43 : : struct list_node n;
44 : : };
45 : :
46 : : /**
47 : : * list_check - check head of a list for consistency
48 : : * @h: the list_head
49 : : * @abortstr: the location to print on aborting, or NULL.
50 : : *
51 : : * Because list_nodes have redundant information, consistency checking between
52 : : * the back and forward links can be done. This is useful as a debugging check.
53 : : * If @abortstr is non-NULL, that will be printed in a diagnostic if the list
54 : : * is inconsistent, and the function will abort.
55 : : *
56 : : * Returns the list head if the list is consistent, NULL if not (it
57 : : * can never return NULL if @abortstr is set).
58 : : *
59 : : * See also: list_check_node()
60 : : *
61 : : * Example:
62 : : * static void dump_parent(struct parent *p)
63 : : * {
64 : : * struct child *c;
65 : : *
66 : : * printf("%s (%u children):\n", p->name, p->num_children);
67 : : * list_check(&p->children, "bad child list");
68 : : * list_for_each(&p->children, c, list)
69 : : * printf(" -> %s\n", c->name);
70 : : * }
71 : : */
72 : : struct list_head *list_check(const struct list_head *h, const char *abortstr);
73 : :
74 : : /**
75 : : * list_check_node - check node of a list for consistency
76 : : * @n: the list_node
77 : : * @abortstr: the location to print on aborting, or NULL.
78 : : *
79 : : * Check consistency of the list node is in (it must be in one).
80 : : *
81 : : * See also: list_check()
82 : : *
83 : : * Example:
84 : : * static void dump_child(const struct child *c)
85 : : * {
86 : : * list_check_node(&c->list, "bad child list");
87 : : * printf("%s\n", c->name);
88 : : * }
89 : : */
90 : : struct list_node *list_check_node(const struct list_node *n,
91 : : const char *abortstr);
92 : :
93 : : #define LIST_LOC __FILE__ ":" stringify(__LINE__)
94 : : #ifdef CCAN_LIST_DEBUG
95 : : #define list_debug(h, loc) list_check((h), loc)
96 : : #define list_debug_node(n, loc) list_check_node((n), loc)
97 : : #else
98 : : #define list_debug(h, loc) ((void)loc, h)
99 : : #define list_debug_node(n, loc) ((void)loc, n)
100 : : #endif
101 : :
102 : : /**
103 : : * LIST_HEAD_INIT - initializer for an empty list_head
104 : : * @name: the name of the list.
105 : : *
106 : : * Explicit initializer for an empty list.
107 : : *
108 : : * See also:
109 : : * LIST_HEAD, list_head_init()
110 : : *
111 : : * Example:
112 : : * static struct list_head my_list = LIST_HEAD_INIT(my_list);
113 : : */
114 : : #define LIST_HEAD_INIT(name) { { &(name).n, &(name).n } }
115 : :
116 : : /**
117 : : * LIST_HEAD - define and initialize an empty list_head
118 : : * @name: the name of the list.
119 : : *
120 : : * The LIST_HEAD macro defines a list_head and initializes it to an empty
121 : : * list. It can be prepended by "static" to define a static list_head.
122 : : *
123 : : * See also:
124 : : * LIST_HEAD_INIT, list_head_init()
125 : : *
126 : : * Example:
127 : : * static LIST_HEAD(my_global_list);
128 : : */
129 : : #define LIST_HEAD(name) \
130 : : struct list_head name = LIST_HEAD_INIT(name)
131 : :
132 : : /**
133 : : * list_head_init - initialize a list_head
134 : : * @h: the list_head to set to the empty list
135 : : *
136 : : * Example:
137 : : * ...
138 : : * struct parent *parent = malloc(sizeof(*parent));
139 : : *
140 : : * list_head_init(&parent->children);
141 : : * parent->num_children = 0;
142 : : */
143 : 1714 : static inline void list_head_init(struct list_head *h)
144 : : {
145 : 1714 : h->n.next = h->n.prev = &h->n;
146 : 1714 : }
147 : :
148 : : /**
149 : : * list_node_init - initialize a list_node
150 : : * @n: the list_node to link to itself.
151 : : *
152 : : * You don't need to use this normally! But it lets you list_del(@n)
153 : : * safely.
154 : : */
155 : 80 : static inline void list_node_init(struct list_node *n)
156 : : {
157 : 80 : n->next = n->prev = n;
158 : 80 : }
159 : :
160 : : /**
161 : : * list_add_after - add an entry after an existing node in a linked list
162 : : * @h: the list_head to add the node to (for debugging)
163 : : * @p: the existing list_node to add the node after
164 : : * @n: the new list_node to add to the list.
165 : : *
166 : : * The existing list_node must already be a member of the list.
167 : : * The new list_node does not need to be initialized; it will be overwritten.
168 : : *
169 : : * Example:
170 : : * struct child c1, c2, c3;
171 : : * LIST_HEAD(h);
172 : : *
173 : : * list_add_tail(&h, &c1.list);
174 : : * list_add_tail(&h, &c3.list);
175 : : * list_add_after(&h, &c1.list, &c2.list);
176 : : */
177 : : #define list_add_after(h, p, n) list_add_after_(h, p, n, LIST_LOC)
178 : 14731 : static inline void list_add_after_(struct list_head *h,
179 : : struct list_node *p,
180 : : struct list_node *n,
181 : : const char *abortstr)
182 : : {
183 : 14731 : n->next = p->next;
184 : 14731 : n->prev = p;
185 : 14731 : p->next->prev = n;
186 : 14731 : p->next = n;
187 : 14731 : (void)list_debug(h, abortstr);
188 : 14731 : }
189 : :
190 : : /**
191 : : * list_add - add an entry at the start of a linked list.
192 : : * @h: the list_head to add the node to
193 : : * @n: the list_node to add to the list.
194 : : *
195 : : * The list_node does not need to be initialized; it will be overwritten.
196 : : * Example:
197 : : * struct child *child = malloc(sizeof(*child));
198 : : *
199 : : * child->name = "marvin";
200 : : * list_add(&parent->children, &child->list);
201 : : * parent->num_children++;
202 : : */
203 : : #define list_add(h, n) list_add_(h, n, LIST_LOC)
204 : 14675 : static inline void list_add_(struct list_head *h,
205 : : struct list_node *n,
206 : : const char *abortstr)
207 : : {
208 : 14675 : list_add_after_(h, &h->n, n, abortstr);
209 : 14675 : }
210 : :
211 : : /**
212 : : * list_add_before - add an entry before an existing node in a linked list
213 : : * @h: the list_head to add the node to (for debugging)
214 : : * @p: the existing list_node to add the node before
215 : : * @n: the new list_node to add to the list.
216 : : *
217 : : * The existing list_node must already be a member of the list.
218 : : * The new list_node does not need to be initialized; it will be overwritten.
219 : : *
220 : : * Example:
221 : : * list_head_init(&h);
222 : : * list_add_tail(&h, &c1.list);
223 : : * list_add_tail(&h, &c3.list);
224 : : * list_add_before(&h, &c3.list, &c2.list);
225 : : */
226 : : #define list_add_before(h, p, n) list_add_before_(h, p, n, LIST_LOC)
227 : 4057 : static inline void list_add_before_(struct list_head *h,
228 : : struct list_node *p,
229 : : struct list_node *n,
230 : : const char *abortstr)
231 : : {
232 : 4057 : n->next = p;
233 : 4057 : n->prev = p->prev;
234 : 4057 : p->prev->next = n;
235 : 4057 : p->prev = n;
236 : 4057 : (void)list_debug(h, abortstr);
237 : 4057 : }
238 : :
239 : : /**
240 : : * list_add_tail - add an entry at the end of a linked list.
241 : : * @h: the list_head to add the node to
242 : : * @n: the list_node to add to the list.
243 : : *
244 : : * The list_node does not need to be initialized; it will be overwritten.
245 : : * Example:
246 : : * list_add_tail(&parent->children, &child->list);
247 : : * parent->num_children++;
248 : : */
249 : : #define list_add_tail(h, n) list_add_tail_(h, n, LIST_LOC)
250 : 3235 : static inline void list_add_tail_(struct list_head *h,
251 : : struct list_node *n,
252 : : const char *abortstr)
253 : : {
254 : 3235 : list_add_before_(h, &h->n, n, abortstr);
255 : 3235 : }
256 : :
257 : : /**
258 : : * list_empty - is a list empty?
259 : : * @h: the list_head
260 : : *
261 : : * If the list is empty, returns true.
262 : : *
263 : : * Example:
264 : : * assert(list_empty(&parent->children) == (parent->num_children == 0));
265 : : */
266 : : #define list_empty(h) list_empty_(h, LIST_LOC)
267 : 158067 : static inline bool list_empty_(const struct list_head *h, const char* abortstr)
268 : : {
269 : 158067 : (void)list_debug(h, abortstr);
270 : 158057 : return h->n.next == &h->n;
271 : : }
272 : :
273 : : /**
274 : : * list_empty_nodebug - is a list empty (and don't perform debug checks)?
275 : : * @h: the list_head
276 : : *
277 : : * If the list is empty, returns true.
278 : : * This differs from list_empty() in that if CCAN_LIST_DEBUG is set it
279 : : * will NOT perform debug checks. Only use this function if you REALLY
280 : : * know what you're doing.
281 : : *
282 : : * Example:
283 : : * assert(list_empty_nodebug(&parent->children) == (parent->num_children == 0));
284 : : */
285 : : #ifndef CCAN_LIST_DEBUG
286 : : #define list_empty_nodebug(h) list_empty(h)
287 : : #else
288 : : static inline bool list_empty_nodebug(const struct list_head *h)
289 : : {
290 : : return h->n.next == &h->n;
291 : : }
292 : : #endif
293 : :
294 : : /**
295 : : * list_empty_nocheck - is a list empty?
296 : : * @h: the list_head
297 : : *
298 : : * If the list is empty, returns true. This doesn't perform any
299 : : * debug check for list consistency, so it can be called without
300 : : * locks, racing with the list being modified. This is ok for
301 : : * checks where an incorrect result is not an issue (optimized
302 : : * bail out path for example).
303 : : */
304 : 130932 : static inline bool list_empty_nocheck(const struct list_head *h)
305 : : {
306 : 130932 : return h->n.next == &h->n;
307 : : }
308 : :
309 : : /**
310 : : * list_del - delete an entry from an (unknown) linked list.
311 : : * @n: the list_node to delete from the list.
312 : : *
313 : : * Note that this leaves @n in an undefined state; it can be added to
314 : : * another list, but not deleted again.
315 : : *
316 : : * See also:
317 : : * list_del_from(), list_del_init()
318 : : *
319 : : * Example:
320 : : * list_del(&child->list);
321 : : * parent->num_children--;
322 : : */
323 : : #define list_del(n) list_del_(n, LIST_LOC)
324 : 18535 : static inline void list_del_(struct list_node *n, const char* abortstr)
325 : : {
326 : 18535 : (void)list_debug_node(n, abortstr);
327 : 18535 : n->next->prev = n->prev;
328 : 18535 : n->prev->next = n->next;
329 : : #ifdef CCAN_LIST_DEBUG
330 : : /* Catch use-after-del. */
331 : 18535 : n->next = n->prev = NULL;
332 : : #endif
333 : 18535 : }
334 : :
335 : : /**
336 : : * list_del_init - delete a node, and reset it so it can be deleted again.
337 : : * @n: the list_node to be deleted.
338 : : *
339 : : * list_del(@n) or list_del_init() again after this will be safe,
340 : : * which can be useful in some cases.
341 : : *
342 : : * See also:
343 : : * list_del_from(), list_del()
344 : : *
345 : : * Example:
346 : : * list_del_init(&child->list);
347 : : * parent->num_children--;
348 : : */
349 : : #define list_del_init(n) list_del_init_(n, LIST_LOC)
350 : 60 : static inline void list_del_init_(struct list_node *n, const char *abortstr)
351 : : {
352 : 60 : list_del_(n, abortstr);
353 : 60 : list_node_init(n);
354 : 60 : }
355 : :
356 : : /**
357 : : * list_del_from - delete an entry from a known linked list.
358 : : * @h: the list_head the node is in.
359 : : * @n: the list_node to delete from the list.
360 : : *
361 : : * This explicitly indicates which list a node is expected to be in,
362 : : * which is better documentation and can catch more bugs.
363 : : *
364 : : * See also: list_del()
365 : : *
366 : : * Example:
367 : : * list_del_from(&parent->children, &child->list);
368 : : * parent->num_children--;
369 : : */
370 : 15144 : static inline void list_del_from(struct list_head *h, struct list_node *n)
371 : : {
372 : : #ifdef CCAN_LIST_DEBUG
373 : : {
374 : : /* Thorough check: make sure it was in list! */
375 : : struct list_node *i;
376 : 16872 : for (i = h->n.next; i != n; i = i->next)
377 : 1728 : assert(i != &h->n);
378 : : }
379 : : #endif /* CCAN_LIST_DEBUG */
380 : :
381 : : /* Quick test that catches a surprising number of bugs. */
382 : 15144 : assert(!list_empty(h));
383 : 15144 : list_del(n);
384 : 15144 : }
385 : :
386 : : /**
387 : : * list_swap - swap out an entry from an (unknown) linked list for a new one.
388 : : * @o: the list_node to replace from the list.
389 : : * @n: the list_node to insert in place of the old one.
390 : : *
391 : : * Note that this leaves @o in an undefined state; it can be added to
392 : : * another list, but not deleted/swapped again.
393 : : *
394 : : * See also:
395 : : * list_del()
396 : : *
397 : : * Example:
398 : : * struct child x1, x2;
399 : : * LIST_HEAD(xh);
400 : : *
401 : : * list_add(&xh, &x1.list);
402 : : * list_swap(&x1.list, &x2.list);
403 : : */
404 : : #define list_swap(o, n) list_swap_(o, n, LIST_LOC)
405 : 20 : static inline void list_swap_(struct list_node *o,
406 : : struct list_node *n,
407 : : const char* abortstr)
408 : : {
409 : 20 : (void)list_debug_node(o, abortstr);
410 : 20 : *n = *o;
411 : 20 : n->next->prev = n;
412 : 20 : n->prev->next = n;
413 : : #ifdef CCAN_LIST_DEBUG
414 : : /* Catch use-after-del. */
415 : 20 : o->next = o->prev = NULL;
416 : : #endif
417 : 20 : }
418 : :
419 : : /**
420 : : * list_entry - convert a list_node back into the structure containing it.
421 : : * @n: the list_node
422 : : * @type: the type of the entry
423 : : * @member: the list_node member of the type
424 : : *
425 : : * Example:
426 : : * // First list entry is children.next; convert back to child.
427 : : * child = list_entry(parent->children.n.next, struct child, list);
428 : : *
429 : : * See Also:
430 : : * list_top(), list_for_each()
431 : : */
432 : : #define list_entry(n, type, member) container_of(n, type, member)
433 : :
434 : : /**
435 : : * list_top - get the first entry in a list
436 : : * @h: the list_head
437 : : * @type: the type of the entry
438 : : * @member: the list_node member of the type
439 : : *
440 : : * If the list is empty, returns NULL.
441 : : *
442 : : * Example:
443 : : * struct child *first;
444 : : * first = list_top(&parent->children, struct child, list);
445 : : * if (!first)
446 : : * printf("Empty list!\n");
447 : : */
448 : : #define list_top(h, type, member) \
449 : : ((type *)list_top_((h), list_off_(type, member)))
450 : :
451 : 132944 : static inline const void *list_top_(const struct list_head *h, size_t off)
452 : : {
453 : 132944 : if (list_empty(h))
454 : 66218 : return NULL;
455 : 66726 : return (const char *)h->n.next - off;
456 : : }
457 : :
458 : : /**
459 : : * list_pop - remove the first entry in a list
460 : : * @h: the list_head
461 : : * @type: the type of the entry
462 : : * @member: the list_node member of the type
463 : : *
464 : : * If the list is empty, returns NULL.
465 : : *
466 : : * Example:
467 : : * struct child *one;
468 : : * one = list_pop(&parent->children, struct child, list);
469 : : * if (!one)
470 : : * printf("Empty list!\n");
471 : : */
472 : : #define list_pop(h, type, member) \
473 : : ((type *)list_pop_((h), list_off_(type, member)))
474 : :
475 : 3522 : static inline const void *list_pop_(const struct list_head *h, size_t off)
476 : : {
477 : : struct list_node *n;
478 : :
479 : 3522 : if (list_empty(h))
480 : 727 : return NULL;
481 : 2795 : n = h->n.next;
482 : 2795 : list_del(n);
483 : 2795 : return (const char *)n - off;
484 : : }
485 : :
486 : : /**
487 : : * list_tail - get the last entry in a list
488 : : * @h: the list_head
489 : : * @type: the type of the entry
490 : : * @member: the list_node member of the type
491 : : *
492 : : * If the list is empty, returns NULL.
493 : : *
494 : : * Example:
495 : : * struct child *last;
496 : : * last = list_tail(&parent->children, struct child, list);
497 : : * if (!last)
498 : : * printf("Empty list!\n");
499 : : */
500 : : #define list_tail(h, type, member) \
501 : : ((type *)list_tail_((h), list_off_(type, member)))
502 : :
503 : 241 : static inline const void *list_tail_(const struct list_head *h, size_t off)
504 : : {
505 : 241 : if (list_empty(h))
506 : 156 : return NULL;
507 : 85 : return (const char *)h->n.prev - off;
508 : : }
509 : :
510 : : /**
511 : : * list_for_each - iterate through a list.
512 : : * @h: the list_head (warning: evaluated multiple times!)
513 : : * @i: the structure containing the list_node
514 : : * @member: the list_node member of the structure
515 : : *
516 : : * This is a convenient wrapper to iterate @i over the entire list. It's
517 : : * a for loop, so you can break and continue as normal.
518 : : *
519 : : * Example:
520 : : * list_for_each(&parent->children, child, list)
521 : : * printf("Name: %s\n", child->name);
522 : : */
523 : : #define list_for_each(h, i, member) \
524 : : list_for_each_off(h, i, list_off_var_(i, member))
525 : :
526 : : /**
527 : : * list_for_each_rev - iterate through a list backwards.
528 : : * @h: the list_head
529 : : * @i: the structure containing the list_node
530 : : * @member: the list_node member of the structure
531 : : *
532 : : * This is a convenient wrapper to iterate @i over the entire list. It's
533 : : * a for loop, so you can break and continue as normal.
534 : : *
535 : : * Example:
536 : : * list_for_each_rev(&parent->children, child, list)
537 : : * printf("Name: %s\n", child->name);
538 : : */
539 : : #define list_for_each_rev(h, i, member) \
540 : : list_for_each_rev_off(h, i, list_off_var_(i, member))
541 : :
542 : : /**
543 : : * list_for_each_rev_safe - iterate through a list backwards,
544 : : * maybe during deletion
545 : : * @h: the list_head
546 : : * @i: the structure containing the list_node
547 : : * @nxt: the structure containing the list_node
548 : : * @member: the list_node member of the structure
549 : : *
550 : : * This is a convenient wrapper to iterate @i over the entire list backwards.
551 : : * It's a for loop, so you can break and continue as normal. The extra
552 : : * variable * @nxt is used to hold the next element, so you can delete @i
553 : : * from the list.
554 : : *
555 : : * Example:
556 : : * struct child *next;
557 : : * list_for_each_rev_safe(&parent->children, child, next, list) {
558 : : * printf("Name: %s\n", child->name);
559 : : * }
560 : : */
561 : : #define list_for_each_rev_safe(h, i, nxt, member) \
562 : : list_for_each_rev_safe_off(h, i, nxt, list_off_var_(i, member))
563 : :
564 : : /**
565 : : * list_for_each_safe - iterate through a list, maybe during deletion
566 : : * @h: the list_head
567 : : * @i: the structure containing the list_node
568 : : * @nxt: the structure containing the list_node
569 : : * @member: the list_node member of the structure
570 : : *
571 : : * This is a convenient wrapper to iterate @i over the entire list. It's
572 : : * a for loop, so you can break and continue as normal. The extra variable
573 : : * @nxt is used to hold the next element, so you can delete @i from the list.
574 : : *
575 : : * Example:
576 : : * list_for_each_safe(&parent->children, child, next, list) {
577 : : * list_del(&child->list);
578 : : * parent->num_children--;
579 : : * }
580 : : */
581 : : #define list_for_each_safe(h, i, nxt, member) \
582 : : list_for_each_safe_off(h, i, nxt, list_off_var_(i, member))
583 : :
584 : : /**
585 : : * list_next - get the next entry in a list
586 : : * @h: the list_head
587 : : * @i: a pointer to an entry in the list.
588 : : * @member: the list_node member of the structure
589 : : *
590 : : * If @i was the last entry in the list, returns NULL.
591 : : *
592 : : * Example:
593 : : * struct child *second;
594 : : * second = list_next(&parent->children, first, list);
595 : : * if (!second)
596 : : * printf("No second child!\n");
597 : : */
598 : : #define list_next(h, i, member) \
599 : : ((list_typeof(i))list_entry_or_null(list_debug(h, \
600 : : __FILE__ ":" stringify(__LINE__)), \
601 : : (i)->member.next, \
602 : : list_off_var_((i), member)))
603 : :
604 : : /**
605 : : * list_prev - get the previous entry in a list
606 : : * @h: the list_head
607 : : * @i: a pointer to an entry in the list.
608 : : * @member: the list_node member of the structure
609 : : *
610 : : * If @i was the first entry in the list, returns NULL.
611 : : *
612 : : * Example:
613 : : * first = list_prev(&parent->children, second, list);
614 : : * if (!first)
615 : : * printf("Can't go back to first child?!\n");
616 : : */
617 : : #define list_prev(h, i, member) \
618 : : ((list_typeof(i))list_entry_or_null(list_debug(h, \
619 : : __FILE__ ":" stringify(__LINE__)), \
620 : : (i)->member.prev, \
621 : : list_off_var_((i), member)))
622 : :
623 : : /**
624 : : * list_append_list - empty one list onto the end of another.
625 : : * @to: the list to append into
626 : : * @from: the list to empty.
627 : : *
628 : : * This takes the entire contents of @from and moves it to the end of
629 : : * @to. After this @from will be empty.
630 : : *
631 : : * Example:
632 : : * struct list_head adopter;
633 : : *
634 : : * list_append_list(&adopter, &parent->children);
635 : : * assert(list_empty(&parent->children));
636 : : * parent->num_children = 0;
637 : : */
638 : : #define list_append_list(t, f) list_append_list_(t, f, \
639 : : __FILE__ ":" stringify(__LINE__))
640 : 50 : static inline void list_append_list_(struct list_head *to,
641 : : struct list_head *from,
642 : : const char *abortstr)
643 : : {
644 : 50 : struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
645 : 50 : struct list_node *to_tail = list_debug(to, abortstr)->n.prev;
646 : :
647 : : /* Sew in head and entire list. */
648 : 50 : to->n.prev = from_tail;
649 : 50 : from_tail->next = &to->n;
650 : 50 : to_tail->next = &from->n;
651 : 50 : from->n.prev = to_tail;
652 : :
653 : : /* Now remove head. */
654 : 50 : list_del(&from->n);
655 : 50 : list_head_init(from);
656 : 50 : }
657 : :
658 : : /**
659 : : * list_prepend_list - empty one list into the start of another.
660 : : * @to: the list to prepend into
661 : : * @from: the list to empty.
662 : : *
663 : : * This takes the entire contents of @from and moves it to the start
664 : : * of @to. After this @from will be empty.
665 : : *
666 : : * Example:
667 : : * list_prepend_list(&adopter, &parent->children);
668 : : * assert(list_empty(&parent->children));
669 : : * parent->num_children = 0;
670 : : */
671 : : #define list_prepend_list(t, f) list_prepend_list_(t, f, LIST_LOC)
672 : 50 : static inline void list_prepend_list_(struct list_head *to,
673 : : struct list_head *from,
674 : : const char *abortstr)
675 : : {
676 : 50 : struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
677 : 50 : struct list_node *to_head = list_debug(to, abortstr)->n.next;
678 : :
679 : : /* Sew in head and entire list. */
680 : 50 : to->n.next = &from->n;
681 : 50 : from->n.prev = &to->n;
682 : 50 : to_head->prev = from_tail;
683 : 50 : from_tail->next = to_head;
684 : :
685 : : /* Now remove head. */
686 : 50 : list_del(&from->n);
687 : 50 : list_head_init(from);
688 : 50 : }
689 : :
690 : : /* internal macros, do not use directly */
691 : : #define list_for_each_off_dir_(h, i, off, dir) \
692 : : for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir, \
693 : : (off)); \
694 : : list_node_from_off_((void *)i, (off)) != &(h)->n; \
695 : : i = list_node_to_off_(list_node_from_off_((void *)i, (off))->dir, \
696 : : (off)))
697 : :
698 : : #define list_for_each_safe_off_dir_(h, i, nxt, off, dir) \
699 : : for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir, \
700 : : (off)), \
701 : : nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir, \
702 : : (off)); \
703 : : list_node_from_off_(i, (off)) != &(h)->n; \
704 : : i = nxt, \
705 : : nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir, \
706 : : (off)))
707 : :
708 : : /**
709 : : * list_for_each_off - iterate through a list of memory regions.
710 : : * @h: the list_head
711 : : * @i: the pointer to a memory region which contains list node data.
712 : : * @off: offset(relative to @i) at which list node data resides.
713 : : *
714 : : * This is a low-level wrapper to iterate @i over the entire list, used to
715 : : * implement all oher, more high-level, for-each constructs. It's a for loop,
716 : : * so you can break and continue as normal.
717 : : *
718 : : * WARNING! Being the low-level macro that it is, this wrapper doesn't know
719 : : * nor care about the type of @i. The only assumption made is that @i points
720 : : * to a chunk of memory that at some @offset, relative to @i, contains a
721 : : * properly filled `struct list_node' which in turn contains pointers to
722 : : * memory chunks and it's turtles all the way down. With all that in mind
723 : : * remember that given the wrong pointer/offset couple this macro will
724 : : * happily churn all you memory until SEGFAULT stops it, in other words
725 : : * caveat emptor.
726 : : *
727 : : * It is worth mentioning that one of legitimate use-cases for that wrapper
728 : : * is operation on opaque types with known offset for `struct list_node'
729 : : * member(preferably 0), because it allows you not to disclose the type of
730 : : * @i.
731 : : *
732 : : * Example:
733 : : * list_for_each_off(&parent->children, child,
734 : : * offsetof(struct child, list))
735 : : * printf("Name: %s\n", child->name);
736 : : */
737 : : #define list_for_each_off(h, i, off) \
738 : : list_for_each_off_dir_((h),(i),(off),next)
739 : :
740 : : /**
741 : : * list_for_each_rev_off - iterate through a list of memory regions backwards
742 : : * @h: the list_head
743 : : * @i: the pointer to a memory region which contains list node data.
744 : : * @off: offset(relative to @i) at which list node data resides.
745 : : *
746 : : * See list_for_each_off for details
747 : : */
748 : : #define list_for_each_rev_off(h, i, off) \
749 : : list_for_each_off_dir_((h),(i),(off),prev)
750 : :
751 : : /**
752 : : * list_for_each_safe_off - iterate through a list of memory regions, maybe
753 : : * during deletion
754 : : * @h: the list_head
755 : : * @i: the pointer to a memory region which contains list node data.
756 : : * @nxt: the structure containing the list_node
757 : : * @off: offset(relative to @i) at which list node data resides.
758 : : *
759 : : * For details see `list_for_each_off' and `list_for_each_safe'
760 : : * descriptions.
761 : : *
762 : : * Example:
763 : : * list_for_each_safe_off(&parent->children, child,
764 : : * next, offsetof(struct child, list))
765 : : * printf("Name: %s\n", child->name);
766 : : */
767 : : #define list_for_each_safe_off(h, i, nxt, off) \
768 : : list_for_each_safe_off_dir_((h),(i),(nxt),(off),next)
769 : :
770 : : /**
771 : : * list_for_each_rev_safe_off - iterate backwards through a list of
772 : : * memory regions, maybe during deletion
773 : : * @h: the list_head
774 : : * @i: the pointer to a memory region which contains list node data.
775 : : * @nxt: the structure containing the list_node
776 : : * @off: offset(relative to @i) at which list node data resides.
777 : : *
778 : : * For details see `list_for_each_rev_off' and `list_for_each_rev_safe'
779 : : * descriptions.
780 : : *
781 : : * Example:
782 : : * list_for_each_rev_safe_off(&parent->children, child,
783 : : * next, offsetof(struct child, list))
784 : : * printf("Name: %s\n", child->name);
785 : : */
786 : : #define list_for_each_rev_safe_off(h, i, nxt, off) \
787 : : list_for_each_safe_off_dir_((h),(i),(nxt),(off),prev)
788 : :
789 : : /* Other -off variants. */
790 : : #define list_entry_off(n, type, off) \
791 : : ((type *)list_node_from_off_((n), (off)))
792 : :
793 : : #define list_head_off(h, type, off) \
794 : : ((type *)list_head_off((h), (off)))
795 : :
796 : : #define list_tail_off(h, type, off) \
797 : : ((type *)list_tail_((h), (off)))
798 : :
799 : : #define list_add_off(h, n, off) \
800 : : list_add((h), list_node_from_off_((n), (off)))
801 : :
802 : : #define list_del_off(n, off) \
803 : : list_del(list_node_from_off_((n), (off)))
804 : :
805 : : #define list_del_from_off(h, n, off) \
806 : : list_del_from(h, list_node_from_off_((n), (off)))
807 : :
808 : : /* Offset helper functions so we only single-evaluate. */
809 : 313484 : static inline void *list_node_to_off_(struct list_node *node, size_t off)
810 : : {
811 : 313484 : return (void *)((char *)node - off);
812 : : }
813 : 483081 : static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
814 : : {
815 : 483081 : return (struct list_node *)((char *)ptr + off);
816 : : }
817 : :
818 : : /* Get the offset of the member, but make sure it's a list_node. */
819 : : #define list_off_(type, member) \
820 : : (container_off(type, member) + \
821 : : check_type(((type *)0)->member, struct list_node))
822 : :
823 : : #define list_off_var_(var, member) \
824 : : (container_off_var(var, member) + \
825 : : check_type(var->member, struct list_node))
826 : :
827 : : #if HAVE_TYPEOF
828 : : #define list_typeof(var) typeof(var)
829 : : #else
830 : : #define list_typeof(var) void *
831 : : #endif
832 : :
833 : : /* Returns member, or NULL if at end of list. */
834 : 203 : static inline void *list_entry_or_null(const struct list_head *h,
835 : : const struct list_node *n,
836 : : size_t off)
837 : : {
838 : 203 : if (n == &h->n)
839 : 81 : return NULL;
840 : 122 : return (char *)n - off;
841 : : }
842 : : #endif /* CCAN_LIST_H */
|
