1 // SPDX-License-Identifier: CDDL-1.0
10  * or https://opensource.org/licenses/CDDL-1.0.
33  * AVL - generic AVL tree implementation for kernel use
47  * rotations, which bring unbalanced subtrees back into the semi-balanced state.
51  *	- The AVL specific data structures are physically embedded as fields
56  *	- Since the AVL data is always embedded in other structures, there is
62  *      - The implementation uses iteration instead of explicit recursion,
67  *      - The left/right children pointers of a node are in an array.
77  *		int left_heavy;	// -1 when left subtree is taller at some node,
81  *		int right_heavy;// will be the opposite of left_heavy (-1 or 1)
83  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
89  *	- The avl_index_t is an opaque "cookie" used to find nodes at or
95  * Note - in addition to userland (e.g. libavl and libutil) and the kernel
120  * - If there is a left child, go to it, then to it's rightmost descendant.
122  * - otherwise we return through parent nodes until we've come from a right
123  *   child.
126  * NULL - if at the end of the nodes
132 	size_t off = tree->avl_offset;  in avl_walk()
134 	int right = 1 - left;  in avl_walk()
147 	 * If this node has a left child, go down one left, then all  in avl_walk()
150 	if (node->avl_child[left] != NULL) {  in avl_walk()
151 		for (node = node->avl_child[left];  in avl_walk()
152 		    node->avl_child[right] != NULL;  in avl_walk()
153 		    node = node->avl_child[right])  in avl_walk()
174  * (leftmost child from root of tree)
181 	size_t off = tree->avl_offset;  in avl_first()
183 	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])  in avl_first()
193  * (rightmost child from root of tree)
200 	size_t off = tree->avl_offset;  in avl_last()
202 	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])  in avl_last()
213  * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
222 	int child = AVL_INDEX2CHILD(where);  in avl_nearest()  local
225 	size_t off = tree->avl_offset;  in avl_nearest()
228 		ASSERT(tree->avl_root == NULL);  in avl_nearest()
232 	if (child != direction)  in avl_nearest()
253 	int child = 0;  in avl_find()  local
255 	size_t off = tree->avl_offset;  in avl_find()
257 	for (node = tree->avl_root; node != NULL;  in avl_find()
258 	    node = node->avl_child[child]) {  in avl_find()
262 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));  in avl_find()
263 		ASSERT(-1 <= diff && diff <= 1);  in avl_find()
271 		child = (diff > 0);  in avl_find()
275 		*where = AVL_MKINDEX(prev, child);  in avl_find()
293  * -2 or +2.
298 	int left = !(balance < 0);	/* when balance = -2, left will be 0 */  in avl_rotation()
299 	int right = 1 - left;  in avl_rotation()
301 	int right_heavy = -left_heavy;  in avl_rotation()
303 	avl_node_t *child = node->avl_child[left];  in avl_rotation()  local
309 	int child_bal = AVL_XBALANCE(child);  in avl_rotation()
312 	 * case 1 : node is overly left heavy, the left child is balanced or  in avl_rotation()
315 	 *                   (node bal:-2)  in avl_rotation()
318 	 *              (child bal:0 or -1)  in avl_rotation()
325 	 *              (child bal:1 or 0)  in avl_rotation()
328 	 *                        (node bal:-1 or 0)  in avl_rotation()
333 	 * we detect this situation by noting that child's balance is not  in avl_rotation()
339 		 * compute new balance of nodes  in avl_rotation()
341 		 * If child used to be left heavy (now balanced) we reduced  in avl_rotation()
342 		 * the height of this sub-tree -- used in "return...;" below  in avl_rotation()
347 		 * move "cright" to be node's left child  in avl_rotation()
349 		cright = child->avl_child[right];  in avl_rotation()
350 		node->avl_child[left] = cright;  in avl_rotation()
357 		 * move node to be child's right child  in avl_rotation()
359 		child->avl_child[right] = node;  in avl_rotation()
360 		AVL_SETBALANCE(node, -child_bal);  in avl_rotation()
362 		AVL_SETPARENT(node, child);  in avl_rotation()
367 		AVL_SETBALANCE(child, child_bal);  in avl_rotation()
368 		AVL_SETCHILD(child, which_child);  in avl_rotation()
369 		AVL_SETPARENT(child, parent);  in avl_rotation()
371 			parent->avl_child[which_child] = child;  in avl_rotation()
373 			tree->avl_root = child;  in avl_rotation()
379 	 * case 2 : When node is left heavy, but child is right heavy we use  in avl_rotation()
382 	 *                   (node b:-2)  in avl_rotation()
386 	 *             (child b:+1)  in avl_rotation()
400 	 *        (child b:?)   (node b:?)  in avl_rotation()
406 	 *	 if gchild was right_heavy, then child is now left heavy  in avl_rotation()
409 	gchild = child->avl_child[right];  in avl_rotation()
410 	gleft = gchild->avl_child[left];  in avl_rotation()
411 	gright = gchild->avl_child[right];  in avl_rotation()
414 	 * move gright to left child of node and  in avl_rotation()
416 	 * move gleft to right child of node  in avl_rotation()
418 	node->avl_child[left] = gright;  in avl_rotation()
424 	child->avl_child[right] = gleft;  in avl_rotation()
426 		AVL_SETPARENT(gleft, child);  in avl_rotation()
431 	 * move child to left child of gchild and  in avl_rotation()
433 	 * move node to right child of gchild and  in avl_rotation()
438 	gchild->avl_child[left] = child;  in avl_rotation()
439 	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));  in avl_rotation()
440 	AVL_SETPARENT(child, gchild);  in avl_rotation()
441 	AVL_SETCHILD(child, left);  in avl_rotation()
443 	gchild->avl_child[right] = node;  in avl_rotation()
452 		parent->avl_child[which_child] = gchild;  in avl_rotation()
454 		tree->avl_root = gchild;  in avl_rotation()
463  * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
478 	size_t off = tree->avl_offset;  in avl_insert()
489 	++tree->avl_numnodes;  in avl_insert()
491 	node->avl_child[0] = NULL;  in avl_insert()
492 	node->avl_child[1] = NULL;  in avl_insert()
498 		ASSERT(parent->avl_child[which_child] == NULL);  in avl_insert()
499 		parent->avl_child[which_child] = node;  in avl_insert()
501 		ASSERT(tree->avl_root == NULL);  in avl_insert()
502 		tree->avl_root = node;  in avl_insert()
505 	 * Now, back up the tree modifying the balance of all nodes above the  in avl_insert()
519 		new_balance = old_balance + (which_child ? 1 : -1);  in avl_insert()
531 		 * from -1 to -2 balance, do a rotation.  in avl_insert()
552  * if the given child of the node is already present we move to either
567 	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */  in avl_insert_here()  local
578 	 * If corresponding child of node is not NULL, go to the neighboring  in avl_insert_here()
581 	node = AVL_DATA2NODE(here, tree->avl_offset);  in avl_insert_here()
584 	diff = tree->avl_compar(new_data, here);  in avl_insert_here()
585 	ASSERT(-1 <= diff && diff <= 1);  in avl_insert_here()
587 	ASSERT(diff > 0 ? child == 1 : child == 0);  in avl_insert_here()
590 	if (node->avl_child[child] != NULL) {  in avl_insert_here()
591 		node = node->avl_child[child];  in avl_insert_here()
592 		child = 1 - child;  in avl_insert_here()
593 		while (node->avl_child[child] != NULL) {  in avl_insert_here()
595 			diff = tree->avl_compar(new_data,  in avl_insert_here()
596 			    AVL_NODE2DATA(node, tree->avl_offset));  in avl_insert_here()
597 			ASSERT(-1 <= diff && diff <= 1);  in avl_insert_here()
599 			ASSERT(diff > 0 ? child == 1 : child == 0);  in avl_insert_here()
601 			node = node->avl_child[child];  in avl_insert_here()
604 		diff = tree->avl_compar(new_data,  in avl_insert_here()
605 		    AVL_NODE2DATA(node, tree->avl_offset));  in avl_insert_here()
606 		ASSERT(-1 <= diff && diff <= 1);  in avl_insert_here()
608 		ASSERT(diff > 0 ? child == 1 : child == 0);  in avl_insert_here()
611 	ASSERT(node->avl_child[child] == NULL);  in avl_insert_here()
613 	avl_insert(tree, new_data, AVL_MKINDEX(node, child));  in avl_insert_here()
618  * be added to the tree with a VERIFY which is enabled for non-DEBUG builds.
665 	size_t off = tree->avl_offset;  in avl_remove()
670 	 * Deletion is easiest with a node that has at most 1 child.  in avl_remove()
672 	 * neighbor node. That node will have at most 1 child. Note this  in avl_remove()
673 	 * has no effect on the ordering of the remaining nodes.  in avl_remove()
679 	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {  in avl_remove()
686 		right = 1 - left;  in avl_remove()
692 		for (node = delete->avl_child[left];  in avl_remove()
693 		    node->avl_child[right] != NULL;  in avl_remove()
694 		    node = node->avl_child[right])  in avl_remove()
704 		if (node->avl_child[left] == node)  in avl_remove()
705 			node->avl_child[left] = &tmp;  in avl_remove()
709 			parent->avl_child[AVL_XCHILD(node)] = node;  in avl_remove()
711 			tree->avl_root = node;  in avl_remove()
712 		AVL_SETPARENT(node->avl_child[left], node);  in avl_remove()
713 		AVL_SETPARENT(node->avl_child[right], node);  in avl_remove()
717 		 * It always has a parent and at most 1 child.  in avl_remove()
721 		parent->avl_child[AVL_XCHILD(delete)] = delete;  in avl_remove()
722 		which_child = (delete->avl_child[1] != 0);  in avl_remove()
723 		if (delete->avl_child[which_child] != NULL)  in avl_remove()
724 			AVL_SETPARENT(delete->avl_child[which_child], delete);  in avl_remove()
732 	ASSERT(tree->avl_numnodes > 0);  in avl_remove()
733 	--tree->avl_numnodes;  in avl_remove()
736 	if (delete->avl_child[0] != NULL)  in avl_remove()
737 		node = delete->avl_child[0];  in avl_remove()
739 		node = delete->avl_child[1];  in avl_remove()
749 		tree->avl_root = node;  in avl_remove()
752 	parent->avl_child[which_child] = node;  in avl_remove()
769 		new_balance = old_balance - (which_child ? 1 : -1);  in avl_remove()
788 		 * of the sub-tree we have finished adjusting.  in avl_remove()
807 	    (t->avl_compar(obj, neighbor) <= 0));  in avl_update_lt()
810 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {  in avl_update_lt()
824 	    (t->avl_compar(obj, neighbor) >= 0));  in avl_update_gt()
827 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {  in avl_update_gt()
841 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {  in avl_update()
847 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {  in avl_update()
861 	ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar);  in avl_swap()
862 	ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset);  in avl_swap()
864 	temp_node = tree1->avl_root;  in avl_swap()
865 	temp_numnodes = tree1->avl_numnodes;  in avl_swap()
866 	tree1->avl_root = tree2->avl_root;  in avl_swap()
867 	tree1->avl_numnodes = tree2->avl_numnodes;  in avl_swap()
868 	tree2->avl_root = temp_node;  in avl_swap()
869 	tree2->avl_numnodes = temp_numnodes;  in avl_swap()
887 	tree->avl_compar = compar;  in avl_create()
888 	tree->avl_root = NULL;  in avl_create()
889 	tree->avl_numnodes = 0;  in avl_create()
890 	tree->avl_offset = offset;  in avl_create()
900 	ASSERT(tree->avl_numnodes == 0);  in avl_destroy()
901 	ASSERT(tree->avl_root == NULL);  in avl_destroy()
906  * Return the number of nodes in an AVL tree.
912 	return (tree->avl_numnodes);  in avl_numnodes()
919 	return (tree->avl_numnodes == 0);  in avl_is_empty()
925  * Post-order tree walk used to visit all tree nodes and destroy the tree
926  * in post order. This is used for removing all the nodes from a tree without
939  * an indication of which child you looked at last.
948 	int		child;  in avl_destroy_nodes()  local
950 	size_t		off = tree->avl_offset;  in avl_destroy_nodes()
976 		if (tree->avl_root != NULL) {  in avl_destroy_nodes()
977 			ASSERT(tree->avl_numnodes == 1);  in avl_destroy_nodes()
978 			tree->avl_root = NULL;  in avl_destroy_nodes()
979 			tree->avl_numnodes = 0;  in avl_destroy_nodes()
985 	 * Remove the child pointer we just visited from the parent and tree.  in avl_destroy_nodes()
987 	child = (uintptr_t)(*cookie) & CHILDBIT;  in avl_destroy_nodes()
988 	parent->avl_child[child] = NULL;  in avl_destroy_nodes()
989 	ASSERT(tree->avl_numnodes > 1);  in avl_destroy_nodes()
990 	--tree->avl_numnodes;  in avl_destroy_nodes()
993 	 * If we just removed a right child or there isn't one, go up to parent.  in avl_destroy_nodes()
995 	if (child == 1 || parent->avl_child[1] == NULL) {  in avl_destroy_nodes()
1002 	 * Do parent's right child, then leftmost descendent.  in avl_destroy_nodes()
1004 	node = parent->avl_child[1];  in avl_destroy_nodes()
1005 	while (node->avl_child[0] != NULL) {  in avl_destroy_nodes()
1007 		node = node->avl_child[0];  in avl_destroy_nodes()
1011 	 * If here, we moved to a left child. It may have one  in avl_destroy_nodes()
1012 	 * child on the right (when balance == +1).  in avl_destroy_nodes()
1015 	if (node->avl_child[1] != NULL) {  in avl_destroy_nodes()
1018 		node = node->avl_child[1];  in avl_destroy_nodes()
1019 		ASSERT(node->avl_child[0] == NULL &&  in avl_destroy_nodes()
1020 		    node->avl_child[1] == NULL);  in avl_destroy_nodes()
1028 		ASSERT(node == tree->avl_root);  in avl_destroy_nodes()