source: rtems/cpukit/score/inline/rtems/score/rbtree.inl @ 8712622

4.115
Last change on this file since 8712622 was 8712622, checked in by Gedare Bloom <gedare@…>, on May 2, 2012 at 3:13:22 PM

score/rbtree: replace _RBTree_Peek_unprotected with _RBTree_First.

  • Property mode set to 100644
File size: 12.5 KB
Line 
1/**
2 *  @file  rtems/score/rbtree.inl
3 *
4 *  This include file contains the bodies of the routines which are
5 *  associated with Red-Black Trees and inlined.
6 *
7 *  @note  The routines in this file are ordered from simple
8 *         to complex.  No other RBTree Handler routine is referenced
9 *         unless it has already been defined.
10 */
11
12/*
13 *  Copyright (c) 2010-2012 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.com/license/LICENSE.
18 */
19
20#ifndef _RTEMS_SCORE_RBTREE_H
21# error "Never use <rtems/score/rbtree.inl> directly; include <rtems/score/rbtree.h> instead."
22#endif
23
24#ifndef _RTEMS_SCORE_RBTREE_INL
25#define _RTEMS_SCORE_RBTREE_INL
26
27/**
28 *  @addtogroup ScoreRBTree
29 *  @{
30 */
31
32/**
33 * @brief Get the direction opposite to @a the_dir
34 */
35RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
36  RBTree_Direction the_dir
37)
38{
39  return (RBTree_Direction) !((int) the_dir);
40}
41
42/** @brief Set off rbtree
43 *
44 *  This function sets the parent and child fields of the @a node to NULL
45 *  indicating the @a node is not part of a rbtree.
46 *
47 */
48RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
49    RBTree_Node *node
50    )
51{
52  node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
53}
54
55/** @brief Is the Node off RBTree
56 *
57 *  This function returns true if the @a node is not on a rbtree. A @a node is
58 *  off rbtree if the parent and child fields are set to NULL.
59 */
60RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
61    const RBTree_Node *node
62    )
63{
64  return (node->parent == NULL) && (node->child[RBT_LEFT] == NULL) && (node->child[RBT_RIGHT] == NULL);
65}
66
67/** @brief Are Two Nodes Equal
68 *
69 *  This function returns true if @a left and @a right are equal,
70 *  and false otherwise.
71 */
72RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
73    const RBTree_Node *left,
74    const RBTree_Node *right
75    )
76{
77  return left == right;
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 */
84RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
85    const RBTree_Control *the_rbtree
86    )
87{
88  return (the_rbtree == NULL);
89}
90
91/** @brief Is the RBTree Node Pointer NULL
92 *
93 *  This function returns true if @a the_node is NULL and false otherwise.
94 */
95RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node(
96    const RBTree_Node *the_node
97    )
98{
99  return (the_node == NULL);
100}
101
102
103/** @brief Return pointer to RBTree's root node
104 *
105 *  This function returns a pointer to the root node of @a the_rbtree.
106 */
107RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
108  const RBTree_Control *the_rbtree
109)
110{
111  return the_rbtree->root;
112}
113
114/** @brief Return pointer to RBTree's First node
115 *
116 *  This function returns a pointer to the first node on @a the_rbtree,
117 *  where @a dir specifies whether to return the minimum (0) or maximum (1).
118 */
119RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
120  const RBTree_Control *the_rbtree,
121  RBTree_Direction dir
122)
123{
124  return the_rbtree->first[dir];
125}
126
127/** @brief Return pointer to the parent of this node
128 *
129 *  This function returns a pointer to the parent node of @a the_node.
130 */
131RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
132  const RBTree_Node *the_node
133)
134{
135  if (!the_node->parent->parent) return NULL;
136  return the_node->parent;
137}
138
139/** @brief Return pointer to the left of this node
140 *
141 *  This function returns a pointer to the left node of this node.
142 *
143 *  @param[in] the_node is the node to be operated upon.
144 *
145 *  @return This method returns the left node on the rbtree.
146 */
147RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
148  const RBTree_Node *the_node
149)
150{
151  return the_node->child[RBT_LEFT];
152}
153
154/** @brief Return pointer to the right of this node
155 *
156 *  This function returns a pointer to the right node of this node.
157 *
158 *  @param[in] the_node is the node to be operated upon.
159 *
160 *  @return This method returns the right node on the rbtree.
161 */
162RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
163  const RBTree_Node *the_node
164)
165{
166  return the_node->child[RBT_RIGHT];
167}
168
169/** @brief Is the RBTree Empty
170 *
171 *  This function returns true if there are no nodes on @a the_rbtree and
172 *  false otherwise.
173 *
174 *  @param[in] the_rbtree is the rbtree to be operated upon.
175 *
176 *  @return This function returns true if there are no nodes on
177 *  @a the_rbtree and false otherwise.
178 */
179RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
180  const RBTree_Control *the_rbtree
181)
182{
183  return (the_rbtree->root == NULL);
184}
185
186/** @brief Is this the First Node on the RBTree
187 *
188 *  This function returns true if @a the_node is the first node on
189 *  @a the_rbtree and false otherwise. @a dir specifies whether first means
190 *  minimum (0) or maximum (1).
191 *
192 */
193RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
194  const RBTree_Control *the_rbtree,
195  const RBTree_Node *the_node,
196  RBTree_Direction dir
197)
198{
199  return (the_node == _RBTree_First(the_rbtree, dir));
200}
201
202/** @brief Is this node red?
203 *
204 *  This function returns true if @a the_node is red and false otherwise.
205 */
206RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
207    const RBTree_Node *the_node
208    )
209{
210  return (the_node && the_node->color == RBT_RED);
211}
212
213
214/** @brief Does this RBTree have only One Node
215 *
216 *  This function returns true if there is only one node on @a the_rbtree and
217 *  false otherwise.
218 *
219 */
220RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node(
221    const RBTree_Control *the_rbtree
222    )
223{
224  if(!the_rbtree) return NULL; /* TODO: expected behavior? */
225  return (the_rbtree->root->child[RBT_LEFT] == NULL && the_rbtree->root->child[RBT_RIGHT] == NULL);
226}
227
228/** @brief Is this Node the RBTree root
229 *
230 *  This function returns true if @a the_node is the root of @a the_rbtree and
231 *  false otherwise.
232 */
233RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
234  const RBTree_Control *the_rbtree,
235  const RBTree_Node    *the_node
236)
237{
238  return (the_node == _RBTree_Root(the_rbtree));
239}
240
241/** @brief Initialize this RBTree as Empty
242 *
243 *  This routine initializes @a the_rbtree to contain zero nodes.
244 */
245RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
246    RBTree_Control          *the_rbtree,
247    RBTree_Compare_function  compare_function,
248    bool                     is_unique
249    )
250{
251  the_rbtree->permanent_null   = NULL;
252  the_rbtree->root             = NULL;
253  the_rbtree->first[0]         = NULL;
254  the_rbtree->first[1]         = NULL;
255  the_rbtree->compare_function = compare_function;
256  the_rbtree->is_unique        = is_unique;
257}
258
259/** @brief Return a pointer to node's grandparent
260 *
261 *  This function returns a pointer to the grandparent of @a the_node if it
262 *  exists, and NULL if not.
263 * 
264 */
265RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
266  const RBTree_Node *the_node
267)
268{
269  if(!the_node) return NULL;
270  if(!(the_node->parent)) return NULL;
271  if(!(the_node->parent->parent)) return NULL;
272  if(!(the_node->parent->parent->parent)) return NULL;
273  return(the_node->parent->parent);
274}
275
276/** @brief Return a pointer to node's sibling
277 *
278 *  This function returns a pointer to the sibling of @a the_node if it
279 *  exists, and NULL if not.
280 */
281RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
282  const RBTree_Node *the_node
283)
284{
285  if(!the_node) return NULL;
286  if(!(the_node->parent)) return NULL;
287  if(!(the_node->parent->parent)) return NULL;
288
289  if(the_node == the_node->parent->child[RBT_LEFT])
290    return the_node->parent->child[RBT_RIGHT];
291  else
292    return the_node->parent->child[RBT_LEFT];
293}
294
295/** @brief Return a pointer to node's parent's sibling
296 *
297 *  This function returns a pointer to the sibling of the parent of
298 *  @a the_node if it exists, and NULL if not.
299 */
300RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
301  const RBTree_Node *the_node
302)
303{
304  if(!the_node) return NULL;
305  if(_RBTree_Grandparent(the_node) == NULL) return NULL;
306
307  return _RBTree_Sibling(the_node->parent);
308}
309
310/** @brief Find the RBTree_Control header given a node in the tree
311 *
312 *  This function returns a pointer to the header of the Red Black
313 *  Tree containing @a the_node if it exists, and NULL if not.
314 */
315RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
316    RBTree_Node *the_node
317    )
318{
319  if(!the_node) return NULL;
320  if(!(the_node->parent)) return NULL;
321  while(the_node->parent) the_node = the_node->parent;
322  return (RBTree_Control*)the_node;
323}
324
325RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
326{
327  return compare_result == 0;
328}
329
330RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
331  int compare_result
332)
333{
334  return compare_result > 0;
335}
336
337RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
338  int compare_result
339)
340{
341  return compare_result < 0;
342}
343
344/** @brief Find the node with given key in the tree
345 *
346 *  This function returns a pointer to the node in @a the_rbtree
347 *  having key equal to key of  @a the_node if it exists,
348 *  and NULL if not. @a the_node has to be made up before a search.
349 *
350 *  @note If the tree is not unique and contains duplicate keys, the set
351 *        of duplicate keys acts as FIFO.
352 */
353RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
354    RBTree_Control *the_rbtree,
355    RBTree_Node *the_node
356    )
357{
358  RBTree_Node* iter_node = the_rbtree->root;
359  RBTree_Node* found = NULL;
360  int compare_result;
361  while (iter_node) {
362    compare_result = the_rbtree->compare_function(the_node, iter_node);
363    if ( _RBTree_Is_equal( compare_result ) ) {
364      found = iter_node;
365      if ( the_rbtree->is_unique )
366        break;
367    }
368
369    RBTree_Direction dir =
370      (RBTree_Direction) _RBTree_Is_greater( compare_result );
371    iter_node = iter_node->child[dir];
372  } /* while(iter_node) */
373
374  return found;
375}
376
377/**
378 * @brief Returns the predecessor of a node.
379 *
380 * @param[in] rbtree The red-black tree.
381 * @param[in] node The node.
382 *
383 * @retval NULL The predecessor does not exist.
384 * @retval otherwise The predecessor node.
385 */
386RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
387  const RBTree_Control *rbtree,
388  const RBTree_Node *node
389)
390{
391  return _RBTree_Next_unprotected( rbtree, node, RBT_LEFT );
392}
393
394/**
395 * @copydoc _RBTree_Predecessor_unprotected()
396 *
397 * The function disables the interrupts protect the operation.
398 */
399RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
400  const RBTree_Control *rbtree,
401  const RBTree_Node *node
402)
403{
404  return _RBTree_Next( rbtree, node, RBT_LEFT );
405}
406
407/**
408 * @brief Returns the successor of a node.
409 *
410 * @param[in] rbtree The red-black tree.
411 * @param[in] node The node.
412 *
413 * @retval NULL The successor does not exist.
414 * @retval otherwise The successor node.
415 */
416RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
417  const RBTree_Control *rbtree,
418  const RBTree_Node *node
419)
420{
421  return _RBTree_Next_unprotected( rbtree, node, RBT_RIGHT );
422}
423
424/**
425 * @copydoc _RBTree_Successor_unprotected()
426 *
427 * The function disables the interrupts protect the operation.
428 */
429RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
430  const RBTree_Control *rbtree,
431  const RBTree_Node *node
432)
433{
434  return _RBTree_Next( rbtree, node, RBT_RIGHT );
435}
436
437/** @brief Get the First Node (unprotected)
438 *
439 *  This function removes the minimum or maximum node from the_rbtree and
440 *  returns a pointer to that node.  It does NOT disable interrupts to ensure
441 *  the atomicity of the get operation.
442 *
443 *  @param[in] the_rbtree is the rbtree to attempt to get the min node from.
444 *  @param[in] dir specifies whether to get minimum (0) or maximum (1)
445 *
446 *  @return This method returns the min or max node on the rbtree, or NULL.
447 *
448 *  @note This routine may return NULL if the RBTree is empty.
449 */
450RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
451    RBTree_Control *the_rbtree,
452    RBTree_Direction dir
453    )
454{
455  RBTree_Node *the_node = the_rbtree->first[dir];
456  _RBTree_Extract_unprotected(the_rbtree, the_node);
457  return the_node;
458}
459
460/** @brief Rotate the_node in the direction passed as second argument
461 * 
462 *  This routine rotates @a the_node to the direction @a dir, swapping
463 *  @a the_node with its child\[@a dir\].
464 */
465RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
466    RBTree_Node *the_node,
467    RBTree_Direction dir
468    )
469{
470  RBTree_Node *c;
471  if (the_node == NULL) return;
472  if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
473
474  c = the_node->child[_RBTree_Opposite_direction(dir)];
475  the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
476
477  if (c->child[dir])
478    c->child[dir]->parent = the_node;
479
480  c->child[dir] = the_node;
481
482  the_node->parent->child[the_node != the_node->parent->child[0]] = c;
483
484  c->parent = the_node->parent;
485  the_node->parent = c;
486}
487
488/** @brief Determines whether the tree is unique
489 */
490RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
491  const RBTree_Control *the_rbtree
492)
493{
494  return( the_rbtree && the_rbtree->is_unique );
495}
496/**@}*/
497
498#endif
499/* end of include file */
Note: See TracBrowser for help on using the repository browser.