diff options
| author | Chris Johns <chrisj@rtems.org> | 2016-02-18 15:29:28 +1100 |
|---|---|---|
| committer | Amar Takhar <verm@darkbeer.org> | 2016-05-02 20:51:26 -0400 |
| commit | 0d86b7111e378286bd61613c363c06cec39d0538 (patch) | |
| tree | db53c1ba4c2ac32c0a1420bfc9074f4c2b526445 /c_user/red_black_trees.rst | |
| parent | Add semaphore attributes figure. (diff) | |
| download | rtems-docs-0d86b7111e378286bd61613c363c06cec39d0538.tar.bz2 | |
Clean up.
Diffstat (limited to '')
| -rw-r--r-- | c_user/red_black_trees.rst | 36 |
1 files changed, 16 insertions, 20 deletions
diff --git a/c_user/red_black_trees.rst b/c_user/red_black_trees.rst index 35c8db9..1884dfa 100644 --- a/c_user/red_black_trees.rst +++ b/c_user/red_black_trees.rst @@ -1,3 +1,7 @@ +.. COMMENT: COPYRIGHT (c) 1988-2012. +.. COMMENT: On-Line Applications Research Corporation (OAR). +.. COMMENT: All rights reserved. + Red-Black Trees ############### @@ -11,8 +15,6 @@ 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: -- build_id - - ``rtems_rtems_rbtree_node`` - Red-Black Tree node embedded in another struct - ``rtems_rtems_rbtree_control`` - Red-Black Tree control node for an entire tree @@ -81,12 +83,12 @@ accesses a red-black tree instance at a time. Nodes ----- -A red-black tree is made up from nodes that orginate from a red-black tree control -object. A node is of type ``rtems_rtems_rbtree_node``. The node -is designed to be part of a user data structure. To obtain the encapsulating -structure users can use the ``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. +A red-black tree is made up from nodes that orginate from a red-black tree +control object. A node is of type ``rtems_rtems_rbtree_node``. The node is +designed to be part of a user data structure. To obtain the encapsulating +structure users can use the ``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. Controls -------- @@ -94,14 +96,15 @@ 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``rtems_rtems_rbtree_control`` structure is treated as a``rtems_rtems_rbtree_node`` structure with a ``NULL`` parent +red-black tree. To accomplish this the ``rtems_rtems_rbtree_control`` structure +is treated as a ``rtems_rtems_rbtree_node`` structure with a ``NULL`` parent and left child pointing to the root. Operations ========== -Examples for using the red-black trees -can be found in the testsuites/sptests/sprbtree01/init.c file. +Examples for using the red-black trees can be found in the +``testsuites/sptests/sprbtree01/init.c`` file. Directives ========== @@ -110,12 +113,5 @@ Documentation for the Red-Black Tree Directives ----------------------------------------------- .. index:: rbtree doc -Source documentation for the Red-Black Tree API can be found in the -generated Doxygen output for cpukit/sapi. - -.. COMMENT: COPYRIGHT (c) 1988-2012. - -.. COMMENT: On-Line Applications Research Corporation (OAR). - -.. COMMENT: All rights reserved. - +Source documentation for the Red-Black Tree API can be found in the generated +Doxygen output for ``cpukit/sapi``. |