5935 libavl should be a public interface

5936 AVL trees should be part of the DDI
Reviewed by: Ryan Zezeski <ryan@zinascii.com>
Reviewed by: Josef 'Jeff' Sipek <josef.sipek@nexenta.com>
Reviewed by: Dan McDonald <danmcd@omniti.com>
Reviewed by: Cody Mello <cody.mello@joyent.com>
Approved by: Garrett D'Amore <garrett@damore.org>

27 files changed, 1656 insertions, 29 deletions

diff --git a/exception_lists/packaging b/exception_lists/packaging
index 3ba665abf8..009f8073e4 100644
--- a/exception_lists/packaging
+++ b/exception_lists/packaging
@@ -454,25 +454,6 @@ usr/include/sys/crypto/ops_impl.h
 usr/include/sys/crypto/sched_impl.h
 #
 # The following files are installed in the proto area
-# by the build of libavl (AVL Tree Interface Library).
-# libavl contains interfaces which are all private interfaces.
-#
-lib/libavl.so
-lib/amd64/libavl.so		i386
-lib/sparcv9/libavl.so		sparc
-lib/llib-lavl
-lib/llib-lavl.ln
-lib/amd64/llib-lavl.ln		i386
-lib/sparcv9/llib-lavl.ln	sparc
-usr/lib/libavl.so
-usr/lib/amd64/libavl.so		i386
-usr/lib/sparcv9/libavl.so	sparc
-usr/lib/llib-lavl
-usr/lib/llib-lavl.ln
-usr/lib/amd64/llib-lavl.ln	i386
-usr/lib/sparcv9/llib-lavl.ln	sparc
-#
-# The following files are installed in the proto area
 # by the build of libcmdutils (Command Utilities Library).
 # libcmdutils contains interfaces which are all private interfaces.
 #
diff --git a/usr/src/cmd/mandoc/lib.in b/usr/src/cmd/mandoc/lib.in
index d80f0a293c..b083172c2d 100644
--- a/usr/src/cmd/mandoc/lib.in
+++ b/usr/src/cmd/mandoc/lib.in
@@ -19,6 +19,7 @@
  * won't be referenced in other man pages.
  */
 LINE("libadm",		"General Administrative Library (libadm, \\-ladm)")
+LINE("libavl",		"AVL Tree Library (libavl, \\-lavl)")
 LINE("libbsdmalloc",	"BSD Memory Allocation Library (libbsdmalloc, -lbsdmalloc)")
 LINE("libbsm",		"Security and Auditing Library (libbsm, \\lbsm)")
 LINE("libc",		"Standard C Library (libc, \\-lc)")
diff --git a/usr/src/cmd/mandoc/msec.in b/usr/src/cmd/mandoc/msec.in
index 0aee249bd7..e1cc5efb90 100644
--- a/usr/src/cmd/mandoc/msec.in
+++ b/usr/src/cmd/mandoc/msec.in
@@ -21,6 +21,7 @@ LINE("1M",		"Maintenance Commands")
 LINE("1S",		"illumos Specific Commands")
 LINE("2",		"System Calls")
 LINE("3",		"Introduction to Library Functions")
+LINE("3AVL",		"AVL Tree Library Functions")
 LINE("3BSDMALLOC",	"BSD Memory Allocation Library")
 LINE("3BSM",		"Security and Auditing Library Functions")
 LINE("3C",		"Standard C Library Functions")
diff --git a/usr/src/lib/libavl/mapfile-vers b/usr/src/lib/libavl/mapfile-vers
index 449cd189e5..8087aef451 100644
--- a/usr/src/lib/libavl/mapfile-vers
+++ b/usr/src/lib/libavl/mapfile-vers
@@ -39,7 +39,7 @@
 
 $mapfile_version 2
 
-SYMBOL_VERSION SUNWprivate_1.1 {
+SYMBOL_VERSION ILLUMOS_1.0 {
     global:
 	avl_add;
 	avl_create;
@@ -56,6 +56,9 @@ SYMBOL_VERSION SUNWprivate_1.1 {
 	avl_remove;
 	avl_swap;
 	avl_walk;
+};
+
+SYMBOL_VERSION SUNWprivate_1.1 {
     local:
 	*;
 };
diff --git a/usr/src/man/Makefile b/usr/src/man/Makefile
index 44d466687b..74d27fb221 100644
--- a/usr/src/man/Makefile
+++ b/usr/src/man/Makefile
@@ -23,6 +23,7 @@ SUBDIRS=	man1		\
 		man1s		\
 		man2		\
 		man3		\
+		man3avl		\
 		man3bsm		\
 		man3c		\
 		man3c_db	\
diff --git a/usr/src/man/man3avl/Makefile b/usr/src/man/man3avl/Makefile
new file mode 100644
index 0000000000..e968d6b895
--- /dev/null
+++ b/usr/src/man/man3avl/Makefile
@@ -0,0 +1,55 @@
+#
+# This file and its contents are supplied under the terms of the
+# Common Development and Distribution License ("CDDL"), version 1.0.
+# You may only use this file in accordance with the terms of version
+# 1.0 of the CDDL.
+#
+# A full copy of the text of the CDDL should have accompanied this
+# source.  A copy of the CDDL is also available via the Internet
+# at http://www.illumos.org/license/CDDL.
+#
+
+#
+# Copyright (c) 2015, Joyent, Inc.  All rights reserved.
+#
+
+include		$(SRC)/Makefile.master
+
+MANSECT =	3avl
+
+MANFILES =					\
+		avl_add.3avl			\
+		avl_create.3avl			\
+		avl_destroy.3avl		\
+		avl_destroy_nodes.3avl		\
+		avl_find.3avl			\
+		avl_first.3avl			\
+		avl_insert.3avl			\
+		avl_is_empty.3avl		\
+		avl_nearest.3avl		\
+		avl_numnodes.3avl		\
+		avl_swap.3avl
+
+MANLINKS =				\
+		AVL_NEXT.3avl		\
+		AVL_PREV.3avl		\
+		avl_insert_here.3avl	\
+		avl_last.3avl		\
+		avl_remove.3avl	
+
+# avl_add.3avl
+avl_remove.3avl		:= LINKSRC = avl_add.3avl
+
+# avl_first.3avl
+AVL_NEXT.3avl		:= LINKSRC = avl_first.3avl
+AVL_PREV.3avl		:= LINKSRC = avl_first.3avl
+avl_last.3avl		:= LINKSRC = avl_first.3avl
+
+# avl_insert.3avl
+avl_insert_here.3avl	:= LINKSRC = avl_insert.3avl
+
+.KEEP_STATE:
+
+include		$(SRC)/man/Makefile.man
+
+install:	$(ROOTMANFILES) $(ROOTMANLINKS)
diff --git a/usr/src/man/man3avl/avl_add.3avl b/usr/src/man/man3avl/avl_add.3avl
new file mode 100644
index 0000000000..0ac7912264
--- /dev/null
+++ b/usr/src/man/man3avl/avl_add.3avl
@@ -0,0 +1,95 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd Apr 13, 2015
+.Dt AVL_ADD 3AVL
+.Os
+.Sh NAME
+.Nm avl_add ,
+.Nm avl_remove
+.Nd add and remove nodes from an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void
+.Fo avl_add
+.Fa "avl_tree_t *tree"
+.Fa "void *node"
+.Fc
+.Ft void
+.Fo avl_remove
+.Fa "avl_tree_t *tree"
+.Fa "void *node"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_add
+and
+.Fn avl_remove
+functions add and remove objects from the AVL tree rooted at
+.Fa tree .
+.Pp
+The
+.Fn avl_add
+function inserts
+.Fa node
+into the tree.
+.Fa node
+must not already be in the tree, thus implying it must not compare equal
+to any other node in the tree. Adding
+.Fa node
+to
+.Fa tree
+will take
+.Sy O(log(n))
+time, as it implicitly determines where to place it in the tree.
+If
+.Fa node Ns 's
+location has already been determined by
+.Xr avl_find 3AVL ,
+then instead use
+.Xr avl_insert 3AVL .
+.Pp
+The
+.Fn avl_remove
+function removes
+.Fa node
+from the tree rooted at
+.Fa tree .
+.Fa node
+must be present in the tree, otherwise, the behavior is undefined.
+Deleting
+.Fa node
+from
+.Fa tree
+occurs in
+.Sy O(log(n))
+time.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_create 3AVL ,
+.Xr avl_insert 3AVL ,
+.Xr avl_insert_here 3AVL ,
+.Xr avl_destroy 3AVL
diff --git a/usr/src/man/man3avl/avl_create.3avl b/usr/src/man/man3avl/avl_create.3avl
new file mode 100644
index 0000000000..4eb687e3e8
--- /dev/null
+++ b/usr/src/man/man3avl/avl_create.3avl
@@ -0,0 +1,107 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_CREATE 3AVL
+.Os
+.Sh NAME
+.Nm avl_create
+.Nd create an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void
+.Fo avl_create
+.Fa "avl_tree_t *tree"
+.Fa "int (*compare)(const void *first, const void *second)"
+.Fa "size_t size"
+.Fa "size_t offset"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_create
+function initializes an AVL tree rooted at
+.Fa tree .
+.Pp
+An AVL tree needs to encode information about the type of data
+structures being stored inside of it and needs to be told how to compare
+two different entries in the same tree. The
+.Fa size
+argument represents the total size of the data structure being used in
+the tree. This is a constant that is generally expressed to
+.Fn avl_create
+using the
+.Sy sizeof
+operator.
+.Pp
+The data structure that is being stored in the AVL tree must include an
+.Sy avl_node_t
+as a member of the structure. The structure may have multiple
+.Sy avl_node_t Ns 's,
+one for each AVL tree that it may concurrently be a member of. The
+.Fa offset
+argument indicates what the offset of the
+.Sy avl_node_t
+is for the data structure that this AVL tree contains.
+.Pp
+The
+.Fa compare
+function pointer is used to compare two nodes in the tree. This is used as part
+of all operations on the tree that cause traversal. The function is
+given, as arguments, two pointers to the actual data nodes, which should be
+cast to the corresponding type of actual data. The return value must
+adhere to the following rules:
+.Bl -enum
+.It
+If the first argument,
+.Fa first ,
+is less than the second argument,
+.Fa second ,
+then the
+.Fa compare
+function must return
+.Sy -1 .
+.It
+If the first argument is greater than the second argument, then the
+.Fa compare
+function must return
+.Sy 1 .
+.It
+Otherwise, if they compare to the same value, then it should return
+.Sy 0 .
+.It
+Only the return values, -1, 0, and 1, are valid. Returning values
+other than those will result in undefined behavior.
+.El
+.Pp
+When two nodes in the tree compare equal, then that means that they
+should represent the same data, though they may not always be equivalent
+pointers, due to lookups.
+.Pp
+The life time and storage of the AVL tree is maintained by the caller.
+The library does not perform any allocations as part of creating an AVL
+tree.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB
diff --git a/usr/src/man/man3avl/avl_destroy.3avl b/usr/src/man/man3avl/avl_destroy.3avl
new file mode 100644
index 0000000000..6ae78c9c60
--- /dev/null
+++ b/usr/src/man/man3avl/avl_destroy.3avl
@@ -0,0 +1,62 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_DESTROY 3AVL
+.Os
+.Sh NAME
+.Nm avl_destroy
+.Nd destroy an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void
+.Fo avl_destroy
+.Fa "avl_tree_t *tree"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_destroy
+function is used to destroy the AVL tree that is rooted at
+.Fa tree .
+At the time that
+.Fn avl_destroy
+is called,
+.Fa tree
+must be empty. It is a programmer error to call
+.Fn avl_destroy
+otherwise. To efficiently remove all entries in the tree, see
+.Xr avl_destroy_nodes 3AVL .
+.Pp
+After a call to
+.Fn avl_destroy ,
+.Fa tree
+should not be used with any other library functions until a subsequent
+call to
+.Xr avl_create 3AVL .
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_create 3AVL ,
+.Xr avl_destroy_nodes 3AVL
diff --git a/usr/src/man/man3avl/avl_destroy_nodes.3avl b/usr/src/man/man3avl/avl_destroy_nodes.3avl
new file mode 100644
index 0000000000..c5488f43fb
--- /dev/null
+++ b/usr/src/man/man3avl/avl_destroy_nodes.3avl
@@ -0,0 +1,96 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_DESTROY_NODES 3AVL
+.Os
+.Sh NAME
+.Nm avl_destroy_nodes
+.Nd efficiently remove nodes from an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void *
+.Fo avl_destroy_nodes
+.Fa "avl_tree_t *tree"
+.Fa "void **cookie"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_destroy_nodes
+function is used to efficiently remove nodes from the AVL tree rooted at
+.Fa tree .
+.Pp
+After the
+.Fn avl_destroy_nodes
+function is called on an AVL tree, the only valid functions that may be
+called on it are additional calls to
+.Fn avl_destroy_nodes
+and finally
+.Fn avl_destroy .
+.Pp
+Before calling
+.Fn avl_destroy_nodes ,
+callers must first initialize a value of type
+.Vt "void *"
+to
+.Sy NULL
+and pass a pointer to it as the argument
+.Fa cookie .
+This is an opaque value that will be used to maintain where to next
+delete items from the tree. Callers should never modify it after
+initializing it. After each call to
+.Fn avl_destroy_nodes ,
+.Fa cookie
+will be updated and must be passed to subsequent calls to
+.Fn avl_destroy_nodes.
+.Pp
+Each time
+.Fn avl_destroy_nodes
+is called, it will return a pointer to an object that had previously
+been inserted into the tree, allowing a caller the opportunity to delete
+or clean it up. Once
+.Fn avl_destroy_nodes
+returns a
+.Sy NULL
+pointer, then the tree is empty and the caller should proceed to call
+.Xr avl_destroy 3AVL .
+.Pp
+The examples in
+.Xr libavl 3LIB
+demonstrate the correct usage of this interface.
+.Sh RETURN VALUES
+The
+.Fn avl_destroy_nodes
+function will return a pointer to the object just removed from
+the tree rooted at
+.Fa tree
+and if
+.Fa tree
+is empty, it will return
+.Sy NULL .
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_destroy 3AVL
diff --git a/usr/src/man/man3avl/avl_find.3avl b/usr/src/man/man3avl/avl_find.3avl
new file mode 100644
index 0000000000..a98778598f
--- /dev/null
+++ b/usr/src/man/man3avl/avl_find.3avl
@@ -0,0 +1,103 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_FIND 3AVL
+.Os
+.Sh NAME
+.Nm avl_find
+.Nd find a node in an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void *
+.Fo avl_find
+.Fa "avl_tree_t *tree"
+.Fa "const void *node"
+.Fa "avl_index_t *where"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_find
+function is used to look up a node in the tree rooted at
+.Fa tree .
+.Pp
+To perform a lookup, a caller should construct an instance of the data
+structure, the argument
+.Fa node .
+.Fn avl_find
+searches through the tree for a node which compares equal to the passed
+in
+.Fa node
+using the comparison function specified when the tree was created with
+.Xr avl_create 3AVL .
+The only fields of
+.Fa node
+that need to be initialized are those that the comparison function will
+use, the others may remain uninitialized.
+.Pp
+If a match exists in the tree, then that entry will be returned.
+Otherwise,
+.Sy NULL
+is returned.
+.Pp
+If
+.Fa node
+does not match anything in the tree and the value of
+.Fa where
+is a
+.Pf non- Sy NULL
+pointer, then
+.Fa where
+will be updated to a value that can be used with both
+.Xr avl_insert 3AVL
+and
+.Xr avl_nearest 3AVL .
+This value is only valid as long as the tree is not modified. If
+anything is added or removed from the tree, then the value of
+.Fa where
+is no longer valid. This is commonly used as part of a pattern to see if
+something that should be added to the tree already exists, and if not,
+insert it. For more information, see the examples in
+.Xr libavl 3LIB .
+.Pp
+If the lookup is successful, then the contents of
+.Fa where
+are undefined.
+.Sh RETURN VALUES
+If
+.Fa node
+matches an entry in the tree, the matching entry is returned. Otherwise,
+.Sy NULL
+is returned and if
+.Fa where
+is
+.Pf non- Sy NULL ,
+it is updated to point to a location in the tree.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_create 3AVL ,
+.Xr avl_insert 3AVL ,
+.Xr avl_nearest 3AVL
diff --git a/usr/src/man/man3avl/avl_first.3avl b/usr/src/man/man3avl/avl_first.3avl
new file mode 100644
index 0000000000..a886308472
--- /dev/null
+++ b/usr/src/man/man3avl/avl_first.3avl
@@ -0,0 +1,132 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_FIRST 3AVL
+.Os
+.Sh NAME
+.Nm avl_first ,
+.Nm AVL_NEXT ,
+.Nm AVL_PREV ,
+.Nm avl_last
+.Nd get the first, next, previous, and last entries from an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void *
+.Fo avl_first
+.Fa "avl_tree_t *tree"
+.Fc
+.Ft void *
+.Fo avl_last
+.Fa "avl_tree_t *tree"
+.Fc
+.Ft void *
+.Fo AVL_NEXT
+.Fa "avl_tree_t *tree"
+.Fa "void *node"
+.Fc
+.Ft void *
+.Fo AVL_PREV
+.Fa "avl_tree_t *tree"
+.Fa "void *node"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_first
+and
+.Fn avl_last
+respectively return the first and last entry in the tree specified by
+.Fa tree .
+Order in the tree is determined by the comparison function that was
+specified at the time the tree was created with
+.Xr avl_create 3AVL .
+If
+.Fa tree
+is empty, then
+.Fn avl_first
+and
+.Fn avl_last
+return
+.Sy NULL .
+.Pp
+The
+.Fn AVL_NEXT
+and
+.Fn AVL_PREV
+functions are macros that may be used to obtain the next and previous
+entry following
+.Fa node
+in the AVL tree
+.Fa tree .
+If there is no next or previous node, for example, if one was at the
+beginning or end of the tree, then
+.Sy NULL
+is returned.
+.Pp
+These constructs are generally used as part of loops to iterate the
+tree. See the examples section in
+.Xr libavl 3LIB
+for more information on using this
+interface.
+.Sh RETURN VALUES
+The
+.Fn avl_first
+function returns a pointer to the first entry in the AVL tree
+.Fa tree
+or
+.Sy NULL
+if the AVL tree is empty.
+.Pp
+The
+.Fn avl_last
+function returns a pointer to the last entry in the AVL tree
+.Fa tree
+or
+.Sy NULL
+if the AVL tree is empty.
+.Pp
+The
+.Fn AVL_NEXT
+macro returns a pointer to the object in the tree that follows
+.Fa node .
+If
+.Fa node
+is the last entry in the tree,
+.Sy NULL
+is returned instead.
+.Pp
+The
+.Fn AVL_PREV
+macro returns a pointer to the object in the tree that precedes
+.Fa node .
+If
+.Fa node
+is the first entry in the tree,
+.Sy NULL
+is returned instead.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_create 3AVL
diff --git a/usr/src/man/man3avl/avl_insert.3avl b/usr/src/man/man3avl/avl_insert.3avl
new file mode 100644
index 0000000000..89d6c8a7af
--- /dev/null
+++ b/usr/src/man/man3avl/avl_insert.3avl
@@ -0,0 +1,110 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_INSERT 3AVL
+.Os
+.Sh NAME
+.Nm avl_insert ,
+.Nm avl_insert_here
+.Nd insert items into an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void
+.Fo avl_insert
+.Fa "avl_tree_t *tree"
+.Fa "void *new"
+.Fa "avl_index_t where"
+.Fc
+.Ft void
+.Fo avl_insert_here
+.Fa "avl_tree_t *tree"
+.Fa "void *new"
+.Fa "void *here"
+.Fa "int direction"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_insert
+and
+.Fn avl_insert_here
+functions are used to add the entry
+.Fa new
+to the tree rooted at
+.Fa tree .
+.Pp
+The
+.Fn avl_insert
+function uses the
+.Fa where
+value, obtained from a call to
+.Xr avl_find 3AVL ,
+to determine where to insert the new entry into the tree. The tree must
+not have been modified inbetween the call to
+.Xr avl_find 3AVL
+and the call to
+.Fn avl_insert .
+If callers are not using
+.Xr avl_find 3AVL
+to validate the presence of
+.Fa new
+in the tree and only immediately insert it, then
+.Xr avl_add 3AVL
+may be used instead.
+.Pp
+The
+.Fn avl_insert_here
+function is for consumers who are keeping track of recently accessed
+data and wish to avoid an additional call to
+.Xr avl_find 3AVL .
+The new entry,
+.Fa new ,
+will be inserted starting at the node
+.Fa here ,
+which must already exist in the tree. To insert the node in the tree
+before
+.Fa here ,
+then the argument
+.Fa direction
+should have the value
+.Dv AVL_BEFORE .
+Otherwise, to indicate that the new entry should be inserted after
+.Fa here,
+then
+.Fa direction
+should be set to
+.Dv AVL_AFTER .
+It is illegal to set
+.Fa direction
+to anything other than
+.Dv AVL_BEFORE
+or
+.Dv AVL_AFTER .
+If this is done, the behavior is not defined.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_add 3AVL ,
+.Xr avl_find 3AVL
diff --git a/usr/src/man/man3avl/avl_is_empty.3avl b/usr/src/man/man3avl/avl_is_empty.3avl
new file mode 100644
index 0000000000..f8d2c17ab2
--- /dev/null
+++ b/usr/src/man/man3avl/avl_is_empty.3avl
@@ -0,0 +1,60 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_IS_EMPTY 3AVL
+.Os
+.Sh NAME
+.Nm avl_is_empty
+.Nd determine if an AVL tree is empty
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft boolean_t
+.Fo avl_is_empty
+.Fa "avl_tree_t *tree"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_is_empty
+function is used to determine whether or not the AVL tree,
+.Fa tree ,
+is empty. If
+.Fa tree
+has zero nodes in it, then
+.Sy B_TRUE
+is returned, otherwise
+.Sy B_FALSE
+is returned.
+.Sh RETURN VALUES
+The
+.Fn avl_is_empty
+function returns
+.Sy B_TRUE
+when there are no nodes in the tree and
+.Sy B_FALSE
+otherwise.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB
diff --git a/usr/src/man/man3avl/avl_nearest.3avl b/usr/src/man/man3avl/avl_nearest.3avl
new file mode 100644
index 0000000000..669f78c61f
--- /dev/null
+++ b/usr/src/man/man3avl/avl_nearest.3avl
@@ -0,0 +1,93 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_NEAREST 3AVL
+.Os
+.Sh NAME
+.Nm avl_nearest
+.Nd find the nearest node in an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void *
+.Fo avl_nearest
+.Fa "avl_tree_t *tree"
+.Fa "avl_index_t where"
+.Fa "int direction"
+.Fc
+.Sh DESCRIPTION
+The
+.Fa avl_nearest
+function returns the closest node in
+.Fa tree
+before or after the insertion point specified by
+.Fa where .
+.Pp
+The value of
+.Fa where
+is obtained when a
+.Pf non- Dv NULL
+pointer is passed in to the
+.Fa where
+argument of
+.Xr avl_find 3AVL
+and it fails to find an entry in the tree.
+.Pp
+If
+.Fa direction
+is set to
+.Dv AVL_AFTER ,
+then the node that would logically have followed it will be returned. If
+.Fa direction
+is instead set to
+.Dv AVL_BEFORE ,
+then the node that would have logically preceded it is returned.
+.Pp
+When there is no nearest node, for example,
+.Dv AVL_AFTER
+is specified and the entry would have been the last node in the tree,
+then
+.Sy NULL is returned .
+.Pp
+If the tree is modified between a call to
+.Xr avl_find 3AVL
+and
+.Fn avl_nearest ,
+then the value of
+.Fa where
+from
+.Xr avl_find 3AVL
+will no longer be valid and
+.Xr avl_find 3AVL
+must be called again.
+.Sh RETURN VALUES
+The
+.Fn avl_nearest
+function returns the node that is closest or
+.Sy NULL
+if there is not a matching one.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB
diff --git a/usr/src/man/man3avl/avl_numnodes.3avl b/usr/src/man/man3avl/avl_numnodes.3avl
new file mode 100644
index 0000000000..a366c38efb
--- /dev/null
+++ b/usr/src/man/man3avl/avl_numnodes.3avl
@@ -0,0 +1,48 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_NUMNODES 3AVL
+.Os
+.Sh NAME
+.Nm avl_numnodes
+.Nd return the number of nodes in an AVL tree
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft ulong_t
+.Fo avl_numnodes
+.Fa "avl_tree_t *tree"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_numnodes
+function returns the number of nodes in the AVL tree rooted
+at
+.Fa tree .
+.Sh RETURN VALUES
+The number of nodes in the tree is returned.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB
diff --git a/usr/src/man/man3avl/avl_swap.3avl b/usr/src/man/man3avl/avl_swap.3avl
new file mode 100644
index 0000000000..0d4ec606fe
--- /dev/null
+++ b/usr/src/man/man3avl/avl_swap.3avl
@@ -0,0 +1,52 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt AVL_SWAP 3AVL
+.Os
+.Sh NAME
+.Nm avl_swap
+.Nd swap the entries in two AVL trees
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Ft void
+.Fo avl_swap
+.Fa "avl_tree_t *tree1"
+.Fa "avl_tree_t *tree2"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn avl_swap
+function swaps the nodes in the AVL tree
+.Fa tree1
+with those in
+.Fa tree2 .
+The two trees must have hold identical kinds of data, the arguments
+passed to
+.Xr avl_create
+must be identical. The behavior when they are not is undefined.
+.Sh EXAMPLES
+See the
+.Sy EXAMPLES
+section in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking
+in
+.Xr libavl 3LIB .
+.Sh SEE ALSO
+.Xr libavl 3LIB
diff --git a/usr/src/man/man3lib/Makefile b/usr/src/man/man3lib/Makefile
index fe9acebc3a..48abd74fd8 100644
--- a/usr/src/man/man3lib/Makefile
+++ b/usr/src/man/man3lib/Makefile
@@ -22,6 +22,7 @@ MANFILES= 	libMPAPI.3lib		\
 	 	libSMHBAAPI.3lib	\
 	 	libadm.3lib		\
 	 	libaio.3lib		\
+		libavl.3lib		\
 	 	libbsdmalloc.3lib	\
 	 	libbsm.3lib		\
 	 	libc.3lib		\
diff --git a/usr/src/man/man3lib/libavl.3lib b/usr/src/man/man3lib/libavl.3lib
new file mode 100644
index 0000000000..be43c1cae9
--- /dev/null
+++ b/usr/src/man/man3lib/libavl.3lib
@@ -0,0 +1,448 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 07, 2015
+.Dt LIBAVL 3LIB
+.Os
+.Sh NAME
+.Nm libavl
+.Nd generic self-balancing binary search tree library
+.Sh SYNOPSIS
+.Lb libavl
+.In sys/avl.h
+.Sh DESCRIPTION
+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.
+.Lp
+Each AVL tree contains entries of a single type of data structure.
+Rather than allocating memory for pointers for those data structures,
+the storage for the tree is embedded into the data structures by
+declaring a member of type
+.Vt avl_node_t .
+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.
+.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.
+.Ss Performance
+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
+.Bd -filled -compact
+Lookup of a single node in a linked list is
+.Sy O(n) ,
+whereas lookup of a single node in an AVL tree is
+.Sy O(log(n)) .
+.Ed
+.It Sy Insert One Node
+.Bd -filled -compact
+Inserting a single node into a linked list is
+.Sy O(1) .
+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.
+.Ed
+.It Sy Delete One Node
+.Bd -filled -compact
+Deleting a single node from a linked list is
+.Sy O(1),
+whereas deleting a single node from an AVL tree takes
+.Sy O(log(n))
+time.
+.Ed
+.It Sy Delete All Nodes
+.Bd -filled -compact
+Deleting all nodes from a linked list is
+.Sy O(n) .
+With an AVL tree, if using the
+.Xr avl_delete_nodes 3AVL
+function then deleting all nodes
+is
+.Sy O(n) .
+However, if iterating over each entry in the tree and then removing it using
+a while loop,
+.Xr avl_first 3AVL
+and
+.Xr avl_remove 3AVL
+then the time to remove all nodes is
+.Sy O(n\ *\ log(n)).
+.Ed
+.It Sy Visit the Next or Previous Node
+.Bd -filled -compact
+Visiting the next or previous node in a linked list is
+.Sy O(1) ,
+whereas going from the next to the previous node in an AVL tree will
+take between
+.Sy O(1)
+and
+.Sy O(log(n)) .
+.Ed
+.El
+.Pp
+In general, AVL trees are a good alternative for linked lists when order
+or lookup speed is important and a reasonable number of items will be
+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.
+.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
+.It Sy avl_find Ta Sy avl_first
+.It Sy avl_insert Ta Sy avl_insert_here
+.It Sy avl_is_empty Ta Sy avl_last
+.It Sy avl_nearest Ta Sy avl_numnodes
+.It Sy avl_remove Ta Sy avl_swap
+.El
+.Pp
+In addition, the library defines C pre-processor macros which are
+defined below and documented in their own manual pages.
+.\"
+.\" Use the same column widths in both cases where we describe the list
+.\" of interfaces, to allow the manual page to better line up when rendered.
+.\"
+.Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes"
+.It Sy AVL_NEXT Ta Sy AVL_PREV
+.El
+.Sh TYPES
+The
+.Nm
+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.
+.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.
+.Lp
+.Sy avl_index_t
+.Lp
+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.
+.Lp
+All routines are both
+.Sy Fork-safe
+and
+.Sy Async-Signal-Safe .
+Callers may call functions in
+.Nm
+from a signal handler and
+.Nm
+calls are all safe in face of
+.Xr fork 2 ;
+however, if callers have their own locks, then they must make sure that
+they are accounted for by the use of routines such as
+.Xr pthread_atfork 3C .
+.Sh EXAMPLES
+The following code shows examples of exercising all of the functionality
+that is present in
+.Nm .
+It can be compiled by using a C compiler and linking
+against
+.Nm .
+For example, given a file named avl.c, with gcc, one would run:
+.Bd -literal
+$ gcc -Wall -o avl avl.c -lavl
+.Ed
+.Bd -literal
+/*
+ * Example of using AVL Trees
+ */
+
+#include <sys/avl.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+static avl_tree_t inttree;
+
+/*
+ * The structure that we're storing in an AVL tree.
+ */
+typedef struct intnode {
+	int in_val;
+	avl_node_t in_avl;
+} intnode_t;
+
+static int
+intnode_comparator(const void *l, const void *r)
+{
+	const intnode_t *li = l;
+	const intnode_t *ri = r;
+
+	if (li->in_val > ri->in_val)
+		return (1);
+	if (li->in_val < ri->in_val)
+		return (-1);
+	return (0);
+}
+
+/*
+ * Create an AVL Tree
+ */
+static void
+create_avl(void)
+{
+	avl_create(&inttree, intnode_comparator, sizeof (intnode_t),
+	    offsetof(intnode_t, in_avl));
+}
+
+/*
+ * Add entries to the tree with the avl_add function.
+ */
+static void
+fill_avl(void)
+{
+	int i;
+	intnode_t *inp;
+
+	for (i = 0; i < 20; i++) {
+		inp = malloc(sizeof (intnode_t));
+		assert(inp != NULL);
+		inp->in_val = i;
+		avl_add(&inttree, inp);
+	}
+}
+
+/*
+ * Find entries in the AVL tree. Note, we create an intnode_t on the
+ * stack that we use to look this up.
+ */
+static void
+find_avl(void)
+{
+	int i;
+	intnode_t lookup, *inp;
+
+	for (i = 10; i < 30; i++) {
+		lookup.in_val = i;
+		inp = avl_find(&inttree, &lookup, NULL);
+		if (inp == NULL) {
+			printf("Entry %d is not in the tree\\n", i);
+		} else {
+			printf("Entry %d is in the tree\\n",
+			    inp->in_val);
+		}
+	}
+}
+
+/*
+ * Walk the tree forwards
+ */
+static void
+walk_forwards(void)
+{
+	intnode_t *inp;
+	for (inp = avl_first(&inttree); inp != NULL;
+	    inp = AVL_NEXT(&inttree, inp)) {
+		printf("Found entry %d\\n", inp->in_val);
+	}
+}
+
+/*
+ * Walk the tree backwards.
+ */
+static void
+walk_backwards(void)
+{
+	intnode_t *inp;
+	for (inp = avl_last(&inttree); inp != NULL;
+	    inp = AVL_PREV(&inttree, inp)) {
+		printf("Found entry %d\\n", inp->in_val);
+	}
+}
+
+/*
+ * Determine the number of nodes in the tree and if it is empty or
+ * not.
+ */
+static void
+inttree_inspect(void)
+{
+	printf("The tree is %s, there are %ld nodes in it\\n",
+	    avl_is_empty(&inttree) == B_TRUE ? "empty" : "not empty",
+	    avl_numnodes(&inttree));
+}
+
+/*
+ * Use avl_remove to remove entries from the tree.
+ */
+static void
+remove_nodes(void)
+{
+	int i;
+	intnode_t lookup, *inp;
+
+	for (i = 0; i < 20; i+= 4) {
+		lookup.in_val = i;
+		inp = avl_find(&inttree, &lookup, NULL);
+		if (inp != NULL)
+			avl_remove(&inttree, inp);
+	}
+}
+
+/*
+ * Find the nearest nodes in the tree.
+ */
+static void
+nearest_nodes(void)
+{
+	intnode_t lookup, *inp;
+	avl_index_t where;
+
+	lookup.in_val = 12;
+	if (avl_find(&inttree, &lookup, &where) != NULL)
+		abort();
+	inp = avl_nearest(&inttree, where, AVL_BEFORE);
+	assert(inp != NULL);
+	printf("closest node before 12 is: %d\\n", inp->in_val);
+	inp = avl_nearest(&inttree, where, AVL_AFTER);
+	assert(inp != NULL);
+	printf("closest node after 12 is: %d\\n", inp->in_val);
+}
+
+static void
+insert_avl(void)
+{
+	intnode_t lookup, *inp;
+	avl_index_t where;
+
+	lookup.in_val = 12;
+	if (avl_find(&inttree, &lookup, &where) != NULL)
+		abort();
+	inp = malloc(sizeof (intnode_t));
+	assert(inp != NULL);
+	avl_insert(&inttree, inp, where);
+}
+
+static void
+swap_avl(void)
+{
+	avl_tree_t swap;
+
+	avl_create(&swap, intnode_comparator, sizeof (intnode_t),
+	    offsetof(intnode_t, in_avl));
+	avl_swap(&inttree, &swap);
+	inttree_inspect();
+	avl_swap(&inttree, &swap);
+	inttree_inspect();
+}
+
+/*
+ * Remove all remaining nodes in the tree. We first use
+ * avl_destroy_nodes to empty the tree, then avl_destroy to finish.
+ */
+static void
+cleanup(void)
+{
+	intnode_t *inp;
+	void *c = NULL;
+
+	while ((inp = avl_destroy_nodes(&inttree, &c)) != NULL) {
+		free(inp);
+	}
+	avl_destroy(&inttree);
+}
+
+int
+main(void)
+{
+	create_avl();
+	inttree_inspect();
+	fill_avl();
+	find_avl();
+	walk_forwards();
+	walk_backwards();
+	inttree_inspect();
+	remove_nodes();
+	inttree_inspect();
+	nearest_nodes();
+	insert_avl();
+	inttree_inspect();
+	swap_avl();
+	cleanup();
+	return (0);
+}
+.Ed
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Level
+See
+.Sx Locking.
+.Sh SEE ALSO
+.Xr Intro 3 ,
+.Xr pthread_atfork 3C
+.Lp
+.Xr avl_add 3AVL ,
+.Xr avl_create 3AVL ,
+.Xr avl_destroy 3AVL ,
+.Xr avl_destroy_nodes 3AVL ,
+.Xr avl_find 3AVL ,
+.Xr avl_first 3AVL ,
+.Xr avl_insert 3AVL ,
+.Xr avl_insert_here 3AVL ,
+.Xr avl_is_empty 3AVL ,
+.Xr avl_last 3AVL ,
+.Xr avl_nearest 3AVL ,
+.Xr avl_numnodes 3AVL ,
+.Xr avl_remove 3AVL ,
+.Xr avl_swap 3AVL ,
+.Rs
+.%A Adel'son-Vel'skiy, G. M.
+.%A Landis, Ye. M.
+.%T "An Algorithm for the Organization of Information"
+.%Q Deklady Akademii Nauk
+.%C USSR, Moscow
+.%P 263-266
+.%V Vol. 16
+.%N No. 2
+.%D 1962
+.Re
diff --git a/usr/src/man/man9f/Makefile b/usr/src/man/man9f/Makefile
index 1198accfda..815e2f8a10 100644
--- a/usr/src/man/man9f/Makefile
+++ b/usr/src/man/man9f/Makefile
@@ -37,6 +37,7 @@ MANFILES= 	ASSERT.9f				\
 	 	atomic_ops.9f				\
 	 	atomic_or.9f				\
 	 	atomic_swap.9f				\
+		avl.9f					\
 	 	backq.9f				\
 	 	bcanput.9f				\
 	 	bcmp.9f					\
@@ -628,6 +629,21 @@ MANLINKS=	SIZEOF_PTR.9f				\
 	 	atomic_swap_uint.9f			\
 	 	atomic_swap_ulong.9f			\
 	 	atomic_swap_ushort.9f			\
+		avl_add.9f				\
+		avl_create.9f				\
+		avl_destroy.9f				\
+		avl_destroy_nodes.9f			\
+		avl_find.9f 				\
+		avl_first.9f				\
+		avl_insert.9f				\
+		avl_insert_here.9f			\
+		avl_is_empty.9f				\
+		avl_last.9f				\
+		avl_nearest.9f				\
+		avl_numnodes.9f				\
+		avl_swap.9f				\
+		AVL_NEXT.9f				\
+		AVL_PREV.9f				\
 	 	bcanputnext.9f				\
 	 	crgetgid.9f				\
 	 	crgetgroups.9f				\
@@ -1303,6 +1319,22 @@ atomic_swap_uint.9f			:= LINKSRC = atomic_swap.9f
 atomic_swap_ulong.9f			:= LINKSRC = atomic_swap.9f
 atomic_swap_ushort.9f			:= LINKSRC = atomic_swap.9f
 
+avl_add.9f				:= LINKSRC = avl.9f
+avl_create.9f				:= LINKSRC = avl.9f
+avl_destroy.9f				:= LINKSRC = avl.9f
+avl_destroy_nodes.9f			:= LINKSRC = avl.9f
+avl_find.9f 				:= LINKSRC = avl.9f
+avl_first.9f				:= LINKSRC = avl.9f
+avl_insert.9f				:= LINKSRC = avl.9f
+avl_insert_here.9f			:= LINKSRC = avl.9f
+avl_is_empty.9f				:= LINKSRC = avl.9f
+avl_last.9f				:= LINKSRC = avl.9f
+avl_nearest.9f				:= LINKSRC = avl.9f
+avl_numnodes.9f				:= LINKSRC = avl.9f
+avl_swap.9f				:= LINKSRC = avl.9f
+AVL_NEXT.9f				:= LINKSRC = avl.9f
+AVL_PREV.9f				:= LINKSRC = avl.9f
+
 dev_err.9f				:= LINKSRC = cmn_err.9f
 vcmn_err.9f				:= LINKSRC = cmn_err.9f
 vzcmn_err.9f				:= LINKSRC = cmn_err.9f
diff --git a/usr/src/man/man9f/avl.9f b/usr/src/man/man9f/avl.9f
new file mode 100644
index 0000000000..e494abad65
--- /dev/null
+++ b/usr/src/man/man9f/avl.9f
@@ -0,0 +1,88 @@
+.\"
+.\" This file and its contents are supplied under the terms of the
+.\" Common Development and Distribution License ("CDDL"), version 1.0.
+.\" You may only use this file in accordance with the terms of version
+.\" 1.0 of the CDDL.
+.\"
+.\" A full copy of the text of the CDDL should have accompanied this
+.\" source.  A copy of the CDDL is also available via the Internet at
+.\" http://www.illumos.org/license/CDDL.
+.\"
+.\"
+.\" Copyright 2015 Joyent, Inc.
+.\"
+.Dd May 08, 2015
+.Dt AVL 9F
+.Os
+.Sh NAME
+.Nm avl ,
+.Nm avl_add ,
+.Nm avl_create ,
+.Nm avl_destroy ,
+.Nm avl_destroy_nodes ,
+.Nm avl_find  ,
+.Nm avl_first ,
+.Nm avl_insert ,
+.Nm avl_insert_here ,
+.Nm avl_is_empty ,
+.Nm avl_last ,
+.Nm avl_nearest ,
+.Nm avl_numnodes ,
+.Nm avl_swap ,
+.Nm AVL_NEXT ,
+.Nm AVL_PREV ,
+.Nd AVL tree routines
+.Sh DESCRIPTION
+AVL trees are a general purpose, self-balancing binary tree that can be
+used instead of the standard linked list interfaces --
+.Xr list_create 9F .
+AVL trees are particularly useful either when order is important or
+better lookup performance is required.
+.Pp
+The AVL tree interfaces are identical in both userland and the kernel.
+For more general information on AVL trees, see
+.Xr libavl 3LIB .
+For more information on any of the funtions defined here, please see the
+corresponding manual page in section 3AVL. Please note, that while
+the descriptions in those manual pages are accurate for writers of
+Device Drivers, the examples provided use scaffolding not available in
+the kernel, such as the use of
+.Fn malloc ,
+and need to be adapated.
+.Sh CONTEXT
+All of the AVL routines may be used in user, kernel, and interrupt
+context.
+.Sh EXAMPLES
+See
+.Sy EXAMPLES
+in
+.Xr libavl 3LIB .
+.Sh INTERFACE STABILITY
+.Sy Committed
+.Sh MT-Safety
+AVL trees do not inherently have any internal locking, it is up to the
+consumer to use locks as appropriate. See
+.Xr mutex 9F
+and
+.Xr rwlock 9F
+for more information on synchronization primitives.
+.Sh SEE ALSO
+.Xr libavl 3LIB ,
+.Xr avl_add 3AVL ,
+.Xr avl_create 3AVL ,
+.Xr avl_destroy 3AVL ,
+.Xr avl_destroy_nodes 3AVL ,
+.Xr avl_find  3AVL ,
+.Xr avl_first 3AVL ,
+.Xr avl_insert 3AVL ,
+.Xr avl_insert_here 3AVL ,
+.Xr avl_is_empty 3AVL ,
+.Xr avl_last 3AVL ,
+.Xr avl_nearest 3AVL ,
+.Xr avl_numnodes 3AVL ,
+.Xr avl_swap 3AVL ,
+.Xr AVL_NEXT 3AVL ,
+.Xr AVL_PREV 3AVL ,
+.Rs
+.%T Writing Device Drivers
+.Re
diff --git a/usr/src/pkg/manifests/developer-library-lint.mf b/usr/src/pkg/manifests/developer-library-lint.mf
index d0dff37e76..f9397a1c45 100644
--- a/usr/src/pkg/manifests/developer-library-lint.mf
+++ b/usr/src/pkg/manifests/developer-library-lint.mf
@@ -46,6 +46,7 @@ dir path=usr/xpg4/lib
 dir path=usr/xpg4/lib/$(ARCH64)
 file path=lib/$(ARCH64)/llib-ladm.ln
 file path=lib/$(ARCH64)/llib-laio.ln
+file path=lib/$(ARCH64)/llib-lavl.ln
 file path=lib/$(ARCH64)/llib-lbsm.ln
 file path=lib/$(ARCH64)/llib-lc.ln
 file path=lib/$(ARCH64)/llib-lc_db.ln
@@ -97,6 +98,8 @@ file path=lib/llib-ladm
 file path=lib/llib-ladm.ln
 file path=lib/llib-laio
 file path=lib/llib-laio.ln
+file path=lib/llib-lavl
+file path=lib/llib-lavl.ln
 file path=lib/llib-lbsm
 file path=lib/llib-lbsm.ln
 file path=lib/llib-lc
@@ -403,6 +406,8 @@ link path=usr/lib/$(ARCH64)/llib-ladm.ln \
     target=../../../lib/$(ARCH64)/llib-ladm.ln
 link path=usr/lib/$(ARCH64)/llib-laio.ln \
     target=../../../lib/$(ARCH64)/llib-laio.ln
+link path=usr/lib/$(ARCH64)/llib-lavl.ln \
+    target=../../../lib/$(ARCH64)/llib-lavl.ln
 link path=usr/lib/$(ARCH64)/llib-lbsm.ln \
     target=../../../lib/$(ARCH64)/llib-lbsm.ln
 link path=usr/lib/$(ARCH64)/llib-lc.ln \
@@ -489,6 +494,8 @@ link path=usr/lib/llib-ladm target=../../lib/llib-ladm
 link path=usr/lib/llib-ladm.ln target=../../lib/llib-ladm.ln
 link path=usr/lib/llib-laio target=../../lib/llib-laio
 link path=usr/lib/llib-laio.ln target=../../lib/llib-laio.ln
+link path=usr/lib/llib-lavl target=../../lib/llib-lavl
+link path=usr/lib/llib-lavl.ln target=../../lib/llib-lavl.ln
 link path=usr/lib/llib-lbsm target=../../lib/llib-lbsm
 link path=usr/lib/llib-lbsm.ln target=../../lib/llib-lbsm.ln
 link path=usr/lib/llib-lc target=../../lib/llib-lc
diff --git a/usr/src/pkg/manifests/system-kernel.man9f.inc b/usr/src/pkg/manifests/system-kernel.man9f.inc
index af0d6d34ae..d2c87c23be 100644
--- a/usr/src/pkg/manifests/system-kernel.man9f.inc
+++ b/usr/src/pkg/manifests/system-kernel.man9f.inc
@@ -33,6 +33,7 @@ file path=usr/share/man/man9f/atomic_inc.9f
 file path=usr/share/man/man9f/atomic_ops.9f
 file path=usr/share/man/man9f/atomic_or.9f
 file path=usr/share/man/man9f/atomic_swap.9f
+file path=usr/share/man/man9f/avl.9f
 file path=usr/share/man/man9f/backq.9f
 file path=usr/share/man/man9f/bcanput.9f
 file path=usr/share/man/man9f/bcmp.9f
@@ -476,6 +477,8 @@ file path=usr/share/man/man9f/ureadc.9f
 file path=usr/share/man/man9f/uwritec.9f
 file path=usr/share/man/man9f/va_arg.9f
 file path=usr/share/man/man9f/vsprintf.9f
+link path=usr/share/man/man9f/AVL_NEXT.9f target=avl.9f
+link path=usr/share/man/man9f/AVL_PREV.9f target=avl.9f
 link path=usr/share/man/man9f/SIZEOF_PTR.9f target=STRUCT_DECL.9f
 link path=usr/share/man/man9f/SIZEOF_STRUCT.9f target=STRUCT_DECL.9f
 link path=usr/share/man/man9f/STRUCT_BUF.9f target=STRUCT_DECL.9f
@@ -595,6 +598,19 @@ link path=usr/share/man/man9f/atomic_swap_uchar.9f target=atomic_swap.9f
 link path=usr/share/man/man9f/atomic_swap_uint.9f target=atomic_swap.9f
 link path=usr/share/man/man9f/atomic_swap_ulong.9f target=atomic_swap.9f
 link path=usr/share/man/man9f/atomic_swap_ushort.9f target=atomic_swap.9f
+link path=usr/share/man/man9f/avl_add.9f target=avl.9f
+link path=usr/share/man/man9f/avl_create.9f target=avl.9f
+link path=usr/share/man/man9f/avl_destroy.9f target=avl.9f
+link path=usr/share/man/man9f/avl_destroy_nodes.9f target=avl.9f
+link path=usr/share/man/man9f/avl_find.9f target=avl.9f
+link path=usr/share/man/man9f/avl_first.9f target=avl.9f
+link path=usr/share/man/man9f/avl_insert.9f target=avl.9f
+link path=usr/share/man/man9f/avl_insert_here.9f target=avl.9f
+link path=usr/share/man/man9f/avl_is_empty.9f target=avl.9f
+link path=usr/share/man/man9f/avl_last.9f target=avl.9f
+link path=usr/share/man/man9f/avl_nearest.9f target=avl.9f
+link path=usr/share/man/man9f/avl_numnodes.9f target=avl.9f
+link path=usr/share/man/man9f/avl_swap.9f target=avl.9f
 link path=usr/share/man/man9f/bcanputnext.9f target=canputnext.9f
 link path=usr/share/man/man9f/crgetgid.9f target=ddi_cred.9f
 link path=usr/share/man/man9f/crgetgroups.9f target=ddi_cred.9f
diff --git a/usr/src/pkg/manifests/system-library.man3avl.inc b/usr/src/pkg/manifests/system-library.man3avl.inc
new file mode 100644
index 0000000000..4f965712db
--- /dev/null
+++ b/usr/src/pkg/manifests/system-library.man3avl.inc
@@ -0,0 +1,32 @@
+#
+# This file and its contents are supplied under the terms of the
+# Common Development and Distribution License ("CDDL"), version 1.0.
+# You may only use this file in accordance with the terms of version
+# 1.0 of the CDDL.
+#
+# A full copy of the text of the CDDL should have accompanied this
+# source.  A copy of the CDDL is also available via the Internet
+# at http://www.illumos.org/license/CDDL.
+#
+
+#
+# Copyright 2015, Joyent, Inc.
+#
+
+file path=usr/share/man/man3avl/avl_add.3avl
+file path=usr/share/man/man3avl/avl_create.3avl
+file path=usr/share/man/man3avl/avl_destroy.3avl
+file path=usr/share/man/man3avl/avl_destroy_nodes.3avl
+file path=usr/share/man/man3avl/avl_find.3avl
+file path=usr/share/man/man3avl/avl_first.3avl
+file path=usr/share/man/man3avl/avl_insert.3avl
+file path=usr/share/man/man3avl/avl_is_empty.3avl
+file path=usr/share/man/man3avl/avl_nearest.3avl
+file path=usr/share/man/man3avl/avl_numnodes.3avl
+file path=usr/share/man/man3avl/avl_swap.3avl
+link path=usr/share/man/man3avl/AVL_NEXT.3avl target=avl_first.3avl
+link path=usr/share/man/man3avl/AVL_PREV.3avl target=avl_first.3avl
+link path=usr/share/man/man3avl/avl_insert_here.3avl target=avl_insert.3avl
+link path=usr/share/man/man3avl/avl_last.3avl target=avl_first.3avl
+link path=usr/share/man/man3avl/avl_remove.3avl target=avl_add.3avl
+
diff --git a/usr/src/pkg/manifests/system-library.man3lib.inc b/usr/src/pkg/manifests/system-library.man3lib.inc
index f017f5dc87..32f4a7c62f 100644
--- a/usr/src/pkg/manifests/system-library.man3lib.inc
+++ b/usr/src/pkg/manifests/system-library.man3lib.inc
@@ -16,6 +16,7 @@
 
 file path=usr/share/man/man3lib/libadm.3lib
 file path=usr/share/man/man3lib/libaio.3lib
+file path=usr/share/man/man3lib/libavl.3lib
 file path=usr/share/man/man3lib/libbsdmalloc.3lib
 file path=usr/share/man/man3lib/libbsm.3lib
 file path=usr/share/man/man3lib/libc.3lib
diff --git a/usr/src/pkg/manifests/system-library.mf b/usr/src/pkg/manifests/system-library.mf
index 3463041f8e..e50eb582df 100644
--- a/usr/src/pkg/manifests/system-library.mf
+++ b/usr/src/pkg/manifests/system-library.mf
@@ -27,6 +27,7 @@
 #
 
 <include system-library.man3.inc>
+<include system-library.man3avl.inc>
 <include system-library.man3bsm.inc>
 <include system-library.man3c.inc>
 <include system-library.man3c_db.inc>
@@ -122,6 +123,7 @@ dir path=usr/lib/security
 dir path=usr/lib/security/$(ARCH64)
 dir path=usr/share/man
 dir path=usr/share/man/man3
+dir path=usr/share/man/man3avl
 dir path=usr/share/man/man3bsm
 dir path=usr/share/man/man3c
 dir path=usr/share/man/man3c_db
@@ -597,6 +599,7 @@ license usr/src/uts/common/sys/THIRDPARTYLICENSE.unicode \
     license=usr/src/uts/common/sys/THIRDPARTYLICENSE.unicode
 link path=lib/$(ARCH64)/libadm.so target=libadm.so.1
 link path=lib/$(ARCH64)/libaio.so target=libaio.so.1
+link path=lib/$(ARCH64)/libavl.so target=libavl.so.1
 link path=lib/$(ARCH64)/libbsm.so target=libbsm.so.1
 link path=lib/$(ARCH64)/libc.so reboot-needed=true target=libc.so.1
 link path=lib/$(ARCH64)/libc_db.so target=libc_db.so.1
@@ -660,6 +663,7 @@ link path=lib/crypto/32 target=.
 link path=lib/crypto/64 target=$(ARCH64)
 link path=lib/libadm.so target=libadm.so.1
 link path=lib/libaio.so target=libaio.so.1
+link path=lib/libavl.so target=libavl.so.1
 link path=lib/libbsm.so target=libbsm.so.1
 link path=lib/libc.so target=libc.so.1
 link path=lib/libc_db.so target=libc_db.so.1
@@ -758,6 +762,8 @@ link path=usr/lib/$(ARCH64)/libaio.so \
     target=../../../lib/$(ARCH64)/libaio.so.1
 link path=usr/lib/$(ARCH64)/libaio.so.1 \
     target=../../../lib/$(ARCH64)/libaio.so.1
+link path=usr/lib/$(ARCH64)/libavl.so \
+    target=../../../lib/$(ARCH64)/libavl.so.1
 link path=usr/lib/$(ARCH64)/libavl.so.1 \
     target=../../../lib/$(ARCH64)/libavl.so.1
 link path=usr/lib/$(ARCH64)/libbsdmalloc.so target=libbsdmalloc.so.1
@@ -1036,6 +1042,7 @@ link path=usr/lib/libadm.so.1 target=../../lib/libadm.so.1
 link path=usr/lib/libadutils.so target=./libadutils.so.1
 link path=usr/lib/libaio.so target=../../lib/libaio.so.1
 link path=usr/lib/libaio.so.1 target=../../lib/libaio.so.1
+link path=usr/lib/libavl.so target=../../lib/libavl.so.1
 link path=usr/lib/libavl.so.1 target=../../lib/libavl.so.1
 link path=usr/lib/libbsdmalloc.so target=./libbsdmalloc.so.1
 link path=usr/lib/libbsm.so target=../../lib/libbsm.so.1
diff --git a/usr/src/uts/common/sys/avl.h b/usr/src/uts/common/sys/avl.h
index 10e0ddaeef..cc4af828e6 100644
--- a/usr/src/uts/common/sys/avl.h
+++ b/usr/src/uts/common/sys/avl.h
@@ -30,11 +30,6 @@
 #ifndef	_AVL_H
 #define	_AVL_H
 
-/*
- * This is a private header file.  Applications should not directly include
- * this file.
- */
-
 #ifdef	__cplusplus
 extern "C" {
 #endif
@@ -43,9 +38,9 @@ extern "C" {
 #include <sys/avl_impl.h>
 
 /*
- * This is a generic implementation 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
@@ -57,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))
  *