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