1 files changed, 154 insertions, 0 deletions
diff --git a/contrib/bind/named/tree.man3 b/contrib/bind/named/tree.man3
new file mode 100644
index 0000000..5be48783
--- /dev/null
+++ b/contrib/bind/named/tree.man3
@@ -0,0 +1,154 @@
+.TH TREE 3 "5 April 1994"
+.\" from .TH TREE 3 "22 Jan 1993"
+.\" from .TH TREE 2 "23 June 1986"
+.UC 4
+.SH NAME
+tree_init, tree_mung, tree_srch, tree_add, tree_delete, tree_trav
+\- balanced binary tree routines
+.SH SYNOPSIS
+.nf
+.B void
+.B tree_init(tree)
+.B void **tree;
+.PP
+.B void *
+.B tree_srch(tree, compare, data)
+.B void **tree;
+.B int (*compare)();
+.B void *data;
+.PP
+.B void
+.B tree_add(tree, compare, data, del_uar)
+.B void **tree;
+.B int (*compare)();
+.B void *data;
+.B void (*del_uar)();
+.PP
+.B int
+.B tree_delete(tree, compare, data, del_uar)
+.B void **tree;
+.B int (*compare)();
+.B void *data;
+.B void (*del_uar)();
+.PP
+.B int
+.B tree_trav(tree, trav_uar)
+.B void **tree;
+.B int (*trav_uar)();
+.PP
+.B void
+.B tree_mung(tree, del_uar)
+.B void **tree;
+.B void (*del_uar)();
+.fi
+.SH DESCRIPTION
+These functions create and manipulate a balanced binary (AVL) tree.  Each node
+of the tree contains the expected left & right subtree pointers, a short int
+balance indicator, and a pointer to the user data.  On a 32 bit system, this
+means an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwise
+alignment constrained system with implied padding, 4+4+4+4 bytes per node).
+There is no key data type enforced by this package; a caller supplied
+compare routine is used to compare user data blocks.
+.PP
+Balanced binary trees are very fast on searches and replacements, but have a
+moderately high cost for additions and deletions.  If your application does a
+lot more searches and replacements than it does additions and deletions, the
+balanced (AVL) binary tree is a good choice for a data structure.
+.PP
+.I Tree_init
+creates an empty tree and binds it to
+.I tree
+(which for this and all other routines in this package should be declared as
+a pointer to void or int, and passed by reference), which can then be used by
+other routines in this package.  Note that more than one
+.I tree
+variable can exist at once; thus multiple trees can be manipulated
+simultaneously.
+.PP
+.I Tree_srch
+searches a tree for a specific node and returns either
+.I NULL
+if no node was found, or the value of the user data pointer if the node
+was found.
+.I compare
+is the address of a function to compare two user data blocks.  This routine
+should work much the way 
+.IR strcmp (3)
+does; in fact,
+.I strcmp
+could be used if the user data was a \s-2NUL\s+2 terminated string.
+.I data
+is the address of a user data block to be used by
+.I compare
+as the search criteria.  The tree is searched for a node where
+.I compare
+returns 0.
+.PP
+.I Tree_add
+inserts or replaces a node in the specified tree.  The tree specified by
+.I tree
+is searched as in
+.I tree_srch,
+and if a node is found to match
+.I data,
+then the
+.I del_uar
+function, if non\-\s-2NULL\s+2, is called with the address of the user data
+block for the node (this routine should deallocate any dynamic memory which
+is referenced exclusively by the node); the user data pointer for the node
+is then replaced by the value of
+.I data.
+If no node is found to match, a new node is added (which may or may not
+cause a transparent rebalance operation), with a user data pointer equal to
+.I data.
+A rebalance may or may not occur, depending on where the node is added
+and what the rest of the tree looks like.
+.I Tree_add
+will return the
+.I data
+pointer unless catastrophe occurs in which case it will return \s-2NULL\s+2.
+.PP
+.I Tree_delete
+deletes a node from
+.I tree.
+A rebalance may or may not occur, depending on where the node is removed from
+and what the rest of the tree looks like.
+.I Tree_delete
+returns TRUE if a node was deleted, FALSE otherwise.
+.PP
+.I Tree_trav
+traverses all of
+.I tree,
+calling
+.I trav_uar
+with the address of each user data block.  If
+.I trav_uar
+returns FALSE at any time,
+.I tree_trav
+will immediately return FALSE to its caller.  Otherwise all nodes will be 
+reached and
+.I tree_trav
+will return TRUE.
+.PP
+.I Tree_mung
+deletes every node in
+.I tree,
+calling
+.I del_uar
+(if it is not \s-2NULL\s+2) with the user data address from each node (see
+.I tree_add
+and
+.I tree_delete
+above).  The tree is left in the same state that
+.I tree_init
+leaves it in \- i.e., empty.
+.SH BUGS
+Should have a way for the caller to specify application specific
+.I malloc
+and
+.I free
+functions to be used internally when allocating meta data.
+.SH AUTHOR
+Paul Vixie, converted and augumented from Modula\-2 examples in
+.I Algorithms & Data Structures,
+Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1.