7 * In-memory database stored as self-balancing AVL tree.
8 * See Lewis & Denenberg, Data Structures and Their Algorithms.
12 singleleft(Avl **tp, Avl *p)
21 l = (r2 > 0? r2: 0)+1 - a->bal;
23 if((a->n[1] = c->n[0]) != nil)
26 if((c->n[0] = a) != nil)
33 c->bal = r2 - ((l > 0? l: 0)+1);
38 singleright(Avl **tp, Avl *p)
46 r = a->bal + ((l2 > 0? l2: 0)+1);
48 if((a->n[0] = c->n[1]) != nil)
51 if((c->n[1] = a) != nil)
58 c->bal = ((r > 0? r: 0)+1) - l2;
62 doublerightleft(Avl **tp, Avl *p)
64 singleright(&(*tp)->n[1], *tp);
69 doubleleftright(Avl **tp, Avl *p)
71 singleleft(&(*tp)->n[0], *tp);
76 balance(Avl **tp, Avl *p)
80 if((*tp)->n[0]->bal <= 0)
82 else if((*tp)->n[0]->bal == 1)
83 doubleleftright(tp, p);
89 if((*tp)->n[1]->bal >= 0)
91 else if((*tp)->n[1]->bal == -1)
92 doublerightleft(tp, p);
110 _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
123 if((i = canoncmp(cmp(r, *tp))) != 0){
124 (*tp)->bal += i * _insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp,
127 return ob == 0 && (*tp)->bal != 0;
130 /* install new entry */
131 *rfree = *tp; /* save old node for freeing */
132 *tp = r; /* insert new node */
133 **tp = **rfree; /* copy old node's Avl contents */
134 if(r->n[0]) /* fix node's children's parent pointers */
143 successor(Avl **tp, Avl *p, Avl **r)
147 if((*tp)->n[0] == nil){
155 (*tp)->bal -= successor(&(*tp)->n[0], *tp, r);
157 return -(ob != 0 && (*tp)->bal == 0);
161 _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
162 void (*predel)(Avl*, void*), void *arg)
171 if((i=canoncmp(cmp(rx, *tp))) != 0){
172 (*tp)->bal += i * _deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp,
175 return -(ob != 0 && (*tp)->bal == 0);
182 if(or->n[i=0] == nil || or->n[i=1] == nil){
190 /* deleting node with two kids, find successor */
191 or->bal += successor(&or->n[1], or, &r);
197 /* node has changed; fix children's parent pointers */
204 return -(ob != 0 && (*tp)->bal == 0);
208 checkparents(Avl *a, Avl *p)
213 print("bad parent\n");
214 checkparents(a->n[0], a);
215 checkparents(a->n[1], a);
221 int (*cmp)(Avl*, Avl*);
234 mkavltree(int (*cmp)(Avl*, Avl*))
238 t = malloc(sizeof *t);
241 memset(t, 0, sizeof *t);
247 insertavl(Avltree *t, Avl *new, Avl **oldp)
250 _insertavl(&t->root, nil, new, t->cmp, oldp);
254 findpredecessor(Avl *a)
260 /* predecessor is rightmost descendant of left child */
261 for(a = a->n[0]; a->n[1]; a = a->n[1])
265 /* we're at a leaf, successor is a parent we enter from the right */
266 while(a->p && a->p->n[0] == a)
273 findsuccessor(Avl *a)
279 /* successor is leftmost descendant of right child */
280 for(a = a->n[1]; a->n[0]; a = a->n[0])
284 /* we're at a leaf, successor is a parent we enter from the left going up */
285 while(a->p && a->p->n[1] == a)
292 _lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*), int neighbor)
302 if((i = canoncmp(cmp(r, t))) == 0)
310 return i > 0 ? p : findpredecessor(p);
311 return i < 0 ? p : findsuccessor(p);
315 searchavl(Avltree *t, Avl *key, int neighbor)
317 return _lookupavl(t->root, key, t->cmp, neighbor);
321 lookupavl(Avltree *t, Avl *key)
323 return _lookupavl(t->root, key, t->cmp, 0);
327 walkdel(Avl *a, void *v)
336 p = findpredecessor(a);
338 for(w = t->walks; w; w = w->next){
340 /* back pointer to predecessor; not perfect but adequate */
350 deleteavl(Avltree *t, Avl *key, Avl **oldp)
353 _deleteavl(&t->root, nil, key, t->cmp, oldp, walkdel, t);
361 w = malloc(sizeof *w);
364 memset(w, 0, sizeof *w);
377 for(a = w->tree->root; a && a->n[0]; a = a->n[0])
382 a = findsuccessor(w->node);
396 for(a = w->tree->root; a && a->n[1]; a = a->n[1])
404 a = findpredecessor(w->node);
419 for(l = &t->walks; *l; l = &(*l)->next){
429 walkavl(Avl *t, void (*f)(Avl*, void*), void *v)
433 walkavl(t->n[0], f, v);
435 walkavl(t->n[1], f, v);