change log for rtems (2011-08-21)
rtems-vc at rtems.org
rtems-vc at rtems.org
Sun Aug 21 20:10:54 UTC 2011
*joel*:
2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1873/cpukit
* score/include/rtems/score/heap.h: When using heap protection, we
should account for adding an aligned protection footer.
M 1.2905 cpukit/ChangeLog
M 1.46 cpukit/score/include/rtems/score/heap.h
diff -u rtems/cpukit/ChangeLog:1.2904 rtems/cpukit/ChangeLog:1.2905
--- rtems/cpukit/ChangeLog:1.2904 Wed Aug 17 04:14:08 2011
+++ rtems/cpukit/ChangeLog Sun Aug 21 14:51:40 2011
@@ -1,3 +1,9 @@
+2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+
+ PR 1873/cpukit
+ * score/include/rtems/score/heap.h: When using heap protection, we
+ should account for adding an aligned protection footer.
+
2011-08-17 Sebastian Huber <sebastian.huber at embedded-brains.de>
* sapi/include/confdefs.h: Revert previous commit due to multi-lib
diff -u rtems/cpukit/score/include/rtems/score/heap.h:1.45 rtems/cpukit/score/include/rtems/score/heap.h:1.46
--- rtems/cpukit/score/include/rtems/score/heap.h:1.45 Thu Feb 17 08:17:09 2011
+++ rtems/cpukit/score/include/rtems/score/heap.h Sun Aug 21 14:51:41 2011
@@ -177,7 +177,9 @@
} Heap_Protection_block_end;
#define HEAP_PROTECTION_HEADER_SIZE \
- (sizeof(Heap_Protection_block_begin) + sizeof(Heap_Protection_block_end))
+ (sizeof(Heap_Protection_block_begin) + \
+ CPU_ALIGNMENT + \
+ sizeof(Heap_Protection_block_end))
#endif
/**
*joel* (on branch rtems-4-9-branch):
2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1890/cpukit
* posix/src/mqueuerecvsupp.c: POSIX says msg_prio is allowed to be
NULL.
M 1.2906 cpukit/ChangeLog
M 1.1539.2.81 cpukit/ChangeLog
M 1.19 cpukit/posix/src/mqueuerecvsupp.c
M 1.17.2.1 cpukit/posix/src/mqueuerecvsupp.c
diff -u rtems/cpukit/ChangeLog:1.2905 rtems/cpukit/ChangeLog:1.2906
--- rtems/cpukit/ChangeLog:1.2905 Sun Aug 21 14:51:40 2011
+++ rtems/cpukit/ChangeLog Sun Aug 21 14:59:03 2011
@@ -1,5 +1,11 @@
2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+ PR 1890/cpukit
+ * posix/src/mqueuerecvsupp.c: POSIX says msg_prio is allowed to be
+ NULL.
+
+2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+
PR 1873/cpukit
* score/include/rtems/score/heap.h: When using heap protection, we
should account for adding an aligned protection footer.
diff -u rtems/cpukit/ChangeLog:1.1539.2.80 rtems/cpukit/ChangeLog:1.1539.2.81
--- rtems/cpukit/ChangeLog:1.1539.2.80 Sun Jul 31 17:41:04 2011
+++ rtems/cpukit/ChangeLog Sun Aug 21 14:59:10 2011
@@ -1,3 +1,9 @@
+2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+
+ PR 1890/cpukit
+ * posix/src/mqueuerecvsupp.c: POSIX says msg_prio is allowed to be
+ NULL.
+
2011-07-31 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1855/cpukit
diff -u rtems/cpukit/posix/src/mqueuerecvsupp.c:1.18 rtems/cpukit/posix/src/mqueuerecvsupp.c:1.19
--- rtems/cpukit/posix/src/mqueuerecvsupp.c:1.18 Tue Feb 3 04:10:48 2009
+++ rtems/cpukit/posix/src/mqueuerecvsupp.c Sun Aug 21 14:59:03 2011
@@ -11,7 +11,7 @@
* This code ignores the O_RDONLY/O_WRONLY/O_RDWR flag at open
* time.
*
- * COPYRIGHT (c) 1989-2008.
+ * COPYRIGHT (c) 1989-2011.
* On-Line Applications Research Corporation (OAR).
*
* The license and distribution terms for this file may be
@@ -105,8 +105,11 @@
);
_Thread_Enable_dispatch();
- *msg_prio =
- _POSIX_Message_queue_Priority_from_core(_Thread_Executing->Wait.count);
+ if (msg_prio) {
+ *msg_prio = _POSIX_Message_queue_Priority_from_core(
+ _Thread_Executing->Wait.count
+ );
+ }
if ( !_Thread_Executing->Wait.return_code )
return length_out;
diff -u rtems/cpukit/posix/src/mqueuerecvsupp.c:1.17 rtems/cpukit/posix/src/mqueuerecvsupp.c:1.17.2.1
--- rtems/cpukit/posix/src/mqueuerecvsupp.c:1.17 Thu Sep 4 10:23:11 2008
+++ rtems/cpukit/posix/src/mqueuerecvsupp.c Sun Aug 21 14:59:13 2011
@@ -11,7 +11,7 @@
* This code ignores the O_RDONLY/O_WRONLY/O_RDWR flag at open
* time.
*
- * COPYRIGHT (c) 1989-2008.
+ * COPYRIGHT (c) 1989-2011.
* On-Line Applications Research Corporation (OAR).
*
* The license and distribution terms for this file may be
@@ -105,8 +105,11 @@
);
_Thread_Enable_dispatch();
- *msg_prio =
- _POSIX_Message_queue_Priority_from_core(_Thread_Executing->Wait.count);
+ if (msg_prio) {
+ *msg_prio = _POSIX_Message_queue_Priority_from_core(
+ _Thread_Executing->Wait.count
+ );
+ }
if ( !_Thread_Executing->Wait.return_code )
return length_out;
*joel* (on branch rtems-4-10-branch):
2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1890/cpukit
* psxmsgq01/init.c: POSIX says msg_prio is allowed to be NULL.
M 1.353 testsuites/psxtests/ChangeLog
M 1.125.2.3 testsuites/psxtests/ChangeLog
M 1.264.2.6 testsuites/psxtests/ChangeLog
M 1.28 testsuites/psxtests/psxmsgq01/init.c
M 1.18.2.1 testsuites/psxtests/psxmsgq01/init.c
M 1.23.2.1 testsuites/psxtests/psxmsgq01/init.c
diff -u rtems/testsuites/psxtests/ChangeLog:1.352 rtems/testsuites/psxtests/ChangeLog:1.353
--- rtems/testsuites/psxtests/ChangeLog:1.352 Thu Aug 18 02:47:37 2011
+++ rtems/testsuites/psxtests/ChangeLog Sun Aug 21 14:59:51 2011
@@ -1,3 +1,8 @@
+2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+
+ PR 1890/cpukit
+ * psxmsgq01/init.c: POSIX says msg_prio is allowed to be NULL.
+
2011-08-18 Sebastian Huber <sebastian.huber at embedded-brains.de>
* psxfatal_support/init.c: Ensure that _Thread_BSP_context is
diff -u rtems/testsuites/psxtests/ChangeLog:1.125.2.2 rtems/testsuites/psxtests/ChangeLog:1.125.2.3
--- rtems/testsuites/psxtests/ChangeLog:1.125.2.2 Sun Jul 31 17:41:16 2011
+++ rtems/testsuites/psxtests/ChangeLog Sun Aug 21 15:00:01 2011
@@ -1,3 +1,8 @@
+2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+
+ PR 1890/cpukit
+ * psxmsgq01/init.c: POSIX says msg_prio is allowed to be NULL.
+
2011-07-31 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1855/cpukit
diff -u rtems/testsuites/psxtests/ChangeLog:1.264.2.5 rtems/testsuites/psxtests/ChangeLog:1.264.2.6
--- rtems/testsuites/psxtests/ChangeLog:1.264.2.5 Sun Jul 31 17:40:53 2011
+++ rtems/testsuites/psxtests/ChangeLog Sun Aug 21 14:59:56 2011
@@ -1,3 +1,8 @@
+2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
+
+ PR 1890/cpukit
+ * psxmsgq01/init.c: POSIX says msg_prio is allowed to be NULL.
+
2011-07-31 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1855/cpukit
diff -u rtems/testsuites/psxtests/psxmsgq01/init.c:1.27 rtems/testsuites/psxtests/psxmsgq01/init.c:1.28
--- rtems/testsuites/psxtests/psxmsgq01/init.c:1.27 Fri May 6 12:29:29 2011
+++ rtems/testsuites/psxtests/psxmsgq01/init.c Sun Aug 21 14:59:51 2011
@@ -1141,11 +1141,10 @@
int is_blocking
)
{
- char message[ 100 ];
- unsigned int priority;
- struct timespec tm;
- struct timeval tv1, tv2, tv3;
- struct timezone tz1, tz2;
+ char message[ 100 ];
+ struct timespec tm;
+ struct timeval tv1, tv2, tv3;
+ struct timezone tz1, tz2;
int status;
printf(
@@ -1158,7 +1157,7 @@
tm.tv_sec = tv1.tv_sec - 1;
tm.tv_nsec = tv1.tv_usec * 1000;
- status = mq_timedreceive( Test_q[ que ].mq, message, 100, &priority, &tm );
+ status = mq_timedreceive( Test_q[ que ].mq, message, 100, NULL, &tm );
gettimeofday( &tv2, &tz2 );
tv3.tv_sec = tv2.tv_sec - tv1.tv_sec;
diff -u rtems/testsuites/psxtests/psxmsgq01/init.c:1.18 rtems/testsuites/psxtests/psxmsgq01/init.c:1.18.2.1
--- rtems/testsuites/psxtests/psxmsgq01/init.c:1.18 Fri Jul 18 13:47:30 2008
+++ rtems/testsuites/psxtests/psxmsgq01/init.c Sun Aug 21 15:00:01 2011
@@ -789,11 +789,10 @@
int is_blocking
)
{
- char message[ 100 ];
- unsigned int priority;
- struct timespec tm;
- struct timeval tv1, tv2, tv3;
- struct timezone tz1, tz2;
+ char message[ 100 ];
+ struct timespec tm;
+ struct timeval tv1, tv2, tv3;
+ struct timezone tz1, tz2;
int status;
printf(
@@ -806,7 +805,7 @@
tm.tv_sec = tv1.tv_sec + 1;
tm.tv_nsec = tv1.tv_usec * 1000;
- status = mq_timedreceive( Test_q[ que ].mq, message, 100, &priority, &tm );
+ status = mq_timedreceive( Test_q[ que ].mq, message, 100, NULL, &tm );
gettimeofday( &tv2, &tz2 );
tv3.tv_sec = tv2.tv_sec - tv1.tv_sec;
diff -u rtems/testsuites/psxtests/psxmsgq01/init.c:1.23 rtems/testsuites/psxtests/psxmsgq01/init.c:1.23.2.1
--- rtems/testsuites/psxtests/psxmsgq01/init.c:1.23 Tue Dec 8 11:52:53 2009
+++ rtems/testsuites/psxtests/psxmsgq01/init.c Sun Aug 21 14:59:56 2011
@@ -1137,11 +1137,10 @@
int is_blocking
)
{
- char message[ 100 ];
- unsigned int priority;
- struct timespec tm;
- struct timeval tv1, tv2, tv3;
- struct timezone tz1, tz2;
+ char message[ 100 ];
+ struct timespec tm;
+ struct timeval tv1, tv2, tv3;
+ struct timezone tz1, tz2;
int status;
printf(
@@ -1154,7 +1153,7 @@
tm.tv_sec = tv1.tv_sec - 1;
tm.tv_nsec = tv1.tv_usec * 1000;
- status = mq_timedreceive( Test_q[ que ].mq, message, 100, &priority, &tm );
+ status = mq_timedreceive( Test_q[ que ].mq, message, 100, NULL, &tm );
gettimeofday( &tv2, &tz2 );
tv3.tv_sec = tv2.tv_sec - tv1.tv_sec;
*joel*:
2011-08-21 Petr Benes <benesp16 at fel.cvut.cz>
PR 1886/cpukit
* sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl,
score/include/rtems/score/rbtree.h,
score/inline/rtems/score/rbtree.inl, score/src/rbtree.c,
score/src/rbtreeinsert.c: This patch enables inserting duplicate keys
into rbtree. It is possible to turn on this feature when initializing
the tree.
M 1.2907 cpukit/ChangeLog
M 1.2 cpukit/sapi/include/rtems/rbtree.h
M 1.3 cpukit/sapi/inline/rtems/rbtree.inl
M 1.6 cpukit/score/include/rtems/score/rbtree.h
M 1.3 cpukit/score/inline/rtems/score/rbtree.inl
M 1.5 cpukit/score/src/rbtree.c
M 1.4 cpukit/score/src/rbtreeinsert.c
diff -u rtems/cpukit/ChangeLog:1.2906 rtems/cpukit/ChangeLog:1.2907
--- rtems/cpukit/ChangeLog:1.2906 Sun Aug 21 14:59:03 2011
+++ rtems/cpukit/ChangeLog Sun Aug 21 15:07:10 2011
@@ -1,3 +1,13 @@
+2011-08-21 Petr Benes <benesp16 at fel.cvut.cz>
+
+ PR 1886/cpukit
+ * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl,
+ score/include/rtems/score/rbtree.h,
+ score/inline/rtems/score/rbtree.inl, score/src/rbtree.c,
+ score/src/rbtreeinsert.c: This patch enables inserting duplicate keys
+ into rbtree. It is possible to turn on this feature when initializing
+ the tree.
+
2011-08-21 Joel Sherrill <joel.sherrilL at OARcorp.com>
PR 1890/cpukit
diff -u rtems/cpukit/sapi/include/rtems/rbtree.h:1.1 rtems/cpukit/sapi/include/rtems/rbtree.h:1.2
--- rtems/cpukit/sapi/include/rtems/rbtree.h:1.1 Mon Apr 4 13:44:16 2011
+++ rtems/cpukit/sapi/include/rtems/rbtree.h Sun Aug 21 15:07:11 2011
@@ -43,6 +43,29 @@
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 rtems_rbtree_unique
+ *
+ * This enum type defines whether the tree can contain nodes with
+ * duplicate keys.
+ */
+typedef enum {
+ /** The tree is not unique, insertion of duplicate keys is performed
+ * in a FIFO manner. */
+ RTEMS_RBTREE_DUPLICATE = false,
+ /** The tree is unique, insertion of duplicate key is refused. */
+ RTEMS_RBTREE_UNIQUE = true
+} rtems_rbtree_unique;
+
+/**
* @brief RBTree initializer for an empty rbtree with designator @a name.
*/
#define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
diff -u rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.2 rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.3
--- rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.2 Tue Aug 2 14:25:59 2011
+++ rtems/cpukit/sapi/inline/rtems/rbtree.inl Sun Aug 21 15:07:11 2011
@@ -35,15 +35,16 @@
* @a starting_address. Each node is of @a node_size bytes.
*/
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
- rtems_rbtree_control *the_rbtree,
- void *compare_function,
- void *starting_address,
- size_t number_nodes,
- size_t node_size
+ rtems_rbtree_control *the_rbtree,
+ rtems_rbtree_compare_function compare_function,
+ void *starting_address,
+ size_t number_nodes,
+ size_t node_size,
+ rtems_rbtree_unique is_unique
)
{
_RBTree_Initialize( the_rbtree, compare_function, starting_address,
- number_nodes, node_size);
+ number_nodes, node_size, is_unique);
}
/**
@@ -52,11 +53,12 @@
* This routine initializes @a the_rbtree to contain zero nodes.
*/
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
- rtems_rbtree_control *the_rbtree,
- void *compare_function
+ rtems_rbtree_control *the_rbtree,
+ rtems_rbtree_compare_function compare_function,
+ rtems_rbtree_unique is_unique
)
{
- _RBTree_Initialize_empty( the_rbtree, compare_function );
+ _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
}
/**
@@ -257,6 +259,9 @@
* 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.
+ *
+ * @note If the tree is not unique and contains duplicate keys, the set
+ * of duplicate keys acts as FIFO.
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
rtems_rbtree_control *the_rbtree,
@@ -382,13 +387,27 @@
*
* This routine inserts @a the_node on @a the_rbtree.
* It disables interrupts to ensure the atomicity of the insert operation.
+ *
+ * @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.
*/
-RTEMS_INLINE_ROUTINE void rtems_rbtree_insert(
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
rtems_rbtree_control *the_rbtree,
rtems_rbtree_node *the_node
)
{
- _RBTree_Insert( the_rbtree, the_node );
+ return _RBTree_Insert( the_rbtree, the_node );
+}
+
+/** @brief Determines whether the tree is unique
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique(
+ rtems_rbtree_control *the_rbtree
+)
+{
+ return( _RBTree_Is_unique(the_rbtree) );
}
#endif
diff -u rtems/cpukit/score/include/rtems/score/rbtree.h:1.5 rtems/cpukit/score/include/rtems/score/rbtree.h:1.6
--- rtems/cpukit/score/include/rtems/score/rbtree.h:1.5 Tue Aug 2 14:25:59 2011
+++ rtems/cpukit/score/include/rtems/score/rbtree.h Sun Aug 21 15:07:11 2011
@@ -100,6 +100,16 @@
} 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.
+ */
+typedef int (*RBTree_Compare_function)(
+ RBTree_Node *node1,
+ RBTree_Node *node2
+);
+
+/**
* @struct RBTree_Control
*
* This is used to manage a RBT. A rbtree consists of a tree of zero or more
@@ -126,11 +136,13 @@
/** 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
+ * 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.
*/
- int (*compare_function) (RBTree_Node*, RBTree_Node*);
+ RBTree_Compare_function compare_function;
+ /** Determines whether the tree accepts duplicate keys. */
+ bool is_unique;
} RBTree_Control;
/**
@@ -142,7 +154,8 @@
.root = NULL, \
.first[0] = NULL, \
.first[1] = NULL, \
- .compare_function = NULL \
+ .compare_function = NULL, \
+ .is_unique = 0 \
}
/**
@@ -176,11 +189,12 @@
* @a starting_address. Each node is of @a node_size bytes.
*/
void _RBTree_Initialize(
- RBTree_Control *the_rbtree,
- void *compare_function,
- void *starting_address,
- size_t number_nodes,
- size_t node_size
+ RBTree_Control *the_rbtree,
+ RBTree_Compare_function compare_function,
+ void *starting_address,
+ size_t number_nodes,
+ size_t node_size,
+ bool is_unique
);
/**
@@ -247,8 +261,8 @@
*
* @retval 0 Successfully inserted.
* @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal value to @a the_node->value exists
- * in @a the_rbtree.
+ * @retval RBTree_Node* if one with equal value to @a the_node 's key exists
+ * in an unique @a the_rbtree.
*
* @note It does NOT disable interrupts to ensure the atomicity
* of the extract operation.
@@ -263,10 +277,15 @@
*
* This routine inserts @a the_node on the tree @a the_rbtree.
*
+ * @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
+ * in an unique @a the_rbtree.
+ *
* @note It disables interrupts to ensure the atomicity
* of the extract operation.
*/
-void _RBTree_Insert(
+RBTree_Node *_RBTree_Insert(
RBTree_Control *the_rbtree,
RBTree_Node *the_node
);
diff -u rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.2 rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.3
--- rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.2 Tue Aug 2 14:25:59 2011
+++ rtems/cpukit/score/inline/rtems/score/rbtree.inl Sun Aug 21 15:07:11 2011
@@ -235,8 +235,9 @@
* This routine initializes @a the_rbtree to contain zero nodes.
*/
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
- RBTree_Control *the_rbtree,
- void *compare_function
+ RBTree_Control *the_rbtree,
+ RBTree_Compare_function compare_function,
+ bool is_unique
)
{
the_rbtree->permanent_null = NULL;
@@ -244,6 +245,7 @@
the_rbtree->first[0] = NULL;
the_rbtree->first[1] = NULL;
the_rbtree->compare_function = compare_function;
+ the_rbtree->is_unique = is_unique;
}
/** @brief Return a pointer to node's grandparent
@@ -317,6 +319,9 @@
* This function returns a pointer to the node in @a the_rbtree
* 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.
+ *
+ * @note If the tree is not unique and contains duplicate keys, the set
+ * of duplicate keys acts as FIFO.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
RBTree_Control *the_rbtree,
@@ -324,18 +329,21 @@
)
{
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);
if (compare_result == 0) {
- return(iter_node);
+ found = iter_node;
+ if ( the_rbtree->is_unique )
+ break;
}
- RBTree_Direction dir = (compare_result != -1);
+ RBTree_Direction dir = (compare_result == 1);
iter_node = iter_node->child[dir];
} /* while(iter_node) */
- return 0;
+ return found;
}
/** @brief Find the nodes in-order predecessor
@@ -428,7 +436,6 @@
RBTree_Node *c;
if (the_node == NULL) return;
if (the_node->child[(1-dir)] == NULL) return;
-
c = the_node->child[(1-dir)];
the_node->child[(1-dir)] = c->child[dir];
@@ -443,6 +450,15 @@
c->parent = the_node->parent;
the_node->parent = c;
}
+
+/** @brief Determines whether the tree is unique
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
+ RBTree_Control *the_rbtree
+)
+{
+ return( the_rbtree && the_rbtree->is_unique );
+}
/**@}*/
#endif
diff -u rtems/cpukit/score/src/rbtree.c:1.4 rtems/cpukit/score/src/rbtree.c:1.5
--- rtems/cpukit/score/src/rbtree.c:1.4 Tue Aug 2 14:25:59 2011
+++ rtems/cpukit/score/src/rbtree.c Sun Aug 21 15:07:11 2011
@@ -32,11 +32,12 @@
*/
void _RBTree_Initialize(
- RBTree_Control *the_rbtree,
- void *compare_function,
- void *starting_address,
- size_t number_nodes,
- size_t node_size
+ RBTree_Control *the_rbtree,
+ RBTree_Compare_function compare_function,
+ void *starting_address,
+ size_t number_nodes,
+ size_t node_size,
+ bool is_unique
)
{
size_t count;
@@ -46,7 +47,7 @@
if (!the_rbtree) return;
/* could do sanity checks here */
- _RBTree_Initialize_empty(the_rbtree, compare_function);
+ _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
count = number_nodes;
next = starting_address;
diff -u rtems/cpukit/score/src/rbtreeinsert.c:1.3 rtems/cpukit/score/src/rbtreeinsert.c:1.4
--- rtems/cpukit/score/src/rbtreeinsert.c:1.3 Tue Aug 2 14:25:59 2011
+++ rtems/cpukit/score/src/rbtreeinsert.c Sun Aug 21 15:07:11 2011
@@ -72,7 +72,7 @@
* @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 @a the_rbtree.
+ * in an unique @a the_rbtree.
*
* @note It does NOT disable interrupts to ensure the atomicity
* of the extract operation.
@@ -97,7 +97,8 @@
/* 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 ( !compare_result ) return iter_node;
+ if ( the_rbtree->is_unique && !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;
@@ -138,7 +139,7 @@
* only case
*/
-void _RBTree_Insert(
+RBTree_Node *_RBTree_Insert(
RBTree_Control *tree,
RBTree_Node *node
)
@@ -146,6 +147,6 @@
ISR_Level level;
_ISR_Disable( level );
- _RBTree_Insert_unprotected( tree, node );
+ return _RBTree_Insert_unprotected( tree, node );
_ISR_Enable( level );
}
*joel*:
2011-08-21 Petr Benes <benesp16 at fel.cvut.cz>
PR 1886/cpukit
* sprbtree01/init.c, sprbtree01/sprbtree01.scn: This patch enables
inserting duplicate keys into rbtree. It is possible to turn on this
feature when initializing the tree.
M 1.474 testsuites/sptests/ChangeLog
M 1.6 testsuites/sptests/sprbtree01/init.c
M 1.4 testsuites/sptests/sprbtree01/sprbtree01.scn
diff -u rtems/testsuites/sptests/ChangeLog:1.473 rtems/testsuites/sptests/ChangeLog:1.474
--- rtems/testsuites/sptests/ChangeLog:1.473 Thu Aug 18 02:47:07 2011
+++ rtems/testsuites/sptests/ChangeLog Sun Aug 21 15:07:23 2011
@@ -1,3 +1,10 @@
+2011-08-21 Petr Benes <benesp16 at fel.cvut.cz>
+
+ PR 1886/cpukit
+ * sprbtree01/init.c, sprbtree01/sprbtree01.scn: This patch enables
+ inserting duplicate keys into rbtree. It is possible to turn on this
+ feature when initializing the tree.
+
2011-08-18 Sebastian Huber <sebastian.huber at embedded-brains.de>
* spfatal_support/init.c: Ensure that _Thread_BSP_context is
diff -u rtems/testsuites/sptests/sprbtree01/init.c:1.5 rtems/testsuites/sptests/sprbtree01/init.c:1.6
--- rtems/testsuites/sptests/sprbtree01/init.c:1.5 Tue Aug 2 16:46:20 2011
+++ rtems/testsuites/sptests/sprbtree01/init.c Sun Aug 21 15:07:23 2011
@@ -100,8 +100,14 @@
puts( "\n\n*** TEST OF RTEMS RBTREE API ***" );
puts( "Init - Initialize rbtree empty" );
- rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function );
-
+ rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function,
+ RTEMS_RBTREE_UNIQUE );
+
+ if ( !rtems_rbtree_is_unique( &rbtree1 ) )
+ puts( "INIT - FAILED IS UNIQUE CHECK" );
+ if ( rtems_rbtree_is_unique( NULL ) )
+ puts( "INIT - FAILED IS UNIQUE CHECK" );
+
/* verify that the rbtree insert work */
puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
node1.id = 1;
@@ -111,7 +117,7 @@
rtems_rbtree_insert( &rbtree1, &node1.Node );
rtems_rbtree_insert( &rbtree1, &node2.Node );
- p = _RBTree_Insert_unprotected( &rbtree1, NULL );
+ p = rtems_rbtree_insert( &rbtree1, NULL );
if (p != (void *)(-1))
puts( "INIT - FAILED NULL NODE INSERT" );
@@ -149,7 +155,11 @@
puts("INIT - Verify rtems_rbtree_insert with the same value twice");
node2.key = node1.key;
rtems_rbtree_insert(&rbtree1, &node1.Node);
- rtems_rbtree_insert(&rbtree1, &node2.Node);
+ p = rtems_rbtree_insert(&rbtree1, &node2.Node);
+
+ if (p != &node1.Node)
+ puts( "INIT - FAILED DUPLICATE INSERT" );
+
for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
test_node *t = rtems_rbtree_container_of(p,test_node,Node);
@@ -527,7 +537,8 @@
node_array[i].key = i;
}
rtems_rbtree_initialize( &rbtree1, &test_compare_function,
- &node_array[0].Node, 100, sizeof(test_node));
+ &node_array[0].Node, 100,
+ sizeof(test_node), RTEMS_RBTREE_UNIQUE );
puts( "INIT - Removing 100 nodes" );
@@ -553,6 +564,98 @@
rtems_test_exit(0);
}
+ /* Initialize the tree for duplicate keys */
+ puts( "Init - Initialize duplicate rbtree empty" );
+ rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function,
+ RTEMS_RBTREE_DUPLICATE );
+
+ if ( rtems_rbtree_is_unique( &rbtree1 ) )
+ puts( "INIT - FAILED IS UNIQUE CHECK" );
+ if ( rtems_rbtree_is_unique( NULL ) )
+ puts( "INIT - FAILED IS UNIQUE CHECK" );
+
+ 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].key = i%5;
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
+ search_node.key = 2;
+ p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) {
+ puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Removing 100 nodes" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 99 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ 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].key = (99-i)%5;
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
+ search_node.key = 2;
+ p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+ if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) {
+ puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Removing 100 nodes" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 99 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
puts( "*** END OF RTEMS RBTREE API TEST ***" );
rtems_test_exit(0);
}
diff -u rtems/testsuites/sptests/sprbtree01/sprbtree01.scn:1.3 rtems/testsuites/sptests/sprbtree01/sprbtree01.scn:1.4
--- rtems/testsuites/sptests/sprbtree01/sprbtree01.scn:1.3 Tue Aug 2 08:38:41 2011
+++ rtems/testsuites/sptests/sprbtree01/sprbtree01.scn Sun Aug 21 15:07:23 2011
@@ -24,4 +24,11 @@
INIT - Removing 20 nodes
INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]
INIT - Removing 100 nodes
+Init - Initialize duplicate rbtree empty
+INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]
+INIT - Verify rtems_rbtree_find in a duplicate tree
+INIT - Removing 100 nodes
+INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]
+INIT - Verify rtems_rbtree_find in a duplicate tree
+INIT - Removing 100 nodes
*** END OF RTEMS RBTREE API TEST ***
--
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/20110821/10dde8a3/attachment.html>
More information about the vc
mailing list