From f53aa8d3026eb97e3c67e44a1c931442dbc95010 Mon Sep 17 00:00:00 2001 From: Gedare Bloom Date: Thu, 3 May 2012 12:43:29 -0400 Subject: 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 804cf382ca..dc53fa0381 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 7facf4f9af..5233778171 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 d98392e872..b3cfc45fa3 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 a079745290..c5187a02ae 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 9a0a18bea8..e3b27fc430 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 33f7e7d454..f6de82b576 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 e79f175f35..0aee0434f6 100644 --- a/cpukit/score/src/rbtreenext.c +++ b/cpukit/score/src/rbtreenext.c @@ -28,7 +28,6 @@ #include 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 7d0d3f60c7..76035f0bf4 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); -- cgit v1.2.3