ref: 4410517b44fd2610abe0dcd1349bb3e6b3c5ddb8
dir: /sys/src/cmd/replica/avl.c/
#include "all.h" /* * In-memory database stored as self-balancing AVL tree. * See Lewis & Denenberg, Data Structures and Their Algorithms. */ static void singleleft(Avl **tp, Avl *p) { Avl *a, *c; int l, r2; a = *tp; c = a->n[1]; r2 = c->bal; l = (r2 > 0 ? r2 : 0)+1 - a->bal; if((a->n[1] = c->n[0]) != nil) a->n[1]->p = a; if((c->n[0] = a) != nil) c->n[0]->p = c; if((*tp = c) != nil) (*tp)->p = p; a->bal = -l; c->bal = r2 - ((l > 0 ? l : 0)+1); } static void singleright(Avl **tp, Avl *p) { Avl *a, *c; int l2, r; a = *tp; c = a->n[0]; l2 = - c->bal; r = a->bal + ((l2 > 0 ? l2 : 0)+1); if((a->n[0] = c->n[1]) != nil) a->n[0]->p = a; if((c->n[1] = a) != nil) c->n[1]->p = c; if((*tp = c) != nil) (*tp)->p = p; a->bal = r; c->bal = ((r > 0 ? r : 0)+1) - l2; } static void doublerightleft(Avl **tp, Avl *p) { singleright(&(*tp)->n[1], *tp); singleleft(tp, p); } static void doubleleftright(Avl **tp, Avl *p) { singleleft(&(*tp)->n[0], *tp); singleright(tp, p); } static void balance(Avl **tp, Avl *p) { switch((*tp)->bal){ case -2: if((*tp)->n[0]->bal <= 0) singleright(tp, p); else if((*tp)->n[0]->bal == 1) doubleleftright(tp, p); else assert(0); break; case 2: if((*tp)->n[1]->bal >= 0) singleleft(tp, p); else if((*tp)->n[1]->bal == -1) doublerightleft(tp, p); else assert(0); break; } } static int canoncmp(int cmp) { if(cmp < 0) return -1; else if(cmp > 0) return 1; return 0; } static int _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree) { int i, ob; if(*tp == nil){ r->bal = 0; r->n[0] = nil; r->n[1] = nil; r->p = p; *tp = r; return 1; } ob = (*tp)->bal; if((i=canoncmp(cmp(r, *tp))) != 0){ (*tp)->bal += i*_insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp, rfree); balance(tp, p); return ob==0 && (*tp)->bal != 0; } /* install new entry */ *rfree = *tp; /* save old node for freeing */ *tp = r; /* insert new node */ **tp = **rfree; /* copy old node's Avl contents */ if(r->n[0]) /* fix node's children's parent pointers */ r->n[0]->p = r; if(r->n[1]) r->n[1]->p = r; return 0; } static Avl* _lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*)) { int i; Avl *p; p = nil; while(t != nil){ assert(t->p == p); if((i=canoncmp(cmp(r, t)))==0) return t; p = t; t = t->n[(i+1)/2]; } return nil; } static int successor(Avl **tp, Avl *p, Avl **r) { int ob; if((*tp)->n[0] == nil){ *r = *tp; *tp = (*r)->n[1]; if(*tp) (*tp)->p = p; return -1; } ob = (*tp)->bal; (*tp)->bal -= successor(&(*tp)->n[0], *tp, r); balance(tp, p); return -(ob!=0 && (*tp)->bal==0); } static int _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del, void (*predel)(Avl*, void*), void *arg) { int i, ob; Avl *r, *or; if(*tp == nil) return 0; ob = (*tp)->bal; if((i=canoncmp(cmp(rx, *tp))) != 0){ (*tp)->bal += i*_deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp, del, predel, arg); balance(tp, p); return -(ob!=0 && (*tp)->bal==0); } if(predel) (*predel)(*tp, arg); or = *tp; if(or->n[i=0]==nil || or->n[i=1]==nil){ *tp = or->n[1-i]; if(*tp) (*tp)->p = p; *del = or; return -1; } /* deleting node with two kids, find successor */ or->bal += successor(&or->n[1], or, &r); r->bal = or->bal; r->n[0] = or->n[0]; r->n[1] = or->n[1]; *tp = r; (*tp)->p = p; /* node has changed; fix children's parent pointers */ if(r->n[0]) r->n[0]->p = r; if(r->n[1]) r->n[1]->p = r; *del = or; balance(tp, p); return -(ob!=0 && (*tp)->bal==0); } static void checkparents(Avl *a, Avl *p) { if(a==nil) return; if(a->p != p) print("bad parent\n"); checkparents(a->n[0], a); checkparents(a->n[1], a); } struct Avltree { Avl *root; int (*cmp)(Avl*, Avl*); Avlwalk *walks; }; struct Avlwalk { int started; int moved; Avlwalk *next; Avltree *tree; Avl *node; }; Avltree* mkavltree(int (*cmp)(Avl*, Avl*)) { Avltree *t; t = emalloc(sizeof(*t)); t->cmp = cmp; return t; } void insertavl(Avltree *t, Avl *new, Avl **oldp) { *oldp = nil; _insertavl(&t->root, nil, new, t->cmp, oldp); } Avl* lookupavl(Avltree *t, Avl *key) { return _lookupavl(t->root, key, t->cmp); } static Avl* findpredecessor(Avl *a) { if(a == nil) return nil; if(a->n[0] != nil){ /* predecessor is rightmost descendant of left child */ for(a=a->n[0]; a->n[1]; a=a->n[1]) ; return a; }else{ /* we're at a leaf, successor is a parent we enter from the right */ while(a->p && a->p->n[0]==a) a = a->p; return a->p; } } static Avl* findsuccessor(Avl *a) { if(a == nil) return nil; if(a->n[1] != nil){ /* successor is leftmost descendant of right child */ for(a=a->n[1]; a->n[0]; a=a->n[0]) ; return a; }else{ /* we're at a leaf, successor is a parent we enter from the left going up */ while(a->p && a->p->n[1] == a) a = a->p; return a->p; } } static void walkdel(Avl *a, void *v) { Avl *p; Avlwalk *w; Avltree *t; if(a == nil) return; p = findpredecessor(a); t = v; for(w=t->walks; w; w=w->next){ if(w->node == a){ /* back pointer to predecessor; not perfect but adequate */ w->moved = 1; w->node = p; if(p == nil) w->started = 0; } } } void deleteavl(Avltree *t, Avl *key, Avl **oldp) { *oldp = nil; _deleteavl(&t->root, nil, key, t->cmp, oldp, walkdel, t); } Avlwalk* avlwalk(Avltree *t) { Avlwalk *w; w = emalloc(sizeof(*w)); w->tree = t; w->next = t->walks; t->walks = w; return w; } Avl* avlnext(Avlwalk *w) { Avl *a; if(w->started==0){ for(a=w->tree->root; a && a->n[0]; a=a->n[0]) ; w->node = a; w->started = 1; }else{ a = findsuccessor(w->node); if(a == w->node) abort(); w->node = a; } return w->node; } Avl* avlprev(Avlwalk *w) { Avl *a; if(w->started == 0){ for(a=w->tree->root; a && a->n[1]; a=a->n[1]) ; w->node = a; w->started = 1; }else if(w->moved){ w->moved = 0; return w->node; }else{ a = findpredecessor(w->node); if(a == w->node) abort(); w->node = a; } return w->node; } void endwalk(Avlwalk *w) { Avltree *t; Avlwalk **l; t = w->tree; for(l=&t->walks; *l; l=&(*l)->next){ if(*l == w){ *l = w->next; break; } } free(w); } static void walkavl(Avl *t, void (*f)(Avl*, void*), void *v) { if(t == nil) return; walkavl(t->n[0], f, v); f(t, v); walkavl(t->n[1], f, v); }