source: rtems/cpukit/include/rtems/score/rbtree.h @ 6539bea

Last change on this file since 6539bea was 6539bea, checked in by Sebastian Huber <sebastian.huber@…>, on Jun 29, 2018 at 6:00:28 PM

score: Add postorder tree iteration support

Update #3465.

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