[PATCH 2/2] rbtree: Reduce RBTree_Control size
Gedare Bloom
gedare at rtems.org
Sun Jul 13 17:43:43 UTC 2014
These 2 patches looked fine at a glance through.
On Sat, Jul 12, 2014 at 3:22 PM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> 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 at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel
More information about the devel
mailing list