alv(2): new avl implementation

5 files changed, 336 insertions, 502 deletions

diff --git a/sys/include/avl.h b/sys/include/avl.h
index 242ee1ba3..49b61fbb6 100644
--- a/sys/include/avl.h
+++ b/sys/include/avl.h
@@ -1,26 +1,23 @@
-#pragma	lib	"libavl.a"
+#pragma lib "libavl.a"
 #pragma src "/sys/src/libavl"
 
-typedef struct Avl	Avl;
-typedef struct Avltree	Avltree;
-typedef struct Avlwalk	Avlwalk;
+typedef struct Avl Avl;
+typedef struct Avltree Avltree;
 
-#pragma incomplete Avltree
-#pragma incomplete Avlwalk
+struct Avl {
+	Avl *c[2];
+	Avl *p;
+	schar balance;
+};
 
-struct Avl
-{
-	Avl	*p;		/* parent */
-	Avl	*n[2];		/* children */
-	int	bal;		/* balance bits */
+struct Avltree {
+	int (*cmp)(Avl*, Avl*);
+	Avl *root;
 };
 
-Avl	*avlnext(Avlwalk *walk);
-Avl	*avlprev(Avlwalk *walk);
-Avlwalk	*avlwalk(Avltree *tree);
-void	deleteavl(Avltree *tree, Avl *key, Avl **oldp);
-void	endwalk(Avlwalk *walk);
-void	insertavl(Avltree *tree, Avl *new, Avl **oldp);
-Avl	*lookupavl(Avltree *tree, Avl *key);
-Avltree	*mkavltree(int(*cmp)(Avl*, Avl*));
-Avl*	searchavl(Avltree *tree, Avl *key, int neighbor);
+Avltree *avlcreate(int(*cmp)(Avl*, Avl*));
+Avl *avllookup(Avltree*, Avl*);
+Avl *avldelete(Avltree*, Avl*);
+Avl *avlinsert(Avltree*, Avl*);
+Avl *avlnext(Avl*);
+Avl *avlprev(Avl*);
diff --git a/sys/man/2/avl b/sys/man/2/avl
index 681f1dcc3..fde1cead1 100644
--- a/sys/man/2/avl
+++ b/sys/man/2/avl
@@ -1,147 +1,119 @@
 .TH AVL 2
 .SH NAME
-mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines
+avlcreate,
+avlinsert,
+avldelete,
+avllookup,
+avlnext,
+avlprev \- Balanced binary search tree routines
 .SH SYNOPSIS
-.\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i
-.ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i
+.ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i
+.\" .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i
 .EX
 #include <u.h>
 #include <libc.h>
 #include <avl.h>
-.sp 0.3v
+
 typedef struct Avl Avl;
-struct Avl
-{
-	Avl	*p;		/* parent */
-	Avl	*n[2];		/* children */
-	int	bal;		/* balance bits */
+typedef struct Avltree Avltree;
+
+struct Avl {
+	Avl *c[2];      /* children */
+	Avl *p;	        /* parent */
+	schar balance;  /* balance factor */
+};
+struct Avltree {
+	int (*cmp)(Avl*, Avl*);
+	Avl *root;
 };
-.sp 0.3v
-Avl	*avlnext(Avlwalk *walk);
-Avl	*avlprev(Avlwalk *walk);
-Avlwalk	*avlwalk(Avltree *tree);
-void	deleteavl(Avltree *tree, Avl *key, Avl **oldp);
-void	endwalk(Avlwalk *walk);
-void	insertavl(Avltree *tree, Avl *new, Avl **oldp);
-Avl	*lookupavl(Avltree *tree, Avl *key);
-Avl	*searchavl(Avltree *tree, Avl *key, int neighbor);
-Avltree	*mkavltree(int(*cmp)(Avl*, Avl*));
+
+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     *avlnext(Avl *n);
+Avl     *avlprev(Avl *n);
+
 .EE
 .SH DESCRIPTION
-An AVL tree is a self-balancing binary search tree.
-These routines allow creation and maintenance of in-memory AVL trees.
+These routines allow creation and maintenance of in-memory balanced
+binary search trees.
 .PP
-An empty AVL tree is created by calling
-.I mkavltree
-with a comparison function as argument.
-This function should take two pointers to
+An empty tree is created by calling
+.I avlcreate
+with a comparison function as an argument.
+The comparison function must take two pointers to
 .B Avl
-objects and return -1, 0 or 1 as the first is
+structures and return an integer less than, equal to, or
+greater than 0 as the first is
 respectively less than,
-equal to, or greater than,
-the second.
-.I Insertavl
-adds a
-.I new
-tree node into
-.IR tree .
-If
-.I oldp
-is non-nil upon return,
-it points to storage for an old node
-with the same key that may now be freed.
-.I Lookupavl
-returns the
-.I tree
-node that matches
-.I key
-by
-.IR tree 's
-comparison function,
-or
-.B nil
-if none.
+equal to, or greater than the second.
 .PP
-.I Searchavl
+.I Avlinsert
+adds a new
+node into the tree and returns an existing
+node with the same key that has been removed
+from the tree and may be freed.
+.I Avllookup
 returns the
-.I tree
-node that matches
-.I key
-by
-.IR tree 's
-comparison function, if it exists.
-If it does not, and
-.I neighbor
-is positive, it returns the nearest node whose
-.I key
-is greater or
-.B nil
-if there is none and, if
-.I neighbor
-is negative, it returns the nearest node whose
-.I key
-is less or
+node that matches the key or
 .B nil
-if there is none.
-It is an error to set
-.I neighbor
-to values other than \-1, 0, or +1.
+if no node matches.
+.I Avldelete
+removes the node matching the key from the tree and returns
+it. It returns nil of no matching key is found.
 .PP
-.I Deleteavl
-removes the node matching
-.I key
-from
-.IR tree ;
-.I oldp
-is handled as per
-.IR insertavl .
-.PP
-.I Avlwalk
-returns a pointer to a newly-allocated
-.B Avlwalk
-object.
-.I Endwalk
-frees such an object.
 .I Avlnext
+returns the next 
+.B Avl 
+node in an in-order walk of the AVL tree
 and
 .I avlprev
-walk the tree associated with
-.IR walk ,
-returning the next
-(respectively, previous)
-tree node in the comparison order
-defined by the comparison function
-associated with the tree associated with
-.IR walk .
+returns the previous node.
 .SH EXAMPLES
-Intended usage seems to be to make an anonymous
+Intended usage is to embed the
 .B Avl
-the first member of the application's tree-node structure,
-then pass these routines tree-node pointers instead of
-.BR Avl* s.
+structure anonymously.
+For example, the following will create a key-value store
+with strings as keys and integers as values.
 .IP
 .EX
 typedef struct Node {
 	Avl;
-	uchar	score[VtScoreSize];
-	int	type;
+	char *key;
+	int val;
 } Node;
-.sp 0.3v
-Avltree *tree;
-Avl *res;
-Node *np;
+
+int
+nodecmp(Avl *la, Avl *lb)
+{
+	Node *a, *b;
+
+	a = (Node*)la;
+	b = (Node*)lb;
+	return strcmp(a->key, b->key);
+}
+
+int
+get(char *key)
+{
+	Node *h, n;
+
+	n.key = key;
+	h = (Node*)avllookup(&n);
+	return h ? h->val : -1;
+}
 \fI\&...\fP
-	res = lookupavl(tree, np);
+	Avltree *t = avlcreate(AVL, nodecmp);
+
 .EE
 .SH SOURCE
 .B /sys/src/libavl
 .SH SEE ALSO
-G. M. Adelson-Velsky,
-E. M. Landis,
-``An algorithm for the organization of information'',
-.IR "Soviet Mathematics" ,
-Vol. 3, pp. 1256—1263.
+.nf
+Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3
 .SH DIAGNOSTICS
-Functions returning pointers return
-.B nil
-on error.
+.I Avlcreate
+returns nil on error.
+.SH HISTORY
+This implementation was written for 9front (Dec, 2016).
diff --git a/sys/src/cmd/venti/copy.c b/sys/src/cmd/venti/copy.c
index db07dcb9d..436ce418a 100644
--- a/sys/src/cmd/venti/copy.c
+++ b/sys/src/cmd/venti/copy.c
@@ -19,7 +19,7 @@ uchar zeroscore[VtScoreSize];	/* all zeros */
 typedef struct ScoreTree ScoreTree;
 struct ScoreTree
 {
-	Avl avl;
+	Avl;
 	uchar score[VtScoreSize];
 	int type;
 };
@@ -51,21 +51,20 @@ havevisited(uchar score[VtScoreSize], int type)
 		return 0;
 	memmove(a.score, score, VtScoreSize);
 	a.type = type;
-	return lookupavl(scoretree, &a.avl) != nil;
+	return avllookup(scoretree, &a) != nil;
 }
 
 static void
 markvisited(uchar score[VtScoreSize], int type)
 {
 	ScoreTree *a;
-	Avl *old;
 
 	if(scoretree == nil)
 		return;
 	a = binalloc(&scorebin, sizeof *a, 1);
 	memmove(a->score, score, VtScoreSize);
 	a->type = type;
-	insertavl(scoretree, &a->avl, &old);
+	avlinsert(scoretree, a);
 }
 
 void
@@ -196,7 +195,7 @@ main(int argc, char *argv[])
 		ignoreerrors = 1;
 		break;
 	case 'm':
-		scoretree = mkavltree(scoretreecmp);
+		scoretree = avlcreate(scoretreecmp);
 		break;
 	case 'r':
 		if(ignoreerrors)
diff --git a/sys/src/libavl/avl.c b/sys/src/libavl/avl.c
index 59266d36d..ebad131dd 100644
--- a/sys/src/libavl/avl.c
+++ b/sys/src/libavl/avl.c
@@ -1,436 +1,306 @@
 #include <u.h>
 #include <libc.h>
-#include <bio.h>
 #include <avl.h>
 
-/*
- * In-memory database stored as self-balancing AVL tree.
- * See Lewis & Denenberg, Data Structures and Their Algorithms.
- */
+/* See Knuth Volume 3, 6.2.3 */
 
-static void
-singleleft(Avl **tp, Avl *p)
-{
-	int l, r2;
-	Avl *a, *c;
-
-	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;
+Avl *avllookup(Avltree*, Avl*);
+Avl *avldelete(Avltree*, Avl*);
+Avl *avlinsert(Avltree*, Avl*);
 
-	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)
+Avltree*
+avlcreate(int (*cmp)(Avl*, Avl*))
 {
-	int l2, r;
-	Avl *a, *c;
-
-	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;
+	Avltree *t;
 
-	if((*tp = c) != nil)
-		(*tp)->p = p;
+	t = malloc(sizeof(*t));
+	if(t == nil)
+		return nil;
 
-	a->bal = r;
-	c->bal = ((r > 0? r: 0)+1) - l2;
+	t->cmp = cmp;
+	t->root = nil;
+	return t;
 }
 
-static void
-doublerightleft(Avl **tp, Avl *p)
+Avl*
+avllookup(Avltree *t, Avl *k)
 {
-	singleright(&(*tp)->n[1], *tp);
-	singleleft(tp, p);
+	Avl *h;
+	int c;
+
+	h = t->root;
+	while(h != nil){
+		c = (t->cmp)(k, h);
+		if(c < 0){
+			h = h->c[0];
+			continue;
+		}
+		if(c > 0){
+			h = h->c[1];
+			continue;
+		}
+		return h;
+	}
+	return nil;
 }
 
-static void
-doubleleftright(Avl **tp, Avl *p)
-{
-	singleleft(&(*tp)->n[0], *tp);
-	singleright(tp, p);
-}
+static int insert(int (*)(Avl*, Avl*), Avl*, Avl**, Avl*, Avl**);
 
-static void
-balance(Avl **tp, Avl *p)
+Avl*
+avlinsert(Avltree *t, Avl *k)
 {
-	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;
-	}
+	Avl *old;
+
+	old = nil;
+	insert(t->cmp, nil, &t->root, k, &old);
+	return old;
 }
 
+static int insertfix(int, Avl**);
+
 static int
-canoncmp(int cmp)
+insert(int (*cmp)(Avl*, Avl*), Avl *p, Avl **qp, Avl *k, Avl **oldp)
 {
-	if(cmp < 0)
-		return -1;
-	else if(cmp > 0)
+	Avl *q;
+	int fix, c;
+
+	q = *qp;
+	if(q == nil) {
+		k->c[0] = nil;
+		k->c[1] = nil;
+		k->balance = 0;
+		k->p = p;
+		*qp = k;
 		return 1;
+	}
+
+	c = cmp(k, q);
+	c = c > 0 ? 1 : c < 0 ? -1: 0;
+	if(c == 0) {
+		*oldp = q;
+		*k = *q;
+		if(q->c[0] != nil)
+			q->c[0]->p = k;
+		if(q->c[1] != nil)
+			q->c[1]->p = k;
+		*qp = k;
+		return 0;
+	}
+	fix = insert(cmp, q, q->c + (c+1)/2, k, oldp);
+	if(fix)
+		return insertfix(c, qp);
 	return 0;
 }
 
+static Avl *singlerot(int, Avl*);
+static Avl *doublerot(int, Avl*);
+
 static int
-_insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
+insertfix(int c, Avl **t)
 {
-	int i, ob;
-
-	if(*tp == nil){
-		r->bal = 0;
-		r->n[0] = nil;
-		r->n[1] = nil;
-		r->p = p;
-		*tp = r;
+	Avl *s;
+
+	s = *t;
+	if(s->balance == 0) {
+		s->balance = c;
 		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;
+	if(s->balance == -c) {
+		s->balance = 0;
+		return 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;
-
+	if(s->c[(c+1)/2]->balance == c)
+		s = singlerot(c, s);
+	else
+		s = doublerot(c, s);
+	*t = s;
 	return 0;
 }
 
-static int
-successor(Avl **tp, Avl *p, Avl **r)
+static int delete(int (*cmp)(Avl*, Avl*), Avl**, Avl*, Avl**);
+static int deletemin(Avl**, Avl**);
+static int deletefix(int, Avl**);
+
+Avl*
+avldelete(Avltree *t, Avl *k)
 {
-	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);
+	Avl *old;
+
+	if(t->root == nil)
+		return nil;
+	old = nil;
+	delete(t->cmp, &t->root, k, &old);
+	return old;
 }
 
 static int
-_deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
-	void (*predel)(Avl*, void*), void *arg)
+delete(int (*cmp)(Avl*, Avl*), Avl **qp, Avl *k, Avl **oldp)
 {
-	int i, ob;
-	Avl *r, *or;
+	Avl *q, *e;
+	int c, fix;
 
-	if(*tp == nil)
+	q = *qp;
+	if(q == 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;
+	c = cmp(k, q);
+	c = c > 0 ? 1 : c < 0 ? -1: 0;
+	if(c == 0) {
+		*oldp = q;
+		if(q->c[1] == nil) {
+			*qp = q->c[0];
+			if(*qp != nil)
+				(*qp)->p = q->p;
+			return 1;
+		}
+		fix = deletemin(q->c+1, &e);
+		*e = *q;
+		if(q->c[0] != nil)
+			q->c[0]->p = e;
+		if(q->c[1] != nil)
+			q->c[1]->p = e;
+		*qp = e;
+		if(fix)
+			return deletefix(-1, qp);
+		return 0;
 	}
-
-	/* 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);
+	fix = delete(cmp, q->c + (c+1)/2, k, oldp);
+	if(fix)
+		return deletefix(-c, qp);
+	return 0;
 }
 
-static void
-checkparents(Avl *a, Avl *p)
+static int
+deletemin(Avl **qp, Avl **oldp)
 {
-	if(a == nil)
-		return;
-	if(a->p != p)
-		print("bad parent\n");
-	checkparents(a->n[0], a);
-	checkparents(a->n[1], a);
+	Avl *q;
+	int fix;
+
+	q = *qp;
+	if(q->c[0] == nil) {
+		*oldp = q;
+		*qp = q->c[1];
+		if(*qp != nil)
+			(*qp)->p = q->p;
+		return 1;
+	}
+	fix = deletemin(q->c, oldp);
+	if(fix)
+		return deletefix(1, qp);
+	return 0;
 }
 
-struct Avltree
-{
-	Avl	*root;
-	int	(*cmp)(Avl*, Avl*);
-	Avlwalk	*walks;
-};
-struct Avlwalk
-{
-	int	started;
-	int	moved;
-	Avlwalk	*next;
-	Avltree	*tree;
-	Avl	*node;
-};
+static Avl *rotate(int, Avl*);
 
-Avltree*
-mkavltree(int (*cmp)(Avl*, Avl*))
+static int
+deletefix(int c, Avl **t)
 {
-	Avltree *t;
+	Avl *s;
+	int a;
 
-	t = malloc(sizeof *t);
-	if(t == nil)
-		return nil;
-	memset(t, 0, 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);
+	s = *t;
+	if(s->balance == 0) {
+		s->balance = c;
+		return 0;
+	}
+	if(s->balance == -c) {
+		s->balance = 0;
+		return 1;
+	}
+	a = (c+1)/2;
+	if(s->c[a]->balance == 0) {
+		s = rotate(c, s);
+		s->balance = -c;
+		*t = s;
+		return 0;
+	}
+	if(s->c[a]->balance == c)
+		s = singlerot(c, s);
+	else
+		s = doublerot(c, s);
+	*t = s;
+	return 1;
 }
 
 static Avl*
-findpredecessor(Avl *a)
+singlerot(int c, Avl *s)
 {
-	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;
-	}
+	s->balance = 0;
+	s = rotate(c, s);
+	s->balance = 0;
+	return s;
 }
 
 static Avl*
-findsuccessor(Avl *a)
+doublerot(int c, Avl *s)
 {
-	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;
-	}
+	Avl *r, *p;
+	int a;
+
+	a = (c+1)/2;
+	r = s->c[a];
+	s->c[a] = rotate(-c, s->c[a]);
+	p = rotate(c, s);
+	assert(r->p == p);
+	assert(s->p == p);
+
+	if(p->balance == c) {
+		s->balance = -c;
+		r->balance = 0;
+	} else if(p->balance == -c) {
+		s->balance = 0;
+		r->balance = c;
+	} else
+		s->balance = r->balance = 0;
+	p->balance = 0;
+	return p;
 }
 
 static Avl*
-_lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*), int neighbor)
+rotate(int c, Avl *s)
 {
-	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 *r, *n;
+	int a;
+
+	a = (c+1)/2;
+	r = s->c[a];
+	s->c[a] = n = r->c[a^1];
+	if(n != nil)
+		n->p = s;
+	r->c[a^1] = s;
+	r->p = s->p;
+	s->p = r;
+	return r;
 }
 
+static Avl *walk1(int, Avl*);
+
 Avl*
-searchavl(Avltree *t, Avl *key, int neighbor)
+avlprev(Avl *q)
 {
-	return _lookupavl(t->root, key, t->cmp, neighbor);
+	return walk1(0, q);
 }
 
 Avl*
-lookupavl(Avltree *t, Avl *key)
+avlnext(Avl *q)
 {
-	return _lookupavl(t->root, key, t->cmp, 0);
+	return walk1(1, q);
 }
 
-static void
-walkdel(Avl *a, void *v)
+static Avl*
+walk1(int a, Avl *q)
 {
 	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 = malloc(sizeof *w);
-	if(w == nil)
+	if(q == nil)
 		return nil;
-	memset(w, 0, 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])
+	if(q->c[a] != nil){
+		for(q = q->c[a]; q->c[a^1] != nil; q = q->c[a^1])
 			;
-		w->node = a;
-		w->started = 1;
-	}else{
-		a = findsuccessor(w->node);
-		if(a == w->node)
-			abort();
-		w->node = a;
+		return q;
 	}
-	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);
+	for(p = q->p; p != nil && p->c[a] == q; p = p->p)
+		q = p;
+	return p;
 }
diff --git a/sys/src/libavl/mkfile b/sys/src/libavl/mkfile
index cebd5806e..b6ff884b8 100644
--- a/sys/src/libavl/mkfile
+++ b/sys/src/libavl/mkfile
@@ -1,15 +1,11 @@
 </$objtype/mkfile
 
 LIB=/$objtype/lib/libavl.a
+
 OFILES=\
 	avl.$O\
 
-HFILES=/sys/include/avl.h
-
-UPDATE=\
-	mkfile\
-	$HFILES\
-	${OFILES:%.$O=%.c}\
-	${LIB:/$objtype/%=/386/%}\
+HFILES=\
+	/sys/include/avl.h\
 
 </sys/src/cmd/mksyslib