]>
Commit | Line | Data |
---|---|---|
a05406e6 MM |
1 | /* |
2 | * BIRD Library -- Safe 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_SLISTS_H_ | |
10 | #define _BIRD_SLISTS_H_ | |
11 | ||
12 | /* | |
13 | * These linked lists work in a way similar to standard lists defined | |
14 | * in lib/lists.h, but in addition to all usual list functions they | |
15 | * provide fast deletion/insertion/everything-safe asynchronous | |
16 | * walking. | |
17 | * | |
18 | * Example: | |
19 | * slist l; | |
20 | * siterator i; | |
21 | * snode *n; | |
22 | * | |
23 | * s_init(&i, &l); // Initialize iteration | |
24 | * ... | |
25 | * n = s_get(&i); // Some time later, fetch present | |
26 | * // value of the iterator and unlink it | |
27 | * // from the list. | |
28 | * while (n->next) { | |
29 | * ... | |
30 | * if (decided_to_stop) { | |
31 | * s_put(&i, n); // Store current position (maybe even | |
32 | * // that we stay at list end) | |
33 | * return; // and return | |
34 | * } | |
35 | * ... | |
36 | * } | |
37 | * // After finishing, don't link the iterator back | |
38 | */ | |
39 | ||
40 | typedef struct snode { | |
41 | struct snode *next, *prev; | |
42 | struct siterator *readers; | |
43 | } snode; | |
44 | ||
45 | typedef struct slist { /* In fact two overlayed snodes */ | |
46 | struct snode *head, *null, *tail; | |
47 | struct siterator *tail_readers; | |
48 | } slist; | |
49 | ||
50 | typedef struct siterator { | |
51 | /* | |
52 | * Caution: Layout of this structure depends hard on layout of the | |
53 | * snode. Our `next' must be at position of snode `readers' | |
54 | * field, our `null' must be at position of `prev' and it must | |
55 | * contain NULL in order to distinguish between siterator | |
56 | * and snode (snodes with NULL `prev' field never carry | |
57 | * iterators). You are not expected to understand this. | |
58 | */ | |
59 | struct siterator *prev, *null, *next; | |
60 | /* | |
61 | * For recently merged nodes this can be NULL, but then it's NULL | |
62 | * for all successors as well. This is done to speed up iterator | |
63 | * merging when there are lots of deletions. | |
64 | */ | |
65 | snode *node; | |
66 | } siterator; | |
67 | ||
68 | #define SNODE (snode *) | |
69 | #define SHEAD(list) ((void *)((list).head)) | |
70 | #define STAIL(list) ((void *)((list).tail)) | |
71 | #define WALK_SLIST(n,list) for(n=SHEAD(list);(SNODE (n))->next; \ | |
72 | n=(void *)((SNODE (n))->next)) | |
73 | #define WALK_SLIST_DELSAFE(n,nxt,list) \ | |
74 | for(n=SHEAD(list); nxt=(void *)((SNODE (n))->next); n=(void *) nxt) | |
75 | #define EMPTY_SLIST(list) (!(list).head->next) | |
76 | ||
77 | void s_add_tail(slist *, snode *); | |
78 | void s_add_head(slist *, snode *); | |
79 | void s_rem_node(snode *); | |
80 | void s_add_tail_list(slist *, slist *); | |
81 | void s_init_list(slist *); | |
82 | void s_insert_node(snode *, snode *); | |
83 | ||
84 | snode *s_get(siterator *); | |
85 | void s_put(siterator *, snode *n); | |
86 | static inline void s_init(siterator *i, slist *l) { s_put(i, SHEAD(*l)); } | |
02a9eeeb | 87 | static inline int s_is_used(siterator *i) { return (i->prev != NULL); } |
a05406e6 MM |
88 | |
89 | #endif |