[PATCH 2/3] rbtree: Add and use RBTree_Compare_result
Sebastian Huber
sebastian.huber at embedded-brains.de
Sun Aug 3 12:45:05 UTC 2014
---
cpukit/posix/include/rtems/posix/keyimpl.h | 2 +-
cpukit/posix/src/key.c | 4 +-
cpukit/sapi/include/rtems/rbheap.h | 1 -
cpukit/sapi/include/rtems/rbtree.h | 9 ++-
cpukit/sapi/src/rbheap.c | 70 ++++++++++++----------
cpukit/score/include/rtems/score/rbtree.h | 11 +++-
cpukit/score/include/rtems/score/rbtreeimpl.h | 8 ++-
.../score/include/rtems/score/scheduleredfimpl.h | 2 +-
cpukit/score/include/rtems/score/threadqimpl.h | 2 +-
cpukit/score/src/rbtreefind.c | 4 +-
cpukit/score/src/rbtreeinsert.c | 13 +++-
cpukit/score/src/scheduleredf.c | 2 +-
cpukit/score/src/threadq.c | 2 +-
testsuites/libtests/rbheap01/init.c | 17 ------
testsuites/sptests/sprbtree01/init.c | 2 +-
15 files changed, 82 insertions(+), 67 deletions(-)
diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h
index aff9749..ded030d 100644
--- a/cpukit/posix/include/rtems/posix/keyimpl.h
+++ b/cpukit/posix/include/rtems/posix/keyimpl.h
@@ -64,7 +64,7 @@ void _POSIX_Key_Manager_initialization(void);
*
* This routine compares the rbtree node
*/
-int _POSIX_Keys_Key_value_compare(
+RBTree_Compare_result _POSIX_Keys_Key_value_compare(
const RBTree_Node *node1,
const RBTree_Node *node2
);
diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
index e231299..67c6e27 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -44,7 +44,7 @@ RBTREE_DEFINE_EMPTY( _POSIX_Keys_Key_value_lookup_tree );
* impossible
*/
-int _POSIX_Keys_Key_value_compare(
+RBTree_Compare_result _POSIX_Keys_Key_value_compare(
const RBTree_Node *node1,
const RBTree_Node *node2
)
@@ -52,7 +52,7 @@ int _POSIX_Keys_Key_value_compare(
POSIX_Keys_Key_value_pair *n1;
POSIX_Keys_Key_value_pair *n2;
Objects_Id thread_id1, thread_id2;
- int diff;
+ RBTree_Compare_result diff;
n1 = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node1 );
n2 = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node2 );
diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h
index 0848b69..c008721 100644
--- a/cpukit/sapi/include/rtems/rbheap.h
+++ b/cpukit/sapi/include/rtems/rbheap.h
@@ -154,7 +154,6 @@ struct rtems_rbheap_control {
* @param[in] handler_arg The handler argument.
*
* @retval RTEMS_SUCCESSFUL Successful operation.
- * @retval RTEMS_INVALID_NUMBER The alignment is not positive.
* @retval RTEMS_INVALID_ADDRESS The memory area is invalid.
* @retval RTEMS_NO_MEMORY Not enough chunk descriptors.
*/
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
index eaf2b6e..0e2ea2c 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -55,9 +55,12 @@ typedef RBTree_Node rtems_rbtree_node;
typedef RBTree_Control rtems_rbtree_control;
/**
- * 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.
+ * @copydoc RBTree_Compare_result
+ */
+typedef RBTree_Compare_result rtems_rbtree_compare_result;
+
+/**
+ * @copydoc RBTree_Compare
*/
typedef RBTree_Compare rtems_rbtree_compare;
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index 20338eb..049a64d 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -46,12 +46,16 @@ static uintptr_t align_down(uintptr_t alignment, uintptr_t value)
return value - excess;
}
-static int chunk_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
+static rtems_rbtree_compare_result chunk_compare(
+ const rtems_rbtree_node *a,
+ const rtems_rbtree_node *b
+)
{
const rtems_rbheap_chunk *left = rtems_rbheap_chunk_of_node(a);
const rtems_rbheap_chunk *right = rtems_rbheap_chunk_of_node(b);
- return (int) (left->begin - right->begin);
+ return (rtems_rbtree_compare_result)
+ ((left->begin >> 1) - (right->begin >> 1));
}
static rtems_rbheap_chunk *get_chunk(rtems_rbheap_control *control)
@@ -93,39 +97,43 @@ rtems_status_code rtems_rbheap_initialize(
)
{
rtems_status_code sc = RTEMS_SUCCESSFUL;
+ uintptr_t begin = (uintptr_t) area_begin;
+ uintptr_t end = begin + area_size;
+ uintptr_t aligned_begin;
+ uintptr_t aligned_end;
- if (alignment > 0) {
- uintptr_t begin = (uintptr_t) area_begin;
- uintptr_t end = begin + area_size;
- uintptr_t aligned_begin = align_up(alignment, begin);
- uintptr_t aligned_end = align_down(alignment, end);
-
- if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
- rtems_chain_control *free_chain = &control->free_chunk_chain;
- rtems_rbtree_control *chunk_tree = &control->chunk_tree;
- rtems_rbheap_chunk *first = NULL;
-
- rtems_chain_initialize_empty(free_chain);
- rtems_chain_initialize_empty(&control->spare_descriptor_chain);
- rtems_rbtree_initialize_empty(chunk_tree);
- control->alignment = alignment;
- control->handler_arg = handler_arg;
- control->extend_descriptors = extend_descriptors;
-
- first = get_chunk(control);
- if (first != NULL) {
- first->begin = aligned_begin;
- first->size = aligned_end - aligned_begin;
- add_to_chain(free_chain, first);
- insert_into_tree(chunk_tree, first);
- } else {
- sc = RTEMS_NO_MEMORY;
- }
+ /*
+ * Ensure that the alignment is at least two, so that we can keep
+ * chunk_compare() that simple.
+ */
+ alignment = alignment < 2 ? 2 : alignment;
+
+ aligned_begin = align_up(alignment, begin);
+ aligned_end = align_down(alignment, end);
+
+ if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
+ rtems_chain_control *free_chain = &control->free_chunk_chain;
+ rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+ rtems_rbheap_chunk *first = NULL;
+
+ rtems_chain_initialize_empty(free_chain);
+ rtems_chain_initialize_empty(&control->spare_descriptor_chain);
+ rtems_rbtree_initialize_empty(chunk_tree);
+ control->alignment = alignment;
+ control->handler_arg = handler_arg;
+ control->extend_descriptors = extend_descriptors;
+
+ first = get_chunk(control);
+ if (first != NULL) {
+ first->begin = aligned_begin;
+ first->size = aligned_end - aligned_begin;
+ add_to_chain(free_chain, first);
+ insert_into_tree(chunk_tree, first);
} else {
- sc = RTEMS_INVALID_ADDRESS;
+ sc = RTEMS_NO_MEMORY;
}
} else {
- sc = RTEMS_INVALID_NUMBER;
+ sc = RTEMS_INVALID_ADDRESS;
}
return sc;
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index d23808f..aa84558 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -90,6 +90,15 @@ typedef enum {
} RBTree_Direction;
/**
+ * @brief Integer type for compare results.
+ *
+ * The type is large enough to represent pointers and 32-bit signed integers.
+ *
+ * @see RBTree_Compare.
+ */
+typedef long RBTree_Compare_result;
+
+/**
* @brief Compares two red-black tree nodes.
*
* @param[in] first The first node.
@@ -102,7 +111,7 @@ typedef enum {
* @retval negative The key value of the first node is less than the one of the
* second node.
*/
-typedef int ( *RBTree_Compare )(
+typedef RBTree_Compare_result ( *RBTree_Compare )(
const RBTree_Node *first,
const RBTree_Node *second
);
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
index f3af7fe..451b5f4 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -144,20 +144,22 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
return _RBTree_Sibling(the_node->parent);
}
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
+ RBTree_Compare_result compare_result
+)
{
return compare_result == 0;
}
RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
- int compare_result
+ RBTree_Compare_result compare_result
)
{
return compare_result > 0;
}
RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
- int compare_result
+ RBTree_Compare_result compare_result
)
{
return compare_result < 0;
diff --git a/cpukit/score/include/rtems/score/scheduleredfimpl.h b/cpukit/score/include/rtems/score/scheduleredfimpl.h
index 50e40bc..a98fb0f 100644
--- a/cpukit/score/include/rtems/score/scheduleredfimpl.h
+++ b/cpukit/score/include/rtems/score/scheduleredfimpl.h
@@ -44,7 +44,7 @@ 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(
+RBTree_Compare_result _Scheduler_EDF_Compare(
const RBTree_Node* n1,
const RBTree_Node* n2
);
diff --git a/cpukit/score/include/rtems/score/threadqimpl.h b/cpukit/score/include/rtems/score/threadqimpl.h
index 0e139cd..5931d22 100644
--- a/cpukit/score/include/rtems/score/threadqimpl.h
+++ b/cpukit/score/include/rtems/score/threadqimpl.h
@@ -260,7 +260,7 @@ void _Thread_queue_Process_timeout(
* @retval 0 The @left node is of equal importance with @right node.
* @retval 1 The @left node is less important than @right node.
*/
-int _Thread_queue_Compare_priority(
+RBTree_Compare_result _Thread_queue_Compare_priority(
const RBTree_Node *left,
const RBTree_Node *right
);
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index f767626..168a108 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -30,8 +30,8 @@ RBTree_Node *_RBTree_Find(
RBTree_Node *found = NULL;
while ( iter_node != NULL ) {
- int compare_result = ( *compare )( the_node, iter_node );
- RBTree_Direction dir;
+ RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node );
+ RBTree_Direction dir;
if ( _RBTree_Is_equal( compare_result ) ) {
found = iter_node;
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index afff1ef..3bccba5 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -12,6 +12,16 @@
#include <rtems/score/rbtreeimpl.h>
+RTEMS_STATIC_ASSERT(
+ sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ),
+ RBTree_Compare_result_intptr_t
+);
+
+RTEMS_STATIC_ASSERT(
+ sizeof( RBTree_Compare_result ) >= sizeof( int32_t ),
+ RBTree_Compare_result_int32_t
+);
+
/** @brief Validate and fix-up tree properties for a new insert/colored node
*
* This routine checks and fixes the Red-Black Tree properties based on
@@ -77,7 +87,8 @@ RBTree_Node *_RBTree_Insert(
} else {
/* typical binary search tree insert, descend tree to leaf and insert */
while ( iter_node ) {
- int compare_result = ( *compare )( the_node, iter_node );
+ RBTree_Compare_result compare_result =
+ ( *compare )( the_node, iter_node );
if ( is_unique && _RBTree_Is_equal( compare_result ) )
return iter_node;
diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c
index 231bc04..cdcdab5 100644
--- a/cpukit/score/src/scheduleredf.c
+++ b/cpukit/score/src/scheduleredf.c
@@ -20,7 +20,7 @@
#include <rtems/score/scheduleredfimpl.h>
-int _Scheduler_EDF_Compare(
+RBTree_Compare_result _Scheduler_EDF_Compare(
const RBTree_Node* n1,
const RBTree_Node* n2
)
diff --git a/cpukit/score/src/threadq.c b/cpukit/score/src/threadq.c
index b146ad4..aa08541 100644
--- a/cpukit/score/src/threadq.c
+++ b/cpukit/score/src/threadq.c
@@ -24,7 +24,7 @@
#include <rtems/score/scheduler.h>
#include <rtems/score/threadimpl.h>
-int _Thread_queue_Compare_priority(
+RBTree_Compare_result _Thread_queue_Compare_priority(
const RBTree_Node *left,
const RBTree_Node *right
)
diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c
index 93813b8..6fd86db 100644
--- a/testsuites/libtests/rbheap01/init.c
+++ b/testsuites/libtests/rbheap01/init.c
@@ -94,22 +94,6 @@ static bool chunk_visitor(
return false;
}
-static void test_init_chunk_alignment(void)
-{
- rtems_status_code sc = RTEMS_SUCCESSFUL;
- rtems_rbheap_control control;
-
- sc = rtems_rbheap_initialize(
- &control,
- area,
- sizeof(area),
- 0,
- extend_descriptors,
- NULL
- );
- rtems_test_assert(sc == RTEMS_INVALID_NUMBER);
-}
-
static void test_init_begin_greater_than_end(void)
{
rtems_status_code sc = RTEMS_SUCCESSFUL;
@@ -597,7 +581,6 @@ static void Init(rtems_task_argument arg)
{
TEST_BEGIN();
- test_init_chunk_alignment();
test_init_begin_greater_than_end();
test_init_begin_greater_than_aligned_begin();
test_init_aligned_begin_greater_than_aligned_end();
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index d78790f..2dd08f5 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -33,7 +33,7 @@ typedef struct {
rtems_rbtree_node Node;
} test_node;
-static int test_compare_function (
+static rtems_rbtree_compare_result test_compare_function (
const rtems_rbtree_node *n1,
const rtems_rbtree_node *n2
)
--
1.8.1.4
More information about the devel
mailing list