doc: add some red-black tree documentation

closes #2059

3 files changed, 103 insertions, 4 deletions

diff --git a/doc/user/Makefile.am b/doc/user/Makefile.am
index e7743199df..cd8b5f3f4d 100644
--- a/doc/user/Makefile.am
+++ b/doc/user/Makefile.am
@@ -14,8 +14,8 @@ GENERATED_FILES = overview.texi concepts.texi datatypes.texi init.texi \
     task.texi intr.texi clock.texi timer.texi sem.texi msg.texi event.texi \
     signal.texi part.texi region.texi dpmem.texi io.texi fatal.texi \
     schedule.texi rtmon.texi barrier.texi bsp.texi userext.texi conf.texi \
-    mp.texi stackchk.texi cpuuse.texi object.texi chains.texi timespec.texi \
-    cbs.texi dirstat.texi smp.texi
+    mp.texi stackchk.texi cpuuse.texi object.texi chains.texi rbtree.texi \
+    timespec.texi cbs.texi dirstat.texi smp.texi
 
 COMMON_FILES += $(top_srcdir)/common/cpright.texi
 
@@ -186,10 +186,15 @@ object.texi: object.t
 chains.texi: chains.t
 	$(BMENU2) -p "Object Services OBJECT_GET_CLASS_INFORMATION - Obtain Class Information" \
 	    -u "Top" \
+	    -n "Red-Black Trees" < $< > $@
+
+rbtree.texi: rbtree.t
+	$(BMENU2) -p "Chains Prepend a Node" \
+	    -u "Top" \
 	    -n "Timespec Helpers" < $< > $@
 
 timespec.texi: timespec.t
-	$(BMENU2) -p "Chains Prepend a Node" \
+	$(BMENU2) -p "Red-Black Trees Documentation for the Red-Black Tree Directives" \
 	    -u "Top" \
 	    -n "Constant Bandwidth Server Scheduler API" < $< > $@
 
@@ -205,7 +210,7 @@ dirstat.texi: dirstat.t
 
 EXTRA_DIST = bsp.t cbs.t clock.t chains.t concepts.t cpuuse.t datatypes.t conf.t \
     dpmem.t event.t fatal.t init.t intr.t io.t mp.t msg.t overview.t \
-    part.t region.t rtmon.t sem.t schedule.t signal.t stackchk.t \
+    part.t rbtree.t region.t rtmon.t sem.t schedule.t signal.t stackchk.t \
     task.t timer.t userext.t dirstat.t $(TXT_FILES) $(PNG_FILES) $(EPS_IMAGES) \
     $(noinst_DATA)
 
diff --git a/doc/user/c_user.texi b/doc/user/c_user.texi
index 2085415e3a..2ff47bf54b 100644
--- a/doc/user/c_user.texi
+++ b/doc/user/c_user.texi
@@ -111,6 +111,7 @@
 * CPU Usage Statistics::
 * Object Services::
 * Chains::
+* Red-Black Trees::
 * Timespec Helpers::
 * Constant Bandwidth Server Scheduler API::
 * Directive Status Codes::
@@ -155,6 +156,7 @@
 @include cpuuse.texi
 @include object.texi
 @include chains.texi
+@include rbtree.texi
 @include timespec.texi
 @include cbs.texi
 @include dirstat.texi
diff --git a/doc/user/rbtree.t b/doc/user/rbtree.t
new file mode 100644
index 0000000000..c90065b6ce
--- /dev/null
+++ b/doc/user/rbtree.t
@@ -0,0 +1,92 @@
+@c
+@c Copyright 2014 Gedare Bloom. 
+@c All rights reserved.
+
+@chapter Red-Black Trees
+
+@cindex rbtrees
+
+@section Introduction
+
+The Red-Black Tree API is an interface to the SuperCore (score) rbtree
+implementation. Within RTEMS, red-black trees are used when a binary search
+tree is needed, including dynamic priority thread queues and non-contiguous
+heap memory. The Red-Black Tree API provided by RTEMS is:
+
+@itemize @bullet
+@c build_id
+@item @code{@value{DIRPREFIX}rtems_rbtree_node} - Red-Black Tree node embedded in another struct
+@item @code{@value{DIRPREFIX}rtems_rbtree_control} - Red-Black Tree control node for an entire tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_initialize} - initialize the red-black tree with nodes
+@item @code{@value{DIRPREFIX}rtems_rbtree_initialize_empty} - initialize the red-black tree as empty
+@item @code{@value{DIRPREFIX}rtems_rbtree_set_off_tree} - Clear a node's links
+@item @code{@value{DIRPREFIX}rtems_rbtree_root} - Return the red-black tree's root node
+@item @code{@value{DIRPREFIX}rtems_rbtree_min} - Return the red-black tree's minimum node
+@item @code{@value{DIRPREFIX}rtems_rbtree_max} - Return the red-black tree's maximum node
+@item @code{@value{DIRPREFIX}rtems_rbtree_left} - Return a node's left child node
+@item @code{@value{DIRPREFIX}rtems_rbtree_right} - Return a node's right child node
+@item @code{@value{DIRPREFIX}rtems_rbtree_parent} - Return a node's parent node
+@item @code{@value{DIRPREFIX}rtems_rbtree_are_nodes_equal} - Are the node's equal ?
+@item @code{@value{DIRPREFIX}rtems_rbtree_is_empty} - Is the red-black tree empty ?
+@item @code{@value{DIRPREFIX}rtems_rbtree_is_min} - Is the Node the minimum in the red-black tree ?
+@item @code{@value{DIRPREFIX}rtems_rbtree_is_max} - Is the Node the maximum in the red-black tree ?
+@item @code{@value{DIRPREFIX}rtems_rbtree_is_root} - Is the Node the root of the red-black tree ?
+@item @code{@value{DIRPREFIX}rtems_rbtree_find} - Find the node with a matching key in the red-black tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_predecessor} - Return the in-order predecessor of a node.
+@item @code{@value{DIRPREFIX}rtems_rbtree_successor} - Return the in-order successor of a node.
+@item @code{@value{DIRPREFIX}rtems_rbtree_extract} - Remove the node from the red-black tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_get_min} - Remove the minimum node from the red-black tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_get_max} - Remove the maximum node from the red-black tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_peek_min} - Returns the minimum node from the red-black tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_peek_max} - Returns the maximum node from the red-black tree
+@item @code{@value{DIRPREFIX}rtems_rbtree_find_control} - Returns the control node of a red-black tree given a node in the tree.
+@item @code{@value{DIRPREFIX}rtems_rbtree_insert} - Add the node to the red-black tree
+@end itemize
+
+@section Background
+
+The Red-Black Trees API is a thin layer above the SuperCore Red-Black Trees
+implementation. A Red-Black Tree is defined by a control node with pointers to
+the root, minimum, and maximum nodes in the tree. Each node in the tree
+consists of a parent pointer, two children pointers, and a color attribute.  A
+tree is parameterized as either unique, meaning identical keys are rejected, or
+not, in which case duplicate keys are allowed.
+
+Users must provide a comparison functor that gets passed to functions that need
+to compare nodes. In addition, no internal synchronization is offered within
+the red-black tree implementation, thus users must ensure at most one thread
+accesses a red-black tree instance at a time.
+
+@subsection Nodes
+
+A red-black tree is made up from nodes that orginate from a red-black tree control
+object. A node is of type @code{@value{DIRPREFIX}rtems_rbtree_node}. The node
+is designed to be part of a user data structure. To obtain the encapsulating
+structure users can use the @code{RTEMS_CONTAINER_OF} macro.
+The node can be placed anywhere within the user's structure and the macro will
+calculate the structure's address from the node's address. 
+
+@subsection Controls
+
+A red-black tree is rooted with a control object. Red-Black Tree control
+provide the user with access to the nodes on the red-black tree.  The
+implementation does not require special checks for manipulating the root of the
+red-black tree. To accomplish this the
+@code{@value{DIRPREFIX}rtems_rbtree_control} structure is treated as a
+@code{@value{DIRPREFIX}rtems_rbtree_node} structure with a @code{NULL} parent
+and left child pointing to the root. 
+
+@section Operations
+
+Examples for using the red-black trees
+can be found in the testsuites/sptests/sprbtree01/init.c file.
+
+@section Directives
+
+@subsection Documentation for the Red-Black Tree Directives
+
+@cindex rbtree doc
+
+Source documentation for the Red-Black Tree API can be found in the
+generated Doxygen output for cpukit/sapi.
+