From dc62a48cc5fc95f9bbe7ab2ed2712b70987bde6f Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Tue, 10 Apr 2012 10:25:14 +0200 Subject: rbtree: PR1995: API change New functions o _RBTree_Next_unprotected(), o _RBTree_Next(), o _RBTree_Successor_unprotected(), o _RBTree_Predecessor_unprotected(), o rtems_rbtree_successor_unprotected(), and o rtems_rbtree_predecessor_unprotected(). Change prototype of o _RBTree_Successor(), o _RBTree_Predecessor(), o rtems_rbtree_successor(), and o rtems_rbtree_predecessor(). --- cpukit/sapi/inline/rtems/rbtree.inl | 44 +++++++++++----- cpukit/score/Makefile.am | 2 +- cpukit/score/include/rtems/score/rbtree.h | 27 ++++++++++ cpukit/score/inline/rtems/score/rbtree.inl | 74 +++++++++++++++++---------- cpukit/score/src/rbtreenext.c | 80 ++++++++++++++++++++++++++++++ testsuites/sptests/sprbtree01/init.c | 4 +- 6 files changed, 190 insertions(+), 41 deletions(-) create mode 100644 cpukit/score/src/rbtreenext.c diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl index 259a586fd1..1a2e99e30b 100644 --- a/cpukit/sapi/inline/rtems/rbtree.inl +++ b/cpukit/sapi/inline/rtems/rbtree.inl @@ -271,28 +271,48 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( return _RBTree_Find( the_rbtree, the_node ); } -/** @brief Find the node's in-order predecessor - * - * This function returns a pointer to the in-order predecessor - * of @a the_node if it exists, and NULL if not. +/** + * @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 ); +} + +/** + * @copydoc _RBTree_Predecessor() */ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor( - rtems_rbtree_node *the_node + const rtems_rbtree_control *rbtree, + const rtems_rbtree_node *node ) { - return _RBTree_Predecessor( the_node ); + return _RBTree_Predecessor( rbtree, node ); } -/** @brief Find the node's in-order successor - * - * This function returns a pointer to the in-order successor - * of @a the_node if it exists, and NULL if not. +/** + * @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 ); +} + +/** + * @copydoc _RBTree_Successor() */ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor( - rtems_rbtree_node *the_node + const rtems_rbtree_control *rbtree, + const rtems_rbtree_node *node ) { - return _RBTree_Successor( the_node ); + return _RBTree_Successor( rbtree, node ); } /** diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 597da3e0cc..1c896e3016 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -265,7 +265,7 @@ libscore_a_SOURCES += src/pheapallocate.c \ ## RBTREE_C_FILES libscore_a_SOURCES += src/rbtree.c \ src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \ - src/rbtreeget.c src/rbtreeinsert.c src/rbtreepeek.c + src/rbtreeget.c src/rbtreeinsert.c src/rbtreepeek.c src/rbtreenext.c ## THREAD_C_FILES libscore_a_SOURCES += src/thread.c src/threadchangepriority.c \ diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index 03e879213d..b2e5776b61 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -321,6 +321,33 @@ void _RBTree_Extract( RBTree_Node *the_node ); +/** + * @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. + * + * @retval NULL The in-order next node does not exist. + * @retval otherwise The next node. + */ +RBTree_Node *_RBTree_Next_unprotected( + const RBTree_Control *rbtree, + const RBTree_Node *node, + RBTree_Direction dir +); + +/** + * @copydoc _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 +); + #ifndef __RTEMS_APPLICATION__ #include #endif diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl index 2ce0b2bbdb..d646b067b8 100644 --- a/cpukit/score/inline/rtems/score/rbtree.inl +++ b/cpukit/score/inline/rtems/score/rbtree.inl @@ -376,42 +376,64 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( return found; } -/** @brief Find the nodes in-order predecessor +/** + * @brief Returns the predecessor of a node. + * + * @param[in] rbtree The red-black tree. + * @param[in] node The node. + * + * @retval NULL The predecessor does not exist. + * @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 ); +} + +/** + * @copydoc _RBTree_Predecessor_unprotected() * - * This function returns a pointer to the in-order predecessor - * of @a the_node if it exists, and NULL if not. + * The function disables the interrupts protect the operation. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( - RBTree_Node *the_node - ) + const RBTree_Control *rbtree, + const RBTree_Node *node +) { - RBTree_Node* iter_node; - if (!the_node) return NULL; - iter_node = the_node->child[RBT_LEFT]; - if (!iter_node) return NULL; - while (iter_node->child[RBT_RIGHT]) { - iter_node = iter_node->child[RBT_RIGHT]; - } - return iter_node; + return _RBTree_Next( rbtree, node, RBT_LEFT ); } -/** @brief Find the nodes in-order successor +/** + * @brief Returns the successor of a node. + * + * @param[in] rbtree The red-black tree. + * @param[in] node The node. + * + * @retval NULL The successor does not exist. + * @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 ); +} + +/** + * @copydoc _RBTree_Successor_unprotected() * - * This function returns a pointer to the in-order successor - * of @a the_node if it exists, and NULL if not. + * The function disables the interrupts protect the operation. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( - RBTree_Node *the_node - ) + const RBTree_Control *rbtree, + const RBTree_Node *node +) { - RBTree_Node* iter_node; - if (!the_node) return NULL; - iter_node = the_node->child[RBT_RIGHT]; - if (!iter_node) return NULL; - while (iter_node->child[RBT_LEFT]) { - iter_node = iter_node->child[RBT_LEFT]; - } - return iter_node; + return _RBTree_Next( rbtree, node, RBT_RIGHT ); } /** @brief Get the First Node (unprotected) diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c new file mode 100644 index 0000000000..e79f175f35 --- /dev/null +++ b/cpukit/score/src/rbtreenext.c @@ -0,0 +1,80 @@ +/** + * @file + * + * @ingroup ScoreRBTree + * + * @brief _RBTree_Next_unprotected() and _RBTree_Next() implementation. + */ + +/* + * Copyright (c) 2012 embedded brains GmbH. All rights reserved. + * + * embedded brains GmbH + * Obere Lagerstr. 30 + * 82178 Puchheim + * Germany + * + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.com/license/LICENSE. + */ + +#if HAVE_CONFIG_H + #include "config.h" +#endif + +#include +#include + +RBTree_Node *_RBTree_Next_unprotected( + const RBTree_Control *rbtree, + const RBTree_Node *node, + RBTree_Direction dir +) +{ + RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); + RBTree_Node *current = node->child [dir]; + RBTree_Node *next = NULL; + + if ( current != NULL ) { + next = current; + while ( (current = current->child [opp_dir]) != NULL ) { + next = current; + } + } else { + const RBTree_Node *null = (const RBTree_Node *) rbtree; + RBTree_Node *parent = node->parent; + + if ( parent != null && node == parent->child [opp_dir] ) { + next = parent; + } else { + while ( parent != null && node == parent->child [dir] ) { + node = parent; + parent = node->parent; + } + + if ( parent != null ) { + next = parent; + } + } + } + + return next; +} + +RBTree_Node *_RBTree_Next( + const RBTree_Control *rbtree, + const RBTree_Node *node, + RBTree_Direction dir +) +{ + RBTree_Node *next; + ISR_Level level; + + _ISR_Disable( level ); + next = _RBTree_Next_unprotected( rbtree, node, dir ); + _ISR_Enable( level ); + + return next; +} diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index 754876d5fa..f3f9c291af 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -440,13 +440,13 @@ rtems_task Init( } puts( "INIT - Verify rtems_rbtree_predecessor/successor"); - p = rtems_rbtree_predecessor(p); + p = rtems_rbtree_predecessor(&rbtree1, 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(p); + p = rtems_rbtree_successor(&rbtree1, 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