]>
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 | #define _BIRD_SLISTS_C_ | |
10 | ||
11 | #include "nest/bird.h" | |
12 | #include "lib/slists.h" | |
13 | ||
14 | static inline void | |
15 | s_merge(snode *from, snode *to) | |
16 | { | |
17 | siterator *f, *g; | |
18 | ||
19 | if (!(f = from->readers)) | |
20 | return; | |
21 | if (!(g = to->readers)) | |
22 | { | |
23 | /* Fast path */ | |
24 | to->readers = f; | |
25 | f->prev = (siterator *) to; | |
26 | fixup: | |
27 | while (f && f->node) | |
28 | { | |
29 | f->node = NULL; | |
30 | f = f->next; | |
31 | } | |
32 | return; | |
33 | } | |
34 | /* Really merging */ | |
35 | while (g->next) | |
36 | g = g->next; | |
37 | g->next = f; | |
38 | f->prev = g; | |
39 | goto fixup; | |
40 | } | |
41 | ||
42 | snode * | |
43 | s_get(siterator *i) | |
44 | { | |
45 | siterator *f, *g; | |
46 | snode *n; | |
47 | ||
48 | if (!(n = i->node)) | |
49 | { | |
50 | /* | |
51 | * No node found. We have to walk the iterator list backwards | |
52 | * to find where are we linked. | |
53 | */ | |
54 | f = i; | |
55 | while (!f->null) | |
56 | f = f->prev; | |
57 | n = (snode *) f; | |
58 | } | |
59 | f = i->prev; /* Maybe the snode itself */ | |
60 | g = i->next; | |
61 | f->next = g; | |
62 | if (g) | |
63 | g->prev = f; | |
02a9eeeb OZ |
64 | |
65 | i->prev = NULL; | |
66 | i->next = NULL; | |
a05406e6 MM |
67 | return n; |
68 | } | |
69 | ||
70 | void | |
71 | s_put(siterator *i, snode *n) | |
72 | { | |
73 | siterator *f; | |
74 | ||
75 | i->node = n; | |
76 | if (f = n->readers) | |
77 | f->prev = i; | |
78 | i->next = f; | |
79 | n->readers = i; | |
80 | i->prev = (siterator *) n; | |
81 | i->null = NULL; | |
82 | } | |
83 | ||
84 | void | |
85 | s_add_tail(slist *l, snode *n) | |
86 | { | |
87 | snode *z = l->tail; | |
88 | ||
89 | n->next = (snode *) &l->null; | |
90 | n->prev = z; | |
91 | z->next = n; | |
92 | l->tail = n; | |
93 | n->readers = NULL; | |
94 | } | |
95 | ||
96 | void | |
97 | s_add_head(slist *l, snode *n) | |
98 | { | |
99 | snode *z = l->head; | |
100 | ||
101 | n->next = z; | |
102 | n->prev = (snode *) &l->head; | |
103 | z->prev = n; | |
104 | l->head = n; | |
105 | n->readers = NULL; | |
106 | } | |
107 | ||
108 | void | |
109 | s_insert_node(snode *n, snode *after) | |
110 | { | |
111 | snode *z = after->next; | |
112 | ||
113 | n->next = z; | |
114 | n->prev = after; | |
115 | after->next = n; | |
116 | z->prev = n; | |
117 | n->readers = NULL; | |
118 | } | |
119 | ||
120 | void | |
121 | s_rem_node(snode *n) | |
122 | { | |
123 | snode *z = n->prev; | |
124 | snode *x = n->next; | |
125 | ||
126 | z->next = x; | |
127 | x->prev = z; | |
128 | s_merge(n, x); | |
129 | } | |
130 | ||
131 | void | |
132 | s_init_list(slist *l) | |
133 | { | |
134 | l->head = (snode *) &l->null; | |
135 | l->null = NULL; | |
136 | l->tail = (snode *) &l->head; | |
137 | l->tail_readers = NULL; | |
138 | } | |
139 | ||
140 | void | |
141 | s_add_tail_list(slist *to, slist *l) | |
142 | { | |
143 | snode *p = to->tail; | |
144 | snode *q = l->head; | |
145 | ||
146 | p->next = q; | |
147 | q->prev = p; | |
148 | q = l->tail; | |
149 | q->next = (snode *) &to->null; | |
150 | to->tail = q; | |
151 | s_merge((snode *) &l->null, (snode *) &to->null); | |
152 | } |