xref: /illumos-gate/usr/src/common/avl/avl.c (revision fa9e4066f08beec538e775443c5be79dd423fcab)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate  * with the License.
87c478bd9Sstevel@tonic-gate  *
97c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate  * and limitations under the License.
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate  *
207c478bd9Sstevel@tonic-gate  * CDDL HEADER END
217c478bd9Sstevel@tonic-gate  */
227c478bd9Sstevel@tonic-gate /*
23*fa9e4066Sahrens  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
247c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate  */
267c478bd9Sstevel@tonic-gate 
277c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
287c478bd9Sstevel@tonic-gate 
297c478bd9Sstevel@tonic-gate 
307c478bd9Sstevel@tonic-gate /*
317c478bd9Sstevel@tonic-gate  * AVL - generic AVL tree implementation for kernel use
327c478bd9Sstevel@tonic-gate  *
337c478bd9Sstevel@tonic-gate  * A complete description of AVL trees can be found in many CS textbooks.
347c478bd9Sstevel@tonic-gate  *
357c478bd9Sstevel@tonic-gate  * Here is a very brief overview. An AVL tree is a binary search tree that is
367c478bd9Sstevel@tonic-gate  * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
377c478bd9Sstevel@tonic-gate  * any given node, the left and right subtrees are allowed to differ in height
387c478bd9Sstevel@tonic-gate  * by at most 1 level.
397c478bd9Sstevel@tonic-gate  *
407c478bd9Sstevel@tonic-gate  * This relaxation from a perfectly balanced binary tree allows doing
417c478bd9Sstevel@tonic-gate  * insertion and deletion relatively efficiently. Searching the tree is
427c478bd9Sstevel@tonic-gate  * still a fast operation, roughly O(log(N)).
437c478bd9Sstevel@tonic-gate  *
447c478bd9Sstevel@tonic-gate  * The key to insertion and deletion is a set of tree maniuplations called
457c478bd9Sstevel@tonic-gate  * rotations, which bring unbalanced subtrees back into the semi-balanced state.
467c478bd9Sstevel@tonic-gate  *
477c478bd9Sstevel@tonic-gate  * This implementation of AVL trees has the following peculiarities:
487c478bd9Sstevel@tonic-gate  *
497c478bd9Sstevel@tonic-gate  *	- The AVL specific data structures are physically embedded as fields
507c478bd9Sstevel@tonic-gate  *	  in the "using" data structures.  To maintain generality the code
517c478bd9Sstevel@tonic-gate  *	  must constantly translate between "avl_node_t *" and containing
527c478bd9Sstevel@tonic-gate  *	  data structure "void *"s by adding/subracting the avl_offset.
537c478bd9Sstevel@tonic-gate  *
547c478bd9Sstevel@tonic-gate  *	- Since the AVL data is always embedded in other structures, there is
557c478bd9Sstevel@tonic-gate  *	  no locking or memory allocation in the AVL routines. This must be
567c478bd9Sstevel@tonic-gate  *	  provided for by the enclosing data structure's semantics. Typically,
57*fa9e4066Sahrens  *	  avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
587c478bd9Sstevel@tonic-gate  *	  exclusive write lock. Other operations require a read lock.
597c478bd9Sstevel@tonic-gate  *
607c478bd9Sstevel@tonic-gate  *      - The implementation uses iteration instead of explicit recursion,
617c478bd9Sstevel@tonic-gate  *	  since it is intended to run on limited size kernel stacks. Since
627c478bd9Sstevel@tonic-gate  *	  there is no recursion stack present to move "up" in the tree,
637c478bd9Sstevel@tonic-gate  *	  there is an explicit "parent" link in the avl_node_t.
647c478bd9Sstevel@tonic-gate  *
657c478bd9Sstevel@tonic-gate  *      - The left/right children pointers of a node are in an array.
667c478bd9Sstevel@tonic-gate  *	  In the code, variables (instead of constants) are used to represent
677c478bd9Sstevel@tonic-gate  *	  left and right indices.  The implementation is written as if it only
687c478bd9Sstevel@tonic-gate  *	  dealt with left handed manipulations.  By changing the value assigned
697c478bd9Sstevel@tonic-gate  *	  to "left", the code also works for right handed trees.  The
707c478bd9Sstevel@tonic-gate  *	  following variables/terms are frequently used:
717c478bd9Sstevel@tonic-gate  *
727c478bd9Sstevel@tonic-gate  *		int left;	// 0 when dealing with left children,
737c478bd9Sstevel@tonic-gate  *				// 1 for dealing with right children
747c478bd9Sstevel@tonic-gate  *
757c478bd9Sstevel@tonic-gate  *		int left_heavy;	// -1 when left subtree is taller at some node,
767c478bd9Sstevel@tonic-gate  *				// +1 when right subtree is taller
777c478bd9Sstevel@tonic-gate  *
787c478bd9Sstevel@tonic-gate  *		int right;	// will be the opposite of left (0 or 1)
797c478bd9Sstevel@tonic-gate  *		int right_heavy;// will be the opposite of left_heavy (-1 or 1)
807c478bd9Sstevel@tonic-gate  *
817c478bd9Sstevel@tonic-gate  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
827c478bd9Sstevel@tonic-gate  *
837c478bd9Sstevel@tonic-gate  *	  Though it is a little more confusing to read the code, the approach
847c478bd9Sstevel@tonic-gate  *	  allows using half as much code (and hence cache footprint) for tree
857c478bd9Sstevel@tonic-gate  *	  manipulations and eliminates many conditional branches.
867c478bd9Sstevel@tonic-gate  *
877c478bd9Sstevel@tonic-gate  *	- The avl_index_t is an opaque "cookie" used to find nodes at or
887c478bd9Sstevel@tonic-gate  *	  adjacent to where a new value would be inserted in the tree. The value
897c478bd9Sstevel@tonic-gate  *	  is a modified "avl_node_t *".  The bottom bit (normally 0 for a
907c478bd9Sstevel@tonic-gate  *	  pointer) is set to indicate if that the new node has a value greater
917c478bd9Sstevel@tonic-gate  *	  than the value of the indicated "avl_node_t *".
927c478bd9Sstevel@tonic-gate  */
937c478bd9Sstevel@tonic-gate 
947c478bd9Sstevel@tonic-gate #include <sys/types.h>
957c478bd9Sstevel@tonic-gate #include <sys/param.h>
967c478bd9Sstevel@tonic-gate #include <sys/debug.h>
977c478bd9Sstevel@tonic-gate #include <sys/avl.h>
98*fa9e4066Sahrens #include <sys/cmn_err.h>
997c478bd9Sstevel@tonic-gate 
1007c478bd9Sstevel@tonic-gate /*
1017c478bd9Sstevel@tonic-gate  * Small arrays to translate between balance (or diff) values and child indeces.
1027c478bd9Sstevel@tonic-gate  *
1037c478bd9Sstevel@tonic-gate  * Code that deals with binary tree data structures will randomly use
1047c478bd9Sstevel@tonic-gate  * left and right children when examining a tree.  C "if()" statements
1057c478bd9Sstevel@tonic-gate  * which evaluate randomly suffer from very poor hardware branch prediction.
1067c478bd9Sstevel@tonic-gate  * In this code we avoid some of the branch mispredictions by using the
1077c478bd9Sstevel@tonic-gate  * following translation arrays. They replace random branches with an
1087c478bd9Sstevel@tonic-gate  * additional memory reference. Since the translation arrays are both very
1097c478bd9Sstevel@tonic-gate  * small the data should remain efficiently in cache.
1107c478bd9Sstevel@tonic-gate  */
1117c478bd9Sstevel@tonic-gate static const int  avl_child2balance[2]	= {-1, 1};
1127c478bd9Sstevel@tonic-gate static const int  avl_balance2child[]	= {0, 0, 1};
1137c478bd9Sstevel@tonic-gate 
1147c478bd9Sstevel@tonic-gate 
1157c478bd9Sstevel@tonic-gate /*
1167c478bd9Sstevel@tonic-gate  * Walk from one node to the previous valued node (ie. an infix walk
1177c478bd9Sstevel@tonic-gate  * towards the left). At any given node we do one of 2 things:
1187c478bd9Sstevel@tonic-gate  *
1197c478bd9Sstevel@tonic-gate  * - If there is a left child, go to it, then to it's rightmost descendant.
1207c478bd9Sstevel@tonic-gate  *
1217c478bd9Sstevel@tonic-gate  * - otherwise we return thru parent nodes until we've come from a right child.
1227c478bd9Sstevel@tonic-gate  *
1237c478bd9Sstevel@tonic-gate  * Return Value:
1247c478bd9Sstevel@tonic-gate  * NULL - if at the end of the nodes
1257c478bd9Sstevel@tonic-gate  * otherwise next node
1267c478bd9Sstevel@tonic-gate  */
1277c478bd9Sstevel@tonic-gate void *
1287c478bd9Sstevel@tonic-gate avl_walk(avl_tree_t *tree, void	*oldnode, int left)
1297c478bd9Sstevel@tonic-gate {
1307c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
1317c478bd9Sstevel@tonic-gate 	avl_node_t *node = AVL_DATA2NODE(oldnode, off);
1327c478bd9Sstevel@tonic-gate 	int right = 1 - left;
1337c478bd9Sstevel@tonic-gate 	int was_child;
1347c478bd9Sstevel@tonic-gate 
1357c478bd9Sstevel@tonic-gate 
1367c478bd9Sstevel@tonic-gate 	/*
1377c478bd9Sstevel@tonic-gate 	 * nowhere to walk to if tree is empty
1387c478bd9Sstevel@tonic-gate 	 */
1397c478bd9Sstevel@tonic-gate 	if (node == NULL)
1407c478bd9Sstevel@tonic-gate 		return (NULL);
1417c478bd9Sstevel@tonic-gate 
1427c478bd9Sstevel@tonic-gate 	/*
1437c478bd9Sstevel@tonic-gate 	 * Visit the previous valued node. There are two possibilities:
1447c478bd9Sstevel@tonic-gate 	 *
1457c478bd9Sstevel@tonic-gate 	 * If this node has a left child, go down one left, then all
1467c478bd9Sstevel@tonic-gate 	 * the way right.
1477c478bd9Sstevel@tonic-gate 	 */
1487c478bd9Sstevel@tonic-gate 	if (node->avl_child[left] != NULL) {
1497c478bd9Sstevel@tonic-gate 		for (node = node->avl_child[left];
1507c478bd9Sstevel@tonic-gate 		    node->avl_child[right] != NULL;
1517c478bd9Sstevel@tonic-gate 		    node = node->avl_child[right])
1527c478bd9Sstevel@tonic-gate 			;
1537c478bd9Sstevel@tonic-gate 	/*
1547c478bd9Sstevel@tonic-gate 	 * Otherwise, return thru left children as far as we can.
1557c478bd9Sstevel@tonic-gate 	 */
1567c478bd9Sstevel@tonic-gate 	} else {
1577c478bd9Sstevel@tonic-gate 		for (;;) {
1587c478bd9Sstevel@tonic-gate 			was_child = AVL_XCHILD(node);
1597c478bd9Sstevel@tonic-gate 			node = AVL_XPARENT(node);
1607c478bd9Sstevel@tonic-gate 			if (node == NULL)
1617c478bd9Sstevel@tonic-gate 				return (NULL);
1627c478bd9Sstevel@tonic-gate 			if (was_child == right)
1637c478bd9Sstevel@tonic-gate 				break;
1647c478bd9Sstevel@tonic-gate 		}
1657c478bd9Sstevel@tonic-gate 	}
1667c478bd9Sstevel@tonic-gate 
1677c478bd9Sstevel@tonic-gate 	return (AVL_NODE2DATA(node, off));
1687c478bd9Sstevel@tonic-gate }
1697c478bd9Sstevel@tonic-gate 
1707c478bd9Sstevel@tonic-gate /*
1717c478bd9Sstevel@tonic-gate  * Return the lowest valued node in a tree or NULL.
1727c478bd9Sstevel@tonic-gate  * (leftmost child from root of tree)
1737c478bd9Sstevel@tonic-gate  */
1747c478bd9Sstevel@tonic-gate void *
1757c478bd9Sstevel@tonic-gate avl_first(avl_tree_t *tree)
1767c478bd9Sstevel@tonic-gate {
1777c478bd9Sstevel@tonic-gate 	avl_node_t *node;
1787c478bd9Sstevel@tonic-gate 	avl_node_t *prev = NULL;
1797c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
1807c478bd9Sstevel@tonic-gate 
1817c478bd9Sstevel@tonic-gate 	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
1827c478bd9Sstevel@tonic-gate 		prev = node;
1837c478bd9Sstevel@tonic-gate 
1847c478bd9Sstevel@tonic-gate 	if (prev != NULL)
1857c478bd9Sstevel@tonic-gate 		return (AVL_NODE2DATA(prev, off));
1867c478bd9Sstevel@tonic-gate 	return (NULL);
1877c478bd9Sstevel@tonic-gate }
1887c478bd9Sstevel@tonic-gate 
1897c478bd9Sstevel@tonic-gate /*
1907c478bd9Sstevel@tonic-gate  * Return the highest valued node in a tree or NULL.
1917c478bd9Sstevel@tonic-gate  * (rightmost child from root of tree)
1927c478bd9Sstevel@tonic-gate  */
1937c478bd9Sstevel@tonic-gate void *
1947c478bd9Sstevel@tonic-gate avl_last(avl_tree_t *tree)
1957c478bd9Sstevel@tonic-gate {
1967c478bd9Sstevel@tonic-gate 	avl_node_t *node;
1977c478bd9Sstevel@tonic-gate 	avl_node_t *prev = NULL;
1987c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
1997c478bd9Sstevel@tonic-gate 
2007c478bd9Sstevel@tonic-gate 	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
2017c478bd9Sstevel@tonic-gate 		prev = node;
2027c478bd9Sstevel@tonic-gate 
2037c478bd9Sstevel@tonic-gate 	if (prev != NULL)
2047c478bd9Sstevel@tonic-gate 		return (AVL_NODE2DATA(prev, off));
2057c478bd9Sstevel@tonic-gate 	return (NULL);
2067c478bd9Sstevel@tonic-gate }
2077c478bd9Sstevel@tonic-gate 
2087c478bd9Sstevel@tonic-gate /*
2097c478bd9Sstevel@tonic-gate  * Access the node immediately before or after an insertion point.
2107c478bd9Sstevel@tonic-gate  *
2117c478bd9Sstevel@tonic-gate  * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
2127c478bd9Sstevel@tonic-gate  *
2137c478bd9Sstevel@tonic-gate  * Return value:
2147c478bd9Sstevel@tonic-gate  *	NULL: no node in the given direction
2157c478bd9Sstevel@tonic-gate  *	"void *"  of the found tree node
2167c478bd9Sstevel@tonic-gate  */
2177c478bd9Sstevel@tonic-gate void *
2187c478bd9Sstevel@tonic-gate avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
2197c478bd9Sstevel@tonic-gate {
2207c478bd9Sstevel@tonic-gate 	int child = AVL_INDEX2CHILD(where);
2217c478bd9Sstevel@tonic-gate 	avl_node_t *node = AVL_INDEX2NODE(where);
2227c478bd9Sstevel@tonic-gate 	void *data;
2237c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
2247c478bd9Sstevel@tonic-gate 
2257c478bd9Sstevel@tonic-gate 	if (node == NULL) {
2267c478bd9Sstevel@tonic-gate 		ASSERT(tree->avl_root == NULL);
2277c478bd9Sstevel@tonic-gate 		return (NULL);
2287c478bd9Sstevel@tonic-gate 	}
2297c478bd9Sstevel@tonic-gate 	data = AVL_NODE2DATA(node, off);
2307c478bd9Sstevel@tonic-gate 	if (child != direction)
2317c478bd9Sstevel@tonic-gate 		return (data);
2327c478bd9Sstevel@tonic-gate 
2337c478bd9Sstevel@tonic-gate 	return (avl_walk(tree, data, direction));
2347c478bd9Sstevel@tonic-gate }
2357c478bd9Sstevel@tonic-gate 
2367c478bd9Sstevel@tonic-gate 
2377c478bd9Sstevel@tonic-gate /*
2387c478bd9Sstevel@tonic-gate  * Search for the node which contains "value".  The algorithm is a
2397c478bd9Sstevel@tonic-gate  * simple binary tree search.
2407c478bd9Sstevel@tonic-gate  *
2417c478bd9Sstevel@tonic-gate  * return value:
2427c478bd9Sstevel@tonic-gate  *	NULL: the value is not in the AVL tree
2437c478bd9Sstevel@tonic-gate  *		*where (if not NULL)  is set to indicate the insertion point
2447c478bd9Sstevel@tonic-gate  *	"void *"  of the found tree node
2457c478bd9Sstevel@tonic-gate  */
2467c478bd9Sstevel@tonic-gate void *
2477c478bd9Sstevel@tonic-gate avl_find(avl_tree_t *tree, void *value, avl_index_t *where)
2487c478bd9Sstevel@tonic-gate {
2497c478bd9Sstevel@tonic-gate 	avl_node_t *node;
2507c478bd9Sstevel@tonic-gate 	avl_node_t *prev = NULL;
2517c478bd9Sstevel@tonic-gate 	int child = 0;
2527c478bd9Sstevel@tonic-gate 	int diff;
2537c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
2547c478bd9Sstevel@tonic-gate 
2557c478bd9Sstevel@tonic-gate 	for (node = tree->avl_root; node != NULL;
2567c478bd9Sstevel@tonic-gate 	    node = node->avl_child[child]) {
2577c478bd9Sstevel@tonic-gate 
2587c478bd9Sstevel@tonic-gate 		prev = node;
2597c478bd9Sstevel@tonic-gate 
2607c478bd9Sstevel@tonic-gate 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
2617c478bd9Sstevel@tonic-gate 		ASSERT(-1 <= diff && diff <= 1);
2627c478bd9Sstevel@tonic-gate 		if (diff == 0) {
2637c478bd9Sstevel@tonic-gate #ifdef DEBUG
2647c478bd9Sstevel@tonic-gate 			if (where != NULL)
2657c478bd9Sstevel@tonic-gate 				*where = NULL;
2667c478bd9Sstevel@tonic-gate #endif
2677c478bd9Sstevel@tonic-gate 			return (AVL_NODE2DATA(node, off));
2687c478bd9Sstevel@tonic-gate 		}
2697c478bd9Sstevel@tonic-gate 		child = avl_balance2child[1 + diff];
2707c478bd9Sstevel@tonic-gate 
2717c478bd9Sstevel@tonic-gate 	}
2727c478bd9Sstevel@tonic-gate 
2737c478bd9Sstevel@tonic-gate 	if (where != NULL)
2747c478bd9Sstevel@tonic-gate 		*where = AVL_MKINDEX(prev, child);
2757c478bd9Sstevel@tonic-gate 
2767c478bd9Sstevel@tonic-gate 	return (NULL);
2777c478bd9Sstevel@tonic-gate }
2787c478bd9Sstevel@tonic-gate 
2797c478bd9Sstevel@tonic-gate 
2807c478bd9Sstevel@tonic-gate /*
2817c478bd9Sstevel@tonic-gate  * Perform a rotation to restore balance at the subtree given by depth.
2827c478bd9Sstevel@tonic-gate  *
2837c478bd9Sstevel@tonic-gate  * This routine is used by both insertion and deletion. The return value
2847c478bd9Sstevel@tonic-gate  * indicates:
2857c478bd9Sstevel@tonic-gate  *	 0 : subtree did not change height
2867c478bd9Sstevel@tonic-gate  *	!0 : subtree was reduced in height
2877c478bd9Sstevel@tonic-gate  *
2887c478bd9Sstevel@tonic-gate  * The code is written as if handling left rotations, right rotations are
2897c478bd9Sstevel@tonic-gate  * symmetric and handled by swapping values of variables right/left[_heavy]
2907c478bd9Sstevel@tonic-gate  *
2917c478bd9Sstevel@tonic-gate  * On input balance is the "new" balance at "node". This value is either
2927c478bd9Sstevel@tonic-gate  * -2 or +2.
2937c478bd9Sstevel@tonic-gate  */
2947c478bd9Sstevel@tonic-gate static int
2957c478bd9Sstevel@tonic-gate avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
2967c478bd9Sstevel@tonic-gate {
2977c478bd9Sstevel@tonic-gate 	int left = !(balance < 0);	/* when balance = -2, left will be 0 */
2987c478bd9Sstevel@tonic-gate 	int right = 1 - left;
2997c478bd9Sstevel@tonic-gate 	int left_heavy = balance >> 1;
3007c478bd9Sstevel@tonic-gate 	int right_heavy = -left_heavy;
3017c478bd9Sstevel@tonic-gate 	avl_node_t *parent = AVL_XPARENT(node);
3027c478bd9Sstevel@tonic-gate 	avl_node_t *child = node->avl_child[left];
3037c478bd9Sstevel@tonic-gate 	avl_node_t *cright;
3047c478bd9Sstevel@tonic-gate 	avl_node_t *gchild;
3057c478bd9Sstevel@tonic-gate 	avl_node_t *gright;
3067c478bd9Sstevel@tonic-gate 	avl_node_t *gleft;
3077c478bd9Sstevel@tonic-gate 	int which_child = AVL_XCHILD(node);
3087c478bd9Sstevel@tonic-gate 	int child_bal = AVL_XBALANCE(child);
3097c478bd9Sstevel@tonic-gate 
3107c478bd9Sstevel@tonic-gate 	/* BEGIN CSTYLED */
3117c478bd9Sstevel@tonic-gate 	/*
3127c478bd9Sstevel@tonic-gate 	 * case 1 : node is overly left heavy, the left child is balanced or
3137c478bd9Sstevel@tonic-gate 	 * also left heavy. This requires the following rotation.
3147c478bd9Sstevel@tonic-gate 	 *
3157c478bd9Sstevel@tonic-gate 	 *                   (node bal:-2)
3167c478bd9Sstevel@tonic-gate 	 *                    /           \
3177c478bd9Sstevel@tonic-gate 	 *                   /             \
3187c478bd9Sstevel@tonic-gate 	 *              (child bal:0 or -1)
3197c478bd9Sstevel@tonic-gate 	 *              /    \
3207c478bd9Sstevel@tonic-gate 	 *             /      \
3217c478bd9Sstevel@tonic-gate 	 *                     cright
3227c478bd9Sstevel@tonic-gate 	 *
3237c478bd9Sstevel@tonic-gate 	 * becomes:
3247c478bd9Sstevel@tonic-gate 	 *
3257c478bd9Sstevel@tonic-gate 	 *              (child bal:1 or 0)
3267c478bd9Sstevel@tonic-gate 	 *              /        \
3277c478bd9Sstevel@tonic-gate 	 *             /          \
3287c478bd9Sstevel@tonic-gate 	 *                        (node bal:-1 or 0)
3297c478bd9Sstevel@tonic-gate 	 *                         /     \
3307c478bd9Sstevel@tonic-gate 	 *                        /       \
3317c478bd9Sstevel@tonic-gate 	 *                     cright
3327c478bd9Sstevel@tonic-gate 	 *
3337c478bd9Sstevel@tonic-gate 	 * we detect this situation by noting that child's balance is not
3347c478bd9Sstevel@tonic-gate 	 * right_heavy.
3357c478bd9Sstevel@tonic-gate 	 */
3367c478bd9Sstevel@tonic-gate 	/* END CSTYLED */
3377c478bd9Sstevel@tonic-gate 	if (child_bal != right_heavy) {
3387c478bd9Sstevel@tonic-gate 
3397c478bd9Sstevel@tonic-gate 		/*
3407c478bd9Sstevel@tonic-gate 		 * compute new balance of nodes
3417c478bd9Sstevel@tonic-gate 		 *
3427c478bd9Sstevel@tonic-gate 		 * If child used to be left heavy (now balanced) we reduced
3437c478bd9Sstevel@tonic-gate 		 * the height of this sub-tree -- used in "return...;" below
3447c478bd9Sstevel@tonic-gate 		 */
3457c478bd9Sstevel@tonic-gate 		child_bal += right_heavy; /* adjust towards right */
3467c478bd9Sstevel@tonic-gate 
3477c478bd9Sstevel@tonic-gate 		/*
3487c478bd9Sstevel@tonic-gate 		 * move "cright" to be node's left child
3497c478bd9Sstevel@tonic-gate 		 */
3507c478bd9Sstevel@tonic-gate 		cright = child->avl_child[right];
3517c478bd9Sstevel@tonic-gate 		node->avl_child[left] = cright;
3527c478bd9Sstevel@tonic-gate 		if (cright != NULL) {
3537c478bd9Sstevel@tonic-gate 			AVL_SETPARENT(cright, node);
3547c478bd9Sstevel@tonic-gate 			AVL_SETCHILD(cright, left);
3557c478bd9Sstevel@tonic-gate 		}
3567c478bd9Sstevel@tonic-gate 
3577c478bd9Sstevel@tonic-gate 		/*
3587c478bd9Sstevel@tonic-gate 		 * move node to be child's right child
3597c478bd9Sstevel@tonic-gate 		 */
3607c478bd9Sstevel@tonic-gate 		child->avl_child[right] = node;
3617c478bd9Sstevel@tonic-gate 		AVL_SETBALANCE(node, -child_bal);
3627c478bd9Sstevel@tonic-gate 		AVL_SETCHILD(node, right);
3637c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(node, child);
3647c478bd9Sstevel@tonic-gate 
3657c478bd9Sstevel@tonic-gate 		/*
3667c478bd9Sstevel@tonic-gate 		 * update the pointer into this subtree
3677c478bd9Sstevel@tonic-gate 		 */
3687c478bd9Sstevel@tonic-gate 		AVL_SETBALANCE(child, child_bal);
3697c478bd9Sstevel@tonic-gate 		AVL_SETCHILD(child, which_child);
3707c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(child, parent);
3717c478bd9Sstevel@tonic-gate 		if (parent != NULL)
3727c478bd9Sstevel@tonic-gate 			parent->avl_child[which_child] = child;
3737c478bd9Sstevel@tonic-gate 		else
3747c478bd9Sstevel@tonic-gate 			tree->avl_root = child;
3757c478bd9Sstevel@tonic-gate 
3767c478bd9Sstevel@tonic-gate 		return (child_bal == 0);
3777c478bd9Sstevel@tonic-gate 	}
3787c478bd9Sstevel@tonic-gate 
3797c478bd9Sstevel@tonic-gate 	/* BEGIN CSTYLED */
3807c478bd9Sstevel@tonic-gate 	/*
3817c478bd9Sstevel@tonic-gate 	 * case 2 : When node is left heavy, but child is right heavy we use
3827c478bd9Sstevel@tonic-gate 	 * a different rotation.
3837c478bd9Sstevel@tonic-gate 	 *
3847c478bd9Sstevel@tonic-gate 	 *                   (node b:-2)
3857c478bd9Sstevel@tonic-gate 	 *                    /   \
3867c478bd9Sstevel@tonic-gate 	 *                   /     \
3877c478bd9Sstevel@tonic-gate 	 *                  /       \
3887c478bd9Sstevel@tonic-gate 	 *             (child b:+1)
3897c478bd9Sstevel@tonic-gate 	 *              /     \
3907c478bd9Sstevel@tonic-gate 	 *             /       \
3917c478bd9Sstevel@tonic-gate 	 *                   (gchild b: != 0)
3927c478bd9Sstevel@tonic-gate 	 *                     /  \
3937c478bd9Sstevel@tonic-gate 	 *                    /    \
3947c478bd9Sstevel@tonic-gate 	 *                 gleft   gright
3957c478bd9Sstevel@tonic-gate 	 *
3967c478bd9Sstevel@tonic-gate 	 * becomes:
3977c478bd9Sstevel@tonic-gate 	 *
3987c478bd9Sstevel@tonic-gate 	 *              (gchild b:0)
3997c478bd9Sstevel@tonic-gate 	 *              /       \
4007c478bd9Sstevel@tonic-gate 	 *             /         \
4017c478bd9Sstevel@tonic-gate 	 *            /           \
4027c478bd9Sstevel@tonic-gate 	 *        (child b:?)   (node b:?)
4037c478bd9Sstevel@tonic-gate 	 *         /  \          /   \
4047c478bd9Sstevel@tonic-gate 	 *        /    \        /     \
4057c478bd9Sstevel@tonic-gate 	 *            gleft   gright
4067c478bd9Sstevel@tonic-gate 	 *
4077c478bd9Sstevel@tonic-gate 	 * computing the new balances is more complicated. As an example:
4087c478bd9Sstevel@tonic-gate 	 *	 if gchild was right_heavy, then child is now left heavy
4097c478bd9Sstevel@tonic-gate 	 *		else it is balanced
4107c478bd9Sstevel@tonic-gate 	 */
4117c478bd9Sstevel@tonic-gate 	/* END CSTYLED */
4127c478bd9Sstevel@tonic-gate 	gchild = child->avl_child[right];
4137c478bd9Sstevel@tonic-gate 	gleft = gchild->avl_child[left];
4147c478bd9Sstevel@tonic-gate 	gright = gchild->avl_child[right];
4157c478bd9Sstevel@tonic-gate 
4167c478bd9Sstevel@tonic-gate 	/*
4177c478bd9Sstevel@tonic-gate 	 * move gright to left child of node and
4187c478bd9Sstevel@tonic-gate 	 *
4197c478bd9Sstevel@tonic-gate 	 * move gleft to right child of node
4207c478bd9Sstevel@tonic-gate 	 */
4217c478bd9Sstevel@tonic-gate 	node->avl_child[left] = gright;
4227c478bd9Sstevel@tonic-gate 	if (gright != NULL) {
4237c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(gright, node);
4247c478bd9Sstevel@tonic-gate 		AVL_SETCHILD(gright, left);
4257c478bd9Sstevel@tonic-gate 	}
4267c478bd9Sstevel@tonic-gate 
4277c478bd9Sstevel@tonic-gate 	child->avl_child[right] = gleft;
4287c478bd9Sstevel@tonic-gate 	if (gleft != NULL) {
4297c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(gleft, child);
4307c478bd9Sstevel@tonic-gate 		AVL_SETCHILD(gleft, right);
4317c478bd9Sstevel@tonic-gate 	}
4327c478bd9Sstevel@tonic-gate 
4337c478bd9Sstevel@tonic-gate 	/*
4347c478bd9Sstevel@tonic-gate 	 * move child to left child of gchild and
4357c478bd9Sstevel@tonic-gate 	 *
4367c478bd9Sstevel@tonic-gate 	 * move node to right child of gchild and
4377c478bd9Sstevel@tonic-gate 	 *
4387c478bd9Sstevel@tonic-gate 	 * fixup parent of all this to point to gchild
4397c478bd9Sstevel@tonic-gate 	 */
4407c478bd9Sstevel@tonic-gate 	balance = AVL_XBALANCE(gchild);
4417c478bd9Sstevel@tonic-gate 	gchild->avl_child[left] = child;
4427c478bd9Sstevel@tonic-gate 	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));
4437c478bd9Sstevel@tonic-gate 	AVL_SETPARENT(child, gchild);
4447c478bd9Sstevel@tonic-gate 	AVL_SETCHILD(child, left);
4457c478bd9Sstevel@tonic-gate 
4467c478bd9Sstevel@tonic-gate 	gchild->avl_child[right] = node;
4477c478bd9Sstevel@tonic-gate 	AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));
4487c478bd9Sstevel@tonic-gate 	AVL_SETPARENT(node, gchild);
4497c478bd9Sstevel@tonic-gate 	AVL_SETCHILD(node, right);
4507c478bd9Sstevel@tonic-gate 
4517c478bd9Sstevel@tonic-gate 	AVL_SETBALANCE(gchild, 0);
4527c478bd9Sstevel@tonic-gate 	AVL_SETPARENT(gchild, parent);
4537c478bd9Sstevel@tonic-gate 	AVL_SETCHILD(gchild, which_child);
4547c478bd9Sstevel@tonic-gate 	if (parent != NULL)
4557c478bd9Sstevel@tonic-gate 		parent->avl_child[which_child] = gchild;
4567c478bd9Sstevel@tonic-gate 	else
4577c478bd9Sstevel@tonic-gate 		tree->avl_root = gchild;
4587c478bd9Sstevel@tonic-gate 
4597c478bd9Sstevel@tonic-gate 	return (1);	/* the new tree is always shorter */
4607c478bd9Sstevel@tonic-gate }
4617c478bd9Sstevel@tonic-gate 
4627c478bd9Sstevel@tonic-gate 
4637c478bd9Sstevel@tonic-gate /*
4647c478bd9Sstevel@tonic-gate  * Insert a new node into an AVL tree at the specified (from avl_find()) place.
4657c478bd9Sstevel@tonic-gate  *
4667c478bd9Sstevel@tonic-gate  * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
4677c478bd9Sstevel@tonic-gate  * searches out to the leaf positions.  The avl_index_t indicates the node
4687c478bd9Sstevel@tonic-gate  * which will be the parent of the new node.
4697c478bd9Sstevel@tonic-gate  *
4707c478bd9Sstevel@tonic-gate  * After the node is inserted, a single rotation further up the tree may
4717c478bd9Sstevel@tonic-gate  * be necessary to maintain an acceptable AVL balance.
4727c478bd9Sstevel@tonic-gate  */
4737c478bd9Sstevel@tonic-gate void
4747c478bd9Sstevel@tonic-gate avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
4757c478bd9Sstevel@tonic-gate {
4767c478bd9Sstevel@tonic-gate 	avl_node_t *node;
4777c478bd9Sstevel@tonic-gate 	avl_node_t *parent = AVL_INDEX2NODE(where);
4787c478bd9Sstevel@tonic-gate 	int old_balance;
4797c478bd9Sstevel@tonic-gate 	int new_balance;
4807c478bd9Sstevel@tonic-gate 	int which_child = AVL_INDEX2CHILD(where);
4817c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
4827c478bd9Sstevel@tonic-gate 
4837c478bd9Sstevel@tonic-gate 	ASSERT(tree);
4847c478bd9Sstevel@tonic-gate #ifdef _LP64
4857c478bd9Sstevel@tonic-gate 	ASSERT(((uintptr_t)new_data & 0x7) == 0);
4867c478bd9Sstevel@tonic-gate #endif
4877c478bd9Sstevel@tonic-gate 
4887c478bd9Sstevel@tonic-gate 	node = AVL_DATA2NODE(new_data, off);
4897c478bd9Sstevel@tonic-gate 
4907c478bd9Sstevel@tonic-gate 	/*
4917c478bd9Sstevel@tonic-gate 	 * First, add the node to the tree at the indicated position.
4927c478bd9Sstevel@tonic-gate 	 */
4937c478bd9Sstevel@tonic-gate 	++tree->avl_numnodes;
4947c478bd9Sstevel@tonic-gate 
4957c478bd9Sstevel@tonic-gate 	node->avl_child[0] = NULL;
4967c478bd9Sstevel@tonic-gate 	node->avl_child[1] = NULL;
4977c478bd9Sstevel@tonic-gate 
4987c478bd9Sstevel@tonic-gate 	AVL_SETCHILD(node, which_child);
4997c478bd9Sstevel@tonic-gate 	AVL_SETBALANCE(node, 0);
5007c478bd9Sstevel@tonic-gate 	AVL_SETPARENT(node, parent);
5017c478bd9Sstevel@tonic-gate 	if (parent != NULL) {
5027c478bd9Sstevel@tonic-gate 		ASSERT(parent->avl_child[which_child] == NULL);
5037c478bd9Sstevel@tonic-gate 		parent->avl_child[which_child] = node;
5047c478bd9Sstevel@tonic-gate 	} else {
5057c478bd9Sstevel@tonic-gate 		ASSERT(tree->avl_root == NULL);
5067c478bd9Sstevel@tonic-gate 		tree->avl_root = node;
5077c478bd9Sstevel@tonic-gate 	}
5087c478bd9Sstevel@tonic-gate 	/*
5097c478bd9Sstevel@tonic-gate 	 * Now, back up the tree modifying the balance of all nodes above the
5107c478bd9Sstevel@tonic-gate 	 * insertion point. If we get to a highly unbalanced ancestor, we
5117c478bd9Sstevel@tonic-gate 	 * need to do a rotation.  If we back out of the tree we are done.
5127c478bd9Sstevel@tonic-gate 	 * If we brought any subtree into perfect balance (0), we are also done.
5137c478bd9Sstevel@tonic-gate 	 */
5147c478bd9Sstevel@tonic-gate 	for (;;) {
5157c478bd9Sstevel@tonic-gate 		node = parent;
5167c478bd9Sstevel@tonic-gate 		if (node == NULL)
5177c478bd9Sstevel@tonic-gate 			return;
5187c478bd9Sstevel@tonic-gate 
5197c478bd9Sstevel@tonic-gate 		/*
5207c478bd9Sstevel@tonic-gate 		 * Compute the new balance
5217c478bd9Sstevel@tonic-gate 		 */
5227c478bd9Sstevel@tonic-gate 		old_balance = AVL_XBALANCE(node);
5237c478bd9Sstevel@tonic-gate 		new_balance = old_balance + avl_child2balance[which_child];
5247c478bd9Sstevel@tonic-gate 
5257c478bd9Sstevel@tonic-gate 		/*
5267c478bd9Sstevel@tonic-gate 		 * If we introduced equal balance, then we are done immediately
5277c478bd9Sstevel@tonic-gate 		 */
5287c478bd9Sstevel@tonic-gate 		if (new_balance == 0) {
5297c478bd9Sstevel@tonic-gate 			AVL_SETBALANCE(node, 0);
5307c478bd9Sstevel@tonic-gate 			return;
5317c478bd9Sstevel@tonic-gate 		}
5327c478bd9Sstevel@tonic-gate 
5337c478bd9Sstevel@tonic-gate 		/*
5347c478bd9Sstevel@tonic-gate 		 * If both old and new are not zero we went
5357c478bd9Sstevel@tonic-gate 		 * from -1 to -2 balance, do a rotation.
5367c478bd9Sstevel@tonic-gate 		 */
5377c478bd9Sstevel@tonic-gate 		if (old_balance != 0)
5387c478bd9Sstevel@tonic-gate 			break;
5397c478bd9Sstevel@tonic-gate 
5407c478bd9Sstevel@tonic-gate 		AVL_SETBALANCE(node, new_balance);
5417c478bd9Sstevel@tonic-gate 		parent = AVL_XPARENT(node);
5427c478bd9Sstevel@tonic-gate 		which_child = AVL_XCHILD(node);
5437c478bd9Sstevel@tonic-gate 	}
5447c478bd9Sstevel@tonic-gate 
5457c478bd9Sstevel@tonic-gate 	/*
5467c478bd9Sstevel@tonic-gate 	 * perform a rotation to fix the tree and return
5477c478bd9Sstevel@tonic-gate 	 */
5487c478bd9Sstevel@tonic-gate 	(void) avl_rotation(tree, node, new_balance);
5497c478bd9Sstevel@tonic-gate }
5507c478bd9Sstevel@tonic-gate 
5517c478bd9Sstevel@tonic-gate /*
5527c478bd9Sstevel@tonic-gate  * Insert "new_data" in "tree" in the given "direction" either after or
5537c478bd9Sstevel@tonic-gate  * before (AVL_AFTER, AVL_BEFORE) the data "here".
5547c478bd9Sstevel@tonic-gate  *
5557c478bd9Sstevel@tonic-gate  * Insertions can only be done at empty leaf points in the tree, therefore
5567c478bd9Sstevel@tonic-gate  * if the given child of the node is already present we move to either
5577c478bd9Sstevel@tonic-gate  * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since
5587c478bd9Sstevel@tonic-gate  * every other node in the tree is a leaf, this always works.
5597c478bd9Sstevel@tonic-gate  *
5607c478bd9Sstevel@tonic-gate  * To help developers using this interface, we assert that the new node
5617c478bd9Sstevel@tonic-gate  * is correctly ordered at every step of the way in DEBUG kernels.
5627c478bd9Sstevel@tonic-gate  */
5637c478bd9Sstevel@tonic-gate void
5647c478bd9Sstevel@tonic-gate avl_insert_here(
5657c478bd9Sstevel@tonic-gate 	avl_tree_t *tree,
5667c478bd9Sstevel@tonic-gate 	void *new_data,
5677c478bd9Sstevel@tonic-gate 	void *here,
5687c478bd9Sstevel@tonic-gate 	int direction)
5697c478bd9Sstevel@tonic-gate {
5707c478bd9Sstevel@tonic-gate 	avl_node_t *node;
5717c478bd9Sstevel@tonic-gate 	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
5727c478bd9Sstevel@tonic-gate 
5737c478bd9Sstevel@tonic-gate 	ASSERT(tree != NULL);
5747c478bd9Sstevel@tonic-gate 	ASSERT(new_data != NULL);
5757c478bd9Sstevel@tonic-gate 	ASSERT(here != NULL);
5767c478bd9Sstevel@tonic-gate 	ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER);
5777c478bd9Sstevel@tonic-gate 
5787c478bd9Sstevel@tonic-gate 	/*
5797c478bd9Sstevel@tonic-gate 	 * If corresponding child of node is not NULL, go to the neighboring
5807c478bd9Sstevel@tonic-gate 	 * node and reverse the insertion direction.
5817c478bd9Sstevel@tonic-gate 	 */
5827c478bd9Sstevel@tonic-gate 	node = AVL_DATA2NODE(here, tree->avl_offset);
5837c478bd9Sstevel@tonic-gate 	ASSERT(tree->avl_compar(new_data, here) > 0 ? child == 1 : child == 0);
5847c478bd9Sstevel@tonic-gate 
5857c478bd9Sstevel@tonic-gate 	if (node->avl_child[child] != NULL) {
5867c478bd9Sstevel@tonic-gate 		node = node->avl_child[child];
5877c478bd9Sstevel@tonic-gate 		child = 1 - child;
5887c478bd9Sstevel@tonic-gate 		while (node->avl_child[child] != NULL) {
5897c478bd9Sstevel@tonic-gate 			ASSERT(tree->avl_compar(new_data,
5907c478bd9Sstevel@tonic-gate 			    AVL_NODE2DATA(node, tree->avl_offset)) > 0 ?
5917c478bd9Sstevel@tonic-gate 			    child == 1 : child == 0);
5927c478bd9Sstevel@tonic-gate 			node = node->avl_child[child];
5937c478bd9Sstevel@tonic-gate 		}
5947c478bd9Sstevel@tonic-gate 		ASSERT(tree->avl_compar(new_data,
5957c478bd9Sstevel@tonic-gate 		    AVL_NODE2DATA(node, tree->avl_offset)) > 0 ?
5967c478bd9Sstevel@tonic-gate 		    child == 1 : child == 0);
5977c478bd9Sstevel@tonic-gate 	}
5987c478bd9Sstevel@tonic-gate 	ASSERT(node->avl_child[child] == NULL);
5997c478bd9Sstevel@tonic-gate 
6007c478bd9Sstevel@tonic-gate 	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
6017c478bd9Sstevel@tonic-gate }
6027c478bd9Sstevel@tonic-gate 
603*fa9e4066Sahrens /*
604*fa9e4066Sahrens  * Add a new node to an AVL tree.
605*fa9e4066Sahrens  */
606*fa9e4066Sahrens void
607*fa9e4066Sahrens avl_add(avl_tree_t *tree, void *new_node)
608*fa9e4066Sahrens {
609*fa9e4066Sahrens 	avl_index_t where;
610*fa9e4066Sahrens 
611*fa9e4066Sahrens 	/*
612*fa9e4066Sahrens 	 * This is unfortunate.  We want to call panic() here, even for
613*fa9e4066Sahrens 	 * non-DEBUG kernels.  In userland, however, we can't depend on anything
614*fa9e4066Sahrens 	 * in libc or else the rtld build process gets confused.  So, all we can
615*fa9e4066Sahrens 	 * do in userland is resort to a normal ASSERT().
616*fa9e4066Sahrens 	 */
617*fa9e4066Sahrens 	if (avl_find(tree, new_node, &where) != NULL)
618*fa9e4066Sahrens #ifdef _KERNEL
619*fa9e4066Sahrens 		panic("avl_find() succeeded inside avl_add()");
620*fa9e4066Sahrens #else
621*fa9e4066Sahrens 		ASSERT(0);
622*fa9e4066Sahrens #endif
623*fa9e4066Sahrens 	avl_insert(tree, new_node, where);
624*fa9e4066Sahrens }
625*fa9e4066Sahrens 
6267c478bd9Sstevel@tonic-gate /*
6277c478bd9Sstevel@tonic-gate  * Delete a node from the AVL tree.  Deletion is similar to insertion, but
6287c478bd9Sstevel@tonic-gate  * with 2 complications.
6297c478bd9Sstevel@tonic-gate  *
6307c478bd9Sstevel@tonic-gate  * First, we may be deleting an interior node. Consider the following subtree:
6317c478bd9Sstevel@tonic-gate  *
6327c478bd9Sstevel@tonic-gate  *     d           c            c
6337c478bd9Sstevel@tonic-gate  *    / \         / \          / \
6347c478bd9Sstevel@tonic-gate  *   b   e       b   e        b   e
6357c478bd9Sstevel@tonic-gate  *  / \	        / \          /
6367c478bd9Sstevel@tonic-gate  * a   c       a            a
6377c478bd9Sstevel@tonic-gate  *
6387c478bd9Sstevel@tonic-gate  * When we are deleting node (d), we find and bring up an adjacent valued leaf
6397c478bd9Sstevel@tonic-gate  * node, say (c), to take the interior node's place. In the code this is
6407c478bd9Sstevel@tonic-gate  * handled by temporarily swapping (d) and (c) in the tree and then using
6417c478bd9Sstevel@tonic-gate  * common code to delete (d) from the leaf position.
6427c478bd9Sstevel@tonic-gate  *
6437c478bd9Sstevel@tonic-gate  * Secondly, an interior deletion from a deep tree may require more than one
6447c478bd9Sstevel@tonic-gate  * rotation to fix the balance. This is handled by moving up the tree through
6457c478bd9Sstevel@tonic-gate  * parents and applying rotations as needed. The return value from
6467c478bd9Sstevel@tonic-gate  * avl_rotation() is used to detect when a subtree did not change overall
6477c478bd9Sstevel@tonic-gate  * height due to a rotation.
6487c478bd9Sstevel@tonic-gate  */
6497c478bd9Sstevel@tonic-gate void
6507c478bd9Sstevel@tonic-gate avl_remove(avl_tree_t *tree, void *data)
6517c478bd9Sstevel@tonic-gate {
6527c478bd9Sstevel@tonic-gate 	avl_node_t *delete;
6537c478bd9Sstevel@tonic-gate 	avl_node_t *parent;
6547c478bd9Sstevel@tonic-gate 	avl_node_t *node;
6557c478bd9Sstevel@tonic-gate 	avl_node_t tmp;
6567c478bd9Sstevel@tonic-gate 	int old_balance;
6577c478bd9Sstevel@tonic-gate 	int new_balance;
6587c478bd9Sstevel@tonic-gate 	int left;
6597c478bd9Sstevel@tonic-gate 	int right;
6607c478bd9Sstevel@tonic-gate 	int which_child;
6617c478bd9Sstevel@tonic-gate 	size_t off = tree->avl_offset;
6627c478bd9Sstevel@tonic-gate 
6637c478bd9Sstevel@tonic-gate 	ASSERT(tree);
6647c478bd9Sstevel@tonic-gate 
6657c478bd9Sstevel@tonic-gate 	delete = AVL_DATA2NODE(data, off);
6667c478bd9Sstevel@tonic-gate 
6677c478bd9Sstevel@tonic-gate 	/*
6687c478bd9Sstevel@tonic-gate 	 * Deletion is easiest with a node that has at most 1 child.
6697c478bd9Sstevel@tonic-gate 	 * We swap a node with 2 children with a sequentially valued
6707c478bd9Sstevel@tonic-gate 	 * neighbor node. That node will have at most 1 child. Note this
6717c478bd9Sstevel@tonic-gate 	 * has no effect on the ordering of the remaining nodes.
6727c478bd9Sstevel@tonic-gate 	 *
6737c478bd9Sstevel@tonic-gate 	 * As an optimization, we choose the greater neighbor if the tree
6747c478bd9Sstevel@tonic-gate 	 * is right heavy, otherwise the left neighbor. This reduces the
6757c478bd9Sstevel@tonic-gate 	 * number of rotations needed.
6767c478bd9Sstevel@tonic-gate 	 */
6777c478bd9Sstevel@tonic-gate 	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {
6787c478bd9Sstevel@tonic-gate 
6797c478bd9Sstevel@tonic-gate 		/*
6807c478bd9Sstevel@tonic-gate 		 * choose node to swap from whichever side is taller
6817c478bd9Sstevel@tonic-gate 		 */
6827c478bd9Sstevel@tonic-gate 		old_balance = AVL_XBALANCE(delete);
6837c478bd9Sstevel@tonic-gate 		left = avl_balance2child[old_balance + 1];
6847c478bd9Sstevel@tonic-gate 		right = 1 - left;
6857c478bd9Sstevel@tonic-gate 
6867c478bd9Sstevel@tonic-gate 		/*
6877c478bd9Sstevel@tonic-gate 		 * get to the previous value'd node
6887c478bd9Sstevel@tonic-gate 		 * (down 1 left, as far as possible right)
6897c478bd9Sstevel@tonic-gate 		 */
6907c478bd9Sstevel@tonic-gate 		for (node = delete->avl_child[left];
6917c478bd9Sstevel@tonic-gate 		    node->avl_child[right] != NULL;
6927c478bd9Sstevel@tonic-gate 		    node = node->avl_child[right])
6937c478bd9Sstevel@tonic-gate 			;
6947c478bd9Sstevel@tonic-gate 
6957c478bd9Sstevel@tonic-gate 		/*
6967c478bd9Sstevel@tonic-gate 		 * create a temp placeholder for 'node'
6977c478bd9Sstevel@tonic-gate 		 * move 'node' to delete's spot in the tree
6987c478bd9Sstevel@tonic-gate 		 */
6997c478bd9Sstevel@tonic-gate 		tmp = *node;
7007c478bd9Sstevel@tonic-gate 
7017c478bd9Sstevel@tonic-gate 		*node = *delete;
7027c478bd9Sstevel@tonic-gate 		if (node->avl_child[left] == node)
7037c478bd9Sstevel@tonic-gate 			node->avl_child[left] = &tmp;
7047c478bd9Sstevel@tonic-gate 
7057c478bd9Sstevel@tonic-gate 		parent = AVL_XPARENT(node);
7067c478bd9Sstevel@tonic-gate 		if (parent != NULL)
7077c478bd9Sstevel@tonic-gate 			parent->avl_child[AVL_XCHILD(node)] = node;
7087c478bd9Sstevel@tonic-gate 		else
7097c478bd9Sstevel@tonic-gate 			tree->avl_root = node;
7107c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(node->avl_child[left], node);
7117c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(node->avl_child[right], node);
7127c478bd9Sstevel@tonic-gate 
7137c478bd9Sstevel@tonic-gate 		/*
7147c478bd9Sstevel@tonic-gate 		 * Put tmp where node used to be (just temporary).
7157c478bd9Sstevel@tonic-gate 		 * It always has a parent and at most 1 child.
7167c478bd9Sstevel@tonic-gate 		 */
7177c478bd9Sstevel@tonic-gate 		delete = &tmp;
7187c478bd9Sstevel@tonic-gate 		parent = AVL_XPARENT(delete);
7197c478bd9Sstevel@tonic-gate 		parent->avl_child[AVL_XCHILD(delete)] = delete;
7207c478bd9Sstevel@tonic-gate 		which_child = (delete->avl_child[1] != 0);
7217c478bd9Sstevel@tonic-gate 		if (delete->avl_child[which_child] != NULL)
7227c478bd9Sstevel@tonic-gate 			AVL_SETPARENT(delete->avl_child[which_child], delete);
7237c478bd9Sstevel@tonic-gate 	}
7247c478bd9Sstevel@tonic-gate 
7257c478bd9Sstevel@tonic-gate 
7267c478bd9Sstevel@tonic-gate 	/*
7277c478bd9Sstevel@tonic-gate 	 * Here we know "delete" is at least partially a leaf node. It can
7287c478bd9Sstevel@tonic-gate 	 * be easily removed from the tree.
7297c478bd9Sstevel@tonic-gate 	 */
7307c478bd9Sstevel@tonic-gate 	--tree->avl_numnodes;
7317c478bd9Sstevel@tonic-gate 	parent = AVL_XPARENT(delete);
7327c478bd9Sstevel@tonic-gate 	which_child = AVL_XCHILD(delete);
7337c478bd9Sstevel@tonic-gate 	if (delete->avl_child[0] != NULL)
7347c478bd9Sstevel@tonic-gate 		node = delete->avl_child[0];
7357c478bd9Sstevel@tonic-gate 	else
7367c478bd9Sstevel@tonic-gate 		node = delete->avl_child[1];
7377c478bd9Sstevel@tonic-gate 
7387c478bd9Sstevel@tonic-gate 	/*
7397c478bd9Sstevel@tonic-gate 	 * Connect parent directly to node (leaving out delete).
7407c478bd9Sstevel@tonic-gate 	 */
7417c478bd9Sstevel@tonic-gate 	if (node != NULL) {
7427c478bd9Sstevel@tonic-gate 		AVL_SETPARENT(node, parent);
7437c478bd9Sstevel@tonic-gate 		AVL_SETCHILD(node, which_child);
7447c478bd9Sstevel@tonic-gate 	}
7457c478bd9Sstevel@tonic-gate 	if (parent == NULL) {
7467c478bd9Sstevel@tonic-gate 		tree->avl_root = node;
7477c478bd9Sstevel@tonic-gate 		return;
7487c478bd9Sstevel@tonic-gate 	}
7497c478bd9Sstevel@tonic-gate 	parent->avl_child[which_child] = node;
7507c478bd9Sstevel@tonic-gate 
7517c478bd9Sstevel@tonic-gate 
7527c478bd9Sstevel@tonic-gate 	/*
7537c478bd9Sstevel@tonic-gate 	 * Since the subtree is now shorter, begin adjusting parent balances
7547c478bd9Sstevel@tonic-gate 	 * and performing any needed rotations.
7557c478bd9Sstevel@tonic-gate 	 */
7567c478bd9Sstevel@tonic-gate 	do {
7577c478bd9Sstevel@tonic-gate 
7587c478bd9Sstevel@tonic-gate 		/*
7597c478bd9Sstevel@tonic-gate 		 * Move up the tree and adjust the balance
7607c478bd9Sstevel@tonic-gate 		 *
7617c478bd9Sstevel@tonic-gate 		 * Capture the parent and which_child values for the next
7627c478bd9Sstevel@tonic-gate 		 * iteration before any rotations occur.
7637c478bd9Sstevel@tonic-gate 		 */
7647c478bd9Sstevel@tonic-gate 		node = parent;
7657c478bd9Sstevel@tonic-gate 		old_balance = AVL_XBALANCE(node);
7667c478bd9Sstevel@tonic-gate 		new_balance = old_balance - avl_child2balance[which_child];
7677c478bd9Sstevel@tonic-gate 		parent = AVL_XPARENT(node);
7687c478bd9Sstevel@tonic-gate 		which_child = AVL_XCHILD(node);
7697c478bd9Sstevel@tonic-gate 
7707c478bd9Sstevel@tonic-gate 		/*
7717c478bd9Sstevel@tonic-gate 		 * If a node was in perfect balance but isn't anymore then
7727c478bd9Sstevel@tonic-gate 		 * we can stop, since the height didn't change above this point
7737c478bd9Sstevel@tonic-gate 		 * due to a deletion.
7747c478bd9Sstevel@tonic-gate 		 */
7757c478bd9Sstevel@tonic-gate 		if (old_balance == 0) {
7767c478bd9Sstevel@tonic-gate 			AVL_SETBALANCE(node, new_balance);
7777c478bd9Sstevel@tonic-gate 			break;
7787c478bd9Sstevel@tonic-gate 		}
7797c478bd9Sstevel@tonic-gate 
7807c478bd9Sstevel@tonic-gate 		/*
7817c478bd9Sstevel@tonic-gate 		 * If the new balance is zero, we don't need to rotate
7827c478bd9Sstevel@tonic-gate 		 * else
7837c478bd9Sstevel@tonic-gate 		 * need a rotation to fix the balance.
7847c478bd9Sstevel@tonic-gate 		 * If the rotation doesn't change the height
7857c478bd9Sstevel@tonic-gate 		 * of the sub-tree we have finished adjusting.
7867c478bd9Sstevel@tonic-gate 		 */
7877c478bd9Sstevel@tonic-gate 		if (new_balance == 0)
7887c478bd9Sstevel@tonic-gate 			AVL_SETBALANCE(node, new_balance);
7897c478bd9Sstevel@tonic-gate 		else if (!avl_rotation(tree, node, new_balance))
7907c478bd9Sstevel@tonic-gate 			break;
7917c478bd9Sstevel@tonic-gate 	} while (parent != NULL);
7927c478bd9Sstevel@tonic-gate }
7937c478bd9Sstevel@tonic-gate 
7947c478bd9Sstevel@tonic-gate /*
7957c478bd9Sstevel@tonic-gate  * initialize a new AVL tree
7967c478bd9Sstevel@tonic-gate  */
7977c478bd9Sstevel@tonic-gate void
7987c478bd9Sstevel@tonic-gate avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
7997c478bd9Sstevel@tonic-gate     size_t size, size_t offset)
8007c478bd9Sstevel@tonic-gate {
8017c478bd9Sstevel@tonic-gate 	ASSERT(tree);
8027c478bd9Sstevel@tonic-gate 	ASSERT(compar);
8037c478bd9Sstevel@tonic-gate 	ASSERT(size > 0);
8047c478bd9Sstevel@tonic-gate 	ASSERT(size >= offset + sizeof (avl_node_t));
8057c478bd9Sstevel@tonic-gate #ifdef _LP64
8067c478bd9Sstevel@tonic-gate 	ASSERT((offset & 0x7) == 0);
8077c478bd9Sstevel@tonic-gate #endif
8087c478bd9Sstevel@tonic-gate 
8097c478bd9Sstevel@tonic-gate 	tree->avl_compar = compar;
8107c478bd9Sstevel@tonic-gate 	tree->avl_root = NULL;
8117c478bd9Sstevel@tonic-gate 	tree->avl_numnodes = 0;
8127c478bd9Sstevel@tonic-gate 	tree->avl_size = size;
8137c478bd9Sstevel@tonic-gate 	tree->avl_offset = offset;
8147c478bd9Sstevel@tonic-gate }
8157c478bd9Sstevel@tonic-gate 
8167c478bd9Sstevel@tonic-gate /*
8177c478bd9Sstevel@tonic-gate  * Delete a tree.
8187c478bd9Sstevel@tonic-gate  */
8197c478bd9Sstevel@tonic-gate /* ARGSUSED */
8207c478bd9Sstevel@tonic-gate void
8217c478bd9Sstevel@tonic-gate avl_destroy(avl_tree_t *tree)
8227c478bd9Sstevel@tonic-gate {
8237c478bd9Sstevel@tonic-gate 	ASSERT(tree);
8247c478bd9Sstevel@tonic-gate 	ASSERT(tree->avl_numnodes == 0);
8257c478bd9Sstevel@tonic-gate 	ASSERT(tree->avl_root == NULL);
8267c478bd9Sstevel@tonic-gate }
8277c478bd9Sstevel@tonic-gate 
8287c478bd9Sstevel@tonic-gate 
8297c478bd9Sstevel@tonic-gate /*
8307c478bd9Sstevel@tonic-gate  * Return the number of nodes in an AVL tree.
8317c478bd9Sstevel@tonic-gate  */
8327c478bd9Sstevel@tonic-gate ulong_t
8337c478bd9Sstevel@tonic-gate avl_numnodes(avl_tree_t *tree)
8347c478bd9Sstevel@tonic-gate {
8357c478bd9Sstevel@tonic-gate 	ASSERT(tree);
8367c478bd9Sstevel@tonic-gate 	return (tree->avl_numnodes);
8377c478bd9Sstevel@tonic-gate }
8387c478bd9Sstevel@tonic-gate 
8397c478bd9Sstevel@tonic-gate 
8407c478bd9Sstevel@tonic-gate #define	CHILDBIT	(1L)
8417c478bd9Sstevel@tonic-gate 
8427c478bd9Sstevel@tonic-gate /*
8437c478bd9Sstevel@tonic-gate  * Post-order tree walk used to visit all tree nodes and destroy the tree
8447c478bd9Sstevel@tonic-gate  * in post order. This is used for destroying a tree w/o paying any cost
8457c478bd9Sstevel@tonic-gate  * for rebalancing it.
8467c478bd9Sstevel@tonic-gate  *
8477c478bd9Sstevel@tonic-gate  * example:
8487c478bd9Sstevel@tonic-gate  *
8497c478bd9Sstevel@tonic-gate  *	void *cookie = NULL;
8507c478bd9Sstevel@tonic-gate  *	my_data_t *node;
8517c478bd9Sstevel@tonic-gate  *
8527c478bd9Sstevel@tonic-gate  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
8537c478bd9Sstevel@tonic-gate  *		free(node);
8547c478bd9Sstevel@tonic-gate  *	avl_destroy(tree);
8557c478bd9Sstevel@tonic-gate  *
8567c478bd9Sstevel@tonic-gate  * The cookie is really an avl_node_t to the current node's parent and
8577c478bd9Sstevel@tonic-gate  * an indication of which child you looked at last.
8587c478bd9Sstevel@tonic-gate  *
8597c478bd9Sstevel@tonic-gate  * On input, a cookie value of CHILDBIT indicates the tree is done.
8607c478bd9Sstevel@tonic-gate  */
8617c478bd9Sstevel@tonic-gate void *
8627c478bd9Sstevel@tonic-gate avl_destroy_nodes(avl_tree_t *tree, void **cookie)
8637c478bd9Sstevel@tonic-gate {
8647c478bd9Sstevel@tonic-gate 	avl_node_t	*node;
8657c478bd9Sstevel@tonic-gate 	avl_node_t	*parent;
8667c478bd9Sstevel@tonic-gate 	int		child;
8677c478bd9Sstevel@tonic-gate 	void		*first;
8687c478bd9Sstevel@tonic-gate 	size_t		off = tree->avl_offset;
8697c478bd9Sstevel@tonic-gate 
8707c478bd9Sstevel@tonic-gate 	/*
8717c478bd9Sstevel@tonic-gate 	 * Initial calls go to the first node or it's right descendant.
8727c478bd9Sstevel@tonic-gate 	 */
8737c478bd9Sstevel@tonic-gate 	if (*cookie == NULL) {
8747c478bd9Sstevel@tonic-gate 		first = avl_first(tree);
8757c478bd9Sstevel@tonic-gate 
8767c478bd9Sstevel@tonic-gate 		/*
8777c478bd9Sstevel@tonic-gate 		 * deal with an empty tree
8787c478bd9Sstevel@tonic-gate 		 */
8797c478bd9Sstevel@tonic-gate 		if (first == NULL) {
8807c478bd9Sstevel@tonic-gate 			*cookie = (void *)CHILDBIT;
8817c478bd9Sstevel@tonic-gate 			return (NULL);
8827c478bd9Sstevel@tonic-gate 		}
8837c478bd9Sstevel@tonic-gate 
8847c478bd9Sstevel@tonic-gate 		node = AVL_DATA2NODE(first, off);
8857c478bd9Sstevel@tonic-gate 		parent = AVL_XPARENT(node);
8867c478bd9Sstevel@tonic-gate 		goto check_right_side;
8877c478bd9Sstevel@tonic-gate 	}
8887c478bd9Sstevel@tonic-gate 
8897c478bd9Sstevel@tonic-gate 	/*
8907c478bd9Sstevel@tonic-gate 	 * If there is no parent to return to we are done.
8917c478bd9Sstevel@tonic-gate 	 */
8927c478bd9Sstevel@tonic-gate 	parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT);
8937c478bd9Sstevel@tonic-gate 	if (parent == NULL) {
8947c478bd9Sstevel@tonic-gate 		if (tree->avl_root != NULL) {
8957c478bd9Sstevel@tonic-gate 			ASSERT(tree->avl_numnodes == 1);
8967c478bd9Sstevel@tonic-gate 			tree->avl_root = NULL;
8977c478bd9Sstevel@tonic-gate 			tree->avl_numnodes = 0;
8987c478bd9Sstevel@tonic-gate 		}
8997c478bd9Sstevel@tonic-gate 		return (NULL);
9007c478bd9Sstevel@tonic-gate 	}
9017c478bd9Sstevel@tonic-gate 
9027c478bd9Sstevel@tonic-gate 	/*
9037c478bd9Sstevel@tonic-gate 	 * Remove the child pointer we just visited from the parent and tree.
9047c478bd9Sstevel@tonic-gate 	 */
9057c478bd9Sstevel@tonic-gate 	child = (uintptr_t)(*cookie) & CHILDBIT;
9067c478bd9Sstevel@tonic-gate 	parent->avl_child[child] = NULL;
9077c478bd9Sstevel@tonic-gate 	ASSERT(tree->avl_numnodes > 1);
9087c478bd9Sstevel@tonic-gate 	--tree->avl_numnodes;
9097c478bd9Sstevel@tonic-gate 
9107c478bd9Sstevel@tonic-gate 	/*
9117c478bd9Sstevel@tonic-gate 	 * If we just did a right child or there isn't one, go up to parent.
9127c478bd9Sstevel@tonic-gate 	 */
9137c478bd9Sstevel@tonic-gate 	if (child == 1 || parent->avl_child[1] == NULL) {
9147c478bd9Sstevel@tonic-gate 		node = parent;
9157c478bd9Sstevel@tonic-gate 		parent = AVL_XPARENT(parent);
9167c478bd9Sstevel@tonic-gate 		goto done;
9177c478bd9Sstevel@tonic-gate 	}
9187c478bd9Sstevel@tonic-gate 
9197c478bd9Sstevel@tonic-gate 	/*
9207c478bd9Sstevel@tonic-gate 	 * Do parent's right child, then leftmost descendent.
9217c478bd9Sstevel@tonic-gate 	 */
9227c478bd9Sstevel@tonic-gate 	node = parent->avl_child[1];
9237c478bd9Sstevel@tonic-gate 	while (node->avl_child[0] != NULL) {
9247c478bd9Sstevel@tonic-gate 		parent = node;
9257c478bd9Sstevel@tonic-gate 		node = node->avl_child[0];
9267c478bd9Sstevel@tonic-gate 	}
9277c478bd9Sstevel@tonic-gate 
9287c478bd9Sstevel@tonic-gate 	/*
9297c478bd9Sstevel@tonic-gate 	 * If here, we moved to a left child. It may have one
9307c478bd9Sstevel@tonic-gate 	 * child on the right (when balance == +1).
9317c478bd9Sstevel@tonic-gate 	 */
9327c478bd9Sstevel@tonic-gate check_right_side:
9337c478bd9Sstevel@tonic-gate 	if (node->avl_child[1] != NULL) {
9347c478bd9Sstevel@tonic-gate 		ASSERT(AVL_XBALANCE(node) == 1);
9357c478bd9Sstevel@tonic-gate 		parent = node;
9367c478bd9Sstevel@tonic-gate 		node = node->avl_child[1];
9377c478bd9Sstevel@tonic-gate 		ASSERT(node->avl_child[0] == NULL &&
9387c478bd9Sstevel@tonic-gate 		    node->avl_child[1] == NULL);
9397c478bd9Sstevel@tonic-gate 	} else {
9407c478bd9Sstevel@tonic-gate 		ASSERT(AVL_XBALANCE(node) <= 0);
9417c478bd9Sstevel@tonic-gate 	}
9427c478bd9Sstevel@tonic-gate 
9437c478bd9Sstevel@tonic-gate done:
9447c478bd9Sstevel@tonic-gate 	if (parent == NULL) {
9457c478bd9Sstevel@tonic-gate 		*cookie = (void *)CHILDBIT;
9467c478bd9Sstevel@tonic-gate 		ASSERT(node == tree->avl_root);
9477c478bd9Sstevel@tonic-gate 	} else {
9487c478bd9Sstevel@tonic-gate 		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));
9497c478bd9Sstevel@tonic-gate 	}
9507c478bd9Sstevel@tonic-gate 
9517c478bd9Sstevel@tonic-gate 	return (AVL_NODE2DATA(node, off));
9527c478bd9Sstevel@tonic-gate }
953