]>
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) \ |
f4a60a9b OZ |
55 | for(n=HEAD(list); nxt=NODE_NEXT(n); n=(void *) nxt) |
56 | #define WALK_LIST2_DELSAFE(n,nn,nxt,list,pos) \ | |
57 | for(nn=HEAD(list); (nxt=nn->next) && (n=SKIP_BACK(typeof(*n),pos,nn)); nn=nxt) | |
58 | ||
b933281e OZ |
59 | /* WALK_LIST_FIRST supposes that called code removes each processed node */ |
60 | #define WALK_LIST_FIRST(n,list) \ | |
61 | while(n=HEAD(list), (NODE (n))->next) | |
b6628a8c MM |
62 | #define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \ |
63 | n=(void *)((NODE (n))->prev)) | |
64 | #define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \ | |
65 | for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv) | |
aea2dcab | 66 | |
58ef912c MM |
67 | #define EMPTY_LIST(list) (!(list).head->next) |
68 | ||
85a3639d PT |
69 | |
70 | #ifndef _BIRD_LISTS_C_ | |
71 | #define LIST_INLINE static inline | |
72 | #include "lib/lists.c" | |
73 | #undef LIST_INLINE | |
74 | ||
75 | #else /* _BIRD_LISTS_C_ */ | |
76 | #define LIST_INLINE | |
58ef912c MM |
77 | void add_tail(list *, node *); |
78 | void add_head(list *, node *); | |
79 | void rem_node(node *); | |
80 | void add_tail_list(list *, list *); | |
81 | void init_list(list *); | |
82 | void insert_node(node *, node *); | |
d15b0b0a | 83 | uint list_length(list *); |
58ef912c MM |
84 | #endif |
85 | ||
86 | #endif |