1.\" Id: tree.mdoc,v 1.3 2004/03/09 06:30:09 marka Exp 2.\" 3.\" Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 4.\" Copyright (c) 1995-1999 by Internet Software Consortium 5.\" 6.\" Permission to use, copy, modify, and distribute this software for any 7.\" purpose with or without fee is hereby granted, provided that the above 8.\" copyright notice and this permission notice appear in all copies. 9.\" 10.\" THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 11.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 13.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 16.\" OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17.\" 18.Dd April 5, 1994 19.Dt TREE 3 20.Os BSD 4 21.Sh NAME 22.Nm tree_init , 23.Nm tree_mung , 24.Nm tree_srch , 25.Nm tree_add , 26.Nm tree_delete , 27.Nm tree_trav 28.Nd balanced binary tree routines 29.Sh SYNOPSIS 30.Ft void 31.Fn tree_init "void **tree" 32.Ft void * 33.Fn tree_srch "void **tree" "int (*compare)()" "void *data" 34.Ft void 35.Fn tree_add "void **tree" "int (*compare)()" \ 36"void *data" "void (*del_uar)()" 37.Ft int 38.Fn tree_delete "void **tree" "int (*compare)()" \ 39"void *data" "void (*del_uar)()" 40.Ft int 41.Fn tree_trav "void **tree" "int (*trav_uar)()" 42.Ft void 43.Fn tree_mung "void **tree" "void (*del_uar)()" 44.Sh DESCRIPTION 45These functions create and manipulate a balanced binary (AVL) tree. Each node 46of the tree contains the expected left & right subtree pointers, a short int 47balance indicator, and a pointer to the user data. On a 32 bit system, this 48means an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwise 49alignment constrained system with implied padding, 4+4+4+4 bytes per node). 50There is no key data type enforced by this package; a caller supplied 51compare routine is used to compare user data blocks. 52.Pp 53Balanced binary trees are very fast on searches and replacements, but have a 54moderately high cost for additions and deletions. If your application does a 55lot more searches and replacements than it does additions and deletions, the 56balanced (AVL) binary tree is a good choice for a data structure. 57.Pp 58.Fn Tree_init 59creates an empty tree and binds it to 60.Dq Fa tree 61(which for this and all other routines in this package should be declared as 62a pointer to void or int, and passed by reference), which can then be used by 63other routines in this package. Note that more than one 64.Dq Fa tree 65variable can exist at once; thus multiple trees can be manipulated 66simultaneously. 67.Pp 68.Fn Tree_srch 69searches a tree for a specific node and returns either 70.Fa NULL 71if no node was found, or the value of the user data pointer if the node 72was found. 73.Fn compare 74is the address of a function to compare two user data blocks. This routine 75should work much the way 76.Xr strcmp 3 77does; in fact, 78.Xr strcmp 79could be used if the user data was a \s-2NUL\s+2 terminated string. 80.Dq Fa Data 81is the address of a user data block to be used by 82.Fn compare 83as the search criteria. The tree is searched for a node where 84.Fn compare 85returns 0. 86.Pp 87.Fn Tree_add 88inserts or replaces a node in the specified tree. The tree specified by 89.Dq Fa tree 90is searched as in 91.Fn tree_srch , 92and if a node is found to match 93.Dq Fa data , 94then the 95.Fn del_uar 96function, if non\-\s-2NULL\s+2, is called with the address of the user data 97block for the node (this routine should deallocate any dynamic memory which 98is referenced exclusively by the node); the user data pointer for the node 99is then replaced by the value of 100.Dq Fa data . 101If no node is found to match, a new node is added (which may or may not 102cause a transparent rebalance operation), with a user data pointer equal to 103.Dq Fa data . 104A rebalance may or may not occur, depending on where the node is added 105and what the rest of the tree looks like. 106.Fn Tree_add 107will return the 108.Dq Fa data 109pointer unless catastrophe occurs in which case it will return \s-2NULL\s+2. 110.Pp 111.Fn Tree_delete 112deletes a node from 113.Dq Fa tree . 114A rebalance may or may not occur, depending on where the node is removed from 115and what the rest of the tree looks like. 116.Fn Tree_delete 117returns TRUE if a node was deleted, FALSE otherwise. 118.Pp 119.Fn Tree_trav 120traverses all of 121.Dq Fa tree , 122calling 123.Fn trav_uar 124with the address of each user data block. If 125.Fn trav_uar 126returns FALSE at any time, 127.Fn tree_trav 128will immediately return FALSE to its caller. Otherwise all nodes will be 129reached and 130.Fn tree_trav 131will return TRUE. 132.Pp 133.Fn Tree_mung 134deletes every node in 135.Dq Fa tree , 136calling 137.Fn del_uar 138(if it is not \s-2NULL\s+2) with the user data address from each node (see 139.Fn tree_add 140and 141.Fn tree_delete 142above). The tree is left in the same state that 143.Fn tree_init 144leaves it in \- i.e., empty. 145.Sh BUGS 146Should have a way for the caller to specify application-specific 147.Xr malloc 148and 149.Xr free 150functions to be used internally when allocating meta data. 151.Sh AUTHOR 152Paul Vixie, converted and augumented from Modula\-2 examples in 153.Dq Algorithms & Data Structures , 154Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1. 155