[PATCH] rbtree: API changes. Replace is_unique with is_stable.
Gedare Bloom
gedare at rtems.org
Thu May 3 17:10:17 UTC 2012
The red-black tree documentation is lagging. I will attempt to fix it.
Probably I (or someone) needs to do a thorough documentation of it,
but right now I'm reviewing the entire implementation to clean-up the
API before it gets "published".
The change to allow duplicates all the time makes the return values
from Insert odd. I'm going to re-examine those given that duplicate
keys are always allowed now.
-Gedare
On Wed, May 2, 2012 at 5:20 PM, Joel Sherrill <joel.sherrill at oarcorp.com> wrote:
> 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