source: rtems/cpukit/score/include/rtems/score/rbtreeimpl.h @ 8e7db68c

4.115
Last change on this file since 8e7db68c was c499856, checked in by Chris Johns <chrisj@…>, on 03/20/14 at 21:10:47

Change all references of rtems.com to rtems.org.

  • Property mode set to 100644
File size: 4.8 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 Is this RBTree control pointer NULL.
81 *
82 * This function returns true if @a the_rbtree is NULL and false otherwise.
83 *
84 * @retval true @a the_rbtree is @c NULL.
85 * @retval false @a the_rbtree is not @c NULL.
86 */
87RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
88    const RBTree_Control *the_rbtree
89    )
90{
91  return (the_rbtree == NULL);
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( int compare_result )
163{
164  return compare_result == 0;
165}
166
167RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
168  int compare_result
169)
170{
171  return compare_result > 0;
172}
173
174RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
175  int compare_result
176)
177{
178  return compare_result < 0;
179}
180
181/**
182 * @brief Rotate the_node in the direction passed as second argument.
183 *
184 * This routine rotates @a the_node to the direction @a dir, swapping
185 * @a the_node with its child\[@a dir\].
186 */
187RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
188    RBTree_Node *the_node,
189    RBTree_Direction dir
190    )
191{
192  RBTree_Node *c;
193  if (the_node == NULL) return;
194  if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
195
196  c = the_node->child[_RBTree_Opposite_direction(dir)];
197  the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
198
199  if (c->child[dir])
200    c->child[dir]->parent = the_node;
201
202  c->child[dir] = the_node;
203
204  the_node->parent->child[the_node != the_node->parent->child[0]] = c;
205
206  c->parent = the_node->parent;
207  the_node->parent = c;
208}
209
210/** @} */
211
212#ifdef __cplusplus
213}
214#endif
215
216#endif
217/* end of include file */
Note: See TracBrowser for help on using the repository browser.