libavl: lookup can return the closest match

7 files changed, 23 insertions, 17 deletions

diff --git a/sys/src/cmd/upas/fs/mtree.c b/sys/src/cmd/upas/fs/mtree.c
index 4f2af5655..d50deaef5 100644
--- a/sys/src/cmd/upas/fs/mtree.c
+++ b/sys/src/cmd/upas/fs/mtree.c
@@ -22,7 +22,7 @@ mtreeisdup(Mailbox *mb, Message *m)
 		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 @@ mtreefind(Mailbox *mb, uchar *digest)
 	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 @@ mtreedelete(Mailbox *mb, Message *m)
 	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);
diff --git a/sys/src/cmd/upas/imap4d/fstree.c b/sys/src/cmd/upas/imap4d/fstree.c
index 13ef32b7c..ee491c3fc 100644
--- a/sys/src/cmd/upas/imap4d/fstree.c
+++ b/sys/src/cmd/upas/imap4d/fstree.c
@@ -25,7 +25,7 @@ fstreefind(Box *mb, int id)
 	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;
 }
diff --git a/sys/src/cmd/upas/imap4d/imp.c b/sys/src/cmd/upas/imap4d/imp.c
index c5542eab7..a8a96fb28 100644
--- a/sys/src/cmd/upas/imap4d/imp.c
+++ b/sys/src/cmd/upas/imap4d/imp.c
@@ -100,7 +100,7 @@ rdimp(Biobuf *b, Box *box)
 		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){
diff --git a/sys/src/cmd/venti/copy.c b/sys/src/cmd/venti/copy.c
index 436ce418a..c9364fc4b 100644
--- a/sys/src/cmd/venti/copy.c
+++ b/sys/src/cmd/venti/copy.c
@@ -51,7 +51,7 @@ havevisited(uchar score[VtScoreSize], int type)
 		return 0;
 	memmove(a.score, score, VtScoreSize);
 	a.type = type;
-	return avllookup(scoretree, &a) != nil;
+	return avllookup(scoretree, &a, 0) != nil;
 }
 
 static void
diff --git a/sys/src/games/galaxy/simulate.c b/sys/src/games/galaxy/simulate.c
index 4622b6421..9fbf135ac 100644
--- 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;
diff --git a/sys/src/games/mix/mix.c b/sys/src/games/mix/mix.c
index 1672afaaf..2eb993fca 100644
--- a/sys/src/games/mix/mix.c
+++ b/sys/src/games/mix/mix.c
@@ -413,7 +413,7 @@ sym(char *name)
 	Sym *s, l;
 
 	l.name = name;
-	s = (Sym*)avllookup(syms, &l);
+	s = (Sym*)avllookup(syms, &l, 0);
 	if(s != nil)
 		return s;
 
diff --git a/sys/src/libavl/avl.c b/sys/src/libavl/avl.c
index 615de4957..8f1c8b075 100644
--- 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,32 +12,42 @@ avlcreate(int (*cmp)(Avl*, Avl*))
 	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;
 }
 
 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**);