diff options
| -rw-r--r-- | usr/src/common/avl/avl.c | 49 | ||||
| -rw-r--r-- | usr/src/uts/common/sys/avl.h | 24 |
2 files changed, 55 insertions, 18 deletions
diff --git a/usr/src/common/avl/avl.c b/usr/src/common/avl/avl.c index dd39c12..ead2fca 100644 --- a/usr/src/common/avl/avl.c +++ b/usr/src/common/avl/avl.c @@ -24,6 +24,11 @@ */ /* + * Copyright (c) 2014 by Delphix. All rights reserved. + * Copyright 2015 Nexenta Systems, Inc. All rights reserved. + */ + +/* * AVL - generic AVL tree implementation for kernel use * * A complete description of AVL trees can be found in many CS textbooks. @@ -37,7 +42,7 @@ * insertion and deletion relatively efficiently. Searching the tree is * still a fast operation, roughly O(log(N)). * - * The key to insertion and deletion is a set of tree maniuplations called + * The key to insertion and deletion is a set of tree manipulations called * rotations, which bring unbalanced subtrees back into the semi-balanced state. * * This implementation of AVL trees has the following peculiarities: @@ -45,7 +50,7 @@ * - The AVL specific data structures are physically embedded as fields * in the "using" data structures. To maintain generality the code * must constantly translate between "avl_node_t *" and containing - * data structure "void *"s by adding/subracting the avl_offset. + * data structure "void *"s by adding/subtracting the avl_offset. * * - Since the AVL data is always embedded in other structures, there is * no locking or memory allocation in the AVL routines. This must be @@ -85,6 +90,12 @@ * is a modified "avl_node_t *". The bottom bit (normally 0 for a * pointer) is set to indicate if that the new node has a value greater * than the value of the indicated "avl_node_t *". + * + * Note - in addition to userland (e.g. libavl and libutil) and the kernel + * (e.g. genunix), avl.c is compiled into ld.so and kmdb's genunix module, + * which each have their own compilation environments and subsequent + * requirements. Each of these environments must be considered when adding + * dependencies from avl.c. */ #include <sys/types.h> @@ -94,7 +105,7 @@ #include <sys/cmn_err.h> /* - * Small arrays to translate between balance (or diff) values and child indeces. + * Small arrays to translate between balance (or diff) values and child indices. * * Code that deals with binary tree data structures will randomly use * left and right children when examining a tree. C "if()" statements @@ -114,7 +125,8 @@ static const int avl_balance2child[] = {0, 0, 1}; * * - If there is a left child, go to it, then to it's rightmost descendant. * - * - otherwise we return thru parent nodes until we've come from a right child. + * - otherwise we return through parent nodes until we've come from a right + * child. * * Return Value: * NULL - if at the end of the nodes @@ -624,14 +636,17 @@ avl_add(avl_tree_t *tree, void *new_node) /* * This is unfortunate. We want to call panic() here, even for * non-DEBUG kernels. In userland, however, we can't depend on anything - * in libc or else the rtld build process gets confused. So, all we can - * do in userland is resort to a normal ASSERT(). + * in libc or else the rtld build process gets confused. + * Thankfully, rtld provides us with its own assfail() so we can use + * that here. We use assfail() directly to get a nice error message + * in the core - much like what panic() does for crashdumps. */ if (avl_find(tree, new_node, &where) != NULL) #ifdef _KERNEL panic("avl_find() succeeded inside avl_add()"); #else - ASSERT(0); + (void) assfail("avl_find() succeeded inside avl_add()", + __FILE__, __LINE__); #endif avl_insert(tree, new_node, where); } @@ -863,6 +878,24 @@ avl_update(avl_tree_t *t, void *obj) return (B_FALSE); } +void +avl_swap(avl_tree_t *tree1, avl_tree_t *tree2) +{ + avl_node_t *temp_node; + ulong_t temp_numnodes; + + ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar); + ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset); + ASSERT3U(tree1->avl_size, ==, tree2->avl_size); + + temp_node = tree1->avl_root; + temp_numnodes = tree1->avl_numnodes; + tree1->avl_root = tree2->avl_root; + tree1->avl_numnodes = tree2->avl_numnodes; + tree2->avl_root = temp_node; + tree2->avl_numnodes = temp_numnodes; +} + /* * initialize a new AVL tree */ @@ -919,7 +952,7 @@ avl_is_empty(avl_tree_t *tree) /* * Post-order tree walk used to visit all tree nodes and destroy the tree - * in post order. This is used for destroying a tree w/o paying any cost + * in post order. This is used for destroying a tree without paying any cost * for rebalancing it. * * example: diff --git a/usr/src/uts/common/sys/avl.h b/usr/src/uts/common/sys/avl.h index ba305c9..cc4af82 100644 --- a/usr/src/uts/common/sys/avl.h +++ b/usr/src/uts/common/sys/avl.h @@ -23,14 +23,13 @@ * Use is subject to license terms. */ -#ifndef _AVL_H -#define _AVL_H - /* - * This is a private header file. Applications should not directly include - * this file. + * Copyright (c) 2014 by Delphix. All rights reserved. */ +#ifndef _AVL_H +#define _AVL_H + #ifdef __cplusplus extern "C" { #endif @@ -39,9 +38,9 @@ extern "C" { #include <sys/avl_impl.h> /* - * This is a generic implemenatation of AVL trees for use in the Solaris kernel. - * The interfaces provide an efficient way of implementing an ordered set of - * data structures. + * This is a generic implementation of AVL trees for use in the illumos. The + * interfaces provide an efficient way of implementing an ordered set of data + * structures. * * AVL trees provide an alternative to using an ordered linked list. Using AVL * trees will usually be faster, however they requires more storage. An ordered @@ -53,7 +52,7 @@ extern "C" { * --------- -------- -------- * lookup O(n) O(log(n)) * - * insert 1 node constant constant + * insert 1 node constant O(log(n)) * * delete 1 node constant between constant and O(log(n)) * @@ -175,7 +174,7 @@ extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); * Insert "new_data" in "tree" in the given "direction" either after * or before the data "here". * - * This might be usefull for avl clients caching recently accessed + * This might be useful for avl clients caching recently accessed * data to avoid doing avl_find() again for insertion. * * new_data - new data to insert @@ -260,6 +259,11 @@ extern boolean_t avl_update_lt(avl_tree_t *, void *); extern boolean_t avl_update_gt(avl_tree_t *, void *); /* + * Swaps the contents of the two trees. + */ +extern void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2); + +/* * Return the number of nodes in the tree */ extern ulong_t avl_numnodes(avl_tree_t *tree); |