Lines Matching +full:in +full:- +full:tree
6 * You may not use this file except in compliance with the License.
9 * or https://opensource.org/licenses/CDDL-1.0.
13 * When distributing Covered Code, include this CDDL HEADER in each
32 * AVL - generic AVL tree implementation for kernel use
34 * A complete description of AVL trees can be found in many CS textbooks.
36 * Here is a very brief overview. An AVL tree is a binary search tree that is
38 * any given node, the left and right subtrees are allowed to differ in height
41 * This relaxation from a perfectly balanced binary tree allows doing
42 * insertion and deletion relatively efficiently. Searching the tree is
45 * The key to insertion and deletion is a set of tree manipulations called
46 * rotations, which bring unbalanced subtrees back into the semi-balanced state.
50 * - The AVL specific data structures are physically embedded as fields
51 * in the "using" data structures. To maintain generality the code
55 * - Since the AVL data is always embedded in other structures, there is
56 * no locking or memory allocation in the AVL routines. This must be
61 * - The implementation uses iteration instead of explicit recursion,
63 * there is no recursion stack present to move "up" in the tree,
64 * there is an explicit "parent" link in the avl_node_t.
66 * - The left/right children pointers of a node are in an array.
67 * In the code, variables (instead of constants) are used to represent
76 * int left_heavy; // -1 when left subtree is taller at some node,
80 * int right_heavy;// will be the opposite of left_heavy (-1 or 1)
85 * allows using half as much code (and hence cache footprint) for tree
88 * - The avl_index_t is an opaque "cookie" used to find nodes at or
89 * adjacent to where a new value would be inserted in the tree. The value
94 * Note - in addition to userland (e.g. libavl and libutil) and the kernel
119 * - If there is a left child, go to it, then to it's rightmost descendant.
121 * - otherwise we return through parent nodes until we've come from a right
125 * NULL - if at the end of the nodes
129 avl_walk(avl_tree_t *tree, void *oldnode, int left) in avl_walk() argument
131 size_t off = tree->avl_offset; in avl_walk()
133 int right = 1 - left; in avl_walk()
138 * nowhere to walk to if tree is empty in avl_walk()
149 if (node->avl_child[left] != NULL) { in avl_walk()
150 for (node = node->avl_child[left]; in avl_walk()
151 node->avl_child[right] != NULL; in avl_walk()
152 node = node->avl_child[right]) in avl_walk()
172 * Return the lowest valued node in a tree or NULL.
173 * (leftmost child from root of tree)
176 avl_first(avl_tree_t *tree) in avl_first() argument
180 size_t off = tree->avl_offset; in avl_first()
182 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) in avl_first()
191 * Return the highest valued node in a tree or NULL.
192 * (rightmost child from root of tree)
195 avl_last(avl_tree_t *tree) in avl_last() argument
199 size_t off = tree->avl_offset; in avl_last()
201 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) in avl_last()
215 * NULL: no node in the given direction
216 * "void *" of the found tree node
219 avl_nearest(avl_tree_t *tree, avl_index_t where, int direction) in avl_nearest() argument
224 size_t off = tree->avl_offset; in avl_nearest()
227 ASSERT(tree->avl_root == NULL); in avl_nearest()
234 return (avl_walk(tree, data, direction)); in avl_nearest()
240 * simple binary tree search.
243 * NULL: the value is not in the AVL tree
245 * "void *" of the found tree node
248 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where) in avl_find() argument
254 size_t off = tree->avl_offset; in avl_find()
256 for (node = tree->avl_root; node != NULL; in avl_find()
257 node = node->avl_child[child]) { in avl_find()
261 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); in avl_find()
262 ASSERT(-1 <= diff && diff <= 1); in avl_find()
286 * !0 : subtree was reduced in height
292 * -2 or +2.
295 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) in avl_rotation() argument
297 int left = !(balance < 0); /* when balance = -2, left will be 0 */ in avl_rotation()
298 int right = 1 - left; in avl_rotation()
300 int right_heavy = -left_heavy; in avl_rotation()
302 avl_node_t *child = node->avl_child[left]; in avl_rotation()
314 * (node bal:-2) in avl_rotation()
317 * (child bal:0 or -1) in avl_rotation()
327 * (node bal:-1 or 0) in avl_rotation()
341 * the height of this sub-tree -- used in "return...;" below in avl_rotation()
348 cright = child->avl_child[right]; in avl_rotation()
349 node->avl_child[left] = cright; in avl_rotation()
358 child->avl_child[right] = node; in avl_rotation()
359 AVL_SETBALANCE(node, -child_bal); in avl_rotation()
370 parent->avl_child[which_child] = child; in avl_rotation()
372 tree->avl_root = child; in avl_rotation()
381 * (node b:-2) in avl_rotation()
408 gchild = child->avl_child[right]; in avl_rotation()
409 gleft = gchild->avl_child[left]; in avl_rotation()
410 gright = gchild->avl_child[right]; in avl_rotation()
417 node->avl_child[left] = gright; in avl_rotation()
423 child->avl_child[right] = gleft; in avl_rotation()
437 gchild->avl_child[left] = child; in avl_rotation()
442 gchild->avl_child[right] = node; in avl_rotation()
451 parent->avl_child[which_child] = gchild; in avl_rotation()
453 tree->avl_root = gchild; in avl_rotation()
455 return (1); /* the new tree is always shorter */ in avl_rotation()
460 * Insert a new node into an AVL tree at the specified (from avl_find()) place.
462 * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
466 * After the node is inserted, a single rotation further up the tree may
470 avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) in avl_insert() argument
477 size_t off = tree->avl_offset; in avl_insert()
486 * First, add the node to the tree at the indicated position. in avl_insert()
488 ++tree->avl_numnodes; in avl_insert()
490 node->avl_child[0] = NULL; in avl_insert()
491 node->avl_child[1] = NULL; in avl_insert()
497 ASSERT(parent->avl_child[which_child] == NULL); in avl_insert()
498 parent->avl_child[which_child] = node; in avl_insert()
500 ASSERT(tree->avl_root == NULL); in avl_insert()
501 tree->avl_root = node; in avl_insert()
504 * Now, back up the tree modifying the balance of all nodes above the in avl_insert()
506 * need to do a rotation. If we back out of the tree we are done. in avl_insert()
518 new_balance = old_balance + (which_child ? 1 : -1); in avl_insert()
530 * from -1 to -2 balance, do a rotation. in avl_insert()
541 * perform a rotation to fix the tree and return in avl_insert()
543 (void) avl_rotation(tree, node, new_balance); in avl_insert()
547 * Insert "new_data" in "tree" in the given "direction" either after or
550 * Insertions can only be done at empty leaf points in the tree, therefore
553 * every other node in the tree is a leaf, this always works.
556 * is correctly ordered at every step of the way in DEBUG kernels.
560 avl_tree_t *tree, in avl_insert_here() argument
571 ASSERT(tree != NULL); in avl_insert_here()
580 node = AVL_DATA2NODE(here, tree->avl_offset); in avl_insert_here()
583 diff = tree->avl_compar(new_data, here); in avl_insert_here()
584 ASSERT(-1 <= diff && diff <= 1); in avl_insert_here()
589 if (node->avl_child[child] != NULL) { in avl_insert_here()
590 node = node->avl_child[child]; in avl_insert_here()
591 child = 1 - child; in avl_insert_here()
592 while (node->avl_child[child] != NULL) { in avl_insert_here()
594 diff = tree->avl_compar(new_data, in avl_insert_here()
595 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
596 ASSERT(-1 <= diff && diff <= 1); in avl_insert_here()
600 node = node->avl_child[child]; in avl_insert_here()
603 diff = tree->avl_compar(new_data, in avl_insert_here()
604 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
605 ASSERT(-1 <= diff && diff <= 1); in avl_insert_here()
610 ASSERT(node->avl_child[child] == NULL); in avl_insert_here()
612 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); in avl_insert_here()
616 * Add a new node to an AVL tree. Strictly enforce that no duplicates can
617 * be added to the tree with a VERIFY which is enabled for non-DEBUG builds.
620 avl_add(avl_tree_t *tree, void *new_node) in avl_add() argument
624 VERIFY(avl_find(tree, new_node, &where) == NULL); in avl_add()
626 avl_insert(tree, new_node, where); in avl_add()
630 * Delete a node from the AVL tree. Deletion is similar to insertion, but
642 * node, say (c), to take the interior node's place. In the code this is
643 * handled by temporarily swapping (d) and (c) in the tree and then using
646 * Secondly, an interior deletion from a deep tree may require more than one
647 * rotation to fix the balance. This is handled by moving up the tree through
653 avl_remove(avl_tree_t *tree, void *data) in avl_remove() argument
664 size_t off = tree->avl_offset; in avl_remove()
674 * As an optimization, we choose the greater neighbor if the tree in avl_remove()
678 if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { in avl_remove()
685 right = 1 - left; in avl_remove()
691 for (node = delete->avl_child[left]; in avl_remove()
692 node->avl_child[right] != NULL; in avl_remove()
693 node = node->avl_child[right]) in avl_remove()
698 * move 'node' to delete's spot in the tree in avl_remove()
703 if (node->avl_child[left] == node) in avl_remove()
704 node->avl_child[left] = &tmp; in avl_remove()
708 parent->avl_child[AVL_XCHILD(node)] = node; in avl_remove()
710 tree->avl_root = node; in avl_remove()
711 AVL_SETPARENT(node->avl_child[left], node); in avl_remove()
712 AVL_SETPARENT(node->avl_child[right], node); in avl_remove()
720 parent->avl_child[AVL_XCHILD(delete)] = delete; in avl_remove()
721 which_child = (delete->avl_child[1] != 0); in avl_remove()
722 if (delete->avl_child[which_child] != NULL) in avl_remove()
723 AVL_SETPARENT(delete->avl_child[which_child], delete); in avl_remove()
729 * be easily removed from the tree. in avl_remove()
731 ASSERT(tree->avl_numnodes > 0); in avl_remove()
732 --tree->avl_numnodes; in avl_remove()
735 if (delete->avl_child[0] != NULL) in avl_remove()
736 node = delete->avl_child[0]; in avl_remove()
738 node = delete->avl_child[1]; in avl_remove()
748 tree->avl_root = node; in avl_remove()
751 parent->avl_child[which_child] = node; in avl_remove()
761 * Move up the tree and adjust the balance in avl_remove()
768 new_balance = old_balance - (which_child ? 1 : -1); in avl_remove()
773 * If a node was in perfect balance but isn't anymore then in avl_remove()
787 * of the sub-tree we have finished adjusting. in avl_remove()
791 else if (!avl_rotation(tree, node, new_balance)) in avl_remove()
796 #define AVL_REINSERT(tree, obj) \ argument
797 avl_remove((tree), (obj)); \
798 avl_add((tree), (obj))
806 (t->avl_compar(obj, neighbor) <= 0)); in avl_update_lt()
809 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { in avl_update_lt()
823 (t->avl_compar(obj, neighbor) >= 0)); in avl_update_gt()
826 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { in avl_update_gt()
840 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { in avl_update()
846 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { in avl_update()
860 ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar); in avl_swap()
861 ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset); in avl_swap()
863 temp_node = tree1->avl_root; in avl_swap()
864 temp_numnodes = tree1->avl_numnodes; in avl_swap()
865 tree1->avl_root = tree2->avl_root; in avl_swap()
866 tree1->avl_numnodes = tree2->avl_numnodes; in avl_swap()
867 tree2->avl_root = temp_node; in avl_swap()
868 tree2->avl_numnodes = temp_numnodes; in avl_swap()
872 * initialize a new AVL tree
875 avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), in avl_create() argument
878 ASSERT(tree); in avl_create()
886 tree->avl_compar = compar; in avl_create()
887 tree->avl_root = NULL; in avl_create()
888 tree->avl_numnodes = 0; in avl_create()
889 tree->avl_offset = offset; in avl_create()
893 * Delete a tree.
896 avl_destroy(avl_tree_t *tree) in avl_destroy() argument
898 ASSERT(tree); in avl_destroy()
899 ASSERT(tree->avl_numnodes == 0); in avl_destroy()
900 ASSERT(tree->avl_root == NULL); in avl_destroy()
905 * Return the number of nodes in an AVL tree.
908 avl_numnodes(avl_tree_t *tree) in avl_numnodes() argument
910 ASSERT(tree); in avl_numnodes()
911 return (tree->avl_numnodes); in avl_numnodes()
915 avl_is_empty(avl_tree_t *tree) in avl_is_empty() argument
917 ASSERT(tree); in avl_is_empty()
918 return (tree->avl_numnodes == 0); in avl_is_empty()
924 * Post-order tree walk used to visit all tree nodes and destroy the tree
925 * in post order. This is used for removing all the nodes from a tree without
933 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
935 * avl_destroy(tree);
940 * On input, a cookie value of CHILDBIT indicates the tree is done.
943 avl_destroy_nodes(avl_tree_t *tree, void **cookie) in avl_destroy_nodes() argument
949 size_t off = tree->avl_offset; in avl_destroy_nodes()
955 first = avl_first(tree); in avl_destroy_nodes()
958 * deal with an empty tree in avl_destroy_nodes()
975 if (tree->avl_root != NULL) { in avl_destroy_nodes()
976 ASSERT(tree->avl_numnodes == 1); in avl_destroy_nodes()
977 tree->avl_root = NULL; in avl_destroy_nodes()
978 tree->avl_numnodes = 0; in avl_destroy_nodes()
984 * Remove the child pointer we just visited from the parent and tree. in avl_destroy_nodes()
987 parent->avl_child[child] = NULL; in avl_destroy_nodes()
988 ASSERT(tree->avl_numnodes > 1); in avl_destroy_nodes()
989 --tree->avl_numnodes; in avl_destroy_nodes()
994 if (child == 1 || parent->avl_child[1] == NULL) { in avl_destroy_nodes()
1003 node = parent->avl_child[1]; in avl_destroy_nodes()
1004 while (node->avl_child[0] != NULL) { in avl_destroy_nodes()
1006 node = node->avl_child[0]; in avl_destroy_nodes()
1014 if (node->avl_child[1] != NULL) { in avl_destroy_nodes()
1017 node = node->avl_child[1]; in avl_destroy_nodes()
1018 ASSERT(node->avl_child[0] == NULL && in avl_destroy_nodes()
1019 node->avl_child[1] == NULL); in avl_destroy_nodes()
1027 ASSERT(node == tree->avl_root); in avl_destroy_nodes()