[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