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>
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.
12 375b78fb 2009-08-23 rsc singleleft(Avl **tp, Avl *p)
21 375b78fb 2009-08-23 rsc l = (r2 > 0? r2: 0)+1 - a->bal;
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;
26 375b78fb 2009-08-23 rsc if((c->n[0] = a) != nil)
27 375b78fb 2009-08-23 rsc c->n[0]->p = c;
29 375b78fb 2009-08-23 rsc if((*tp = c) != nil)
30 375b78fb 2009-08-23 rsc (*tp)->p = p;
33 375b78fb 2009-08-23 rsc c->bal = r2 - ((l > 0? l: 0)+1);
38 375b78fb 2009-08-23 rsc singleright(Avl **tp, Avl *p)
45 375b78fb 2009-08-23 rsc l2 = - c->bal;
46 375b78fb 2009-08-23 rsc r = a->bal + ((l2 > 0? l2: 0)+1);
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;
51 375b78fb 2009-08-23 rsc if((c->n[1] = a) != nil)
52 375b78fb 2009-08-23 rsc c->n[1]->p = c;
54 375b78fb 2009-08-23 rsc if((*tp = c) != nil)
55 375b78fb 2009-08-23 rsc (*tp)->p = p;
58 375b78fb 2009-08-23 rsc c->bal = ((r > 0? r: 0)+1) - l2;
62 375b78fb 2009-08-23 rsc doublerightleft(Avl **tp, Avl *p)
64 375b78fb 2009-08-23 rsc singleright(&(*tp)->n[1], *tp);
65 375b78fb 2009-08-23 rsc singleleft(tp, p);
69 375b78fb 2009-08-23 rsc doubleleftright(Avl **tp, Avl *p)
71 375b78fb 2009-08-23 rsc singleleft(&(*tp)->n[0], *tp);
72 375b78fb 2009-08-23 rsc singleright(tp, p);
76 375b78fb 2009-08-23 rsc balance(Avl **tp, Avl *p)
78 375b78fb 2009-08-23 rsc switch((*tp)->bal){
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);
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);
100 f5a8ea6f 2011-06-02 rsc canoncmp(int cmp)
104 f5a8ea6f 2011-06-02 rsc else if(cmp > 0)
110 375b78fb 2009-08-23 rsc _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
114 375b78fb 2009-08-23 rsc if(*tp == nil){
116 375b78fb 2009-08-23 rsc r->n[0] = nil;
117 375b78fb 2009-08-23 rsc r->n[1] = nil;
122 375b78fb 2009-08-23 rsc ob = (*tp)->bal;
123 f5a8ea6f 2011-06-02 rsc if((i = canoncmp(cmp(r, *tp))) != 0){
124 375b78fb 2009-08-23 rsc (*tp)->bal += i * _insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp,
126 375b78fb 2009-08-23 rsc balance(tp, p);
127 375b78fb 2009-08-23 rsc return ob == 0 && (*tp)->bal != 0;
130 375b78fb 2009-08-23 rsc /* install new entry */
131 375b78fb 2009-08-23 rsc *rfree = *tp; /* save old node for freeing */
132 375b78fb 2009-08-23 rsc *tp = r; /* insert new node */
133 375b78fb 2009-08-23 rsc **tp = **rfree; /* copy old node's Avl contents */
134 375b78fb 2009-08-23 rsc if(r->n[0]) /* fix node's children's parent pointers */
135 375b78fb 2009-08-23 rsc r->n[0]->p = r;
137 375b78fb 2009-08-23 rsc r->n[1]->p = r;
143 375b78fb 2009-08-23 rsc successor(Avl **tp, Avl *p, Avl **r)
147 375b78fb 2009-08-23 rsc if((*tp)->n[0] == nil){
149 375b78fb 2009-08-23 rsc *tp = (*r)->n[1];
151 375b78fb 2009-08-23 rsc (*tp)->p = p;
154 375b78fb 2009-08-23 rsc ob = (*tp)->bal;
155 375b78fb 2009-08-23 rsc (*tp)->bal -= successor(&(*tp)->n[0], *tp, r);
156 375b78fb 2009-08-23 rsc balance(tp, p);
157 375b78fb 2009-08-23 rsc return -(ob != 0 && (*tp)->bal == 0);
161 375b78fb 2009-08-23 rsc _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
162 375b78fb 2009-08-23 rsc void (*predel)(Avl*, void*), void *arg)
165 375b78fb 2009-08-23 rsc Avl *r, *or;
167 375b78fb 2009-08-23 rsc if(*tp == nil)
170 375b78fb 2009-08-23 rsc ob = (*tp)->bal;
171 f5a8ea6f 2011-06-02 rsc if((i=canoncmp(cmp(rx, *tp))) != 0){
172 375b78fb 2009-08-23 rsc (*tp)->bal += i * _deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp,
173 375b78fb 2009-08-23 rsc del, predel, arg);
174 375b78fb 2009-08-23 rsc balance(tp, p);
175 375b78fb 2009-08-23 rsc return -(ob != 0 && (*tp)->bal == 0);
179 375b78fb 2009-08-23 rsc (*predel)(*tp, arg);
182 375b78fb 2009-08-23 rsc if(or->n[i=0] == nil || or->n[i=1] == nil){
183 375b78fb 2009-08-23 rsc *tp = or->n[1-i];
185 375b78fb 2009-08-23 rsc (*tp)->p = p;
190 375b78fb 2009-08-23 rsc /* deleting node with two kids, find successor */
191 375b78fb 2009-08-23 rsc or->bal += successor(&or->n[1], or, &r);
192 375b78fb 2009-08-23 rsc r->bal = or->bal;
193 375b78fb 2009-08-23 rsc r->n[0] = or->n[0];
194 375b78fb 2009-08-23 rsc r->n[1] = or->n[1];
196 375b78fb 2009-08-23 rsc (*tp)->p = p;
197 375b78fb 2009-08-23 rsc /* node has changed; fix children's parent pointers */
199 375b78fb 2009-08-23 rsc r->n[0]->p = r;
201 375b78fb 2009-08-23 rsc r->n[1]->p = r;
203 375b78fb 2009-08-23 rsc balance(tp, p);
204 375b78fb 2009-08-23 rsc return -(ob != 0 && (*tp)->bal == 0);
209 375b78fb 2009-08-23 rsc checkparents(Avl *a, Avl *p)
211 375b78fb 2009-08-23 rsc if(a == nil)
213 375b78fb 2009-08-23 rsc if(a->p != p)
214 375b78fb 2009-08-23 rsc print("bad parent\n");
215 375b78fb 2009-08-23 rsc checkparents(a->n[0], a);
216 375b78fb 2009-08-23 rsc checkparents(a->n[1], a);
220 375b78fb 2009-08-23 rsc struct Avltree
223 375b78fb 2009-08-23 rsc int (*cmp)(Avl*, Avl*);
224 375b78fb 2009-08-23 rsc Avlwalk *walks;
226 375b78fb 2009-08-23 rsc struct Avlwalk
228 375b78fb 2009-08-23 rsc int started;
230 375b78fb 2009-08-23 rsc Avlwalk *next;
231 375b78fb 2009-08-23 rsc Avltree *tree;
236 375b78fb 2009-08-23 rsc mkavltree(int (*cmp)(Avl*, Avl*))
240 375b78fb 2009-08-23 rsc t = malloc(sizeof *t);
241 375b78fb 2009-08-23 rsc if(t == nil)
243 375b78fb 2009-08-23 rsc memset(t, 0, sizeof *t);
244 375b78fb 2009-08-23 rsc t->cmp = cmp;
249 375b78fb 2009-08-23 rsc insertavl(Avltree *t, Avl *new, Avl **oldp)
251 375b78fb 2009-08-23 rsc *oldp = nil;
252 375b78fb 2009-08-23 rsc _insertavl(&t->root, nil, new, t->cmp, oldp);
256 375b78fb 2009-08-23 rsc findpredecessor(Avl *a)
258 375b78fb 2009-08-23 rsc if(a == nil)
261 375b78fb 2009-08-23 rsc if(a->n[0] != nil){
262 375b78fb 2009-08-23 rsc /* predecessor is rightmost descendant of left child */
263 375b78fb 2009-08-23 rsc for(a = a->n[0]; a->n[1]; a = a->n[1])
267 375b78fb 2009-08-23 rsc /* we're at a leaf, successor is a parent we enter from the right */
268 375b78fb 2009-08-23 rsc while(a->p && a->p->n[0] == a)
270 375b78fb 2009-08-23 rsc return a->p;
275 375b78fb 2009-08-23 rsc findsuccessor(Avl *a)
277 375b78fb 2009-08-23 rsc if(a == nil)
280 375b78fb 2009-08-23 rsc if(a->n[1] != nil){
281 375b78fb 2009-08-23 rsc /* successor is leftmost descendant of right child */
282 375b78fb 2009-08-23 rsc for(a = a->n[1]; a->n[0]; a = a->n[0])
286 375b78fb 2009-08-23 rsc /* we're at a leaf, successor is a parent we enter from the left going up */
287 375b78fb 2009-08-23 rsc while(a->p && a->p->n[1] == a)
289 375b78fb 2009-08-23 rsc return a->p;
294 f5a8ea6f 2011-06-02 rsc _lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*), int neighbor)
300 f5a8ea6f 2011-06-02 rsc if(t == nil)
303 f5a8ea6f 2011-06-02 rsc assert(t->p == p);
304 f5a8ea6f 2011-06-02 rsc if((i = canoncmp(cmp(r, t))) == 0)
307 f5a8ea6f 2011-06-02 rsc t = t->n[(i+1)/2];
309 f5a8ea6f 2011-06-02 rsc if(neighbor == 0)
311 f5a8ea6f 2011-06-02 rsc if(neighbor < 0)
312 f5a8ea6f 2011-06-02 rsc return i > 0 ? p : findpredecessor(p);
313 f5a8ea6f 2011-06-02 rsc return i < 0 ? p : findsuccessor(p);
317 f5a8ea6f 2011-06-02 rsc searchavl(Avltree *t, Avl *key, int neighbor)
319 f5a8ea6f 2011-06-02 rsc return _lookupavl(t->root, key, t->cmp, neighbor);
323 f5a8ea6f 2011-06-02 rsc lookupavl(Avltree *t, Avl *key)
325 f5a8ea6f 2011-06-02 rsc return _lookupavl(t->root, key, t->cmp, 0);
329 375b78fb 2009-08-23 rsc walkdel(Avl *a, void *v)
335 375b78fb 2009-08-23 rsc if(a == nil)
338 375b78fb 2009-08-23 rsc p = findpredecessor(a);
340 375b78fb 2009-08-23 rsc for(w = t->walks; w; w = w->next){
341 375b78fb 2009-08-23 rsc if(w->node == a){
342 375b78fb 2009-08-23 rsc /* back pointer to predecessor; not perfect but adequate */
343 375b78fb 2009-08-23 rsc w->moved = 1;
344 375b78fb 2009-08-23 rsc w->node = p;
345 375b78fb 2009-08-23 rsc if(p == nil)
346 375b78fb 2009-08-23 rsc w->started = 0;
352 375b78fb 2009-08-23 rsc deleteavl(Avltree *t, Avl *key, Avl **oldp)
354 375b78fb 2009-08-23 rsc *oldp = nil;
355 375b78fb 2009-08-23 rsc _deleteavl(&t->root, nil, key, t->cmp, oldp, walkdel, t);
359 375b78fb 2009-08-23 rsc avlwalk(Avltree *t)
363 375b78fb 2009-08-23 rsc w = malloc(sizeof *w);
364 375b78fb 2009-08-23 rsc if(w == nil)
366 375b78fb 2009-08-23 rsc memset(w, 0, sizeof *w);
367 375b78fb 2009-08-23 rsc w->tree = t;
368 375b78fb 2009-08-23 rsc w->next = t->walks;
369 375b78fb 2009-08-23 rsc t->walks = w;
374 375b78fb 2009-08-23 rsc avlnext(Avlwalk *w)
378 375b78fb 2009-08-23 rsc if(w->started==0){
379 375b78fb 2009-08-23 rsc for(a = w->tree->root; a && a->n[0]; a = a->n[0])
381 375b78fb 2009-08-23 rsc w->node = a;
382 375b78fb 2009-08-23 rsc w->started = 1;
384 375b78fb 2009-08-23 rsc a = findsuccessor(w->node);
385 375b78fb 2009-08-23 rsc if(a == w->node)
387 375b78fb 2009-08-23 rsc w->node = a;
389 375b78fb 2009-08-23 rsc return w->node;
393 375b78fb 2009-08-23 rsc avlprev(Avlwalk *w)
397 375b78fb 2009-08-23 rsc if(w->started == 0){
398 375b78fb 2009-08-23 rsc for(a = w->tree->root; a && a->n[1]; a = a->n[1])
400 375b78fb 2009-08-23 rsc w->node = a;
401 375b78fb 2009-08-23 rsc w->started = 1;
402 375b78fb 2009-08-23 rsc }else if(w->moved){
403 375b78fb 2009-08-23 rsc w->moved = 0;
404 375b78fb 2009-08-23 rsc return w->node;
406 375b78fb 2009-08-23 rsc a = findpredecessor(w->node);
407 375b78fb 2009-08-23 rsc if(a == w->node)
409 375b78fb 2009-08-23 rsc w->node = a;
411 375b78fb 2009-08-23 rsc return w->node;
415 375b78fb 2009-08-23 rsc endwalk(Avlwalk *w)
418 375b78fb 2009-08-23 rsc Avlwalk **l;
420 375b78fb 2009-08-23 rsc t = w->tree;
421 375b78fb 2009-08-23 rsc for(l = &t->walks; *l; l = &(*l)->next){
422 375b78fb 2009-08-23 rsc if(*l == w){
423 375b78fb 2009-08-23 rsc *l = w->next;
432 375b78fb 2009-08-23 rsc walkavl(Avl *t, void (*f)(Avl*, void*), void *v)
434 375b78fb 2009-08-23 rsc if(t == nil)
436 375b78fb 2009-08-23 rsc walkavl(t->n[0], f, v);
438 375b78fb 2009-08-23 rsc walkavl(t->n[1], f, v);