Print this page 
4745 fix AVL code misspellings
Split Close
Expand all
Collapse all
          --- old/usr/src/common/avl/avl.c
          +++ new/usr/src/common/avl/avl.c
↓ open down ↓ 29 lines elided ↑ open up ↑ 
  30   30   *
  31   31   * Here is a very brief overview. An AVL tree is a binary search tree that is
  32   32   * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
  33   33   * any given node, the left and right subtrees are allowed to differ in height
  34   34   * by at most 1 level.
  35   35   *
  36   36   * This relaxation from a perfectly balanced binary tree allows doing
  37   37   * insertion and deletion relatively efficiently. Searching the tree is
  38   38   * still a fast operation, roughly O(log(N)).
  39   39   *
  40      - * The key to insertion and deletion is a set of tree maniuplations called
       40 + * The key to insertion and deletion is a set of tree manipulations called
  41   41   * rotations, which bring unbalanced subtrees back into the semi-balanced state.
  42   42   *
  43   43   * This implementation of AVL trees has the following peculiarities:
  44   44   *
  45   45   *      - The AVL specific data structures are physically embedded as fields
  46   46   *        in the "using" data structures.  To maintain generality the code
  47   47   *        must constantly translate between "avl_node_t *" and containing
  48      - *        data structure "void *"s by adding/subracting the avl_offset.
       48 + *        data structure "void *"s by adding/subtracting the avl_offset.
  49   49   *
  50   50   *      - Since the AVL data is always embedded in other structures, there is
  51   51   *        no locking or memory allocation in the AVL routines. This must be
  52   52   *        provided for by the enclosing data structure's semantics. Typically,
  53   53   *        avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
  54   54   *        exclusive write lock. Other operations require a read lock.
  55   55   *
  56   56   *      - The implementation uses iteration instead of explicit recursion,
  57   57   *        since it is intended to run on limited size kernel stacks. Since
  58   58   *        there is no recursion stack present to move "up" in the tree,
↓ open down ↓ 28 lines elided ↑ open up ↑ 
  87   87   *        than the value of the indicated "avl_node_t *".
  88   88   */
  89   89  
  90   90  #include <sys/types.h>
  91   91  #include <sys/param.h>
  92   92  #include <sys/debug.h>
  93   93  #include <sys/avl.h>
  94   94  #include <sys/cmn_err.h>
  95   95  
  96   96  /*
  97      - * Small arrays to translate between balance (or diff) values and child indeces.
       97 + * Small arrays to translate between balance (or diff) values and child indices.
  98   98   *
  99   99   * Code that deals with binary tree data structures will randomly use
 100  100   * left and right children when examining a tree.  C "if()" statements
 101  101   * which evaluate randomly suffer from very poor hardware branch prediction.
 102  102   * In this code we avoid some of the branch mispredictions by using the
 103  103   * following translation arrays. They replace random branches with an
 104  104   * additional memory reference. Since the translation arrays are both very
 105  105   * small the data should remain efficiently in cache.
 106  106   */
 107  107  static const int  avl_child2balance[2]  = {-1, 1};
 108  108  static const int  avl_balance2child[]   = {0, 0, 1};
 109  109  
 110  110  
 111  111  /*
 112  112   * Walk from one node to the previous valued node (ie. an infix walk
 113  113   * towards the left). At any given node we do one of 2 things:
 114  114   *
 115  115   * - If there is a left child, go to it, then to it's rightmost descendant.
 116  116   *
 117      - * - otherwise we return thru parent nodes until we've come from a right child.
      117 + * - otherwise we return through parent nodes until we've come from a right
      118 + *   child.
 118  119   *
 119  120   * Return Value:
 120  121   * NULL - if at the end of the nodes
 121  122   * otherwise next node
 122  123   */
 123  124  void *
 124  125  avl_walk(avl_tree_t *tree, void *oldnode, int left)
 125  126  {
 126  127          size_t off = tree->avl_offset;
 127  128          avl_node_t *node = AVL_DATA2NODE(oldnode, off);
↓ open down ↓ 784 lines elided ↑ open up ↑ 
 912  913  avl_is_empty(avl_tree_t *tree)
 913  914  {
 914  915          ASSERT(tree);
 915  916          return (tree->avl_numnodes == 0);
 916  917  }
 917  918  
 918  919  #define CHILDBIT        (1L)
 919  920  
 920  921  /*
 921  922   * Post-order tree walk used to visit all tree nodes and destroy the tree
 922      - * in post order. This is used for destroying a tree w/o paying any cost
      923 + * in post order. This is used for destroying a tree without paying any cost
 923  924   * for rebalancing it.
 924  925   *
 925  926   * example:
 926  927   *
 927  928   *      void *cookie = NULL;
 928  929   *      my_data_t *node;
 929  930   *
 930  931   *      while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
 931  932   *              free(node);
 932  933   *      avl_destroy(tree);
↓ open down ↓ 98 lines elided ↑ open up ↑ 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX