diff options
Diffstat (limited to 'cpukit/score')
| -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 |
8 files changed, 107 insertions, 112 deletions
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 ); |