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