]>
git.ipfire.org Git - thirdparty/bird.git/blob - lib/lists.h
2 * BIRD Library -- Linked Lists
4 * (c) 1998 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
10 #define _BIRD_LISTS_H_
13 * I admit the list structure is very tricky and also somewhat awkward,
14 * but it's both efficient and easy to manipulate once one understands the
15 * basic trick: The list head always contains two synthetic nodes which are
16 * always present in the list: the head and the tail. But as the `next'
17 * entry of the tail and the `prev' entry of the head are both NULL, the
18 * nodes can overlap each other:
21 * null head_node.prev tail_node.next
26 struct node
*next
, *prev
;
29 typedef union list
{ /* In fact two overlayed nodes */
30 struct { /* Head node */
31 struct node head_node
;
34 struct { /* Tail node */
36 struct node tail_node
;
38 struct { /* Split to separate pointers */
47 #define HEAD(list) ((void *)((list).head))
48 #define TAIL(list) ((void *)((list).tail))
49 #define NODE_NEXT(n) ((void *)((NODE (n))->next))
50 #define NODE_VALID(n) ((NODE (n))->next)
51 #define WALK_LIST(n,list) for(n=HEAD(list); NODE_VALID(n); n=NODE_NEXT(n))
52 #define WALK_LIST2(n,nn,list,pos) \
53 for(nn=(list).head; NODE_VALID(nn) && (n=SKIP_BACK(typeof(*n),pos,nn)); nn=nn->next)
54 #define WALK_LIST_DELSAFE(n,nxt,list) \
55 for(n=HEAD(list); nxt=NODE_NEXT(n); n=(void *) nxt)
56 /* WALK_LIST_FIRST supposes that called code removes each processed node */
57 #define WALK_LIST_FIRST(n,list) \
58 while(n=HEAD(list), (NODE (n))->next)
59 #define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
60 n=(void *)((NODE (n))->prev))
61 #define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
62 for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
64 #define EMPTY_LIST(list) (!(list).head->next)
67 #ifndef _BIRD_LISTS_C_
68 #define LIST_INLINE static inline
69 #include "lib/lists.c"
72 #else /* _BIRD_LISTS_C_ */
74 void add_tail(list
*, node
*);
75 void add_head(list
*, node
*);
76 void rem_node(node
*);
77 void add_tail_list(list
*, list
*);
78 void init_list(list
*);
79 void insert_node(node
*, node
*);