source: rtems/cpukit/include/rtems/score/rbtree.h @ 0b698ba5

Last change on this file since 0b698ba5 was 0b698ba5, checked in by Chris Johns <chrisj@…>, on May 13, 2019 at 10:39:55 PM

doxygen: score: Fix block comment end marker.

  • Property mode set to 100644
File size: 16.6 KB
Line 
1/**
2 * @file
3 *
4 * @ingroup RTEMSScoreRBTree
5 *
6 * @brief Constants and Structures Associated with the Red-Black Tree Handler
7 *
8 * This include file contains all the constants and structures associated
9 * with the Red-Black Tree Handler.
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_SCORE_RBTREE_H
21#define _RTEMS_SCORE_RBTREE_H
22
23#include <sys/tree.h>
24#include <rtems/score/basedefs.h>
25#include <rtems/score/assert.h>
26
27#ifdef __cplusplus
28extern "C" {
29#endif
30
31/**
32 * @defgroup RTEMSScoreRBTree Red-Black Tree Handler
33 *
34 * @ingroup RTEMSScore
35 *
36 * @brief Red-Black Tree Handler.
37 *
38 * The Red-Black Tree Handler is used to manage sets of entities.  This handler
39 * provides two data structures.  The rbtree Node data structure is included
40 * as the first part of every data structure that will be placed on
41 * a RBTree.  The second data structure is rbtree Control which is used
42 * to manage a set of rbtree Nodes.
43 *
44 * @{
45 */
46
47struct RBTree_Control;
48
49/**
50 * @brief Red-black tree node.
51 *
52 * This is used to manage each node (element) which is placed on a red-black
53 * tree.
54 */
55typedef struct RBTree_Node {
56  RB_ENTRY(RBTree_Node) Node;
57} RBTree_Node;
58
59/**
60 * @brief Red-black tree control.
61 *
62 * This is used to manage a red-black tree.  A red-black tree consists of a
63 * tree of zero or more nodes.
64 */
65typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
66
67/**
68 * @brief Initializer for an empty red-black tree with designator @a name.
69 */
70#define RBTREE_INITIALIZER_EMPTY( name ) \
71  RB_INITIALIZER( name )
72
73/**
74 * @brief Definition for an empty red-black tree with designator @a name.
75 */
76#define RBTREE_DEFINE_EMPTY( name ) \
77  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
78
79/**
80 * @brief Sets a red-black tree node as off-tree.
81 *
82 * Do not use this function on nodes which are a part of a tree.
83 *
84 * @param[out] the_node The node to set off-tree.
85 *
86 * @see _RBTree_Is_node_off_tree().
87 */
88RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
89{
90  RB_COLOR( the_node, Node ) = -1;
91}
92
93/**
94 * @brief Checks if this red-black tree node is off-tree.
95 *
96 * @param the_node The node to test.
97 *
98 * @retval true The node is not a part of a tree (off-tree).
99 * @retval false The node is part of a tree.
100 *
101 * @see _RBTree_Set_off_tree().
102 */
103RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
104  const RBTree_Node *the_node
105)
106{
107  return RB_COLOR( the_node, Node ) == -1;
108}
109
110/**
111 * @brief Rebalances the red-black tree after insertion of the node.
112 *
113 * @param[in, out] the_rbtree The red-black tree control.
114 * @param[in, out] the_node The most recently inserted node.
115 */
116void _RBTree_Insert_color(
117  RBTree_Control *the_rbtree,
118  RBTree_Node    *the_node
119);
120
121/**
122 * @brief Initializes a red-black tree node.
123 *
124 * In debug configurations, the node is set off tree.  In all other
125 * configurations, this function does nothing.
126 *
127 * @param[out] the_node The red-black tree node to initialize.
128 */
129RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node )
130{
131#if defined(RTEMS_DEBUG)
132  _RBTree_Set_off_tree( the_node );
133#else
134  (void) the_node;
135#endif
136}
137
138/**
139 * @brief Adds a child node to a parent node.
140 *
141 * @param child The child node.
142 * @param[out] parent The parent node.
143 * @param[out] 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, out] the_rbtree The red-black tree control.
161 * @param[in, out] the_node The node to insert.
162 * @param[out] parent The parent node.
163 * @param[out] 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 the case this is desired, then
221 * call _RBTree_Set_off_tree() after the extraction.
222 *
223 * In the case the node to extract is not a node of the tree, then this function
224 * yields unpredictable results.
225 *
226 * @param[in, out] the_rbtree The red-black tree control.
227 * @param[out] 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 the_rbtree The red-black tree control.
240 *
241 * @retval root The root node.
242 * @retval NULL The tree is empty.
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 *
256 * @param the_rbtree The red-black tree control.
257 *
258 * @retval pointer Pointer to the root node.
259 * @retval NULL The tree is empty.
260 */
261RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference(
262  RBTree_Control *the_rbtree
263)
264{
265  return &RB_ROOT( the_rbtree );
266}
267
268/**
269 * @brief Returns a constant reference to the root pointer of the red-black tree.
270 *
271 * @param the_rbtree The red-black tree control.
272 *
273 * @retval pointer Pointer to the root node.
274 * @retval NULL The tree is empty.
275 */
276RTEMS_INLINE_ROUTINE RBTree_Node * const *_RBTree_Root_const_reference(
277  const RBTree_Control *the_rbtree
278)
279{
280  return &RB_ROOT( the_rbtree );
281}
282
283/**
284 * @brief Returns a pointer to the parent of this node.
285 *
286 * The node must have a parent, thus it is invalid to use this function for the
287 * root node or a node that is not part of a tree.  To test for the root node
288 * compare with _RBTree_Root() or use _RBTree_Is_root().
289 *
290 * @param the_node The node of interest.
291 *
292 * @retval parent The parent of this node.
293 * @retval undefined The node is the root node or not part of a tree.
294 */
295RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
296  const RBTree_Node *the_node
297)
298{
299  return RB_PARENT( the_node, Node );
300}
301
302/**
303 * @brief Returns pointer to the left of this node.
304 *
305 * This function returns a pointer to the left node of this node.
306 *
307 * @param the_node is the node to be operated upon.
308 *
309 * @return This method returns the left node on the rbtree.
310 */
311RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
312  const RBTree_Node *the_node
313)
314{
315  return RB_LEFT( the_node, Node );
316}
317
318/**
319 * @brief Returns a reference to the left child pointer of the red-black tree
320 * node.
321 *
322 * @param the_node is the node to be operated upon.
323 *
324 * @return This method returns a reference to the left child pointer on the rbtree.
325 */
326RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference(
327  RBTree_Node *the_node
328)
329{
330  return &RB_LEFT( the_node, Node );
331}
332
333/**
334 * @brief Returns pointer to the right of this node.
335 *
336 * This function returns a pointer to the right node of this node.
337 *
338 * @param the_node is the node to be operated upon.
339 *
340 * @return This method returns the right node on the rbtree.
341 */
342RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
343  const RBTree_Node *the_node
344)
345{
346  return RB_RIGHT( the_node, Node );
347}
348
349/**
350 * @brief Returns a reference to the right child pointer of the red-black tree
351 * node.
352 *
353 * @param the_node is the node to be operated upon.
354 *
355 * @return This method returns a reference to the right child pointer on the rbtree.
356 */
357RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference(
358  RBTree_Node *the_node
359)
360{
361  return &RB_RIGHT( the_node, Node );
362}
363
364/**
365 * @brief Checks if the RBTree is empty.
366 *
367 * This function returns true if there are no nodes on @a the_rbtree and
368 * false otherwise.
369 *
370 * @param the_rbtree is the rbtree to be operated upon.
371 *
372 * @retval true There are no nodes on @a the_rbtree.
373 * @retval false There are nodes on @a the_rbtree.
374 */
375RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
376  const RBTree_Control *the_rbtree
377)
378{
379  return RB_EMPTY( the_rbtree );
380}
381
382/**
383 * @brief Checks if this node is the root node of a red-black tree.
384 *
385 * The root node may change after insert or extract operations.  In case the
386 * node is not a node of a tree, then this function yields unpredictable
387 * results.
388 *
389 * @param the_node The node of interest.
390 *
391 * @retval true @a the_node is the root node.
392 * @retval false @a the_node is not the root node.
393 *
394 * @see _RBTree_Root().
395 */
396RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
397  const RBTree_Node *the_node
398)
399{
400  return _RBTree_Parent( the_node ) == NULL;
401}
402
403/**
404 * @brief Initializes this RBTree as empty.
405 *
406 * This routine initializes @a the_rbtree to contain zero nodes.
407 *
408 * @param[out] the_rbtree The rbtree to initialize.
409 */
410RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
411  RBTree_Control *the_rbtree
412)
413{
414  RB_INIT( the_rbtree );
415}
416
417/**
418 * @brief Initializes this red-black tree to contain exactly the specified
419 * node.
420 *
421 * @param[out] the_rbtree The red-black tree control.
422 * @param[out] the_node The one and only node.
423 */
424RTEMS_INLINE_ROUTINE void _RBTree_Initialize_one(
425  RBTree_Control *the_rbtree,
426  RBTree_Node    *the_node
427)
428{
429  _Assert( _RBTree_Is_node_off_tree( the_node ) );
430  RB_ROOT( the_rbtree ) = the_node;
431  RB_PARENT( the_node, Node ) = NULL;
432  RB_LEFT( the_node, Node ) = NULL;
433  RB_RIGHT( the_node, Node ) = NULL;
434  RB_COLOR( the_node, Node ) = RB_BLACK;
435}
436
437/**
438 * @brief Returns the minimum node of the red-black tree.
439 *
440 * @param the_rbtree The red-black tree control.
441 *
442 * @retval node The minimum node.
443 * @retval NULL The red-black tree is empty.
444 */
445RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );
446
447/**
448 * @brief Returns the maximum node of the red-black tree.
449 *
450 * @param the_rbtree The red-black tree control.
451 *
452 * @retval node The maximum node.
453 * @retval NULL The red-black tree is empty.
454 */
455RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );
456
457/**
458 * @brief Returns the predecessor of a node.
459 *
460 * @param node is the node.
461 *
462 * @retval node The predecessor node.
463 * @retval NULL The predecessor does not exist.
464 */
465RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );
466
467/**
468 * @brief Returns the successor of a node.
469 *
470 * @param node is the node.
471 *
472 * @retval node The successor node.
473 * @retval NULL The successor does not exist.
474 */
475RBTree_Node *_RBTree_Successor( const RBTree_Node *node );
476
477/**
478 * @brief Replaces a node in the red-black tree without a rebalance.
479 *
480 * @param[in, out] the_rbtree The red-black tree control.
481 * @param victim The victim node.
482 * @param[out] replacement The replacement node.
483 */
484void _RBTree_Replace_node(
485  RBTree_Control *the_rbtree,
486  RBTree_Node    *victim,
487  RBTree_Node    *replacement
488);
489
490/**
491 * @brief Inserts the node into the red-black tree.
492 *
493 * @param[in, out] the_rbtree The red-black tree control.
494 * @param[out] the_node The node to insert.
495 * @param key The key of the node to insert.  This key must be equal to the key
496 *   stored in the node to insert.  The separate key parameter is provided for
497 *   two reasons.  Firstly, it allows to share the less operator with
498 *   _RBTree_Find_inline().  Secondly, the compiler may generate better code if
499 *   the key is stored in a local variable.
500 * @param less Must return true if the specified key is less than the key of
501 *   the node, otherwise false.
502 *
503 * @retval true The inserted node is the new minimum node according to the
504 *   specified less order function.
505 * @retval false The inserted node is not the new minimum node according to the
506 *   specified less order function.
507 */
508RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline(
509  RBTree_Control *the_rbtree,
510  RBTree_Node    *the_node,
511  const void     *key,
512  bool         ( *less )( const void *, const RBTree_Node * )
513)
514{
515  RBTree_Node **link;
516  RBTree_Node  *parent;
517  bool          is_new_minimum;
518
519  link = _RBTree_Root_reference( the_rbtree );
520  parent = NULL;
521  is_new_minimum = true;
522
523  while ( *link != NULL ) {
524    parent = *link;
525
526    if ( ( *less )( key, parent ) ) {
527      link = _RBTree_Left_reference( parent );
528    } else {
529      link = _RBTree_Right_reference( parent );
530      is_new_minimum = false;
531    }
532  }
533
534  _RBTree_Add_child( the_node, parent, link );
535  _RBTree_Insert_color( the_rbtree, the_node );
536  return is_new_minimum;
537}
538
539/**
540 * @brief Finds an object in the red-black tree with the specified key.
541 *
542 * @param the_rbtree The red-black tree control.
543 * @param key The key to look after.
544 * @param equal Must return true if the specified key equals the key of the
545 *   node, otherwise false.
546 * @param less Must return true if the specified key is less than the key of
547 *   the node, otherwise false.
548 * @param map In case a node with the specified key is found, then this
549 *   function is called to map the node to the object returned.  Usually it
550 *   performs some offset operation via RTEMS_CONTAINER_OF() to map the node to
551 *   its containing object.  Thus, the return type is a void pointer and not a
552 *   red-black tree node.
553 *
554 * @retval object An object with the specified key.
555 * @retval NULL No object with the specified key exists in the red-black tree.
556 */
557RTEMS_INLINE_ROUTINE void *_RBTree_Find_inline(
558  const RBTree_Control *the_rbtree,
559  const void           *key,
560  bool               ( *equal )( const void *, const RBTree_Node * ),
561  bool               ( *less )( const void *, const RBTree_Node * ),
562  void              *( *map )( RBTree_Node * )
563)
564{
565  RBTree_Node * const *link;
566  RBTree_Node         *parent;
567
568  link = _RBTree_Root_const_reference( the_rbtree );
569  parent = NULL;
570
571  while ( *link != NULL ) {
572    parent = *link;
573
574    if ( ( *equal )( key, parent ) ) {
575      return ( *map )( parent );
576    } else if ( ( *less )( key, parent ) ) {
577      link = _RBTree_Left_reference( parent );
578    } else {
579      link = _RBTree_Right_reference( parent );
580    }
581  }
582
583  return NULL;
584}
585
586/**
587 * @brief Returns the container of the first node of the specified red-black
588 * tree in postorder.
589 *
590 * Postorder traversal may be used to delete all nodes of a red-black tree.
591 *
592 * @param the_rbtree The red-black tree control.
593 * @param offset The offset to the red-black tree node in the container structure.
594 *
595 * @retval container The container of the first node of the specified red-black
596 *   tree in postorder.
597 * @retval NULL The red-black tree is empty.
598 *
599 * @see _RBTree_Postorder_next().
600 *
601 * @code
602 * #include <rtems/score/rbtree.h>
603 *
604 * typedef struct {
605 *   int         data;
606 *   RBTree_Node Node;
607 * } Container_Control;
608 *
609 * void visit( Container_Control *the_container );
610 *
611 * void postorder_traversal( RBTree_Control *the_rbtree )
612 * {
613 *   Container_Control *the_container;
614 *
615 *   the_container = _RBTree_Postorder_first(
616 *     the_rbtree,
617 *     offsetof( Container_Control, Node )
618 *   );
619 *
620 *   while ( the_container != NULL ) {
621 *     visit( the_container );
622 *
623 *     the_container = _RBTree_Postorder_next(
624 *       &the_container->Node,
625 *       offsetof( Container_Control, Node )
626 *     );
627 *   }
628 * }
629 * @endcode
630 */
631void *_RBTree_Postorder_first(
632  const RBTree_Control *the_rbtree,
633  size_t                offset
634);
635
636/**
637 * @brief Returns the container of the next node in postorder.
638 *
639 * @param the_node The red-black tree node.  The node must not be NULL.
640 * @param offset The offset to the red-black tree node in the container structure.
641 *
642 * @retval container The container of the next node in postorder.
643 * @retval NULL The node is NULL or there is no next node in postorder.
644 *
645 * @see _RBTree_Postorder_first().
646 */
647void *_RBTree_Postorder_next(
648  const RBTree_Node *the_node,
649  size_t             offset
650);
651
652/** @} */
653
654#ifdef __cplusplus
655}
656#endif
657
658#endif
659/* end of include file */
Note: See TracBrowser for help on using the repository browser.