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