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;
|