Print this page
4745 fix AVL code misspellings


  20  */
  21 /*
  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 /*
  27  * AVL - generic AVL tree implementation for kernel use
  28  *
  29  * A complete description of AVL trees can be found in many CS textbooks.
  30  *
  31  * Here is a very brief overview. An AVL tree is a binary search tree that is
  32  * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
  33  * any given node, the left and right subtrees are allowed to differ in height
  34  * by at most 1 level.
  35  *
  36  * This relaxation from a perfectly balanced binary tree allows doing
  37  * insertion and deletion relatively efficiently. Searching the tree is
  38  * still a fast operation, roughly O(log(N)).
  39  *
  40  * The key to insertion and deletion is a set of tree maniuplations called
  41  * rotations, which bring unbalanced subtrees back into the semi-balanced state.
  42  *
  43  * This implementation of AVL trees has the following peculiarities:
  44  *
  45  *      - The AVL specific data structures are physically embedded as fields
  46  *        in the "using" data structures.  To maintain generality the code
  47  *        must constantly translate between "avl_node_t *" and containing
  48  *        data structure "void *"s by adding/subracting the avl_offset.
  49  *
  50  *      - Since the AVL data is always embedded in other structures, there is
  51  *        no locking or memory allocation in the AVL routines. This must be
  52  *        provided for by the enclosing data structure's semantics. Typically,
  53  *        avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
  54  *        exclusive write lock. Other operations require a read lock.
  55  *
  56  *      - The implementation uses iteration instead of explicit recursion,
  57  *        since it is intended to run on limited size kernel stacks. Since
  58  *        there is no recursion stack present to move "up" in the tree,
  59  *        there is an explicit "parent" link in the avl_node_t.
  60  *
  61  *      - The left/right children pointers of a node are in an array.
  62  *        In the code, variables (instead of constants) are used to represent
  63  *        left and right indices.  The implementation is written as if it only
  64  *        dealt with left handed manipulations.  By changing the value assigned
  65  *        to "left", the code also works for right handed trees.  The
  66  *        following variables/terms are frequently used:
  67  *
  68  *              int left;       // 0 when dealing with left children,


  77  *              int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
  78  *
  79  *        Though it is a little more confusing to read the code, the approach
  80  *        allows using half as much code (and hence cache footprint) for tree
  81  *        manipulations and eliminates many conditional branches.
  82  *
  83  *      - The avl_index_t is an opaque "cookie" used to find nodes at or
  84  *        adjacent to where a new value would be inserted in the tree. The value
  85  *        is a modified "avl_node_t *".  The bottom bit (normally 0 for a
  86  *        pointer) is set to indicate if that the new node has a value greater
  87  *        than the value of the indicated "avl_node_t *".
  88  */
  89 
  90 #include <sys/types.h>
  91 #include <sys/param.h>
  92 #include <sys/debug.h>
  93 #include <sys/avl.h>
  94 #include <sys/cmn_err.h>
  95 
  96 /*
  97  * Small arrays to translate between balance (or diff) values and child indeces.
  98  *
  99  * Code that deals with binary tree data structures will randomly use
 100  * left and right children when examining a tree.  C "if()" statements
 101  * which evaluate randomly suffer from very poor hardware branch prediction.
 102  * In this code we avoid some of the branch mispredictions by using the
 103  * following translation arrays. They replace random branches with an
 104  * additional memory reference. Since the translation arrays are both very
 105  * small the data should remain efficiently in cache.
 106  */
 107 static const int  avl_child2balance[2]  = {-1, 1};
 108 static const int  avl_balance2child[]   = {0, 0, 1};
 109 
 110 
 111 /*
 112  * Walk from one node to the previous valued node (ie. an infix walk
 113  * towards the left). At any given node we do one of 2 things:
 114  *
 115  * - If there is a left child, go to it, then to it's rightmost descendant.
 116  *
 117  * - otherwise we return thru parent nodes until we've come from a right child.

 118  *
 119  * Return Value:
 120  * NULL - if at the end of the nodes
 121  * otherwise next node
 122  */
 123 void *
 124 avl_walk(avl_tree_t *tree, void *oldnode, int left)
 125 {
 126         size_t off = tree->avl_offset;
 127         avl_node_t *node = AVL_DATA2NODE(oldnode, off);
 128         int right = 1 - left;
 129         int was_child;
 130 
 131 
 132         /*
 133          * nowhere to walk to if tree is empty
 134          */
 135         if (node == NULL)
 136                 return (NULL);
 137 


 902  * Return the number of nodes in an AVL tree.
 903  */
 904 ulong_t
 905 avl_numnodes(avl_tree_t *tree)
 906 {
 907         ASSERT(tree);
 908         return (tree->avl_numnodes);
 909 }
 910 
 911 boolean_t
 912 avl_is_empty(avl_tree_t *tree)
 913 {
 914         ASSERT(tree);
 915         return (tree->avl_numnodes == 0);
 916 }
 917 
 918 #define CHILDBIT        (1L)
 919 
 920 /*
 921  * 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  * for rebalancing it.
 924  *
 925  * example:
 926  *
 927  *      void *cookie = NULL;
 928  *      my_data_t *node;
 929  *
 930  *      while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
 931  *              free(node);
 932  *      avl_destroy(tree);
 933  *
 934  * The cookie is really an avl_node_t to the current node's parent and
 935  * an indication of which child you looked at last.
 936  *
 937  * On input, a cookie value of CHILDBIT indicates the tree is done.
 938  */
 939 void *
 940 avl_destroy_nodes(avl_tree_t *tree, void **cookie)
 941 {
 942         avl_node_t      *node;




  20  */
  21 /*
  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 /*
  27  * AVL - generic AVL tree implementation for kernel use
  28  *
  29  * A complete description of AVL trees can be found in many CS textbooks.
  30  *
  31  * Here is a very brief overview. An AVL tree is a binary search tree that is
  32  * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
  33  * any given node, the left and right subtrees are allowed to differ in height
  34  * by at most 1 level.
  35  *
  36  * This relaxation from a perfectly balanced binary tree allows doing
  37  * insertion and deletion relatively efficiently. Searching the tree is
  38  * still a fast operation, roughly O(log(N)).
  39  *
  40  * The key to insertion and deletion is a set of tree manipulations called
  41  * rotations, which bring unbalanced subtrees back into the semi-balanced state.
  42  *
  43  * This implementation of AVL trees has the following peculiarities:
  44  *
  45  *      - The AVL specific data structures are physically embedded as fields
  46  *        in the "using" data structures.  To maintain generality the code
  47  *        must constantly translate between "avl_node_t *" and containing
  48  *        data structure "void *"s by adding/subtracting the avl_offset.
  49  *
  50  *      - Since the AVL data is always embedded in other structures, there is
  51  *        no locking or memory allocation in the AVL routines. This must be
  52  *        provided for by the enclosing data structure's semantics. Typically,
  53  *        avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
  54  *        exclusive write lock. Other operations require a read lock.
  55  *
  56  *      - The implementation uses iteration instead of explicit recursion,
  57  *        since it is intended to run on limited size kernel stacks. Since
  58  *        there is no recursion stack present to move "up" in the tree,
  59  *        there is an explicit "parent" link in the avl_node_t.
  60  *
  61  *      - The left/right children pointers of a node are in an array.
  62  *        In the code, variables (instead of constants) are used to represent
  63  *        left and right indices.  The implementation is written as if it only
  64  *        dealt with left handed manipulations.  By changing the value assigned
  65  *        to "left", the code also works for right handed trees.  The
  66  *        following variables/terms are frequently used:
  67  *
  68  *              int left;       // 0 when dealing with left children,


  77  *              int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
  78  *
  79  *        Though it is a little more confusing to read the code, the approach
  80  *        allows using half as much code (and hence cache footprint) for tree
  81  *        manipulations and eliminates many conditional branches.
  82  *
  83  *      - The avl_index_t is an opaque "cookie" used to find nodes at or
  84  *        adjacent to where a new value would be inserted in the tree. The value
  85  *        is a modified "avl_node_t *".  The bottom bit (normally 0 for a
  86  *        pointer) is set to indicate if that the new node has a value greater
  87  *        than the value of the indicated "avl_node_t *".
  88  */
  89 
  90 #include <sys/types.h>
  91 #include <sys/param.h>
  92 #include <sys/debug.h>
  93 #include <sys/avl.h>
  94 #include <sys/cmn_err.h>
  95 
  96 /*
  97  * Small arrays to translate between balance (or diff) values and child indices.
  98  *
  99  * Code that deals with binary tree data structures will randomly use
 100  * left and right children when examining a tree.  C "if()" statements
 101  * which evaluate randomly suffer from very poor hardware branch prediction.
 102  * In this code we avoid some of the branch mispredictions by using the
 103  * following translation arrays. They replace random branches with an
 104  * additional memory reference. Since the translation arrays are both very
 105  * small the data should remain efficiently in cache.
 106  */
 107 static const int  avl_child2balance[2]  = {-1, 1};
 108 static const int  avl_balance2child[]   = {0, 0, 1};
 109 
 110 
 111 /*
 112  * Walk from one node to the previous valued node (ie. an infix walk
 113  * towards the left). At any given node we do one of 2 things:
 114  *
 115  * - If there is a left child, go to it, then to it's rightmost descendant.
 116  *
 117  * - otherwise we return through parent nodes until we've come from a right
 118  *   child.
 119  *
 120  * Return Value:
 121  * NULL - if at the end of the nodes
 122  * otherwise next node
 123  */
 124 void *
 125 avl_walk(avl_tree_t *tree, void *oldnode, int left)
 126 {
 127         size_t off = tree->avl_offset;
 128         avl_node_t *node = AVL_DATA2NODE(oldnode, off);
 129         int right = 1 - left;
 130         int was_child;
 131 
 132 
 133         /*
 134          * nowhere to walk to if tree is empty
 135          */
 136         if (node == NULL)
 137                 return (NULL);
 138 


 903  * Return the number of nodes in an AVL tree.
 904  */
 905 ulong_t
 906 avl_numnodes(avl_tree_t *tree)
 907 {
 908         ASSERT(tree);
 909         return (tree->avl_numnodes);
 910 }
 911 
 912 boolean_t
 913 avl_is_empty(avl_tree_t *tree)
 914 {
 915         ASSERT(tree);
 916         return (tree->avl_numnodes == 0);
 917 }
 918 
 919 #define CHILDBIT        (1L)
 920 
 921 /*
 922  * Post-order tree walk used to visit all tree nodes and destroy the tree
 923  * in post order. This is used for destroying a tree without paying any cost
 924  * for rebalancing it.
 925  *
 926  * example:
 927  *
 928  *      void *cookie = NULL;
 929  *      my_data_t *node;
 930  *
 931  *      while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
 932  *              free(node);
 933  *      avl_destroy(tree);
 934  *
 935  * The cookie is really an avl_node_t to the current node's parent and
 936  * an indication of which child you looked at last.
 937  *
 938  * On input, a cookie value of CHILDBIT indicates the tree is done.
 939  */
 940 void *
 941 avl_destroy_nodes(avl_tree_t *tree, void **cookie)
 942 {
 943         avl_node_t      *node;