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