source: rtems/cpukit/score/inline/rtems/score/rbtree.inl @ 74f1c73e

4.115
Last change on this file since 74f1c73e was 74f1c73e, checked in by Joel Sherrill <joel.sherrill@…>, on 08/21/11 at 20:07:11

2011-08-21 Petr Benes <benesp16@…>

PR 1886/cpukit

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