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
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.
76  *		int left_heavy;	// -1 when left subtree is taller at some node,
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
91  *	  pointer) is set to indicate if that the new node has a value greater
94  * Note - in addition to userland (e.g. libavl and libutil) and the kernel
116  * Walk from one node to the previous valued node (ie. an infix walk
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
122  *   child.
125  * NULL - if at the end of the nodes
126  * otherwise next node
131 	size_t off = tree->avl_offset;  in avl_walk()
132 	avl_node_t *node = AVL_DATA2NODE(oldnode, off);  in avl_walk()  local
133 	int right = 1 - left;  in avl_walk()
140 	if (node == NULL)  in avl_walk()
144 	 * Visit the previous valued node. There are two possibilities:  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()
159 			was_child = AVL_XCHILD(node);  in avl_walk()
160 			node = AVL_XPARENT(node);  in avl_walk()
161 			if (node == NULL)  in avl_walk()
168 	return (AVL_NODE2DATA(node, off));  in avl_walk()
172  * Return the lowest valued node in a tree or NULL.
173  * (leftmost child from root of tree)
178 	avl_node_t *node;  in avl_first()  local
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()
183 		prev = node;  in avl_first()
191  * Return the highest valued node in a tree or NULL.
192  * (rightmost child from root of tree)
197 	avl_node_t *node;  in avl_last()  local
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()
202 		prev = node;  in avl_last()
210  * Access the node immediately before or after an insertion point.
212  * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
215  *	NULL: no node in the given direction
216  *	"void *"  of the found tree node
221 	int child = AVL_INDEX2CHILD(where);  in avl_nearest()  local
222 	avl_node_t *node = AVL_INDEX2NODE(where);  in avl_nearest()  local
224 	size_t off = tree->avl_offset;  in avl_nearest()
226 	if (node == NULL) {  in avl_nearest()
227 		ASSERT(tree->avl_root == NULL);  in avl_nearest()
230 	data = AVL_NODE2DATA(node, off);  in avl_nearest()
231 	if (child != direction)  in avl_nearest()
239  * Search for the node which contains "value".  The algorithm is a
245  *	"void *"  of the found tree node
250 	avl_node_t *node;  in avl_find()  local
252 	int child = 0;  in avl_find()  local
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()
259 		prev = node;  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()
268 			return (AVL_NODE2DATA(node, off));  in avl_find()
270 		child = (diff > 0);  in avl_find()
274 		*where = AVL_MKINDEX(prev, child);  in avl_find()
291  * On input balance is the "new" balance at "node". This value is either
292  * -2 or +2.
295 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)  in avl_rotation()  argument
297 	int left = !(balance < 0);	/* when balance = -2, left will be 0 */  in avl_rotation()
298 	int right = 1 - left;  in avl_rotation()
300 	int right_heavy = -left_heavy;  in avl_rotation()
301 	avl_node_t *parent = AVL_XPARENT(node);  in avl_rotation()
302 	avl_node_t *child = node->avl_child[left];  in avl_rotation()  local
307 	int which_child = AVL_XCHILD(node);  in avl_rotation()
308 	int child_bal = AVL_XBALANCE(child);  in avl_rotation()
311 	 * case 1 : node is overly left heavy, the left child is balanced or  in avl_rotation()
314 	 *                   (node bal:-2)  in avl_rotation()
317 	 *              (child bal:0 or -1)  in avl_rotation()
324 	 *              (child bal:1 or 0)  in avl_rotation()
327 	 *                        (node bal:-1 or 0)  in avl_rotation()
332 	 * we detect this situation by noting that child's balance is not  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()
351 			AVL_SETPARENT(cright, node);  in avl_rotation()
356 		 * move node to be child's right child  in avl_rotation()
358 		child->avl_child[right] = node;  in avl_rotation()
359 		AVL_SETBALANCE(node, -child_bal);  in avl_rotation()
360 		AVL_SETCHILD(node, right);  in avl_rotation()
361 		AVL_SETPARENT(node, child);  in avl_rotation()
366 		AVL_SETBALANCE(child, child_bal);  in avl_rotation()
367 		AVL_SETCHILD(child, which_child);  in avl_rotation()
368 		AVL_SETPARENT(child, parent);  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()
385 	 *             (child b:+1)  in avl_rotation()
399 	 *        (child b:?)   (node b:?)  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()
415 	 * move gleft to right child of node  in avl_rotation()
417 	node->avl_child[left] = gright;  in avl_rotation()
419 		AVL_SETPARENT(gright, node);  in avl_rotation()
423 	child->avl_child[right] = gleft;  in avl_rotation()
425 		AVL_SETPARENT(gleft, child);  in avl_rotation()
430 	 * move child to left child of gchild and  in avl_rotation()
432 	 * move node to right child of gchild and  in avl_rotation()
437 	gchild->avl_child[left] = child;  in avl_rotation()
438 	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));  in avl_rotation()
439 	AVL_SETPARENT(child, gchild);  in avl_rotation()
440 	AVL_SETCHILD(child, left);  in avl_rotation()
442 	gchild->avl_child[right] = node;  in avl_rotation()
443 	AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));  in avl_rotation()
444 	AVL_SETPARENT(node, gchild);  in avl_rotation()
445 	AVL_SETCHILD(node, right);  in avl_rotation()
451 		parent->avl_child[which_child] = gchild;  in avl_rotation()
453 		tree->avl_root = gchild;  in avl_rotation()
460  * Insert a new node into an AVL tree at the specified (from avl_find()) place.
463  * searches out to the leaf positions.  The avl_index_t indicates the node
464  * which will be the parent of the new node.
466  * After the node is inserted, a single rotation further up the tree may
472 	avl_node_t *node;  in avl_insert()  local
477 	size_t off = tree->avl_offset;  in avl_insert()
483 	node = AVL_DATA2NODE(new_data, off);  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()
490 	node->avl_child[0] = NULL;  in avl_insert()
491 	node->avl_child[1] = NULL;  in avl_insert()
493 	AVL_SETCHILD(node, which_child);  in avl_insert()
494 	AVL_SETBALANCE(node, 0);  in avl_insert()
495 	AVL_SETPARENT(node, parent);  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()
510 		node = parent;  in avl_insert()
511 		if (node == NULL)  in avl_insert()
517 		old_balance = AVL_XBALANCE(node);  in avl_insert()
518 		new_balance = old_balance + (which_child ? 1 : -1);  in avl_insert()
524 			AVL_SETBALANCE(node, 0);  in avl_insert()
530 		 * from -1 to -2 balance, do a rotation.  in avl_insert()
535 		AVL_SETBALANCE(node, new_balance);  in avl_insert()
536 		parent = AVL_XPARENT(node);  in avl_insert()
537 		which_child = AVL_XCHILD(node);  in avl_insert()
543 	(void) avl_rotation(tree, node, new_balance);  in avl_insert()
551  * if the given child of the node is already present we move to either
553  * every other node in the tree is a leaf, this always works.
555  * To help developers using this interface, we assert that the new node
565 	avl_node_t *node;  in avl_insert_here()  local
566 	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */  in avl_insert_here()  local
577 	 * If corresponding child of node is not NULL, go to the neighboring  in avl_insert_here()
578 	 * node and reverse the insertion direction.  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()
584 	ASSERT(-1 <= diff && diff <= 1);  in avl_insert_here()
586 	ASSERT(diff > 0 ? child == 1 : child == 0);  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()
598 			ASSERT(diff > 0 ? child == 1 : child == 0);  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()
607 		ASSERT(diff > 0 ? child == 1 : child == 0);  in avl_insert_here()
610 	ASSERT(node->avl_child[child] == NULL);  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.
630  * Delete a node from the AVL tree.  Deletion is similar to insertion, but
633  * First, we may be deleting an interior node. Consider the following subtree:
641  * When we are deleting node (d), we find and bring up an adjacent valued leaf
642  * node, say (c), to take the interior node's place. In the code this is
657 	avl_node_t *node;  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()
670 	 * We swap a node with 2 children with a sequentially valued  in avl_remove()
671 	 * neighbor node. That node will have at most 1 child. Note this  in avl_remove()
678 	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {  in avl_remove()
681 		 * choose node to swap from whichever side is taller  in avl_remove()
685 		right = 1 - left;  in avl_remove()
688 		 * get to the previous value'd node  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()
697 		 * create a temp placeholder for 'node'  in avl_remove()
698 		 * move 'node' to delete's spot in the tree  in avl_remove()
700 		tmp = *node;  in avl_remove()
702 		memcpy(node, delete, sizeof (*node));  in avl_remove()
703 		if (node->avl_child[left] == node)  in avl_remove()
704 			node->avl_child[left] = &tmp;  in avl_remove()
706 		parent = AVL_XPARENT(node);  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()
715 		 * Put tmp where node used to be (just temporary).  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()
728 	 * Here we know "delete" is at least partially a leaf node. It can  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()
741 	 * Connect parent directly to node (leaving out delete).  in avl_remove()
743 	if (node != NULL) {  in avl_remove()
744 		AVL_SETPARENT(node, parent);  in avl_remove()
745 		AVL_SETCHILD(node, which_child);  in avl_remove()
748 		tree->avl_root = node;  in avl_remove()
751 	parent->avl_child[which_child] = node;  in avl_remove()
766 		node = parent;  in avl_remove()
767 		old_balance = AVL_XBALANCE(node);  in avl_remove()
768 		new_balance = old_balance - (which_child ? 1 : -1);  in avl_remove()
769 		parent = AVL_XPARENT(node);  in avl_remove()
770 		which_child = AVL_XCHILD(node);  in avl_remove()
773 		 * If a node was in perfect balance but isn't anymore then  in avl_remove()
778 			AVL_SETBALANCE(node, new_balance);  in avl_remove()
787 		 * of the sub-tree we have finished adjusting.  in avl_remove()
790 			AVL_SETBALANCE(node, new_balance);  in avl_remove()
791 		else if (!avl_rotation(tree, node, new_balance))  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
931  *	my_data_t *node;
933  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
934  *		free(node);
937  * The cookie is really an avl_node_t to the current node's parent and
938  * an indication of which child you looked at last.
945 	avl_node_t	*node;  in avl_destroy_nodes()  local
947 	int		child;  in avl_destroy_nodes()  local
949 	size_t		off = tree->avl_offset;  in avl_destroy_nodes()
952 	 * Initial calls go to the first node or it's right descendant.  in avl_destroy_nodes()
965 		node = AVL_DATA2NODE(first, off);  in avl_destroy_nodes()
966 		parent = AVL_XPARENT(node);  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()
986 	child = (uintptr_t)(*cookie) & CHILDBIT;  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()
992 	 * If we just removed a right child or there isn't one, go up to parent.  in avl_destroy_nodes()
994 	if (child == 1 || parent->avl_child[1] == NULL) {  in avl_destroy_nodes()
995 		node = parent;  in avl_destroy_nodes()
1001 	 * Do parent's right child, then leftmost descendent.  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()
1005 		parent = node;  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()
1011 	 * child on the right (when balance == +1).  in avl_destroy_nodes()
1014 	if (node->avl_child[1] != NULL) {  in avl_destroy_nodes()
1015 		ASSERT(AVL_XBALANCE(node) == 1);  in avl_destroy_nodes()
1016 		parent = node;  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()
1021 		ASSERT(AVL_XBALANCE(node) <= 0);  in avl_destroy_nodes()
1027 		ASSERT(node == tree->avl_root);  in avl_destroy_nodes()
1029 		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));  in avl_destroy_nodes()
1032 	return (AVL_NODE2DATA(node, off));  in avl_destroy_nodes()