rbtree: Reduce RBTree_Control size

Remove compare function and is unique indicator from the control
structure.  Rename RBTree_Compare_function to RBTree_Compare.  Rename
rtems_rbtree_compare_function to rtems_rbtree_compare.  Provide C++
compatible initializers.  Add compare function and is unique indicator
to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
rtems_rbtree_insert().  Remove _RBTree_Is_unique() and
rtems_rbtree_is_unique().  Remove compare function and is unique
indicator from _RBTree_Initialize_empty() and
rtems_rbtree_initialize_empty().

16 files changed, 229 insertions, 216 deletions

diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h
index 6aab2449c6..b21c1d30fc 100644
--- a/cpukit/posix/include/rtems/posix/keyimpl.h
+++ b/cpukit/posix/include/rtems/posix/keyimpl.h
@@ -42,7 +42,7 @@ POSIX_EXTERN Objects_Information  _POSIX_Keys_Information;
 /**
  * @brief The rbtree control block used to manage all key values
  */
-POSIX_EXTERN RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
+extern RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
 
 /**
  * @brief This freechain is used as a memory pool for POSIX_Keys_Key_value_pair.
@@ -61,7 +61,7 @@ void _POSIX_Key_Manager_initialization(void);
  *
  * This routine compares the rbtree node
  */
-int _POSIX_Keys_Key_value_lookup_tree_compare_function(
+int _POSIX_Keys_Key_value_compare(
   const RBTree_Node *node1,
   const RBTree_Node *node2
 );
@@ -165,6 +165,23 @@ RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_pair_free(
   _Freechain_Put( &_POSIX_Keys_Keypool, key_value_pair );
 }
 
+RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Find(
+  pthread_key_t              key,
+  Objects_Id                 thread_id,
+  POSIX_Keys_Key_value_pair *search_node
+)
+{
+  search_node->key = key;
+  search_node->thread_id = thread_id;
+
+  return _RBTree_Find(
+    &_POSIX_Keys_Key_value_lookup_tree,
+    &search_node->Key_value_lookup_node,
+    _POSIX_Keys_Key_value_compare,
+    true
+  );
+}
+
 /** @} */
 
 #ifdef __cplusplus
diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
index de61b43e88..105706a92c 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -26,6 +26,8 @@
 #include <rtems/score/objectimpl.h>
 #include <rtems/score/wkspace.h>
 
+RBTREE_DEFINE_EMPTY( _POSIX_Keys_Key_value_lookup_tree );
+
 /**
  * @brief This routine compares the rbtree node by comparing POSIX key first
  * and comparing thread id second.
@@ -42,7 +44,7 @@
  * impossible
  */
 
-int _POSIX_Keys_Key_value_lookup_tree_compare_function(
+int _POSIX_Keys_Key_value_compare(
   const RBTree_Node *node1,
   const RBTree_Node *node2
 )
@@ -153,11 +155,5 @@ void _POSIX_Key_Manager_initialization(void)
 #endif
   );
 
-  _RBTree_Initialize_empty(
-      &_POSIX_Keys_Key_value_lookup_tree,
-      _POSIX_Keys_Key_value_lookup_tree_compare_function,
-      true
-  );
-
   _POSIX_Keys_Initialize_keypool();
 }
diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
index 04c914f27d..b419f1fc95 100644
--- a/cpukit/posix/src/keyfreememory.c
+++ b/cpukit/posix/src/keyfreememory.c
@@ -32,9 +32,7 @@ void _POSIX_Keys_Free_memory(
   Objects_Id key_id;
 
   key_id = the_key->Object.id;
-  search_node.key = key_id;
-  search_node.thread_id = 0;
-  iter = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree, &search_node.Key_value_lookup_node );
+  iter = _POSIX_Keys_Find( key_id, 0, &search_node );
   if ( !iter )
     return;
   /**
diff --git a/cpukit/posix/src/keygetspecific.c b/cpukit/posix/src/keygetspecific.c
index eeab2e3130..9c54112fde 100644
--- a/cpukit/posix/src/keygetspecific.c
+++ b/cpukit/posix/src/keygetspecific.c
@@ -49,19 +49,14 @@ void *pthread_getspecific(
   switch ( location ) {
 
     case OBJECTS_LOCAL:
-      search_node.key = key;
-      search_node.thread_id = _Thread_Executing->Object.id;
-      p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
-                                    &search_node.Key_value_lookup_node );
-      key_data = NULL;
-      if ( p ) {
+      p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
+      if ( p != NULL ) {
         value_pair_p = _RBTree_Container_of( p,
                                           POSIX_Keys_Key_value_pair,
                                           Key_value_lookup_node );
-        /* key_data = _RBTree_Container_of( p, */
-        /*                                  POSIX_Keys_Key_value_pair, */
-        /*                                  Key_value_lookup_node )->value; */
         key_data = value_pair_p->value;
+      } else {
+        key_data = NULL;
       }
 
       _Objects_Put( &the_key->Object );
diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
index 3284991edb..0f7c682506 100644
--- a/cpukit/posix/src/keysetspecific.c
+++ b/cpukit/posix/src/keysetspecific.c
@@ -44,12 +44,8 @@ int pthread_setspecific(
   switch ( location ) {
 
     case OBJECTS_LOCAL:
-      search_node.key = key;
-      search_node.thread_id = _Thread_Executing->Object.id;
-      p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
-                                    &search_node.Key_value_lookup_node );
-
-      if ( p ) {
+      p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
+      if ( p != NULL ) {
         value_pair_ptr = _RBTree_Container_of( p,
                                           POSIX_Keys_Key_value_pair,
                                           Key_value_lookup_node );
@@ -69,8 +65,12 @@ int pthread_setspecific(
         value_pair_ptr->value = value;
         /* The insert can only go wrong if the same node is already in a unique
          * tree. This has been already checked with the _RBTree_Find() */
-        (void) _RBTree_Insert( &_POSIX_Keys_Key_value_lookup_tree,
-                             &(value_pair_ptr->Key_value_lookup_node) );
+        _RBTree_Insert(
+          &_POSIX_Keys_Key_value_lookup_tree,
+          &value_pair_ptr->Key_value_lookup_node,
+          _POSIX_Keys_Key_value_compare,
+          true
+        );
 
         /** append rb_node to the thread API extension's chain */
         _Chain_Append_unprotected(
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
index 7e59e036a2..2005b367e7 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -55,13 +55,11 @@ typedef RBTree_Node rtems_rbtree_node;
 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 RBTree_Compare rtems_rbtree_compare;
 
 /**
  * @brief RBTree initializer for an empty rbtree with designator @a name.
@@ -93,15 +91,15 @@ typedef RBTree_Compare_function rtems_rbtree_compare_function;
  * @a starting_address.  Each node is of @a node_size bytes.
  */
 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
-  rtems_rbtree_control          *the_rbtree,
-  rtems_rbtree_compare_function  compare_function,
-  void                          *starting_address,
-  size_t                         number_nodes,
-  size_t                         node_size,
-  bool                           is_unique
+  rtems_rbtree_control *the_rbtree,
+  rtems_rbtree_compare  compare,
+  void                 *starting_address,
+  size_t                number_nodes,
+  size_t                node_size,
+  bool                  is_unique
 )
 {
-  _RBTree_Initialize( the_rbtree, compare_function, starting_address,
+  _RBTree_Initialize( the_rbtree, compare, starting_address,
     number_nodes, node_size, is_unique);
 }
 
@@ -111,12 +109,10 @@ 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_compare_function  compare_function,
-  bool                           is_unique
+  rtems_rbtree_control *the_rbtree
 )
 {
-  _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
+  _RBTree_Initialize_empty( the_rbtree );
 }
 
 /**
@@ -277,10 +273,12 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
   const rtems_rbtree_control *the_rbtree,
-  const rtems_rbtree_node *the_node
+  const rtems_rbtree_node    *the_node,
+  rtems_rbtree_compare        compare,
+  bool                        is_unique
 )
 {
-  return _RBTree_Find( the_rbtree, the_node );
+  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
 }
 
 /**
@@ -385,20 +383,12 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
   rtems_rbtree_control *the_rbtree,
-  rtems_rbtree_node *the_node
-)
-{
-  return _RBTree_Insert( the_rbtree, the_node );
-}
-
-/** 
- * @brief Determines whether the tree is unique.
- */
-RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
-  const rtems_rbtree_control *the_rbtree
+  rtems_rbtree_node    *the_node,
+  rtems_rbtree_compare  compare,
+  bool                  is_unique
 )
 {
-  return _RBTree_Is_unique(the_rbtree);
+  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
 }
 
 /** @} */
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index febd65f131..20338eb1bd 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -80,7 +80,7 @@ static void insert_into_tree(
   rtems_rbheap_chunk *chunk
 )
 {
-  _RBTree_Insert(tree, &chunk->tree_node);
+  rtems_rbtree_insert(tree, &chunk->tree_node, chunk_compare, true);
 }
 
 rtems_status_code rtems_rbheap_initialize(
@@ -107,7 +107,7 @@ rtems_status_code rtems_rbheap_initialize(
 
       rtems_chain_initialize_empty(free_chain);
       rtems_chain_initialize_empty(&control->spare_descriptor_chain);
-      rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
+      rtems_rbtree_initialize_empty(chunk_tree);
       control->alignment = alignment;
       control->handler_arg = handler_arg;
       control->extend_descriptors = extend_descriptors;
@@ -198,7 +198,7 @@ static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
   rtems_rbheap_chunk chunk = { .begin = key };
 
   return rtems_rbheap_chunk_of_node(
-    _RBTree_Find(chunk_tree, &chunk.tree_node)
+    rtems_rbtree_find(chunk_tree, &chunk.tree_node, chunk_compare, true)
   );
 }
 
@@ -230,7 +230,7 @@ static void check_and_merge(
     a->size += b->size;
     rtems_chain_extract_unprotected(&b->chain_node);
     add_to_chain(free_chain, b);
-    _RBTree_Extract(chunk_tree, &b->tree_node);
+    rtems_rbtree_extract(chunk_tree, &b->tree_node);
   }
 }
 
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 5a296b6853..a219a6e9b4 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -104,13 +104,21 @@ typedef enum {
 } 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.
+ * @brief Compares two red-black tree nodes.
+ *
+ * @param[in] first The first node.
+ * @param[in] second The second node.
+ *
+ * @retval positive The key value of the first node is greater than the one of
+ *   the second node.
+ * @retval 0 The key value of the first node is equal to the one of the second
+ *   node.
+ * @retval negative The key value of the first node is less than the one of the
+ *   second node.
  */
-typedef int (*RBTree_Compare_function)(
-  const RBTree_Node *node1,
-  const RBTree_Node *node2
+typedef int ( *RBTree_Compare )(
+  const RBTree_Node *first,
+  const RBTree_Node *second
 );
 
 /**
@@ -139,51 +147,31 @@ 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 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.
-   */
-  RBTree_Compare_function compare_function;
-  /** Determines whether the tree accepts duplicate keys. */
-  bool is_unique;
 } RBTree_Control;
 
 /**
  *  @brief RBTree initializer for an empty rbtree with designator @a name.
  */
-#define RBTREE_INITIALIZER_EMPTY(name) \
-{ \
-  .permanent_null = NULL, \
-  .root = NULL, \
-  .first[0] = NULL, \
-  .first[1] = NULL, \
-  .compare_function = NULL, \
-  .is_unique = 0 \
-}
+#define RBTREE_INITIALIZER_EMPTY( name ) \
+  { NULL, NULL, { NULL, NULL } }
 
 /**
  *  @brief RBTree definition for an empty rbtree with designator @a name.
  */
-#define RBTREE_DEFINE_EMPTY(name) \
-RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)
+#define RBTREE_DEFINE_EMPTY( name ) \
+  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
 
 /**
  *  @brief RBTree_Node initializer for an empty node with designator @a name.
  */
-#define RBTREE_NODE_INITIALIZER_EMPTY(name) \
-{ \
-  .parent = NULL, \
-  .child[0] = NULL, \
-  .child[1] = NULL, \
-  RBT_RED \
-}
+#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
+  { NULL, { NULL, NULL }, RBT_RED }
 
 /**
  *  @brief RBTree definition for an empty rbtree with designator @a name.
  */
-#define RBTREE_NODE_DEFINE_EMPTY(name) \
-RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
+#define RBTREE_NODE_DEFINE_EMPTY( name ) \
+  RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )
 
 /**
  *  @brief Initialize a RBTree Header.
@@ -193,17 +181,20 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
  *  @a starting_address.  Each node is of @a node_size bytes.
  *
  *  @param[in] the_rbtree is the pointer to rbtree header
+ *  @param[in] compare The node compare function.
  *  @param[in] starting_address is the starting address of first node
  *  @param[in] number_nodes is the number of nodes in rbtree
  *  @param[in] node_size is the size of node in bytes
+ *  @param[in] is_unique If true, then reject nodes with a duplicate key, else
+ *    otherwise.
  */
 void _RBTree_Initialize(
-  RBTree_Control          *the_rbtree,
-  RBTree_Compare_function  compare_function,
-  void                    *starting_address,
-  size_t                   number_nodes,
-  size_t                   node_size,
-  bool                     is_unique
+  RBTree_Control *the_rbtree,
+  RBTree_Compare  compare,
+  void           *starting_address,
+  size_t          number_nodes,
+  size_t          node_size,
+  bool            is_unique
 );
 
 /**
@@ -211,6 +202,10 @@ void _RBTree_Initialize(
  *
  * @param[in] the_rbtree The red-black tree control.
  * @param[in] the_node A node specifying the key.
+ * @param[in] compare The node compare function.
+ * @param[in] is_unique If true, then return the first node with a key equal to
+ *   the one of the node specified if it exits, else return the last node if it
+ *   exists.
  *
  * @retval node A node corresponding to the key.  If the tree is not unique
  * and contains duplicate keys, the set of duplicate keys acts as FIFO.
@@ -218,7 +213,9 @@ void _RBTree_Initialize(
  */
 RBTree_Node *_RBTree_Find(
   const RBTree_Control *the_rbtree,
-  const RBTree_Node *the_node
+  const RBTree_Node    *the_node,
+  RBTree_Compare        compare,
+  bool                  is_unique
 );
 
 /**
@@ -226,6 +223,12 @@ RBTree_Node *_RBTree_Find(
  *
  *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
  *
+ * @param[in] the_rbtree The red-black tree control.
+ * @param[in] the_node The node to insert.
+ * @param[in] compare The node compare function.
+ * @param[in] is_unique If true, then reject nodes with a duplicate key, else
+ *   otherwise.
+ *
  *  @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
@@ -233,7 +236,9 @@ RBTree_Node *_RBTree_Find(
  */
 RBTree_Node *_RBTree_Insert(
   RBTree_Control *the_rbtree,
-  RBTree_Node *the_node
+  RBTree_Node    *the_node,
+  RBTree_Compare  compare,
+  bool            is_unique
 );
 
 /**
@@ -437,17 +442,13 @@ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header(
  * This routine initializes @a the_rbtree to contain zero nodes.
  */
 RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
-    RBTree_Control          *the_rbtree,
-    RBTree_Compare_function  compare_function,
-    bool                     is_unique
-    )
+  RBTree_Control *the_rbtree
+)
 {
   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;
-  the_rbtree->is_unique        = is_unique;
+  the_rbtree->first[RBT_LEFT]  = NULL;
+  the_rbtree->first[RBT_RIGHT] = NULL;
 }
 
 /**
@@ -502,16 +503,6 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
   return the_node;
 }
 
-/**
- * @brief Determines whether the tree is unique.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
-  const RBTree_Control *the_rbtree
-)
-{
-  return( the_rbtree && the_rbtree->is_unique );
-}
-
 /**@}*/
 
 #ifdef __cplusplus
diff --git a/cpukit/score/include/rtems/score/scheduleredfimpl.h b/cpukit/score/include/rtems/score/scheduleredfimpl.h
index aab338edc0..019c5449c9 100644
--- a/cpukit/score/include/rtems/score/scheduleredfimpl.h
+++ b/cpukit/score/include/rtems/score/scheduleredfimpl.h
@@ -44,6 +44,11 @@ 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(
+  const RBTree_Node* n1,
+  const RBTree_Node* n2
+);
+
 RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
   const Scheduler_Control *scheduler,
   Thread_Control          *the_thread
@@ -53,7 +58,12 @@ RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
     _Scheduler_EDF_Get_context( scheduler );
   Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
 
-  _RBTree_Insert( &context->Ready, &node->Node );
+  _RBTree_Insert(
+    &context->Ready,
+    &node->Node,
+    _Scheduler_EDF_Compare,
+    false
+  );
   node->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
 }
 
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
index 958aed005a..5e8520da5e 100644
--- a/cpukit/score/src/rbtree.c
+++ b/cpukit/score/src/rbtree.c
@@ -23,12 +23,12 @@
 #include <rtems/score/isr.h>
 
 void _RBTree_Initialize(
-  RBTree_Control          *the_rbtree,
-  RBTree_Compare_function  compare_function,
-  void                    *starting_address,
-  size_t                   number_nodes,
-  size_t                   node_size,
-  bool                     is_unique
+  RBTree_Control *the_rbtree,
+  RBTree_Compare  compare,
+  void           *starting_address,
+  size_t          number_nodes,
+  size_t          node_size,
+  bool            is_unique
 )
 {
   size_t      count;
@@ -38,13 +38,12 @@ void _RBTree_Initialize(
   if (!the_rbtree) return;
 
   /* could do sanity checks here */
-  _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
+  _RBTree_Initialize_empty( the_rbtree );
 
   count = number_nodes;
   next  = starting_address;
   while ( count-- ) {
-    _RBTree_Insert(the_rbtree, next);
-    next           = (RBTree_Node *)
-                        _Addresses_Add_offset( (void *) next, node_size );
+    _RBTree_Insert( the_rbtree, next, compare, is_unique );
+    next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
   }
 }
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 4aaf236430..ad0c9fdf80 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -18,28 +18,30 @@
 #endif
 
 #include <rtems/score/rbtreeimpl.h>
-#include <rtems/score/isr.h>
 
 RBTree_Node *_RBTree_Find(
   const RBTree_Control *the_rbtree,
-  const RBTree_Node *the_node
+  const RBTree_Node    *the_node,
+  RBTree_Compare        compare,
+  bool                  is_unique
 )
 {
   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);
+
+  while ( iter_node != NULL ) {
+    int compare_result = ( *compare )( the_node, iter_node );
+    RBTree_Direction dir;
+
     if ( _RBTree_Is_equal( compare_result ) ) {
       found = iter_node;
-      if ( the_rbtree->is_unique )
+      if ( is_unique )
         break;
     }
 
-    RBTree_Direction dir =
-      (RBTree_Direction) _RBTree_Is_greater( compare_result );
-    iter_node = iter_node->child[dir];
-  } /* while(iter_node) */
+    dir = (RBTree_Direction) _RBTree_Is_greater( compare_result );
+    iter_node = iter_node->child[ dir ];
+  }
 
   return found;
 }
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 39f7c2bb09..7174529ade 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -59,24 +59,12 @@ static void _RBTree_Validate_insert(
   if(!the_node->parent->parent) the_node->color = RBT_BLACK;
 }
 
-
-
-/** @brief Insert a Node (unprotected)
- *
- *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
- *
- *  @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.
- *
- *  @note It does NOT disable interrupts to ensure the atomicity
- *        of the extract operation.
- */
 RBTree_Node *_RBTree_Insert(
-    RBTree_Control *the_rbtree,
-    RBTree_Node *the_node
-    )
+  RBTree_Control *the_rbtree,
+  RBTree_Node    *the_node,
+  RBTree_Compare  compare,
+  bool            is_unique
+)
 {
   if(!the_node) return (RBTree_Node*)-1;
 
@@ -92,8 +80,8 @@ RBTree_Node *_RBTree_Insert(
   } else {
     /* 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 ( the_rbtree->is_unique && _RBTree_Is_equal( compare_result ) )
+      compare_result = ( *compare )( the_node, iter_node );
+      if ( is_unique && _RBTree_Is_equal( compare_result ) )
         return iter_node;
       RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
       if (!iter_node->child[dir]) {
@@ -102,9 +90,9 @@ RBTree_Node *_RBTree_Insert(
         iter_node->child[dir] = the_node;
         the_node->parent = iter_node;
         /* update min/max */
-        compare_result = the_rbtree->compare_function(
-            the_node,
-            _RBTree_First(the_rbtree, dir)
+        compare_result = ( *compare )(
+          the_node,
+          _RBTree_First( the_rbtree, dir )
         );
         if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
               (dir && _RBTree_Is_greater(compare_result)) ) {
diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c
index 010d053949..01b5244cf6 100644
--- a/cpukit/score/src/scheduleredf.c
+++ b/cpukit/score/src/scheduleredf.c
@@ -20,8 +20,7 @@
 
 #include <rtems/score/scheduleredfimpl.h>
 
-static int _Scheduler_EDF_RBTree_compare_function
-(
+int _Scheduler_EDF_Compare(
   const RBTree_Node* n1,
   const RBTree_Node* n2
 )
@@ -43,9 +42,5 @@ void _Scheduler_EDF_Initialize( const Scheduler_Control *scheduler )
   Scheduler_EDF_Context *context =
     _Scheduler_EDF_Get_context( scheduler );
 
-  _RBTree_Initialize_empty(
-    &context->Ready,
-    _Scheduler_EDF_RBTree_compare_function,
-    0
-  );
+  _RBTree_Initialize_empty( &context->Ready );
 }
diff --git a/cpukit/score/src/scheduleredfchangepriority.c b/cpukit/score/src/scheduleredfchangepriority.c
index 32b0993d8f..3eabc83878 100644
--- a/cpukit/score/src/scheduleredfchangepriority.c
+++ b/cpukit/score/src/scheduleredfchangepriority.c
@@ -32,7 +32,12 @@ Scheduler_Void_or_thread _Scheduler_EDF_Change_priority(
   Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
 
   _RBTree_Extract( &context->Ready, &node->Node );
-  _RBTree_Insert( &context->Ready, &node->Node );
+  _RBTree_Insert(
+    &context->Ready,
+    &node->Node,
+    _Scheduler_EDF_Compare,
+    false
+  );
 
   SCHEDULER_RETURN_VOID_OR_NULL;
 }
diff --git a/cpukit/score/src/scheduleredfyield.c b/cpukit/score/src/scheduleredfyield.c
index 5aa2afd8db..0ad5c32c7c 100644
--- a/cpukit/score/src/scheduleredfyield.c
+++ b/cpukit/score/src/scheduleredfyield.c
@@ -35,7 +35,12 @@ Scheduler_Void_or_thread _Scheduler_EDF_Yield(
    * with the same priority in case there are such ones.
    */
   _RBTree_Extract( &context->Ready, &node->Node );
-  _RBTree_Insert( &context->Ready, &node->Node );
+  _RBTree_Insert(
+    &context->Ready,
+    &node->Node,
+    _Scheduler_EDF_Compare,
+    false
+  );
 
   _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );
 
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index abec11e860..acf7f68bbb 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -42,9 +42,41 @@ static int test_compare_function (
   return key1 - key2;
 }
 
-/* 
- * 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. 
+static rtems_rbtree_node *rb_insert_unique(
+  rtems_rbtree_control *rbtree,
+  rtems_rbtree_node    *node
+)
+{
+  return rtems_rbtree_insert( rbtree, node, test_compare_function, true );
+}
+
+static rtems_rbtree_node *rb_insert_multi(
+  rtems_rbtree_control *rbtree,
+  rtems_rbtree_node    *node
+)
+{
+  return rtems_rbtree_insert( rbtree, node, test_compare_function, false );
+}
+
+static rtems_rbtree_node *rb_find_unique(
+  rtems_rbtree_control *rbtree,
+  rtems_rbtree_node    *node
+)
+{
+  return rtems_rbtree_find( rbtree, node, test_compare_function, true );
+}
+
+static rtems_rbtree_node *rb_find_multi(
+  rtems_rbtree_control *rbtree,
+  rtems_rbtree_node    *node
+)
+{
+  return rtems_rbtree_find( rbtree, node, test_compare_function, false );
+}
+
+/*
+ * 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.
  */
 static int rb_assert ( rtems_rbtree_node *root )
 {
@@ -106,12 +138,7 @@ rtems_task Init(
   TEST_BEGIN();
 
   puts( "Init - Initialize rbtree empty" );
-  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, true );
-
-  if ( !rtems_rbtree_is_unique( &rbtree1 ) )
-    puts( "INIT - FAILED IS UNIQUE CHECK" );
-  if ( rtems_rbtree_is_unique( NULL ) )
-    puts( "INIT - FAILED IS UNIQUE CHECK" );
+  rtems_rbtree_initialize_empty( &rbtree1 );
 
   /* verify that the rbtree insert work */
   puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
@@ -119,10 +146,10 @@ rtems_task Init(
   node1.key = 1;
   node2.id = 2;
   node2.key = 2;
-  rtems_rbtree_insert( &rbtree1, &node1.Node );
-  rtems_rbtree_insert( &rbtree1, &node2.Node );
+  rb_insert_unique( &rbtree1, &node1.Node );
+  rb_insert_unique( &rbtree1, &node2.Node );
 
-  p = rtems_rbtree_insert( &rbtree1, NULL );
+  p = rb_insert_unique( &rbtree1, NULL );
   if (p != (void *)(-1))
     puts( "INIT - FAILED NULL NODE INSERT" );
 
@@ -159,8 +186,8 @@ rtems_task Init(
 
   puts("INIT - Verify rtems_rbtree_insert with the same value twice");
   node2.key = node1.key;
-  rtems_rbtree_insert(&rbtree1, &node1.Node);
-  p = rtems_rbtree_insert(&rbtree1, &node2.Node);
+  rb_insert_unique(&rbtree1, &node1.Node);
+  p = rb_insert_unique(&rbtree1, &node2.Node);
 
   if (p != &node1.Node)
     puts( "INIT - FAILED DUPLICATE INSERT" );
@@ -218,8 +245,8 @@ rtems_task Init(
   node1.key = 2;
   node2.id = 1;
   node2.key = 1;
-  rtems_rbtree_insert( &rbtree1, &node1.Node );
-  rtems_rbtree_insert( &rbtree1, &node2.Node );
+  rb_insert_unique( &rbtree1, &node1.Node );
+  rb_insert_unique( &rbtree1, &node2.Node );
 
   puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
   test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1),
@@ -237,7 +264,7 @@ rtems_task Init(
     puts( "INIT - rtems_rbtree_extract failed");
     rtems_test_exit(0);
   }
-  rtems_rbtree_insert(&rbtree1, p);
+  rb_insert_unique(&rbtree1, p);
 
   for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
@@ -256,7 +283,7 @@ rtems_task Init(
   for (i = 0; i < 100; i++) {
     node_array[i].id = i;
     node_array[i].key = i;
-    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+    rb_insert_unique( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -289,7 +316,7 @@ rtems_task Init(
   for (i = 0; i < 100; i++) {
     node_array[i].id = 99-i;
     node_array[i].key = 99-i;
-    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+    rb_insert_unique( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -324,7 +351,7 @@ rtems_task Init(
   for (i = 0; i < 100; i++) {
     node_array[i].id = i;
     node_array[i].key = i;
-    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+    rb_insert_unique( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -376,13 +403,13 @@ rtems_task Init(
     node_array[i].id = i;
     node_array[i].key = i;
   }
-  rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
-  rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
-  rtems_rbtree_insert( &rbtree1, &node_array[5].Node );
-  rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
-  rtems_rbtree_insert( &rbtree1, &node_array[2].Node );
-  rtems_rbtree_insert( &rbtree1, &node_array[4].Node );
-  rtems_rbtree_insert( &rbtree1, &node_array[6].Node );
+  rb_insert_unique( &rbtree1, &node_array[3].Node );
+  rb_insert_unique( &rbtree1, &node_array[1].Node );
+  rb_insert_unique( &rbtree1, &node_array[5].Node );
+  rb_insert_unique( &rbtree1, &node_array[0].Node );
+  rb_insert_unique( &rbtree1, &node_array[2].Node );
+  rb_insert_unique( &rbtree1, &node_array[4].Node );
+  rb_insert_unique( &rbtree1, &node_array[6].Node );
   rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
   /* node_array[1] has now only a left child. */
   if ( !node_array[1].Node.child[RBT_LEFT] ||
@@ -395,7 +422,7 @@ rtems_task Init(
   for (i = 0; i < 100; i++) {
     node_array[i].id = 99-i;
     node_array[i].key = 99-i;
-    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+    rb_insert_unique( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -428,7 +455,7 @@ rtems_task Init(
   for (i = 0; i < 100; i++) {
     node_array[i].id = i;
     node_array[i].key = i;
-    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+    rb_insert_unique( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -436,7 +463,7 @@ rtems_task Init(
 
   puts( "INIT - Verify rtems_rbtree_find" );
   search_node.key = 30;
-  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+  p = rb_find_unique(&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);
@@ -448,14 +475,14 @@ rtems_task Init(
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);
   }
-  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+  p = rb_find_unique(&rbtree1, &search_node.Node);
   p = rtems_rbtree_successor(p);
   if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);
   }
 
-  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+  p = rb_find_unique(&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");
@@ -509,7 +536,7 @@ rtems_task Init(
   for (i = 0; i < 20; i++) {
     node_array[i].id = numbers[i];
     node_array[i].key = numbers[i];
-    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+    rb_insert_unique( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -573,18 +600,13 @@ rtems_task Init(
 
   /* Initialize the tree for duplicate keys */
   puts( "Init - Initialize duplicate rbtree empty" );
-  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, false );
-
-  if ( rtems_rbtree_is_unique( &rbtree1 ) )
-    puts( "INIT - FAILED IS UNIQUE CHECK" );
-  if ( rtems_rbtree_is_unique( NULL ) )
-    puts( "INIT - FAILED IS UNIQUE CHECK" );
+  rtems_rbtree_initialize_empty( &rbtree1 );
 
   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 );
+    rb_insert_multi( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -592,7 +614,7 @@ rtems_task Init(
 
   puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
   search_node.key = 2;
-  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+  p = rb_find_multi(&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);
@@ -625,7 +647,7 @@ rtems_task Init(
   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 );
+    rb_insert_multi( &rbtree1, &node_array[i].Node );
 
     if (!rb_assert(rbtree1.root) )
       puts( "INIT - FAILED TREE CHECK" );
@@ -633,7 +655,7 @@ rtems_task Init(
 
   puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
   search_node.key = 2;
-  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
+  p = rb_find_multi(&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);