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/score/inline/rtems/score/rbtree.inl | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) (limited to 'cpukit/score/inline/rtems/score') 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) -- cgit v1.2.3