32  * AVL - generic AVL tree implementation for kernel use
36  * Here is a very brief overview. An AVL tree is a binary search tree that is
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
63  *	  there is no recursion stack present to move "up" in the tree,
85  *	  allows using half as much code (and hence cache footprint) for tree
89  *	  adjacent to where a new value would be inserted in the tree. The value
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()
138 	 * nowhere to walk to if tree is empty  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()
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()
261 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));  in avl_find()
295 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)  in avl_rotation()  argument
341 		 * the height of this sub-tree -- used in "return...;" below  in avl_rotation()
372 			tree->avl_root = child;  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()
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()
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.
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()
594 			diff = tree->avl_compar(new_data,  in avl_insert_here()
595 			    AVL_NODE2DATA(node, tree->avl_offset));  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()
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
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()
698 		 * move 'node' to delete's spot in the tree  in avl_remove()
710 			tree->avl_root = node;  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()
748 		tree->avl_root = node;  in avl_remove()
761 		 * Move up the tree and adjust the balance  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))
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()
988 	ASSERT(tree->avl_numnodes > 1);  in avl_destroy_nodes()
989 	--tree->avl_numnodes;  in avl_destroy_nodes()
1027 		ASSERT(node == tree->avl_root);  in avl_destroy_nodes()