RTEMS  5.0.0
rbtree.h
Go to the documentation of this file.
1 
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
26 extern "C" {
27 #endif
28 
49 
55 typedef RBTree_Control rtems_rbtree_control;
56 
65 
80  const RBTree_Node *first,
81  const RBTree_Node *second
82 );
83 
87 #define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
88  RBTREE_INITIALIZER_EMPTY(name)
89 
93 #define RTEMS_RBTREE_DEFINE_EMPTY(name) \
94  RBTREE_DEFINE_EMPTY(name)
95 
112  rtems_rbtree_control *the_rbtree,
113  rtems_rbtree_compare compare,
114  void *starting_address,
115  size_t number_nodes,
116  size_t node_size,
117  bool is_unique
118 );
119 
126  rtems_rbtree_control *the_rbtree
127 )
128 {
129  _RBTree_Initialize_empty( the_rbtree );
130 }
131 
139  rtems_rbtree_node *node
140 )
141 {
142  _RBTree_Set_off_tree( node );
143 }
144 
152  const rtems_rbtree_node *node
153 )
154 {
155  return _RBTree_Is_node_off_tree( node );
156 }
157 
164  const rtems_rbtree_control *the_rbtree
165 )
166 {
167  return _RBTree_Root( the_rbtree );
168 }
169 
174  const rtems_rbtree_control *the_rbtree
175 )
176 {
177  return _RBTree_Minimum( the_rbtree );
178 }
179 
184  const rtems_rbtree_control *the_rbtree
185 )
186 {
187  return _RBTree_Maximum( the_rbtree );
188 }
189 
196  const rtems_rbtree_node *the_node
197 )
198 {
199  return _RBTree_Left( the_node );
200 }
201 
208  const rtems_rbtree_node *the_node
209 )
210 {
211  return _RBTree_Right( the_node );
212 }
213 
218  const rtems_rbtree_node *the_node
219 )
220 {
221  return _RBTree_Parent( the_node );
222 }
223 
231  const rtems_rbtree_control *the_rbtree
232 )
233 {
234  return _RBTree_Is_empty( the_rbtree );
235 }
236 
244  const rtems_rbtree_control *the_rbtree,
245  const rtems_rbtree_node *the_node
246 )
247 {
248  return rtems_rbtree_min( the_rbtree ) == the_node;
249 }
250 
258  const rtems_rbtree_control *the_rbtree,
259  const rtems_rbtree_node *the_node
260 )
261 {
262  return rtems_rbtree_max( the_rbtree ) == the_node;
263 }
264 
269  const rtems_rbtree_node *the_node
270 )
271 {
272  return _RBTree_Is_root( the_node );
273 }
274 
275 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_equal(
276  rtems_rbtree_compare_result compare_result
277 )
278 {
279  return compare_result == 0;
280 }
281 
282 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_greater(
283  rtems_rbtree_compare_result compare_result
284 )
285 {
286  return compare_result > 0;
287 }
288 
289 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_lesser(
290  rtems_rbtree_compare_result compare_result
291 )
292 {
293  return compare_result < 0;
294 }
295 
310 rtems_rbtree_node* rtems_rbtree_find(
311  const rtems_rbtree_control *the_rbtree,
312  const rtems_rbtree_node *the_node,
313  rtems_rbtree_compare compare,
314  bool is_unique
315 );
316 
321  const rtems_rbtree_node *node
322 )
323 {
324  return _RBTree_Predecessor( node );
325 }
326 
331  const rtems_rbtree_node *node
332 )
333 {
334  return _RBTree_Successor( node );
335 }
336 
341  rtems_rbtree_control *the_rbtree,
342  rtems_rbtree_node *the_node
343 )
344 {
345  _RBTree_Extract( the_rbtree, the_node );
346 }
347 
361  rtems_rbtree_control *the_rbtree
362 )
363 {
364  rtems_rbtree_node *the_node = rtems_rbtree_min( the_rbtree );
365 
366  if ( the_node != NULL ) {
367  rtems_rbtree_extract( the_rbtree, the_node );
368  }
369 
370  return the_node;
371 }
372 
386  rtems_rbtree_control *the_rbtree
387 )
388 {
389  rtems_rbtree_node *the_node = rtems_rbtree_max( the_rbtree );
390 
391  if ( the_node != NULL ) {
392  rtems_rbtree_extract( the_rbtree, the_node );
393  }
394 
395  return the_node;
396 }
397 
406  const rtems_rbtree_control *the_rbtree
407 )
408 {
409  return rtems_rbtree_min( the_rbtree );
410 }
411 
420  const rtems_rbtree_control *the_rbtree
421 )
422 {
423  return rtems_rbtree_max( the_rbtree );
424 }
425 
442 rtems_rbtree_node *rtems_rbtree_insert(
443  RBTree_Control *the_rbtree,
444  RBTree_Node *the_node,
445  rtems_rbtree_compare compare,
446  bool is_unique
447 );
448 
451 #ifdef __cplusplus
452 }
453 #endif
454 
455 #endif
456 /* end of include file */
RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(const RBTree_Control *the_rbtree)
Is the RBTree empty.
Definition: rbtree.h:353
RBTree_Node rtems_rbtree_node
Definition: rbtree.h:48
RBTree_Node * _RBTree_Maximum(const RBTree_Control *the_rbtree)
Returns the maximum node of the red-black tree.
Definition: rbtreenext.c:41
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_tree(const rtems_rbtree_node *node)
Is the Node off RBTree.
Definition: rbtree.h:151
#define RTEMS_INLINE_ROUTINE
Definition: basedefs.h:65
rtems_rbtree_compare_result(* rtems_rbtree_compare)(const RBTree_Node *first, const RBTree_Node *second)
Compares two red-black tree nodes.
Definition: rbtree.h:79
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Root(const RBTree_Control *the_rbtree)
Returns a pointer to root node of the red-black tree.
Definition: rbtree.h:242
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_predecessor(const rtems_rbtree_node *node)
Returns the predecessor of a node.
Definition: rbtree.h:320
RBTree_Node * _RBTree_Successor(const RBTree_Node *node)
Returns the successor of a node.
Definition: rbtreenext.c:46
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_parent(const rtems_rbtree_node *the_node)
Returns a pointer to the parent of this node.
Definition: rbtree.h:217
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_get_min(rtems_rbtree_control *the_rbtree)
Gets a node with the minimum key value from the red-black tree.
Definition: rbtree.h:360
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(rtems_rbtree_control *the_rbtree)
Initialize this RBTree as Empty.
Definition: rbtree.h:125
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_successor(const rtems_rbtree_node *node)
Returns the successor of a node.
Definition: rbtree.h:330
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_root(const rtems_rbtree_control *the_rbtree)
Return pointer to RBTree root.
Definition: rbtree.h:163
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_min(const rtems_rbtree_control *the_rbtree)
Returns the minimum node of the red-black tree.
Definition: rbtree.h:173
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_get_max(rtems_rbtree_control *the_rbtree)
Gets a node with the maximal key value from the red-black tree.
Definition: rbtree.h:385
Red-black tree node.
Definition: rbtree.h:50
RBTree_Control rtems_rbtree_control
Definition: rbtree.h:55
RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_tree(rtems_rbtree_node *node)
Set off RBtree.
Definition: rbtree.h:138
rtems_rbtree_node * rtems_rbtree_insert(RBTree_Control *the_rbtree, RBTree_Node *the_node, rtems_rbtree_compare compare, bool is_unique)
Inserts the node into the red-black tree.
Definition: sapirbtreeinsert.c:26
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_peek_min(const rtems_rbtree_control *the_rbtree)
Peek at the min node on a rbtree.
Definition: rbtree.h:405
RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(rtems_rbtree_control *the_rbtree, rtems_rbtree_node *the_node)
Extracts (removes) the node from the red-black tree.
Definition: rbtree.h:340
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Right(const RBTree_Node *the_node)
Return pointer to the right of this node.
Definition: rbtree.h:324
void rtems_rbtree_initialize(rtems_rbtree_control *the_rbtree, rtems_rbtree_compare compare, void *starting_address, size_t number_nodes, size_t node_size, bool is_unique)
Initialize a RBTree header.
Definition: rbtree.c:23
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(const rtems_rbtree_control *the_rbtree)
Is the RBTree empty.
Definition: rbtree.h:230
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(const rtems_rbtree_node *the_node)
Returns true if this node is the root node of a red-black tree, and false otherwise.
Definition: rbtree.h:268
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Parent(const RBTree_Node *the_node)
Returns a pointer to the parent of this node.
Definition: rbtree.h:281
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node)
Is this the maximum node on the RBTree.
Definition: rbtree.h:257
Constants and Structures Associated with the Red-Black Tree Handler.
RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(const RBTree_Node *the_node)
Returns true, if this red-black tree node is off-tree, and false otherwise.
Definition: rbtree.h:99
RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree(RBTree_Node *the_node)
Sets a red-black tree node as off-tree.
Definition: rbtree.h:83
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_peek_max(const rtems_rbtree_control *the_rbtree)
Peek at the max node on a rbtree.
Definition: rbtree.h:419
rtems_rbtree_node * rtems_rbtree_find(const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node, rtems_rbtree_compare compare, bool is_unique)
Tries to find a node for the specified key in the tree.
Definition: rbtreefind.c:22
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_left(const rtems_rbtree_node *the_node)
Return pointer to the left child node from this node.
Definition: rbtree.h:195
long rtems_rbtree_compare_result
Integer type for compare results.
Definition: rbtree.h:64
RBTree_Node * _RBTree_Minimum(const RBTree_Control *the_rbtree)
Returns the minimum node of the red-black tree.
Definition: rbtreenext.c:36
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node)
Is this the minimum node on the RBTree.
Definition: rbtree.h:243
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Left(const RBTree_Node *the_node)
Return pointer to the left of this node.
Definition: rbtree.h:297
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_right(const rtems_rbtree_node *the_node)
Return pointer to the right child node from this node.
Definition: rbtree.h:207
void _RBTree_Extract(RBTree_Control *the_rbtree, RBTree_Node *the_node)
Extracts (removes) the node from the red-black tree.
Definition: rbtreeextract.c:35
RBTree_Node * _RBTree_Predecessor(const RBTree_Node *node)
Returns the predecessor of a node.
Definition: rbtreenext.c:51
RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(const RBTree_Node *the_node)
Returns true if this node is the root node of a red-black tree, and false otherwise.
Definition: rbtree.h:375
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(RBTree_Control *the_rbtree)
Initialize this RBTree as empty.
Definition: rbtree.h:387
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_max(const rtems_rbtree_control *the_rbtree)
Returns the maximum node of the red-black tree.
Definition: rbtree.h:183
#define NULL
Requests a GPIO pin group configuration.
Definition: bestcomm_api.h:77