common/avl/avl.c

27  * AVL - generic AVL tree implementation for kernel use
31  * Here is a very brief overview. An AVL tree is a binary search tree that is
36  * This relaxation from a perfectly balanced binary tree allows doing
37  * insertion and deletion relatively efficiently. Searching the tree is
40  * The key to insertion and deletion is a set of tree maniuplations called
58  *	  there is no recursion stack present to move "up" in the tree,
80  *	  allows using half as much code (and hence cache footprint) for tree
84  *	  adjacent to where a new value would be inserted in the tree. The value
99  * Code that deals with binary tree data structures will randomly use
100  * left and right children when examining a tree.  C "if()" statements
124 avl_walk(avl_tree_t *tree, void	*oldnode, int left)
126 	size_t off = tree->avl_offset;
133 	 * nowhere to walk to if tree is empty
167  * Return the lowest valued node in a tree or NULL.
168  * (leftmost child from root of tree)
171 avl_first(avl_tree_t *tree)
175 	size_t off = tree->avl_offset;
177 	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
186  * Return the highest valued node in a tree or NULL.
187  * (rightmost child from root of tree)
190 avl_last(avl_tree_t *tree)
194 	size_t off = tree->avl_offset;
196 	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
211  *	"void *"  of the found tree node
214 avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
219 	size_t off = tree->avl_offset;
222 		ASSERT(tree->avl_root == NULL);
229 	return (avl_walk(tree, data, direction));
235  * simple binary tree search.
238  *	NULL: the value is not in the AVL tree
240  *	"void *"  of the found tree node
243 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where)
249 	size_t off = tree->avl_offset;
251 	for (node = tree->avl_root; node != NULL;
256 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
291 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
339 		 * the height of this sub-tree -- used in "return...;" below
370 			tree->avl_root = child;
453 		tree->avl_root = gchild;
455 	return (1);	/* the new tree is always shorter */
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)
477 	size_t off = tree->avl_offset;
479 	ASSERT(tree);
487 	 * First, add the node to the tree at the indicated position.
489 	++tree->avl_numnodes;
501 		ASSERT(tree->avl_root == NULL);
502 		tree->avl_root = node;
505 	 * Now, back up the tree modifying the balance of all nodes above the
507 	 * need to do a rotation.  If we back out of the tree we are done.
542 	 * perform a rotation to fix the tree and return
544 	(void) avl_rotation(tree, node, new_balance);
548  * Insert "new_data" in "tree" in the given "direction" either after or
551  * Insertions can only be done at empty leaf points in the tree, therefore
554  * every other node in the tree is a leaf, this always works.
561 	avl_tree_t *tree,
572 	ASSERT(tree != NULL);
581 	node = AVL_DATA2NODE(here, tree->avl_offset);
584 	diff = tree->avl_compar(new_data, here);
595 			diff = tree->avl_compar(new_data,
596 			    AVL_NODE2DATA(node, tree->avl_offset));
604 		diff = tree->avl_compar(new_data,
605 		    AVL_NODE2DATA(node, tree->avl_offset));
613 	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
617  * Add a new node to an AVL tree.
620 avl_add(avl_tree_t *tree, void *new_node)
630 	if (avl_find(tree, new_node, &where) != NULL)
636 	avl_insert(tree, new_node, where);
640  * Delete a node from the AVL tree.  Deletion is similar to insertion, but
653  * handled by temporarily swapping (d) and (c) in the tree and then using
656  * Secondly, an interior deletion from a deep tree may require more than one
657  * rotation to fix the balance. This is handled by moving up the tree through
663 avl_remove(avl_tree_t *tree, void *data)
674 	size_t off = tree->avl_offset;
676 	ASSERT(tree);
686 	 * As an optimization, we choose the greater neighbor if the tree
710 		 * move 'node' to delete's spot in the tree
722 			tree->avl_root = node;
741 	 * be easily removed from the tree.
743 	ASSERT(tree->avl_numnodes > 0);
744 	--tree->avl_numnodes;
760 		tree->avl_root = node;
773 		 * Move up the tree and adjust the balance
799 		 * of the sub-tree we have finished adjusting.
803 		else if (!avl_rotation(tree, node, new_balance))
808 #define	AVL_REINSERT(tree, obj)		\
809 	avl_remove((tree), (obj));	\
810 	avl_add((tree), (obj))
867  * initialize a new AVL tree
870 avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
873 	ASSERT(tree);
881 	tree->avl_compar = compar;
882 	tree->avl_root = NULL;
883 	tree->avl_numnodes = 0;
884 	tree->avl_size = size;
885 	tree->avl_offset = offset;
889  * Delete a tree.
893 avl_destroy(avl_tree_t *tree)
895 	ASSERT(tree);
896 	ASSERT(tree->avl_numnodes == 0);
897 	ASSERT(tree->avl_root == NULL);
902  * Return the number of nodes in an AVL tree.
905 avl_numnodes(avl_tree_t *tree)
907 	ASSERT(tree);
908 	return (tree->avl_numnodes);
912 avl_is_empty(avl_tree_t *tree)
914 	ASSERT(tree);
915 	return (tree->avl_numnodes == 0);
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
930  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
932  *	avl_destroy(tree);
937  * On input, a cookie value of CHILDBIT indicates the tree is done.
940 avl_destroy_nodes(avl_tree_t *tree, void **cookie)
946 	size_t		off = tree->avl_offset;
952 		first = avl_first(tree);
955 		 * deal with an empty tree
972 		if (tree->avl_root != NULL) {
973 			ASSERT(tree->avl_numnodes == 1);
974 			tree->avl_root = NULL;
975 			tree->avl_numnodes = 0;
981 	 * Remove the child pointer we just visited from the parent and tree.
985 	ASSERT(tree->avl_numnodes > 1);
986 	--tree->avl_numnodes;
1024 		ASSERT(node == tree->avl_root);