xref: /illumos-gate/usr/src/common/avl/avl.c (revision 6907ca4b)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /*
27  * AVL - generic AVL tree implementation for kernel use
28  *
29  * A complete description of AVL trees can be found in many CS textbooks.
30  *
31  * Here is a very brief overview. An AVL tree is a binary search tree that is
32  * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
33  * any given node, the left and right subtrees are allowed to differ in height
34  * by at most 1 level.
35  *
36  * This relaxation from a perfectly balanced binary tree allows doing
37  * insertion and deletion relatively efficiently. Searching the tree is
38  * still a fast operation, roughly O(log(N)).
39  *
40  * The key to insertion and deletion is a set of tree manipulations called
41  * rotations, which bring unbalanced subtrees back into the semi-balanced state.
42  *
43  * This implementation of AVL trees has the following peculiarities:
44  *
45  *	- The AVL specific data structures are physically embedded as fields
46  *	  in the "using" data structures.  To maintain generality the code
47  *	  must constantly translate between "avl_node_t *" and containing
48  *	  data structure "void *"s by adding/subtracting the avl_offset.
49  *
50  *	- Since the AVL data is always embedded in other structures, there is
51  *	  no locking or memory allocation in the AVL routines. This must be
52  *	  provided for by the enclosing data structure's semantics. Typically,
53  *	  avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
54  *	  exclusive write lock. Other operations require a read lock.
55  *
56  *      - The implementation uses iteration instead of explicit recursion,
57  *	  since it is intended to run on limited size kernel stacks. Since
58  *	  there is no recursion stack present to move "up" in the tree,
59  *	  there is an explicit "parent" link in the avl_node_t.
60  *
61  *      - The left/right children pointers of a node are in an array.
62  *	  In the code, variables (instead of constants) are used to represent
63  *	  left and right indices.  The implementation is written as if it only
64  *	  dealt with left handed manipulations.  By changing the value assigned
65  *	  to "left", the code also works for right handed trees.  The
66  *	  following variables/terms are frequently used:
67  *
68  *		int left;	// 0 when dealing with left children,
69  *				// 1 for dealing with right children
70  *
71  *		int left_heavy;	// -1 when left subtree is taller at some node,
72  *				// +1 when right subtree is taller
73  *
74  *		int right;	// will be the opposite of left (0 or 1)
75  *		int right_heavy;// will be the opposite of left_heavy (-1 or 1)
76  *
77  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
78  *
79  *	  Though it is a little more confusing to read the code, the approach
80  *	  allows using half as much code (and hence cache footprint) for tree
81  *	  manipulations and eliminates many conditional branches.
82  *
83  *	- The avl_index_t is an opaque "cookie" used to find nodes at or
84  *	  adjacent to where a new value would be inserted in the tree. The value
85  *	  is a modified "avl_node_t *".  The bottom bit (normally 0 for a
86  *	  pointer) is set to indicate if that the new node has a value greater
87  *	  than the value of the indicated "avl_node_t *".
88  */
89 
90 #include <sys/types.h>
91 #include <sys/param.h>
92 #include <sys/debug.h>
93 #include <sys/avl.h>
94 #include <sys/cmn_err.h>
95 
96 /*
97  * Small arrays to translate between balance (or diff) values and child indices.
98  *
99  * Code that deals with binary tree data structures will randomly use
100  * left and right children when examining a tree.  C "if()" statements
101  * which evaluate randomly suffer from very poor hardware branch prediction.
102  * In this code we avoid some of the branch mispredictions by using the
103  * following translation arrays. They replace random branches with an
104  * additional memory reference. Since the translation arrays are both very
105  * small the data should remain efficiently in cache.
106  */
107 static const int  avl_child2balance[2]	= {-1, 1};
108 static const int  avl_balance2child[]	= {0, 0, 1};
109 
110 
111 /*
112  * Walk from one node to the previous valued node (ie. an infix walk
113  * towards the left). At any given node we do one of 2 things:
114  *
115  * - If there is a left child, go to it, then to it's rightmost descendant.
116  *
117  * - otherwise we return through parent nodes until we've come from a right
118  *   child.
119  *
120  * Return Value:
121  * NULL - if at the end of the nodes
122  * otherwise next node
123  */
124 void *
125 avl_walk(avl_tree_t *tree, void	*oldnode, int left)
126 {
127 	size_t off = tree->avl_offset;
128 	avl_node_t *node = AVL_DATA2NODE(oldnode, off);
129 	int right = 1 - left;
130 	int was_child;
131 
132 
133 	/*
134 	 * nowhere to walk to if tree is empty
135 	 */
136 	if (node == NULL)
137 		return (NULL);
138 
139 	/*
140 	 * Visit the previous valued node. There are two possibilities:
141 	 *
142 	 * If this node has a left child, go down one left, then all
143 	 * the way right.
144 	 */
145 	if (node->avl_child[left] != NULL) {
146 		for (node = node->avl_child[left];
147 		    node->avl_child[right] != NULL;
148 		    node = node->avl_child[right])
149 			;
150 	/*
151 	 * Otherwise, return thru left children as far as we can.
152 	 */
153 	} else {
154 		for (;;) {
155 			was_child = AVL_XCHILD(node);
156 			node = AVL_XPARENT(node);
157 			if (node == NULL)
158 				return (NULL);
159 			if (was_child == right)
160 				break;
161 		}
162 	}
163 
164 	return (AVL_NODE2DATA(node, off));
165 }
166 
167 /*
168  * Return the lowest valued node in a tree or NULL.
169  * (leftmost child from root of tree)
170  */
171 void *
172 avl_first(avl_tree_t *tree)
173 {
174 	avl_node_t *node;
175 	avl_node_t *prev = NULL;
176 	size_t off = tree->avl_offset;
177 
178 	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
179 		prev = node;
180 
181 	if (prev != NULL)
182 		return (AVL_NODE2DATA(prev, off));
183 	return (NULL);
184 }
185 
186 /*
187  * Return the highest valued node in a tree or NULL.
188  * (rightmost child from root of tree)
189  */
190 void *
191 avl_last(avl_tree_t *tree)
192 {
193 	avl_node_t *node;
194 	avl_node_t *prev = NULL;
195 	size_t off = tree->avl_offset;
196 
197 	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
198 		prev = node;
199 
200 	if (prev != NULL)
201 		return (AVL_NODE2DATA(prev, off));
202 	return (NULL);
203 }
204 
205 /*
206  * Access the node immediately before or after an insertion point.
207  *
208  * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
209  *
210  * Return value:
211  *	NULL: no node in the given direction
212  *	"void *"  of the found tree node
213  */
214 void *
215 avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
216 {
217 	int child = AVL_INDEX2CHILD(where);
218 	avl_node_t *node = AVL_INDEX2NODE(where);
219 	void *data;
220 	size_t off = tree->avl_offset;
221 
222 	if (node == NULL) {
223 		ASSERT(tree->avl_root == NULL);
224 		return (NULL);
225 	}
226 	data = AVL_NODE2DATA(node, off);
227 	if (child != direction)
228 		return (data);
229 
230 	return (avl_walk(tree, data, direction));
231 }
232 
233 
234 /*
235  * Search for the node which contains "value".  The algorithm is a
236  * simple binary tree search.
237  *
238  * return value:
239  *	NULL: the value is not in the AVL tree
240  *		*where (if not NULL)  is set to indicate the insertion point
241  *	"void *"  of the found tree node
242  */
243 void *
244 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where)
245 {
246 	avl_node_t *node;
247 	avl_node_t *prev = NULL;
248 	int child = 0;
249 	int diff;
250 	size_t off = tree->avl_offset;
251 
252 	for (node = tree->avl_root; node != NULL;
253 	    node = node->avl_child[child]) {
254 
255 		prev = node;
256 
257 		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
258 		ASSERT(-1 <= diff && diff <= 1);
259 		if (diff == 0) {
260 #ifdef DEBUG
261 			if (where != NULL)
262 				*where = 0;
263 #endif
264 			return (AVL_NODE2DATA(node, off));
265 		}
266 		child = avl_balance2child[1 + diff];
267 
268 	}
269 
270 	if (where != NULL)
271 		*where = AVL_MKINDEX(prev, child);
272 
273 	return (NULL);
274 }
275 
276 
277 /*
278  * Perform a rotation to restore balance at the subtree given by depth.
279  *
280  * This routine is used by both insertion and deletion. The return value
281  * indicates:
282  *	 0 : subtree did not change height
283  *	!0 : subtree was reduced in height
284  *
285  * The code is written as if handling left rotations, right rotations are
286  * symmetric and handled by swapping values of variables right/left[_heavy]
287  *
288  * On input balance is the "new" balance at "node". This value is either
289  * -2 or +2.
290  */
291 static int
292 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
293 {
294 	int left = !(balance < 0);	/* when balance = -2, left will be 0 */
295 	int right = 1 - left;
296 	int left_heavy = balance >> 1;
297 	int right_heavy = -left_heavy;
298 	avl_node_t *parent = AVL_XPARENT(node);
299 	avl_node_t *child = node->avl_child[left];
300 	avl_node_t *cright;
301 	avl_node_t *gchild;
302 	avl_node_t *gright;
303 	avl_node_t *gleft;
304 	int which_child = AVL_XCHILD(node);
305 	int child_bal = AVL_XBALANCE(child);
306 
307 	/* BEGIN CSTYLED */
308 	/*
309 	 * case 1 : node is overly left heavy, the left child is balanced or
310 	 * also left heavy. This requires the following rotation.
311 	 *
312 	 *                   (node bal:-2)
313 	 *                    /           \
314 	 *                   /             \
315 	 *              (child bal:0 or -1)
316 	 *              /    \
317 	 *             /      \
318 	 *                     cright
319 	 *
320 	 * becomes:
321 	 *
322 	 *              (child bal:1 or 0)
323 	 *              /        \
324 	 *             /          \
325 	 *                        (node bal:-1 or 0)
326 	 *                         /     \
327 	 *                        /       \
328 	 *                     cright
329 	 *
330 	 * we detect this situation by noting that child's balance is not
331 	 * right_heavy.
332 	 */
333 	/* END CSTYLED */
334 	if (child_bal != right_heavy) {
335 
336 		/*
337 		 * compute new balance of nodes
338 		 *
339 		 * If child used to be left heavy (now balanced) we reduced
340 		 * the height of this sub-tree -- used in "return...;" below
341 		 */
342 		child_bal += right_heavy; /* adjust towards right */
343 
344 		/*
345 		 * move "cright" to be node's left child
346 		 */
347 		cright = child->avl_child[right];
348 		node->avl_child[left] = cright;
349 		if (cright != NULL) {
350 			AVL_SETPARENT(cright, node);
351 			AVL_SETCHILD(cright, left);
352 		}
353 
354 		/*
355 		 * move node to be child's right child
356 		 */
357 		child->avl_child[right] = node;
358 		AVL_SETBALANCE(node, -child_bal);
359 		AVL_SETCHILD(node, right);
360 		AVL_SETPARENT(node, child);
361 
362 		/*
363 		 * update the pointer into this subtree
364 		 */
365 		AVL_SETBALANCE(child, child_bal);
366 		AVL_SETCHILD(child, which_child);
367 		AVL_SETPARENT(child, parent);
368 		if (parent != NULL)
369 			parent->avl_child[which_child] = child;
370 		else
371 			tree->avl_root = child;
372 
373 		return (child_bal == 0);
374 	}
375 
376 	/* BEGIN CSTYLED */
377 	/*
378 	 * case 2 : When node is left heavy, but child is right heavy we use
379 	 * a different rotation.
380 	 *
381 	 *                   (node b:-2)
382 	 *                    /   \
383 	 *                   /     \
384 	 *                  /       \
385 	 *             (child b:+1)
386 	 *              /     \
387 	 *             /       \
388 	 *                   (gchild b: != 0)
389 	 *                     /  \
390 	 *                    /    \
391 	 *                 gleft   gright
392 	 *
393 	 * becomes:
394 	 *
395 	 *              (gchild b:0)
396 	 *              /       \
397 	 *             /         \
398 	 *            /           \
399 	 *        (child b:?)   (node b:?)
400 	 *         /  \          /   \
401 	 *        /    \        /     \
402 	 *            gleft   gright
403 	 *
404 	 * computing the new balances is more complicated. As an example:
405 	 *	 if gchild was right_heavy, then child is now left heavy
406 	 *		else it is balanced
407 	 */
408 	/* END CSTYLED */
409 	gchild = child->avl_child[right];
410 	gleft = gchild->avl_child[left];
411 	gright = gchild->avl_child[right];
412 
413 	/*
414 	 * move gright to left child of node and
415 	 *
416 	 * move gleft to right child of node
417 	 */
418 	node->avl_child[left] = gright;
419 	if (gright != NULL) {
420 		AVL_SETPARENT(gright, node);
421 		AVL_SETCHILD(gright, left);
422 	}
423 
424 	child->avl_child[right] = gleft;
425 	if (gleft != NULL) {
426 		AVL_SETPARENT(gleft, child);
427 		AVL_SETCHILD(gleft, right);
428 	}
429 
430 	/*
431 	 * move child to left child of gchild and
432 	 *
433 	 * move node to right child of gchild and
434 	 *
435 	 * fixup parent of all this to point to gchild
436 	 */
437 	balance = AVL_XBALANCE(gchild);
438 	gchild->avl_child[left] = child;
439 	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));
440 	AVL_SETPARENT(child, gchild);
441 	AVL_SETCHILD(child, left);
442 
443 	gchild->avl_child[right] = node;
444 	AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));
445 	AVL_SETPARENT(node, gchild);
446 	AVL_SETCHILD(node, right);
447 
448 	AVL_SETBALANCE(gchild, 0);
449 	AVL_SETPARENT(gchild, parent);
450 	AVL_SETCHILD(gchild, which_child);
451 	if (parent != NULL)
452 		parent->avl_child[which_child] = gchild;
453 	else
454 		tree->avl_root = gchild;
455 
456 	return (1);	/* the new tree is always shorter */
457 }
458 
459 
460 /*
461  * Insert a new node into an AVL tree at the specified (from avl_find()) place.
462  *
463  * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
464  * searches out to the leaf positions.  The avl_index_t indicates the node
465  * which will be the parent of the new node.
466  *
467  * After the node is inserted, a single rotation further up the tree may
468  * be necessary to maintain an acceptable AVL balance.
469  */
470 void
471 avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
472 {
473 	avl_node_t *node;
474 	avl_node_t *parent = AVL_INDEX2NODE(where);
475 	int old_balance;
476 	int new_balance;
477 	int which_child = AVL_INDEX2CHILD(where);
478 	size_t off = tree->avl_offset;
479 
480 	ASSERT(tree);
481 #ifdef _LP64
482 	ASSERT(((uintptr_t)new_data & 0x7) == 0);
483 #endif
484 
485 	node = AVL_DATA2NODE(new_data, off);
486 
487 	/*
488 	 * First, add the node to the tree at the indicated position.
489 	 */
490 	++tree->avl_numnodes;
491 
492 	node->avl_child[0] = NULL;
493 	node->avl_child[1] = NULL;
494 
495 	AVL_SETCHILD(node, which_child);
496 	AVL_SETBALANCE(node, 0);
497 	AVL_SETPARENT(node, parent);
498 	if (parent != NULL) {
499 		ASSERT(parent->avl_child[which_child] == NULL);
500 		parent->avl_child[which_child] = node;
501 	} else {
502 		ASSERT(tree->avl_root == NULL);
503 		tree->avl_root = node;
504 	}
505 	/*
506 	 * Now, back up the tree modifying the balance of all nodes above the
507 	 * insertion point. If we get to a highly unbalanced ancestor, we
508 	 * need to do a rotation.  If we back out of the tree we are done.
509 	 * If we brought any subtree into perfect balance (0), we are also done.
510 	 */
511 	for (;;) {
512 		node = parent;
513 		if (node == NULL)
514 			return;
515 
516 		/*
517 		 * Compute the new balance
518 		 */
519 		old_balance = AVL_XBALANCE(node);
520 		new_balance = old_balance + avl_child2balance[which_child];
521 
522 		/*
523 		 * If we introduced equal balance, then we are done immediately
524 		 */
525 		if (new_balance == 0) {
526 			AVL_SETBALANCE(node, 0);
527 			return;
528 		}
529 
530 		/*
531 		 * If both old and new are not zero we went
532 		 * from -1 to -2 balance, do a rotation.
533 		 */
534 		if (old_balance != 0)
535 			break;
536 
537 		AVL_SETBALANCE(node, new_balance);
538 		parent = AVL_XPARENT(node);
539 		which_child = AVL_XCHILD(node);
540 	}
541 
542 	/*
543 	 * perform a rotation to fix the tree and return
544 	 */
545 	(void) avl_rotation(tree, node, new_balance);
546 }
547 
548 /*
549  * Insert "new_data" in "tree" in the given "direction" either after or
550  * before (AVL_AFTER, AVL_BEFORE) the data "here".
551  *
552  * Insertions can only be done at empty leaf points in the tree, therefore
553  * if the given child of the node is already present we move to either
554  * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since
555  * every other node in the tree is a leaf, this always works.
556  *
557  * To help developers using this interface, we assert that the new node
558  * is correctly ordered at every step of the way in DEBUG kernels.
559  */
560 void
561 avl_insert_here(
562 	avl_tree_t *tree,
563 	void *new_data,
564 	void *here,
565 	int direction)
566 {
567 	avl_node_t *node;
568 	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
569 #ifdef DEBUG
570 	int diff;
571 #endif
572 
573 	ASSERT(tree != NULL);
574 	ASSERT(new_data != NULL);
575 	ASSERT(here != NULL);
576 	ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER);
577 
578 	/*
579 	 * If corresponding child of node is not NULL, go to the neighboring
580 	 * node and reverse the insertion direction.
581 	 */
582 	node = AVL_DATA2NODE(here, tree->avl_offset);
583 
584 #ifdef DEBUG
585 	diff = tree->avl_compar(new_data, here);
586 	ASSERT(-1 <= diff && diff <= 1);
587 	ASSERT(diff != 0);
588 	ASSERT(diff > 0 ? child == 1 : child == 0);
589 #endif
590 
591 	if (node->avl_child[child] != NULL) {
592 		node = node->avl_child[child];
593 		child = 1 - child;
594 		while (node->avl_child[child] != NULL) {
595 #ifdef DEBUG
596 			diff = tree->avl_compar(new_data,
597 			    AVL_NODE2DATA(node, tree->avl_offset));
598 			ASSERT(-1 <= diff && diff <= 1);
599 			ASSERT(diff != 0);
600 			ASSERT(diff > 0 ? child == 1 : child == 0);
601 #endif
602 			node = node->avl_child[child];
603 		}
604 #ifdef DEBUG
605 		diff = tree->avl_compar(new_data,
606 		    AVL_NODE2DATA(node, tree->avl_offset));
607 		ASSERT(-1 <= diff && diff <= 1);
608 		ASSERT(diff != 0);
609 		ASSERT(diff > 0 ? child == 1 : child == 0);
610 #endif
611 	}
612 	ASSERT(node->avl_child[child] == NULL);
613 
614 	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
615 }
616 
617 /*
618  * Add a new node to an AVL tree.
619  */
620 void
621 avl_add(avl_tree_t *tree, void *new_node)
622 {
623 	avl_index_t where;
624 
625 	/*
626 	 * This is unfortunate.  We want to call panic() here, even for
627 	 * non-DEBUG kernels.  In userland, however, we can't depend on anything
628 	 * in libc or else the rtld build process gets confused.  So, all we can
629 	 * do in userland is resort to a normal ASSERT().
630 	 */
631 	if (avl_find(tree, new_node, &where) != NULL)
632 #ifdef _KERNEL
633 		panic("avl_find() succeeded inside avl_add()");
634 #else
635 		ASSERT(0);
636 #endif
637 	avl_insert(tree, new_node, where);
638 }
639 
640 /*
641  * Delete a node from the AVL tree.  Deletion is similar to insertion, but
642  * with 2 complications.
643  *
644  * First, we may be deleting an interior node. Consider the following subtree:
645  *
646  *     d           c            c
647  *    / \         / \          / \
648  *   b   e       b   e        b   e
649  *  / \	        / \          /
650  * a   c       a            a
651  *
652  * When we are deleting node (d), we find and bring up an adjacent valued leaf
653  * node, say (c), to take the interior node's place. In the code this is
654  * handled by temporarily swapping (d) and (c) in the tree and then using
655  * common code to delete (d) from the leaf position.
656  *
657  * Secondly, an interior deletion from a deep tree may require more than one
658  * rotation to fix the balance. This is handled by moving up the tree through
659  * parents and applying rotations as needed. The return value from
660  * avl_rotation() is used to detect when a subtree did not change overall
661  * height due to a rotation.
662  */
663 void
664 avl_remove(avl_tree_t *tree, void *data)
665 {
666 	avl_node_t *delete;
667 	avl_node_t *parent;
668 	avl_node_t *node;
669 	avl_node_t tmp;
670 	int old_balance;
671 	int new_balance;
672 	int left;
673 	int right;
674 	int which_child;
675 	size_t off = tree->avl_offset;
676 
677 	ASSERT(tree);
678 
679 	delete = AVL_DATA2NODE(data, off);
680 
681 	/*
682 	 * Deletion is easiest with a node that has at most 1 child.
683 	 * We swap a node with 2 children with a sequentially valued
684 	 * neighbor node. That node will have at most 1 child. Note this
685 	 * has no effect on the ordering of the remaining nodes.
686 	 *
687 	 * As an optimization, we choose the greater neighbor if the tree
688 	 * is right heavy, otherwise the left neighbor. This reduces the
689 	 * number of rotations needed.
690 	 */
691 	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {
692 
693 		/*
694 		 * choose node to swap from whichever side is taller
695 		 */
696 		old_balance = AVL_XBALANCE(delete);
697 		left = avl_balance2child[old_balance + 1];
698 		right = 1 - left;
699 
700 		/*
701 		 * get to the previous value'd node
702 		 * (down 1 left, as far as possible right)
703 		 */
704 		for (node = delete->avl_child[left];
705 		    node->avl_child[right] != NULL;
706 		    node = node->avl_child[right])
707 			;
708 
709 		/*
710 		 * create a temp placeholder for 'node'
711 		 * move 'node' to delete's spot in the tree
712 		 */
713 		tmp = *node;
714 
715 		*node = *delete;
716 		if (node->avl_child[left] == node)
717 			node->avl_child[left] = &tmp;
718 
719 		parent = AVL_XPARENT(node);
720 		if (parent != NULL)
721 			parent->avl_child[AVL_XCHILD(node)] = node;
722 		else
723 			tree->avl_root = node;
724 		AVL_SETPARENT(node->avl_child[left], node);
725 		AVL_SETPARENT(node->avl_child[right], node);
726 
727 		/*
728 		 * Put tmp where node used to be (just temporary).
729 		 * It always has a parent and at most 1 child.
730 		 */
731 		delete = &tmp;
732 		parent = AVL_XPARENT(delete);
733 		parent->avl_child[AVL_XCHILD(delete)] = delete;
734 		which_child = (delete->avl_child[1] != 0);
735 		if (delete->avl_child[which_child] != NULL)
736 			AVL_SETPARENT(delete->avl_child[which_child], delete);
737 	}
738 
739 
740 	/*
741 	 * Here we know "delete" is at least partially a leaf node. It can
742 	 * be easily removed from the tree.
743 	 */
744 	ASSERT(tree->avl_numnodes > 0);
745 	--tree->avl_numnodes;
746 	parent = AVL_XPARENT(delete);
747 	which_child = AVL_XCHILD(delete);
748 	if (delete->avl_child[0] != NULL)
749 		node = delete->avl_child[0];
750 	else
751 		node = delete->avl_child[1];
752 
753 	/*
754 	 * Connect parent directly to node (leaving out delete).
755 	 */
756 	if (node != NULL) {
757 		AVL_SETPARENT(node, parent);
758 		AVL_SETCHILD(node, which_child);
759 	}
760 	if (parent == NULL) {
761 		tree->avl_root = node;
762 		return;
763 	}
764 	parent->avl_child[which_child] = node;
765 
766 
767 	/*
768 	 * Since the subtree is now shorter, begin adjusting parent balances
769 	 * and performing any needed rotations.
770 	 */
771 	do {
772 
773 		/*
774 		 * Move up the tree and adjust the balance
775 		 *
776 		 * Capture the parent and which_child values for the next
777 		 * iteration before any rotations occur.
778 		 */
779 		node = parent;
780 		old_balance = AVL_XBALANCE(node);
781 		new_balance = old_balance - avl_child2balance[which_child];
782 		parent = AVL_XPARENT(node);
783 		which_child = AVL_XCHILD(node);
784 
785 		/*
786 		 * If a node was in perfect balance but isn't anymore then
787 		 * we can stop, since the height didn't change above this point
788 		 * due to a deletion.
789 		 */
790 		if (old_balance == 0) {
791 			AVL_SETBALANCE(node, new_balance);
792 			break;
793 		}
794 
795 		/*
796 		 * If the new balance is zero, we don't need to rotate
797 		 * else
798 		 * need a rotation to fix the balance.
799 		 * If the rotation doesn't change the height
800 		 * of the sub-tree we have finished adjusting.
801 		 */
802 		if (new_balance == 0)
803 			AVL_SETBALANCE(node, new_balance);
804 		else if (!avl_rotation(tree, node, new_balance))
805 			break;
806 	} while (parent != NULL);
807 }
808 
809 #define	AVL_REINSERT(tree, obj)		\
810 	avl_remove((tree), (obj));	\
811 	avl_add((tree), (obj))
812 
813 boolean_t
814 avl_update_lt(avl_tree_t *t, void *obj)
815 {
816 	void *neighbor;
817 
818 	ASSERT(((neighbor = AVL_NEXT(t, obj)) == NULL) ||
819 	    (t->avl_compar(obj, neighbor) <= 0));
820 
821 	neighbor = AVL_PREV(t, obj);
822 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
823 		AVL_REINSERT(t, obj);
824 		return (B_TRUE);
825 	}
826 
827 	return (B_FALSE);
828 }
829 
830 boolean_t
831 avl_update_gt(avl_tree_t *t, void *obj)
832 {
833 	void *neighbor;
834 
835 	ASSERT(((neighbor = AVL_PREV(t, obj)) == NULL) ||
836 	    (t->avl_compar(obj, neighbor) >= 0));
837 
838 	neighbor = AVL_NEXT(t, obj);
839 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
840 		AVL_REINSERT(t, obj);
841 		return (B_TRUE);
842 	}
843 
844 	return (B_FALSE);
845 }
846 
847 boolean_t
848 avl_update(avl_tree_t *t, void *obj)
849 {
850 	void *neighbor;
851 
852 	neighbor = AVL_PREV(t, obj);
853 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
854 		AVL_REINSERT(t, obj);
855 		return (B_TRUE);
856 	}
857 
858 	neighbor = AVL_NEXT(t, obj);
859 	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
860 		AVL_REINSERT(t, obj);
861 		return (B_TRUE);
862 	}
863 
864 	return (B_FALSE);
865 }
866 
867 /*
868  * initialize a new AVL tree
869  */
870 void
871 avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
872     size_t size, size_t offset)
873 {
874 	ASSERT(tree);
875 	ASSERT(compar);
876 	ASSERT(size > 0);
877 	ASSERT(size >= offset + sizeof (avl_node_t));
878 #ifdef _LP64
879 	ASSERT((offset & 0x7) == 0);
880 #endif
881 
882 	tree->avl_compar = compar;
883 	tree->avl_root = NULL;
884 	tree->avl_numnodes = 0;
885 	tree->avl_size = size;
886 	tree->avl_offset = offset;
887 }
888 
889 /*
890  * Delete a tree.
891  */
892 /* ARGSUSED */
893 void
894 avl_destroy(avl_tree_t *tree)
895 {
896 	ASSERT(tree);
897 	ASSERT(tree->avl_numnodes == 0);
898 	ASSERT(tree->avl_root == NULL);
899 }
900 
901 
902 /*
903  * Return the number of nodes in an AVL tree.
904  */
905 ulong_t
906 avl_numnodes(avl_tree_t *tree)
907 {
908 	ASSERT(tree);
909 	return (tree->avl_numnodes);
910 }
911 
912 boolean_t
913 avl_is_empty(avl_tree_t *tree)
914 {
915 	ASSERT(tree);
916 	return (tree->avl_numnodes == 0);
917 }
918 
919 #define	CHILDBIT	(1L)
920 
921 /*
922  * Post-order tree walk used to visit all tree nodes and destroy the tree
923  * in post order. This is used for destroying a tree without paying any cost
924  * for rebalancing it.
925  *
926  * example:
927  *
928  *	void *cookie = NULL;
929  *	my_data_t *node;
930  *
931  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
932  *		free(node);
933  *	avl_destroy(tree);
934  *
935  * The cookie is really an avl_node_t to the current node's parent and
936  * an indication of which child you looked at last.
937  *
938  * On input, a cookie value of CHILDBIT indicates the tree is done.
939  */
940 void *
941 avl_destroy_nodes(avl_tree_t *tree, void **cookie)
942 {
943 	avl_node_t	*node;
944 	avl_node_t	*parent;
945 	int		child;
946 	void		*first;
947 	size_t		off = tree->avl_offset;
948 
949 	/*
950 	 * Initial calls go to the first node or it's right descendant.
951 	 */
952 	if (*cookie == NULL) {
953 		first = avl_first(tree);
954 
955 		/*
956 		 * deal with an empty tree
957 		 */
958 		if (first == NULL) {
959 			*cookie = (void *)CHILDBIT;
960 			return (NULL);
961 		}
962 
963 		node = AVL_DATA2NODE(first, off);
964 		parent = AVL_XPARENT(node);
965 		goto check_right_side;
966 	}
967 
968 	/*
969 	 * If there is no parent to return to we are done.
970 	 */
971 	parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT);
972 	if (parent == NULL) {
973 		if (tree->avl_root != NULL) {
974 			ASSERT(tree->avl_numnodes == 1);
975 			tree->avl_root = NULL;
976 			tree->avl_numnodes = 0;
977 		}
978 		return (NULL);
979 	}
980 
981 	/*
982 	 * Remove the child pointer we just visited from the parent and tree.
983 	 */
984 	child = (uintptr_t)(*cookie) & CHILDBIT;
985 	parent->avl_child[child] = NULL;
986 	ASSERT(tree->avl_numnodes > 1);
987 	--tree->avl_numnodes;
988 
989 	/*
990 	 * If we just did a right child or there isn't one, go up to parent.
991 	 */
992 	if (child == 1 || parent->avl_child[1] == NULL) {
993 		node = parent;
994 		parent = AVL_XPARENT(parent);
995 		goto done;
996 	}
997 
998 	/*
999 	 * Do parent's right child, then leftmost descendent.
1000 	 */
1001 	node = parent->avl_child[1];
1002 	while (node->avl_child[0] != NULL) {
1003 		parent = node;
1004 		node = node->avl_child[0];
1005 	}
1006 
1007 	/*
1008 	 * If here, we moved to a left child. It may have one
1009 	 * child on the right (when balance == +1).
1010 	 */
1011 check_right_side:
1012 	if (node->avl_child[1] != NULL) {
1013 		ASSERT(AVL_XBALANCE(node) == 1);
1014 		parent = node;
1015 		node = node->avl_child[1];
1016 		ASSERT(node->avl_child[0] == NULL &&
1017 		    node->avl_child[1] == NULL);
1018 	} else {
1019 		ASSERT(AVL_XBALANCE(node) <= 0);
1020 	}
1021 
1022 done:
1023 	if (parent == NULL) {
1024 		*cookie = (void *)CHILDBIT;
1025 		ASSERT(node == tree->avl_root);
1026 	} else {
1027 		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));
1028 	}
1029 
1030 	return (AVL_NODE2DATA(node, off));
1031 }
1032