source: rtems/cpukit/sapi/include/rtems/rbtree.h @ 993f5ac

4.115
Last change on this file since 993f5ac was 993f5ac, checked in by Sebastian Huber <sebastian.huber@…>, on 07/23/14 at 11:03:54

rbtree: Simplify insert and extract

Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more
superfluous NULL pointer checks. Change _RBTree_Is_root() to use only
the node. Add parent parameter to _RBTree_Sibling(). Delete
_RBTree_Grandparent() and _RBTree_Parent_sibling().

  • Property mode set to 100644
File size: 8.7 KB
Line 
1/**
2 * @file
3 *
4 * @brief Constants and Structures Associated with the RBTree API in RTEMS
5 *
6 * This include file contains all the constants and structures associated
7 * with the RBTree API in RTEMS. The rbtree is a Red Black Tree that
8 * is part of the Super Core. This is the published interface to that
9 * code.
10 */
11
12/*
13 *  Copyright (c) 2010 Gedare Bloom.
14 *
15 *  The license and distribution terms for this file may be
16 *  found in the file LICENSE in this distribution or at
17 *  http://www.rtems.org/license/LICENSE.
18 */
19
20#ifndef _RTEMS_RBTREE_H
21#define _RTEMS_RBTREE_H
22
23#include <rtems/score/rbtree.h>
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/**
30 * @defgroup ClassicRBTrees Red-Black Trees
31 *
32 * @ingroup ClassicRTEMS
33 *
34 * @brief A Red-Black Tree container.
35 *
36 * The red-black tree container offers no internal protection against
37 * concurrent access.  The user must ensure that at most one thread at once can
38 * access a red-black tree instance.
39 *
40 * @{
41 */
42
43/**
44 * @typedef rtems_rbtree_node
45 *
46 * A node that can be manipulated in the rbtree.
47 */
48typedef RBTree_Node rtems_rbtree_node;
49
50/**
51 * @typedef rtems_rbtree_control
52 *
53 * The rbtree's control anchors the rbtree.
54 */
55typedef RBTree_Control rtems_rbtree_control;
56
57/**
58 * @copydoc RBTree_Compare_result
59 */
60typedef RBTree_Compare_result rtems_rbtree_compare_result;
61
62/**
63 * @copydoc RBTree_Compare
64 */
65typedef RBTree_Compare rtems_rbtree_compare;
66
67/**
68 * @brief RBTree initializer for an empty rbtree with designator @a name.
69 */
70#define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
71  RBTREE_INITIALIZER_EMPTY(name)
72
73/**
74 * @brief RBTree definition for an empty rbtree with designator @a name.
75 */
76#define RTEMS_RBTREE_DEFINE_EMPTY(name) \
77  RBTREE_DEFINE_EMPTY(name)
78
79/**
80 * @brief Initialize a RBTree header.
81 *
82 * This routine initializes @a the_rbtree structure to manage the
83 * contiguous array of @a number_nodes nodes which starts at
84 * @a starting_address.  Each node is of @a node_size bytes.
85 */
86RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
87  rtems_rbtree_control *the_rbtree,
88  rtems_rbtree_compare  compare,
89  void                 *starting_address,
90  size_t                number_nodes,
91  size_t                node_size,
92  bool                  is_unique
93)
94{
95  _RBTree_Initialize( the_rbtree, compare, starting_address,
96    number_nodes, node_size, is_unique);
97}
98
99/**
100 * @brief Initialize this RBTree as Empty
101 *
102 * This routine initializes @a the_rbtree to contain zero nodes.
103 */
104RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
105  rtems_rbtree_control *the_rbtree
106)
107{
108  _RBTree_Initialize_empty( the_rbtree );
109}
110
111/**
112 * @brief Set off RBtree.
113 *
114 * This function sets the next and previous fields of the @a node to NULL
115 * indicating the @a node is not part of any rbtree.
116 */
117RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_tree(
118  rtems_rbtree_node *node
119)
120{
121  _RBTree_Set_off_tree( node );
122}
123
124/**
125 * @brief Is the Node off RBTree.
126 *
127 * This function returns true if the @a node is not on a rbtree. A @a node is
128 * off rbtree if the next and previous fields are set to NULL.
129 */
130RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_tree(
131  const rtems_rbtree_node *node
132)
133{
134  return _RBTree_Is_node_off_tree( node );
135}
136
137/**
138 * @brief Return pointer to RBTree root.
139 *
140 * This function returns a pointer to the root node of @a the_rbtree.
141 */
142RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root(
143  const rtems_rbtree_control *the_rbtree
144)
145{
146  return _RBTree_Root( the_rbtree );
147}
148
149/**
150 * @brief Return pointer to RBTree Minimum
151 *
152 * This function returns a pointer to the minimum node of @a the_rbtree.
153 */
154RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min(
155  const rtems_rbtree_control *the_rbtree
156)
157{
158  return _RBTree_First( the_rbtree, RBT_LEFT );
159}
160
161/**
162 * @brief Return pointer to RBTree maximum.
163 *
164 * This function returns a pointer to the maximum node of @a the_rbtree.
165 */
166RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max(
167  const rtems_rbtree_control *the_rbtree
168)
169{
170  return _RBTree_First( the_rbtree, RBT_RIGHT );
171}
172
173/**
174 * @brief Return pointer to the left child node from this node.
175 *
176 * This function returns a pointer to the left child node of @a the_node.
177 */
178RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left(
179  const rtems_rbtree_node *the_node
180)
181{
182  return _RBTree_Left( the_node );
183}
184
185/**
186 * @brief Return pointer to the right child node from this node.
187 *
188 * This function returns a pointer to the right child node of @a the_node.
189 */
190RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
191  const rtems_rbtree_node *the_node
192)
193{
194  return _RBTree_Right( the_node );
195}
196
197/**
198 * @copydoc _RBTree_Parent()
199 */
200RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
201  const rtems_rbtree_node *the_node
202)
203{
204  return _RBTree_Parent( the_node );
205}
206
207/**
208 * @brief Is the RBTree empty.
209 *
210 * This function returns true if there a no nodes on @a the_rbtree and
211 * false otherwise.
212 */
213RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(
214  const rtems_rbtree_control *the_rbtree
215)
216{
217  return _RBTree_Is_empty( the_rbtree );
218}
219
220/**
221 * @brief Is this the minimum node on the RBTree.
222 *
223 * This function returns true if @a the_node is the min node on @a the_rbtree
224 * and false otherwise.
225 */
226RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(
227  const rtems_rbtree_control *the_rbtree,
228  const rtems_rbtree_node *the_node
229)
230{
231  return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT );
232}
233
234/**
235 * @brief Is this the maximum node on the RBTree.
236 *
237 * This function returns true if @a the_node is the max node on @a the_rbtree
238 * and false otherwise.
239 */
240RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
241  const rtems_rbtree_control *the_rbtree,
242  const rtems_rbtree_node *the_node
243)
244{
245  return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT );
246}
247
248/**
249 * @copydoc _RBTree_Is_root()
250 */
251RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
252  const rtems_rbtree_node *the_node
253)
254{
255  return _RBTree_Is_root( the_node );
256}
257
258/**
259 * @copydoc _RBTree_Find()
260 */
261RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
262  const rtems_rbtree_control *the_rbtree,
263  const rtems_rbtree_node    *the_node,
264  rtems_rbtree_compare        compare,
265  bool                        is_unique
266)
267{
268  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
269}
270
271/**
272 * @copydoc _RBTree_Predecessor()
273 */
274RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
275  const rtems_rbtree_node *node
276)
277{
278  return _RBTree_Predecessor( node );
279}
280
281/**
282 * @copydoc _RBTree_Successor()
283 */
284RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
285  const rtems_rbtree_node *node
286)
287{
288  return _RBTree_Successor( node );
289}
290
291/**
292 * @copydoc _RBTree_Extract()
293 */
294RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
295  rtems_rbtree_control *the_rbtree,
296  rtems_rbtree_node *the_node
297)
298{
299  _RBTree_Extract( the_rbtree, the_node );
300}
301
302/**
303 * @brief Obtain the min node on a rbtree.
304 *
305 * This function removes the min node from @a the_rbtree and returns
306 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
307 */
308
309RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
310  rtems_rbtree_control *the_rbtree
311)
312{
313  return _RBTree_Get( the_rbtree, RBT_LEFT );
314}
315
316/**
317 * @brief Obtain the max node on a rbtree.
318 *
319 * This function removes the max node from @a the_rbtree and returns
320 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
321 */
322
323RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
324  rtems_rbtree_control *the_rbtree
325)
326{
327  return _RBTree_Get( the_rbtree, RBT_RIGHT );
328}
329
330/**
331 * @brief Peek at the min node on a rbtree.
332 *
333 * This function returns a pointer to the min node from @a the_rbtree
334 * without changing the tree.  If @a the_rbtree is empty,
335 * then NULL is returned.
336 */
337RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
338  const rtems_rbtree_control *the_rbtree
339)
340{
341  return _RBTree_First( the_rbtree, RBT_LEFT );
342}
343
344/**
345 * @brief Peek at the max node on a rbtree.
346 *
347 * This function returns a pointer to the max node from @a the_rbtree
348 * without changing the tree.  If @a the_rbtree is empty,
349 * then NULL is returned.
350 */
351RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
352  const rtems_rbtree_control *the_rbtree
353)
354{
355  return _RBTree_First( the_rbtree, RBT_RIGHT );
356}
357
358/**
359 * @copydoc _RBTree_Find_control()
360 */
361RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_control(
362  const rtems_rbtree_node *the_node
363)
364{
365  return _RBTree_Find_control( the_node );
366}
367
368/**
369 * @copydoc _RBTree_Insert()
370 */
371RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
372  rtems_rbtree_control *the_rbtree,
373  rtems_rbtree_node    *the_node,
374  rtems_rbtree_compare  compare,
375  bool                  is_unique
376)
377{
378  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
379}
380
381/** @} */
382
383#ifdef __cplusplus
384}
385#endif
386
387#endif
388/* end of include file */
Note: See TracBrowser for help on using the repository browser.