venti: import changes from plan 9

R=rsc
CC=plan9port.codebot
http://codereview.appspot.com/4523057

1 files changed, 47 insertions, 25 deletions

diff --git a/src/libavl/avl.c b/src/libavl/avl.c
index b2c2f7d9..ab8e81d2 100644
--- a/src/libavl/avl.c
+++ b/src/libavl/avl.c
@@ -97,6 +97,16 @@ balance(Avl **tp, Avl *p)
 }
 
 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;
@@ -110,7 +120,7 @@ _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
 		return 1;
 	}
 	ob = (*tp)->bal;
-	if((i = cmp(r, *tp)) != 0){
+	if((i = canoncmp(cmp(r, *tp))) != 0){
 		(*tp)->bal += i * _insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp,
 			rfree);
 		balance(tp, p);
@@ -129,23 +139,6 @@ _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
 	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 = 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)
 {
@@ -175,7 +168,7 @@ _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
 		return 0;
 
 	ob = (*tp)->bal;
-	if((i=cmp(rx, *tp)) != 0){
+	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);
@@ -259,12 +252,6 @@ insertavl(Avltree *t, Avl *new, Avl **oldp)
 	_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)
 {
@@ -303,6 +290,41 @@ findsuccessor(Avl *a)
 	}
 }
 
+static Avl*
+_lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*), int neighbor)
+{
+	int i;
+	Avl *p;
+
+	p = nil;
+	if(t == nil)
+		return nil;
+	do{
+		assert(t->p == p);
+		if((i = canoncmp(cmp(r, t))) == 0)
+			return t;
+		p = t;
+		t = t->n[(i+1)/2];
+	}while(t);
+	if(neighbor == 0)
+		return nil;
+	if(neighbor < 0)
+		return i > 0 ? p : findpredecessor(p);
+	return i < 0 ? p : findsuccessor(p);
+}
+
+Avl*
+searchavl(Avltree *t, Avl *key, int neighbor)
+{
+	return _lookupavl(t->root, key, t->cmp, neighbor);
+}
+
+Avl*
+lookupavl(Avltree *t, Avl *key)
+{
+	return _lookupavl(t->root, key, t->cmp, 0);
+}
+
 static void
 walkdel(Avl *a, void *v)
 {