diff options
| author | Jerry Jelinek <jerry.jelinek@joyent.com> | 2017-06-08 10:10:29 +0000 |
|---|---|---|
| committer | Jerry Jelinek <jerry.jelinek@joyent.com> | 2017-06-08 10:10:29 +0000 |
| commit | 8cb9f5acecaded019a9a55454a31dcf4328d0d1b (patch) | |
| tree | 7c69e28b9b9b5ac2d9f928324a663becf2efa2d7 /usr/src/man/man3lib/libavl.3lib | |
| parent | 3a5445f1b9d90e4f1538503bd60913c8f302c17f (diff) | |
| parent | 79809f9cf402f130667349b2d4007ecd65d63c6f (diff) | |
| download | illumos-joyent-8cb9f5acecaded019a9a55454a31dcf4328d0d1b.tar.gz | |
[illumos-gate merge]release-20170608
commit 79809f9cf402f130667349b2d4007ecd65d63c6f
8269 dtrace stddev aggregation is normalized incorrectly
commit 22c8b9583d07895c16549075a53668d7bc988cf3
8108 zdb -l fails to read labels 2 and 3
commit 0255edcc85fc0cd1dda0e49bcd52eb66c06a1b16
8056 zfs send size estimate is inaccurate for some zvols
commit dbfd9f930004c390a2ce2cf850c71b4f880eef9c
8156 dbuf_evict_notify() does not need dbuf_evict_lock
commit 690031d326342fa4ea28b5e80f1ad6a16281519d
8168 NULL pointer dereference in zfs_create()
commit 7c4ab494ff60bbbcc0889e71388ae63e903bbf57
8276 rpcbind leaks memory due to libumem per thread caching.
commit f176a0a4cd61cbd708a7f25dc30d221f4d5902ba
8270 dnlc_reverse_lookup() is unsafe at any speed
commit 72d3dbb9ab4481606cb93caca98ba3b3a8eb6ce2
8300 fix man page issues found by mandoc 1.14.1
commit cb4d790db8fe85bce9f9647fe4e1bdc274c7af1c
8337 gss: misleading-indentation
commit f53522305c07915a44e86f2455cc62e7aac27037
8324 more: misleading-indentation
Conflicts:
usr/src/uts/common/fs/lookup.c
usr/src/man/man3c/thrd_equal.3c
Diffstat (limited to 'usr/src/man/man3lib/libavl.3lib')
| -rw-r--r-- | usr/src/man/man3lib/libavl.3lib | 69 |
1 files changed, 38 insertions, 31 deletions
diff --git a/usr/src/man/man3lib/libavl.3lib b/usr/src/man/man3lib/libavl.3lib index 6b65f387fe..bcb9c2c50e 100644 --- a/usr/src/man/man3lib/libavl.3lib +++ b/usr/src/man/man3lib/libavl.3lib @@ -24,10 +24,10 @@ The .Nm library provides a generic implementation of AVL trees, a form of -self-balancing binary tree. The interfaces provided allow for an -efficient way of implementing an ordered set of data structures and, due -to its embeddable nature, allow for a single instance of a data -structure to belong to multiple AVL trees. +self-balancing binary tree. +The interfaces provided allow for an efficient way of implementing an ordered +set of data structures and, due to its embeddable nature, allow for a single +instance of a data structure to belong to multiple AVL trees. .Lp Each AVL tree contains entries of a single type of data structure. Rather than allocating memory for pointers for those data structures, @@ -38,17 +38,18 @@ When an AVL tree is created, through the use of .Fn avl_create , it encodes the size of the data structure, the offset of the data structure, and a comparator function which is used to compare two -instances of a data structure. A data structure may be a member of -multiple AVL trees by creating AVL trees which use different -offsets (different members) into the data structure. +instances of a data structure. +A data structure may be a member of multiple AVL trees by creating AVL trees +which use different offsets (different members) into the data structure. .Lp AVL trees support both look up of an arbitrary item and ordered -iteration over the contents of the entire tree. In addition, from any -node, you can find the previous and next entries in the tree, if they -exist. In addition, AVL trees support arbitrary insertion and deletion. +iteration over the contents of the entire tree. +In addition, from any node, you can find the previous and next entries in the +tree, if they exist. +In addition, AVL trees support arbitrary insertion and deletion. .Ss Performance -AVL trees are often used in place of linked lists. Compared to the -standard, intrusive, doubly linked list, it has the following +AVL trees are often used in place of linked lists. +Compared to the standard, intrusive, doubly linked list, it has the following performance characteristics: .Bl -hang -width Ds .It Sy Lookup One Node @@ -66,10 +67,10 @@ Inserting a single node into an AVL tree is .Sy O(log(n)) . .Pp Note, insertions into an AVL tree always result in an ordered tree. -Insertions into a linked list do not guarantee order. If order is -required, then the time to do the insertion into a linked list will -depend on the time of the search algorithm being employed to find the -place to insert at. +Insertions into a linked list do not guarantee order. +If order is required, then the time to do the insertion into a linked list will +depend on the time of the search algorithm being employed to find the place to +insert at. .Ed .It Sy Delete One Node .Bd -filled -compact @@ -114,10 +115,11 @@ present. .Sh INTERFACES The shared object .Sy libavl.so.1 -provides the public interfaces defined below. See -.Xr Intro(3) -for additional information on shared object interfaces. Individual -functions are documented in their own manual pages. +provides the public interfaces defined below. +See +.Xr Intro 3 +for additional information on shared object interfaces. +Individual functions are documented in their own manual pages. .Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes" .It Sy avl_add Ta Sy avl_create .It Sy avl_destroy Ta Sy avl_destroy_nodes @@ -144,29 +146,34 @@ library defines the following types: .Lp .Sy avl_tree_t .Lp -Type used for the root of the AVL tree. Consumers define one of these -for each of the different trees that they want to have. +Type used for the root of the AVL tree. +Consumers define one of these for each of the different trees that they want to +have. .Lp .Sy avl_node_t .Lp -Type used as the data node for an AVL tree. One of these is embedded in -each data structure that is the member of an AVL tree. +Type used as the data node for an AVL tree. +One of these is embedded in each data structure that is the member of an AVL +tree. .Lp .Sy avl_index_t .Lp -Type used to locate a position in a tree. This is used with +Type used to locate a position in a tree. +This is used with .Xr avl_find 3AVL and .Xr avl_insert 3AVL . .Sh LOCKING The .Nm -library provides no locking. Callers that are using the same AVL tree -from multiple threads need to provide their own synchronization. If only -one thread is ever accessing or modifying the AVL tree, then there are -no synchronization concerns. If multiple AVL trees exist, then they may -all be used simultaneously; however, they are subject to the same rules -around simultaneous access from a single thread. +library provides no locking. +Callers that are using the same AVL tree from multiple threads need to provide +their own synchronization. +If only one thread is ever accessing or modifying the AVL tree, then there are +no synchronization concerns. +If multiple AVL trees exist, then they may all be used simultaneously; however, +they are subject to the same rules around simultaneous access from a single +thread. .Lp All routines are both .Sy Fork-safe |
