]>
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 | ||
29 | typedef struct list { /* In fact two overlayed nodes */ | |
30 | struct node *head, *null, *tail; | |
31 | } list; | |
32 | ||
33 | #define NODE (node *) | |
34 | #define HEAD(list) ((void *)((list).head)) | |
35 | #define TAIL(list) ((void *)((list).tail)) | |
d5356072 OZ |
36 | #define NODE_NEXT(n) ((void *)((NODE (n))->next)) |
37 | #define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; n=NODE_NEXT(n)) | |
d92882be | 38 | #define WALK_LIST_DELSAFE(n,nxt,list) \ |
d5356072 | 39 | for(n=HEAD(list); nxt=NODE_NEXT(n); n=(void *) nxt) |
b933281e OZ |
40 | /* WALK_LIST_FIRST supposes that called code removes each processed node */ |
41 | #define WALK_LIST_FIRST(n,list) \ | |
42 | while(n=HEAD(list), (NODE (n))->next) | |
b6628a8c MM |
43 | #define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \ |
44 | n=(void *)((NODE (n))->prev)) | |
45 | #define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \ | |
46 | for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv) | |
aea2dcab | 47 | |
58ef912c MM |
48 | #define EMPTY_LIST(list) (!(list).head->next) |
49 | ||
50 | void add_tail(list *, node *); | |
51 | void add_head(list *, node *); | |
52 | void rem_node(node *); | |
53 | void add_tail_list(list *, list *); | |
54 | void init_list(list *); | |
55 | void insert_node(node *, node *); | |
56 | ||
57 | #ifndef _BIRD_LISTS_C_ | |
58 | #define LIST_INLINE extern inline | |
18c8241a | 59 | #include "lib/lists.c" |
58ef912c MM |
60 | #undef LIST_INLINE |
61 | #else | |
62 | #define LIST_INLINE | |
63 | #endif | |
64 | ||
65 | #endif |