common/avl/avl.c

31  * AVL - generic AVL tree implementation for kernel use
35  * Here is a very brief overview. An AVL tree is a binary search tree that is
40  * This relaxation from a perfectly balanced binary tree allows doing
41  * insertion and deletion relatively efficiently. Searching the tree is
44  * The key to insertion and deletion is a set of tree manipulations called
62  *	  there is no recursion stack present to move "up" in the tree,
84  *	  allows using half as much code (and hence cache footprint) for tree
88  *	  adjacent to where a new value would be inserted in the tree. The value
109  * Code that deals with binary tree data structures will randomly use
110  * left and right children when examining a tree.  C "if()" statements
135 avl_walk(avl_tree_t *tree, void	*oldnode, int left)
137 	size_t off = tree->avl_offset;
144 	 * nowhere to walk to if tree is empty
178  * Return the lowest valued node in a tree or NULL.
179  * (leftmost child from root of tree)
182 avl_first(avl_tree_t *tree)
186 	size_t off = tree->avl_offset;
188 	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
197  * Return the highest valued node in a tree or NULL.
198  * (rightmost child from root of tree)
201 avl_last(avl_tree_t *tree)
205 	size_t off = tree->avl_offset;
207 	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
222  *	"void *"  of the found tree node
225 avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
230 	size_t off = tree->avl_offset;
233 		ASSERT(tree->avl_root == NULL);
240 	return (avl_walk(tree, data, direction));
246  * simple binary tree search.
249  *	NULL: the value is not in the AVL tree
251  *	"void *"  of the found tree node
254 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where)
260 	size_t off = tree->avl_offset;
262 	for (node = tree->avl_root; node != NULL;
267 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
302 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
350 		 * the height of this sub-tree -- used in "return...;" below
381 			tree->avl_root = child;
464 		tree->avl_root = gchild;
466 	return (1);	/* the new tree is always shorter */
471  * Insert a new node into an AVL tree at the specified (from avl_find()) place.
473  * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
477  * After the node is inserted, a single rotation further up the tree may
481 avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
488 	size_t off = tree->avl_offset;
490 	ASSERT(tree);
498 	 * First, add the node to the tree at the indicated position.
500 	++tree->avl_numnodes;
512 		ASSERT(tree->avl_root == NULL);
513 		tree->avl_root = node;
516 	 * Now, back up the tree modifying the balance of all nodes above the
518 	 * need to do a rotation.  If we back out of the tree we are done.
553 	 * perform a rotation to fix the tree and return
555 	(void) avl_rotation(tree, node, new_balance);
559  * Insert "new_data" in "tree" in the given "direction" either after or
562  * Insertions can only be done at empty leaf points in the tree, therefore
565  * every other node in the tree is a leaf, this always works.
572 	avl_tree_t *tree,
583 	ASSERT(tree != NULL);
592 	node = AVL_DATA2NODE(here, tree->avl_offset);
595 	diff = tree->avl_compar(new_data, here);
606 			diff = tree->avl_compar(new_data,
607 			    AVL_NODE2DATA(node, tree->avl_offset));
615 		diff = tree->avl_compar(new_data,
616 		    AVL_NODE2DATA(node, tree->avl_offset));
624 	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
628  * Add a new node to an AVL tree.
631 avl_add(avl_tree_t *tree, void *new_node)
641 	if (avl_find(tree, new_node, &where) != NULL)
647 	avl_insert(tree, new_node, where);
651  * Delete a node from the AVL tree.  Deletion is similar to insertion, but
664  * handled by temporarily swapping (d) and (c) in the tree and then using
667  * Secondly, an interior deletion from a deep tree may require more than one
668  * rotation to fix the balance. This is handled by moving up the tree through
674 avl_remove(avl_tree_t *tree, void *data)
685 	size_t off = tree->avl_offset;
687 	ASSERT(tree);
697 	 * As an optimization, we choose the greater neighbor if the tree
721 		 * move 'node' to delete's spot in the tree
733 			tree->avl_root = node;
752 	 * be easily removed from the tree.
754 	ASSERT(tree->avl_numnodes > 0);
755 	--tree->avl_numnodes;
771 		tree->avl_root = node;
784 		 * Move up the tree and adjust the balance
810 		 * of the sub-tree we have finished adjusting.
814 		else if (!avl_rotation(tree, node, new_balance))
819 #define	AVL_REINSERT(tree, obj)		\
820 	avl_remove((tree), (obj));	\
821 	avl_add((tree), (obj))
896  * initialize a new AVL tree
899 avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
902 	ASSERT(tree);
910 	tree->avl_compar = compar;
911 	tree->avl_root = NULL;
912 	tree->avl_numnodes = 0;
913 	tree->avl_size = size;
914 	tree->avl_offset = offset;
918  * Delete a tree.
922 avl_destroy(avl_tree_t *tree)
924 	ASSERT(tree);
925 	ASSERT(tree->avl_numnodes == 0);
926 	ASSERT(tree->avl_root == NULL);
931  * Return the number of nodes in an AVL tree.
934 avl_numnodes(avl_tree_t *tree)
936 	ASSERT(tree);
937 	return (tree->avl_numnodes);
941 avl_is_empty(avl_tree_t *tree)
943 	ASSERT(tree);
944 	return (tree->avl_numnodes == 0);
950  * Post-order tree walk used to visit all tree nodes and destroy the tree
951  * in post order. This is used for destroying a tree without paying any cost
959  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
961  *	avl_destroy(tree);
966  * On input, a cookie value of CHILDBIT indicates the tree is done.
969 avl_destroy_nodes(avl_tree_t *tree, void **cookie)
975 	size_t		off = tree->avl_offset;
981 		first = avl_first(tree);
984 		 * deal with an empty tree
1001 		if (tree->avl_root != NULL) {
1002 			ASSERT(tree->avl_numnodes == 1);
1003 			tree->avl_root = NULL;
1004 			tree->avl_numnodes = 0;
1010 	 * Remove the child pointer we just visited from the parent and tree.
1014 	ASSERT(tree->avl_numnodes > 1);
1015 	--tree->avl_numnodes;
1053 		ASSERT(node == tree->avl_root);