]>
git.proxmox.com Git - mirror_zfs.git/blob - module/avl/avl.c
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.
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.
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]
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
27 * AVL - generic AVL tree implementation for kernel use
29 * A complete description of AVL trees can be found in many CS textbooks.
31 * Here is a very brief overview. An AVL tree is a binary search tree that is
32 * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
33 * any given node, the left and right subtrees are allowed to differ in height
36 * This relaxation from a perfectly balanced binary tree allows doing
37 * insertion and deletion relatively efficiently. Searching the tree is
38 * still a fast operation, roughly O(log(N)).
40 * The key to insertion and deletion is a set of tree maniuplations called
41 * rotations, which bring unbalanced subtrees back into the semi-balanced state.
43 * This implementation of AVL trees has the following peculiarities:
45 * - The AVL specific data structures are physically embedded as fields
46 * in the "using" data structures. To maintain generality the code
47 * must constantly translate between "avl_node_t *" and containing
48 * data structure "void *"s by adding/subracting the avl_offset.
50 * - Since the AVL data is always embedded in other structures, there is
51 * no locking or memory allocation in the AVL routines. This must be
52 * provided for by the enclosing data structure's semantics. Typically,
53 * avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
54 * exclusive write lock. Other operations require a read lock.
56 * - The implementation uses iteration instead of explicit recursion,
57 * since it is intended to run on limited size kernel stacks. Since
58 * there is no recursion stack present to move "up" in the tree,
59 * there is an explicit "parent" link in the avl_node_t.
61 * - The left/right children pointers of a node are in an array.
62 * In the code, variables (instead of constants) are used to represent
63 * left and right indices. The implementation is written as if it only
64 * dealt with left handed manipulations. By changing the value assigned
65 * to "left", the code also works for right handed trees. The
66 * following variables/terms are frequently used:
68 * int left; // 0 when dealing with left children,
69 * // 1 for dealing with right children
71 * int left_heavy; // -1 when left subtree is taller at some node,
72 * // +1 when right subtree is taller
74 * int right; // will be the opposite of left (0 or 1)
75 * int right_heavy;// will be the opposite of left_heavy (-1 or 1)
77 * int direction; // 0 for "<" (ie. left child); 1 for ">" (right)
79 * Though it is a little more confusing to read the code, the approach
80 * allows using half as much code (and hence cache footprint) for tree
81 * manipulations and eliminates many conditional branches.
83 * - The avl_index_t is an opaque "cookie" used to find nodes at or
84 * adjacent to where a new value would be inserted in the tree. The value
85 * is a modified "avl_node_t *". The bottom bit (normally 0 for a
86 * pointer) is set to indicate if that the new node has a value greater
87 * than the value of the indicated "avl_node_t *".
90 #include <sys/types.h>
91 #include <sys/param.h>
92 #include <sys/debug.h>
94 #include <sys/cmn_err.h>
97 * Small arrays to translate between balance (or diff) values and child indeces.
99 * Code that deals with binary tree data structures will randomly use
100 * left and right children when examining a tree. C "if()" statements
101 * which evaluate randomly suffer from very poor hardware branch prediction.
102 * In this code we avoid some of the branch mispredictions by using the
103 * following translation arrays. They replace random branches with an
104 * additional memory reference. Since the translation arrays are both very
105 * small the data should remain efficiently in cache.
107 static const int avl_child2balance
[2] = {-1, 1};
108 static const int avl_balance2child
[] = {0, 0, 1};
112 * Walk from one node to the previous valued node (ie. an infix walk
113 * towards the left). At any given node we do one of 2 things:
115 * - If there is a left child, go to it, then to it's rightmost descendant.
117 * - otherwise we return thru parent nodes until we've come from a right child.
120 * NULL - if at the end of the nodes
121 * otherwise next node
124 avl_walk(avl_tree_t
*tree
, void *oldnode
, int left
)
126 size_t off
= tree
->avl_offset
;
127 avl_node_t
*node
= AVL_DATA2NODE(oldnode
, off
);
128 int right
= 1 - left
;
133 * nowhere to walk to if tree is empty
139 * Visit the previous valued node. There are two possibilities:
141 * If this node has a left child, go down one left, then all
144 if (node
->avl_child
[left
] != NULL
) {
145 for (node
= node
->avl_child
[left
];
146 node
->avl_child
[right
] != NULL
;
147 node
= node
->avl_child
[right
])
150 * Otherwise, return thru left children as far as we can.
154 was_child
= AVL_XCHILD(node
);
155 node
= AVL_XPARENT(node
);
158 if (was_child
== right
)
163 return (AVL_NODE2DATA(node
, off
));
167 * Return the lowest valued node in a tree or NULL.
168 * (leftmost child from root of tree)
171 avl_first(avl_tree_t
*tree
)
174 avl_node_t
*prev
= NULL
;
175 size_t off
= tree
->avl_offset
;
177 for (node
= tree
->avl_root
; node
!= NULL
; node
= node
->avl_child
[0])
181 return (AVL_NODE2DATA(prev
, off
));
186 * Return the highest valued node in a tree or NULL.
187 * (rightmost child from root of tree)
190 avl_last(avl_tree_t
*tree
)
193 avl_node_t
*prev
= NULL
;
194 size_t off
= tree
->avl_offset
;
196 for (node
= tree
->avl_root
; node
!= NULL
; node
= node
->avl_child
[1])
200 return (AVL_NODE2DATA(prev
, off
));
205 * Access the node immediately before or after an insertion point.
207 * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
210 * NULL: no node in the given direction
211 * "void *" of the found tree node
214 avl_nearest(avl_tree_t
*tree
, avl_index_t where
, int direction
)
216 int child
= AVL_INDEX2CHILD(where
);
217 avl_node_t
*node
= AVL_INDEX2NODE(where
);
219 size_t off
= tree
->avl_offset
;
222 ASSERT(tree
->avl_root
== NULL
);
225 data
= AVL_NODE2DATA(node
, off
);
226 if (child
!= direction
)
229 return (avl_walk(tree
, data
, direction
));
234 * Search for the node which contains "value". The algorithm is a
235 * simple binary tree search.
238 * NULL: the value is not in the AVL tree
239 * *where (if not NULL) is set to indicate the insertion point
240 * "void *" of the found tree node
243 avl_find(avl_tree_t
*tree
, const void *value
, avl_index_t
*where
)
246 avl_node_t
*prev
= NULL
;
249 size_t off
= tree
->avl_offset
;
251 for (node
= tree
->avl_root
; node
!= NULL
;
252 node
= node
->avl_child
[child
]) {
256 diff
= tree
->avl_compar(value
, AVL_NODE2DATA(node
, off
));
257 ASSERT(-1 <= diff
&& diff
<= 1);
263 return (AVL_NODE2DATA(node
, off
));
265 child
= avl_balance2child
[1 + diff
];
270 *where
= AVL_MKINDEX(prev
, child
);
277 * Perform a rotation to restore balance at the subtree given by depth.
279 * This routine is used by both insertion and deletion. The return value
281 * 0 : subtree did not change height
282 * !0 : subtree was reduced in height
284 * The code is written as if handling left rotations, right rotations are
285 * symmetric and handled by swapping values of variables right/left[_heavy]
287 * On input balance is the "new" balance at "node". This value is either
291 avl_rotation(avl_tree_t
*tree
, avl_node_t
*node
, int balance
)
293 int left
= !(balance
< 0); /* when balance = -2, left will be 0 */
294 int right
= 1 - left
;
295 int left_heavy
= balance
>> 1;
296 int right_heavy
= -left_heavy
;
297 avl_node_t
*parent
= AVL_XPARENT(node
);
298 avl_node_t
*child
= node
->avl_child
[left
];
303 int which_child
= AVL_XCHILD(node
);
304 int child_bal
= AVL_XBALANCE(child
);
308 * case 1 : node is overly left heavy, the left child is balanced or
309 * also left heavy. This requires the following rotation.
314 * (child bal:0 or -1)
329 * we detect this situation by noting that child's balance is not
333 if (child_bal
!= right_heavy
) {
336 * compute new balance of nodes
338 * If child used to be left heavy (now balanced) we reduced
339 * the height of this sub-tree -- used in "return...;" below
341 child_bal
+= right_heavy
; /* adjust towards right */
344 * move "cright" to be node's left child
346 cright
= child
->avl_child
[right
];
347 node
->avl_child
[left
] = cright
;
348 if (cright
!= NULL
) {
349 AVL_SETPARENT(cright
, node
);
350 AVL_SETCHILD(cright
, left
);
354 * move node to be child's right child
356 child
->avl_child
[right
] = node
;
357 AVL_SETBALANCE(node
, -child_bal
);
358 AVL_SETCHILD(node
, right
);
359 AVL_SETPARENT(node
, child
);
362 * update the pointer into this subtree
364 AVL_SETBALANCE(child
, child_bal
);
365 AVL_SETCHILD(child
, which_child
);
366 AVL_SETPARENT(child
, parent
);
368 parent
->avl_child
[which_child
] = child
;
370 tree
->avl_root
= child
;
372 return (child_bal
== 0);
377 * case 2 : When node is left heavy, but child is right heavy we use
378 * a different rotation.
398 * (child b:?) (node b:?)
403 * computing the new balances is more complicated. As an example:
404 * if gchild was right_heavy, then child is now left heavy
405 * else it is balanced
408 gchild
= child
->avl_child
[right
];
409 gleft
= gchild
->avl_child
[left
];
410 gright
= gchild
->avl_child
[right
];
413 * move gright to left child of node and
415 * move gleft to right child of node
417 node
->avl_child
[left
] = gright
;
418 if (gright
!= NULL
) {
419 AVL_SETPARENT(gright
, node
);
420 AVL_SETCHILD(gright
, left
);
423 child
->avl_child
[right
] = gleft
;
425 AVL_SETPARENT(gleft
, child
);
426 AVL_SETCHILD(gleft
, right
);
430 * move child to left child of gchild and
432 * move node to right child of gchild and
434 * fixup parent of all this to point to gchild
436 balance
= AVL_XBALANCE(gchild
);
437 gchild
->avl_child
[left
] = child
;
438 AVL_SETBALANCE(child
, (balance
== right_heavy
? left_heavy
: 0));
439 AVL_SETPARENT(child
, gchild
);
440 AVL_SETCHILD(child
, left
);
442 gchild
->avl_child
[right
] = node
;
443 AVL_SETBALANCE(node
, (balance
== left_heavy
? right_heavy
: 0));
444 AVL_SETPARENT(node
, gchild
);
445 AVL_SETCHILD(node
, right
);
447 AVL_SETBALANCE(gchild
, 0);
448 AVL_SETPARENT(gchild
, parent
);
449 AVL_SETCHILD(gchild
, which_child
);
451 parent
->avl_child
[which_child
] = gchild
;
453 tree
->avl_root
= gchild
;
455 return (1); /* the new tree is always shorter */
460 * Insert a new node into an AVL tree at the specified (from avl_find()) place.
462 * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
463 * searches out to the leaf positions. The avl_index_t indicates the node
464 * which will be the parent of the new node.
466 * After the node is inserted, a single rotation further up the tree may
467 * be necessary to maintain an acceptable AVL balance.
470 avl_insert(avl_tree_t
*tree
, void *new_data
, avl_index_t where
)
473 avl_node_t
*parent
= AVL_INDEX2NODE(where
);
476 int which_child
= AVL_INDEX2CHILD(where
);
477 size_t off
= tree
->avl_offset
;
481 ASSERT(((uintptr_t)new_data
& 0x7) == 0);
484 node
= AVL_DATA2NODE(new_data
, off
);
487 * First, add the node to the tree at the indicated position.
489 ++tree
->avl_numnodes
;
491 node
->avl_child
[0] = NULL
;
492 node
->avl_child
[1] = NULL
;
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
;
501 ASSERT(tree
->avl_root
== NULL
);
502 tree
->avl_root
= node
;
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.
516 * Compute the new balance
518 old_balance
= AVL_XBALANCE(node
);
519 new_balance
= old_balance
+ avl_child2balance
[which_child
];
522 * If we introduced equal balance, then we are done immediately
524 if (new_balance
== 0) {
525 AVL_SETBALANCE(node
, 0);
530 * If both old and new are not zero we went
531 * from -1 to -2 balance, do a rotation.
533 if (old_balance
!= 0)
536 AVL_SETBALANCE(node
, new_balance
);
537 parent
= AVL_XPARENT(node
);
538 which_child
= AVL_XCHILD(node
);
542 * perform a rotation to fix the tree and return
544 (void) avl_rotation(tree
, node
, new_balance
);
548 * Insert "new_data" in "tree" in the given "direction" either after or
549 * before (AVL_AFTER, AVL_BEFORE) the data "here".
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.
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.
567 int child
= direction
; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
572 ASSERT(tree
!= NULL
);
573 ASSERT(new_data
!= NULL
);
574 ASSERT(here
!= NULL
);
575 ASSERT(direction
== AVL_BEFORE
|| direction
== AVL_AFTER
);
578 * If corresponding child of node is not NULL, go to the neighboring
579 * node and reverse the insertion direction.
581 node
= AVL_DATA2NODE(here
, tree
->avl_offset
);
584 diff
= tree
->avl_compar(new_data
, here
);
585 ASSERT(-1 <= diff
&& diff
<= 1);
587 ASSERT(diff
> 0 ? child
== 1 : child
== 0);
590 if (node
->avl_child
[child
] != NULL
) {
591 node
= node
->avl_child
[child
];
593 while (node
->avl_child
[child
] != NULL
) {
595 diff
= tree
->avl_compar(new_data
,
596 AVL_NODE2DATA(node
, tree
->avl_offset
));
597 ASSERT(-1 <= diff
&& diff
<= 1);
599 ASSERT(diff
> 0 ? child
== 1 : child
== 0);
601 node
= node
->avl_child
[child
];
604 diff
= tree
->avl_compar(new_data
,
605 AVL_NODE2DATA(node
, tree
->avl_offset
));
606 ASSERT(-1 <= diff
&& diff
<= 1);
608 ASSERT(diff
> 0 ? child
== 1 : child
== 0);
611 ASSERT(node
->avl_child
[child
] == NULL
);
613 avl_insert(tree
, new_data
, AVL_MKINDEX(node
, child
));
617 * Add a new node to an AVL tree.
620 avl_add(avl_tree_t
*tree
, void *new_node
)
625 * This is unfortunate. We want to call panic() here, even for
626 * non-DEBUG kernels. In userland, however, we can't depend on anything
627 * in libc or else the rtld build process gets confused. So, all we can
628 * do in userland is resort to a normal ASSERT().
630 if (avl_find(tree
, new_node
, &where
) != NULL
)
632 panic("avl_find() succeeded inside avl_add()");
636 avl_insert(tree
, new_node
, where
);
640 * Delete a node from the AVL tree. Deletion is similar to insertion, but
641 * with 2 complications.
643 * First, we may be deleting an interior node. Consider the following subtree:
651 * When we are deleting node (d), we find and bring up an adjacent valued leaf
652 * node, say (c), to take the interior node's place. In the code this is
653 * handled by temporarily swapping (d) and (c) in the tree and then using
654 * common code to delete (d) from the leaf position.
656 * Secondly, an interior deletion from a deep tree may require more than one
657 * rotation to fix the balance. This is handled by moving up the tree through
658 * parents and applying rotations as needed. The return value from
659 * avl_rotation() is used to detect when a subtree did not change overall
660 * height due to a rotation.
663 avl_remove(avl_tree_t
*tree
, void *data
)
674 size_t off
= tree
->avl_offset
;
678 delete = AVL_DATA2NODE(data
, off
);
681 * Deletion is easiest with a node that has at most 1 child.
682 * We swap a node with 2 children with a sequentially valued
683 * neighbor node. That node will have at most 1 child. Note this
684 * has no effect on the ordering of the remaining nodes.
686 * As an optimization, we choose the greater neighbor if the tree
687 * is right heavy, otherwise the left neighbor. This reduces the
688 * number of rotations needed.
690 if (delete->avl_child
[0] != NULL
&& delete->avl_child
[1] != NULL
) {
693 * choose node to swap from whichever side is taller
695 old_balance
= AVL_XBALANCE(delete);
696 left
= avl_balance2child
[old_balance
+ 1];
700 * get to the previous value'd node
701 * (down 1 left, as far as possible right)
703 for (node
= delete->avl_child
[left
];
704 node
->avl_child
[right
] != NULL
;
705 node
= node
->avl_child
[right
])
709 * create a temp placeholder for 'node'
710 * move 'node' to delete's spot in the tree
715 if (node
->avl_child
[left
] == node
)
716 node
->avl_child
[left
] = &tmp
;
718 parent
= AVL_XPARENT(node
);
720 parent
->avl_child
[AVL_XCHILD(node
)] = node
;
722 tree
->avl_root
= node
;
723 AVL_SETPARENT(node
->avl_child
[left
], node
);
724 AVL_SETPARENT(node
->avl_child
[right
], node
);
727 * Put tmp where node used to be (just temporary).
728 * It always has a parent and at most 1 child.
731 parent
= AVL_XPARENT(delete);
732 parent
->avl_child
[AVL_XCHILD(delete)] = delete;
733 which_child
= (delete->avl_child
[1] != 0);
734 if (delete->avl_child
[which_child
] != NULL
)
735 AVL_SETPARENT(delete->avl_child
[which_child
], delete);
740 * Here we know "delete" is at least partially a leaf node. It can
741 * be easily removed from the tree.
743 ASSERT(tree
->avl_numnodes
> 0);
744 --tree
->avl_numnodes
;
745 parent
= AVL_XPARENT(delete);
746 which_child
= AVL_XCHILD(delete);
747 if (delete->avl_child
[0] != NULL
)
748 node
= delete->avl_child
[0];
750 node
= delete->avl_child
[1];
753 * Connect parent directly to node (leaving out delete).
756 AVL_SETPARENT(node
, parent
);
757 AVL_SETCHILD(node
, which_child
);
759 if (parent
== NULL
) {
760 tree
->avl_root
= node
;
763 parent
->avl_child
[which_child
] = node
;
767 * Since the subtree is now shorter, begin adjusting parent balances
768 * and performing any needed rotations.
773 * Move up the tree and adjust the balance
775 * Capture the parent and which_child values for the next
776 * iteration before any rotations occur.
779 old_balance
= AVL_XBALANCE(node
);
780 new_balance
= old_balance
- avl_child2balance
[which_child
];
781 parent
= AVL_XPARENT(node
);
782 which_child
= AVL_XCHILD(node
);
785 * If a node was in perfect balance but isn't anymore then
786 * we can stop, since the height didn't change above this point
789 if (old_balance
== 0) {
790 AVL_SETBALANCE(node
, new_balance
);
795 * If the new balance is zero, we don't need to rotate
797 * need a rotation to fix the balance.
798 * If the rotation doesn't change the height
799 * of the sub-tree we have finished adjusting.
801 if (new_balance
== 0)
802 AVL_SETBALANCE(node
, new_balance
);
803 else if (!avl_rotation(tree
, node
, new_balance
))
805 } while (parent
!= NULL
);
808 #define AVL_REINSERT(tree, obj) \
809 avl_remove((tree), (obj)); \
810 avl_add((tree), (obj))
813 avl_update_lt(avl_tree_t
*t
, void *obj
)
817 ASSERT(((neighbor
= AVL_NEXT(t
, obj
)) == NULL
) ||
818 (t
->avl_compar(obj
, neighbor
) <= 0));
820 neighbor
= AVL_PREV(t
, obj
);
821 if ((neighbor
!= NULL
) && (t
->avl_compar(obj
, neighbor
) < 0)) {
822 AVL_REINSERT(t
, obj
);
830 avl_update_gt(avl_tree_t
*t
, void *obj
)
834 ASSERT(((neighbor
= AVL_PREV(t
, obj
)) == NULL
) ||
835 (t
->avl_compar(obj
, neighbor
) >= 0));
837 neighbor
= AVL_NEXT(t
, obj
);
838 if ((neighbor
!= NULL
) && (t
->avl_compar(obj
, neighbor
) > 0)) {
839 AVL_REINSERT(t
, obj
);
847 avl_update(avl_tree_t
*t
, void *obj
)
851 neighbor
= AVL_PREV(t
, obj
);
852 if ((neighbor
!= NULL
) && (t
->avl_compar(obj
, neighbor
) < 0)) {
853 AVL_REINSERT(t
, obj
);
857 neighbor
= AVL_NEXT(t
, obj
);
858 if ((neighbor
!= NULL
) && (t
->avl_compar(obj
, neighbor
) > 0)) {
859 AVL_REINSERT(t
, obj
);
867 * initialize a new AVL tree
870 avl_create(avl_tree_t
*tree
, int (*compar
) (const void *, const void *),
871 size_t size
, size_t offset
)
876 ASSERT(size
>= offset
+ sizeof (avl_node_t
));
878 ASSERT((offset
& 0x7) == 0);
881 tree
->avl_compar
= compar
;
882 tree
->avl_root
= NULL
;
883 tree
->avl_numnodes
= 0;
884 tree
->avl_size
= size
;
885 tree
->avl_offset
= offset
;
893 avl_destroy(avl_tree_t
*tree
)
896 ASSERT(tree
->avl_numnodes
== 0);
897 ASSERT(tree
->avl_root
== NULL
);
902 * Return the number of nodes in an AVL tree.
905 avl_numnodes(avl_tree_t
*tree
)
908 return (tree
->avl_numnodes
);
912 avl_is_empty(avl_tree_t
*tree
)
915 return (tree
->avl_numnodes
== 0);
918 #define CHILDBIT (1L)
921 * Post-order tree walk used to visit all tree nodes and destroy the tree
922 * in post order. This is used for destroying a tree w/o paying any cost
923 * for rebalancing it.
927 * void *cookie = NULL;
930 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
934 * The cookie is really an avl_node_t to the current node's parent and
935 * an indication of which child you looked at last.
937 * On input, a cookie value of CHILDBIT indicates the tree is done.
940 avl_destroy_nodes(avl_tree_t
*tree
, void **cookie
)
946 size_t off
= tree
->avl_offset
;
949 * Initial calls go to the first node or it's right descendant.
951 if (*cookie
== NULL
) {
952 first
= avl_first(tree
);
955 * deal with an empty tree
958 *cookie
= (void *)CHILDBIT
;
962 node
= AVL_DATA2NODE(first
, off
);
963 parent
= AVL_XPARENT(node
);
964 goto check_right_side
;
968 * If there is no parent to return to we are done.
970 parent
= (avl_node_t
*)((uintptr_t)(*cookie
) & ~CHILDBIT
);
971 if (parent
== NULL
) {
972 if (tree
->avl_root
!= NULL
) {
973 ASSERT(tree
->avl_numnodes
== 1);
974 tree
->avl_root
= NULL
;
975 tree
->avl_numnodes
= 0;
981 * Remove the child pointer we just visited from the parent and tree.
983 child
= (uintptr_t)(*cookie
) & CHILDBIT
;
984 parent
->avl_child
[child
] = NULL
;
985 ASSERT(tree
->avl_numnodes
> 1);
986 --tree
->avl_numnodes
;
989 * If we just did a right child or there isn't one, go up to parent.
991 if (child
== 1 || parent
->avl_child
[1] == NULL
) {
993 parent
= AVL_XPARENT(parent
);
998 * Do parent's right child, then leftmost descendent.
1000 node
= parent
->avl_child
[1];
1001 while (node
->avl_child
[0] != NULL
) {
1003 node
= node
->avl_child
[0];
1007 * If here, we moved to a left child. It may have one
1008 * child on the right (when balance == +1).
1011 if (node
->avl_child
[1] != NULL
) {
1012 ASSERT(AVL_XBALANCE(node
) == 1);
1014 node
= node
->avl_child
[1];
1015 ASSERT(node
->avl_child
[0] == NULL
&&
1016 node
->avl_child
[1] == NULL
);
1018 ASSERT(AVL_XBALANCE(node
) <= 0);
1022 if (parent
== NULL
) {
1023 *cookie
= (void *)CHILDBIT
;
1024 ASSERT(node
== tree
->avl_root
);
1026 *cookie
= (void *)((uintptr_t)parent
| AVL_XCHILD(node
));
1029 return (AVL_NODE2DATA(node
, off
));
1032 #if defined(_KERNEL) && defined(HAVE_SPL)
1034 static int avl_init(void) { return 0; }
1035 static int avl_fini(void) { return 0; }
1037 spl_module_init(avl_init
);
1038 spl_module_exit(avl_fini
);
1040 MODULE_DESCRIPTION("Generic AVL tree implementation");
1041 MODULE_AUTHOR(ZFS_META_AUTHOR
);
1042 MODULE_LICENSE(ZFS_META_LICENSE
);
1044 EXPORT_SYMBOL(avl_create
);
1045 EXPORT_SYMBOL(avl_find
);
1046 EXPORT_SYMBOL(avl_insert
);
1047 EXPORT_SYMBOL(avl_insert_here
);
1048 EXPORT_SYMBOL(avl_walk
);
1049 EXPORT_SYMBOL(avl_first
);
1050 EXPORT_SYMBOL(avl_last
);
1051 EXPORT_SYMBOL(avl_nearest
);
1052 EXPORT_SYMBOL(avl_add
);
1053 EXPORT_SYMBOL(avl_remove
);
1054 EXPORT_SYMBOL(avl_numnodes
);
1055 EXPORT_SYMBOL(avl_destroy_nodes
);
1056 EXPORT_SYMBOL(avl_destroy
);