source: rtems/cpukit/score/src/rbtreenext.c @ 2d7ae960

4.115
Last change on this file since 2d7ae960 was f53aa8d, checked in by Gedare Bloom <gedare@…>, on 05/03/12 at 16:43:29

rbtree: API changes. Remove rbtree control node from RBTree_Next.

The implementation of RBTree_Next was using an awkward construction to detect
and avoid accessing the false root of the red-black tree. To deal with the
false root, RBTree_Next was comparing node parents with the control node.
Instead the false root can be detected by checking if the grandparent of a
node exists; the grandparent of the tree's true root is NULL by definition
so the root of the tree is found while walking up the tree by checking for
the non-existence of a grandparent.

This change propagates into the predecessor/successor and iterate functions.

  • Property mode set to 100644
File size: 1.5 KB
Line 
1/**
2 * @file
3 *
4 * @ingroup ScoreRBTree
5 *
6 * @brief _RBTree_Next_unprotected() and _RBTree_Next() implementation.
7 */
8
9/*
10 * Copyright (c) 2012 embedded brains GmbH.  All rights reserved.
11 *
12 *  embedded brains GmbH
13 *  Obere Lagerstr. 30
14 *  82178 Puchheim
15 *  Germany
16 *  <rtems@embedded-brains.de>
17 *
18 * The license and distribution terms for this file may be
19 * found in the file LICENSE in this distribution or at
20 * http://www.rtems.com/license/LICENSE.
21 */
22
23#if HAVE_CONFIG_H
24  #include "config.h"
25#endif
26
27#include <rtems/score/rbtree.h>
28#include <rtems/score/isr.h>
29
30RBTree_Node *_RBTree_Next_unprotected(
31  const RBTree_Node *node,
32  RBTree_Direction dir
33)
34{
35  RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
36  RBTree_Node *current = node->child [dir];
37  RBTree_Node *next = NULL;
38
39  if ( current != NULL ) {
40    next = current;
41    while ( (current = current->child [opp_dir]) != NULL ) {
42      next = current;
43    }
44  } else {
45    RBTree_Node *parent = node->parent;
46
47    if ( parent->parent && node == parent->child [opp_dir] ) {
48      next = parent;
49    } else {
50      while ( parent->parent && node == parent->child [dir] ) {
51        node = parent;
52        parent = parent->parent;
53      }
54
55      if ( parent->parent ) {
56        next = parent;
57      }
58    }
59  }
60
61  return next;
62}
63
64RBTree_Node *_RBTree_Next(
65  const RBTree_Node *node,
66  RBTree_Direction dir
67)
68{
69  RBTree_Node *next;
70  ISR_Level level;
71
72  _ISR_Disable( level );
73  next = _RBTree_Next_unprotected( node, dir );
74  _ISR_Enable( level );
75
76  return next;
77}
Note: See TracBrowser for help on using the repository browser.