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

4.115
Last change on this file since dc62a48c was dc62a48c, checked in by Sebastian Huber <sebastian.huber@…>, on Apr 10, 2012 at 8:25:14 AM

rbtree: PR1995: API change

New functions

o _RBTree_Next_unprotected(),
o _RBTree_Next(),
o _RBTree_Successor_unprotected(),
o _RBTree_Predecessor_unprotected(),
o rtems_rbtree_successor_unprotected(), and
o rtems_rbtree_predecessor_unprotected().

Change prototype of

o _RBTree_Successor(),
o _RBTree_Predecessor(),
o rtems_rbtree_successor(), and
o rtems_rbtree_predecessor().

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