Blame


1 375b78fb 2009-08-23 rsc #include <u.h>
2 375b78fb 2009-08-23 rsc #include <libc.h>
3 375b78fb 2009-08-23 rsc #include <bio.h>
4 375b78fb 2009-08-23 rsc #include <avl.h>
5 375b78fb 2009-08-23 rsc
6 375b78fb 2009-08-23 rsc /*
7 375b78fb 2009-08-23 rsc * In-memory database stored as self-balancing AVL tree.
8 375b78fb 2009-08-23 rsc * See Lewis & Denenberg, Data Structures and Their Algorithms.
9 375b78fb 2009-08-23 rsc */
10 375b78fb 2009-08-23 rsc
11 375b78fb 2009-08-23 rsc static void
12 375b78fb 2009-08-23 rsc singleleft(Avl **tp, Avl *p)
13 375b78fb 2009-08-23 rsc {
14 375b78fb 2009-08-23 rsc int l, r2;
15 375b78fb 2009-08-23 rsc Avl *a, *c;
16 375b78fb 2009-08-23 rsc
17 375b78fb 2009-08-23 rsc a = *tp;
18 375b78fb 2009-08-23 rsc c = a->n[1];
19 375b78fb 2009-08-23 rsc
20 375b78fb 2009-08-23 rsc r2 = c->bal;
21 375b78fb 2009-08-23 rsc l = (r2 > 0? r2: 0)+1 - a->bal;
22 375b78fb 2009-08-23 rsc
23 375b78fb 2009-08-23 rsc if((a->n[1] = c->n[0]) != nil)
24 375b78fb 2009-08-23 rsc a->n[1]->p = a;
25 375b78fb 2009-08-23 rsc
26 375b78fb 2009-08-23 rsc if((c->n[0] = a) != nil)
27 375b78fb 2009-08-23 rsc c->n[0]->p = c;
28 375b78fb 2009-08-23 rsc
29 375b78fb 2009-08-23 rsc if((*tp = c) != nil)
30 375b78fb 2009-08-23 rsc (*tp)->p = p;
31 375b78fb 2009-08-23 rsc
32 375b78fb 2009-08-23 rsc a->bal = -l;
33 375b78fb 2009-08-23 rsc c->bal = r2 - ((l > 0? l: 0)+1);
34 375b78fb 2009-08-23 rsc
35 375b78fb 2009-08-23 rsc }
36 375b78fb 2009-08-23 rsc
37 375b78fb 2009-08-23 rsc static void
38 375b78fb 2009-08-23 rsc singleright(Avl **tp, Avl *p)
39 375b78fb 2009-08-23 rsc {
40 375b78fb 2009-08-23 rsc int l2, r;
41 375b78fb 2009-08-23 rsc Avl *a, *c;
42 375b78fb 2009-08-23 rsc
43 375b78fb 2009-08-23 rsc a = *tp;
44 375b78fb 2009-08-23 rsc c = a->n[0];
45 375b78fb 2009-08-23 rsc l2 = - c->bal;
46 375b78fb 2009-08-23 rsc r = a->bal + ((l2 > 0? l2: 0)+1);
47 375b78fb 2009-08-23 rsc
48 375b78fb 2009-08-23 rsc if((a->n[0] = c->n[1]) != nil)
49 375b78fb 2009-08-23 rsc a->n[0]->p = a;
50 375b78fb 2009-08-23 rsc
51 375b78fb 2009-08-23 rsc if((c->n[1] = a) != nil)
52 375b78fb 2009-08-23 rsc c->n[1]->p = c;
53 375b78fb 2009-08-23 rsc
54 375b78fb 2009-08-23 rsc if((*tp = c) != nil)
55 375b78fb 2009-08-23 rsc (*tp)->p = p;
56 375b78fb 2009-08-23 rsc
57 375b78fb 2009-08-23 rsc a->bal = r;
58 375b78fb 2009-08-23 rsc c->bal = ((r > 0? r: 0)+1) - l2;
59 375b78fb 2009-08-23 rsc }
60 375b78fb 2009-08-23 rsc
61 375b78fb 2009-08-23 rsc static void
62 375b78fb 2009-08-23 rsc doublerightleft(Avl **tp, Avl *p)
63 375b78fb 2009-08-23 rsc {
64 375b78fb 2009-08-23 rsc singleright(&(*tp)->n[1], *tp);
65 375b78fb 2009-08-23 rsc singleleft(tp, p);
66 375b78fb 2009-08-23 rsc }
67 375b78fb 2009-08-23 rsc
68 375b78fb 2009-08-23 rsc static void
69 375b78fb 2009-08-23 rsc doubleleftright(Avl **tp, Avl *p)
70 375b78fb 2009-08-23 rsc {
71 375b78fb 2009-08-23 rsc singleleft(&(*tp)->n[0], *tp);
72 375b78fb 2009-08-23 rsc singleright(tp, p);
73 375b78fb 2009-08-23 rsc }
74 375b78fb 2009-08-23 rsc
75 375b78fb 2009-08-23 rsc static void
76 375b78fb 2009-08-23 rsc balance(Avl **tp, Avl *p)
77 375b78fb 2009-08-23 rsc {
78 375b78fb 2009-08-23 rsc switch((*tp)->bal){
79 375b78fb 2009-08-23 rsc case -2:
80 375b78fb 2009-08-23 rsc if((*tp)->n[0]->bal <= 0)
81 375b78fb 2009-08-23 rsc singleright(tp, p);
82 375b78fb 2009-08-23 rsc else if((*tp)->n[0]->bal == 1)
83 375b78fb 2009-08-23 rsc doubleleftright(tp, p);
84 375b78fb 2009-08-23 rsc else
85 375b78fb 2009-08-23 rsc assert(0);
86 375b78fb 2009-08-23 rsc break;
87 375b78fb 2009-08-23 rsc
88 375b78fb 2009-08-23 rsc case 2:
89 375b78fb 2009-08-23 rsc if((*tp)->n[1]->bal >= 0)
90 375b78fb 2009-08-23 rsc singleleft(tp, p);
91 375b78fb 2009-08-23 rsc else if((*tp)->n[1]->bal == -1)
92 375b78fb 2009-08-23 rsc doublerightleft(tp, p);
93 375b78fb 2009-08-23 rsc else
94 375b78fb 2009-08-23 rsc assert(0);
95 375b78fb 2009-08-23 rsc break;
96 375b78fb 2009-08-23 rsc }
97 375b78fb 2009-08-23 rsc }
98 375b78fb 2009-08-23 rsc
99 375b78fb 2009-08-23 rsc static int
100 375b78fb 2009-08-23 rsc _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
101 375b78fb 2009-08-23 rsc {
102 375b78fb 2009-08-23 rsc int i, ob;
103 375b78fb 2009-08-23 rsc
104 375b78fb 2009-08-23 rsc if(*tp == nil){
105 375b78fb 2009-08-23 rsc r->bal = 0;
106 375b78fb 2009-08-23 rsc r->n[0] = nil;
107 375b78fb 2009-08-23 rsc r->n[1] = nil;
108 375b78fb 2009-08-23 rsc r->p = p;
109 375b78fb 2009-08-23 rsc *tp = r;
110 375b78fb 2009-08-23 rsc return 1;
111 375b78fb 2009-08-23 rsc }
112 375b78fb 2009-08-23 rsc ob = (*tp)->bal;
113 375b78fb 2009-08-23 rsc if((i = cmp(r, *tp)) != 0){
114 375b78fb 2009-08-23 rsc (*tp)->bal += i * _insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp,
115 375b78fb 2009-08-23 rsc rfree);
116 375b78fb 2009-08-23 rsc balance(tp, p);
117 375b78fb 2009-08-23 rsc return ob == 0 && (*tp)->bal != 0;
118 375b78fb 2009-08-23 rsc }
119 375b78fb 2009-08-23 rsc
120 375b78fb 2009-08-23 rsc /* install new entry */
121 375b78fb 2009-08-23 rsc *rfree = *tp; /* save old node for freeing */
122 375b78fb 2009-08-23 rsc *tp = r; /* insert new node */
123 375b78fb 2009-08-23 rsc **tp = **rfree; /* copy old node's Avl contents */
124 375b78fb 2009-08-23 rsc if(r->n[0]) /* fix node's children's parent pointers */
125 375b78fb 2009-08-23 rsc r->n[0]->p = r;
126 375b78fb 2009-08-23 rsc if(r->n[1])
127 375b78fb 2009-08-23 rsc r->n[1]->p = r;
128 375b78fb 2009-08-23 rsc
129 375b78fb 2009-08-23 rsc return 0;
130 375b78fb 2009-08-23 rsc }
131 375b78fb 2009-08-23 rsc
132 375b78fb 2009-08-23 rsc static Avl*
133 375b78fb 2009-08-23 rsc _lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*))
134 375b78fb 2009-08-23 rsc {
135 375b78fb 2009-08-23 rsc int i;
136 375b78fb 2009-08-23 rsc Avl *p;
137 375b78fb 2009-08-23 rsc
138 375b78fb 2009-08-23 rsc p = nil;
139 375b78fb 2009-08-23 rsc while(t != nil){
140 375b78fb 2009-08-23 rsc assert(t->p == p);
141 375b78fb 2009-08-23 rsc if((i = cmp(r, t)) == 0)
142 375b78fb 2009-08-23 rsc return t;
143 375b78fb 2009-08-23 rsc p = t;
144 375b78fb 2009-08-23 rsc t = t->n[(i+1)/2];
145 375b78fb 2009-08-23 rsc }
146 375b78fb 2009-08-23 rsc return nil;
147 375b78fb 2009-08-23 rsc }
148 375b78fb 2009-08-23 rsc
149 375b78fb 2009-08-23 rsc static int
150 375b78fb 2009-08-23 rsc successor(Avl **tp, Avl *p, Avl **r)
151 375b78fb 2009-08-23 rsc {
152 375b78fb 2009-08-23 rsc int ob;
153 375b78fb 2009-08-23 rsc
154 375b78fb 2009-08-23 rsc if((*tp)->n[0] == nil){
155 375b78fb 2009-08-23 rsc *r = *tp;
156 375b78fb 2009-08-23 rsc *tp = (*r)->n[1];
157 375b78fb 2009-08-23 rsc if(*tp)
158 375b78fb 2009-08-23 rsc (*tp)->p = p;
159 375b78fb 2009-08-23 rsc return -1;
160 375b78fb 2009-08-23 rsc }
161 375b78fb 2009-08-23 rsc ob = (*tp)->bal;
162 375b78fb 2009-08-23 rsc (*tp)->bal -= successor(&(*tp)->n[0], *tp, r);
163 375b78fb 2009-08-23 rsc balance(tp, p);
164 375b78fb 2009-08-23 rsc return -(ob != 0 && (*tp)->bal == 0);
165 375b78fb 2009-08-23 rsc }
166 375b78fb 2009-08-23 rsc
167 375b78fb 2009-08-23 rsc static int
168 375b78fb 2009-08-23 rsc _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
169 375b78fb 2009-08-23 rsc void (*predel)(Avl*, void*), void *arg)
170 375b78fb 2009-08-23 rsc {
171 375b78fb 2009-08-23 rsc int i, ob;
172 375b78fb 2009-08-23 rsc Avl *r, *or;
173 375b78fb 2009-08-23 rsc
174 375b78fb 2009-08-23 rsc if(*tp == nil)
175 375b78fb 2009-08-23 rsc return 0;
176 375b78fb 2009-08-23 rsc
177 375b78fb 2009-08-23 rsc ob = (*tp)->bal;
178 375b78fb 2009-08-23 rsc if((i=cmp(rx, *tp)) != 0){
179 375b78fb 2009-08-23 rsc (*tp)->bal += i * _deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp,
180 375b78fb 2009-08-23 rsc del, predel, arg);
181 375b78fb 2009-08-23 rsc balance(tp, p);
182 375b78fb 2009-08-23 rsc return -(ob != 0 && (*tp)->bal == 0);
183 375b78fb 2009-08-23 rsc }
184 375b78fb 2009-08-23 rsc
185 375b78fb 2009-08-23 rsc if(predel)
186 375b78fb 2009-08-23 rsc (*predel)(*tp, arg);
187 375b78fb 2009-08-23 rsc
188 375b78fb 2009-08-23 rsc or = *tp;
189 375b78fb 2009-08-23 rsc if(or->n[i=0] == nil || or->n[i=1] == nil){
190 375b78fb 2009-08-23 rsc *tp = or->n[1-i];
191 375b78fb 2009-08-23 rsc if(*tp)
192 375b78fb 2009-08-23 rsc (*tp)->p = p;
193 375b78fb 2009-08-23 rsc *del = or;
194 375b78fb 2009-08-23 rsc return -1;
195 375b78fb 2009-08-23 rsc }
196 375b78fb 2009-08-23 rsc
197 375b78fb 2009-08-23 rsc /* deleting node with two kids, find successor */
198 375b78fb 2009-08-23 rsc or->bal += successor(&or->n[1], or, &r);
199 375b78fb 2009-08-23 rsc r->bal = or->bal;
200 375b78fb 2009-08-23 rsc r->n[0] = or->n[0];
201 375b78fb 2009-08-23 rsc r->n[1] = or->n[1];
202 375b78fb 2009-08-23 rsc *tp = r;
203 375b78fb 2009-08-23 rsc (*tp)->p = p;
204 375b78fb 2009-08-23 rsc /* node has changed; fix children's parent pointers */
205 375b78fb 2009-08-23 rsc if(r->n[0])
206 375b78fb 2009-08-23 rsc r->n[0]->p = r;
207 375b78fb 2009-08-23 rsc if(r->n[1])
208 375b78fb 2009-08-23 rsc r->n[1]->p = r;
209 375b78fb 2009-08-23 rsc *del = or;
210 375b78fb 2009-08-23 rsc balance(tp, p);
211 375b78fb 2009-08-23 rsc return -(ob != 0 && (*tp)->bal == 0);
212 375b78fb 2009-08-23 rsc }
213 375b78fb 2009-08-23 rsc
214 375b78fb 2009-08-23 rsc static void
215 375b78fb 2009-08-23 rsc checkparents(Avl *a, Avl *p)
216 375b78fb 2009-08-23 rsc {
217 375b78fb 2009-08-23 rsc if(a == nil)
218 375b78fb 2009-08-23 rsc return;
219 375b78fb 2009-08-23 rsc if(a->p != p)
220 375b78fb 2009-08-23 rsc print("bad parent\n");
221 375b78fb 2009-08-23 rsc checkparents(a->n[0], a);
222 375b78fb 2009-08-23 rsc checkparents(a->n[1], a);
223 375b78fb 2009-08-23 rsc }
224 375b78fb 2009-08-23 rsc
225 375b78fb 2009-08-23 rsc struct Avltree
226 375b78fb 2009-08-23 rsc {
227 375b78fb 2009-08-23 rsc Avl *root;
228 375b78fb 2009-08-23 rsc int (*cmp)(Avl*, Avl*);
229 375b78fb 2009-08-23 rsc Avlwalk *walks;
230 375b78fb 2009-08-23 rsc };
231 375b78fb 2009-08-23 rsc struct Avlwalk
232 375b78fb 2009-08-23 rsc {
233 375b78fb 2009-08-23 rsc int started;
234 375b78fb 2009-08-23 rsc int moved;
235 375b78fb 2009-08-23 rsc Avlwalk *next;
236 375b78fb 2009-08-23 rsc Avltree *tree;
237 375b78fb 2009-08-23 rsc Avl *node;
238 375b78fb 2009-08-23 rsc };
239 375b78fb 2009-08-23 rsc
240 375b78fb 2009-08-23 rsc Avltree*
241 375b78fb 2009-08-23 rsc mkavltree(int (*cmp)(Avl*, Avl*))
242 375b78fb 2009-08-23 rsc {
243 375b78fb 2009-08-23 rsc Avltree *t;
244 375b78fb 2009-08-23 rsc
245 375b78fb 2009-08-23 rsc t = malloc(sizeof *t);
246 375b78fb 2009-08-23 rsc if(t == nil)
247 375b78fb 2009-08-23 rsc return nil;
248 375b78fb 2009-08-23 rsc memset(t, 0, sizeof *t);
249 375b78fb 2009-08-23 rsc t->cmp = cmp;
250 375b78fb 2009-08-23 rsc return t;
251 375b78fb 2009-08-23 rsc }
252 375b78fb 2009-08-23 rsc
253 375b78fb 2009-08-23 rsc void
254 375b78fb 2009-08-23 rsc insertavl(Avltree *t, Avl *new, Avl **oldp)
255 375b78fb 2009-08-23 rsc {
256 375b78fb 2009-08-23 rsc *oldp = nil;
257 375b78fb 2009-08-23 rsc _insertavl(&t->root, nil, new, t->cmp, oldp);
258 375b78fb 2009-08-23 rsc }
259 375b78fb 2009-08-23 rsc
260 375b78fb 2009-08-23 rsc Avl*
261 375b78fb 2009-08-23 rsc lookupavl(Avltree *t, Avl *key)
262 375b78fb 2009-08-23 rsc {
263 375b78fb 2009-08-23 rsc return _lookupavl(t->root, key, t->cmp);
264 375b78fb 2009-08-23 rsc }
265 375b78fb 2009-08-23 rsc
266 375b78fb 2009-08-23 rsc static Avl*
267 375b78fb 2009-08-23 rsc findpredecessor(Avl *a)
268 375b78fb 2009-08-23 rsc {
269 375b78fb 2009-08-23 rsc if(a == nil)
270 375b78fb 2009-08-23 rsc return nil;
271 375b78fb 2009-08-23 rsc
272 375b78fb 2009-08-23 rsc if(a->n[0] != nil){
273 375b78fb 2009-08-23 rsc /* predecessor is rightmost descendant of left child */
274 375b78fb 2009-08-23 rsc for(a = a->n[0]; a->n[1]; a = a->n[1])
275 375b78fb 2009-08-23 rsc ;
276 375b78fb 2009-08-23 rsc return a;
277 375b78fb 2009-08-23 rsc }else{
278 375b78fb 2009-08-23 rsc /* we're at a leaf, successor is a parent we enter from the right */
279 375b78fb 2009-08-23 rsc while(a->p && a->p->n[0] == a)
280 375b78fb 2009-08-23 rsc a = a->p;
281 375b78fb 2009-08-23 rsc return a->p;
282 375b78fb 2009-08-23 rsc }
283 375b78fb 2009-08-23 rsc }
284 375b78fb 2009-08-23 rsc
285 375b78fb 2009-08-23 rsc static Avl*
286 375b78fb 2009-08-23 rsc findsuccessor(Avl *a)
287 375b78fb 2009-08-23 rsc {
288 375b78fb 2009-08-23 rsc if(a == nil)
289 375b78fb 2009-08-23 rsc return nil;
290 375b78fb 2009-08-23 rsc
291 375b78fb 2009-08-23 rsc if(a->n[1] != nil){
292 375b78fb 2009-08-23 rsc /* successor is leftmost descendant of right child */
293 375b78fb 2009-08-23 rsc for(a = a->n[1]; a->n[0]; a = a->n[0])
294 375b78fb 2009-08-23 rsc ;
295 375b78fb 2009-08-23 rsc return a;
296 375b78fb 2009-08-23 rsc }else{
297 375b78fb 2009-08-23 rsc /* we're at a leaf, successor is a parent we enter from the left going up */
298 375b78fb 2009-08-23 rsc while(a->p && a->p->n[1] == a)
299 375b78fb 2009-08-23 rsc a = a->p;
300 375b78fb 2009-08-23 rsc return a->p;
301 375b78fb 2009-08-23 rsc }
302 375b78fb 2009-08-23 rsc }
303 375b78fb 2009-08-23 rsc
304 375b78fb 2009-08-23 rsc static void
305 375b78fb 2009-08-23 rsc walkdel(Avl *a, void *v)
306 375b78fb 2009-08-23 rsc {
307 375b78fb 2009-08-23 rsc Avl *p;
308 375b78fb 2009-08-23 rsc Avlwalk *w;
309 375b78fb 2009-08-23 rsc Avltree *t;
310 375b78fb 2009-08-23 rsc
311 375b78fb 2009-08-23 rsc if(a == nil)
312 375b78fb 2009-08-23 rsc return;
313 375b78fb 2009-08-23 rsc
314 375b78fb 2009-08-23 rsc p = findpredecessor(a);
315 375b78fb 2009-08-23 rsc t = v;
316 375b78fb 2009-08-23 rsc for(w = t->walks; w; w = w->next){
317 375b78fb 2009-08-23 rsc if(w->node == a){
318 375b78fb 2009-08-23 rsc /* back pointer to predecessor; not perfect but adequate */
319 375b78fb 2009-08-23 rsc w->moved = 1;
320 375b78fb 2009-08-23 rsc w->node = p;
321 375b78fb 2009-08-23 rsc if(p == nil)
322 375b78fb 2009-08-23 rsc w->started = 0;
323 375b78fb 2009-08-23 rsc }
324 375b78fb 2009-08-23 rsc }
325 375b78fb 2009-08-23 rsc }
326 375b78fb 2009-08-23 rsc
327 375b78fb 2009-08-23 rsc void
328 375b78fb 2009-08-23 rsc deleteavl(Avltree *t, Avl *key, Avl **oldp)
329 375b78fb 2009-08-23 rsc {
330 375b78fb 2009-08-23 rsc *oldp = nil;
331 375b78fb 2009-08-23 rsc _deleteavl(&t->root, nil, key, t->cmp, oldp, walkdel, t);
332 375b78fb 2009-08-23 rsc }
333 375b78fb 2009-08-23 rsc
334 375b78fb 2009-08-23 rsc Avlwalk*
335 375b78fb 2009-08-23 rsc avlwalk(Avltree *t)
336 375b78fb 2009-08-23 rsc {
337 375b78fb 2009-08-23 rsc Avlwalk *w;
338 375b78fb 2009-08-23 rsc
339 375b78fb 2009-08-23 rsc w = malloc(sizeof *w);
340 375b78fb 2009-08-23 rsc if(w == nil)
341 375b78fb 2009-08-23 rsc return nil;
342 375b78fb 2009-08-23 rsc memset(w, 0, sizeof *w);
343 375b78fb 2009-08-23 rsc w->tree = t;
344 375b78fb 2009-08-23 rsc w->next = t->walks;
345 375b78fb 2009-08-23 rsc t->walks = w;
346 375b78fb 2009-08-23 rsc return w;
347 375b78fb 2009-08-23 rsc }
348 375b78fb 2009-08-23 rsc
349 375b78fb 2009-08-23 rsc Avl*
350 375b78fb 2009-08-23 rsc avlnext(Avlwalk *w)
351 375b78fb 2009-08-23 rsc {
352 375b78fb 2009-08-23 rsc Avl *a;
353 375b78fb 2009-08-23 rsc
354 375b78fb 2009-08-23 rsc if(w->started==0){
355 375b78fb 2009-08-23 rsc for(a = w->tree->root; a && a->n[0]; a = a->n[0])
356 375b78fb 2009-08-23 rsc ;
357 375b78fb 2009-08-23 rsc w->node = a;
358 375b78fb 2009-08-23 rsc w->started = 1;
359 375b78fb 2009-08-23 rsc }else{
360 375b78fb 2009-08-23 rsc a = findsuccessor(w->node);
361 375b78fb 2009-08-23 rsc if(a == w->node)
362 375b78fb 2009-08-23 rsc abort();
363 375b78fb 2009-08-23 rsc w->node = a;
364 375b78fb 2009-08-23 rsc }
365 375b78fb 2009-08-23 rsc return w->node;
366 375b78fb 2009-08-23 rsc }
367 375b78fb 2009-08-23 rsc
368 375b78fb 2009-08-23 rsc Avl*
369 375b78fb 2009-08-23 rsc avlprev(Avlwalk *w)
370 375b78fb 2009-08-23 rsc {
371 375b78fb 2009-08-23 rsc Avl *a;
372 375b78fb 2009-08-23 rsc
373 375b78fb 2009-08-23 rsc if(w->started == 0){
374 375b78fb 2009-08-23 rsc for(a = w->tree->root; a && a->n[1]; a = a->n[1])
375 375b78fb 2009-08-23 rsc ;
376 375b78fb 2009-08-23 rsc w->node = a;
377 375b78fb 2009-08-23 rsc w->started = 1;
378 375b78fb 2009-08-23 rsc }else if(w->moved){
379 375b78fb 2009-08-23 rsc w->moved = 0;
380 375b78fb 2009-08-23 rsc return w->node;
381 375b78fb 2009-08-23 rsc }else{
382 375b78fb 2009-08-23 rsc a = findpredecessor(w->node);
383 375b78fb 2009-08-23 rsc if(a == w->node)
384 375b78fb 2009-08-23 rsc abort();
385 375b78fb 2009-08-23 rsc w->node = a;
386 375b78fb 2009-08-23 rsc }
387 375b78fb 2009-08-23 rsc return w->node;
388 375b78fb 2009-08-23 rsc }
389 375b78fb 2009-08-23 rsc
390 375b78fb 2009-08-23 rsc void
391 375b78fb 2009-08-23 rsc endwalk(Avlwalk *w)
392 375b78fb 2009-08-23 rsc {
393 375b78fb 2009-08-23 rsc Avltree *t;
394 375b78fb 2009-08-23 rsc Avlwalk **l;
395 375b78fb 2009-08-23 rsc
396 375b78fb 2009-08-23 rsc t = w->tree;
397 375b78fb 2009-08-23 rsc for(l = &t->walks; *l; l = &(*l)->next){
398 375b78fb 2009-08-23 rsc if(*l == w){
399 375b78fb 2009-08-23 rsc *l = w->next;
400 375b78fb 2009-08-23 rsc break;
401 375b78fb 2009-08-23 rsc }
402 375b78fb 2009-08-23 rsc }
403 375b78fb 2009-08-23 rsc free(w);
404 375b78fb 2009-08-23 rsc }
405 375b78fb 2009-08-23 rsc
406 375b78fb 2009-08-23 rsc static void
407 375b78fb 2009-08-23 rsc walkavl(Avl *t, void (*f)(Avl*, void*), void *v)
408 375b78fb 2009-08-23 rsc {
409 375b78fb 2009-08-23 rsc if(t == nil)
410 375b78fb 2009-08-23 rsc return;
411 375b78fb 2009-08-23 rsc walkavl(t->n[0], f, v);
412 375b78fb 2009-08-23 rsc f(t, v);
413 375b78fb 2009-08-23 rsc walkavl(t->n[1], f, v);
414 375b78fb 2009-08-23 rsc }