1 | @c |
---|
2 | @c Copyright 2014 Gedare Bloom. |
---|
3 | @c All rights reserved. |
---|
4 | |
---|
5 | @chapter Red-Black Trees |
---|
6 | |
---|
7 | @cindex rbtrees |
---|
8 | |
---|
9 | @section Introduction |
---|
10 | |
---|
11 | The Red-Black Tree API is an interface to the SuperCore (score) rbtree |
---|
12 | implementation. Within RTEMS, red-black trees are used when a binary search |
---|
13 | tree is needed, including dynamic priority thread queues and non-contiguous |
---|
14 | heap memory. The Red-Black Tree API provided by RTEMS is: |
---|
15 | |
---|
16 | @itemize @bullet |
---|
17 | @c build_id |
---|
18 | @item @code{@value{DIRPREFIX}rtems_rbtree_node} - Red-Black Tree node embedded in another struct |
---|
19 | @item @code{@value{DIRPREFIX}rtems_rbtree_control} - Red-Black Tree control node for an entire tree |
---|
20 | @item @code{@value{DIRPREFIX}rtems_rbtree_initialize} - initialize the red-black tree with nodes |
---|
21 | @item @code{@value{DIRPREFIX}rtems_rbtree_initialize_empty} - initialize the red-black tree as empty |
---|
22 | @item @code{@value{DIRPREFIX}rtems_rbtree_set_off_tree} - Clear a node's links |
---|
23 | @item @code{@value{DIRPREFIX}rtems_rbtree_root} - Return the red-black tree's root node |
---|
24 | @item @code{@value{DIRPREFIX}rtems_rbtree_min} - Return the red-black tree's minimum node |
---|
25 | @item @code{@value{DIRPREFIX}rtems_rbtree_max} - Return the red-black tree's maximum node |
---|
26 | @item @code{@value{DIRPREFIX}rtems_rbtree_left} - Return a node's left child node |
---|
27 | @item @code{@value{DIRPREFIX}rtems_rbtree_right} - Return a node's right child node |
---|
28 | @item @code{@value{DIRPREFIX}rtems_rbtree_parent} - Return a node's parent node |
---|
29 | @item @code{@value{DIRPREFIX}rtems_rbtree_are_nodes_equal} - Are the node's equal ? |
---|
30 | @item @code{@value{DIRPREFIX}rtems_rbtree_is_empty} - Is the red-black tree empty ? |
---|
31 | @item @code{@value{DIRPREFIX}rtems_rbtree_is_min} - Is the Node the minimum in the red-black tree ? |
---|
32 | @item @code{@value{DIRPREFIX}rtems_rbtree_is_max} - Is the Node the maximum in the red-black tree ? |
---|
33 | @item @code{@value{DIRPREFIX}rtems_rbtree_is_root} - Is the Node the root of the red-black tree ? |
---|
34 | @item @code{@value{DIRPREFIX}rtems_rbtree_find} - Find the node with a matching key in the red-black tree |
---|
35 | @item @code{@value{DIRPREFIX}rtems_rbtree_predecessor} - Return the in-order predecessor of a node. |
---|
36 | @item @code{@value{DIRPREFIX}rtems_rbtree_successor} - Return the in-order successor of a node. |
---|
37 | @item @code{@value{DIRPREFIX}rtems_rbtree_extract} - Remove the node from the red-black tree |
---|
38 | @item @code{@value{DIRPREFIX}rtems_rbtree_get_min} - Remove the minimum node from the red-black tree |
---|
39 | @item @code{@value{DIRPREFIX}rtems_rbtree_get_max} - Remove the maximum node from the red-black tree |
---|
40 | @item @code{@value{DIRPREFIX}rtems_rbtree_peek_min} - Returns the minimum node from the red-black tree |
---|
41 | @item @code{@value{DIRPREFIX}rtems_rbtree_peek_max} - Returns the maximum node from the red-black tree |
---|
42 | @item @code{@value{DIRPREFIX}rtems_rbtree_insert} - Add the node to the red-black tree |
---|
43 | @end itemize |
---|
44 | |
---|
45 | @section Background |
---|
46 | |
---|
47 | The Red-Black Trees API is a thin layer above the SuperCore Red-Black Trees |
---|
48 | implementation. A Red-Black Tree is defined by a control node with pointers to |
---|
49 | the root, minimum, and maximum nodes in the tree. Each node in the tree |
---|
50 | consists of a parent pointer, two children pointers, and a color attribute. A |
---|
51 | tree is parameterized as either unique, meaning identical keys are rejected, or |
---|
52 | not, in which case duplicate keys are allowed. |
---|
53 | |
---|
54 | Users must provide a comparison functor that gets passed to functions that need |
---|
55 | to compare nodes. In addition, no internal synchronization is offered within |
---|
56 | the red-black tree implementation, thus users must ensure at most one thread |
---|
57 | accesses a red-black tree instance at a time. |
---|
58 | |
---|
59 | @subsection Nodes |
---|
60 | |
---|
61 | A red-black tree is made up from nodes that orginate from a red-black tree control |
---|
62 | object. A node is of type @code{@value{DIRPREFIX}rtems_rbtree_node}. The node |
---|
63 | is designed to be part of a user data structure. To obtain the encapsulating |
---|
64 | structure users can use the @code{RTEMS_CONTAINER_OF} macro. |
---|
65 | The node can be placed anywhere within the user's structure and the macro will |
---|
66 | calculate the structure's address from the node's address. |
---|
67 | |
---|
68 | @subsection Controls |
---|
69 | |
---|
70 | A red-black tree is rooted with a control object. Red-Black Tree control |
---|
71 | provide the user with access to the nodes on the red-black tree. The |
---|
72 | implementation does not require special checks for manipulating the root of the |
---|
73 | red-black tree. To accomplish this the |
---|
74 | @code{@value{DIRPREFIX}rtems_rbtree_control} structure is treated as a |
---|
75 | @code{@value{DIRPREFIX}rtems_rbtree_node} structure with a @code{NULL} parent |
---|
76 | and left child pointing to the root. |
---|
77 | |
---|
78 | @section Operations |
---|
79 | |
---|
80 | Examples for using the red-black trees |
---|
81 | can be found in the testsuites/sptests/sprbtree01/init.c file. |
---|
82 | |
---|
83 | @section Directives |
---|
84 | |
---|
85 | @subsection Documentation for the Red-Black Tree Directives |
---|
86 | |
---|
87 | @cindex rbtree doc |
---|
88 | |
---|
89 | Source documentation for the Red-Black Tree API can be found in the |
---|
90 | generated Doxygen output for cpukit/sapi. |
---|
91 | |
---|