From 69a6802bfa8878d3e9a8296c1516ff5feac77bbc Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 17 Jun 2016 07:50:01 +0200 Subject: score: Move _RBTree_Find() The _RBTree_Find() is no longer used in the score. Move it to sapi and make it rtems_rbtree_find(). Move corresponding types and support functions to sapi. --- cpukit/sapi/Makefile.am | 1 + cpukit/sapi/include/rtems/rbtree.h | 72 ++++++++++++++++++++++----- cpukit/sapi/src/rbtreefind.c | 51 +++++++++++++++++++ cpukit/sapi/src/rbtreeinsert.c | 16 +++--- cpukit/score/Makefile.am | 2 +- cpukit/score/include/rtems/score/rbtree.h | 48 ------------------ cpukit/score/include/rtems/score/rbtreeimpl.h | 21 -------- cpukit/score/src/rbtreefind.c | 50 ------------------- 8 files changed, 120 insertions(+), 141 deletions(-) create mode 100644 cpukit/sapi/src/rbtreefind.c delete mode 100644 cpukit/score/src/rbtreefind.c (limited to 'cpukit') diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am index 58d2ce509d..4e85062bb8 100644 --- a/cpukit/sapi/Makefile.am +++ b/cpukit/sapi/Makefile.am @@ -40,6 +40,7 @@ libsapi_a_SOURCES += src/cpucounterconverter.c libsapi_a_SOURCES += src/delayticks.c libsapi_a_SOURCES += src/delaynano.c libsapi_a_SOURCES += src/rbtree.c +libsapi_a_SOURCES += src/rbtreefind.c libsapi_a_SOURCES += src/rbtreeinsert.c libsapi_a_SOURCES += src/profilingiterate.c libsapi_a_SOURCES += src/profilingreportxml.c diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h index 2b43eaaae1..57821cf31d 100644 --- a/cpukit/sapi/include/rtems/rbtree.h +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -55,14 +55,31 @@ typedef RBTree_Node rtems_rbtree_node; typedef RBTree_Control rtems_rbtree_control; /** - * @copydoc RBTree_Compare_result + * @brief Integer type for compare results. + * + * The type is large enough to represent pointers and 32-bit signed integers. + * + * @see rtems_rbtree_compare. */ -typedef RBTree_Compare_result rtems_rbtree_compare_result; +typedef long rtems_rbtree_compare_result; /** - * @copydoc RBTree_Compare - */ -typedef RBTree_Compare rtems_rbtree_compare; + * @brief Compares two red-black tree nodes. + * + * @param[in] first The first node. + * @param[in] second The second node. + * + * @retval positive The key value of the first node is greater than the one of + * the second node. + * @retval 0 The key value of the first node is equal to the one of the second + * node. + * @retval negative The key value of the first node is less than the one of the + * second node. + */ +typedef rtems_rbtree_compare_result ( *rtems_rbtree_compare )( + const RBTree_Node *first, + const RBTree_Node *second +); /** * @brief RBTree initializer for an empty rbtree with designator @a name. @@ -255,18 +272,47 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( return _RBTree_Is_root( the_node ); } +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_equal( + rtems_rbtree_compare_result compare_result +) +{ + return compare_result == 0; +} + +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_greater( + rtems_rbtree_compare_result compare_result +) +{ + return compare_result > 0; +} + +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_lesser( + rtems_rbtree_compare_result compare_result +) +{ + return compare_result < 0; +} + /** - * @copydoc _RBTree_Find() + * @brief Tries to find a node for the specified key in the tree. + * + * @param[in] the_rbtree The red-black tree control. + * @param[in] the_node A node specifying the key. + * @param[in] compare The node compare function. + * @param[in] is_unique If true, then return the first node with a key equal to + * the one of the node specified if it exits, else return the last node if it + * exists. + * + * @retval node A node corresponding to the key. If the tree is not unique + * and contains duplicate keys, the set of duplicate keys acts as FIFO. + * @retval NULL No node exists in the tree for the key. */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( +rtems_rbtree_node* rtems_rbtree_find( const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node, - rtems_rbtree_compare compare, + rtems_rbtree_compare compare, bool is_unique -) -{ - return _RBTree_Find( the_rbtree, the_node, compare, is_unique ); -} +); /** * @copydoc _RBTree_Predecessor() @@ -396,7 +442,7 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max( rtems_rbtree_node *rtems_rbtree_insert( RBTree_Control *the_rbtree, RBTree_Node *the_node, - RBTree_Compare compare, + rtems_rbtree_compare compare, bool is_unique ); diff --git a/cpukit/sapi/src/rbtreefind.c b/cpukit/sapi/src/rbtreefind.c new file mode 100644 index 0000000000..d3f67a6462 --- /dev/null +++ b/cpukit/sapi/src/rbtreefind.c @@ -0,0 +1,51 @@ +/** + * @file + * + * @brief Find the control structure of the tree containing the given node + * @ingroup Scorertems_rbtree + */ + +/* + * Copyright (c) 2010 Gedare Bloom. + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.org/license/LICENSE. + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include + +rtems_rbtree_node *rtems_rbtree_find( + const rtems_rbtree_control *the_rbtree, + const rtems_rbtree_node *the_node, + rtems_rbtree_compare compare, + bool is_unique +) +{ + rtems_rbtree_node *iter_node = rtems_rbtree_root( the_rbtree ); + rtems_rbtree_node *found = NULL; + + while ( iter_node != NULL ) { + rtems_rbtree_compare_result compare_result = + ( *compare )( the_node, iter_node ); + + if ( rtems_rbtree_is_equal( compare_result ) ) { + found = iter_node; + + if ( is_unique ) + break; + } + + if ( rtems_rbtree_is_greater( compare_result ) ) { + iter_node = rtems_rbtree_right( iter_node ); + } else { + iter_node = rtems_rbtree_left( iter_node ); + } + } + + return found; +} diff --git a/cpukit/sapi/src/rbtreeinsert.c b/cpukit/sapi/src/rbtreeinsert.c index a4850ff4cf..38b2f5b4ca 100644 --- a/cpukit/sapi/src/rbtreeinsert.c +++ b/cpukit/sapi/src/rbtreeinsert.c @@ -14,19 +14,19 @@ #include RTEMS_STATIC_ASSERT( - sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ), - RBTree_Compare_result_intptr_t + sizeof( rtems_rbtree_compare_result ) >= sizeof( intptr_t ), + rtems_rbtree_compare_result_intptr_t ); RTEMS_STATIC_ASSERT( - sizeof( RBTree_Compare_result ) >= sizeof( int32_t ), - RBTree_Compare_result_int32_t + sizeof( rtems_rbtree_compare_result ) >= sizeof( int32_t ), + rtems_rbtree_compare_result_int32_t ); rtems_rbtree_node *rtems_rbtree_insert( rtems_rbtree_control *the_rbtree, rtems_rbtree_node *the_node, - RBTree_Compare compare, + rtems_rbtree_compare compare, bool is_unique ) { @@ -34,16 +34,16 @@ rtems_rbtree_node *rtems_rbtree_insert( rtems_rbtree_node *parent = NULL; while ( *which != NULL ) { - RBTree_Compare_result compare_result; + rtems_rbtree_compare_result compare_result; parent = *which; compare_result = ( *compare )( the_node, parent ); - if ( is_unique && _RBTree_Is_equal( compare_result ) ) { + if ( is_unique && rtems_rbtree_is_equal( compare_result ) ) { return parent; } - if ( _RBTree_Is_lesser( compare_result ) ) { + if ( rtems_rbtree_is_lesser( compare_result ) ) { which = _RBTree_Left_reference( parent ); } else { which = _RBTree_Right_reference( parent ); diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 97f0b3d615..a58aedcc09 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -292,7 +292,7 @@ libscore_a_SOURCES += src/freechain.c ## RBTREE_C_FILES libscore_a_SOURCES += \ - src/rbtreeextract.c src/rbtreefind.c \ + src/rbtreeextract.c \ src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c libscore_a_SOURCES += src/rbtreereplace.c diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index f0590c0904..e7e65f7b91 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -56,33 +56,6 @@ typedef struct RBTree_Node { */ typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control; -/** - * @brief Integer type for compare results. - * - * The type is large enough to represent pointers and 32-bit signed integers. - * - * @see RBTree_Compare. - */ -typedef long RBTree_Compare_result; - -/** - * @brief Compares two red-black tree nodes. - * - * @param[in] first The first node. - * @param[in] second The second node. - * - * @retval positive The key value of the first node is greater than the one of - * the second node. - * @retval 0 The key value of the first node is equal to the one of the second - * node. - * @retval negative The key value of the first node is less than the one of the - * second node. - */ -typedef RBTree_Compare_result ( *RBTree_Compare )( - const RBTree_Node *first, - const RBTree_Node *second -); - /** * @brief Initializer for an empty red-black tree with designator @a name. */ @@ -95,27 +68,6 @@ typedef RBTree_Compare_result ( *RBTree_Compare )( #define RBTREE_DEFINE_EMPTY( name ) \ RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name ) -/** - * @brief Tries to find a node for the specified key in the tree. - * - * @param[in] the_rbtree The red-black tree control. - * @param[in] the_node A node specifying the key. - * @param[in] compare The node compare function. - * @param[in] is_unique If true, then return the first node with a key equal to - * the one of the node specified if it exits, else return the last node if it - * exists. - * - * @retval node A node corresponding to the key. If the tree is not unique - * and contains duplicate keys, the set of duplicate keys acts as FIFO. - * @retval NULL No node exists in the tree for the key. - */ -RBTree_Node *_RBTree_Find( - const RBTree_Control *the_rbtree, - const RBTree_Node *the_node, - RBTree_Compare compare, - bool is_unique -); - /** * @brief Rebalances the red-black tree after insertion of the node. * diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h index 9c748eb01c..bf92e29228 100644 --- a/cpukit/score/include/rtems/score/rbtreeimpl.h +++ b/cpukit/score/include/rtems/score/rbtreeimpl.h @@ -62,27 +62,6 @@ void _RBTree_Iterate( void *visitor_arg ); -RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( - RBTree_Compare_result compare_result -) -{ - return compare_result == 0; -} - -RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater( - RBTree_Compare_result compare_result -) -{ - return compare_result > 0; -} - -RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser( - RBTree_Compare_result compare_result -) -{ - return compare_result < 0; -} - /** @} */ #ifdef __cplusplus diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c deleted file mode 100644 index f920febd41..0000000000 --- a/cpukit/score/src/rbtreefind.c +++ /dev/null @@ -1,50 +0,0 @@ -/** - * @file - * - * @brief Find the control structure of the tree containing the given node - * @ingroup ScoreRBTree - */ - -/* - * Copyright (c) 2010 Gedare Bloom. - * - * The license and distribution terms for this file may be - * found in the file LICENSE in this distribution or at - * http://www.rtems.org/license/LICENSE. - */ - -#if HAVE_CONFIG_H -#include "config.h" -#endif - -#include - -RBTree_Node *_RBTree_Find( - const RBTree_Control *the_rbtree, - const RBTree_Node *the_node, - RBTree_Compare compare, - bool is_unique -) -{ - RBTree_Node *iter_node = _RBTree_Root( the_rbtree ); - RBTree_Node *found = NULL; - - while ( iter_node != NULL ) { - RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node ); - - if ( _RBTree_Is_equal( compare_result ) ) { - found = iter_node; - - if ( is_unique ) - break; - } - - if ( _RBTree_Is_greater( compare_result ) ) { - iter_node = _RBTree_Right( iter_node ); - } else { - iter_node = _RBTree_Left( iter_node ); - } - } - - return found; -} -- cgit v1.2.3