Flatten bind9 vendor work area

1 files changed, 154 insertions, 0 deletions

diff --git a/lib/bind/isc/tree.mdoc b/lib/bind/isc/tree.mdoc
new file mode 100644
index 0000000..2c24e1f
--- /dev/null
+++ b/lib/bind/isc/tree.mdoc
@@ -0,0 +1,154 @@
+.\" $Id: tree.mdoc,v 1.3 2004/03/09 06:30:09 marka Exp $
+.\"
+.\" Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
+.\" Copyright (c) 1995-1999 by Internet Software Consortium
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
+.\" OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd April 5, 1994
+.Dt TREE 3
+.Os BSD 4
+.Sh NAME
+.Nm tree_init ,
+.Nm tree_mung ,
+.Nm tree_srch ,
+.Nm tree_add ,
+.Nm tree_delete ,
+.Nm tree_trav
+.Nd balanced binary tree routines
+.Sh SYNOPSIS
+.Ft void
+.Fn tree_init "void **tree"
+.Ft void *
+.Fn tree_srch "void **tree" "int (*compare)()" "void *data"
+.Ft void
+.Fn tree_add "void **tree" "int (*compare)()" \
+"void *data" "void (*del_uar)()"
+.Ft int
+.Fn tree_delete "void **tree" "int (*compare)()" \
+"void *data" "void (*del_uar)()"
+.Ft int
+.Fn tree_trav "void **tree" "int (*trav_uar)()"
+.Ft void
+.Fn tree_mung "void **tree" "void (*del_uar)()"
+.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
+.Fn Tree_init
+creates an empty tree and binds it to
+.Dq Fa 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
+.Dq Fa tree
+variable can exist at once; thus multiple trees can be manipulated
+simultaneously.
+.Pp
+.Fn Tree_srch
+searches a tree for a specific node and returns either
+.Fa NULL
+if no node was found, or the value of the user data pointer if the node
+was found.
+.Fn compare
+is the address of a function to compare two user data blocks.  This routine
+should work much the way 
+.Xr strcmp 3
+does; in fact,
+.Xr strcmp
+could be used if the user data was a \s-2NUL\s+2 terminated string.
+.Dq Fa Data
+is the address of a user data block to be used by
+.Fn compare
+as the search criteria.  The tree is searched for a node where
+.Fn compare
+returns 0.
+.Pp
+.Fn Tree_add
+inserts or replaces a node in the specified tree.  The tree specified by
+.Dq Fa tree
+is searched as in
+.Fn tree_srch ,
+and if a node is found to match
+.Dq Fa data ,
+then the
+.Fn 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
+.Dq Fa 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
+.Dq Fa data .
+A rebalance may or may not occur, depending on where the node is added
+and what the rest of the tree looks like.
+.Fn Tree_add
+will return the
+.Dq Fa data
+pointer unless catastrophe occurs in which case it will return \s-2NULL\s+2.
+.Pp
+.Fn Tree_delete
+deletes a node from
+.Dq Fa 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.
+.Fn Tree_delete
+returns TRUE if a node was deleted, FALSE otherwise.
+.Pp
+.Fn Tree_trav
+traverses all of
+.Dq Fa tree ,
+calling
+.Fn trav_uar
+with the address of each user data block.  If
+.Fn trav_uar
+returns FALSE at any time,
+.Fn tree_trav
+will immediately return FALSE to its caller.  Otherwise all nodes will be 
+reached and
+.Fn tree_trav
+will return TRUE.
+.Pp
+.Fn Tree_mung
+deletes every node in
+.Dq Fa tree ,
+calling
+.Fn del_uar
+(if it is not \s-2NULL\s+2) with the user data address from each node (see
+.Fn tree_add
+and
+.Fn tree_delete
+above).  The tree is left in the same state that
+.Fn tree_init
+leaves it in \- i.e., empty.
+.Sh BUGS
+Should have a way for the caller to specify application-specific
+.Xr malloc
+and
+.Xr free
+functions to be used internally when allocating meta data.
+.Sh AUTHOR
+Paul Vixie, converted and augumented from Modula\-2 examples in
+.Dq Algorithms & Data Structures ,
+Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1.