From 6261dcb06b11c2db815b2e259b25b18a9673d900 Mon Sep 17 00:00:00 2001 From: spew Date: Sat, 22 Apr 2017 14:28:02 -0500 Subject: replica: use libavl for avl tree implementation --- sys/src/cmd/replica/all.h | 27 +-- sys/src/cmd/replica/applychanges.c | 4 +- sys/src/cmd/replica/applylog.c | 4 +- sys/src/cmd/replica/avl.c | 415 ------------------------------------- sys/src/cmd/replica/compactdb.c | 4 +- sys/src/cmd/replica/db.c | 10 +- sys/src/cmd/replica/mkfile | 1 - sys/src/cmd/replica/updatedb.c | 4 +- 8 files changed, 10 insertions(+), 459 deletions(-) delete mode 100644 sys/src/cmd/replica/avl.c (limited to 'sys/src/cmd/replica') diff --git a/sys/src/cmd/replica/all.h b/sys/src/cmd/replica/all.h index 96d8e1f54..5e8148de4 100644 --- a/sys/src/cmd/replica/all.h +++ b/sys/src/cmd/replica/all.h @@ -2,37 +2,14 @@ #include #include #include - -/* avl.c */ -typedef struct Avl Avl; -typedef struct Avltree Avltree; -typedef struct Avlwalk Avlwalk; - -#pragma incomplete Avltree -#pragma incomplete Avlwalk - -struct Avl -{ - Avl *p; /* parent */ - Avl *n[2]; /* children */ - int bal; /* balance bits */ -}; - -Avltree *mkavltree(int(*cmp)(Avl*, Avl*)); -void insertavl(Avltree *tree, Avl *new, Avl **oldp); -Avl *lookupavl(Avltree *tree, Avl *key); -void deleteavl(Avltree *tree, Avl *key, Avl **oldp); -Avlwalk *avlwalk(Avltree *tree); -Avl *avlnext(Avlwalk *walk); -Avl *avlprev(Avlwalk *walk); -void endwalk(Avlwalk *walk); +#include /* db.c */ typedef struct Db Db; typedef struct Entry Entry; struct Entry { - Avl a; + Avl; char *name; struct { char *name; diff --git a/sys/src/cmd/replica/applychanges.c b/sys/src/cmd/replica/applychanges.c index 70534e804..b3823fa8a 100644 --- a/sys/src/cmd/replica/applychanges.c +++ b/sys/src/cmd/replica/applychanges.c @@ -148,7 +148,6 @@ void main(int argc, char **argv) { char *proto; - Avlwalk *w; Dir *xd, d; Entry *e; @@ -190,8 +189,7 @@ main(int argc, char **argv) if(revrdproto(proto, clientroot, serverroot, walk, nil, nil) < 0) sysfatal("rdproto: %r"); - w = avlwalk(db->avl); - while(e = (Entry*)avlprev(w)){ + for(e = (Entry*)avlmax(db->avl); e != nil; e = (Entry*)avlprev(e)){ if(!ismatch(e->name)) continue; if(!e->d.mark){ /* not visited during walk */ diff --git a/sys/src/cmd/replica/applylog.c b/sys/src/cmd/replica/applylog.c index 183011400..63e2721fb 100644 --- a/sys/src/cmd/replica/applylog.c +++ b/sys/src/cmd/replica/applylog.c @@ -175,7 +175,6 @@ main(int argc, char **argv) ulong now; Biobuf bin; Dir dbd, ld, nd, rd; - Avlwalk *w; Entry *e; membogus(argv); @@ -706,8 +705,7 @@ main(int argc, char **argv) } } - w = avlwalk(copyerr->avl); - while(e = (Entry*)avlnext(w)) + for(e = (Entry*)avlmin(copyerr->avl); e != nil; e = (Entry*)avlnext(e)) error("copying %q: %s\n", e->name, e->d.name); if(timefile) diff --git a/sys/src/cmd/replica/avl.c b/sys/src/cmd/replica/avl.c deleted file mode 100644 index 42391ac89..000000000 --- a/sys/src/cmd/replica/avl.c +++ /dev/null @@ -1,415 +0,0 @@ -#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); -} - diff --git a/sys/src/cmd/replica/compactdb.c b/sys/src/cmd/replica/compactdb.c index df9af7809..3fb93ae3d 100644 --- a/sys/src/cmd/replica/compactdb.c +++ b/sys/src/cmd/replica/compactdb.c @@ -15,7 +15,6 @@ usage(void) void main(int argc, char **argv) { - Avlwalk *w; Biobuf bout; Entry *e; @@ -30,8 +29,7 @@ main(int argc, char **argv) Binit(&bout, 1, OWRITE); db = opendb(argv[0]); - w = avlwalk(db->avl); - while(e = (Entry*)avlnext(w)) + for(e = (Entry*)avlmin(db->avl); e != nil; e = (Entry*)avlnext(e)) Bprint(&bout, "%q %q %luo %q %q %lud %lld\n", e->name, strcmp(e->name, e->d.name)==0 ? "-" : e->d.name, e->d.mode, e->d.uid, e->d.gid, e->d.mtime, e->d.length); diff --git a/sys/src/cmd/replica/db.c b/sys/src/cmd/replica/db.c index 29e6b0a39..df63a2a7e 100644 --- a/sys/src/cmd/replica/db.c +++ b/sys/src/cmd/replica/db.c @@ -35,8 +35,7 @@ _removedb(Db *db, char *name) memset(&k, 0, sizeof k); k.name = name; - e = nil; - deleteavl(db->avl, (Avl*)&k, (Avl**)&e); + e = (Entry*)avldelete(db->avl, &k); if(e) freeentry(e); } @@ -48,8 +47,7 @@ _insertdb(Db *db, Entry *e) ne = allocentry(); *ne = *e; - o = nil; - insertavl(db->avl, (Avl*)ne, (Avl**)&o); + o = (Entry*)avlinsert(db->avl, ne); if(o) freeentry(o); } @@ -78,7 +76,7 @@ opendb(char *file) else if((fd = open(file, ORDWR)) < 0) sysfatal("opendb %s: %r", file); db = emalloc(sizeof(Db)); - db->avl = mkavltree(entrycmp); + db->avl = avlcreate(entrycmp); db->fd = fd; if(fd < 0) return db; @@ -118,7 +116,7 @@ _finddb(Db *db, char *name, Dir *d, int domark) memset(&k, 0, sizeof k); k.name = name; - e = (Entry*)lookupavl(db->avl, (Avl*)&k); + e = (Entry*)avllookup(db->avl, &k, 0); if(e == nil) return -1; memset(d, 0, sizeof *d); diff --git a/sys/src/cmd/replica/mkfile b/sys/src/cmd/replica/mkfile index 966bd5c78..61f83d965 100644 --- a/sys/src/cmd/replica/mkfile +++ b/sys/src/cmd/replica/mkfile @@ -15,7 +15,6 @@ TARG=\ $SCRIPTS\ OFILES=\ - avl.$O\ db.$O\ util.$O\ diff --git a/sys/src/cmd/replica/updatedb.c b/sys/src/cmd/replica/updatedb.c index d63a53c0f..126e4de61 100644 --- a/sys/src/cmd/replica/updatedb.c +++ b/sys/src/cmd/replica/updatedb.c @@ -140,7 +140,6 @@ void main(int argc, char **argv) { char *proto; - Avlwalk *w; Dir d; Entry *e; @@ -188,8 +187,7 @@ main(int argc, char **argv) sysfatal("rdproto: %r"); if(!changesonly){ - w = avlwalk(db->avl); - while(e = (Entry*)avlprev(w)){ + for(e = (Entry*)avlmax(db->avl); e != nil; e = (Entry*)avlprev(e)){ if(!ismatch(e->name)) continue; if(!e->d.mark){ /* not visited during walk */ -- cgit v1.2.3