1 | .. COMMENT: COPYRIGHT (c) 1988-2012. |
---|
2 | .. COMMENT: On-Line Applications Research Corporation (OAR). |
---|
3 | .. COMMENT: All rights reserved. |
---|
4 | |
---|
5 | Red-Black Trees |
---|
6 | ############### |
---|
7 | |
---|
8 | .. index:: rbtrees |
---|
9 | |
---|
10 | Introduction |
---|
11 | ============ |
---|
12 | |
---|
13 | The Red-Black Tree API is an interface to the SuperCore (score) rbtree |
---|
14 | implementation. Within RTEMS, red-black trees are used when a binary search |
---|
15 | tree is needed, including dynamic priority thread queues and non-contiguous |
---|
16 | heap memory. The Red-Black Tree API provided by RTEMS is: |
---|
17 | |
---|
18 | - ``rtems_rtems_rbtree_node`` - Red-Black Tree node embedded in another struct |
---|
19 | |
---|
20 | - ``rtems_rtems_rbtree_control`` - Red-Black Tree control node for an entire tree |
---|
21 | |
---|
22 | - ``rtems_rtems_rbtree_initialize`` - initialize the red-black tree with nodes |
---|
23 | |
---|
24 | - ``rtems_rtems_rbtree_initialize_empty`` - initialize the red-black tree as empty |
---|
25 | |
---|
26 | - ``rtems_rtems_rbtree_set_off_tree`` - Clear a node's links |
---|
27 | |
---|
28 | - ``rtems_rtems_rbtree_root`` - Return the red-black tree's root node |
---|
29 | |
---|
30 | - ``rtems_rtems_rbtree_min`` - Return the red-black tree's minimum node |
---|
31 | |
---|
32 | - ``rtems_rtems_rbtree_max`` - Return the red-black tree's maximum node |
---|
33 | |
---|
34 | - ``rtems_rtems_rbtree_left`` - Return a node's left child node |
---|
35 | |
---|
36 | - ``rtems_rtems_rbtree_right`` - Return a node's right child node |
---|
37 | |
---|
38 | - ``rtems_rtems_rbtree_parent`` - Return a node's parent node |
---|
39 | |
---|
40 | - ``rtems_rtems_rbtree_are_nodes_equal`` - Are the node's equal ? |
---|
41 | |
---|
42 | - ``rtems_rtems_rbtree_is_empty`` - Is the red-black tree empty ? |
---|
43 | |
---|
44 | - ``rtems_rtems_rbtree_is_min`` - Is the Node the minimum in the red-black tree ? |
---|
45 | |
---|
46 | - ``rtems_rtems_rbtree_is_max`` - Is the Node the maximum in the red-black tree ? |
---|
47 | |
---|
48 | - ``rtems_rtems_rbtree_is_root`` - Is the Node the root of the red-black tree ? |
---|
49 | |
---|
50 | - ``rtems_rtems_rbtree_find`` - Find the node with a matching key in the red-black tree |
---|
51 | |
---|
52 | - ``rtems_rtems_rbtree_predecessor`` - Return the in-order predecessor of a node. |
---|
53 | |
---|
54 | - ``rtems_rtems_rbtree_successor`` - Return the in-order successor of a node. |
---|
55 | |
---|
56 | - ``rtems_rtems_rbtree_extract`` - Remove the node from the red-black tree |
---|
57 | |
---|
58 | - ``rtems_rtems_rbtree_get_min`` - Remove the minimum node from the red-black tree |
---|
59 | |
---|
60 | - ``rtems_rtems_rbtree_get_max`` - Remove the maximum node from the red-black tree |
---|
61 | |
---|
62 | - ``rtems_rtems_rbtree_peek_min`` - Returns the minimum node from the red-black tree |
---|
63 | |
---|
64 | - ``rtems_rtems_rbtree_peek_max`` - Returns the maximum node from the red-black tree |
---|
65 | |
---|
66 | - ``rtems_rtems_rbtree_insert`` - Add the node to the red-black tree |
---|
67 | |
---|
68 | Background |
---|
69 | ========== |
---|
70 | |
---|
71 | The Red-Black Trees API is a thin layer above the SuperCore Red-Black Trees |
---|
72 | implementation. A Red-Black Tree is defined by a control node with pointers to |
---|
73 | the root, minimum, and maximum nodes in the tree. Each node in the tree |
---|
74 | consists of a parent pointer, two children pointers, and a color attribute. A |
---|
75 | tree is parameterized as either unique, meaning identical keys are rejected, or |
---|
76 | not, in which case duplicate keys are allowed. |
---|
77 | |
---|
78 | Users must provide a comparison functor that gets passed to functions that need |
---|
79 | to compare nodes. In addition, no internal synchronization is offered within |
---|
80 | the red-black tree implementation, thus users must ensure at most one thread |
---|
81 | accesses a red-black tree instance at a time. |
---|
82 | |
---|
83 | Nodes |
---|
84 | ----- |
---|
85 | |
---|
86 | A red-black tree is made up from nodes that orginate from a red-black tree |
---|
87 | control object. A node is of type ``rtems_rtems_rbtree_node``. The node is |
---|
88 | designed to be part of a user data structure. To obtain the encapsulating |
---|
89 | structure users can use the ``RTEMS_CONTAINER_OF`` macro. The node can be |
---|
90 | placed anywhere within the user's structure and the macro will calculate the |
---|
91 | structure's address from the node's address. |
---|
92 | |
---|
93 | Controls |
---|
94 | -------- |
---|
95 | |
---|
96 | A red-black tree is rooted with a control object. Red-Black Tree control |
---|
97 | provide the user with access to the nodes on the red-black tree. The |
---|
98 | implementation does not require special checks for manipulating the root of the |
---|
99 | red-black tree. To accomplish this the ``rtems_rtems_rbtree_control`` structure |
---|
100 | is treated as a ``rtems_rtems_rbtree_node`` structure with a ``NULL`` parent |
---|
101 | and left child pointing to the root. |
---|
102 | |
---|
103 | Operations |
---|
104 | ========== |
---|
105 | |
---|
106 | Examples for using the red-black trees can be found in the |
---|
107 | ``testsuites/sptests/sprbtree01/init.c`` file. |
---|
108 | |
---|
109 | Directives |
---|
110 | ========== |
---|
111 | |
---|
112 | Documentation for the Red-Black Tree Directives |
---|
113 | ----------------------------------------------- |
---|
114 | .. index:: rbtree doc |
---|
115 | |
---|
116 | Source documentation for the Red-Black Tree API can be found in the generated |
---|
117 | Doxygen output for ``cpukit/sapi``. |
---|