diff options
author | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-08-02 19:25:59 +0000 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-08-02 19:25:59 +0000 |
commit | 13c4f853e6655e6b1c759255bea4f63c77806cdc (patch) | |
tree | 6347f845f2761b7ea2863c44c672e83f40177c9e | |
parent | 2011-08-02 Ricardo Aguirre <el.mastin@ymail.com> (diff) | |
download | rtems-13c4f853e6655e6b1c759255bea4f63c77806cdc.tar.bz2 |
2011-08-02 Joel Sherrill <joel.sherrill@oarcorp.com>
PR 1877/cpukit
* libfs/src/imfs/imfs_mknod.c, libfs/src/imfs/memfile.c,
sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h,
score/inline/rtems/score/rbtree.inl, score/src/rbtree.c,
score/src/rbtreefind.c, score/src/rbtreeinsert.c: Add comparison
function for RBTrees.
-rw-r--r-- | cpukit/ChangeLog | 9 | ||||
-rw-r--r-- | cpukit/libfs/src/imfs/imfs_mknod.c | 2 | ||||
-rw-r--r-- | cpukit/libfs/src/imfs/memfile.c | 3 | ||||
-rw-r--r-- | cpukit/sapi/inline/rtems/rbtree.inl | 26 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 26 | ||||
-rw-r--r-- | cpukit/score/inline/rtems/score/rbtree.inl | 27 | ||||
-rw-r--r-- | cpukit/score/src/rbtree.c | 3 | ||||
-rw-r--r-- | cpukit/score/src/rbtreefind.c | 8 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 8 |
9 files changed, 73 insertions, 39 deletions
diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog index ee98705571..529bb3268d 100644 --- a/cpukit/ChangeLog +++ b/cpukit/ChangeLog @@ -1,3 +1,12 @@ +2011-08-02 Joel Sherrill <joel.sherrill@oarcorp.com> + + PR 1877/cpukit + * libfs/src/imfs/imfs_mknod.c, libfs/src/imfs/memfile.c, + sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, + score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, + score/src/rbtreefind.c, score/src/rbtreeinsert.c: Add comparison + function for RBTrees. + 2011-08-02 Jennifer Averett <Jennifer.Averett@OARcorp.com> * score/include/rtems/score/coremutex.h: Move check dispatch for seize diff --git a/cpukit/libfs/src/imfs/imfs_mknod.c b/cpukit/libfs/src/imfs/imfs_mknod.c index 1a0175af0a..2d09c73db5 100644 --- a/cpukit/libfs/src/imfs/imfs_mknod.c +++ b/cpukit/libfs/src/imfs/imfs_mknod.c @@ -72,5 +72,7 @@ int IMFS_mknod( if ( !new_node ) rtems_set_errno_and_return_minus_one( ENOMEM ); + IMFS_update_ctime(new_node->Parent); + IMFS_update_mtime(new_node->Parent); return 0; } diff --git a/cpukit/libfs/src/imfs/memfile.c b/cpukit/libfs/src/imfs/memfile.c index 56722a186c..069d352606 100644 --- a/cpukit/libfs/src/imfs/memfile.c +++ b/cpukit/libfs/src/imfs/memfile.c @@ -326,6 +326,9 @@ MEMFILE_STATIC int IMFS_memfile_extend( * Set the new length of the file. */ the_jnode->info.file.size = new_length; + + IMFS_update_ctime(the_jnode); + IMFS_update_mtime(the_jnode); return 0; } diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl index 3f2045189e..52fdcb3f23 100644 --- a/cpukit/sapi/inline/rtems/rbtree.inl +++ b/cpukit/sapi/inline/rtems/rbtree.inl @@ -36,12 +36,14 @@ */ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( rtems_rbtree_control *the_rbtree, - void *starting_address, - size_t number_nodes, - size_t node_size + void *compare_function, + void *starting_address, + size_t number_nodes, + size_t node_size ) { - _RBTree_Initialize( the_rbtree, starting_address, number_nodes, node_size); + _RBTree_Initialize( the_rbtree, compare_function, starting_address, + number_nodes, node_size); } /** @@ -50,10 +52,11 @@ 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_control *the_rbtree, + void *compare_function ) { - _RBTree_Initialize_empty( the_rbtree ); + _RBTree_Initialize_empty( the_rbtree, compare_function ); } /** @@ -249,17 +252,18 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( return _RBTree_Is_root( the_rbtree, the_node ); } -/** @brief Find the node with given value in the tree +/** @brief Find the node with given key in the tree * - * This function returns a pointer to the node having value equal to @a value - * if it exists within @a the_rbtree, and NULL if not. + * This function returns a pointer to the node having key equal to the key + * of @a the_node if it exists within @a the_rbtree, and NULL if not. + * @a the_node has to be made up before a search. */ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( rtems_rbtree_control *the_rbtree, - unsigned int value + rtems_rbtree_node *the_node ) { - return _RBTree_Find( the_rbtree, value ); + return _RBTree_Find( the_rbtree, the_node ); } /** @brief Find the node's in-order predecessor diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index a3c5639767..8a9e11f795 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -75,8 +75,6 @@ struct RBTree_Node_struct { RBTree_Node *parent; /** child[0] points to the left child, child[1] points to the right child */ RBTree_Node *child[2]; - /** This is the integer value stored by this node, used for sorting */ - unsigned int value; /** The color of the node. Either red or black */ RBTree_Color color; }; @@ -127,6 +125,12 @@ 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 has 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. + */ + int (*compare_function) (RBTree_Node*, RBTree_Node*); } RBTree_Control; /** @@ -138,6 +142,7 @@ typedef struct { .root = NULL, \ .first[0] = NULL, \ .first[1] = NULL, \ + .compare_function = NULL \ } /** @@ -154,7 +159,6 @@ RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name) .parent = NULL, \ .child[0] = NULL, \ .child[1] = NULL, \ - .value = -1, \ RBT_RED \ } @@ -173,9 +177,10 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name) */ void _RBTree_Initialize( RBTree_Control *the_rbtree, - void *starting_address, - size_t number_nodes, - size_t node_size + void *compare_function, + void *starting_address, + size_t number_nodes, + size_t node_size ); /** @@ -214,14 +219,15 @@ RBTree_Node *_RBTree_Peek( ); /** - * @brief Find the node with given value in the tree + * @brief Find the node with given key in the tree * - * This function returns a pointer to the node with value equal to @a value - * if it exists in the Red-Black Tree @a the_rbtree, and NULL if not. + * This function returns a pointer to the node with key equal to a key + * of @a the_node if it exists in the Red-Black Tree @a the_rbtree, + * and NULL if not. */ RBTree_Node *_RBTree_Find( RBTree_Control *the_rbtree, - unsigned int value + RBTree_Node *the_node ); /** diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl index 097cede027..08eddfecba 100644 --- a/cpukit/score/inline/rtems/score/rbtree.inl +++ b/cpukit/score/inline/rtems/score/rbtree.inl @@ -235,13 +235,15 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( * This routine initializes @a the_rbtree to contain zero nodes. */ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( - RBTree_Control *the_rbtree + RBTree_Control *the_rbtree, + void *compare_function ) { - the_rbtree->permanent_null = NULL; - the_rbtree->root = NULL; - the_rbtree->first[0] = NULL; - the_rbtree->first[1] = NULL; + 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; } /** @brief Return a pointer to node's grandparent @@ -310,21 +312,26 @@ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected( return (RBTree_Control*)the_node; } -/** @brief Find the node with given value in the tree +/** @brief Find the node with given key in the tree * * This function returns a pointer to the node in @a the_rbtree - * having value equal to @a the_value if it exists, and NULL if not. + * having key equal to key of @a the_node if it exists, + * and NULL if not. @a the_node has to be made up before a search. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( RBTree_Control *the_rbtree, - unsigned int the_value + RBTree_Node *the_node ) { RBTree_Node* iter_node = the_rbtree->root; + int compare_result; while (iter_node) { - if (the_value == iter_node->value) return(iter_node); + compare_result = the_rbtree->compare_function(the_node, iter_node); + if (compare_result == 0) { + return(iter_node); + } - RBTree_Direction dir = the_value > iter_node->value; + RBTree_Direction dir = (compare_result != -1); iter_node = iter_node->child[dir]; } /* while(iter_node) */ diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c index 0b52989927..eb3af773cb 100644 --- a/cpukit/score/src/rbtree.c +++ b/cpukit/score/src/rbtree.c @@ -33,6 +33,7 @@ void _RBTree_Initialize( RBTree_Control *the_rbtree, + void *compare_function, void *starting_address, size_t number_nodes, size_t node_size @@ -45,7 +46,7 @@ void _RBTree_Initialize( if (!the_rbtree) return; /* could do sanity checks here */ - _RBTree_Initialize_empty(the_rbtree); + _RBTree_Initialize_empty(the_rbtree, compare_function); count = number_nodes; next = starting_address; diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c index 1002982342..904a5b87c8 100644 --- a/cpukit/score/src/rbtreefind.c +++ b/cpukit/score/src/rbtreefind.c @@ -21,11 +21,11 @@ * _RBTree_Find * * This kernel routine returns a pointer to the rbtree node containing the - * given value within the given tree, if it exists, or NULL otherwise. + * given key within the given tree, if it exists, or NULL otherwise. * * Input parameters: * the_rbtree - pointer to rbtree control - * the_value - value of the node to search for + * search_node - node with the key to search for * * Output parameters: * return_node - pointer to control header of rbtree @@ -38,7 +38,7 @@ RBTree_Node *_RBTree_Find( RBTree_Control *the_rbtree, - unsigned int the_value + RBTree_Node *search_node ) { ISR_Level level; @@ -46,7 +46,7 @@ RBTree_Node *_RBTree_Find( return_node = NULL; _ISR_Disable( level ); - return_node = _RBTree_Find_unprotected( the_rbtree, the_value ); + return_node = _RBTree_Find_unprotected( the_rbtree, search_node ); _ISR_Enable( level ); return return_node; } diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index 8a694063ff..bb1915de54 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -71,7 +71,7 @@ void _RBTree_Validate_insert_unprotected( * * @retval 0 Successfully inserted. * @retval -1 NULL @a the_node. - * @retval RBTree_Node* if one with equal value to @a the_node->value exists + * @retval RBTree_Node* if one with equal key to the key of @a the_node exists * in @a the_rbtree. * * @note It does NOT disable interrupts to ensure the atomicity @@ -85,6 +85,7 @@ RBTree_Node *_RBTree_Insert_unprotected( if(!the_node) return (RBTree_Node*)-1; RBTree_Node *iter_node = the_rbtree->root; + int compare_result; if (!iter_node) { /* special case: first node inserted */ the_node->color = RBT_BLACK; @@ -95,8 +96,9 @@ RBTree_Node *_RBTree_Insert_unprotected( } else { /* typical binary search tree insert, descend tree to leaf and insert */ while (iter_node) { - if(the_node->value == iter_node->value) return(iter_node); - RBTree_Direction dir = the_node->value > iter_node->value; + compare_result = the_rbtree->compare_function(the_node, iter_node); + if ( !compare_result ) return iter_node; + RBTree_Direction dir = (compare_result != -1); if (!iter_node->child[dir]) { the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; the_node->color = RBT_RED; |