9  * or https://opensource.org/licenses/CDDL-1.0.
32  * AVL - generic AVL tree implementation for kernel use
38  * any given node, the left and right subtrees are allowed to differ in height
39  * by at most 1 level.
46  * rotations, which bring unbalanced subtrees back into the semi-balanced state.
50  *	- The AVL specific data structures are physically embedded as fields
55  *	- Since the AVL data is always embedded in other structures, there is
61  *      - The implementation uses iteration instead of explicit recursion,
66  *      - The left/right children pointers of a node are in an array.
68  *	  left and right indices.  The implementation is written as if it only
69  *	  dealt with left handed manipulations.  By changing the value assigned
70  *	  to "left", the code also works for right handed trees.  The
73  *		int left;	// 0 when dealing with left children,
76  *		int left_heavy;	// -1 when left subtree is taller at some node,
79  *		int right;	// will be the opposite of left (0 or 1)
80  *		int right_heavy;// will be the opposite of left_heavy (-1 or 1)
82  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
88  *	- The avl_index_t is an opaque "cookie" used to find nodes at or
94  * Note - in addition to userland (e.g. libavl and libutil) and the kernel
117  * towards the left). At any given node we do one of 2 things:
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()
146 	 * If this node has a left child, go down one left, then all  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()
155 	 * Otherwise, return through left children as far as we can.  in avl_walk()
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()
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()
224 	size_t off = tree->avl_offset;  in avl_nearest()
227 		ASSERT(tree->avl_root == NULL);  in avl_nearest()
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()
288  * The code is written as if handling left rotations, right rotations are
289  * symmetric and handled by swapping values of variables right/left[_heavy]
292  * -2 or +2.
297 	int left = !(balance < 0);	/* when balance = -2, left will be 0 */  in avl_rotation()  local
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()
311 	 * case 1 : node is overly left heavy, the left child is balanced or  in avl_rotation()
312 	 * also left heavy. This requires the following rotation.  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()
340 		 * If child used to be left heavy (now balanced) we reduced  in avl_rotation()
341 		 * the height of this sub-tree -- used in "return...;" below  in avl_rotation()
346 		 * move "cright" to be node's left child  in avl_rotation()
348 		cright = child->avl_child[right];  in avl_rotation()
349 		node->avl_child[left] = cright;  in avl_rotation()
352 			AVL_SETCHILD(cright, left);  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()
378 	 * case 2 : When node is left heavy, but child is right heavy we use  in avl_rotation()
381 	 *                   (node b:-2)  in avl_rotation()
405 	 *	 if gchild was right_heavy, then child is now left heavy  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()
413 	 * move gright to left child of node and  in avl_rotation()
417 	node->avl_child[left] = gright;  in avl_rotation()
420 		AVL_SETCHILD(gright, left);  in avl_rotation()
423 	child->avl_child[right] = gleft;  in avl_rotation()
430 	 * move child to left child of gchild and  in avl_rotation()
437 	gchild->avl_child[left] = child;  in avl_rotation()
440 	AVL_SETCHILD(child, left);  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()
477 	size_t off = tree->avl_offset;  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()
518 		new_balance = old_balance + (which_child ? 1 : -1);  in avl_insert()
530 		 * from -1 to -2 balance, do a rotation.  in avl_insert()
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()
617  * be added to the tree with a VERIFY which is enabled for non-DEBUG builds.
661 	int left;  in avl_remove()  local
664 	size_t off = tree->avl_offset;  in avl_remove()
669 	 * Deletion is easiest with a node that has at most 1 child.  in avl_remove()
671 	 * neighbor node. That node will have at most 1 child. Note this  in avl_remove()
675 	 * is right heavy, otherwise the left neighbor. This reduces the  in avl_remove()
678 	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {  in avl_remove()
684 		left = (old_balance > 0);  in avl_remove()
685 		right = 1 - left;  in avl_remove()
689 		 * (down 1 left, as far as possible right)  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()
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()
716 		 * It always has a parent and at most 1 child.  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()
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()
768 		new_balance = old_balance - (which_child ? 1 : -1);  in avl_remove()
787 		 * of the sub-tree we have finished adjusting.  in avl_remove()
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()
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()
899 	ASSERT(tree->avl_numnodes == 0);  in avl_destroy()
900 	ASSERT(tree->avl_root == NULL);  in avl_destroy()
911 	return (tree->avl_numnodes);  in avl_numnodes()
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
949 	size_t		off = tree->avl_offset;  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()
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()
1010 	 * If here, we moved to a left child. It may have one  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()