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
s_merge(snode * from,snode * to)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 *
s_get(siterator * i)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
s_put(siterator * i,snode * n)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
s_add_tail(slist * l,snode * n)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
s_add_head(slist * l,snode * n)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
s_insert_node(snode * n,snode * after)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
s_rem_node(snode * n)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
s_init_list(slist * l)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
s_add_tail_list(slist * to,slist * l)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