shithub: riscv

Info  •  Files  •  Log  •  Branches

libavl: lookup can return the closest match

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

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

@@ -15,8 +15,9 @@

 	Avl *root;

 };

-Avltree *avlcreate(int(*cmp)(Avl*, Avl*));

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

+Avltree *avlinit(Avltree*, int(*)(Avl*, Avl*));

+Avltree *avlcreate(int(*)(Avl*, Avl*));

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

 Avl *avldelete(Avltree*, Avl*);

 Avl *avlinsert(Avltree*, Avl*);

 Avl *avlnext(Avl*);

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

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

@@ -30,7 +30,7 @@

 Avltree *avlcreate(int(*cmp)(Avl*, Avl*));

 Avl     *avlinsert(Avltree *tree, Avl *new);

 Avl     *avldelete(Avltree *tree, Avl *key);

-Avl     *avllookup(Avltree *tree, Avl *key);

+Avl     *avllookup(Avltree *tree, Avl *key, int dir);

 Avl     *avlnext(Avl *n);

 Avl     *avlprev(Avl *n);

@@ -55,13 +55,15 @@

 node with the same key that has been removed

 from the tree and may be freed.

 .I Avllookup

-returns the

-node that matches the key or

-.B nil

-if no node matches.

+searches for a given key and returns

+the closest node less than the given key, 

+.BR nil ,

+or the closest node greater than the key depending on whether

+.I dir

+is less than, equal to, or greater than zero, respectively.

 .I Avldelete

 removes the node matching the key from the tree and returns

-it. It returns nil of no matching key is found.

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

 .PP

 .I Avlnext

 returns the next 

--- a/sys/src/cmd/upas/fs/mtree.c

+++ b/sys/src/cmd/upas/fs/mtree.c

@@ -22,7 +22,7 @@

 		return 0;

 	memset(&t, 0, sizeof t);

 	t.m = m;

-	if(avllookup(mb->mtree, &t))

+	if(avllookup(mb->mtree, &t, 0))

 		return 1;

 	return 0;

 }

@@ -36,7 +36,7 @@

 	m0.digest = digest;

 	memset(&t, 0, sizeof t);

 	t.m = &m0;

-	if(p = (Mtree*)avllookup(mb->mtree, &t))

+	if(p = (Mtree*)avllookup(mb->mtree, &t, 0))

 		return p->m;

 	return nil;

 }

@@ -65,7 +65,7 @@

 	if(m->deleted & ~Deleted){

 		if(m->digest == nil)

 			return;

-		p = (Mtree*)avllookup(mb->mtree, &t);

+		p = (Mtree*)avllookup(mb->mtree, &t, 0);

 		if(p == nil || p->m != m)

 			return;

 		p = (Mtree*)avldelete(mb->mtree, &t);

--- a/sys/src/cmd/upas/imap4d/fstree.c

+++ b/sys/src/cmd/upas/imap4d/fstree.c

@@ -25,7 +25,7 @@

 	memset(&t, 0, sizeof t);

 	m0.id = id;

 	t.m = &m0;

-	if(p = (Fstree*)avllookup(mb->fstree, &t))

+	if(p = (Fstree*)avllookup(mb->fstree, &t, 0))

 		return p->m;

 	return nil;

 }

--- a/sys/src/cmd/upas/imap4d/imp.c

+++ b/sys/src/cmd/upas/imap4d/imp.c

@@ -100,7 +100,7 @@

 		memset(&t, 0, sizeof t);

 		m0.info[Idigest] = f[0];

 		t.m = &m0;

-		p = (Mtree*)avllookup(mtree, &t);

+		p = (Mtree*)avllookup(mtree, &t, 0);

 		if(p){

 			m = p->m;

 			if(m->uid && m->uid != u){

--- a/sys/src/cmd/venti/copy.c

+++ b/sys/src/cmd/venti/copy.c

@@ -51,7 +51,7 @@

 		return 0;

 	memmove(a.score, score, VtScoreSize);

 	a.type = type;

-	return avllookup(scoretree, &a) != nil;

+	return avllookup(scoretree, &a, 0) != nil;

 }

 static void

--- a/sys/src/games/galaxy/simulate.c

+++ b/sys/src/games/galaxy/simulate.c

@@ -6,9 +6,9 @@

 int extraproc = -1, throttle;

-static QLock* golock;

-static Rendez* gorend;

-static int* go;

+static QLock *golock;

+static Rendez *gorend;

+static int *go;

 static QLock runninglock;

 static Rendez runningrend;

--- a/sys/src/games/mix/mix.c

+++ b/sys/src/games/mix/mix.c

@@ -413,7 +413,7 @@

 	Sym *s, l;

 	l.name = name;

-	s = (Sym*)avllookup(syms, &l);

+	s = (Sym*)avllookup(syms, &l, 0);

 	if(s != nil)

 		return s;

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

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

@@ -4,10 +4,6 @@

 /* See Knuth Volume 3, 6.2.3 */

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

-Avl *avldelete(Avltree*, Avl*);

-Avl *avlinsert(Avltree*, Avl*);

-

 Avltree*

 avlcreate(int (*cmp)(Avl*, Avl*))

 {

@@ -16,7 +12,12 @@

 	t = malloc(sizeof(*t));

 	if(t == nil)

 		return nil;

+	return avlinit(t, cmp);

+}

+Avltree*

+avlinit(Avltree *t, int (*cmp)(Avl*, Avl*))

+{

 	t->cmp = cmp;

 	t->root = nil;

 	return t;

@@ -23,25 +24,30 @@

 }

 Avl*

-avllookup(Avltree *t, Avl *k)

+avllookup(Avltree *t, Avl *k, int d)

 {

-	Avl *h;

+	Avl *h, *n;

 	int c;

+	n = nil;

 	h = t->root;

 	while(h != nil){

 		c = (t->cmp)(k, h);

 		if(c < 0){

+			if(d > 0)

+				n = h;

 			h = h->c[0];

 			continue;

 		}

 		if(c > 0){

+			if(d < 0)

+				n = h;

 			h = h->c[1];

 			continue;

 		}

 		return h;

 	}

-	return nil;

+	return n;

 }

 static int insert(int (*)(Avl*, Avl*), Avl*, Avl**, Avl*, Avl**);