Remove compare function and is unique indicator from the control
structure. Rename RBTree_Compare_function to RBTree_Compare. Rename
rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++
compatible initializers. Add compare function and is unique indicator
to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
rtems_rbtree_insert(). Remove _RBTree_Is_unique() and
rtems_rbtree_is_unique(). Remove compare function and is unique
indicator from _RBTree_Initialize_empty() and
rtems_rbtree_initialize_empty().
---
cpukit/posix/include/rtems/posix/keyimpl.h | 21 +++-
cpukit/posix/src/key.c | 10 +-
cpukit/posix/src/keyfreememory.c | 4 +-
cpukit/posix/src/keygetspecific.c | 13 +--
cpukit/posix/src/keysetspecific.c | 16 +--
cpukit/sapi/include/rtems/rbtree.h | 46 ++++-----
cpukit/sapi/src/rbheap.c | 8 +-
cpukit/score/include/rtems/score/rbtree.h | 111 ++++++++++-----------
.../score/include/rtems/score/scheduleredfimpl.h | 12 ++-
cpukit/score/src/rbtree.c | 19 ++--
cpukit/score/src/rbtreefind.c | 22 ++--
cpukit/score/src/rbtreeinsert.c | 32 ++----
cpukit/score/src/scheduleredf.c | 9 +-
cpukit/score/src/scheduleredfchangepriority.c | 7 +-
cpukit/score/src/scheduleredfyield.c | 7 +-
testsuites/sptests/sprbtree01/init.c | 102 +++++++++++--------
16 files changed, 226 insertions(+), 213 deletions(-)
diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h
b/cpukit/posix/include/rtems/posix/keyimpl.h
index 6aab244..b21c1d3 100644
--- a/cpukit/posix/include/rtems/posix/keyimpl.h
+++ b/cpukit/posix/include/rtems/posix/keyimpl.h
@@ -42,7 +42,7 @@ POSIX_EXTERN Objects_Information _POSIX_Keys_Information;
/**
* @brief The rbtree control block used to manage all key values
*/
-POSIX_EXTERN RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
+extern RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
/**
* @brief This freechain is used as a memory pool for
POSIX_Keys_Key_value_pair.
@@ -61,7 +61,7 @@ void _POSIX_Key_Manager_initialization(void);
*
* This routine compares the rbtree node
*/
-int _POSIX_Keys_Key_value_lookup_tree_compare_function(
+int _POSIX_Keys_Key_value_compare(
const RBTree_Node *node1,
const RBTree_Node *node2
);
@@ -165,6 +165,23 @@ RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_pair_free(
_Freechain_Put( &_POSIX_Keys_Keypool, key_value_pair );
}
+RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Find(
+ pthread_key_t key,
+ Objects_Id thread_id,
+ POSIX_Keys_Key_value_pair *search_node
+)
+{
+ search_node->key = key;
+ search_node->thread_id = thread_id;
+
+ return _RBTree_Find(
+ &_POSIX_Keys_Key_value_lookup_tree,
+ &search_node->Key_value_lookup_node,
+ _POSIX_Keys_Key_value_compare,
+ true
+ );
+}
+
/** @} */
#ifdef __cplusplus
diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
index de61b43..105706a 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -26,6 +26,8 @@
#include <rtems/score/objectimpl.h>
#include <rtems/score/wkspace.h>
+RBTREE_DEFINE_EMPTY( _POSIX_Keys_Key_value_lookup_tree );
+
/**
* @brief This routine compares the rbtree node by comparing POSIX key first
* and comparing thread id second.
@@ -42,7 +44,7 @@
* impossible
*/
-int _POSIX_Keys_Key_value_lookup_tree_compare_function(
+int _POSIX_Keys_Key_value_compare(
const RBTree_Node *node1,
const RBTree_Node *node2
)
@@ -153,11 +155,5 @@ void _POSIX_Key_Manager_initialization(void)
#endif
);
- _RBTree_Initialize_empty(
- &_POSIX_Keys_Key_value_lookup_tree,
- _POSIX_Keys_Key_value_lookup_tree_compare_function,
- true
- );
-
_POSIX_Keys_Initialize_keypool();
}
diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
index 04c914f..b419f1f 100644
--- a/cpukit/posix/src/keyfreememory.c
+++ b/cpukit/posix/src/keyfreememory.c
@@ -32,9 +32,7 @@ void _POSIX_Keys_Free_memory(
Objects_Id key_id;
key_id = the_key->Object.id;
- search_node.key = key_id;
- search_node.thread_id = 0;
- iter = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
&search_node.Key_value_lookup_node );
+ iter = _POSIX_Keys_Find( key_id, 0, &search_node );
if ( !iter )
return;
/**
diff --git a/cpukit/posix/src/keygetspecific.c
b/cpukit/posix/src/keygetspecific.c
index eeab2e3..9c54112 100644
--- a/cpukit/posix/src/keygetspecific.c
+++ b/cpukit/posix/src/keygetspecific.c
@@ -49,19 +49,14 @@ void *pthread_getspecific(
switch ( location ) {
case OBJECTS_LOCAL:
- search_node.key = key;
- search_node.thread_id = _Thread_Executing->Object.id;
- p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
- &search_node.Key_value_lookup_node );
- key_data = NULL;
- if ( p ) {
+ p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
+ if ( p != NULL ) {
value_pair_p = _RBTree_Container_of( p,
POSIX_Keys_Key_value_pair,
Key_value_lookup_node );
- /* key_data = _RBTree_Container_of( p, */
- /* POSIX_Keys_Key_value_pair, */
- /* Key_value_lookup_node )->value; */
key_data = value_pair_p->value;
+ } else {
+ key_data = NULL;
}
_Objects_Put( &the_key->Object );
diff --git a/cpukit/posix/src/keysetspecific.c
b/cpukit/posix/src/keysetspecific.c
index 3284991..0f7c682 100644
--- a/cpukit/posix/src/keysetspecific.c
+++ b/cpukit/posix/src/keysetspecific.c
@@ -44,12 +44,8 @@ int pthread_setspecific(
switch ( location ) {
case OBJECTS_LOCAL:
- search_node.key = key;
- search_node.thread_id = _Thread_Executing->Object.id;
- p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
- &search_node.Key_value_lookup_node );
-
- if ( p ) {
+ p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
+ if ( p != NULL ) {
value_pair_ptr = _RBTree_Container_of( p,
POSIX_Keys_Key_value_pair,
Key_value_lookup_node );
@@ -69,8 +65,12 @@ int pthread_setspecific(
value_pair_ptr->value = value;
/* The insert can only go wrong if the same node is already in a unique
* tree. This has been already checked with the _RBTree_Find() */
- (void) _RBTree_Insert( &_POSIX_Keys_Key_value_lookup_tree,
- &(value_pair_ptr->Key_value_lookup_node) );
+ _RBTree_Insert(
+ &_POSIX_Keys_Key_value_lookup_tree,
+ &value_pair_ptr->Key_value_lookup_node,
+ _POSIX_Keys_Key_value_compare,
+ true
+ );
/** append rb_node to the thread API extension's chain */
_Chain_Append_unprotected(
diff --git a/cpukit/sapi/include/rtems/rbtree.h
b/cpukit/sapi/include/rtems/rbtree.h
index 7e59e03..2005b36 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -55,13 +55,11 @@ typedef RBTree_Node rtems_rbtree_node;
typedef RBTree_Control rtems_rbtree_control;
/**
- * @typedef rtems_rbtree_compare_function
- *
* This type defines function pointers for user-provided comparison
* function. The function compares two nodes in order to determine
* the order in a red-black tree.
*/
-typedef RBTree_Compare_function rtems_rbtree_compare_function;
+typedef RBTree_Compare rtems_rbtree_compare;
/**
* @brief RBTree initializer for an empty rbtree with designator @a name.
@@ -93,15 +91,15 @@ typedef RBTree_Compare_function
rtems_rbtree_compare_function;
* @a starting_address. Each node is of @a node_size bytes.
*/
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
- rtems_rbtree_control *the_rbtree,
- rtems_rbtree_compare_function compare_function,
- void *starting_address,
- size_t number_nodes,
- size_t node_size,
- bool is_unique
+ rtems_rbtree_control *the_rbtree,
+ rtems_rbtree_compare compare,
+ void *starting_address,
+ size_t number_nodes,
+ size_t node_size,
+ bool is_unique
)
{
- _RBTree_Initialize( the_rbtree, compare_function, starting_address,
+ _RBTree_Initialize( the_rbtree, compare, starting_address,
number_nodes, node_size, is_unique);
}
@@ -111,12 +109,10 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
* This routine initializes @a the_rbtree to contain zero nodes.
*/
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
- rtems_rbtree_control *the_rbtree,
- rtems_rbtree_compare_function compare_function,
- bool is_unique
+ rtems_rbtree_control *the_rbtree
)
{
- _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
+ _RBTree_Initialize_empty( the_rbtree );
}
/**
@@ -277,10 +273,12 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
const rtems_rbtree_control *the_rbtree,
- const rtems_rbtree_node *the_node
+ const rtems_rbtree_node *the_node,
+ rtems_rbtree_compare compare,
+ bool is_unique
)
{
- return _RBTree_Find( the_rbtree, the_node );
+ return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
}
/**
@@ -385,20 +383,12 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control
*rtems_rbtree_find_header(
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
rtems_rbtree_control *the_rbtree,
- rtems_rbtree_node *the_node
-)
-{
- return _RBTree_Insert( the_rbtree, the_node );
-}
-
-/**
- * @brief Determines whether the tree is unique.
- */
-RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
- const rtems_rbtree_control *the_rbtree
+ rtems_rbtree_node *the_node,
+ rtems_rbtree_compare compare,
+ bool is_unique
)
{
- return _RBTree_Is_unique(the_rbtree);
+ return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
}
/** @} */
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index febd65f..20338eb 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -80,7 +80,7 @@ static void insert_into_tree(
rtems_rbheap_chunk *chunk
)
{
- _RBTree_Insert(tree, &chunk->tree_node);
+ rtems_rbtree_insert(tree, &chunk->tree_node, chunk_compare, true);
}
rtems_status_code rtems_rbheap_initialize(
@@ -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);
control->alignment = alignment;
control->handler_arg = handler_arg;
control->extend_descriptors = extend_descriptors;
@@ -198,7 +198,7 @@ static rtems_rbheap_chunk *find(rtems_rbtree_control
*chunk_tree, uintptr_t key)
rtems_rbheap_chunk chunk = { .begin = key };
return rtems_rbheap_chunk_of_node(
- _RBTree_Find(chunk_tree, &chunk.tree_node)
+ rtems_rbtree_find(chunk_tree, &chunk.tree_node, chunk_compare, true)
);
}
@@ -230,7 +230,7 @@ static void check_and_merge(
a->size += b->size;
rtems_chain_extract_unprotected(&b->chain_node);
add_to_chain(free_chain, b);
- _RBTree_Extract(chunk_tree, &b->tree_node);
+ rtems_rbtree_extract(chunk_tree, &b->tree_node);
}
}
diff --git a/cpukit/score/include/rtems/score/rbtree.h
b/cpukit/score/include/rtems/score/rbtree.h
index 5a296b6..a219a6e 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -104,13 +104,21 @@ typedef enum {
} RBTree_Direction;
/**
- * This type defines function pointers for user-provided comparison
- * function. The function compares two nodes in order to determine
- * the order in a red-black tree.
+ * @brief Compares two red-black tree nodes.
+ *
+ * @param[in] first The first node.
+ * @param[in] second The second node.
+ *
+ * @retval positive The key value of the first node is greater than the one of
+ * the second node.
+ * @retval 0 The key value of the first node is equal to the one of the second
+ * node.
+ * @retval negative The key value of the first node is less than the one of the
+ * second node.
*/
-typedef int (*RBTree_Compare_function)(
- const RBTree_Node *node1,
- const RBTree_Node *node2
+typedef int ( *RBTree_Compare )(
+ const RBTree_Node *first,
+ const RBTree_Node *second
);
/**
@@ -139,51 +147,31 @@ typedef struct {
RBTree_Node *root;
/** This points to the min and max nodes of this RBT. */
RBTree_Node *first[2];
- /**
- * Comparison function pointer. Keys to compare have to be found
- * inside to maintain generality. It has to return 1 if first node
- * 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;
} RBTree_Control;
/**
* @brief RBTree initializer for an empty rbtree with designator @a name.
*/
-#define RBTREE_INITIALIZER_EMPTY(name) \
-{ \
- .permanent_null = NULL, \
- .root = NULL, \
- .first[0] = NULL, \
- .first[1] = NULL, \
- .compare_function = NULL, \
- .is_unique = 0 \
-}
+#define RBTREE_INITIALIZER_EMPTY( name ) \
+ { NULL, NULL, { NULL, NULL } }
/**
* @brief RBTree definition for an empty rbtree with designator @a name.
*/
-#define RBTREE_DEFINE_EMPTY(name) \
-RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)
+#define RBTREE_DEFINE_EMPTY( name ) \
+ RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
/**
* @brief RBTree_Node initializer for an empty node with designator @a name.
*/
-#define RBTREE_NODE_INITIALIZER_EMPTY(name) \
-{ \
- .parent = NULL, \
- .child[0] = NULL, \
- .child[1] = NULL, \
- RBT_RED \
-}
+#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
+ { NULL, { NULL, NULL }, RBT_RED }
/**
* @brief RBTree definition for an empty rbtree with designator @a name.
*/
-#define RBTREE_NODE_DEFINE_EMPTY(name) \
-RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
+#define RBTREE_NODE_DEFINE_EMPTY( name ) \
+ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )
/**
* @brief Initialize a RBTree Header.
@@ -193,17 +181,20 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
* @a starting_address. Each node is of @a node_size bytes.
*
* @param[in] the_rbtree is the pointer to rbtree header
+ * @param[in] compare The node compare function.
* @param[in] starting_address is the starting address of first node
* @param[in] number_nodes is the number of nodes in rbtree
* @param[in] node_size is the size of node in bytes
+ * @param[in] is_unique If true, then reject nodes with a duplicate key, else
+ * otherwise.
*/
void _RBTree_Initialize(
- RBTree_Control *the_rbtree,
- RBTree_Compare_function compare_function,
- void *starting_address,
- size_t number_nodes,
- size_t node_size,
- bool is_unique
+ RBTree_Control *the_rbtree,
+ RBTree_Compare compare,
+ void *starting_address,
+ size_t number_nodes,
+ size_t node_size,
+ bool is_unique
);
/**
@@ -211,6 +202,10 @@ void _RBTree_Initialize(
*
* @param[in] the_rbtree The red-black tree control.
* @param[in] the_node A node specifying the key.
+ * @param[in] compare The node compare function.
+ * @param[in] is_unique If true, then return the first node with a key equal to
+ * the one of the node specified if it exits, else return the last node if it
+ * exists.
*
* @retval node A node corresponding to the key. If the tree is not unique
* and contains duplicate keys, the set of duplicate keys acts as FIFO.
@@ -218,7 +213,9 @@ void _RBTree_Initialize(
*/
RBTree_Node *_RBTree_Find(
const RBTree_Control *the_rbtree,
- const RBTree_Node *the_node
+ const RBTree_Node *the_node,
+ RBTree_Compare compare,
+ bool is_unique
);
/**
@@ -226,6 +223,12 @@ RBTree_Node *_RBTree_Find(
*
* This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
*
+ * @param[in] the_rbtree The red-black tree control.
+ * @param[in] the_node The node to insert.
+ * @param[in] compare The node compare function.
+ * @param[in] is_unique If true, then reject nodes with a duplicate key, else
+ * otherwise.
+ *
* @retval 0 Successfully inserted.
* @retval -1 NULL @a the_node.
* @retval RBTree_Node* if one with equal value to @a the_node 's key exists
@@ -233,7 +236,9 @@ RBTree_Node *_RBTree_Find(
*/
RBTree_Node *_RBTree_Insert(
RBTree_Control *the_rbtree,
- RBTree_Node *the_node
+ RBTree_Node *the_node,
+ RBTree_Compare compare,
+ bool is_unique
);
/**
@@ -437,17 +442,13 @@ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header(
* This routine initializes @a the_rbtree to contain zero nodes.
*/
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
- RBTree_Control *the_rbtree,
- RBTree_Compare_function compare_function,
- bool is_unique
- )
+ RBTree_Control *the_rbtree
+)
{
the_rbtree->permanent_null = NULL;
the_rbtree->root = NULL;
- the_rbtree->first[0] = NULL;
- the_rbtree->first[1] = NULL;
- the_rbtree->compare_function = compare_function;
- the_rbtree->is_unique = is_unique;
+ the_rbtree->first[RBT_LEFT] = NULL;
+ the_rbtree->first[RBT_RIGHT] = NULL;
}
/**
@@ -502,16 +503,6 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
return the_node;
}
-/**
- * @brief Determines whether the tree is unique.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
- const RBTree_Control *the_rbtree
-)
-{
- return( the_rbtree && the_rbtree->is_unique );
-}
-
/**@}*/
#ifdef __cplusplus
diff --git a/cpukit/score/include/rtems/score/scheduleredfimpl.h
b/cpukit/score/include/rtems/score/scheduleredfimpl.h
index aab338e..019c544 100644
--- a/cpukit/score/include/rtems/score/scheduleredfimpl.h
+++ b/cpukit/score/include/rtems/score/scheduleredfimpl.h
@@ -44,6 +44,11 @@ RTEMS_INLINE_ROUTINE Scheduler_EDF_Node
*_Scheduler_EDF_Thread_get_node(
return (Scheduler_EDF_Node *) _Scheduler_Thread_get_node( the_thread );
}
+int _Scheduler_EDF_Compare(
+ const RBTree_Node* n1,
+ const RBTree_Node* n2
+);
+
RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
const Scheduler_Control *scheduler,
Thread_Control *the_thread
@@ -53,7 +58,12 @@ RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
_Scheduler_EDF_Get_context( scheduler );
Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
- _RBTree_Insert( &context->Ready, &node->Node );
+ _RBTree_Insert(
+ &context->Ready,
+ &node->Node,
+ _Scheduler_EDF_Compare,
+ false
+ );
node->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
}
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
index 958aed0..5e8520d 100644
--- a/cpukit/score/src/rbtree.c
+++ b/cpukit/score/src/rbtree.c
@@ -23,12 +23,12 @@
#include <rtems/score/isr.h>
void _RBTree_Initialize(
- RBTree_Control *the_rbtree,
- RBTree_Compare_function compare_function,
- void *starting_address,
- size_t number_nodes,
- size_t node_size,
- bool is_unique
+ RBTree_Control *the_rbtree,
+ RBTree_Compare compare,
+ void *starting_address,
+ size_t number_nodes,
+ size_t node_size,
+ bool is_unique
)
{
size_t count;
@@ -38,13 +38,12 @@ 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 );
count = number_nodes;
next = starting_address;
while ( count-- ) {
- _RBTree_Insert(the_rbtree, next);
- next = (RBTree_Node *)
- _Addresses_Add_offset( (void *) next, node_size );
+ _RBTree_Insert( the_rbtree, next, compare, is_unique );
+ next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
}
}
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 4aaf236..ad0c9fd 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -18,28 +18,30 @@
#endif
#include <rtems/score/rbtreeimpl.h>
-#include <rtems/score/isr.h>
RBTree_Node *_RBTree_Find(
const RBTree_Control *the_rbtree,
- const RBTree_Node *the_node
+ const RBTree_Node *the_node,
+ RBTree_Compare compare,
+ bool is_unique
)
{
RBTree_Node* iter_node = the_rbtree->root;
RBTree_Node* found = NULL;
- int compare_result;
- while (iter_node) {
- compare_result = the_rbtree->compare_function(the_node, iter_node);
+
+ while ( iter_node != NULL ) {
+ int compare_result = ( *compare )( the_node, iter_node );
+ RBTree_Direction dir;
+
if ( _RBTree_Is_equal( compare_result ) ) {
found = iter_node;
- if ( the_rbtree->is_unique )
+ if ( is_unique )
break;
}
- RBTree_Direction dir =
- (RBTree_Direction) _RBTree_Is_greater( compare_result );
- iter_node = iter_node->child[dir];
- } /* while(iter_node) */
+ dir = (RBTree_Direction) _RBTree_Is_greater( compare_result );
+ iter_node = iter_node->child[ dir ];
+ }
return found;
}
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 39f7c2b..7174529 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -59,24 +59,12 @@ static void _RBTree_Validate_insert(
if(!the_node->parent->parent) the_node->color = RBT_BLACK;
}
-
-
-/** @brief Insert a Node (unprotected)
- *
- * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
- *
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal key to the key of @a the_node exists
- * in an unique @a the_rbtree.
- *
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
- */
RBTree_Node *_RBTree_Insert(
- RBTree_Control *the_rbtree,
- RBTree_Node *the_node
- )
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node,
+ RBTree_Compare compare,
+ bool is_unique
+)
{
if(!the_node) return (RBTree_Node*)-1;
@@ -92,8 +80,8 @@ RBTree_Node *_RBTree_Insert(
} else {
/* 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 ) )
+ compare_result = ( *compare )( the_node, iter_node );
+ if ( is_unique && _RBTree_Is_equal( compare_result ) )
return iter_node;
RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
if (!iter_node->child[dir]) {
@@ -102,9 +90,9 @@ RBTree_Node *_RBTree_Insert(
iter_node->child[dir] = the_node;
the_node->parent = iter_node;
/* update min/max */
- compare_result = the_rbtree->compare_function(
- the_node,
- _RBTree_First(the_rbtree, dir)
+ compare_result = ( *compare )(
+ the_node,
+ _RBTree_First( the_rbtree, dir )
);
if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
(dir && _RBTree_Is_greater(compare_result)) ) {
diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c
index 010d053..01b5244 100644
--- a/cpukit/score/src/scheduleredf.c
+++ b/cpukit/score/src/scheduleredf.c
@@ -20,8 +20,7 @@
#include <rtems/score/scheduleredfimpl.h>
-static int _Scheduler_EDF_RBTree_compare_function
-(
+int _Scheduler_EDF_Compare(
const RBTree_Node* n1,
const RBTree_Node* n2
)
@@ -43,9 +42,5 @@ void _Scheduler_EDF_Initialize( const Scheduler_Control
*scheduler )
Scheduler_EDF_Context *context =
_Scheduler_EDF_Get_context( scheduler );
- _RBTree_Initialize_empty(
- &context->Ready,
- _Scheduler_EDF_RBTree_compare_function,
- 0
- );
+ _RBTree_Initialize_empty( &context->Ready );
}
diff --git a/cpukit/score/src/scheduleredfchangepriority.c
b/cpukit/score/src/scheduleredfchangepriority.c
index 32b0993..3eabc83 100644
--- a/cpukit/score/src/scheduleredfchangepriority.c
+++ b/cpukit/score/src/scheduleredfchangepriority.c
@@ -32,7 +32,12 @@ Scheduler_Void_or_thread _Scheduler_EDF_Change_priority(
Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
_RBTree_Extract( &context->Ready, &node->Node );
- _RBTree_Insert( &context->Ready, &node->Node );
+ _RBTree_Insert(
+ &context->Ready,
+ &node->Node,
+ _Scheduler_EDF_Compare,
+ false
+ );
SCHEDULER_RETURN_VOID_OR_NULL;
}
diff --git a/cpukit/score/src/scheduleredfyield.c
b/cpukit/score/src/scheduleredfyield.c
index 5aa2afd..0ad5c32 100644
--- a/cpukit/score/src/scheduleredfyield.c
+++ b/cpukit/score/src/scheduleredfyield.c
@@ -35,7 +35,12 @@ Scheduler_Void_or_thread _Scheduler_EDF_Yield(
* with the same priority in case there are such ones.
*/
_RBTree_Extract( &context->Ready, &node->Node );
- _RBTree_Insert( &context->Ready, &node->Node );
+ _RBTree_Insert(
+ &context->Ready,
+ &node->Node,
+ _Scheduler_EDF_Compare,
+ false
+ );
_Scheduler_EDF_Schedule_body( scheduler, the_thread, false );
diff --git a/testsuites/sptests/sprbtree01/init.c
b/testsuites/sptests/sprbtree01/init.c
index abec11e..d58a8b5 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -42,6 +42,38 @@ static int test_compare_function (
return key1 - key2;
}
+static rtems_rbtree_node *rb_insert_unique(
+ rtems_rbtree_control *rbtree,
+ rtems_rbtree_node *node
+)
+{
+ return rtems_rbtree_insert( rbtree, node, test_compare_function, true );
+}
+
+static rtems_rbtree_node *rb_insert_multi(
+ rtems_rbtree_control *rbtree,
+ rtems_rbtree_node *node
+)
+{
+ return rtems_rbtree_insert( rbtree, node, test_compare_function, false );
+}
+
+static rtems_rbtree_node *rb_find_unique(
+ rtems_rbtree_control *rbtree,
+ rtems_rbtree_node *node
+)
+{
+ return rtems_rbtree_find( rbtree, node, test_compare_function, true );
+}
+
+static rtems_rbtree_node *rb_find_multi(
+ rtems_rbtree_control *rbtree,
+ rtems_rbtree_node *node
+)
+{
+ return rtems_rbtree_find( rbtree, node, test_compare_function, false );
+}
+
/*
* recursively checks tree. if the tree is built properly it should only
* be a depth of 7 function calls for 100 entries in the tree.
@@ -106,12 +138,7 @@ rtems_task Init(
TEST_BEGIN();
puts( "Init - Initialize rbtree empty" );
- 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" );
+ rtems_rbtree_initialize_empty( &rbtree1 );
/* verify that the rbtree insert work */
puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
@@ -119,10 +146,10 @@ rtems_task Init(
node1.key = 1;
node2.id = 2;
node2.key = 2;
- rtems_rbtree_insert( &rbtree1, &node1.Node );
- rtems_rbtree_insert( &rbtree1, &node2.Node );
+ rb_insert_unique( &rbtree1, &node1.Node );
+ rb_insert_unique( &rbtree1, &node2.Node );
- p = rtems_rbtree_insert( &rbtree1, NULL );
+ p = rb_insert_unique( &rbtree1, NULL );
if (p != (void *)(-1))
puts( "INIT - FAILED NULL NODE INSERT" );
@@ -159,8 +186,8 @@ rtems_task Init(
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);
+ rb_insert_unique(&rbtree1, &node1.Node);
+ p = rb_insert_unique(&rbtree1, &node2.Node);
if (p != &node1.Node)
puts( "INIT - FAILED DUPLICATE INSERT" );
@@ -218,8 +245,8 @@ rtems_task Init(
node1.key = 2;
node2.id = 1;
node2.key = 1;
- rtems_rbtree_insert( &rbtree1, &node1.Node );
- rtems_rbtree_insert( &rbtree1, &node2.Node );
+ rb_insert_unique( &rbtree1, &node1.Node );
+ rb_insert_unique( &rbtree1, &node2.Node );
puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1),
@@ -237,7 +264,7 @@ rtems_task Init(
puts( "INIT - rtems_rbtree_extract failed");
rtems_test_exit(0);
}
- rtems_rbtree_insert(&rbtree1, p);
+ rb_insert_unique(&rbtree1, p);
for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
@@ -256,7 +283,7 @@ rtems_task Init(
for (i = 0; i < 100; i++) {
node_array[i].id = i;
node_array[i].key = i;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_unique( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -289,7 +316,7 @@ rtems_task Init(
for (i = 0; i < 100; i++) {
node_array[i].id = 99-i;
node_array[i].key = 99-i;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_unique( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -324,7 +351,7 @@ rtems_task Init(
for (i = 0; i < 100; i++) {
node_array[i].id = i;
node_array[i].key = i;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_unique( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -376,13 +403,13 @@ rtems_task Init(
node_array[i].id = i;
node_array[i].key = i;
}
- rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
- rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
- rtems_rbtree_insert( &rbtree1, &node_array[5].Node );
- rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
- rtems_rbtree_insert( &rbtree1, &node_array[2].Node );
- rtems_rbtree_insert( &rbtree1, &node_array[4].Node );
- rtems_rbtree_insert( &rbtree1, &node_array[6].Node );
+ rb_insert_unique( &rbtree1, &node_array[3].Node );
+ rb_insert_unique( &rbtree1, &node_array[1].Node );
+ rb_insert_unique( &rbtree1, &node_array[5].Node );
+ rb_insert_unique( &rbtree1, &node_array[0].Node );
+ rb_insert_unique( &rbtree1, &node_array[2].Node );
+ rb_insert_unique( &rbtree1, &node_array[4].Node );
+ rb_insert_unique( &rbtree1, &node_array[6].Node );
rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
/* node_array[1] has now only a left child. */
if ( !node_array[1].Node.child[RBT_LEFT] ||
@@ -395,7 +422,7 @@ rtems_task Init(
for (i = 0; i < 100; i++) {
node_array[i].id = 99-i;
node_array[i].key = 99-i;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_unique( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -428,7 +455,7 @@ rtems_task Init(
for (i = 0; i < 100; i++) {
node_array[i].id = i;
node_array[i].key = i;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_unique( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -436,7 +463,7 @@ rtems_task Init(
puts( "INIT - Verify rtems_rbtree_find" );
search_node.key = 30;
- p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ p = rb_find_unique(&rbtree1, &search_node.Node);
if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
@@ -448,14 +475,14 @@ rtems_task Init(
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
}
- p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ p = rb_find_unique(&rbtree1, &search_node.Node);
p = rtems_rbtree_successor(p);
if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
}
- p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ p = rb_find_unique(&rbtree1, &search_node.Node);
puts( "INIT - Verify rtems_rbtree_find_header" );
if (rtems_rbtree_find_header(p) != &rbtree1) {
puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
@@ -509,7 +536,7 @@ rtems_task Init(
for (i = 0; i < 20; i++) {
node_array[i].id = numbers[i];
node_array[i].key = numbers[i];
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_unique( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -573,18 +600,13 @@ rtems_task Init(
/* Initialize the tree for duplicate keys */
puts( "Init - Initialize duplicate rbtree empty" );
- 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" );
+ rtems_rbtree_initialize_empty( &rbtree1 );
puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
for (i = 0; i < 100; i++) {
node_array[i].id = i;
node_array[i].key = i%5;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_multi( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -592,7 +614,7 @@ rtems_task Init(
puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
search_node.key = 2;
- p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ p = rb_find_multi(&rbtree1, &search_node.Node);
if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
@@ -625,7 +647,7 @@ rtems_task Init(
for (i = 0; i < 100; i++) {
node_array[i].id = 99-i;
node_array[i].key = (99-i)%5;
- rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+ rb_insert_multi( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
puts( "INIT - FAILED TREE CHECK" );
@@ -633,7 +655,7 @@ rtems_task Init(
puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
search_node.key = 2;
- p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ p = rb_find_multi(&rbtree1, &search_node.Node);
if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
--
1.8.1.4
_______________________________________________
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
