rbtree: Add and use RBTree_Compare_result

13 files changed, 81 insertions, 49 deletions

diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h
index aff9749996..ded030d3a3 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 e231299c22..67c6e27bc5 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 0848b69eb7..c008721b23 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 eaf2b6e8d5..0e2ea2c743 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 20338eb1bd..049a64d4df 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 d23808ffd4..aa84558721 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 f3af7fe6ec..451b5f453a 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 50e40bc0eb..a98fb0f9c8 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 0e139cdbc6..5931d2252b 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 f7676260dc..168a108962 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 afff1ef5f9..3bccba5aaa 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 6dfa288999..00b6181e59 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 b146ad410c..aa08541e93 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
 )