external/bsd/libbind/dist/isc/tree.mdoc

   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
  45 These functions create and manipulate a balanced binary (AVL) tree.  Each node
  46 of the tree contains the expected left & right subtree pointers, a short int
  47 balance indicator, and a pointer to the user data.  On a 32 bit system, this
  48 means an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwise
  49 alignment constrained system with implied padding, 4+4+4+4 bytes per node).
  50 There is no key data type enforced by this package; a caller supplied
  51 compare routine is used to compare user data blocks.
  52 .Pp
  53 Balanced binary trees are very fast on searches and replacements, but have a
  54 moderately high cost for additions and deletions.  If your application does a
  55 lot more searches and replacements than it does additions and deletions, the
  56 balanced (AVL) binary tree is a good choice for a data structure.
  57 .Pp
  58 .Fn Tree_init
  59 creates 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
  62 a pointer to void or int, and passed by reference), which can then be used by
  63 other routines in this package.  Note that more than one
  64 .Dq Fa tree
  65 variable can exist at once; thus multiple trees can be manipulated
  66 simultaneously.
  67 .Pp
  68 .Fn Tree_srch
  69 searches a tree for a specific node and returns either
  70 .Fa NULL
  71 if no node was found, or the value of the user data pointer if the node
  72 was found.
  73 .Fn compare
  74 is the address of a function to compare two user data blocks.  This routine
  75 should work much the way
  76 .Xr strcmp 3
  77 does; in fact,
  78 .Xr strcmp
  79 could be used if the user data was a \s-2NUL\s+2 terminated string.
  80 .Dq Fa Data
  81 is the address of a user data block to be used by
  82 .Fn compare
  83 as the search criteria.  The tree is searched for a node where
  84 .Fn compare
  85 returns 0.
  86 .Pp
  87 .Fn Tree_add
  88 inserts or replaces a node in the specified tree.  The tree specified by
  89 .Dq Fa tree
  90 is searched as in
  91 .Fn tree_srch ,
  92 and if a node is found to match
  93 .Dq Fa data ,
  94 then the
  95 .Fn del_uar
  96 function, if non\-\s-2NULL\s+2, is called with the address of the user data
  97 block for the node (this routine should deallocate any dynamic memory which
  98 is referenced exclusively by the node); the user data pointer for the node
  99 is then replaced by the value of
 100 .Dq Fa data .
 101 If no node is found to match, a new node is added (which may or may not
 102 cause a transparent rebalance operation), with a user data pointer equal to
 103 .Dq Fa data .
 104 A rebalance may or may not occur, depending on where the node is added
 105 and what the rest of the tree looks like.
 106 .Fn Tree_add
 107 will return the
 108 .Dq Fa data
 109 pointer unless catastrophe occurs in which case it will return \s-2NULL\s+2.
 110 .Pp
 111 .Fn Tree_delete
 112 deletes a node from
 113 .Dq Fa tree .
 114 A rebalance may or may not occur, depending on where the node is removed from
 115 and what the rest of the tree looks like.
 116 .Fn Tree_delete
 117 returns TRUE if a node was deleted, FALSE otherwise.
 118 .Pp
 119 .Fn Tree_trav
 120 traverses all of
 121 .Dq Fa tree ,
 122 calling
 123 .Fn trav_uar
 124 with the address of each user data block.  If
 125 .Fn trav_uar
 126 returns FALSE at any time,
 127 .Fn tree_trav
 128 will immediately return FALSE to its caller.  Otherwise all nodes will be
 129 reached and
 130 .Fn tree_trav
 131 will return TRUE.
 132 .Pp
 133 .Fn Tree_mung
 134 deletes every node in
 135 .Dq Fa tree ,
 136 calling
 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
 140 and
 141 .Fn tree_delete
 142 above).  The tree is left in the same state that
 143 .Fn tree_init
 144 leaves it in \- i.e., empty.
 145 .Sh BUGS
 146 Should have a way for the caller to specify application-specific
 147 .Xr malloc
 148 and
 149 .Xr free
 150 functions to be used internally when allocating meta data.
 151 .Sh AUTHOR
 152 Paul Vixie, converted and augumented from Modula\-2 examples in
 153 .Dq Algorithms & Data Structures ,
 154 Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1.