source: rtems/cpukit/score/include/rtems/score/rbtree.h @ c5430e06

5
Last change on this file since c5430e06 was c5430e06, checked in by Sebastian Huber <sebastian.huber@…>, on Jan 30, 2017 at 11:29:31 AM

score: Fix unused parameter warning

Close #2890.

  • Property mode set to 100644
File size: 14.4 KB
Line 
1/**
2 *  @file  rtems/score/rbtree.h
3 *
4 *  @brief Constants and Structures Associated with the Red-Black Tree Handler
5 *
6 *  This include file contains all the constants and structures associated
7 *  with the Red-Black Tree Handler.
8 */
9
10/*
11 *  Copyright (c) 2010 Gedare Bloom.
12 *
13 *  The license and distribution terms for this file may be
14 *  found in the file LICENSE in this distribution or at
15 *  http://www.rtems.org/license/LICENSE.
16 */
17
18#ifndef _RTEMS_SCORE_RBTREE_H
19#define _RTEMS_SCORE_RBTREE_H
20
21#include <sys/tree.h>
22#include <rtems/score/basedefs.h>
23#include <rtems/score/assert.h>
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/**
30 *  @defgroup ScoreRBTree Red-Black Tree Handler
31 *
32 *  @ingroup Score
33 *
34 *  The Red-Black Tree Handler is used to manage sets of entities.  This handler
35 *  provides two data structures.  The rbtree Node data structure is included
36 *  as the first part of every data structure that will be placed on
37 *  a RBTree.  The second data structure is rbtree Control which is used
38 *  to manage a set of rbtree Nodes.
39 */
40/**@{*/
41
42struct RBTree_Control;
43
44/**
45 * @brief Red-black tree node.
46 *
47 * This is used to manage each node (element) which is placed on a red-black
48 * tree.
49 */
50typedef struct RBTree_Node {
51  RB_ENTRY(RBTree_Node) Node;
52#if defined(RTEMS_DEBUG)
53  const struct RBTree_Control *tree;
54#endif
55} RBTree_Node;
56
57/**
58 * @brief Red-black tree control.
59 *
60 * This is used to manage a red-black tree.  A red-black tree consists of a
61 * tree of zero or more nodes.
62 */
63typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
64
65/**
66 * @brief Initializer for an empty red-black tree with designator @a name.
67 */
68#define RBTREE_INITIALIZER_EMPTY( name ) \
69  RB_INITIALIZER( name )
70
71/**
72 * @brief Definition for an empty red-black tree with designator @a name.
73 */
74#define RBTREE_DEFINE_EMPTY( name ) \
75  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
76
77/**
78 * @brief Sets a red-black tree node as off-tree.
79 *
80 * Do not use this function on nodes which are a part of a tree.
81 *
82 * @param[in] the_node The node to set off-tree.
83 *
84 * @see _RBTree_Is_node_off_tree().
85 */
86RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
87{
88  RB_COLOR( the_node, Node ) = -1;
89}
90
91/**
92 * @brief Returns true, if this red-black tree node is off-tree, and false
93 * otherwise.
94 *
95 * @param[in] the_node The node to test.
96 *
97 * @retval true The node is not a part of a tree (off-tree).
98 * @retval false Otherwise.
99 *
100 * @see _RBTree_Set_off_tree().
101 */
102RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
103  const RBTree_Node *the_node
104)
105{
106  return RB_COLOR( the_node, Node ) == -1;
107}
108
109/**
110 * @brief Rebalances the red-black tree after insertion of the node.
111 *
112 * @param[in] the_rbtree The red-black tree control.
113 * @param[in] the_node The most recently inserted node.
114 */
115void _RBTree_Insert_color(
116  RBTree_Control *the_rbtree,
117  RBTree_Node    *the_node
118);
119
120/**
121 * @brief Initializes a red-black tree node.
122 *
123 * In debug configurations, the node is set off tree.  In all other
124 * configurations, this function does nothing.
125 *
126 * @param[in] the_node The red-black tree node to initialize.
127 */
128RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node )
129{
130#if defined(RTEMS_DEBUG)
131  _RBTree_Set_off_tree( the_node );
132  the_node->tree = NULL;
133#else
134  (void) the_node;
135#endif
136}
137
138/**
139 * @brief Adds a child node to a parent node.
140 *
141 * @param[in] child The child node.
142 * @param[in] parent The parent node.
143 * @param[in] link The child node link of the parent node.
144 */
145RTEMS_INLINE_ROUTINE void _RBTree_Add_child(
146  RBTree_Node  *child,
147  RBTree_Node  *parent,
148  RBTree_Node **link
149)
150{
151  _Assert( _RBTree_Is_node_off_tree( child ) );
152  RB_SET( child, parent, Node );
153  *link = child;
154}
155
156/**
157 * @brief Inserts the node into the red-black tree using the specified parent
158 * node and link.
159 *
160 * @param[in] the_rbtree The red-black tree control.
161 * @param[in] the_node The node to insert.
162 * @param[in] parent The parent node.
163 * @param[in] link The child node link of the parent node.
164 *
165 * @code
166 * #include <rtems/score/rbtree.h>
167 *
168 * typedef struct {
169 *   int value;
170 *   RBTree_Node Node;
171 * } Some_Node;
172 *
173 * bool _Some_Less(
174 *   const RBTree_Node *a,
175 *   const RBTree_Node *b
176 * )
177 * {
178 *   const Some_Node *aa = RTEMS_CONTAINER_OF( a, Some_Node, Node );
179 *   const Some_Node *bb = RTEMS_CONTAINER_OF( b, Some_Node, Node );
180 *
181 *   return aa->value < bb->value;
182 * }
183 *
184 * void _Some_Insert(
185 *   RBTree_Control *the_rbtree,
186 *   Some_Node      *the_node
187 * )
188 * {
189 *   RBTree_Node **link = _RBTree_Root_reference( the_rbtree );
190 *   RBTree_Node  *parent = NULL;
191 *
192 *   while ( *link != NULL ) {
193 *     parent = *link;
194 *
195 *     if ( _Some_Less( &the_node->Node, parent ) ) {
196 *       link = _RBTree_Left_reference( parent );
197 *     } else {
198 *       link = _RBTree_Right_reference( parent );
199 *     }
200 *   }
201 *
202 *   _RBTree_Insert_with_parent( the_rbtree, &the_node->Node, parent, link );
203 * }
204 * @endcode
205 */
206RTEMS_INLINE_ROUTINE void _RBTree_Insert_with_parent(
207  RBTree_Control  *the_rbtree,
208  RBTree_Node     *the_node,
209  RBTree_Node     *parent,
210  RBTree_Node    **link
211)
212{
213  _RBTree_Add_child( the_node, parent, link );
214  _RBTree_Insert_color( the_rbtree, the_node );
215}
216
217/**
218 * @brief Extracts (removes) the node from the red-black tree.
219 *
220 * This function does not set the node off-tree.  In case this is desired, then
221 * call _RBTree_Set_off_tree() after the extraction.
222 *
223 * In case the node to extract is not a node of the tree, then this function
224 * yields unpredictable results.
225 *
226 * @param[in] the_rbtree The red-black tree control.
227 * @param[in] the_node The node to extract.
228 */
229void _RBTree_Extract(
230  RBTree_Control *the_rbtree,
231  RBTree_Node *the_node
232);
233
234/**
235 * @brief Returns a pointer to root node of the red-black tree.
236 *
237 * The root node may change after insert or extract operations.
238 *
239 * @param[in] the_rbtree The red-black tree control.
240 *
241 * @retval NULL The tree is empty.
242 * @retval root The root node.
243 *
244 * @see _RBTree_Is_root().
245 */
246RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
247  const RBTree_Control *the_rbtree
248)
249{
250  return RB_ROOT( the_rbtree );
251}
252
253/**
254 * @brief Returns a reference to the root pointer of the red-black tree.
255 */
256RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference(
257  RBTree_Control *the_rbtree
258)
259{
260  return &RB_ROOT( the_rbtree );
261}
262
263/**
264 * @brief Returns a constant reference to the root pointer of the red-black tree.
265 */
266RTEMS_INLINE_ROUTINE RBTree_Node * const *_RBTree_Root_const_reference(
267  const RBTree_Control *the_rbtree
268)
269{
270  return &RB_ROOT( the_rbtree );
271}
272
273/**
274 * @brief Returns a pointer to the parent of this node.
275 *
276 * The node must have a parent, thus it is invalid to use this function for the
277 * root node or a node that is not part of a tree.  To test for the root node
278 * compare with _RBTree_Root() or use _RBTree_Is_root().
279 *
280 * @param[in] the_node The node of interest.
281 *
282 * @retval parent The parent of this node.
283 * @retval undefined The node is the root node or not part of a tree.
284 */
285RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
286  const RBTree_Node *the_node
287)
288{
289  return RB_PARENT( the_node, Node );
290}
291
292/**
293 * @brief Return pointer to the left of this node.
294 *
295 * This function returns a pointer to the left node of this node.
296 *
297 * @param[in] the_node is the node to be operated upon.
298 *
299 * @return This method returns the left node on the rbtree.
300 */
301RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
302  const RBTree_Node *the_node
303)
304{
305  return RB_LEFT( the_node, Node );
306}
307
308/**
309 * @brief Returns a reference to the left child pointer of the red-black tree
310 * node.
311 */
312RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference(
313  RBTree_Node *the_node
314)
315{
316  return &RB_LEFT( the_node, Node );
317}
318
319/**
320 * @brief Return pointer to the right of this node.
321 *
322 * This function returns a pointer to the right node of this node.
323 *
324 * @param[in] the_node is the node to be operated upon.
325 *
326 * @return This method returns the right node on the rbtree.
327 */
328RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
329  const RBTree_Node *the_node
330)
331{
332  return RB_RIGHT( the_node, Node );
333}
334
335/**
336 * @brief Returns a reference to the right child pointer of the red-black tree
337 * node.
338 */
339RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference(
340  RBTree_Node *the_node
341)
342{
343  return &RB_RIGHT( the_node, Node );
344}
345
346/**
347 * @brief Is the RBTree empty.
348 *
349 * This function returns true if there are no nodes on @a the_rbtree and
350 * false otherwise.
351 *
352 * @param[in] the_rbtree is the rbtree to be operated upon.
353 *
354 * @retval true There are no nodes on @a the_rbtree.
355 * @retval false There are nodes on @a the_rbtree.
356 */
357RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
358  const RBTree_Control *the_rbtree
359)
360{
361  return RB_EMPTY( the_rbtree );
362}
363
364/**
365 * @brief Returns true if this node is the root node of a red-black tree, and
366 * false otherwise.
367 *
368 * The root node may change after insert or extract operations.  In case the
369 * node is not a node of a tree, then this function yields unpredictable
370 * results.
371 *
372 * @param[in] the_node The node of interest.
373 *
374 * @retval true The node is the root node.
375 * @retval false Otherwise.
376 *
377 * @see _RBTree_Root().
378 */
379RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
380  const RBTree_Node *the_node
381)
382{
383  return _RBTree_Parent( the_node ) == NULL;
384}
385
386/**
387 * @brief Initialize this RBTree as empty.
388 *
389 * This routine initializes @a the_rbtree to contain zero nodes.
390 */
391RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
392  RBTree_Control *the_rbtree
393)
394{
395  RB_INIT( the_rbtree );
396}
397
398/**
399 * @brief Initializes this red-black tree to contain exactly the specified
400 * node.
401 *
402 * @param[in] the_rbtree The red-black tree control.
403 * @param[in] the_node The one and only node.
404 */
405RTEMS_INLINE_ROUTINE void _RBTree_Initialize_one(
406  RBTree_Control *the_rbtree,
407  RBTree_Node    *the_node
408)
409{
410  _Assert( _RBTree_Is_node_off_tree( the_node ) );
411#if defined(RTEMS_DEBUG)
412  _Assert( the_node->tree == NULL );
413  the_node->tree = the_rbtree;
414#endif
415  RB_ROOT( the_rbtree ) = the_node;
416  RB_PARENT( the_node, Node ) = NULL;
417  RB_LEFT( the_node, Node ) = NULL;
418  RB_RIGHT( the_node, Node ) = NULL;
419  RB_COLOR( the_node, Node ) = RB_BLACK;
420}
421
422/**
423 * @brief Returns the minimum node of the red-black tree.
424 *
425 * @param[in] the_rbtree The red-black tree control.
426 *
427 * @retval NULL The red-black tree is empty.
428 * @retval node The minimum node.
429 */
430RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );
431
432/**
433 * @brief Returns the maximum node of the red-black tree.
434 *
435 * @param[in] the_rbtree The red-black tree control.
436 *
437 * @retval NULL The red-black tree is empty.
438 * @retval node The maximum node.
439 */
440RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );
441
442/**
443 * @brief Returns the predecessor of a node.
444 *
445 * @param[in] node is the node.
446 *
447 * @retval NULL The predecessor does not exist.  Otherwise it returns
448 *         the predecessor node.
449 */
450RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );
451
452/**
453 * @brief Returns the successor of a node.
454 *
455 * @param[in] node is the node.
456 *
457 * @retval NULL The successor does not exist.  Otherwise the successor node.
458 */
459RBTree_Node *_RBTree_Successor( const RBTree_Node *node );
460
461/**
462 * @brief Replaces a node in the red-black tree without a rebalance.
463 *
464 * @param[in] the_rbtree The red-black tree control.
465 * @param[in] victim The victim node.
466 * @param[in] replacement The replacement node.
467 */
468void _RBTree_Replace_node(
469  RBTree_Control *the_rbtree,
470  RBTree_Node    *victim,
471  RBTree_Node    *replacement
472);
473
474/**
475 * @brief Inserts the node into the red-black tree.
476 *
477 * @param the_rbtree The red-black tree control.
478 * @param the_node The node to insert.
479 * @param key The key of the node to insert.  This key must be equal to the key
480 *   stored in the node to insert.  The separate key parameter is provided for
481 *   two reasons.  Firstly, it allows to share the less operator with
482 *   _RBTree_Find_inline().  Secondly, the compiler may generate better code if
483 *   the key is stored in a local variable.
484 * @param less Must return true if the specified key is less than the key of
485 *   the node, otherwise false.
486 *
487 * @retval true The inserted node is the new minimum node according to the
488 *   specified less order function.
489 * @retval false Otherwise.
490 */
491RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline(
492  RBTree_Control *the_rbtree,
493  RBTree_Node    *the_node,
494  const void     *key,
495  bool         ( *less )( const void *, const RBTree_Node * )
496)
497{
498  RBTree_Node **link;
499  RBTree_Node  *parent;
500  bool          is_new_minimum;
501
502  link = _RBTree_Root_reference( the_rbtree );
503  parent = NULL;
504  is_new_minimum = true;
505
506  while ( *link != NULL ) {
507    parent = *link;
508
509    if ( ( *less )( key, parent ) ) {
510      link = _RBTree_Left_reference( parent );
511    } else {
512      link = _RBTree_Right_reference( parent );
513      is_new_minimum = false;
514    }
515  }
516
517  _RBTree_Add_child( the_node, parent, link );
518  _RBTree_Insert_color( the_rbtree, the_node );
519  return is_new_minimum;
520}
521
522/**
523 * @brief Finds an object in the red-black tree with the specified key.
524 *
525 * @param the_rbtree The red-black tree control.
526 * @param key The key to look after.
527 * @param equal Must return true if the specified key equals the key of the
528 *   node, otherwise false.
529 * @param less Must return true if the specified key is less than the key of
530 *   the node, otherwise false.
531 * @param map In case a node with the specified key is found, then this
532 *   function is called to map the node to the object returned.  Usually it
533 *   performs some offset operation via RTEMS_CONTAINER_OF() to map the node to
534 *   its containing object.  Thus, the return type is a void pointer and not a
535 *   red-black tree node.
536 *
537 * @retval object An object with the specified key.
538 * @retval NULL No object with the specified key exists in the red-black tree.
539 */
540RTEMS_INLINE_ROUTINE void *_RBTree_Find_inline(
541  const RBTree_Control *the_rbtree,
542  const void           *key,
543  bool               ( *equal )( const void *, const RBTree_Node * ),
544  bool               ( *less )( const void *, const RBTree_Node * ),
545  void              *( *map )( RBTree_Node * )
546)
547{
548  RBTree_Node * const *link;
549  RBTree_Node         *parent;
550
551  link = _RBTree_Root_const_reference( the_rbtree );
552  parent = NULL;
553
554  while ( *link != NULL ) {
555    parent = *link;
556
557    if ( ( *equal )( key, parent ) ) {
558      return ( *map )( parent );
559    } else if ( ( *less )( key, parent ) ) {
560      link = _RBTree_Left_reference( parent );
561    } else {
562      link = _RBTree_Right_reference( parent );
563    }
564  }
565
566  return NULL;
567}
568
569/**@}*/
570
571#ifdef __cplusplus
572}
573#endif
574
575#endif
576/* end of include file */
Note: See TracBrowser for help on using the repository browser.