libavl: lookup can return the closest match

1 files changed, 13 insertions, 7 deletions

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