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 */
29
30 /*
31 * AVL - generic AVL tree implementation for kernel use
32 *
33 * A complete description of AVL trees can be found in many CS textbooks.
34 *
35 * Here is a very brief overview. An AVL tree is a binary search tree that is
36 * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
37 * any given node, the left and right subtrees are allowed to differ in height
38 * by at most 1 level.
39 *
40 * This relaxation from a perfectly balanced binary tree allows doing
41 * insertion and deletion relatively efficiently. Searching the tree is
42 * still a fast operation, roughly O(log(N)).
43 *
44 * The key to insertion and deletion is a set of tree manipulations called
45 * rotations, which bring unbalanced subtrees back into the semi-balanced state.
46 *
47 * This implementation of AVL trees has the following peculiarities:
618 ASSERT(diff != 0);
619 ASSERT(diff > 0 ? child == 1 : child == 0);
620 #endif
621 }
622 ASSERT(node->avl_child[child] == NULL);
623
624 avl_insert(tree, new_data, AVL_MKINDEX(node, child));
625 }
626
627 /*
628 * Add a new node to an AVL tree.
629 */
630 void
631 avl_add(avl_tree_t *tree, void *new_node)
632 {
633 avl_index_t where;
634
635 /*
636 * This is unfortunate. We want to call panic() here, even for
637 * non-DEBUG kernels. In userland, however, we can't depend on anything
638 * in libc or else the rtld build process gets confused. So, all we can
639 * do in userland is resort to a normal ASSERT().
640 */
641 if (avl_find(tree, new_node, &where) != NULL)
642 #ifdef _KERNEL
643 panic("avl_find() succeeded inside avl_add()");
644 #else
645 ASSERT(0);
646 #endif
647 avl_insert(tree, new_node, where);
648 }
649
650 /*
651 * Delete a node from the AVL tree. Deletion is similar to insertion, but
652 * with 2 complications.
653 *
654 * First, we may be deleting an interior node. Consider the following subtree:
655 *
656 * d c c
657 * / \ / \ / \
658 * b e b e b e
659 * / \ / \ /
660 * a c a a
661 *
662 * When we are deleting node (d), we find and bring up an adjacent valued leaf
663 * node, say (c), to take the interior node's place. In the code this is
664 * handled by temporarily swapping (d) and (c) in the tree and then using
665 * common code to delete (d) from the leaf position.
|
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:
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
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.
|