.\" $Id: tree.mdoc,v 1.1.2.2 2004/03/09 09:17:36 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.