change log for rtems (2011-08-02)
rtems-vc at rtems.org
rtems-vc at rtems.org
Tue Aug 2 20:10:12 UTC 2011
*joel*:
2011-08-02 Joel Sherrill <joel.sherrill at 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.
M 1.2901 cpukit/ChangeLog
M 1.16 cpukit/libfs/src/imfs/imfs_mknod.c
M 1.41 cpukit/libfs/src/imfs/memfile.c
M 1.2 cpukit/sapi/inline/rtems/rbtree.inl
M 1.5 cpukit/score/include/rtems/score/rbtree.h
M 1.2 cpukit/score/inline/rtems/score/rbtree.inl
M 1.4 cpukit/score/src/rbtree.c
M 1.3 cpukit/score/src/rbtreefind.c
M 1.3 cpukit/score/src/rbtreeinsert.c
diff -u rtems/cpukit/ChangeLog:1.2900 rtems/cpukit/ChangeLog:1.2901
--- rtems/cpukit/ChangeLog:1.2900 Tue Aug 2 08:59:48 2011
+++ rtems/cpukit/ChangeLog Tue Aug 2 14:25:58 2011
@@ -1,3 +1,12 @@
+2011-08-02 Joel Sherrill <joel.sherrill at 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 at OARcorp.com>
* score/include/rtems/score/coremutex.h: Move check dispatch for seize
diff -u rtems/cpukit/libfs/src/imfs/imfs_mknod.c:1.15 rtems/cpukit/libfs/src/imfs/imfs_mknod.c:1.16
--- rtems/cpukit/libfs/src/imfs/imfs_mknod.c:1.15 Mon Aug 2 13:27:23 2010
+++ rtems/cpukit/libfs/src/imfs/imfs_mknod.c Tue Aug 2 14:25:59 2011
@@ -72,5 +72,7 @@
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 -u rtems/cpukit/libfs/src/imfs/memfile.c:1.40 rtems/cpukit/libfs/src/imfs/memfile.c:1.41
--- rtems/cpukit/libfs/src/imfs/memfile.c:1.40 Tue Apr 5 08:38:49 2011
+++ rtems/cpukit/libfs/src/imfs/memfile.c Tue Aug 2 14:25:59 2011
@@ -326,6 +326,9 @@
* 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 -u rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.1 rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.2
--- rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.1 Mon Apr 4 13:44:16 2011
+++ rtems/cpukit/sapi/inline/rtems/rbtree.inl Tue Aug 2 14:25:59 2011
@@ -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 @@
* 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 @@
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 -u rtems/cpukit/score/include/rtems/score/rbtree.h:1.4 rtems/cpukit/score/include/rtems/score/rbtree.h:1.5
--- rtems/cpukit/score/include/rtems/score/rbtree.h:1.4 Fri Jun 17 10:40:09 2011
+++ rtems/cpukit/score/include/rtems/score/rbtree.h Tue Aug 2 14:25:59 2011
@@ -75,8 +75,6 @@
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 @@
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 @@
.root = NULL, \
.first[0] = NULL, \
.first[1] = NULL, \
+ .compare_function = NULL \
}
/**
@@ -154,7 +159,6 @@
.parent = NULL, \
.child[0] = NULL, \
.child[1] = NULL, \
- .value = -1, \
RBT_RED \
}
@@ -173,9 +177,10 @@
*/
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 @@
);
/**
- * @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 -u rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.1 rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.2
--- rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.1 Mon Apr 4 13:44:16 2011
+++ rtems/cpukit/score/inline/rtems/score/rbtree.inl Tue Aug 2 14:25:59 2011
@@ -235,13 +235,15 @@
* 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 @@
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 -u rtems/cpukit/score/src/rbtree.c:1.3 rtems/cpukit/score/src/rbtree.c:1.4
--- rtems/cpukit/score/src/rbtree.c:1.3 Sun Jul 24 18:55:14 2011
+++ rtems/cpukit/score/src/rbtree.c Tue Aug 2 14:25:59 2011
@@ -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 @@
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 -u rtems/cpukit/score/src/rbtreefind.c:1.2 rtems/cpukit/score/src/rbtreefind.c:1.3
--- rtems/cpukit/score/src/rbtreefind.c:1.2 Mon May 23 21:44:57 2011
+++ rtems/cpukit/score/src/rbtreefind.c Tue Aug 2 14:25:59 2011
@@ -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 @@
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 -u rtems/cpukit/score/src/rbtreeinsert.c:1.2 rtems/cpukit/score/src/rbtreeinsert.c:1.3
--- rtems/cpukit/score/src/rbtreeinsert.c:1.2 Mon May 23 21:44:57 2011
+++ rtems/cpukit/score/src/rbtreeinsert.c Tue Aug 2 14:25:59 2011
@@ -71,7 +71,7 @@
*
* @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 @@
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 @@
} 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;
*joel*:
2011-08-02 Joel Sherrill <joel.sherrill at oarcorp.com>
PR 1877/cpukit
* sprbtree01/init.c: Add comparison function for RBTrees.
M 1.471 testsuites/sptests/ChangeLog
M 1.4 testsuites/sptests/sprbtree01/init.c
diff -u rtems/testsuites/sptests/ChangeLog:1.470 rtems/testsuites/sptests/ChangeLog:1.471
--- rtems/testsuites/sptests/ChangeLog:1.470 Tue Aug 2 08:38:40 2011
+++ rtems/testsuites/sptests/ChangeLog Tue Aug 2 14:26:05 2011
@@ -1,3 +1,8 @@
+2011-08-02 Joel Sherrill <joel.sherrill at oarcorp.com>
+
+ PR 1877/cpukit
+ * sprbtree01/init.c: Add comparison function for RBTrees.
+
2011-08-02 Petr Benes <benesp16 at fel.cvut.cz>
PR 1862/testing
diff -u rtems/testsuites/sptests/sprbtree01/init.c:1.3 rtems/testsuites/sptests/sprbtree01/init.c:1.4
--- rtems/testsuites/sptests/sprbtree01/init.c:1.3 Tue Aug 2 08:38:41 2011
+++ rtems/testsuites/sptests/sprbtree01/init.c Tue Aug 2 14:26:05 2011
@@ -19,9 +19,23 @@
typedef struct {
int id;
+ int key;
rtems_rbtree_node Node;
} test_node;
+int test_compare_function (
+ rtems_rbtree_node* n1,
+ rtems_rbtree_node* n2
+)
+{
+ int key1 = rtems_rbtree_container_of( n1, test_node, Node )->key;
+ int key2 = rtems_rbtree_container_of( n2, test_node, Node )->key;
+
+ if (key1 > key2) return 1;
+ else if (key1 < key2) return -1;
+ else return 0;
+}
+
/*
* 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.
@@ -48,8 +62,8 @@
rh = rb_assert ( rn );
/* Invalid binary search tree */
- if ( ( ln != NULL && ln->value >= root->value )
- || ( rn != NULL && rn->value <= root->value ) )
+ if ( ( ln != NULL && test_compare_function(ln, root) > 0 )
+ || ( rn != NULL && test_compare_function(rn, root) < 0 ) )
{
puts ( "Binary tree violation" );
return -1;
@@ -79,20 +93,21 @@
rtems_rbtree_node *p;
test_node node1, node2;
test_node node_array[100];
+ test_node search_node;
int id;
int i;
puts( "\n\n*** TEST OF RTEMS RBTREE API ***" );
puts( "Init - Initialize rbtree empty" );
- rtems_rbtree_initialize_empty( &rbtree1 );
+ rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function );
/* verify that the rbtree insert work */
puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
node1.id = 1;
- node1.Node.value = 1;
+ node1.key = 1;
node2.id = 2;
- node2.Node.value = 2;
+ node2.key = 2;
rtems_rbtree_insert( &rbtree1, &node1.Node );
rtems_rbtree_insert( &rbtree1, &node2.Node );
@@ -132,7 +147,7 @@
}
puts("INIT - Verify rtems_rbtree_insert with the same value twice");
- node2.Node.value = node1.Node.value;
+ node2.key = node1.key;
rtems_rbtree_insert(&rbtree1, &node1.Node);
rtems_rbtree_insert(&rbtree1, &node2.Node);
for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
@@ -154,7 +169,7 @@
puts("INIT - NOT ENOUGH NODES ON RBTREE");
rtems_test_exit(0);
}
- node2.Node.value = 2;
+ node2.key = 2;
/* verify that the rbtree is empty */
puts( "INIT - Verify rtems_rbtree_is_empty" );
@@ -185,21 +200,25 @@
/* verify that the rbtree insert works after a tree is emptied */
puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
node1.id = 2;
- node1.Node.value = 2;
+ node1.key = 2;
node2.id = 1;
- node2.Node.value = 1;
+ node2.key = 1;
rtems_rbtree_insert( &rbtree1, &node1.Node );
rtems_rbtree_insert( &rbtree1, &node2.Node );
puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
- if(rtems_rbtree_peek_max(&rbtree1)->value -
- rtems_rbtree_peek_min(&rbtree1)->value != 1) {
+ test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1),
+ test_node,Node);
+ test_node *t2 = rtems_rbtree_container_of(rtems_rbtree_peek_min(&rbtree1),
+ test_node,Node);
+ if (t1->key - t2->key != 1) {
puts( "INIT - Peek Min - Max failed" );
rtems_test_exit(0);
}
p = rtems_rbtree_peek_max(&rbtree1);
rtems_rbtree_extract(&rbtree1, p);
- if (p->value != 2) {
+ t1 = rtems_rbtree_container_of(p,test_node,Node);
+ if (t1->key != 2) {
puts( "INIT - rtems_rbtree_extract failed");
rtems_test_exit(0);
}
@@ -221,7 +240,7 @@
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].Node.value = i;
+ node_array[i].key = i;
rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
@@ -254,7 +273,7 @@
puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
for (i = 0; i < 100; i++) {
node_array[i].id = 99-i;
- node_array[i].Node.value = 99-i;
+ node_array[i].key = 99-i;
rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
@@ -289,7 +308,7 @@
puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
for (i = 0; i < 100; i++) {
node_array[i].id = i;
- node_array[i].Node.value = i;
+ node_array[i].key = i;
rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
@@ -340,7 +359,7 @@
* with two children while target node has a left child only. */
for ( i = 0; i < 7; i++ ) {
node_array[i].id = i;
- node_array[i].Node.value = i;
+ node_array[i].key = i;
}
rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
@@ -360,7 +379,7 @@
puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
for (i = 0; i < 100; i++) {
node_array[i].id = 99-i;
- node_array[i].Node.value = 99-i;
+ node_array[i].key = 99-i;
rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
@@ -393,7 +412,7 @@
puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
for (i = 0; i < 100; i++) {
node_array[i].id = i;
- node_array[i].Node.value = i;
+ node_array[i].key = i;
rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
@@ -401,7 +420,8 @@
}
puts( "INIT - Verify rtems_rbtree_find" );
- p = rtems_rbtree_find(&rbtree1, 30);
+ search_node.key = 30;
+ p = rtems_rbtree_find(&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);
@@ -413,14 +433,14 @@
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
}
- p = rtems_rbtree_find(&rbtree1, 30);
+ p = rtems_rbtree_find(&rbtree1, &search_node.Node);
p = rtems_rbtree_successor(p);
if(p && rtems_rbtree_container_of(p,test_node,Node)->id < 30) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
}
- p = rtems_rbtree_find(&rbtree1, 30);
+ p = rtems_rbtree_find(&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");
@@ -469,7 +489,7 @@
puts("INIT - Insert 20 random numbers");
for (i = 0; i < 20; i++) {
node_array[i].id = numbers[i];
- node_array[i].Node.value = numbers[i];
+ node_array[i].key = numbers[i];
rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
if (!rb_assert(rbtree1.root) )
@@ -502,10 +522,10 @@
puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
for (i = 0; i < 100; i++) {
node_array[i].id = i;
- node_array[i].Node.value = i;
+ node_array[i].key = i;
}
- rtems_rbtree_initialize( &rbtree1, &node_array[0].Node, 100,
- sizeof(test_node));
+ rtems_rbtree_initialize( &rbtree1, &test_compare_function,
+ &node_array[0].Node, 100, sizeof(test_node));
puts( "INIT - Removing 100 nodes" );
--
Generated by Deluxe Loginfo [http://www.codewiz.org/projects/index.html#loginfo] 2.122 by Bernardo Innocenti <bernie at develer.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/vc/attachments/20110802/d47e5d90/attachment-0001.html>
More information about the vc
mailing list