diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2014-07-12 14:22:22 -0500 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@oarcorp.com> | 2014-07-15 10:03:48 -0500 |
commit | 64939bc9efcaf945b493e9c371901de33c3868a3 (patch) | |
tree | e196959688afe714c8c334f93598cb99234970e4 /cpukit | |
parent | rbtree: Delete unused functions (diff) | |
download | rtems-64939bc9efcaf945b493e9c371901de33c3868a3.tar.bz2 |
rbtree: Reduce RBTree_Control size
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().
Diffstat (limited to 'cpukit')
-rw-r--r-- | cpukit/posix/include/rtems/posix/keyimpl.h | 21 | ||||
-rw-r--r-- | cpukit/posix/src/key.c | 10 | ||||
-rw-r--r-- | cpukit/posix/src/keyfreememory.c | 4 | ||||
-rw-r--r-- | cpukit/posix/src/keygetspecific.c | 13 | ||||
-rw-r--r-- | cpukit/posix/src/keysetspecific.c | 16 | ||||
-rw-r--r-- | cpukit/sapi/include/rtems/rbtree.h | 46 | ||||
-rw-r--r-- | cpukit/sapi/src/rbheap.c | 8 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 111 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/scheduleredfimpl.h | 12 | ||||
-rw-r--r-- | cpukit/score/src/rbtree.c | 19 | ||||
-rw-r--r-- | cpukit/score/src/rbtreefind.c | 22 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 32 | ||||
-rw-r--r-- | cpukit/score/src/scheduleredf.c | 9 | ||||
-rw-r--r-- | cpukit/score/src/scheduleredfchangepriority.c | 7 | ||||
-rw-r--r-- | cpukit/score/src/scheduleredfyield.c | 7 |
15 files changed, 164 insertions, 173 deletions
diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h index 6aab2449c6..b21c1d30fc 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 de61b43e88..105706a92c 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 04c914f27d..b419f1fc95 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 eeab2e3130..9c54112fde 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 3284991edb..0f7c682506 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 7e59e036a2..2005b367e7 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 febd65f131..20338eb1bd 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 5a296b6853..a219a6e9b4 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 aab338edc0..019c5449c9 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 958aed005a..5e8520da5e 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 4aaf236430..ad0c9fdf80 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 39f7c2bb09..7174529ade 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 010d053949..01b5244cf6 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 32b0993d8f..3eabc83878 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 5aa2afd8db..0ad5c32c7c 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 ); |