[rtems commit] doc: add some red-black tree documentation
Gedare Bloom
gedare at rtems.org
Fri Dec 19 17:17:45 UTC 2014
Module: rtems
Branch: master
Commit: 0a789927c54d63d043ab257378058ce896691dc3
Changeset: http://git.rtems.org/rtems/commit/?id=0a789927c54d63d043ab257378058ce896691dc3
Author: Gedare Bloom <gedare at rtems.org>
Date: Fri Dec 19 11:44:39 2014 -0500
doc: add some red-black tree documentation
closes #2059
---
doc/user/Makefile.am | 13 +++++---
doc/user/c_user.texi | 2 ++
doc/user/rbtree.t | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 103 insertions(+), 4 deletions(-)
diff --git a/doc/user/Makefile.am b/doc/user/Makefile.am
index e774319..cd8b5f3 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 2085415..2ff47bf 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
+ at 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 0000000..c90065b
--- /dev/null
+++ b/doc/user/rbtree.t
@@ -0,0 +1,92 @@
+ at c
+ at c Copyright 2014 Gedare Bloom.
+ at c All rights reserved.
+
+ at chapter Red-Black Trees
+
+ at cindex rbtrees
+
+ at 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:
+
+ at itemize @bullet
+ at c build_id
+ at item @code{@value{DIRPREFIX}rtems_rbtree_node} - Red-Black Tree node embedded in another struct
+ at item @code{@value{DIRPREFIX}rtems_rbtree_control} - Red-Black Tree control node for an entire tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_initialize} - initialize the red-black tree with nodes
+ at item @code{@value{DIRPREFIX}rtems_rbtree_initialize_empty} - initialize the red-black tree as empty
+ at item @code{@value{DIRPREFIX}rtems_rbtree_set_off_tree} - Clear a node's links
+ at item @code{@value{DIRPREFIX}rtems_rbtree_root} - Return the red-black tree's root node
+ at item @code{@value{DIRPREFIX}rtems_rbtree_min} - Return the red-black tree's minimum node
+ at item @code{@value{DIRPREFIX}rtems_rbtree_max} - Return the red-black tree's maximum node
+ at item @code{@value{DIRPREFIX}rtems_rbtree_left} - Return a node's left child node
+ at item @code{@value{DIRPREFIX}rtems_rbtree_right} - Return a node's right child node
+ at item @code{@value{DIRPREFIX}rtems_rbtree_parent} - Return a node's parent node
+ at item @code{@value{DIRPREFIX}rtems_rbtree_are_nodes_equal} - Are the node's equal ?
+ at item @code{@value{DIRPREFIX}rtems_rbtree_is_empty} - Is the red-black tree empty ?
+ at item @code{@value{DIRPREFIX}rtems_rbtree_is_min} - Is the Node the minimum in the red-black tree ?
+ at item @code{@value{DIRPREFIX}rtems_rbtree_is_max} - Is the Node the maximum in the red-black tree ?
+ at item @code{@value{DIRPREFIX}rtems_rbtree_is_root} - Is the Node the root of the red-black tree ?
+ at item @code{@value{DIRPREFIX}rtems_rbtree_find} - Find the node with a matching key in the red-black tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_predecessor} - Return the in-order predecessor of a node.
+ at item @code{@value{DIRPREFIX}rtems_rbtree_successor} - Return the in-order successor of a node.
+ at item @code{@value{DIRPREFIX}rtems_rbtree_extract} - Remove the node from the red-black tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_get_min} - Remove the minimum node from the red-black tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_get_max} - Remove the maximum node from the red-black tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_peek_min} - Returns the minimum node from the red-black tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_peek_max} - Returns the maximum node from the red-black tree
+ at item @code{@value{DIRPREFIX}rtems_rbtree_find_control} - Returns the control node of a red-black tree given a node in the tree.
+ at item @code{@value{DIRPREFIX}rtems_rbtree_insert} - Add the node to the red-black tree
+ at end itemize
+
+ at 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.
+
+ at 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.
+
+ at 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
+ at code{@value{DIRPREFIX}rtems_rbtree_control} structure is treated as a
+ at code{@value{DIRPREFIX}rtems_rbtree_node} structure with a @code{NULL} parent
+and left child pointing to the root.
+
+ at section Operations
+
+Examples for using the red-black trees
+can be found in the testsuites/sptests/sprbtree01/init.c file.
+
+ at section Directives
+
+ at subsection Documentation for the Red-Black Tree Directives
+
+ at cindex rbtree doc
+
+Source documentation for the Red-Black Tree API can be found in the
+generated Doxygen output for cpukit/sapi.
+
More information about the vc
mailing list