.\" $Id: tree.mdoc,v 1.1.2.1.10.1 2004/03/09 08:33:44 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 DESCRIPTIONThese functions create and manipulate a balanced binary (AVL) tree.  Each nodeof the tree contains the expected left & right subtree pointers, a short intbalance indicator, and a pointer to the user data.  On a 32 bit system, thismeans an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwisealignment constrained system with implied padding, 4+4+4+4 bytes per node).There is no key data type enforced by this package; a caller suppliedcompare routine is used to compare user data blocks..PpBalanced binary trees are very fast on searches and replacements, but have amoderately high cost for additions and deletions.  If your application does alot more searches and replacements than it does additions and deletions, thebalanced (AVL) binary tree is a good choice for a data structure..Pp.Fn Tree_initcreates an empty tree and binds it to.Dq Fa tree(which for this and all other routines in this package should be declared asa pointer to void or int, and passed by reference), which can then be used byother routines in this package.  Note that more than one.Dq Fa treevariable can exist at once; thus multiple trees can be manipulatedsimultaneously..Pp.Fn Tree_srchsearches a tree for a specific node and returns either.Fa NULLif no node was found, or the value of the user data pointer if the nodewas found..Fn compareis the address of a function to compare two user data blocks.  This routineshould work much the way .Xr strcmp 3does; in fact,.Xr strcmpcould be used if the user data was a \s-2NUL\s+2 terminated string..Dq Fa Datais the address of a user data block to be used by.Fn compareas the search criteria.  The tree is searched for a node where.Fn comparereturns 0..Pp.Fn Tree_addinserts or replaces a node in the specified tree.  The tree specified by.Dq Fa treeis searched as in.Fn tree_srch ,and if a node is found to match.Dq Fa data ,then the.Fn del_uarfunction, if non\-\s-2NULL\s+2, is called with the address of the user datablock for the node (this routine should deallocate any dynamic memory whichis referenced exclusively by the node); the user data pointer for the nodeis 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 notcause 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 addedand what the rest of the tree looks like..Fn Tree_addwill return the.Dq Fa datapointer unless catastrophe occurs in which case it will return \s-2NULL\s+2..Pp.Fn Tree_deletedeletes a node from.Dq Fa tree .A rebalance may or may not occur, depending on where the node is removed fromand what the rest of the tree looks like..Fn Tree_deletereturns TRUE if a node was deleted, FALSE otherwise..Pp.Fn Tree_travtraverses all of.Dq Fa tree ,calling.Fn trav_uarwith the address of each user data block.  If.Fn trav_uarreturns FALSE at any time,.Fn tree_travwill immediately return FALSE to its caller.  Otherwise all nodes will be reached and.Fn tree_travwill return TRUE..Pp.Fn Tree_mungdeletes 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_addand.Fn tree_deleteabove).  The tree is left in the same state that.Fn tree_initleaves it in \- i.e., empty..Sh BUGSShould have a way for the caller to specify application-specific.Xr mallocand.Xr freefunctions to be used internally when allocating meta data..Sh AUTHORPaul Vixie, converted and augumented from Modula\-2 examples in.Dq Algorithms & Data Structures ,Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1.