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