source: rtems/cpukit/score/include/rtems/score/rbtreeimpl.h @ 4752550f

4.115
Last change on this file since 4752550f was 4752550f, checked in by Sebastian Huber <sebastian.huber@…>, on 07/23/14 at 11:19:09

rbtree: Simplify _RBTree_Rotate()

Add and use _RBTree_Direction().

  • Property mode set to 100644
File size: 5.5 KB
Line 
1/**
2 * @file
3 *
4 * @brief Inlined Routines Associated with Red-Black Trees
5 *
6 * This include file contains the bodies of the routines which are
7 * associated with Red-Black Trees and inlined.
8 *
9 * @note  The routines in this file are ordered from simple
10 *        to complex.  No other RBTree Handler routine is referenced
11 *        unless it has already been defined.
12 */
13
14/*
15 *  Copyright (c) 2010-2012 Gedare Bloom.
16 *
17 *  The license and distribution terms for this file may be
18 *  found in the file LICENSE in this distribution or at
19 *  http://www.rtems.org/license/LICENSE.
20 */
21
22#ifndef _RTEMS_SCORE_RBTREEIMPL_H
23#define _RTEMS_SCORE_RBTREEIMPL_H
24
25#include <rtems/score/rbtree.h>
26
27#ifdef __cplusplus
28extern "C" {
29#endif
30
31/**
32 * @addtogroup ScoreRBTree
33 */
34/**@{**/
35
36/**
37 * @brief Red-black tree visitor.
38 *
39 * @param[in] node The node.
40 * @param[in] dir The direction.
41 * @param[in] visitor_arg The visitor argument.
42 *
43 * @retval true Stop the iteration.
44 * @retval false Continue the iteration.
45 *
46 * @see _RBTree_Iterate().
47 */
48typedef bool (*RBTree_Visitor)(
49  const RBTree_Node *node,
50  RBTree_Direction dir,
51  void *visitor_arg
52);
53
54/**
55 * @brief Red-black tree iteration.
56 *
57 * @param[in] rbtree The red-black tree.
58 * @param[in] dir The direction.
59 * @param[in] visitor The visitor.
60 * @param[in] visitor_arg The visitor argument.
61 */
62void _RBTree_Iterate(
63  const RBTree_Control *rbtree,
64  RBTree_Direction dir,
65  RBTree_Visitor visitor,
66  void *visitor_arg
67);
68
69/**
70 * @brief Get the direction opposite to @a the_dir.
71 */
72RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
73  RBTree_Direction the_dir
74)
75{
76  return (RBTree_Direction) !((int) the_dir);
77}
78
79/**
80 * @brief Returns the direction of the node.
81 *
82 * @param[in] the_node The node of interest.
83 * @param[in] parent The parent of the node.  The parent must exist, thus it is
84 * invalid to use this function for the root node.
85 */
86RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction(
87  const RBTree_Node *the_node,
88  const RBTree_Node *parent
89)
90{
91  return (RBTree_Direction) ( the_node != parent->child[ 0 ] );
92}
93
94/**
95 * @brief Is this node red.
96 *
97 * This function returns true if @a the_node is red and false otherwise.
98 *
99 * @retval true @a the_node is red.
100 * @retval false @a the_node in not red.
101 */
102RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
103    const RBTree_Node *the_node
104    )
105{
106  return (the_node && the_node->color == RBT_RED);
107}
108
109/**
110 * @brief Return a pointer to node's grandparent.
111 *
112 * This function returns a pointer to the grandparent of @a the_node if it
113 * exists, and NULL if not.
114 */
115RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
116  const RBTree_Node *the_node
117)
118{
119  if(!the_node) return NULL;
120  if(!(the_node->parent)) return NULL;
121  if(!(the_node->parent->parent)) return NULL;
122  if(!(the_node->parent->parent->parent)) return NULL;
123  return(the_node->parent->parent);
124}
125
126/**
127 * @brief Return a pointer to node's sibling.
128 *
129 * This function returns a pointer to the sibling of @a the_node if it
130 * exists, and NULL if not.
131 */
132RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
133  const RBTree_Node *the_node
134)
135{
136  if(!the_node) return NULL;
137  if(!(the_node->parent)) return NULL;
138  if(!(the_node->parent->parent)) return NULL;
139
140  if(the_node == the_node->parent->child[RBT_LEFT])
141    return the_node->parent->child[RBT_RIGHT];
142  else
143    return the_node->parent->child[RBT_LEFT];
144}
145
146/**
147 * @brief Return a pointer to node's parent's sibling.
148 *
149 * This function returns a pointer to the sibling of the parent of
150 * @a the_node if it exists, and NULL if not.
151 */
152RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
153  const RBTree_Node *the_node
154)
155{
156  if(!the_node) return NULL;
157  if(_RBTree_Grandparent(the_node) == NULL) return NULL;
158
159  return _RBTree_Sibling(the_node->parent);
160}
161
162RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
163  RBTree_Compare_result compare_result
164)
165{
166  return compare_result == 0;
167}
168
169RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
170  RBTree_Compare_result compare_result
171)
172{
173  return compare_result > 0;
174}
175
176RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
177  RBTree_Compare_result compare_result
178)
179{
180  return compare_result < 0;
181}
182
183/**
184 * @brief Rotates the node in the specified direction.
185 *
186 * The node is swapped with its child in the opposite direction if it exists.
187 *
188 * Sub-tree before rotation:
189 * @dot
190 * digraph state {
191 *   parent -> the_node;
192 *   the_node -> sibling [label="dir"];
193 *   the_node -> child [label="opp_dir"];
194 *   child -> grandchild [label="dir"];
195 *   child -> grandchildsibling [label="opp_dir"];
196 * }
197 * @enddot
198 *
199 * Sub-tree after rotation:
200 * @dot
201 * digraph state {
202 *   parent -> child;
203 *   the_node -> sibling [label="dir"];
204 *   the_node -> grandchild [label="opp_dir"];
205 *   child -> the_node [label="dir"];
206 *   child -> grandchildsibling [label="opp_dir"];
207 * }
208 * @enddot
209 *
210 * @param[in] the_node The node to rotate.
211 * @param[in] dir The rotation direction.
212 */
213RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
214  RBTree_Node      *the_node,
215  RBTree_Direction  dir
216)
217{
218  RBTree_Direction  opp_dir = _RBTree_Opposite_direction( dir );
219  RBTree_Node      *child = the_node->child[ opp_dir ];
220  RBTree_Node      *grandchild;
221  RBTree_Node      *parent;
222
223  if ( child == NULL)
224    return;
225
226  grandchild = child->child[ dir ];
227  the_node->child[ opp_dir ] = grandchild;
228
229  if ( grandchild != NULL )
230    grandchild->parent = the_node;
231
232  child->child[ dir ] = the_node;
233
234  parent = _RBTree_Parent( the_node );
235  parent->child[ _RBTree_Direction( the_node, parent ) ] = child;
236
237  child->parent = parent;
238  the_node->parent = child;
239}
240
241/** @} */
242
243#ifdef __cplusplus
244}
245#endif
246
247#endif
248/* end of include file */
Note: See TracBrowser for help on using the repository browser.