[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