Date: Tue, 29 Jul 2014 07:08:32 +0000 (UTC) From: Xin LI <delphij@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-vendor@freebsd.org Subject: svn commit: r269223 - vendor-sys/illumos/dist/common/avl vendor-sys/illumos/dist/uts/common/fs/zfs vendor-sys/illumos/dist/uts/common/fs/zfs/sys vendor-sys/illumos/dist/uts/common/sys vendor/illumo... Message-ID: <201407290708.s6T78Wwv000177@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: delphij Date: Tue Jul 29 07:08:32 2014 New Revision: 269223 URL: http://svnweb.freebsd.org/changeset/base/269223 Log: 4873 zvol unmap calls can take a very long time for larger datasets Reviewed by: George Wilson <george@delphix.com> Reviewed by: Matthew Ahrens <mahrens@delphix.com> Reviewed by: Paul Dagnelie <paul.dagnelie@delphix.com> Reviewed by: Basil Crow <basil.crow@delphix.com> Reviewed by: Dan McDonald <danmcd@omniti.com> Approved by: Robert Mustacchi <rm@joyent.com> illumos/illumos-gate@0f6d88aded0d165f5954688a9b13bac76c38da84 Modified: vendor/illumos/dist/common/avl/avl.c Changes in other areas also in this revision: Modified: vendor-sys/illumos/dist/common/avl/avl.c vendor-sys/illumos/dist/uts/common/fs/zfs/dbuf.c vendor-sys/illumos/dist/uts/common/fs/zfs/dnode.c vendor-sys/illumos/dist/uts/common/fs/zfs/dnode_sync.c vendor-sys/illumos/dist/uts/common/fs/zfs/sys/dbuf.h vendor-sys/illumos/dist/uts/common/fs/zfs/sys/dnode.h vendor-sys/illumos/dist/uts/common/sys/avl.h Modified: vendor/illumos/dist/common/avl/avl.c ============================================================================== --- vendor/illumos/dist/common/avl/avl.c Tue Jul 29 06:57:13 2014 (r269222) +++ vendor/illumos/dist/common/avl/avl.c Tue Jul 29 07:08:32 2014 (r269223) @@ -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[] = * * - 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:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201407290708.s6T78Wwv000177>