summaryrefslogtreecommitdiffstats
path: root/cddl
diff options
context:
space:
mode:
authordelphij <delphij@FreeBSD.org>2014-08-12 00:53:03 +0000
committerdelphij <delphij@FreeBSD.org>2014-08-12 00:53:03 +0000
commit63a479a6fbfba8b52dc7d41d8cf7bf3e13048dc5 (patch)
tree67bace82f10217b9fefcf35a7d14f3f213f2a533 /cddl
parent2a07fd9787d8e4590d16e794e7b9dbbf8f0bfaf2 (diff)
downloadFreeBSD-src-63a479a6fbfba8b52dc7d41d8cf7bf3e13048dc5.zip
FreeBSD-src-63a479a6fbfba8b52dc7d41d8cf7bf3e13048dc5.tar.gz
MFC r269229,269404,269466: MFV r269223:
Change dn->dn_dbufs from linked list to AVL tree. Illumos issues: 4873 zvol unmap calls can take a very long time for larger datasets
Diffstat (limited to 'cddl')
-rw-r--r--cddl/contrib/opensolaris/common/avl/avl.c39
1 files changed, 34 insertions, 5 deletions
diff --git a/cddl/contrib/opensolaris/common/avl/avl.c b/cddl/contrib/opensolaris/common/avl/avl.c
index dd39c12..4223da4 100644
--- a/cddl/contrib/opensolaris/common/avl/avl.c
+++ b/cddl/contrib/opensolaris/common/avl/avl.c
@@ -24,6 +24,10 @@
*/
/*
+ * Copyright (c) 2014 by Delphix. 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 +41,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 +49,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 +89,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 +104,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 +124,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
@@ -863,6 +874,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 +948,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:
OpenPOWER on IntegriCloud