27c478bdstevel@tonic-gate * CDDL HEADER START
37c478bdstevel@tonic-gate *
47c478bdstevel@tonic-gate * The contents of this file are subject to the terms of the
5208e825sommerfe * Common Development and Distribution License (the "License").
6208e825sommerfe * You may not use this file except in compliance with the License.
77c478bdstevel@tonic-gate *
87c478bdstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bdstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bdstevel@tonic-gate * See the License for the specific language governing permissions
117c478bdstevel@tonic-gate * and limitations under the License.
127c478bdstevel@tonic-gate *
137c478bdstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bdstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bdstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bdstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bdstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bdstevel@tonic-gate *
197c478bdstevel@tonic-gate * CDDL HEADER END
207c478bdstevel@tonic-gate */
22b24ab67Jeff Bonwick * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
237c478bdstevel@tonic-gate * Use is subject to license terms.
247c478bdstevel@tonic-gate */
27faa2b6bJosef 'Jeff' Sipek * Copyright 2015 Nexenta Systems, Inc.  All rights reserved.
2886f617eEli Rosenthal * Copyright (c) 2015 by Delphix. All rights reserved.
290f6d88aAlex Reece */
300f6d88aAlex Reece
310f6d88aAlex Reece/*
327c478bdstevel@tonic-gate * AVL - generic AVL tree implementation for kernel use
337c478bdstevel@tonic-gate *
347c478bdstevel@tonic-gate * A complete description of AVL trees can be found in many CS textbooks.
357c478bdstevel@tonic-gate *
367c478bdstevel@tonic-gate * Here is a very brief overview. An AVL tree is a binary search tree that is
377c478bdstevel@tonic-gate * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
387c478bdstevel@tonic-gate * any given node, the left and right subtrees are allowed to differ in height
397c478bdstevel@tonic-gate * by at most 1 level.
407c478bdstevel@tonic-gate *
417c478bdstevel@tonic-gate * This relaxation from a perfectly balanced binary tree allows doing
427c478bdstevel@tonic-gate * insertion and deletion relatively efficiently. Searching the tree is
437c478bdstevel@tonic-gate * still a fast operation, roughly O(log(N)).
447c478bdstevel@tonic-gate *
456907ca4Josef 'Jeff' Sipek * The key to insertion and deletion is a set of tree manipulations called
467c478bdstevel@tonic-gate * rotations, which bring unbalanced subtrees back into the semi-balanced state.
477c478bdstevel@tonic-gate *
487c478bdstevel@tonic-gate * This implementation of AVL trees has the following peculiarities:
497c478bdstevel@tonic-gate *
507c478bdstevel@tonic-gate *	- The AVL specific data structures are physically embedded as fields
517c478bdstevel@tonic-gate *	  in the "using" data structures.  To maintain generality the code
527c478bdstevel@tonic-gate *	  must constantly translate between "avl_node_t *" and containing
536907ca4Josef 'Jeff' Sipek *	  data structure "void *"s by adding/subtracting the avl_offset.
547c478bdstevel@tonic-gate *
557c478bdstevel@tonic-gate *	- Since the AVL data is always embedded in other structures, there is
567c478bdstevel@tonic-gate *	  no locking or memory allocation in the AVL routines. This must be
577c478bdstevel@tonic-gate *	  provided for by the enclosing data structure's semantics. Typically,
58fa9e406ahrens *	  avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
597c478bdstevel@tonic-gate *	  exclusive write lock. Other operations require a read lock.
607c478bdstevel@tonic-gate *
617c478bdstevel@tonic-gate *      - The implementation uses iteration instead of explicit recursion,
627c478bdstevel@tonic-gate *	  since it is intended to run on limited size kernel stacks. Since
637c478bdstevel@tonic-gate *	  there is no recursion stack present to move "up" in the tree,
647c478bdstevel@tonic-gate *	  there is an explicit "parent" link in the avl_node_t.
657c478bdstevel@tonic-gate *
667c478bdstevel@tonic-gate *      - The left/right children pointers of a node are in an array.
677c478bdstevel@tonic-gate *	  In the code, variables (instead of constants) are used to represent
687c478bdstevel@tonic-gate *	  left and right indices.  The implementation is written as if it only
697c478bdstevel@tonic-gate *	  dealt with left handed manipulations.  By changing the value assigned
707c478bdstevel@tonic-gate *	  to "left", the code also works for right handed trees.  The
717c478bdstevel@tonic-gate *	  following variables/terms are frequently used:
727c478bdstevel@tonic-gate *
737c478bdstevel@tonic-gate *		int left;	// 0 when dealing with left children,
747c478bdstevel@tonic-gate *				// 1 for dealing with right children
757c478bdstevel@tonic-gate *
767c478bdstevel@tonic-gate *		int left_heavy;	// -1 when left subtree is taller at some node,
777c478bdstevel@tonic-gate *				// +1 when right subtree is taller
787c478bdstevel@tonic-gate *
797c478bdstevel@tonic-gate *		int right;	// will be the opposite of left (0 or 1)
807c478bdstevel@tonic-gate *		int right_heavy;// will be the opposite of left_heavy (-1 or 1)
817c478bdstevel@tonic-gate *
827c478bdstevel@tonic-gate *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
837c478bdstevel@tonic-gate *
847c478bdstevel@tonic-gate *	  Though it is a little more confusing to read the code, the approach
857c478bdstevel@tonic-gate *	  allows using half as much code (and hence cache footprint) for tree
867c478bdstevel@tonic-gate *	  manipulations and eliminates many conditional branches.
877c478bdstevel@tonic-gate *
887c478bdstevel@tonic-gate *	- The avl_index_t is an opaque "cookie" used to find nodes at or
897c478bdstevel@tonic-gate *	  adjacent to where a new value would be inserted in the tree. The value
907c478bdstevel@tonic-gate *	  is a modified "avl_node_t *".  The bottom bit (normally 0 for a
917c478bdstevel@tonic-gate *	  pointer) is set to indicate if that the new node has a value greater
927c478bdstevel@tonic-gate *	  than the value of the indicated "avl_node_t *".
930f6d88aAlex Reece *
940f6d88aAlex Reece * Note - in addition to userland (e.g. libavl and libutil) and the kernel
950f6d88aAlex Reece * (e.g. genunix), avl.c is compiled into ld.so and kmdb's genunix module,
960f6d88aAlex Reece * which each have their own compilation environments and subsequent
970f6d88aAlex Reece * requirements. Each of these environments must be considered when adding
980f6d88aAlex Reece * dependencies from avl.c.
997c478bdstevel@tonic-gate */
1017c478bdstevel@tonic-gate#include <sys/types.h>
1027c478bdstevel@tonic-gate#include <sys/param.h>
1037c478bdstevel@tonic-gate#include <sys/debug.h>
1047c478bdstevel@tonic-gate#include <sys/avl.h>
105fa9e406ahrens#include <sys/cmn_err.h>
1086907ca4Josef 'Jeff' Sipek * Small arrays to translate between balance (or diff) values and child indices.
1097c478bdstevel@tonic-gate *
1107c478bdstevel@tonic-gate * Code that deals with binary tree data structures will randomly use
1117c478bdstevel@tonic-gate * left and right children when examining a tree.  C "if()" statements
1127c478bdstevel@tonic-gate * which evaluate randomly suffer from very poor hardware branch prediction.
1137c478bdstevel@tonic-gate * In this code we avoid some of the branch mispredictions by using the
1147c478bdstevel@tonic-gate * following translation arrays. They replace random branches with an
1157c478bdstevel@tonic-gate * additional memory reference. Since the translation arrays are both very
1167c478bdstevel@tonic-gate * small the data should remain efficiently in cache.
1177c478bdstevel@tonic-gate */
1187c478bdstevel@tonic-gatestatic const int  avl_child2balance[2]	= {-1, 1};
1197c478bdstevel@tonic-gatestatic const int  avl_balance2child[]	= {0, 0, 1};
1237c478bdstevel@tonic-gate * Walk from one node to the previous valued node (ie. an infix walk
1247c478bdstevel@tonic-gate * towards the left). At any given node we do one of 2 things:
1257c478bdstevel@tonic-gate *
1267c478bdstevel@tonic-gate * - If there is a left child, go to it, then to it's rightmost descendant.
1277c478bdstevel@tonic-gate *
1286907ca4Josef 'Jeff' Sipek * - otherwise we return through parent nodes until we've come from a right
1296907ca4Josef 'Jeff' Sipek *   child.
1307c478bdstevel@tonic-gate *
1317c478bdstevel@tonic-gate * Return Value:
1327c478bdstevel@tonic-gate * NULL - if at the end of the nodes
1337c478bdstevel@tonic-gate * otherwise next node
1347c478bdstevel@tonic-gate */
1357c478bdstevel@tonic-gatevoid *
1367c478bdstevel@tonic-gateavl_walk(avl_tree_t *tree, void	*oldnode, int left)
1387c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
1397c478bdstevel@tonic-gate	avl_node_t *node = AVL_DATA2NODE(oldnode, off);
1407c478bdstevel@tonic-gate	int right = 1 - left;
1417c478bdstevel@tonic-gate	int was_child;
1447c478bdstevel@tonic-gate	/*
1457c478bdstevel@tonic-gate	 * nowhere to walk to if tree is empty
1467c478bdstevel@tonic-gate	 */
1477c478bdstevel@tonic-gate	if (node == NULL)
1487c478bdstevel@tonic-gate		return (NULL);
1507c478bdstevel@tonic-gate	/*
1517c478bdstevel@tonic-gate	 * Visit the previous valued node. There are two possibilities:
1527c478bdstevel@tonic-gate	 *
1537c478bdstevel@tonic-gate	 * If this node has a left child, go down one left, then all
1547c478bdstevel@tonic-gate	 * the way right.
1557c478bdstevel@tonic-gate	 */
1567c478bdstevel@tonic-gate	if (node->avl_child[left] != NULL) {
1577c478bdstevel@tonic-gate		for (node = node->avl_child[left];
1587c478bdstevel@tonic-gate		    node->avl_child[right] != NULL;
1597c478bdstevel@tonic-gate		    node = node->avl_child[right])
1607c478bdstevel@tonic-gate			;
1617c478bdstevel@tonic-gate	/*
1627c478bdstevel@tonic-gate	 * Otherwise, return thru left children as far as we can.
1637c478bdstevel@tonic-gate	 */
1647c478bdstevel@tonic-gate	} else {
1657c478bdstevel@tonic-gate		for (;;) {
1667c478bdstevel@tonic-gate			was_child = AVL_XCHILD(node);
1677c478bdstevel@tonic-gate			node = AVL_XPARENT(node);
1687c478bdstevel@tonic-gate			if (node == NULL)
1697c478bdstevel@tonic-gate				return (NULL);
1707c478bdstevel@tonic-gate			if (was_child == right)
1717c478bdstevel@tonic-gate				break;
1727c478bdstevel@tonic-gate		}
1737c478bdstevel@tonic-gate	}
1757c478bdstevel@tonic-gate	return (AVL_NODE2DATA(node, off));
1797c478bdstevel@tonic-gate * Return the lowest valued node in a tree or NULL.
1807c478bdstevel@tonic-gate * (leftmost child from root of tree)
1817c478bdstevel@tonic-gate */
1827c478bdstevel@tonic-gatevoid *
1837c478bdstevel@tonic-gateavl_first(avl_tree_t *tree)
1857c478bdstevel@tonic-gate	avl_node_t *node;
1867c478bdstevel@tonic-gate	avl_node_t *prev = NULL;
1877c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
1897c478bdstevel@tonic-gate	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
1907c478bdstevel@tonic-gate		prev = node;
1927c478bdstevel@tonic-gate	if (prev != NULL)
1937c478bdstevel@tonic-gate		return (AVL_NODE2DATA(prev, off));
1947c478bdstevel@tonic-gate	return (NULL);
1987c478bdstevel@tonic-gate * Return the highest valued node in a tree or NULL.
1997c478bdstevel@tonic-gate * (rightmost child from root of tree)
2007c478bdstevel@tonic-gate */
2017c478bdstevel@tonic-gatevoid *
2027c478bdstevel@tonic-gateavl_last(avl_tree_t *tree)
2047c478bdstevel@tonic-gate	avl_node_t *node;
2057c478bdstevel@tonic-gate	avl_node_t *prev = NULL;
2067c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
2087c478bdstevel@tonic-gate	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
2097c478bdstevel@tonic-gate		prev = node;
2117c478bdstevel@tonic-gate	if (prev != NULL)
2127c478bdstevel@tonic-gate		return (AVL_NODE2DATA(prev, off));
2137c478bdstevel@tonic-gate	return (NULL);
2177c478bdstevel@tonic-gate * Access the node immediately before or after an insertion point.
2187c478bdstevel@tonic-gate *
2197c478bdstevel@tonic-gate * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
2207c478bdstevel@tonic-gate *
2217c478bdstevel@tonic-gate * Return value:
2227c478bdstevel@tonic-gate *	NULL: no node in the given direction
2237c478bdstevel@tonic-gate *	"void *"  of the found tree node
2247c478bdstevel@tonic-gate */
2257c478bdstevel@tonic-gatevoid *
2267c478bdstevel@tonic-gateavl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
2287c478bdstevel@tonic-gate	int child = AVL_INDEX2CHILD(where);
2297c478bdstevel@tonic-gate	avl_node_t *node = AVL_INDEX2NODE(where);
2307c478bdstevel@tonic-gate	void *data;
2317c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
2337c478bdstevel@tonic-gate	if (node == NULL) {
2347c478bdstevel@tonic-gate		ASSERT(tree->avl_root == NULL);
2357c478bdstevel@tonic-gate		return (NULL);
2367c478bdstevel@tonic-gate	}
2377c478bdstevel@tonic-gate	data = AVL_NODE2DATA(node, off);
2387c478bdstevel@tonic-gate	if (child != direction)
2397c478bdstevel@tonic-gate		return (data);
2417c478bdstevel@tonic-gate	return (avl_walk(tree, data, direction));
2467c478bdstevel@tonic-gate * Search for the node which contains "value".  The algorithm is a
2477c478bdstevel@tonic-gate * simple binary tree search.
2487c478bdstevel@tonic-gate *
2497c478bdstevel@tonic-gate * return value:
2507c478bdstevel@tonic-gate *	NULL: the value is not in the AVL tree
2517c478bdstevel@tonic-gate *		*where (if not NULL)  is set to indicate the insertion point
2527c478bdstevel@tonic-gate *	"void *"  of the found tree node
2537c478bdstevel@tonic-gate */
2547c478bdstevel@tonic-gatevoid *
255b24ab67Jeff Bonwickavl_find(avl_tree_t *tree, const void *value, avl_index_t *where)
2577c478bdstevel@tonic-gate	avl_node_t *node;
2587c478bdstevel@tonic-gate	avl_node_t *prev = NULL;
2597c478bdstevel@tonic-gate	int child = 0;
2607c478bdstevel@tonic-gate	int diff;
2617c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
2637c478bdstevel@tonic-gate	for (node = tree->avl_root; node != NULL;
2647c478bdstevel@tonic-gate	    node = node->avl_child[child]) {
2667c478bdstevel@tonic-gate		prev = node;
2687c478bdstevel@tonic-gate		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
2697c478bdstevel@tonic-gate		ASSERT(-1 <= diff && diff <= 1);
2707c478bdstevel@tonic-gate		if (diff == 0) {
2717c478bdstevel@tonic-gate#ifdef DEBUG
2727c478bdstevel@tonic-gate			if (where != NULL)
2735ad8204nd				*where = 0;
2757c478bdstevel@tonic-gate			return (AVL_NODE2DATA(node, off));
2767c478bdstevel@tonic-gate		}
2777c478bdstevel@tonic-gate		child = avl_balance2child[1 + diff];
2797c478bdstevel@tonic-gate	}
2817c478bdstevel@tonic-gate	if (where != NULL)
2827c478bdstevel@tonic-gate		*where = AVL_MKINDEX(prev, child);
2847c478bdstevel@tonic-gate	return (NULL);
2897c478bdstevel@tonic-gate * Perform a rotation to restore balance at the subtree given by depth.
2907c478bdstevel@tonic-gate *
2917c478bdstevel@tonic-gate * This routine is used by both insertion and deletion. The return value
2927c478bdstevel@tonic-gate * indicates:
2937c478bdstevel@tonic-gate *	 0 : subtree did not change height
2947c478bdstevel@tonic-gate *	!0 : subtree was reduced in height
2957c478bdstevel@tonic-gate *
2967c478bdstevel@tonic-gate * The code is written as if handling left rotations, right rotations are
2977c478bdstevel@tonic-gate * symmetric and handled by swapping values of variables right/left[_heavy]
2987c478bdstevel@tonic-gate *
2997c478bdstevel@tonic-gate * On input balance is the "new" balance at "node". This value is either
3007c478bdstevel@tonic-gate * -2 or +2.
3017c478bdstevel@tonic-gate */
3027c478bdstevel@tonic-gatestatic int
3037c478bdstevel@tonic-gateavl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
3057c478bdstevel@tonic-gate	int left = !(balance < 0);	/* when balance = -2, left will be 0 */
3067c478bdstevel@tonic-gate	int right = 1 - left;
3077c478bdstevel@tonic-gate	int left_heavy = balance >> 1;
3087c478bdstevel@tonic-gate	int right_heavy = -left_heavy;
3097c478bdstevel@tonic-gate	avl_node_t *parent = AVL_XPARENT(node);
3107c478bdstevel@tonic-gate	avl_node_t *child = node->avl_child[left];
3117c478bdstevel@tonic-gate	avl_node_t *cright;
3127c478bdstevel@tonic-gate	avl_node_t *gchild;
3137c478bdstevel@tonic-gate	avl_node_t *gright;
3147c478bdstevel@tonic-gate	avl_node_t *gleft;
3157c478bdstevel@tonic-gate	int which_child = AVL_XCHILD(node);
3167c478bdstevel@tonic-gate	int child_bal = AVL_XBALANCE(child);
3187c478bdstevel@tonic-gate	/* BEGIN CSTYLED */
3197c478bdstevel@tonic-gate	/*
3207c478bdstevel@tonic-gate	 * case 1 : node is overly left heavy, the left child is balanced or
3217c478bdstevel@tonic-gate	 * also left heavy. This requires the following rotation.
3227c478bdstevel@tonic-gate	 *
3237c478bdstevel@tonic-gate	 *                   (node bal:-2)
3247c478bdstevel@tonic-gate	 *                    /           \
3257c478bdstevel@tonic-gate	 *                   /             \
3267c478bdstevel@tonic-gate	 *              (child bal:0 or -1)
3277c478bdstevel@tonic-gate	 *              /    \
3287c478bdstevel@tonic-gate	 *             /      \
3297c478bdstevel@tonic-gate	 *                     cright
3307c478bdstevel@tonic-gate	 *
3317c478bdstevel@tonic-gate	 * becomes:
3327c478bdstevel@tonic-gate	 *
3337c478bdstevel@tonic-gate	 *              (child bal:1 or 0)
3347c478bdstevel@tonic-gate	 *              /        \
3357c478bdstevel@tonic-gate	 *             /          \
3367c478bdstevel@tonic-gate	 *                        (node bal:-1 or 0)
3377c478bdstevel@tonic-gate	 *                         /     \
3387c478bdstevel@tonic-gate	 *                        /       \
3397c478bdstevel@tonic-gate	 *                     cright
3407c478bdstevel@tonic-gate	 *
3417c478bdstevel@tonic-gate	 * we detect this situation by noting that child's balance is not
3427c478bdstevel@tonic-gate	 * right_heavy.
3437c478bdstevel@tonic-gate	 */
3447c478bdstevel@tonic-gate	/* END CSTYLED */
3457c478bdstevel@tonic-gate	if (child_bal != right_heavy) {
3477c478bdstevel@tonic-gate		/*
3487c478bdstevel@tonic-gate		 * compute new balance of nodes
3497c478bdstevel@tonic-gate		 *
3507c478bdstevel@tonic-gate		 * If child used to be left heavy (now balanced) we reduced
3517c478bdstevel@tonic-gate		 * the height of this sub-tree -- used in "return...;" below
3527c478bdstevel@tonic-gate		 */
3537c478bdstevel@tonic-gate		child_bal += right_heavy; /* adjust towards right */
3557c478bdstevel@tonic-gate		/*
3567c478bdstevel@tonic-gate		 * move "cright" to be node's left child
3577c478bdstevel@tonic-gate		 */
3587c478bdstevel@tonic-gate		cright = child->avl_child[right];
3597c478bdstevel@tonic-gate		node->avl_child[left] = cright;
3607c478bdstevel@tonic-gate		if (cright != NULL) {
3617c478bdstevel@tonic-gate			AVL_SETPARENT(cright, node);
3627c478bdstevel@tonic-gate			AVL_SETCHILD(cright, left);
3637c478bdstevel@tonic-gate		}
3657c478bdstevel@tonic-gate		/*
3667c478bdstevel@tonic-gate		 * move node to be child's right child
3677c478bdstevel@tonic-gate		 */
3687c478bdstevel@tonic-gate		child->avl_child[right] = node;
3697c478bdstevel@tonic-gate		AVL_SETBALANCE(node, -child_bal);
3707c478bdstevel@tonic-gate		AVL_SETCHILD(node, right);
3717c478bdstevel@tonic-gate		AVL_SETPARENT(node, child);
3737c478bdstevel@tonic-gate		/*
3747c478bdstevel@tonic-gate		 * update the pointer into this subtree
3757c478bdstevel@tonic-gate		 */
3767c478bdstevel@tonic-gate		AVL_SETBALANCE(child, child_bal);
3777c478bdstevel@tonic-gate		AVL_SETCHILD(child, which_child);
3787c478bdstevel@tonic-gate		AVL_SETPARENT(child, parent);
3797c478bdstevel@tonic-gate		if (parent != NULL)
3807c478bdstevel@tonic-gate			parent->avl_child[which_child] = child;
3817c478bdstevel@tonic-gate		else
3827c478bdstevel@tonic-gate			tree->avl_root = child;
3847c478bdstevel@tonic-gate		return (child_bal == 0);
3857c478bdstevel@tonic-gate	}
3877c478bdstevel@tonic-gate	/* BEGIN CSTYLED */
3887c478bdstevel@tonic-gate	/*
3897c478bdstevel@tonic-gate	 * case 2 : When node is left heavy, but child is right heavy we use
3907c478bdstevel@tonic-gate	 * a different rotation.
3917c478bdstevel@tonic-gate	 *
3927c478bdstevel@tonic-gate	 *                   (node b:-2)
3937c478bdstevel@tonic-gate	 *                    /   \
3947c478bdstevel@tonic-gate	 *                   /     \
3957c478bdstevel@tonic-gate	 *                  /       \
3967c478bdstevel@tonic-gate	 *             (child b:+1)
3977c478bdstevel@tonic-gate	 *              /     \
3987c478bdstevel@tonic-gate	 *             /       \
3997c478bdstevel@tonic-gate	 *                   (gchild b: != 0)
4007c478bdstevel@tonic-gate	 *                     /  \
4017c478bdstevel@tonic-gate	 *                    /    \
4027c478bdstevel@tonic-gate	 *                 gleft   gright
4037c478bdstevel@tonic-gate	 *
4047c478bdstevel@tonic-gate	 * becomes:
4057c478bdstevel@tonic-gate	 *
4067c478bdstevel@tonic-gate	 *              (gchild b:0)
4077c478bdstevel@tonic-gate	 *              /       \
4087c478bdstevel@tonic-gate	 *             /         \
4097c478bdstevel@tonic-gate	 *            /           \
4107c478bdstevel@tonic-gate	 *        (child b:?)   (node b:?)
4117c478bdstevel@tonic-gate	 *         /  \          /   \
4127c478bdstevel@tonic-gate	 *        /    \        /     \
4137c478bdstevel@tonic-gate	 *            gleft   gright
4147c478bdstevel@tonic-gate	 *
4157c478bdstevel@tonic-gate	 * computing the new balances is more complicated. As an example:
4167c478bdstevel@tonic-gate	 *	 if gchild was right_heavy, then child is now left heavy
4177c478bdstevel@tonic-gate	 *		else it is balanced
4187c478bdstevel@tonic-gate	 */
4197c478bdstevel@tonic-gate	/* END CSTYLED */
4207c478bdstevel@tonic-gate	gchild = child->avl_child[right];
4217c478bdstevel@tonic-gate	gleft = gchild->avl_child[left];
4227c478bdstevel@tonic-gate	gright = gchild->avl_child[right];
4247c478bdstevel@tonic-gate	/*
4257c478bdstevel@tonic-gate	 * move gright to left child of node and
4267c478bdstevel@tonic-gate	 *
4277c478bdstevel@tonic-gate	 * move gleft to right child of node
4287c478bdstevel@tonic-gate	 */
4297c478bdstevel@tonic-gate	node->avl_child[left] = gright;
4307c478bdstevel@tonic-gate	if (gright != NULL) {
4317c478bdstevel@tonic-gate		AVL_SETPARENT(gright, node);
4327c478bdstevel@tonic-gate		AVL_SETCHILD(gright, left);
4337c478bdstevel@tonic-gate	}
4357c478bdstevel@tonic-gate	child->avl_child[right] = gleft;
4367c478bdstevel@tonic-gate	if (gleft != NULL) {
4377c478bdstevel@tonic-gate		AVL_SETPARENT(gleft, child);
4387c478bdstevel@tonic-gate		AVL_SETCHILD(gleft, right);
4397c478bdstevel@tonic-gate	}
4417c478bdstevel@tonic-gate	/*
4427c478bdstevel@tonic-gate	 * move child to left child of gchild and
4437c478bdstevel@tonic-gate	 *
4447c478bdstevel@tonic-gate	 * move node to right child of gchild and
4457c478bdstevel@tonic-gate	 *
4467c478bdstevel@tonic-gate	 * fixup parent of all this to point to gchild
4477c478bdstevel@tonic-gate	 */
4487c478bdstevel@tonic-gate	balance = AVL_XBALANCE(gchild);
4497c478bdstevel@tonic-gate	gchild->avl_child[left] = child;
4507c478bdstevel@tonic-gate	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));
4517c478bdstevel@tonic-gate	AVL_SETPARENT(child, gchild);
4527c478bdstevel@tonic-gate	AVL_SETCHILD(child, left);
4547c478bdstevel@tonic-gate	gchild->avl_child[right] = node;
4557c478bdstevel@tonic-gate	AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));
4567c478bdstevel@tonic-gate	AVL_SETPARENT(node, gchild);
4577c478bdstevel@tonic-gate	AVL_SETCHILD(node, right);
4597c478bdstevel@tonic-gate	AVL_SETBALANCE(gchild, 0);
4607c478bdstevel@tonic-gate	AVL_SETPARENT(gchild, parent);
4617c478bdstevel@tonic-gate	AVL_SETCHILD(gchild, which_child);
4627c478bdstevel@tonic-gate	if (parent != NULL)
4637c478bdstevel@tonic-gate		parent->avl_child[which_child] = gchild;
4647c478bdstevel@tonic-gate	else
4657c478bdstevel@tonic-gate		tree->avl_root = gchild;
4677c478bdstevel@tonic-gate	return (1);	/* the new tree is always shorter */
4727c478bdstevel@tonic-gate * Insert a new node into an AVL tree at the specified (from avl_find()) place.
4737c478bdstevel@tonic-gate *
4747c478bdstevel@tonic-gate * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
4757c478bdstevel@tonic-gate * searches out to the leaf positions.  The avl_index_t indicates the node
4767c478bdstevel@tonic-gate * which will be the parent of the new node.
4777c478bdstevel@tonic-gate *
4787c478bdstevel@tonic-gate * After the node is inserted, a single rotation further up the tree may
4797c478bdstevel@tonic-gate * be necessary to maintain an acceptable AVL balance.
4807c478bdstevel@tonic-gate */
4827c478bdstevel@tonic-gateavl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
4847c478bdstevel@tonic-gate	avl_node_t *node;
4857c478bdstevel@tonic-gate	avl_node_t *parent = AVL_INDEX2NODE(where);
4867c478bdstevel@tonic-gate	int old_balance;
4877c478bdstevel@tonic-gate	int new_balance;
4887c478bdstevel@tonic-gate	int which_child = AVL_INDEX2CHILD(where);
4897c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
4917c478bdstevel@tonic-gate	ASSERT(tree);
4927c478bdstevel@tonic-gate#ifdef _LP64
4937c478bdstevel@tonic-gate	ASSERT(((uintptr_t)new_data & 0x7) == 0);
4967c478bdstevel@tonic-gate	node = AVL_DATA2NODE(new_data, off);
4987c478bdstevel@tonic-gate	/*
4997c478bdstevel@tonic-gate	 * First, add the node to the tree at the indicated position.
5007c478bdstevel@tonic-gate	 */
5017c478bdstevel@tonic-gate	++tree->avl_numnodes;
5037c478bdstevel@tonic-gate	node->avl_child[0] = NULL;
5047c478bdstevel@tonic-gate	node->avl_child[1] = NULL;
5067c478bdstevel@tonic-gate	AVL_SETCHILD(node, which_child);
5077c478bdstevel@tonic-gate	AVL_SETBALANCE(node, 0);
5087c478bdstevel@tonic-gate	AVL_SETPARENT(node, parent);
5097c478bdstevel@tonic-gate	if (parent != NULL) {
5107c478bdstevel@tonic-gate		ASSERT(parent->avl_child[which_child] == NULL);
5117c478bdstevel@tonic-gate		parent->avl_child[which_child] = node;
5127c478bdstevel@tonic-gate	} else {
5137c478bdstevel@tonic-gate		ASSERT(tree->avl_root == NULL);
5147c478bdstevel@tonic-gate		tree->avl_root = node;
5157c478bdstevel@tonic-gate	}
5167c478bdstevel@tonic-gate	/*
5177c478bdstevel@tonic-gate	 * Now, back up the tree modifying the balance of all nodes above the
5187c478bdstevel@tonic-gate	 * insertion point. If we get to a highly unbalanced ancestor, we
5197c478bdstevel@tonic-gate	 * need to do a rotation.  If we back out of the tree we are done.
5207c478bdstevel@tonic-gate	 * If we brought any subtree into perfect balance (0), we are also done.
5217c478bdstevel@tonic-gate	 */
5227c478bdstevel@tonic-gate	for (;;) {
5237c478bdstevel@tonic-gate		node = parent;
5247c478bdstevel@tonic-gate		if (node == NULL)
5257c478bdstevel@tonic-gate			return;
5277c478bdstevel@tonic-gate		/*
5287c478bdstevel@tonic-gate		 * Compute the new balance
5297c478bdstevel@tonic-gate		 */
5307c478bdstevel@tonic-gate		old_balance = AVL_XBALANCE(node);
5317c478bdstevel@tonic-gate		new_balance = old_balance + avl_child2balance[which_child];
5337c478bdstevel@tonic-gate		/*
5347c478bdstevel@tonic-gate		 * If we introduced equal balance, then we are done immediately
5357c478bdstevel@tonic-gate		 */
5367c478bdstevel@tonic-gate		if (new_balance == 0) {
5377c478bdstevel@tonic-gate			AVL_SETBALANCE(node, 0);
5387c478bdstevel@tonic-gate			return;
5397c478bdstevel@tonic-gate		}
5417c478bdstevel@tonic-gate		/*
5427c478bdstevel@tonic-gate		 * If both old and new are not zero we went
5437c478bdstevel@tonic-gate		 * from -1 to -2 balance, do a rotation.
5447c478bdstevel@tonic-gate		 */
5457c478bdstevel@tonic-gate		if (old_balance != 0)
5467c478bdstevel@tonic-gate			break;
5487c478bdstevel@tonic-gate		AVL_SETBALANCE(node, new_balance);
5497c478bdstevel@tonic-gate		parent = AVL_XPARENT(node);
5507c478bdstevel@tonic-gate		which_child = AVL_XCHILD(node);
5517c478bdstevel@tonic-gate	}
5537c478bdstevel@tonic-gate	/*
5547c478bdstevel@tonic-gate	 * perform a rotation to fix the tree and return
5557c478bdstevel@tonic-gate	 */
5567c478bdstevel@tonic-gate	(void) avl_rotation(tree, node, new_balance);
5607c478bdstevel@tonic-gate * Insert "new_data" in "tree" in the given "direction" either after or
5617c478bdstevel@tonic-gate * before (AVL_AFTER, AVL_BEFORE) the data "here".
5627c478bdstevel@tonic-gate *
5637c478bdstevel@tonic-gate * Insertions can only be done at empty leaf points in the tree, therefore
5647c478bdstevel@tonic-gate * if the given child of the node is already present we move to either
5657c478bdstevel@tonic-gate * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since
5667c478bdstevel@tonic-gate * every other node in the tree is a leaf, this always works.
5677c478bdstevel@tonic-gate *
5687c478bdstevel@tonic-gate * To help developers using this interface, we assert that the new node
5697c478bdstevel@tonic-gate * is correctly ordered at every step of the way in DEBUG kernels.
5707c478bdstevel@tonic-gate */
5737c478bdstevel@tonic-gate	avl_tree_t *tree,
5747c478bdstevel@tonic-gate	void *new_data,
5757c478bdstevel@tonic-gate	void *here,
5767c478bdstevel@tonic-gate	int direction)
5787c478bdstevel@tonic-gate	avl_node_t *node;
5797c478bdstevel@tonic-gate	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
580208e825sommerfe#ifdef DEBUG
581208e825sommerfe	int diff;
5847c478bdstevel@tonic-gate	ASSERT(tree != NULL);
5857c478bdstevel@tonic-gate	ASSERT(new_data != NULL);
5867c478bdstevel@tonic-gate	ASSERT(here != NULL);
5877c478bdstevel@tonic-gate	ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER);
5897c478bdstevel@tonic-gate	/*
5907c478bdstevel@tonic-gate	 * If corresponding child of node is not NULL, go to the neighboring
5917c478bdstevel@tonic-gate	 * node and reverse the insertion direction.
5927c478bdstevel@tonic-gate	 */
5937c478bdstevel@tonic-gate	node = AVL_DATA2NODE(here, tree->avl_offset);
595208e825sommerfe#ifdef DEBUG
596208e825sommerfe	diff = tree->avl_compar(new_data, here);
597208e825sommerfe	ASSERT(-1 <= diff && diff <= 1);
598208e825sommerfe	ASSERT(diff != 0);
599208e825sommerfe	ASSERT(diff > 0 ? child == 1 : child == 0);
6027c478bdstevel@tonic-gate	if (node->avl_child[child] != NULL) {
6037c478bdstevel@tonic-gate		node = node->avl_child[child];
6047c478bdstevel@tonic-gate		child = 1 - child;
6057c478bdstevel@tonic-gate		while (node->avl_child[child] != NULL) {
606208e825sommerfe#ifdef DEBUG
607208e825sommerfe			diff = tree->avl_compar(new_data,
608208e825sommerfe			    AVL_NODE2DATA(node, tree->avl_offset));
609208e825sommerfe			ASSERT(-1 <= diff && diff <= 1);
610208e825sommerfe			ASSERT(diff != 0);
611208e825sommerfe			ASSERT(diff > 0 ? child == 1 : child == 0);
6137c478bdstevel@tonic-gate			node = node->avl_child[child];
6147c478bdstevel@tonic-gate		}
615208e825sommerfe#ifdef DEBUG
616208e825sommerfe		diff = tree->avl_compar(new_data,
617208e825sommerfe		    AVL_NODE2DATA(node, tree->avl_offset));
618208e825sommerfe		ASSERT(-1 <= diff && diff <= 1);
619208e825sommerfe		ASSERT(diff != 0);
620208e825sommerfe		ASSERT(diff > 0 ? child == 1 : child == 0);
6227c478bdstevel@tonic-gate	}
6237c478bdstevel@tonic-gate	ASSERT(node->avl_child[child] == NULL);
6257c478bdstevel@tonic-gate	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
629fa9e406ahrens * Add a new node to an AVL tree.
630fa9e406ahrens */
632fa9e406ahrensavl_add(avl_tree_t *tree, void *new_node)
634fa9e406ahrens	avl_index_t where;
636fa9e406ahrens	/*
637fa9e406ahrens	 * This is unfortunate.  We want to call panic() here, even for
638fa9e406ahrens	 * non-DEBUG kernels.  In userland, however, we can't depend on anything
639faa2b6bJosef 'Jeff' Sipek	 * in libc or else the rtld build process gets confused.
640faa2b6bJosef 'Jeff' Sipek	 * Thankfully, rtld provides us with its own assfail() so we can use
641faa2b6bJosef 'Jeff' Sipek	 * that here.  We use assfail() directly to get a nice error message
642faa2b6bJosef 'Jeff' Sipek	 * in the core - much like what panic() does for crashdumps.
643fa9e406ahrens	 */
644fa9e406ahrens	if (avl_find(tree, new_node, &where) != NULL)
645fa9e406ahrens#ifdef _KERNEL
646fa9e406ahrens		panic("avl_find() succeeded inside avl_add()");
648faa2b6bJosef 'Jeff' Sipek		(void) assfail("avl_find() succeeded inside avl_add()",
649faa2b6bJosef 'Jeff' Sipek		    __FILE__, __LINE__);
651fa9e406ahrens	avl_insert(tree, new_node, where);
6557c478bdstevel@tonic-gate * Delete a node from the AVL tree.  Deletion is similar to insertion, but
6567c478bdstevel@tonic-gate * with 2 complications.
6577c478bdstevel@tonic-gate *
6587c478bdstevel@tonic-gate * First, we may be deleting an interior node. Consider the following subtree:
6597c478bdstevel@tonic-gate *
6607c478bdstevel@tonic-gate *     d           c            c
6617c478bdstevel@tonic-gate *    / \         / \          / \
6627c478bdstevel@tonic-gate *   b   e       b   e        b   e
6637c478bdstevel@tonic-gate *  / \	        / \          /
6647c478bdstevel@tonic-gate * a   c       a            a
6657c478bdstevel@tonic-gate *
6667c478bdstevel@tonic-gate * When we are deleting node (d), we find and bring up an adjacent valued leaf
6677c478bdstevel@tonic-gate * node, say (c), to take the interior node's place. In the code this is
6687c478bdstevel@tonic-gate * handled by temporarily swapping (d) and (c) in the tree and then using
6697c478bdstevel@tonic-gate * common code to delete (d) from the leaf position.
6707c478bdstevel@tonic-gate *
6717c478bdstevel@tonic-gate * Secondly, an interior deletion from a deep tree may require more than one
6727c478bdstevel@tonic-gate * rotation to fix the balance. This is handled by moving up the tree through
6737c478bdstevel@tonic-gate * parents and applying rotations as needed. The return value from
6747c478bdstevel@tonic-gate * avl_rotation() is used to detect when a subtree did not change overall
6757c478bdstevel@tonic-gate * height due to a rotation.
6767c478bdstevel@tonic-gate */
6787c478bdstevel@tonic-gateavl_remove(avl_tree_t *tree, void *data)
6807c478bdstevel@tonic-gate	avl_node_t *delete;
6817c478bdstevel@tonic-gate	avl_node_t *parent;
6827c478bdstevel@tonic-gate	avl_node_t *node;
6837c478bdstevel@tonic-gate	avl_node_t tmp;
6847c478bdstevel@tonic-gate	int old_balance;
6857c478bdstevel@tonic-gate	int new_balance;
6867c478bdstevel@tonic-gate	int left;
6877c478bdstevel@tonic-gate	int right;
6887c478bdstevel@tonic-gate	int which_child;
6897c478bdstevel@tonic-gate	size_t off = tree->avl_offset;
6917c478bdstevel@tonic-gate	ASSERT(tree);
6937c478bdstevel@tonic-gate	delete = AVL_DATA2NODE(data, off);
6957c478bdstevel@tonic-gate	/*
6967c478bdstevel@tonic-gate	 * Deletion is easiest with a node that has at most 1 child.
6977c478bdstevel@tonic-gate	 * We swap a node with 2 children with a sequentially valued
6987c478bdstevel@tonic-gate	 * neighbor node. That node will have at most 1 child. Note this
6997c478bdstevel@tonic-gate	 * has no effect on the ordering of the remaining nodes.
7007c478bdstevel@tonic-gate	 *
7017c478bdstevel@tonic-gate	 * As an optimization, we choose the greater neighbor if the tree
7027c478bdstevel@tonic-gate	 * is right heavy, otherwise the left neighbor. This reduces the
7037c478bdstevel@tonic-gate	 * number of rotations needed.
7047c478bdstevel@tonic-gate	 */
7057c478bdstevel@tonic-gate	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {
7077c478bdstevel@tonic-gate		/*
7087c478bdstevel@tonic-gate		 * choose node to swap from whichever side is taller
7097c478bdstevel@tonic-gate		 */
7107c478bdstevel@tonic-gate		old_balance = AVL_XBALANCE(delete);
7117c478bdstevel@tonic-gate		left = avl_balance2child[old_balance + 1];
7127c478bdstevel@tonic-gate		right = 1 - left;
7147c478bdstevel@tonic-gate		/*
7157c478bdstevel@tonic-gate		 * get to the previous value'd node
7167c478bdstevel@tonic-gate		 * (down 1 left, as far as possible right)
7177c478bdstevel@tonic-gate		 */
7187c478bdstevel@tonic-gate		for (node = delete->avl_child[left];
7197c478bdstevel@tonic-gate		    node->avl_child[right] != NULL;
7207c478bdstevel@tonic-gate		    node = node->avl_child[right])
7217c478bdstevel@tonic-gate			;
7237c478bdstevel@tonic-gate		/*
7247c478bdstevel@tonic-gate		 * create a temp placeholder for 'node'
7257c478bdstevel@tonic-gate		 * move 'node' to delete's spot in the tree
7267c478bdstevel@tonic-gate		 */
7277c478bdstevel@tonic-gate		tmp = *node;
7297c478bdstevel@tonic-gate		*node = *delete;
7307c478bdstevel@tonic-gate		if (node->avl_child[left] == node)
7317c478bdstevel@tonic-gate			node->avl_child[left] = &tmp;
7337c478bdstevel@tonic-gate		parent = AVL_XPARENT(node);
7347c478bdstevel@tonic-gate		if (parent != NULL)
7357c478bdstevel@tonic-gate			parent->avl_child[AVL_XCHILD(node)] = node;
7367c478bdstevel@tonic-gate		else
7377c478bdstevel@tonic-gate			tree->avl_root = node;
7387c478bdstevel@tonic-gate		AVL_SETPARENT(node->avl_child[left], node);
7397c478bdstevel@tonic-gate		AVL_SETPARENT(node->avl_child[right], node);
7417c478bdstevel@tonic-gate		/*
7427c478bdstevel@tonic-gate		 * Put tmp where node used to be (just temporary).
7437c478bdstevel@tonic-gate		 * It always has a parent and at most 1 child.
7447c478bdstevel@tonic-gate		 */
7457c478bdstevel@tonic-gate		delete = &tmp;
7467c478bdstevel@tonic-gate		parent = AVL_XPARENT(delete);
7477c478bdstevel@tonic-gate		parent->avl_child[AVL_XCHILD(delete)] = delete;
7487c478bdstevel@tonic-gate		which_child = (delete->avl_child[1] != 0);
7497c478bdstevel@tonic-gate		if (delete->avl_child[which_child] != NULL)
7507c478bdstevel@tonic-gate			AVL_SETPARENT(delete->avl_child[which_child], delete);
7517c478bdstevel@tonic-gate	}
7547c478bdstevel@tonic-gate	/*
7557c478bdstevel@tonic-gate	 * Here we know "delete" is at least partially a leaf node. It can
7567c478bdstevel@tonic-gate	 * be easily removed from the tree.
7577c478bdstevel@tonic-gate	 */
758208e825sommerfe	ASSERT(tree->avl_numnodes > 0);
7597c478bdstevel@tonic-gate	--tree->avl_numnodes;
7607c478bdstevel@tonic-gate	parent = AVL_XPARENT(delete);
7617c478bdstevel@tonic-gate	which_child = AVL_XCHILD(delete);
7627c478bdstevel@tonic-gate	if (delete->avl_child[0] != NULL)
7637c478bdstevel@tonic-gate		node = delete->avl_child[0];
7647c478bdstevel@tonic-gate	else
7657c478bdstevel@tonic-gate		node = delete->avl_child[1];
7677c478bdstevel@tonic-gate	/*
7687c478bdstevel@tonic-gate	 * Connect parent directly to node (leaving out delete).
7697c478bdstevel@tonic-gate	 */
7707c478bdstevel@tonic-gate	if (node != NULL) {
7717c478bdstevel@tonic-gate		AVL_SETPARENT(node, parent);
7727c478bdstevel@tonic-gate		AVL_SETCHILD(node, which_child);
7737c478bdstevel@tonic-gate	}
7747c478bdstevel@tonic-gate	if (parent == NULL) {
7757c478bdstevel@tonic-gate		tree->avl_root = node;
7767c478bdstevel@tonic-gate		return;
7777c478bdstevel@tonic-gate	}
7787c478bdstevel@tonic-gate	parent->avl_child[which_child] = node;
7817c478bdstevel@tonic-gate	/*
7827c478bdstevel@tonic-gate	 * Since the subtree is now shorter, begin adjusting parent balances
7837c478bdstevel@tonic-gate	 * and performing any needed rotations.
7847c478bdstevel@tonic-gate	 */
7857c478bdstevel@tonic-gate	do {
7877c478bdstevel@tonic-gate		/*
7887c478bdstevel@tonic-gate		 * Move up the tree and adjust the balance
7897c478bdstevel@tonic-gate		 *
7907c478bdstevel@tonic-gate		 * Capture the parent and which_child values for the next
7917c478bdstevel@tonic-gate		 * iteration before any rotations occur.
7927c478bdstevel@tonic-gate		 */
7937c478bdstevel@tonic-gate		node = parent;
7947c478bdstevel@tonic-gate		old_balance = AVL_XBALANCE(node);
7957c478bdstevel@tonic-gate		new_balance = old_balance - avl_child2balance[which_child];
7967c478bdstevel@tonic-gate		parent = AVL_XPARENT(node);
7977c478bdstevel@tonic-gate		which_child = AVL_XCHILD(node);
7997c478bdstevel@tonic-gate		/*
8007c478bdstevel@tonic-gate		 * If a node was in perfect balance but isn't anymore then
8017c478bdstevel@tonic-gate		 * we can stop, since the height didn't change above this point
8027c478bdstevel@tonic-gate		 * due to a deletion.
8037c478bdstevel@tonic-gate		 */
8047c478bdstevel@tonic-gate		if (old_balance == 0) {
8057c478bdstevel@tonic-gate			AVL_SETBALANCE(node, new_balance);
8067c478bdstevel@tonic-gate			break;
8077c478bdstevel@tonic-gate		}
8097c478bdstevel@tonic-gate		/*
8107c478bdstevel@tonic-gate		 * If the new balance is zero, we don't need to rotate
8117c478bdstevel@tonic-gate		 * else
8127c478bdstevel@tonic-gate		 * need a rotation to fix the balance.
8137c478bdstevel@tonic-gate		 * If the rotation doesn't change the height
8147c478bdstevel@tonic-gate		 * of the sub-tree we have finished adjusting.
8157c478bdstevel@tonic-gate		 */
8167c478bdstevel@tonic-gate		if (new_balance == 0)
8177c478bdstevel@tonic-gate			AVL_SETBALANCE(node, new_balance);
8187c478bdstevel@tonic-gate		else if (!avl_rotation(tree, node, new_balance))
8197c478bdstevel@tonic-gate			break;
8207c478bdstevel@tonic-gate	} while (parent != NULL);
823b5fca8ftomee#define	AVL_REINSERT(tree, obj)		\
824b5fca8ftomee	avl_remove((tree), (obj));	\
825b5fca8ftomee	avl_add((tree), (obj))
828b5fca8ftomeeavl_update_lt(avl_tree_t *t, void *obj)
830b5fca8ftomee	void *neighbor;
832b5fca8ftomee	ASSERT(((neighbor = AVL_NEXT(t, obj)) == NULL) ||
833b5fca8ftomee	    (t->avl_compar(obj, neighbor) <= 0));
835b5fca8ftomee	neighbor = AVL_PREV(t, obj);
836b5fca8ftomee	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
837b5fca8ftomee		AVL_REINSERT(t, obj);
838b5fca8ftomee		return (B_TRUE);
839b5fca8ftomee	}
841b5fca8ftomee	return (B_FALSE);
845b5fca8ftomeeavl_update_gt(avl_tree_t *t, void *obj)
847b5fca8ftomee	void *neighbor;
849b5fca8ftomee	ASSERT(((neighbor = AVL_PREV(t, obj)) == NULL) ||
850b5fca8ftomee	    (t->avl_compar(obj, neighbor) >= 0));
852b5fca8ftomee	neighbor = AVL_NEXT(t, obj);
853b5fca8ftomee	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
854b5fca8ftomee		AVL_REINSERT(t, obj);
855b5fca8ftomee		return (B_TRUE);
856b5fca8ftomee	}
858b5fca8ftomee	return (B_FALSE);
862b5fca8ftomeeavl_update(avl_tree_t *t, void *obj)
864b5fca8ftomee	void *neighbor;
866b5fca8ftomee	neighbor = AVL_PREV(t, obj);
867b5fca8ftomee	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
868b5fca8ftomee		AVL_REINSERT(t, obj);
869b5fca8ftomee		return (B_TRUE);
870b5fca8ftomee	}
872b5fca8ftomee	neighbor = AVL_NEXT(t, obj);
873b5fca8ftomee	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
874b5fca8ftomee		AVL_REINSERT(t, obj);
875b5fca8ftomee		return (B_TRUE);
876b5fca8ftomee	}
878b5fca8ftomee	return (B_FALSE);
8810f6d88aAlex Reecevoid
8820f6d88aAlex Reeceavl_swap(avl_tree_t *tree1, avl_tree_t *tree2)
8830f6d88aAlex Reece{
8840f6d88aAlex Reece	avl_node_t *temp_node;
8850f6d88aAlex Reece	ulong_t temp_numnodes;
8860f6d88aAlex Reece
8870f6d88aAlex Reece	ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar);
8880f6d88aAlex Reece	ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset);
8890f6d88aAlex Reece	ASSERT3U(tree1->avl_size, ==, tree2->avl_size);
8900f6d88aAlex Reece
8910f6d88aAlex Reece	temp_node = tree1->avl_root;
8920f6d88aAlex Reece	temp_numnodes = tree1->avl_numnodes;
8930f6d88aAlex Reece	tree1->avl_root = tree2->avl_root;
8940f6d88aAlex Reece	tree1->avl_numnodes = tree2->avl_numnodes;
8950f6d88aAlex Reece	tree2->avl_root = temp_node;
8960f6d88aAlex Reece	tree2->avl_numnodes = temp_numnodes;
8970f6d88aAlex Reece}
8980f6d88aAlex Reece
9007c478bdstevel@tonic-gate * initialize a new AVL tree
9017c478bdstevel@tonic-gate */
9037c478bdstevel@tonic-gateavl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
9047c478bdstevel@tonic-gate    size_t size, size_t offset)
9067c478bdstevel@tonic-gate	ASSERT(tree);
9077c478bdstevel@tonic-gate	ASSERT(compar);
9087c478bdstevel@tonic-gate	ASSERT(size > 0);
9097c478bdstevel@tonic-gate	ASSERT(size >= offset + sizeof (avl_node_t));
9107c478bdstevel@tonic-gate#ifdef _LP64
9117c478bdstevel@tonic-gate	ASSERT((offset & 0x7) == 0);
9147c478bdstevel@tonic-gate	tree->avl_compar = compar;
9157c478bdstevel@tonic-gate	tree->avl_root = NULL;
9167c478bdstevel@tonic-gate	tree->avl_numnodes = 0;
9177c478bdstevel@tonic-gate	tree->avl_size = size;
9187c478bdstevel@tonic-gate	tree->avl_offset = offset;
9227c478bdstevel@tonic-gate * Delete a tree.
9237c478bdstevel@tonic-gate */
9247c478bdstevel@tonic-gate/* ARGSUSED */
9267c478bdstevel@tonic-gateavl_destroy(avl_tree_t *tree)
9287c478bdstevel@tonic-gate	ASSERT(tree);
9297c478bdstevel@tonic-gate	ASSERT(tree->avl_numnodes == 0);
9307c478bdstevel@tonic-gate	ASSERT(tree->avl_root == NULL);
9357c478bdstevel@tonic-gate * Return the number of nodes in an AVL tree.
9367c478bdstevel@tonic-gate */
9387c478bdstevel@tonic-gateavl_numnodes(avl_tree_t *tree)
9407c478bdstevel@tonic-gate	ASSERT(tree);
9417c478bdstevel@tonic-gate	return (tree->avl_numnodes);
945b5fca8ftomeeavl_is_empty(avl_tree_t *tree)
947b5fca8ftomee	ASSERT(tree);
948b5fca8ftomee	return (tree->avl_numnodes == 0);
9517c478bdstevel@tonic-gate#define	CHILDBIT	(1L)
9547c478bdstevel@tonic-gate * Post-order tree walk used to visit all tree nodes and destroy the tree
95586f617eEli Rosenthal * in post order. This is used for removing all the nodes from a tree without
95686f617eEli Rosenthal * paying any cost for rebalancing it.
9577c478bdstevel@tonic-gate *
9587c478bdstevel@tonic-gate * example:
9597c478bdstevel@tonic-gate *
9607c478bdstevel@tonic-gate *	void *cookie = NULL;
9617c478bdstevel@tonic-gate *	my_data_t *node;
9627c478bdstevel@tonic-gate *
9637c478bdstevel@tonic-gate *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
9647c478bdstevel@tonic-gate *		free(node);
9657c478bdstevel@tonic-gate *	avl_destroy(tree);
9667c478bdstevel@tonic-gate *
9677c478bdstevel@tonic-gate * The cookie is really an avl_node_t to the current node's parent and
9687c478bdstevel@tonic-gate * an indication of which child you looked at last.
9697c478bdstevel@tonic-gate *
9707c478bdstevel@tonic-gate * On input, a cookie value of CHILDBIT indicates the tree is done.
9717c478bdstevel@tonic-gate */
9727c478bdstevel@tonic-gatevoid *
9737c478bdstevel@tonic-gateavl_destroy_nodes(avl_tree_t *tree, void **cookie)
9757c478bdstevel@tonic-gate	avl_node_t	*node;
9767c478bdstevel@tonic-gate	avl_node_t	*parent;
9777c478bdstevel@tonic-gate	int		child;
9787c478bdstevel@tonic-gate	void		*first;
9797c478bdstevel@tonic-gate	size_t		off = tree->avl_offset;
9817c478bdstevel@tonic-gate	/*
9827c478bdstevel@tonic-gate	 * Initial calls go to the first node or it's right descendant.
9837c478bdstevel@tonic-gate	 */
9847c478bdstevel@tonic-gate	if (*cookie == NULL) {
9857c478bdstevel@tonic-gate		first = avl_first(tree);
9877c478bdstevel@tonic-gate		/*
9887c478bdstevel@tonic-gate		 * deal with an empty tree
9897c478bdstevel@tonic-gate		 */
9907c478bdstevel@tonic-gate		if (first == NULL) {
9917c478bdstevel@tonic-gate			*cookie = (void *)CHILDBIT;
9927c478bdstevel@tonic-gate			return (NULL);
9937c478bdstevel@tonic-gate		}
9957c478bdstevel@tonic-gate		node = AVL_DATA2NODE(first, off);
9967c478bdstevel@tonic-gate		parent = AVL_XPARENT(node);
9977c478bdstevel@tonic-gate		goto check_right_side;
9987c478bdstevel@tonic-gate	}
10007c478bdstevel@tonic-gate	/*
10017c478bdstevel@tonic-gate	 * If there is no parent to return to we are done.
10027c478bdstevel@tonic-gate	 */
10037c478bdstevel@tonic-gate	parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT);
10047c478bdstevel@tonic-gate	if (parent == NULL) {
10057c478bdstevel@tonic-gate		if (tree->avl_root != NULL) {
10067c478bdstevel@tonic-gate			ASSERT(tree->avl_numnodes == 1);
10077c478bdstevel@tonic-gate			tree->avl_root = NULL;
10087c478bdstevel@tonic-gate			tree->avl_numnodes = 0;
10097c478bdstevel@tonic-gate		}
10107c478bdstevel@tonic-gate		return (NULL);
10117c478bdstevel@tonic-gate	}
10137c478bdstevel@tonic-gate	/*
10147c478bdstevel@tonic-gate	 * Remove the child pointer we just visited from the parent and tree.
10157c478bdstevel@tonic-gate	 */
10167c478bdstevel@tonic-gate	child = (uintptr_t)(*cookie) & CHILDBIT;
10177c478bdstevel@tonic-gate	parent->avl_child[child] = NULL;
10187c478bdstevel@tonic-gate	ASSERT(tree->avl_numnodes > 1);
10197c478bdstevel@tonic-gate	--tree->avl_numnodes;
10217c478bdstevel@tonic-gate	/*
10227c478bdstevel@tonic-gate	 * If we just did a right child or there isn't one, go up to parent.
10237c478bdstevel@tonic-gate	 */
10247c478bdstevel@tonic-gate	if (child == 1 || parent->avl_child[1] == NULL) {
10257c478bdstevel@tonic-gate		node = parent;
10267c478bdstevel@tonic-gate		parent = AVL_XPARENT(parent);
10277c478bdstevel@tonic-gate		goto done;
10287c478bdstevel@tonic-gate	}
10307c478bdstevel@tonic-gate	/*
10317c478bdstevel@tonic-gate	 * Do parent's right child, then leftmost descendent.
10327c478bdstevel@tonic-gate	 */
10337c478bdstevel@tonic-gate	node = parent->avl_child[1];
10347c478bdstevel@tonic-gate	while (node->avl_child[0] != NULL) {
10357c478bdstevel@tonic-gate		parent = node;
10367c478bdstevel@tonic-gate		node = node->avl_child[0];
10377c478bdstevel@tonic-gate	}
10397c478bdstevel@tonic-gate	/*
10407c478bdstevel@tonic-gate	 * If here, we moved to a left child. It may have one
10417c478bdstevel@tonic-gate	 * child on the right (when balance == +1).
10427c478bdstevel@tonic-gate	 */
10447c478bdstevel@tonic-gate	if (node->avl_child[1] != NULL) {
10457c478bdstevel@tonic-gate		ASSERT(AVL_XBALANCE(node) == 1);
10467c478bdstevel@tonic-gate		parent = node;
10477c478bdstevel@tonic-gate		node = node->avl_child[1];
10487c478bdstevel@tonic-gate		ASSERT(node->avl_child[0] == NULL &&
10497c478bdstevel@tonic-gate		    node->avl_child[1] == NULL);
10507c478bdstevel@tonic-gate	} else {
10517c478bdstevel@tonic-gate		ASSERT(AVL_XBALANCE(node) <= 0);
10527c478bdstevel@tonic-gate	}
10557c478bdstevel@tonic-gate	if (parent == NULL) {
10567c478bdstevel@tonic-gate		*cookie = (void *)CHILDBIT;
10577c478bdstevel@tonic-gate		ASSERT(node == tree->avl_root);
10587c478bdstevel@tonic-gate	} else {
10597c478bdstevel@tonic-gate		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));
10607c478bdstevel@tonic-gate	}
10627c478bdstevel@tonic-gate	return (AVL_NODE2DATA(node, off));