shithub: riscv

Info  •  Files  •  Log  •  Branches

alv(2): new avl implementation

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

--- 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 */

 };

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

+struct Avltree {

+	int (*cmp)(Avl*, Avl*);

+	Avl *root;

+};

+

+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

+node that matches the key or

 .B nil

-if there is none and, if

-.I neighbor

-is negative, it returns the nearest node whose

-.I key

-is less 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).

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

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

@@ -19,7 +19,7 @@

 typedef struct ScoreTree ScoreTree;

 struct ScoreTree

 {

-	Avl avl;

+	Avl;

 	uchar score[VtScoreSize];

 	int type;

 };

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

 		return 0;

 	memmove(a.score, score, VtScoreSize);

 	a.type = type;

-	return lookupavl(scoretree, &a.avl) != nil;

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

 }

 static void

@@ -58,7 +58,6 @@

 markvisited(uchar score[VtScoreSize], int type)

 {

 	ScoreTree *a;

-	Avl *old;

 	if(scoretree == nil)

 		return;

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

 	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 @@

 		ignoreerrors = 1;

 		break;

 	case 'm':

-		scoretree = mkavltree(scoretreecmp);

+		scoretree = avlcreate(scoretreecmp);

 		break;

 	case 'r':

 		if(ignoreerrors)

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

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

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

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

+

+Avltree*

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

 {

-	int l, r2;

-	Avl *a, *c;

+	Avltree *t;

-	a = *tp;

-	c = a->n[1];

+	t = malloc(sizeof(*t));

+	if(t == nil)

+		return nil;

-	r2 = c->bal;

-	l = (r2 > 0? r2: 0)+1 - a->bal;

-

-	if((a->n[1] = c->n[0]) != nil)

-		a->n[1]->p = a;

-

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

-

+	t->cmp = cmp;

+	t->root = nil;

+	return t;

 }

-static void

-singleright(Avl **tp, Avl *p)

+Avl*

+avllookup(Avltree *t, Avl *k)

 {

-	int l2, r;

-	Avl *a, *c;

+	Avl *h;

+	int 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;

-

-	if((*tp = c) != nil)

-		(*tp)->p = p;

-

-	a->bal = r;

-	c->bal = ((r > 0? r: 0)+1) - l2;

+	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

-doublerightleft(Avl **tp, Avl *p)

-{

-	singleright(&(*tp)->n[1], *tp);

-	singleleft(tp, p);

-}

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

-static void

-doubleleftright(Avl **tp, Avl *p)

+Avl*

+avlinsert(Avltree *t, Avl *k)

 {

-	singleleft(&(*tp)->n[0], *tp);

-	singleright(tp, p);

-}

+	Avl *old;

-static void

-balance(Avl **tp, Avl *p)

-{

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

-	}

+	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;

+	Avl *s;

-	if(*tp == nil){

-		r->bal = 0;

-		r->n[0] = nil;

-		r->n[1] = nil;

-		r->p = p;

-		*tp = r;

+	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;

+	Avl *old;

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

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

+	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;

 	}

+	fix = delete(cmp, q->c + (c+1)/2, k, oldp);

+	if(fix)

+		return deletefix(-c, qp);

+	return 0;

+}

-	if(predel)

-		(*predel)(*tp, arg);

+static int

+deletemin(Avl **qp, Avl **oldp)

+{

+	Avl *q;

+	int fix;

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

+	q = *qp;

+	if(q->c[0] == nil) {

+		*oldp = q;

+		*qp = q->c[1];

+		if(*qp != nil)

+			(*qp)->p = q->p;

+		return 1;

 	}

-

-	/* 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 = deletemin(q->c, oldp);

+	if(fix)

+		return deletefix(1, qp);

+	return 0;

 }

-static void

-checkparents(Avl *a, Avl *p)

-{

-	if(a == nil)

-		return;

-	if(a->p != p)

-		print("bad parent\n");

-	checkparents(a->n[0], a);

-	checkparents(a->n[1], a);

-}

+static Avl *rotate(int, Avl*);

-struct Avltree

+static int

+deletefix(int c, Avl **t)

 {

-	Avl	*root;

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

-	Avlwalk	*walks;

-};

-struct Avlwalk

-{

-	int	started;

-	int	moved;

-	Avlwalk	*next;

-	Avltree	*tree;

-	Avl	*node;

-};

+	Avl *s;

+	int a;

-Avltree*

-mkavltree(int (*cmp)(Avl*, Avl*))

-{

-	Avltree *t;

-

-	t = malloc(sizeof *t);

-	if(t == nil)

-		return nil;

-	memset(t, 0, sizeof *t);

-	t->cmp = cmp;

-	return t;

+	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;

 }

-void

-insertavl(Avltree *t, Avl *new, Avl **oldp)

-{

-	*oldp = nil;

-	_insertavl(&t->root, nil, new, t->cmp, oldp);

-}

-

 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;

+	Avl *r, *p;

+	int a;

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

-	}

+	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;

+	Avl *r, *n;

+	int a;

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

+	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;

 }

--- 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