39  * any given node, the left and right subtrees are allowed to differ in height
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,
92  *	  pointer) is set to indicate if that the new node has a value greater
117  * Walk from one node to the previous valued node (ie. an infix walk
118  * towards the left). At any given node we do one of 2 things:
127  * otherwise next node
133 	avl_node_t *node = AVL_DATA2NODE(oldnode, off);  in avl_walk()  local
141 	if (node == NULL)  in avl_walk()
145 	 * Visit the previous valued node. There are two possibilities:  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()
160 			was_child = AVL_XCHILD(node);  in avl_walk()
161 			node = AVL_XPARENT(node);  in avl_walk()
162 			if (node == NULL)  in avl_walk()
169 	return (AVL_NODE2DATA(node, off));  in avl_walk()
173  * Return the lowest valued node in a tree or NULL.
179 	avl_node_t *node;  in avl_first()  local
183 	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])  in avl_first()
184 		prev = node;  in avl_first()
192  * Return the highest valued node in a tree or NULL.
198 	avl_node_t *node;  in avl_last()  local
202 	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])  in avl_last()
203 		prev = node;  in avl_last()
211  * Access the node immediately before or after an insertion point.
216  *	NULL: no node in the given direction
217  *	"void *"  of the found tree node
223 	avl_node_t *node = AVL_INDEX2NODE(where);  in avl_nearest()  local
227 	if (node == NULL) {  in avl_nearest()
231 	data = AVL_NODE2DATA(node, off);  in avl_nearest()
240  * Search for the node which contains "value".  The algorithm is a
246  *	"void *"  of the found tree node
251 	avl_node_t *node;  in avl_find()  local
257 	for (node = tree->avl_root; node != NULL;  in avl_find()
258 	    node = node->avl_child[child]) {  in avl_find()
260 		prev = node;  in avl_find()
262 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));  in avl_find()
269 			return (AVL_NODE2DATA(node, off));  in avl_find()
292  * On input balance is the "new" balance at "node". This value is either
296 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)  in avl_rotation()  argument
302 	avl_node_t *parent = AVL_XPARENT(node);  in avl_rotation()
303 	avl_node_t *child = node->avl_child[left];  in avl_rotation()
308 	int which_child = AVL_XCHILD(node);  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()
328 	 *                        (node bal:-1 or 0)  in avl_rotation()
347 		 * move "cright" to be node's left child  in avl_rotation()
350 		node->avl_child[left] = cright;  in avl_rotation()
352 			AVL_SETPARENT(cright, node);  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()
361 		AVL_SETCHILD(node, right);  in avl_rotation()
362 		AVL_SETPARENT(node, 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()
400 	 *        (child b:?)   (node b:?)  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()
420 		AVL_SETPARENT(gright, node);  in avl_rotation()
433 	 * move node to right child of gchild and  in avl_rotation()
443 	gchild->avl_child[right] = node;  in avl_rotation()
444 	AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));  in avl_rotation()
445 	AVL_SETPARENT(node, gchild);  in avl_rotation()
446 	AVL_SETCHILD(node, right);  in avl_rotation()
461  * Insert a new node into an AVL tree at the specified (from avl_find()) place.
464  * searches out to the leaf positions.  The avl_index_t indicates the node
465  * which will be the parent of the new node.
467  * After the node is inserted, a single rotation further up the tree may
473 	avl_node_t *node;  in avl_insert()  local
484 	node = AVL_DATA2NODE(new_data, off);  in avl_insert()
487 	 * First, add the node to the tree at the indicated position.  in avl_insert()
491 	node->avl_child[0] = NULL;  in avl_insert()
492 	node->avl_child[1] = NULL;  in avl_insert()
494 	AVL_SETCHILD(node, which_child);  in avl_insert()
495 	AVL_SETBALANCE(node, 0);  in avl_insert()
496 	AVL_SETPARENT(node, parent);  in avl_insert()
499 		parent->avl_child[which_child] = node;  in avl_insert()
502 		tree->avl_root = node;  in avl_insert()
511 		node = parent;  in avl_insert()
512 		if (node == NULL)  in avl_insert()
518 		old_balance = AVL_XBALANCE(node);  in avl_insert()
525 			AVL_SETBALANCE(node, 0);  in avl_insert()
536 		AVL_SETBALANCE(node, new_balance);  in avl_insert()
537 		parent = AVL_XPARENT(node);  in avl_insert()
538 		which_child = AVL_XCHILD(node);  in avl_insert()
544 	(void) avl_rotation(tree, node, new_balance);  in avl_insert()
552  * if the given child of the node is already present we move to either
554  * every other node in the tree is a leaf, this always works.
556  * To help developers using this interface, we assert that the new node
566 	avl_node_t *node;  in avl_insert_here()  local
578 	 * If corresponding child of node is not NULL, go to the neighboring  in avl_insert_here()
579 	 * node and reverse the insertion direction.  in avl_insert_here()
581 	node = AVL_DATA2NODE(here, tree->avl_offset);  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()
593 		while (node->avl_child[child] != NULL) {  in avl_insert_here()
596 			    AVL_NODE2DATA(node, tree->avl_offset));  in avl_insert_here()
601 			node = node->avl_child[child];  in avl_insert_here()
605 		    AVL_NODE2DATA(node, tree->avl_offset));  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()
617  * Add a new node to an AVL tree.  Strictly enforce that no duplicates can
631  * Delete a node from the AVL tree.  Deletion is similar to insertion, but
634  * First, we may be deleting an interior node. Consider the following subtree:
642  * When we are deleting node (d), we find and bring up an adjacent valued leaf
643  * node, say (c), to take the interior node's place. In the code this is
658 	avl_node_t *node;  in avl_remove()  local
670 	 * Deletion is easiest with a node that has at most 1 child.  in avl_remove()
671 	 * We swap a node with 2 children with a sequentially valued  in avl_remove()
672 	 * neighbor node. That node will have at most 1 child. Note this  in avl_remove()
682 		 * choose node to swap from whichever side is taller  in avl_remove()
689 		 * get to the previous value'd node  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()
698 		 * create a temp placeholder for 'node'  in avl_remove()
699 		 * move 'node' to delete's spot in the tree  in avl_remove()
701 		tmp = *node;  in avl_remove()
703 		memcpy(node, delete, sizeof (*node));  in avl_remove()
704 		if (node->avl_child[left] == node)  in avl_remove()
705 			node->avl_child[left] = &tmp;  in avl_remove()
707 		parent = AVL_XPARENT(node);  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()
716 		 * Put tmp where node used to be (just temporary).  in avl_remove()
729 	 * Here we know "delete" is at least partially a leaf node. It can  in avl_remove()
737 		node = delete->avl_child[0];  in avl_remove()
739 		node = delete->avl_child[1];  in avl_remove()
742 	 * Connect parent directly to node (leaving out delete).  in avl_remove()
744 	if (node != NULL) {  in avl_remove()
745 		AVL_SETPARENT(node, parent);  in avl_remove()
746 		AVL_SETCHILD(node, which_child);  in avl_remove()
749 		tree->avl_root = node;  in avl_remove()
752 	parent->avl_child[which_child] = node;  in avl_remove()
767 		node = parent;  in avl_remove()
768 		old_balance = AVL_XBALANCE(node);  in avl_remove()
770 		parent = AVL_XPARENT(node);  in avl_remove()
771 		which_child = AVL_XCHILD(node);  in avl_remove()
774 		 * If a node was in perfect balance but isn't anymore then  in avl_remove()
779 			AVL_SETBALANCE(node, new_balance);  in avl_remove()
791 			AVL_SETBALANCE(node, new_balance);  in avl_remove()
792 		else if (!avl_rotation(tree, node, new_balance))  in avl_remove()
932  *	my_data_t *node;
934  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
935  *		free(node);
938  * The cookie is really an avl_node_t to the current node's parent and
946 	avl_node_t	*node;  in avl_destroy_nodes()  local
953 	 * Initial calls go to the first node or it's right descendant.  in avl_destroy_nodes()
966 		node = AVL_DATA2NODE(first, off);  in avl_destroy_nodes()
967 		parent = AVL_XPARENT(node);  in avl_destroy_nodes()
996 		node = parent;  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()
1006 		parent = node;  in avl_destroy_nodes()
1007 		node = node->avl_child[0];  in avl_destroy_nodes()
1015 	if (node->avl_child[1] != NULL) {  in avl_destroy_nodes()
1016 		ASSERT(AVL_XBALANCE(node) == 1);  in avl_destroy_nodes()
1017 		parent = node;  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()
1022 		ASSERT(AVL_XBALANCE(node) <= 0);  in avl_destroy_nodes()
1028 		ASSERT(node == tree->avl_root);  in avl_destroy_nodes()
1030 		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));  in avl_destroy_nodes()
1033 	return (AVL_NODE2DATA(node, off));  in avl_destroy_nodes()