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

Gedare Bloom gedare at rtems.org
Wed May 2 21:00:01 UTC 2012


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