[PATCH] rbtree: API changes. Replace is_unique with is_stable.
Joel Sherrill
joel.sherrill at OARcorp.com
Wed May 2 21:20:55 UTC 2012
Did the changing of "is_unique" to "is_stable" impact any
doxygen comments? I didn't see a change to a lot of
comments and was curious.
Otherwise, it is OK. Apply
On 05/02/2012 04:00 PM, Gedare Bloom wrote:
> This patch changes the red-black tree to always allow duplicate keys. We still
> need to determine if a tree sorts the duplicate nodes in a stable order
> (ensuring FIFO ordering for find operations). So the is_unique field has been
> replaced with is_stable which is symmetrically the opposite of is_unique:
> if is_unique was true (false) then is_stable should be false (true).
> Maintaining stability in a red-black tree imposes extra costs when searching
> so if stability is not required slightly better performance can be obtained.
> ---
> cpukit/sapi/inline/rtems/rbtree.inl | 14 ++--
> cpukit/sapi/src/rbheap.c | 2 +-
> cpukit/score/include/rtems/score/rbtree.h | 8 +-
> cpukit/score/inline/rtems/score/rbtree.inl | 12 ++--
> cpukit/score/src/rbtree.c | 4 +-
> cpukit/score/src/rbtreeinsert.c | 2 -
> cpukit/score/src/scheduleredf.c | 2 +-
> testsuites/sptests/sprbtree01/init.c | 102 +++++++++++++---------------
> 8 files changed, 67 insertions(+), 79 deletions(-)
>
> diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
> index 804cf38..43d411f 100644
> --- a/cpukit/sapi/inline/rtems/rbtree.inl
> +++ b/cpukit/sapi/inline/rtems/rbtree.inl
> @@ -37,11 +37,11 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
> void *starting_address,
> size_t number_nodes,
> size_t node_size,
> - bool is_unique
> + bool is_stable
> )
> {
> _RBTree_Initialize( the_rbtree, compare_function, starting_address,
> - number_nodes, node_size, is_unique);
> + number_nodes, node_size, is_stable);
> }
>
> /**
> @@ -52,10 +52,10 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
> RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
> rtems_rbtree_control *the_rbtree,
> rtems_rbtree_compare_function compare_function,
> - bool is_unique
> + bool is_stable
> )
> {
> - _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
> + _RBTree_Initialize_empty( the_rbtree, compare_function, is_stable );
> }
>
> /**
> @@ -486,13 +486,13 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
> return _RBTree_Insert( the_rbtree, the_node );
> }
>
> -/** @brief Determines whether the tree is unique
> +/** @brief Determines whether the tree sorts node in stable (FIFO) order.
> */
> -RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
> +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_stable(
> const rtems_rbtree_control *the_rbtree
> )
> {
> - return _RBTree_Is_unique(the_rbtree);
> + return _RBTree_Is_stable(the_rbtree);
> }
>
> #endif
> diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
> index 7facf4f..b7faffd 100644
> --- a/cpukit/sapi/src/rbheap.c
> +++ b/cpukit/sapi/src/rbheap.c
> @@ -107,7 +107,7 @@ rtems_status_code rtems_rbheap_initialize(
>
> rtems_chain_initialize_empty(free_chain);
> rtems_chain_initialize_empty(&control->spare_descriptor_chain);
> - rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
> + rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, false);
> control->alignment = alignment;
> control->handler_arg = handler_arg;
> control->extend_descriptors = extend_descriptors;
> diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
> index d98392e..9273e5c 100644
> --- a/cpukit/score/include/rtems/score/rbtree.h
> +++ b/cpukit/score/include/rtems/score/rbtree.h
> @@ -145,8 +145,8 @@ typedef struct {
> * has higher key than second, -1 if lower, 0 if equal.
> */
> RBTree_Compare_function compare_function;
> - /** Determines whether the tree accepts duplicate keys. */
> - bool is_unique;
> + /** True if the tree keeps nodes with duplicate keys in FIFO order. */
> + bool is_stable;
> } RBTree_Control;
>
> /**
> @@ -159,7 +159,7 @@ typedef struct {
> .first[0] = NULL, \
> .first[1] = NULL, \
> .compare_function = NULL, \
> - .is_unique = 0 \
> + .is_stable = false \
> }
>
> /**
> @@ -198,7 +198,7 @@ void _RBTree_Initialize(
> void *starting_address,
> size_t number_nodes,
> size_t node_size,
> - bool is_unique
> + bool is_stable
> );
>
> /**
> diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
> index a079745..ef3d1fe 100644
> --- a/cpukit/score/inline/rtems/score/rbtree.inl
> +++ b/cpukit/score/inline/rtems/score/rbtree.inl
> @@ -245,7 +245,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
> RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
> RBTree_Control *the_rbtree,
> RBTree_Compare_function compare_function,
> - bool is_unique
> + bool is_stable
> )
> {
> the_rbtree->permanent_null = NULL;
> @@ -253,7 +253,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
> the_rbtree->first[0] = NULL;
> the_rbtree->first[1] = NULL;
> the_rbtree->compare_function = compare_function;
> - the_rbtree->is_unique = is_unique;
> + the_rbtree->is_stable = is_stable;
> }
>
> /** @brief Return a pointer to node's grandparent
> @@ -362,7 +362,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
> compare_result = the_rbtree->compare_function(the_node, iter_node);
> if ( _RBTree_Is_equal( compare_result ) ) {
> found = iter_node;
> - if ( the_rbtree->is_unique )
> + if ( !the_rbtree->is_stable )
> break;
> }
>
> @@ -485,13 +485,13 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
> the_node->parent = c;
> }
>
> -/** @brief Determines whether the tree is unique
> +/** @brief True if @a the_rbtree stores duplicates in stable (FIFO) order.
> */
> -RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
> +RTEMS_INLINE_ROUTINE bool _RBTree_Is_stable(
> const RBTree_Control *the_rbtree
> )
> {
> - return( the_rbtree&& the_rbtree->is_unique );
> + return( the_rbtree&& the_rbtree->is_stable );
> }
> /**@}*/
>
> diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
> index 387e66b..005a00e 100644
> --- a/cpukit/score/src/rbtree.c
> +++ b/cpukit/score/src/rbtree.c
> @@ -37,7 +37,7 @@ void _RBTree_Initialize(
> void *starting_address,
> size_t number_nodes,
> size_t node_size,
> - bool is_unique
> + bool is_stable
> )
> {
> size_t count;
> @@ -47,7 +47,7 @@ void _RBTree_Initialize(
> if (!the_rbtree) return;
>
> /* could do sanity checks here */
> - _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
> + _RBTree_Initialize_empty(the_rbtree, compare_function, is_stable);
>
> count = number_nodes;
> next = starting_address;
> diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
> index d2d5442..74f8a33 100644
> --- a/cpukit/score/src/rbtreeinsert.c
> +++ b/cpukit/score/src/rbtreeinsert.c
> @@ -97,8 +97,6 @@ RBTree_Node *_RBTree_Insert_unprotected(
> /* typical binary search tree insert, descend tree to leaf and insert */
> while (iter_node) {
> compare_result = the_rbtree->compare_function(the_node, iter_node);
> - if ( the_rbtree->is_unique&& _RBTree_Is_equal( compare_result ) )
> - return iter_node;
> RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
> if (!iter_node->child[dir]) {
> the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
> diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c
> index 0407122..9e1752a 100644
> --- a/cpukit/score/src/scheduleredf.c
> +++ b/cpukit/score/src/scheduleredf.c
> @@ -41,7 +41,7 @@ void _Scheduler_EDF_Initialize(void)
> _RBTree_Initialize_empty(
> &_Scheduler_EDF_Ready_queue,
> &_Scheduler_EDF_RBTree_compare_function,
> - 0
> + true
> );
> }
>
> diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
> index 7d0d3f6..1424eef 100644
> --- a/testsuites/sptests/sprbtree01/init.c
> +++ b/testsuites/sptests/sprbtree01/init.c
> @@ -4,8 +4,6 @@
> * 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.
> - *
> - * $Id$
> */
>
> #ifdef HAVE_CONFIG_H
> @@ -15,6 +13,17 @@
> #include<tmacros.h>
> #include<rtems/rbtree.h>
>
> +/* configuration information */
> +#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
> +#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
> +
> +#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
> +#define CONFIGURE_MAXIMUM_TASKS 1
> +
> +#define CONFIGURE_INIT
> +#include<rtems/confdefs.h>
> +
> +/* global variables */
> int numbers[20] = {
> 52, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71};
>
> @@ -85,8 +94,6 @@ static int rb_assert ( rtems_rbtree_node *root )
> }
> }
>
> -
> -
> rtems_task Init(
> rtems_task_argument ignored
> )
> @@ -102,12 +109,12 @@ rtems_task Init(
> puts( "\n\n*** TEST OF RTEMS RBTREE API ***" );
>
> puts( "Init - Initialize rbtree empty" );
> - rtems_rbtree_initialize_empty(&rbtree1,&test_compare_function, true );
> + rtems_rbtree_initialize_empty(&rbtree1,&test_compare_function, false );
>
> - if ( !rtems_rbtree_is_unique(&rbtree1 ) )
> - puts( "INIT - FAILED IS UNIQUE CHECK" );
> - if ( rtems_rbtree_is_unique( NULL ) )
> - puts( "INIT - FAILED IS UNIQUE CHECK" );
> + if ( rtems_rbtree_is_stable(&rbtree1 ) )
> + puts( "INIT - FAILED IS STABLE CHECK" );
> + if ( rtems_rbtree_is_stable( NULL ) )
> + puts( "INIT - FAILED IS STABLE CHECK" );
>
> /* verify that the rbtree insert work */
> puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
> @@ -153,35 +160,6 @@ rtems_task Init(
> rtems_test_exit(0);
> }
>
> - puts("INIT - Verify rtems_rbtree_insert with the same value twice");
> - node2.key = node1.key;
> - rtems_rbtree_insert(&rbtree1,&node1.Node);
> - p = rtems_rbtree_insert(&rbtree1,&node2.Node);
> -
> - if (p !=&node1.Node)
> - puts( "INIT - FAILED DUPLICATE INSERT" );
> -
> - for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
> - p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
> - test_node *t = rtems_rbtree_container_of(p,test_node,Node);
> - if ( id> 1 ) {
> - puts( "INIT - TOO MANY NODES ON RBTREE" );
> - rtems_test_exit(0);
> - }
> - if ( t->id != id ) {
> - puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
> - rtems_test_exit(0);
> - }
> -
> - if (!rb_assert(rbtree1.root) )
> - puts( "INIT - FAILED TREE CHECK" );
> - }
> - if (id< 1) {
> - puts("INIT - NOT ENOUGH NODES ON RBTREE");
> - rtems_test_exit(0);
> - }
> - node2.key = 2;
> -
> /* verify that the rbtree is empty */
> puts( "INIT - Verify rtems_rbtree_is_empty" );
> if(!rtems_rbtree_is_empty(&rbtree1)) {
> @@ -569,12 +547,37 @@ rtems_task Init(
>
> /* Initialize the tree for duplicate keys */
> puts( "Init - Initialize duplicate rbtree empty" );
> - rtems_rbtree_initialize_empty(&rbtree1,&test_compare_function, false );
> + rtems_rbtree_initialize_empty(&rbtree1,&test_compare_function, true );
>
> - if ( rtems_rbtree_is_unique(&rbtree1 ) )
> - puts( "INIT - FAILED IS UNIQUE CHECK" );
> - if ( rtems_rbtree_is_unique( NULL ) )
> - puts( "INIT - FAILED IS UNIQUE CHECK" );
> + if ( !rtems_rbtree_is_stable(&rbtree1 ) )
> + puts( "INIT - FAILED IS STABLE CHECK" );
> +
> + puts ( "INIT - Verify stable duplicates" );
> + for (i = 0; i< 10; i++) {
> + node_array[i].id = i;
> + }
> + node_array[0].key = 3;
> + node_array[1].key = 3;
> + node_array[2].key = 3;
> + node_array[3].key = 3;
> + node_array[4].key = 3;
> + node_array[5].key = 1;
> + node_array[6].key = 2;
> + for (i = 0; i< 7; i++) {
> + rtems_rbtree_insert(&rbtree1,&node_array[i].Node );
> +
> + if (!rb_assert(rbtree1.root) )
> + puts( "INIT - FAILED TREE CHECK" );
> + }
> + search_node.key = 3;
> + p = rtems_rbtree_find(&rbtree1,&search_node.Node);
> + if(rtems_rbtree_container_of(p,test_node,Node)->id != 0) {
> + puts ("INIT - ERROR ON RBTREE ID MISMATCH");
> + rtems_test_exit(0);
> + }
> +
> + for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
> + p = rtems_rbtree_get_min(&rbtree1) , id++ );
>
> puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
> for (i = 0; i< 100; i++) {
> @@ -661,16 +664,3 @@ rtems_task Init(
> puts( "*** END OF RTEMS RBTREE API TEST ***" );
> rtems_test_exit(0);
> }
> -
> -/* configuration information */
> -
> -#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
> -#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
> -
> -#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
> -#define CONFIGURE_MAXIMUM_TASKS 1
> -
> -#define CONFIGURE_INIT
> -#include<rtems/confdefs.h>
> -
> -/* global variables */
> --
> 1.7.1
>
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
--
Joel Sherrill, Ph.D. Director of Research& Development
joel.sherrill at OARcorp.com On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985
More information about the devel
mailing list