libavl: import from Plan 9

4 files changed, 570 insertions, 0 deletions

diff --git a/include/avl.h b/include/avl.h
new file mode 100644
index 00000000..d118ffd1
--- /dev/null
+++ b/include/avl.h
@@ -0,0 +1,27 @@
+/* #pragma	lib	"libavl.a" */
+/* #pragma src "/sys/src/libavl" */
+
+AUTOLIB(avl)
+
+typedef struct Avl	Avl;
+typedef struct Avltree	Avltree;
+typedef struct Avlwalk	Avlwalk;
+
+/* #pragma incomplete Avltree */
+/* #pragma incomplete Avlwalk */
+
+struct Avl
+{
+	Avl	*p;		/* parent */
+	Avl	*n[2];		/* children */
+	int	bal;		/* balance bits */
+};
+
+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*));
diff --git a/man/man3/avl.3 b/man/man3/avl.3
new file mode 100644
index 00000000..f87fd97c
--- /dev/null
+++ b/man/man3/avl.3
@@ -0,0 +1,120 @@
+.TH AVL 3
+.SH NAME
+mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL 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
+.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 */
+};
+.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);
+Avltree	*mkavltree(int(*cmp)(Avl*, Avl*));
+.EE
+.SH DESCRIPTION
+An AVL tree is a self-balancing binary search tree.
+These routines allow creation and maintenance of in-memory AVL 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
+.B Avl
+objects and return -1, 0 or 1 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.
+.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
+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 .
+.SH EXAMPLES
+Intended usage seems to be to make an anonymous
+.B Avl
+the first member of the application's tree-node structure,
+then pass these routines tree-node pointers instead of
+.BR Avl* s.
+.IP
+.EX
+typedef struct Node {
+	Avl;
+	uchar	score[VtScoreSize];
+	int	type;
+} Node;
+.sp 0.3v
+Avltree *tree;
+Avl *res;
+Node *np;
+\fI\&...\fP
+	res = lookupavl(tree, np);
+.EE
+.SH SOURCE
+.B \*9/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.
+.SH DIAGNOSTICS
+Functions returning pointers return
+.B nil
+on error.
diff --git a/src/libavl/avl.c b/src/libavl/avl.c
new file mode 100644
index 00000000..2567c98d
--- /dev/null
+++ b/src/libavl/avl.c
@@ -0,0 +1,414 @@
+#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.
+ */
+
+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;
+
+	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)
+{
+	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;
+
+	if((*tp = c) != nil)
+		(*tp)->p = p;
+
+	a->bal = r;
+	c->bal = ((r > 0? r: 0)+1) - l2;
+}
+
+static void
+doublerightleft(Avl **tp, Avl *p)
+{
+	singleright(&(*tp)->n[1], *tp);
+	singleleft(tp, p);
+}
+
+static void
+doubleleftright(Avl **tp, Avl *p)
+{
+	singleleft(&(*tp)->n[0], *tp);
+	singleright(tp, p);
+}
+
+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;
+	}
+}
+
+static int
+_insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
+{
+	int i, ob;
+
+	if(*tp == nil){
+		r->bal = 0;
+		r->n[0] = nil;
+		r->n[1] = nil;
+		r->p = p;
+		*tp = r;
+		return 1;
+	}
+	ob = (*tp)->bal;
+	if((i = 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;
+	}
+
+	/* 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;
+
+	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)
+{
+	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);
+}
+
+static int
+_deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
+	void (*predel)(Avl*, void*), void *arg)
+{
+	int i, ob;
+	Avl *r, *or;
+
+	if(*tp == nil)
+		return 0;
+
+	ob = (*tp)->bal;
+	if((i=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;
+	}
+
+	/* 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);
+}
+
+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);
+}
+
+struct Avltree
+{
+	Avl	*root;
+	int	(*cmp)(Avl*, Avl*);
+	Avlwalk	*walks;
+};
+struct Avlwalk
+{
+	int	started;
+	int	moved;
+	Avlwalk	*next;
+	Avltree	*tree;
+	Avl	*node;
+};
+
+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;
+}
+
+void
+insertavl(Avltree *t, Avl *new, Avl **oldp)
+{
+	*oldp = nil;
+	_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)
+{
+	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;
+	}
+}
+
+static Avl*
+findsuccessor(Avl *a)
+{
+	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;
+	}
+}
+
+static void
+walkdel(Avl *a, void *v)
+{
+	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)
+		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])
+			;
+		w->node = a;
+		w->started = 1;
+	}else{
+		a = findsuccessor(w->node);
+		if(a == w->node)
+			abort();
+		w->node = a;
+	}
+	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);
+}
diff --git a/src/libavl/mkfile b/src/libavl/mkfile
new file mode 100644
index 00000000..1970b186
--- /dev/null
+++ b/src/libavl/mkfile
@@ -0,0 +1,9 @@
+<$PLAN9/src/mkhdr
+
+LIB=libavl.a
+OFILES=\
+	avl.$O\
+
+HFILES=$PLAN9/include/avl.h
+
+<$PLAN9/src/mksyslib