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

5
Last change on this file since da15db78 was da15db78, checked in by Sebastian Huber <sebastian.huber@…>, on Aug 24, 2016 at 1:25:33 PM

score: Improve red-black tree debug support

Ensure that we extract a node only from the right tree.

  • 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#endif
134}
135
136/**
137 * @brief Adds a child node to a parent node.
138 *
139 * @param[in] child The child node.
140 * @param[in] parent The parent node.
141 * @param[in] link The child node link of the parent node.
142 */
143RTEMS_INLINE_ROUTINE void _RBTree_Add_child(
144  RBTree_Node  *child,
145  RBTree_Node  *parent,
146  RBTree_Node **link
147)
148{
149  _Assert( _RBTree_Is_node_off_tree( child ) );
150  RB_SET( child, parent, Node );
151  *link = child;
152}
153
154/**
155 * @brief Inserts the node into the red-black tree using the specified parent
156 * node and link.
157 *
158 * @param[in] the_rbtree The red-black tree control.
159 * @param[in] the_node The node to insert.
160 * @param[in] parent The parent node.
161 * @param[in] link The child node link of the parent node.
162 *
163 * @code
164 * #include <rtems/score/rbtree.h>
165 *
166 * typedef struct {
167 *   int value;
168 *   RBTree_Node Node;
169 * } Some_Node;
170 *
171 * bool _Some_Less(
172 *   const RBTree_Node *a,
173 *   const RBTree_Node *b
174 * )
175 * {
176 *   const Some_Node *aa = RTEMS_CONTAINER_OF( a, Some_Node, Node );
177 *   const Some_Node *bb = RTEMS_CONTAINER_OF( b, Some_Node, Node );
178 *
179 *   return aa->value < bb->value;
180 * }
181 *
182 * void _Some_Insert(
183 *   RBTree_Control *the_rbtree,
184 *   Some_Node      *the_node
185 * )
186 * {
187 *   RBTree_Node **link = _RBTree_Root_reference( the_rbtree );
188 *   RBTree_Node  *parent = NULL;
189 *
190 *   while ( *link != NULL ) {
191 *     parent = *link;
192 *
193 *     if ( _Some_Less( &the_node->Node, parent ) ) {
194 *       link = _RBTree_Left_reference( parent );
195 *     } else {
196 *       link = _RBTree_Right_reference( parent );
197 *     }
198 *   }
199 *
200 *   _RBTree_Insert_with_parent( the_rbtree, &the_node->Node, parent, link );
201 * }
202 * @endcode
203 */
204RTEMS_INLINE_ROUTINE void _RBTree_Insert_with_parent(
205  RBTree_Control  *the_rbtree,
206  RBTree_Node     *the_node,
207  RBTree_Node     *parent,
208  RBTree_Node    **link
209)
210{
211  _RBTree_Add_child( the_node, parent, link );
212  _RBTree_Insert_color( the_rbtree, the_node );
213}
214
215/**
216 * @brief Extracts (removes) the node from the red-black tree.
217 *
218 * This function does not set the node off-tree.  In case this is desired, then
219 * call _RBTree_Set_off_tree() after the extraction.
220 *
221 * In case the node to extract is not a node of the tree, then this function
222 * yields unpredictable results.
223 *
224 * @param[in] the_rbtree The red-black tree control.
225 * @param[in] the_node The node to extract.
226 */
227void _RBTree_Extract(
228  RBTree_Control *the_rbtree,
229  RBTree_Node *the_node
230);
231
232/**
233 * @brief Returns a pointer to root node of the red-black tree.
234 *
235 * The root node may change after insert or extract operations.
236 *
237 * @param[in] the_rbtree The red-black tree control.
238 *
239 * @retval NULL The tree is empty.
240 * @retval root The root node.
241 *
242 * @see _RBTree_Is_root().
243 */
244RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
245  const RBTree_Control *the_rbtree
246)
247{
248  return RB_ROOT( the_rbtree );
249}
250
251/**
252 * @brief Returns a reference to the root pointer of the red-black tree.
253 */
254RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference(
255  RBTree_Control *the_rbtree
256)
257{
258  return &RB_ROOT( the_rbtree );
259}
260
261/**
262 * @brief Returns a constant reference to the root pointer of the red-black tree.
263 */
264RTEMS_INLINE_ROUTINE RBTree_Node * const *_RBTree_Root_const_reference(
265  const RBTree_Control *the_rbtree
266)
267{
268  return &RB_ROOT( the_rbtree );
269}
270
271/**
272 * @brief Returns a pointer to the parent of this node.
273 *
274 * The node must have a parent, thus it is invalid to use this function for the
275 * root node or a node that is not part of a tree.  To test for the root node
276 * compare with _RBTree_Root() or use _RBTree_Is_root().
277 *
278 * @param[in] the_node The node of interest.
279 *
280 * @retval parent The parent of this node.
281 * @retval undefined The node is the root node or not part of a tree.
282 */
283RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
284  const RBTree_Node *the_node
285)
286{
287  return RB_PARENT( the_node, Node );
288}
289
290/**
291 * @brief Return pointer to the left of this node.
292 *
293 * This function returns a pointer to the left node of this node.
294 *
295 * @param[in] the_node is the node to be operated upon.
296 *
297 * @return This method returns the left node on the rbtree.
298 */
299RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
300  const RBTree_Node *the_node
301)
302{
303  return RB_LEFT( the_node, Node );
304}
305
306/**
307 * @brief Returns a reference to the left child pointer of the red-black tree
308 * node.
309 */
310RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference(
311  RBTree_Node *the_node
312)
313{
314  return &RB_LEFT( the_node, Node );
315}
316
317/**
318 * @brief Return pointer to the right of this node.
319 *
320 * This function returns a pointer to the right node of this node.
321 *
322 * @param[in] the_node is the node to be operated upon.
323 *
324 * @return This method returns the right node on the rbtree.
325 */
326RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
327  const RBTree_Node *the_node
328)
329{
330  return RB_RIGHT( the_node, Node );
331}
332
333/**
334 * @brief Returns a reference to the right child pointer of the red-black tree
335 * node.
336 */
337RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference(
338  RBTree_Node *the_node
339)
340{
341  return &RB_RIGHT( the_node, Node );
342}
343
344/**
345 * @brief Is the RBTree empty.
346 *
347 * This function returns true if there are no nodes on @a the_rbtree and
348 * false otherwise.
349 *
350 * @param[in] the_rbtree is the rbtree to be operated upon.
351 *
352 * @retval true There are no nodes on @a the_rbtree.
353 * @retval false There are nodes on @a the_rbtree.
354 */
355RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
356  const RBTree_Control *the_rbtree
357)
358{
359  return RB_EMPTY( the_rbtree );
360}
361
362/**
363 * @brief Returns true if this node is the root node of a red-black tree, and
364 * false otherwise.
365 *
366 * The root node may change after insert or extract operations.  In case the
367 * node is not a node of a tree, then this function yields unpredictable
368 * results.
369 *
370 * @param[in] the_node The node of interest.
371 *
372 * @retval true The node is the root node.
373 * @retval false Otherwise.
374 *
375 * @see _RBTree_Root().
376 */
377RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
378  const RBTree_Node *the_node
379)
380{
381  return _RBTree_Parent( the_node ) == NULL;
382}
383
384/**
385 * @brief Initialize this RBTree as empty.
386 *
387 * This routine initializes @a the_rbtree to contain zero nodes.
388 */
389RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
390  RBTree_Control *the_rbtree
391)
392{
393  RB_INIT( the_rbtree );
394}
395
396/**
397 * @brief Initializes this red-black tree to contain exactly the specified
398 * node.
399 *
400 * @param[in] the_rbtree The red-black tree control.
401 * @param[in] the_node The one and only node.
402 */
403RTEMS_INLINE_ROUTINE void _RBTree_Initialize_one(
404  RBTree_Control *the_rbtree,
405  RBTree_Node    *the_node
406)
407{
408  _Assert( _RBTree_Is_node_off_tree( the_node ) );
409#if defined(RTEMS_DEBUG)
410  _Assert( the_node->tree == NULL );
411  the_node->tree = the_rbtree;
412#endif
413  RB_ROOT( the_rbtree ) = the_node;
414  RB_PARENT( the_node, Node ) = NULL;
415  RB_LEFT( the_node, Node ) = NULL;
416  RB_RIGHT( the_node, Node ) = NULL;
417  RB_COLOR( the_node, Node ) = RB_BLACK;
418}
419
420/**
421 * @brief Returns the minimum node of the red-black tree.
422 *
423 * @param[in] the_rbtree The red-black tree control.
424 *
425 * @retval NULL The red-black tree is empty.
426 * @retval node The minimum node.
427 */
428RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );
429
430/**
431 * @brief Returns the maximum node of the red-black tree.
432 *
433 * @param[in] the_rbtree The red-black tree control.
434 *
435 * @retval NULL The red-black tree is empty.
436 * @retval node The maximum node.
437 */
438RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );
439
440/**
441 * @brief Returns the predecessor of a node.
442 *
443 * @param[in] node is the node.
444 *
445 * @retval NULL The predecessor does not exist.  Otherwise it returns
446 *         the predecessor node.
447 */
448RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );
449
450/**
451 * @brief Returns the successor of a node.
452 *
453 * @param[in] node is the node.
454 *
455 * @retval NULL The successor does not exist.  Otherwise the successor node.
456 */
457RBTree_Node *_RBTree_Successor( const RBTree_Node *node );
458
459/**
460 * @brief Replaces a node in the red-black tree without a rebalance.
461 *
462 * @param[in] the_rbtree The red-black tree control.
463 * @param[in] victim The victim node.
464 * @param[in] replacement The replacement node.
465 */
466void _RBTree_Replace_node(
467  RBTree_Control *the_rbtree,
468  RBTree_Node    *victim,
469  RBTree_Node    *replacement
470);
471
472/**
473 * @brief Inserts the node into the red-black tree.
474 *
475 * @param the_rbtree The red-black tree control.
476 * @param the_node The node to insert.
477 * @param key The key of the node to insert.  This key must be equal to the key
478 *   stored in the node to insert.  The separate key parameter is provided for
479 *   two reasons.  Firstly, it allows to share the less operator with
480 *   _RBTree_Find_inline().  Secondly, the compiler may generate better code if
481 *   the key is stored in a local variable.
482 * @param less Must return true if the specified key is less than the key of
483 *   the node, otherwise false.
484 *
485 * @retval true The inserted node is the new minimum node according to the
486 *   specified less order function.
487 * @retval false Otherwise.
488 */
489RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline(
490  RBTree_Control *the_rbtree,
491  RBTree_Node    *the_node,
492  const void     *key,
493  bool         ( *less )( const void *, const RBTree_Node * )
494)
495{
496  RBTree_Node **link;
497  RBTree_Node  *parent;
498  bool          is_new_minimum;
499
500  link = _RBTree_Root_reference( the_rbtree );
501  parent = NULL;
502  is_new_minimum = true;
503
504  while ( *link != NULL ) {
505    parent = *link;
506
507    if ( ( *less )( key, parent ) ) {
508      link = _RBTree_Left_reference( parent );
509    } else {
510      link = _RBTree_Right_reference( parent );
511      is_new_minimum = false;
512    }
513  }
514
515  _RBTree_Add_child( the_node, parent, link );
516  _RBTree_Insert_color( the_rbtree, the_node );
517  return is_new_minimum;
518}
519
520/**
521 * @brief Finds an object in the red-black tree with the specified key.
522 *
523 * @param the_rbtree The red-black tree control.
524 * @param key The key to look after.
525 * @param equal Must return true if the specified key equals the key of the
526 *   node, otherwise false.
527 * @param less Must return true if the specified key is less than the key of
528 *   the node, otherwise false.
529 * @param map In case a node with the specified key is found, then this
530 *   function is called to map the node to the object returned.  Usually it
531 *   performs some offset operation via RTEMS_CONTAINER_OF() to map the node to
532 *   its containing object.  Thus, the return type is a void pointer and not a
533 *   red-black tree node.
534 *
535 * @retval object An object with the specified key.
536 * @retval NULL No object with the specified key exists in the red-black tree.
537 */
538RTEMS_INLINE_ROUTINE void *_RBTree_Find_inline(
539  const RBTree_Control *the_rbtree,
540  const void           *key,
541  bool               ( *equal )( const void *, const RBTree_Node * ),
542  bool               ( *less )( const void *, const RBTree_Node * ),
543  void              *( *map )( RBTree_Node * )
544)
545{
546  RBTree_Node * const *link;
547  RBTree_Node         *parent;
548
549  link = _RBTree_Root_const_reference( the_rbtree );
550  parent = NULL;
551
552  while ( *link != NULL ) {
553    parent = *link;
554
555    if ( ( *equal )( key, parent ) ) {
556      return ( *map )( parent );
557    } else if ( ( *less )( key, parent ) ) {
558      link = _RBTree_Left_reference( parent );
559    } else {
560      link = _RBTree_Right_reference( parent );
561    }
562  }
563
564  return NULL;
565}
566
567/**@}*/
568
569#ifdef __cplusplus
570}
571#endif
572
573#endif
574/* end of include file */
Note: See TracBrowser for help on using the repository browser.