]>
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 | } | |
153 | ||
154 | #ifdef TEST | |
155 | ||
156 | #include "lib/resource.h" | |
157 | #include <stdio.h> | |
158 | ||
159 | void dump(char *c, slist *a) | |
160 | { | |
161 | snode *x; | |
162 | ||
163 | puts(c); | |
164 | for(x=SHEAD(*a); x; x=x->next) | |
165 | { | |
166 | siterator *i, *j; | |
167 | printf("%p", x); | |
168 | j = (siterator *) x; | |
169 | for(i=x->readers; i; i=i->next) | |
170 | { | |
171 | if (i->prev != j) | |
172 | printf(" ???"); | |
173 | j = i; | |
174 | printf(" [%p:%p]", i, i->node); | |
175 | } | |
176 | putchar('\n'); | |
177 | } | |
178 | puts("---"); | |
179 | } | |
180 | ||
181 | int main(void) | |
182 | { | |
183 | slist a, b; | |
184 | snode *x, *y; | |
185 | siterator i, j; | |
186 | ||
187 | s_init_list(&a); | |
188 | s_init_list(&b); | |
189 | x = xmalloc(sizeof(*x)); | |
190 | s_add_tail(&a, x); | |
191 | x = xmalloc(sizeof(*x)); | |
192 | s_add_tail(&a, x); | |
193 | x = xmalloc(sizeof(*x)); | |
194 | s_add_tail(&a, x); | |
195 | dump("1", &a); | |
196 | ||
197 | s_init(&i, &a); | |
198 | s_init(&j, &a); | |
199 | dump("2", &a); | |
200 | ||
201 | x = s_get(&i); | |
202 | printf("Got %p\n", x); | |
203 | dump("3", &a); | |
204 | ||
205 | s_put(&i, x->next); | |
206 | dump("4", &a); | |
207 | ||
208 | y = s_get(&j); | |
209 | while (y) | |
210 | { | |
211 | s_put(&j, y); | |
212 | dump("5*", &a); | |
213 | y = s_get(&j)->next; | |
214 | } | |
215 | ||
216 | dump("5 done", &a); | |
217 | ||
218 | s_rem_node(a.head->next); | |
219 | dump("6 (deletion)", &a); | |
220 | ||
221 | s_put(&i, s_get(&i)->next); | |
222 | dump("6 (relink)", &a); | |
223 | ||
224 | x = xmalloc(sizeof(*x)); | |
225 | s_add_tail(&b, x); | |
226 | dump("7 (second list)", &b); | |
227 | ||
228 | s_add_tail_list(&b, &a); | |
229 | dump("8 (after merge)", &b); | |
230 | ||
231 | return 0; | |
232 | } | |
233 | ||
234 | #endif |