home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 35 Internet / 35-Internet.zip / radi116c.zip / radius116c / src / radius / tree.doc < prev    next >
Text File  |  1998-12-28  |  5KB  |  117 lines
  1.  $Id: tree.mdoc,v 8.1 1997/01/30 20:27:25 vixie Exp $
  2.  
  3. Copyright (c) 1995, 1996 by Internet Software Consortium
  4.  
  5. Permission to use, copy, modify, and distribute this software for any
  6. purpose with or without fee is hereby granted, provided that the above
  7. copyright notice and this permission notice appear in all copies.
  8.  
  9. THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
  10. ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
  11. OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
  12. CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
  13. DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  14. PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  15. ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  16. SOFTWARE.
  17.  
  18.  April 5, 1994
  19.  TREE 3
  20.  BSD 4
  21.  
  22.  NAME
  23.  tree_init ,
  24.  tree_mung ,
  25.  tree_srch ,
  26.  tree_add ,
  27.  tree_delete ,
  28.  tree_trav
  29.  
  30.  balanced binary tree routines
  31.  
  32.  SYNOPSIS
  33.  void tree_init "void **tree"
  34.  void * tree_srch "void **tree" "int (*compare)()" "void *data"
  35.  void tree_add(tree, compare, data, del_uar) 
  36.      "void **tree" "int (*compare)()" \
  37.      "void *data" "void (*del_uar)()"
  38.  int tree_delete(tree, compare, data, del_uar) 
  39.      "void **tree" "int (*compare)()" \
  40.      "void *data" "void (*del_uar)()"
  41.  int tree_trav(tree, trav_uar) "void **tree" "int (*trav_uar)()"
  42.  void tree_mung(tree, del_uar) "void **tree" "void (*del_uar)()"
  43.  
  44.  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.  
  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.  
  58.  Tree_init creates an empty tree and binds it to tree
  59. (which for this and all other routines in this package should be declared as
  60. a pointer to void or int, and passed by reference), which can then be used by
  61. other routines in this package.  Note that more than one tree
  62. variable can exist at once; thus multiple trees can be manipulated
  63. simultaneously.
  64.  
  65.  Tree_srch searches a tree for a specific node and returns either
  66.  NULL
  67.    if no node was found, or the value of the user data pointer if the node
  68. was found.
  69.   compare
  70. is the address of a function to compare two user data blocks.  This routine
  71. should work much the way strcmp does; in fact, strcmp could be used if 
  72. the user data was a NUL terminated string.
  73.   Data
  74. is the address of a user data block to be used by compare as the 
  75. search criteria.  The tree is searched for a node where compare returns 0.
  76.  
  77.  Tree_add inserts or replaces a node in the specified tree.  The tree 
  78.  specified by tree is searched as in tree_srch, and if a node is found 
  79.  to match data, then the del_uar function, if 
  80.  non NULL, is called with the address of the user data
  81. block for the node (this routine should deallocate any dynamic memory which
  82. is referenced exclusively by the node); the user data pointer for the node
  83. is then replaced by the value of data.
  84. If no node is found to match, a new node is added (which may or may not
  85. cause a transparent rebalance operation), with a user data pointer equal to
  86. data. A rebalance may or may not occur, depending on where the node is added
  87. and what the rest of the tree looks like.
  88.  
  89.  Tree_add will return the data pointer unless catastrophe occurs in 
  90. which case it will return NULL.
  91.  
  92.  Tree_delete deletes a node from tree.  A rebalance may or may not occur,
  93.  depending on where the node is removed from and what the rest of the 
  94.  tree looks like.
  95.  
  96.  tree_delete returns TRUE if a node was deleted, FALSE otherwise.
  97.  
  98. Tree_trav traverses all of tree, calling trav_uar with the address 
  99. of each user data block.  If trav_uar returns FALSE at any time,
  100. tree_trav will immediately return FALSE to its caller.  Otherwise 
  101. all nodes will be reached and tree_trav will return TRUE.
  102.  
  103. Tree_mung deletes every node in tree, calling del_uar (if it is 
  104. not NULL) with the user data address from each node (see tree_add and
  105. tree_delete above).  The tree is left in the same state that
  106. tree_init leaves it in - i.e., empty.
  107.  
  108. BUGS
  109. Should have a way for the caller to specify application-specific
  110. malloc and free functions to be used internally when allocating 
  111. meta data.
  112.  
  113. AUTHOR
  114. Paul Vixie, converted and augumented from Modula\-2 examples in
  115. Algorithms & Data Structures , Niklaus Wirth, 
  116. Prentice-Hall, ISBN 0-13-022005-1.
  117.