libavl: import from Plan 9

1 files changed, 120 insertions, 0 deletions

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.