shithub: riscv

Info  •  Files  •  Log  •  Branches

replica: use libavl for avl tree implementation

--- a/sys/include/avl.h

+++ b/sys/include/avl.h

@@ -20,5 +20,7 @@

 Avl *avllookup(Avltree*, Avl*, int);

 Avl *avldelete(Avltree*, Avl*);

 Avl *avlinsert(Avltree*, Avl*);

+Avl *avlmin(Avltree*);

+Avl *avlmax(Avltree*);

 Avl *avlnext(Avl*);

 Avl *avlprev(Avl*);

--- a/sys/man/2/avl

+++ b/sys/man/2/avl

@@ -65,6 +65,12 @@

 removes the node matching the key from the tree and returns

 it. It returns nil if no matching key is found.

 .PP

+.I Avlmin

+returns the minimum

+.B Avl

+node in the tree and

+.I avlmax

+returns the maximum node.

 .I Avlnext

 returns the next 

 .B Avl 

--- a/sys/src/cmd/replica/all.h

+++ b/sys/src/cmd/replica/all.h

@@ -2,37 +2,14 @@

 #include <libc.h>

 #include <bio.h>

 #include <disk.h>

+#include <avl.h>

-/* 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);

-

 /* db.c */

 typedef struct Db Db;

 typedef struct Entry Entry;

 struct Entry

 {

-	Avl a;

+	Avl;

 	char *name;

 	struct {

 		char *name;

--- a/sys/src/cmd/replica/applychanges.c

+++ b/sys/src/cmd/replica/applychanges.c

@@ -148,7 +148,6 @@

 main(int argc, char **argv)

 {

 	char *proto;

-	Avlwalk *w;

 	Dir *xd, d;

 	Entry *e;

@@ -190,8 +189,7 @@

 	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 */

--- a/sys/src/cmd/replica/applylog.c

+++ b/sys/src/cmd/replica/applylog.c

@@ -175,7 +175,6 @@

 	ulong now;

 	Biobuf bin;

 	Dir dbd, ld, nd, rd;

-	Avlwalk *w;

 	Entry *e;

 	membogus(argv);

@@ -706,8 +705,7 @@

 		}

 	}

-	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)

--- a/sys/src/cmd/replica/avl.c

+++ /dev/null

@@ -1,415 +1,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);

-}

-

--- a/sys/src/cmd/replica/compactdb.c

+++ b/sys/src/cmd/replica/compactdb.c

@@ -15,7 +15,6 @@

 void

 main(int argc, char **argv)

 {

-	Avlwalk *w;

 	Biobuf bout;

 	Entry *e;

@@ -30,8 +29,7 @@

 	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);

--- a/sys/src/cmd/replica/db.c

+++ b/sys/src/cmd/replica/db.c

@@ -35,8 +35,7 @@

 	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 @@

 	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 @@

 	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 @@

 	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);

--- a/sys/src/cmd/replica/mkfile

+++ b/sys/src/cmd/replica/mkfile

@@ -15,7 +15,6 @@

 	$SCRIPTS\

 OFILES=\

-	avl.$O\

 	db.$O\

 	util.$O\

--- a/sys/src/cmd/replica/updatedb.c

+++ b/sys/src/cmd/replica/updatedb.c

@@ -140,7 +140,6 @@

 main(int argc, char **argv)

 {

 	char *proto;

-	Avlwalk *w;

 	Dir d;

 	Entry *e;

@@ -188,8 +187,7 @@

 		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 */

--- a/sys/src/libavl/avl.c

+++ b/sys/src/libavl/avl.c

@@ -310,3 +310,32 @@

 		q = p;

 	return p;

 }

+

+static Avl *bottom(Avltree*,int);

+

+Avl*

+avlmin(Avltree *t)

+{

+	return bottom(t, 0);

+}

+

+Avl*

+avlmax(Avltree *t)

+{

+	return bottom(t, 1);

+}

+

+static Avl*

+bottom(Avltree *t, int d)

+{

+	Avl *n;

+

+	if(t == nil)

+		return nil;

+	if(t->root == nil)

+		return nil;

+

+	for(n = t->root; n->c[d] != nil; n = n->c[d])

+		;

+	return n;

+}