From 64939bc9efcaf945b493e9c371901de33c3868a3 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Sat, 12 Jul 2014 14:22:22 -0500 Subject: 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(). --- 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 +++++- 6 files changed, 45 insertions(+), 51 deletions(-) (limited to 'cpukit/score/src') 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 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 -#include 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 -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 ); -- cgit v1.2.3