summaryrefslogtreecommitdiff
path: root/usr/src/man/man3lib/libavl.3lib
diff options
context:
space:
mode:
authorJerry Jelinek <jerry.jelinek@joyent.com>2017-06-08 10:10:29 +0000
committerJerry Jelinek <jerry.jelinek@joyent.com>2017-06-08 10:10:29 +0000
commit8cb9f5acecaded019a9a55454a31dcf4328d0d1b (patch)
tree7c69e28b9b9b5ac2d9f928324a663becf2efa2d7 /usr/src/man/man3lib/libavl.3lib
parent3a5445f1b9d90e4f1538503bd60913c8f302c17f (diff)
parent79809f9cf402f130667349b2d4007ecd65d63c6f (diff)
downloadillumos-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.3lib69
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