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