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