]>
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 * Copyright 2015 Nexenta Systems, Inc. All rights reserved.
28 * Copyright (c) 2015 by Delphix. All rights reserved.
32 * AVL - generic AVL tree implementation for kernel use
34 * A complete description of AVL trees can be found in many CS textbooks.
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
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)).
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.
48 * This implementation of AVL trees has the following peculiarities:
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.
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.
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.
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:
73 * int left; // 0 when dealing with left children,
74 * // 1 for dealing with right children
76 * int left_heavy; // -1 when left subtree is taller at some node,
77 * // +1 when right subtree is taller
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)
82 * int direction; // 0 for "<" (ie. left child); 1 for ">" (right)
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.
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 *".
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.
101 #include <sys/types.h>
102 #include <sys/param.h>
103 #include <sys/debug.h>
105 #include <sys/cmn_err.h>
108 * Small arrays to translate between balance (or diff) values and child indices.
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.
118 static const int avl_child2balance
[2] = {-1, 1};
119 static const int avl_balance2child
[] = {0, 0, 1};
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:
126 * - If there is a left child, go to it, then to it's rightmost descendant.
128 * - otherwise we return through parent nodes until we've come from a right
132 * NULL - if at the end of the nodes
133 * otherwise next node
136 avl_walk(avl_tree_t
*tree
, void *oldnode
, int left
)
138 size_t off
= tree
->avl_offset
;
139 avl_node_t
*node
= AVL_DATA2NODE(oldnode
, off
);
140 int right
= 1 - left
;
145 * nowhere to walk to if tree is empty
151 * Visit the previous valued node. There are two possibilities:
153 * If this node has a left child, go down one left, then all
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
])
162 * Otherwise, return thru left children as far as we can.
166 was_child
= AVL_XCHILD(node
);
167 node
= AVL_XPARENT(node
);
170 if (was_child
== right
)
175 return (AVL_NODE2DATA(node
, off
));
179 * Return the lowest valued node in a tree or NULL.
180 * (leftmost child from root of tree)
183 avl_first(avl_tree_t
*tree
)
186 avl_node_t
*prev
= NULL
;
187 size_t off
= tree
->avl_offset
;
189 for (node
= tree
->avl_root
; node
!= NULL
; node
= node
->avl_child
[0])
193 return (AVL_NODE2DATA(prev
, off
));
198 * Return the highest valued node in a tree or NULL.
199 * (rightmost child from root of tree)
202 avl_last(avl_tree_t
*tree
)
205 avl_node_t
*prev
= NULL
;
206 size_t off
= tree
->avl_offset
;
208 for (node
= tree
->avl_root
; node
!= NULL
; node
= node
->avl_child
[1])
212 return (AVL_NODE2DATA(prev
, off
));
217 * Access the node immediately before or after an insertion point.
219 * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
222 * NULL: no node in the given direction
223 * "void *" of the found tree node
226 avl_nearest(avl_tree_t
*tree
, avl_index_t where
, int direction
)
228 int child
= AVL_INDEX2CHILD(where
);
229 avl_node_t
*node
= AVL_INDEX2NODE(where
);
231 size_t off
= tree
->avl_offset
;
234 ASSERT(tree
->avl_root
== NULL
);
237 data
= AVL_NODE2DATA(node
, off
);
238 if (child
!= direction
)
241 return (avl_walk(tree
, data
, direction
));
246 * Search for the node which contains "value". The algorithm is a
247 * simple binary tree search.
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
255 avl_find(avl_tree_t
*tree
, const void *value
, avl_index_t
*where
)
258 avl_node_t
*prev
= NULL
;
261 size_t off
= tree
->avl_offset
;
263 for (node
= tree
->avl_root
; node
!= NULL
;
264 node
= node
->avl_child
[child
]) {
268 diff
= tree
->avl_compar(value
, AVL_NODE2DATA(node
, off
));
269 ASSERT(-1 <= diff
&& diff
<= 1);
275 return (AVL_NODE2DATA(node
, off
));
277 child
= avl_balance2child
[1 + diff
];
282 *where
= AVL_MKINDEX(prev
, child
);
289 * Perform a rotation to restore balance at the subtree given by depth.
291 * This routine is used by both insertion and deletion. The return value
293 * 0 : subtree did not change height
294 * !0 : subtree was reduced in height
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]
299 * On input balance is the "new" balance at "node". This value is either
303 avl_rotation(avl_tree_t
*tree
, avl_node_t
*node
, int balance
)
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
];
315 int which_child
= AVL_XCHILD(node
);
316 int child_bal
= AVL_XBALANCE(child
);
320 * case 1 : node is overly left heavy, the left child is balanced or
321 * also left heavy. This requires the following rotation.
326 * (child bal:0 or -1)
341 * we detect this situation by noting that child's balance is not
345 if (child_bal
!= right_heavy
) {
348 * compute new balance of nodes
350 * If child used to be left heavy (now balanced) we reduced
351 * the height of this sub-tree -- used in "return...;" below
353 child_bal
+= right_heavy
; /* adjust towards right */
356 * move "cright" to be node's left child
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
);
366 * move node to be child's right child
368 child
->avl_child
[right
] = node
;
369 AVL_SETBALANCE(node
, -child_bal
);
370 AVL_SETCHILD(node
, right
);
371 AVL_SETPARENT(node
, child
);
374 * update the pointer into this subtree
376 AVL_SETBALANCE(child
, child_bal
);
377 AVL_SETCHILD(child
, which_child
);
378 AVL_SETPARENT(child
, parent
);
380 parent
->avl_child
[which_child
] = child
;
382 tree
->avl_root
= child
;
384 return (child_bal
== 0);
389 * case 2 : When node is left heavy, but child is right heavy we use
390 * a different rotation.
410 * (child b:?) (node b:?)
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
420 gchild
= child
->avl_child
[right
];
421 gleft
= gchild
->avl_child
[left
];
422 gright
= gchild
->avl_child
[right
];
425 * move gright to left child of node and
427 * move gleft to right child of node
429 node
->avl_child
[left
] = gright
;
430 if (gright
!= NULL
) {
431 AVL_SETPARENT(gright
, node
);
432 AVL_SETCHILD(gright
, left
);
435 child
->avl_child
[right
] = gleft
;
437 AVL_SETPARENT(gleft
, child
);
438 AVL_SETCHILD(gleft
, right
);
442 * move child to left child of gchild and
444 * move node to right child of gchild and
446 * fixup parent of all this to point to gchild
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
);
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
);
459 AVL_SETBALANCE(gchild
, 0);
460 AVL_SETPARENT(gchild
, parent
);
461 AVL_SETCHILD(gchild
, which_child
);
463 parent
->avl_child
[which_child
] = gchild
;
465 tree
->avl_root
= gchild
;
467 return (1); /* the new tree is always shorter */
472 * Insert a new node into an AVL tree at the specified (from avl_find()) place.
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.
478 * After the node is inserted, a single rotation further up the tree may
479 * be necessary to maintain an acceptable AVL balance.
482 avl_insert(avl_tree_t
*tree
, void *new_data
, avl_index_t where
)
485 avl_node_t
*parent
= AVL_INDEX2NODE(where
);
488 int which_child
= AVL_INDEX2CHILD(where
);
489 size_t off
= tree
->avl_offset
;
493 ASSERT(((uintptr_t)new_data
& 0x7) == 0);
496 node
= AVL_DATA2NODE(new_data
, off
);
499 * First, add the node to the tree at the indicated position.
501 ++tree
->avl_numnodes
;
503 node
->avl_child
[0] = NULL
;
504 node
->avl_child
[1] = NULL
;
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
;
513 ASSERT(tree
->avl_root
== NULL
);
514 tree
->avl_root
= node
;
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.
528 * Compute the new balance
530 old_balance
= AVL_XBALANCE(node
);
531 new_balance
= old_balance
+ avl_child2balance
[which_child
];
534 * If we introduced equal balance, then we are done immediately
536 if (new_balance
== 0) {
537 AVL_SETBALANCE(node
, 0);
542 * If both old and new are not zero we went
543 * from -1 to -2 balance, do a rotation.
545 if (old_balance
!= 0)
548 AVL_SETBALANCE(node
, new_balance
);
549 parent
= AVL_XPARENT(node
);
550 which_child
= AVL_XCHILD(node
);
554 * perform a rotation to fix the tree and return
556 (void) avl_rotation(tree
, node
, new_balance
);
560 * Insert "new_data" in "tree" in the given "direction" either after or
561 * before (AVL_AFTER, AVL_BEFORE) the data "here".
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.
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.
579 int child
= direction
; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
584 ASSERT(tree
!= NULL
);
585 ASSERT(new_data
!= NULL
);
586 ASSERT(here
!= NULL
);
587 ASSERT(direction
== AVL_BEFORE
|| direction
== AVL_AFTER
);
590 * If corresponding child of node is not NULL, go to the neighboring
591 * node and reverse the insertion direction.
593 node
= AVL_DATA2NODE(here
, tree
->avl_offset
);
596 diff
= tree
->avl_compar(new_data
, here
);
597 ASSERT(-1 <= diff
&& diff
<= 1);
599 ASSERT(diff
> 0 ? child
== 1 : child
== 0);
602 if (node
->avl_child
[child
] != NULL
) {
603 node
= node
->avl_child
[child
];
605 while (node
->avl_child
[child
] != NULL
) {
607 diff
= tree
->avl_compar(new_data
,
608 AVL_NODE2DATA(node
, tree
->avl_offset
));
609 ASSERT(-1 <= diff
&& diff
<= 1);
611 ASSERT(diff
> 0 ? child
== 1 : child
== 0);
613 node
= node
->avl_child
[child
];
616 diff
= tree
->avl_compar(new_data
,
617 AVL_NODE2DATA(node
, tree
->avl_offset
));
618 ASSERT(-1 <= diff
&& diff
<= 1);
620 ASSERT(diff
> 0 ? child
== 1 : child
== 0);
623 ASSERT(node
->avl_child
[child
] == NULL
);
625 avl_insert(tree
, new_data
, AVL_MKINDEX(node
, child
));
629 * Add a new node to an AVL tree. Strictly enforce that no duplicates can
630 * be added to the tree with a VERIFY which is enabled for non-DEBUG builds.
633 avl_add(avl_tree_t
*tree
, void *new_node
)
635 avl_index_t where
= 0;
637 VERIFY(avl_find(tree
, new_node
, &where
) == NULL
);
639 avl_insert(tree
, new_node
, where
);
643 * Delete a node from the AVL tree. Deletion is similar to insertion, but
644 * with 2 complications.
646 * First, we may be deleting an interior node. Consider the following subtree:
654 * When we are deleting node (d), we find and bring up an adjacent valued leaf
655 * node, say (c), to take the interior node's place. In the code this is
656 * handled by temporarily swapping (d) and (c) in the tree and then using
657 * common code to delete (d) from the leaf position.
659 * Secondly, an interior deletion from a deep tree may require more than one
660 * rotation to fix the balance. This is handled by moving up the tree through
661 * parents and applying rotations as needed. The return value from
662 * avl_rotation() is used to detect when a subtree did not change overall
663 * height due to a rotation.
666 avl_remove(avl_tree_t
*tree
, void *data
)
677 size_t off
= tree
->avl_offset
;
681 delete = AVL_DATA2NODE(data
, off
);
684 * Deletion is easiest with a node that has at most 1 child.
685 * We swap a node with 2 children with a sequentially valued
686 * neighbor node. That node will have at most 1 child. Note this
687 * has no effect on the ordering of the remaining nodes.
689 * As an optimization, we choose the greater neighbor if the tree
690 * is right heavy, otherwise the left neighbor. This reduces the
691 * number of rotations needed.
693 if (delete->avl_child
[0] != NULL
&& delete->avl_child
[1] != NULL
) {
696 * choose node to swap from whichever side is taller
698 old_balance
= AVL_XBALANCE(delete);
699 left
= avl_balance2child
[old_balance
+ 1];
703 * get to the previous value'd node
704 * (down 1 left, as far as possible right)
706 for (node
= delete->avl_child
[left
];
707 node
->avl_child
[right
] != NULL
;
708 node
= node
->avl_child
[right
])
712 * create a temp placeholder for 'node'
713 * move 'node' to delete's spot in the tree
718 if (node
->avl_child
[left
] == node
)
719 node
->avl_child
[left
] = &tmp
;
721 parent
= AVL_XPARENT(node
);
723 parent
->avl_child
[AVL_XCHILD(node
)] = node
;
725 tree
->avl_root
= node
;
726 AVL_SETPARENT(node
->avl_child
[left
], node
);
727 AVL_SETPARENT(node
->avl_child
[right
], node
);
730 * Put tmp where node used to be (just temporary).
731 * It always has a parent and at most 1 child.
734 parent
= AVL_XPARENT(delete);
735 parent
->avl_child
[AVL_XCHILD(delete)] = delete;
736 which_child
= (delete->avl_child
[1] != 0);
737 if (delete->avl_child
[which_child
] != NULL
)
738 AVL_SETPARENT(delete->avl_child
[which_child
], delete);
743 * Here we know "delete" is at least partially a leaf node. It can
744 * be easily removed from the tree.
746 ASSERT(tree
->avl_numnodes
> 0);
747 --tree
->avl_numnodes
;
748 parent
= AVL_XPARENT(delete);
749 which_child
= AVL_XCHILD(delete);
750 if (delete->avl_child
[0] != NULL
)
751 node
= delete->avl_child
[0];
753 node
= delete->avl_child
[1];
756 * Connect parent directly to node (leaving out delete).
759 AVL_SETPARENT(node
, parent
);
760 AVL_SETCHILD(node
, which_child
);
762 if (parent
== NULL
) {
763 tree
->avl_root
= node
;
766 parent
->avl_child
[which_child
] = node
;
770 * Since the subtree is now shorter, begin adjusting parent balances
771 * and performing any needed rotations.
776 * Move up the tree and adjust the balance
778 * Capture the parent and which_child values for the next
779 * iteration before any rotations occur.
782 old_balance
= AVL_XBALANCE(node
);
783 new_balance
= old_balance
- avl_child2balance
[which_child
];
784 parent
= AVL_XPARENT(node
);
785 which_child
= AVL_XCHILD(node
);
788 * If a node was in perfect balance but isn't anymore then
789 * we can stop, since the height didn't change above this point
792 if (old_balance
== 0) {
793 AVL_SETBALANCE(node
, new_balance
);
798 * If the new balance is zero, we don't need to rotate
800 * need a rotation to fix the balance.
801 * If the rotation doesn't change the height
802 * of the sub-tree we have finished adjusting.
804 if (new_balance
== 0)
805 AVL_SETBALANCE(node
, new_balance
);
806 else if (!avl_rotation(tree
, node
, new_balance
))
808 } while (parent
!= NULL
);
812 avl_swap(avl_tree_t
*tree1
, avl_tree_t
*tree2
)
814 avl_node_t
*temp_node
;
815 ulong_t temp_numnodes
;
817 ASSERT3P(tree1
->avl_compar
, ==, tree2
->avl_compar
);
818 ASSERT3U(tree1
->avl_offset
, ==, tree2
->avl_offset
);
819 ASSERT3U(tree1
->avl_size
, ==, tree2
->avl_size
);
821 temp_node
= tree1
->avl_root
;
822 temp_numnodes
= tree1
->avl_numnodes
;
823 tree1
->avl_root
= tree2
->avl_root
;
824 tree1
->avl_numnodes
= tree2
->avl_numnodes
;
825 tree2
->avl_root
= temp_node
;
826 tree2
->avl_numnodes
= temp_numnodes
;
830 * initialize a new AVL tree
833 avl_create(avl_tree_t
*tree
, int (*compar
) (const void *, const void *),
834 size_t size
, size_t offset
)
839 ASSERT(size
>= offset
+ sizeof (avl_node_t
));
841 ASSERT((offset
& 0x7) == 0);
844 tree
->avl_compar
= compar
;
845 tree
->avl_root
= NULL
;
846 tree
->avl_numnodes
= 0;
847 tree
->avl_size
= size
;
848 tree
->avl_offset
= offset
;
856 avl_destroy(avl_tree_t
*tree
)
859 ASSERT(tree
->avl_numnodes
== 0);
860 ASSERT(tree
->avl_root
== NULL
);
865 * Return the number of nodes in an AVL tree.
868 avl_numnodes(avl_tree_t
*tree
)
871 return (tree
->avl_numnodes
);
875 avl_is_empty(avl_tree_t
*tree
)
878 return (tree
->avl_numnodes
== 0);
881 #define CHILDBIT (1L)
884 * Post-order tree walk used to visit all tree nodes and destroy the tree
885 * in post order. This is used for removing all the nodes from a tree without
886 * paying any cost for rebalancing it.
890 * void *cookie = NULL;
893 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
897 * The cookie is really an avl_node_t to the current node's parent and
898 * an indication of which child you looked at last.
900 * On input, a cookie value of CHILDBIT indicates the tree is done.
903 avl_destroy_nodes(avl_tree_t
*tree
, void **cookie
)
909 size_t off
= tree
->avl_offset
;
912 * Initial calls go to the first node or it's right descendant.
914 if (*cookie
== NULL
) {
915 first
= avl_first(tree
);
918 * deal with an empty tree
921 *cookie
= (void *)CHILDBIT
;
925 node
= AVL_DATA2NODE(first
, off
);
926 parent
= AVL_XPARENT(node
);
927 goto check_right_side
;
931 * If there is no parent to return to we are done.
933 parent
= (avl_node_t
*)((uintptr_t)(*cookie
) & ~CHILDBIT
);
934 if (parent
== NULL
) {
935 if (tree
->avl_root
!= NULL
) {
936 ASSERT(tree
->avl_numnodes
== 1);
937 tree
->avl_root
= NULL
;
938 tree
->avl_numnodes
= 0;
944 * Remove the child pointer we just visited from the parent and tree.
946 child
= (uintptr_t)(*cookie
) & CHILDBIT
;
947 parent
->avl_child
[child
] = NULL
;
948 ASSERT(tree
->avl_numnodes
> 1);
949 --tree
->avl_numnodes
;
952 * If we just did a right child or there isn't one, go up to parent.
954 if (child
== 1 || parent
->avl_child
[1] == NULL
) {
956 parent
= AVL_XPARENT(parent
);
961 * Do parent's right child, then leftmost descendent.
963 node
= parent
->avl_child
[1];
964 while (node
->avl_child
[0] != NULL
) {
966 node
= node
->avl_child
[0];
970 * If here, we moved to a left child. It may have one
971 * child on the right (when balance == +1).
974 if (node
->avl_child
[1] != NULL
) {
975 ASSERT(AVL_XBALANCE(node
) == 1);
977 node
= node
->avl_child
[1];
978 ASSERT(node
->avl_child
[0] == NULL
&&
979 node
->avl_child
[1] == NULL
);
981 ASSERT(AVL_XBALANCE(node
) <= 0);
985 if (parent
== NULL
) {
986 *cookie
= (void *)CHILDBIT
;
987 ASSERT(node
== tree
->avl_root
);
989 *cookie
= (void *)((uintptr_t)parent
| AVL_XCHILD(node
));
992 return (AVL_NODE2DATA(node
, off
));
996 #include <linux/module.h>
1009 module_init(avl_init
);
1010 module_exit(avl_fini
);
1012 MODULE_DESCRIPTION("Generic AVL tree implementation");
1013 MODULE_AUTHOR(ZFS_META_AUTHOR
);
1014 MODULE_LICENSE(ZFS_META_LICENSE
);
1015 MODULE_VERSION(ZFS_META_VERSION
"-" ZFS_META_RELEASE
);
1017 EXPORT_SYMBOL(avl_create
);
1018 EXPORT_SYMBOL(avl_find
);
1019 EXPORT_SYMBOL(avl_insert
);
1020 EXPORT_SYMBOL(avl_insert_here
);
1021 EXPORT_SYMBOL(avl_walk
);
1022 EXPORT_SYMBOL(avl_first
);
1023 EXPORT_SYMBOL(avl_last
);
1024 EXPORT_SYMBOL(avl_nearest
);
1025 EXPORT_SYMBOL(avl_add
);
1026 EXPORT_SYMBOL(avl_swap
);
1027 EXPORT_SYMBOL(avl_is_empty
);
1028 EXPORT_SYMBOL(avl_remove
);
1029 EXPORT_SYMBOL(avl_numnodes
);
1030 EXPORT_SYMBOL(avl_destroy_nodes
);
1031 EXPORT_SYMBOL(avl_destroy
);