[PATCH] rbtree: API changes. Replace is_unique with is_stable.

Gedare Bloom gedare at rtems.org
Fri May 4 16:29:59 UTC 2012


I'm starting to reconsider eliminating the "unique" option. I think it
might be useful to enforce uniqueness as an option and also stability
as an option. I'm leaning toward introducing an attribute field to the
red-black tree control node that can encode uniqueness and stability
at the minimum. There may be other attributes of a red-black tree that
may be worth considering as options also.

-Gedare

On Wed, May 2, 2012 at 5:00 PM, Gedare Bloom <gedare at rtems.org> 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
>




More information about the devel mailing list