]>
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 | ||
9 | #ifndef _BIRD_LISTS_H_ | |
10 | #define _BIRD_LISTS_H_ | |
11 | ||
a2d01907 MM |
12 | /* |
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: | |
19 | * | |
20 | * head head_node.next | |
21 | * null head_node.prev tail_node.next | |
22 | * tail tail_node.prev | |
23 | */ | |
24 | ||
58ef912c MM |
25 | typedef struct node { |
26 | struct node *next, *prev; | |
27 | } node; | |
28 | ||
54bb032d JMM |
29 | typedef union list { /* In fact two overlayed nodes */ |
30 | struct { /* Head node */ | |
31 | struct node head_node; | |
32 | void *head_padding; | |
33 | }; | |
34 | struct { /* Tail node */ | |
35 | void *tail_padding; | |
36 | struct node tail_node; | |
37 | }; | |
38 | struct { /* Split to separate pointers */ | |
39 | struct node *head; | |
40 | struct node *null; | |
41 | struct node *tail; | |
42 | }; | |
58ef912c MM |
43 | } list; |
44 | ||
54bb032d | 45 | |
58ef912c MM |
46 | #define NODE (node *) |
47 | #define HEAD(list) ((void *)((list).head)) | |
48 | #define TAIL(list) ((void *)((list).tail)) | |
d5356072 | 49 | #define NODE_NEXT(n) ((void *)((NODE (n))->next)) |
fc06fb62 OZ |
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)) | |
0c791f87 OZ |
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) | |
d92882be | 54 | #define WALK_LIST_DELSAFE(n,nxt,list) \ |
d5356072 | 55 | for(n=HEAD(list); nxt=NODE_NEXT(n); n=(void *) nxt) |
b933281e OZ |
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) | |
b6628a8c MM |
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) | |
aea2dcab | 63 | |
58ef912c MM |
64 | #define EMPTY_LIST(list) (!(list).head->next) |
65 | ||
85a3639d PT |
66 | |
67 | #ifndef _BIRD_LISTS_C_ | |
68 | #define LIST_INLINE static inline | |
69 | #include "lib/lists.c" | |
70 | #undef LIST_INLINE | |
71 | ||
72 | #else /* _BIRD_LISTS_C_ */ | |
73 | #define LIST_INLINE | |
58ef912c MM |
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 *); | |
58ef912c MM |
80 | #endif |
81 | ||
82 | #endif |