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 }