From 0a789927c54d63d043ab257378058ce896691dc3 Mon Sep 17 00:00:00 2001 From: Gedare Bloom Date: Fri, 19 Dec 2014 11:44:39 -0500 Subject: 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(-) create mode 100644 doc/user/rbtree.t 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 @@ -185,11 +185,16 @@ 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. + -- cgit v1.2.3