[rtems commit] rbtree: API changes. Remove rbtree control node from RBTree_Next.
Gedare Bloom
gedare at rtems.org
Tue May 8 22:37:56 UTC 2012
Module: rtems
Branch: master
Commit: f53aa8d3026eb97e3c67e44a1c931442dbc95010
Changeset: http://git.rtems.org/rtems/commit/?id=f53aa8d3026eb97e3c67e44a1c931442dbc95010
Author: Gedare Bloom <gedare at rtems.org>
Date: Thu May 3 12:43:29 2012 -0400
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.
---
cpukit/sapi/inline/rtems/rbtree.inl | 12 ++++--------
cpukit/sapi/src/rbheap.c | 7 +++----
cpukit/score/include/rtems/score/rbtree.h | 3 ---
cpukit/score/inline/rtems/score/rbtree.inl | 12 ++++--------
cpukit/score/src/rbtreeextract.c | 4 ++--
cpukit/score/src/rbtreeiterate.c | 2 +-
cpukit/score/src/rbtreenext.c | 13 +++++--------
testsuites/sptests/sprbtree01/init.c | 4 ++--
8 files changed, 21 insertions(+), 36 deletions(-)
diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
index 804cf38..dc53fa0 100644
--- a/cpukit/sapi/inline/rtems/rbtree.inl
+++ b/cpukit/sapi/inline/rtems/rbtree.inl
@@ -283,44 +283,40 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
* @copydoc _RBTree_Predecessor_unprotected()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
- const rtems_rbtree_control *rbtree,
const rtems_rbtree_node *node
)
{
- return _RBTree_Predecessor_unprotected( rbtree, node );
+ return _RBTree_Predecessor_unprotected( node );
}
/**
* @copydoc _RBTree_Predecessor()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
- const rtems_rbtree_control *rbtree,
const rtems_rbtree_node *node
)
{
- return _RBTree_Predecessor( rbtree, node );
+ return _RBTree_Predecessor( node );
}
/**
* @copydoc _RBTree_Successor_unprotected()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
- const rtems_rbtree_control *rbtree,
const rtems_rbtree_node *node
)
{
- return _RBTree_Successor_unprotected( rbtree, node );
+ return _RBTree_Successor_unprotected( node );
}
/**
* @copydoc _RBTree_Successor()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
- const rtems_rbtree_control *rbtree,
const rtems_rbtree_node *node
)
{
- return _RBTree_Successor( rbtree, node );
+ return _RBTree_Successor( node );
}
/**
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index 7facf4f..5233778 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -203,13 +203,12 @@ static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
}
static rtems_rbheap_chunk *get_next(
- const rtems_rbtree_control *chunk_tree,
const rtems_rbheap_chunk *chunk,
RBTree_Direction dir
)
{
return rtems_rbheap_chunk_of_node(
- _RBTree_Next_unprotected(chunk_tree, &chunk->tree_node, dir)
+ _RBTree_Next_unprotected(&chunk->tree_node, dir)
);
}
@@ -246,8 +245,8 @@ rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr)
if (chunk != NULL_PAGE) {
if (!rtems_rbheap_is_chunk_free(chunk)) {
- rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT);
- rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT);
+ rtems_rbheap_chunk *pred = get_next(chunk, RBT_LEFT);
+ rtems_rbheap_chunk *succ = get_next(chunk, RBT_RIGHT);
check_and_merge(free_chain, chunk_tree, chunk, succ);
add_to_chain(free_chain, chunk);
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index d98392e..b3cfc45 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -307,7 +307,6 @@ void _RBTree_Extract(
/**
* @brief Returns the in-order next node of a node.
*
- * @param[in] rbtree The red-black tree.
* @param[in] node The node.
* @param[in] dir The direction.
*
@@ -315,7 +314,6 @@ void _RBTree_Extract(
* @retval otherwise The next node.
*/
RBTree_Node *_RBTree_Next_unprotected(
- const RBTree_Control *rbtree,
const RBTree_Node *node,
RBTree_Direction dir
);
@@ -326,7 +324,6 @@ RBTree_Node *_RBTree_Next_unprotected(
* The function disables the interrupts protect the operation.
*/
RBTree_Node *_RBTree_Next(
- const RBTree_Control *rbtree,
const RBTree_Node *node,
RBTree_Direction dir
);
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index a079745..c5187a0 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -384,11 +384,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
* @retval otherwise The predecessor node.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
- const RBTree_Control *rbtree,
const RBTree_Node *node
)
{
- return _RBTree_Next_unprotected( rbtree, node, RBT_LEFT );
+ return _RBTree_Next_unprotected( node, RBT_LEFT );
}
/**
@@ -397,11 +396,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
* The function disables the interrupts protect the operation.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
- const RBTree_Control *rbtree,
const RBTree_Node *node
)
{
- return _RBTree_Next( rbtree, node, RBT_LEFT );
+ return _RBTree_Next( node, RBT_LEFT );
}
/**
@@ -414,11 +412,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
* @retval otherwise The successor node.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
- const RBTree_Control *rbtree,
const RBTree_Node *node
)
{
- return _RBTree_Next_unprotected( rbtree, node, RBT_RIGHT );
+ return _RBTree_Next_unprotected( node, RBT_RIGHT );
}
/**
@@ -427,11 +424,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
* The function disables the interrupts protect the operation.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
- const RBTree_Control *rbtree,
const RBTree_Node *node
)
{
- return _RBTree_Next( rbtree, node, RBT_RIGHT );
+ return _RBTree_Next( node, RBT_RIGHT );
}
/** @brief Get the First Node (unprotected)
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 9a0a18b..e3b27fc 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -109,7 +109,7 @@ void _RBTree_Extract_unprotected(
/* check if min needs to be updated */
if (the_node == the_rbtree->first[RBT_LEFT]) {
RBTree_Node *next;
- next = _RBTree_Successor_unprotected(the_rbtree, the_node);
+ next = _RBTree_Successor_unprotected(the_node);
the_rbtree->first[RBT_LEFT] = next;
}
@@ -117,7 +117,7 @@ void _RBTree_Extract_unprotected(
* do not use else if here. */
if (the_node == the_rbtree->first[RBT_RIGHT]) {
RBTree_Node *previous;
- previous = _RBTree_Predecessor_unprotected(the_rbtree, the_node);
+ previous = _RBTree_Predecessor_unprotected(the_node);
the_rbtree->first[RBT_RIGHT] = previous;
}
diff --git a/cpukit/score/src/rbtreeiterate.c b/cpukit/score/src/rbtreeiterate.c
index 33f7e7d..f6de82b 100644
--- a/cpukit/score/src/rbtreeiterate.c
+++ b/cpukit/score/src/rbtreeiterate.c
@@ -40,6 +40,6 @@ void _RBTree_Iterate_unprotected(
while ( !stop && current != NULL ) {
stop = (*visitor)( current, dir, visitor_arg );
- current = _RBTree_Next_unprotected( rbtree, current, dir );
+ current = _RBTree_Next_unprotected( current, dir );
}
}
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
index e79f175..0aee043 100644
--- a/cpukit/score/src/rbtreenext.c
+++ b/cpukit/score/src/rbtreenext.c
@@ -28,7 +28,6 @@
#include <rtems/score/isr.h>
RBTree_Node *_RBTree_Next_unprotected(
- const RBTree_Control *rbtree,
const RBTree_Node *node,
RBTree_Direction dir
)
@@ -43,18 +42,17 @@ RBTree_Node *_RBTree_Next_unprotected(
next = current;
}
} else {
- const RBTree_Node *null = (const RBTree_Node *) rbtree;
RBTree_Node *parent = node->parent;
- if ( parent != null && node == parent->child [opp_dir] ) {
+ if ( parent->parent && node == parent->child [opp_dir] ) {
next = parent;
} else {
- while ( parent != null && node == parent->child [dir] ) {
+ while ( parent->parent && node == parent->child [dir] ) {
node = parent;
- parent = node->parent;
+ parent = parent->parent;
}
- if ( parent != null ) {
+ if ( parent->parent ) {
next = parent;
}
}
@@ -64,7 +62,6 @@ RBTree_Node *_RBTree_Next_unprotected(
}
RBTree_Node *_RBTree_Next(
- const RBTree_Control *rbtree,
const RBTree_Node *node,
RBTree_Direction dir
)
@@ -73,7 +70,7 @@ RBTree_Node *_RBTree_Next(
ISR_Level level;
_ISR_Disable( level );
- next = _RBTree_Next_unprotected( rbtree, node, dir );
+ next = _RBTree_Next_unprotected( node, dir );
_ISR_Enable( level );
return next;
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 7d0d3f6..76035f0 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -439,13 +439,13 @@ rtems_task Init(
}
puts( "INIT - Verify rtems_rbtree_predecessor/successor");
- p = rtems_rbtree_predecessor(&rbtree1, p);
+ p = rtems_rbtree_predecessor(p);
if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 29) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
}
p = rtems_rbtree_find(&rbtree1, &search_node.Node);
- p = rtems_rbtree_successor(&rbtree1, p);
+ p = rtems_rbtree_successor(p);
if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
More information about the vc
mailing list