![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to slists.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib|
Return to slists.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib |
1.1 misho 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;
64:
65: i->prev = NULL;
66: i->next = NULL;
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