Function avl_insert

freebsd/contrib/openzfs/module/avl/avl.c:485–561

* Insert a new node into an AVL tree at the specified (from avl_find()) place. * * Newly inserted nodes are always leaf nodes in the tree, since avl_find() * searches out to the leaf positions. The avl_index_t indicates the node * which will be the parent of the new node. * * After the node is inserted, a single rotation further up the tree may * be necessary to maintain an acceptable AVL

 * be necessary to maintain an acceptable AVL balance.
 */
void
avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
{
	avl_node_t *node;
	avl_node_t *parent = AVL_INDEX2NODE(where);
	int old_balance;
	int new_balance;
	int which_child = AVL_INDEX2CHILD(where);
	size_t off = tree->avl_offset;

	ASSERT(tree);
#ifdef _LP64
	ASSERT(((uintptr_t)new_data & 0x7) == 0);
#endif

	node = AVL_DATA2NODE(new_data, off);

	/*
	 * First, add the node to the tree at the indicated position.
	 */
	++tree->avl_numnodes;

	node->avl_child[0] = NULL;
	node->avl_child[1] = NULL;

	AVL_SETCHILD(node, which_child);
	AVL_SETBALANCE(node, 0);
	AVL_SETPARENT(node, parent);
	if (parent != NULL) {
		ASSERT(parent->avl_child[which_child] == NULL);
		parent->avl_child[which_child] = node;
	} else {
		ASSERT(tree->avl_root == NULL);
		tree->avl_root = node;
	}
	/*
	 * Now, back up the tree modifying the balance of all nodes above the
	 * insertion point. If we get to a highly unbalanced ancestor, we
	 * need to do a rotation.  If we back out of the tree we are done.
	 * If we brought any subtree into perfect balance (0), we are also done.
	 */
	for (;;) {
		node = parent;
		if (node == NULL)
			return;

		/*
		 * Compute the new balance
		 */
		old_balance = AVL_XBALANCE(node);
		new_balance = old_balance + avl_child2balance[which_child];

		/*
		 * If we introduced equal balance, then we are done immediately
		 */
		if (new_balance == 0) {
			AVL_SETBALANCE(node, 0);
			return;