score: Create rbtree implementation header

Move implementation specific parts of rbtree.h and rbtree.inl into new
header file rbtreeimpl.h.  The rbtree.h contains now only the
application visible API.

11 files changed, 553 insertions, 561 deletions

diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index cb5628ab63..c2ea6bf3f0 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -40,6 +40,7 @@ include_rtems_score_HEADERS += include/rtems/score/percpu.h
 include_rtems_score_HEADERS += include/rtems/score/priority.h
 include_rtems_score_HEADERS += include/rtems/score/prioritybitmap.h
 include_rtems_score_HEADERS += include/rtems/score/rbtree.h
+include_rtems_score_HEADERS += include/rtems/score/rbtreeimpl.h
 include_rtems_score_HEADERS += include/rtems/score/scheduler.h
 include_rtems_score_HEADERS += include/rtems/score/schedulercbs.h
 include_rtems_score_HEADERS += include/rtems/score/scheduleredf.h
@@ -96,7 +97,6 @@ include_rtems_score_HEADERS += inline/rtems/score/heap.inl
 include_rtems_score_HEADERS += inline/rtems/score/object.inl
 include_rtems_score_HEADERS += inline/rtems/score/priority.inl
 include_rtems_score_HEADERS += inline/rtems/score/prioritybitmap.inl
-include_rtems_score_HEADERS += inline/rtems/score/rbtree.inl
 include_rtems_score_HEADERS += inline/rtems/score/scheduler.inl
 include_rtems_score_HEADERS += inline/rtems/score/schedulerpriority.inl
 include_rtems_score_HEADERS += inline/rtems/score/schedulersimple.inl
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 55b5c55720..1414bdf04f 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -20,6 +20,12 @@
 
 #include <stddef.h>
 
+#include <rtems/score/address.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 /**
  *  @defgroup ScoreRBTree Red-Black Tree Handler
  *
@@ -33,12 +39,6 @@
  */
 /**@{*/
 
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#include <rtems/score/address.h>
-
 /**
  *  @typedef RBTree_Node
  *
@@ -363,47 +363,337 @@ RBTree_Node *_RBTree_Next(
 );
 
 /**
- * @brief Red-black tree visitor.
+ * @brief Set off RBtree.
  *
- * @param[in] node The node.
- * @param[in] dir The direction.
- * @param[in] visitor_arg The visitor argument.
+ * This function sets the parent and child fields of the @a node to NULL
+ * indicating the @a node is not part of a rbtree.
  *
- * @retval true Stop the iteration.
- * @retval false Continue the iteration.
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
+    RBTree_Node *node
+    )
+{
+  node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
+}
+
+/**
+ * @brief Is the node off RBTree.
  *
- * @see _RBTree_Iterate_unprotected().
+ * This function returns true if the @a node is not on a rbtree. A @a node is
+ * off rbtree if the parent and child fields are set to NULL.
  */
-typedef bool (*RBTree_Visitor)(
-  const RBTree_Node *node,
-  RBTree_Direction dir,
-  void *visitor_arg
-);
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
+    const RBTree_Node *node
+    )
+{
+  return (node->parent == NULL) &&
+         (node->child[RBT_LEFT] == NULL) &&
+         (node->child[RBT_RIGHT] == NULL);
+}
 
 /**
- * @brief Red-black tree iteration.
+ * @brief Are two Nodes equal.
  *
- * @param[in] rbtree The red-black tree.
- * @param[in] dir The direction.
- * @param[in] visitor The visitor.
- * @param[in] visitor_arg The visitor argument.
- */
-void _RBTree_Iterate_unprotected(
-  const RBTree_Control *rbtree,
-  RBTree_Direction dir,
-  RBTree_Visitor visitor,
-  void *visitor_arg
-);
+ * This function returns true if @a left and @a right are equal,
+ * and false otherwise.
+ *
+ * @retval true @a left and @a right are equal.
+ * @retval false @a left and @a right are not equal.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
+    const RBTree_Node *left,
+    const RBTree_Node *right
+    )
+{
+  return left == right;
+}
 
-#ifndef __RTEMS_APPLICATION__
-#include <rtems/score/rbtree.inl>
-#endif
+/**
+ * @brief Is the RBTree node pointer NUL.
+ *
+ * This function returns true if @a the_node is NULL and false otherwise.
+ *
+ * @retval true @a the_node is @c NULL.
+ * @retval false @a the_node is not @c NULL.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node(
+    const RBTree_Node *the_node
+    )
+{
+  return (the_node == NULL);
+}
 
-#ifdef __cplusplus
+/**
+ * @brief Return pointer to RBTree's root node.
+ *
+ * This function returns a pointer to the root node of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
+  const RBTree_Control *the_rbtree
+)
+{
+  return the_rbtree->root;
+}
+
+/**
+ * @brief Return pointer to RBTree's first node.
+ *
+ * This function returns a pointer to the first node on @a the_rbtree,
+ * where @a dir specifies whether to return the minimum (0) or maximum (1).
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
+  const RBTree_Control *the_rbtree,
+  RBTree_Direction dir
+)
+{
+  return the_rbtree->first[dir];
+}
+
+/**
+ * @brief Return pointer to the parent of this node.
+ *
+ * This function returns a pointer to the parent node of @a the_node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
+  const RBTree_Node *the_node
+)
+{
+  if (!the_node->parent->parent) return NULL;
+  return the_node->parent;
+}
+
+/**
+ * @brief Return pointer to the left of this node.
+ *
+ * This function returns a pointer to the left node of this node.
+ *
+ * @param[in] the_node is the node to be operated upon.
+ *
+ * @return This method returns the left node on the rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
+  const RBTree_Node *the_node
+)
+{
+  return the_node->child[RBT_LEFT];
+}
+
+/**
+ * @brief Return pointer to the right of this node.
+ *
+ * This function returns a pointer to the right node of this node.
+ *
+ * @param[in] the_node is the node to be operated upon.
+ *
+ * @return This method returns the right node on the rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
+  const RBTree_Node *the_node
+)
+{
+  return the_node->child[RBT_RIGHT];
+}
+
+/**
+ * @brief Is the RBTree empty.
+ *
+ * This function returns true if there are no nodes on @a the_rbtree and
+ * false otherwise.
+ *
+ * @param[in] the_rbtree is the rbtree to be operated upon.
+ *
+ * @retval true There are no nodes on @a the_rbtree.
+ * @retval false There are nodes on @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
+  const RBTree_Control *the_rbtree
+)
+{
+  return (the_rbtree->root == NULL);
+}
+
+/**
+ * @brief Is this the first node on the RBTree.
+ *
+ * This function returns true if @a the_node is the first node on
+ * @a the_rbtree and false otherwise. @a dir specifies whether first means
+ * minimum (0) or maximum (1).
+ *
+ * @retval true @a the_node is the first node on @a the_rbtree.
+ * @retval false @a the_node is not the first node on @a the_rbtree.
+ *
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
+  const RBTree_Control *the_rbtree,
+  const RBTree_Node *the_node,
+  RBTree_Direction dir
+)
+{
+  return (the_node == _RBTree_First(the_rbtree, dir));
+}
+
+/**
+ * @brief Does this RBTree have only one node.
+ *
+ * This function returns true if there is only one node on @a the_rbtree and
+ * false otherwise.
+ *
+ * @retval true @a the_rbtree has only one node.
+ * @retval false @a the_rbtree has more than one nodes.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node(
+    const RBTree_Control *the_rbtree
+    )
+{
+  if(!the_rbtree) return false; /* TODO: expected behavior? */
+  return (the_rbtree->root->child[RBT_LEFT] == NULL &&
+          the_rbtree->root->child[RBT_RIGHT] == NULL);
+}
+
+/**
+ * @brief Is this node the RBTree root.
+ *
+ * This function returns true if @a the_node is the root of @a the_rbtree and
+ * false otherwise.
+ *
+ * @retval true @a the_node is the root of @a the_rbtree.
+ * @retval false @a the_node is not the root of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
+  const RBTree_Control *the_rbtree,
+  const RBTree_Node    *the_node
+)
+{
+  return (the_node == _RBTree_Root(the_rbtree));
+}
+
+/**
+ * @brief Find the RBTree_Control header given a node in the tree.
+ *
+ * This function returns a pointer to the header of the Red Black
+ * Tree containing @a the_node if it exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
+    RBTree_Node *the_node
+    )
+{
+  if(!the_node) return NULL;
+  if(!(the_node->parent)) return NULL;
+  while(the_node->parent) the_node = the_node->parent;
+  return (RBTree_Control*)the_node;
+}
+
+/**
+ * @brief Initialize this RBTree as empty.
+ *
+ * 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
+    )
+{
+  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;
+}
+
+/**
+ * @brief Returns the predecessor of a node.
+ *
+ * @param[in] node is the node.
+ *
+ * @retval NULL The predecessor does not exist.  Otherwise it returns
+ *         the predecessor node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
+  const RBTree_Node *node
+)
+{
+  return _RBTree_Next_unprotected( node, RBT_LEFT );
+}
+
+/**
+ * @copydoc _RBTree_Predecessor_unprotected()
+ *
+ * The function disables the interrupts protect the operation.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
+  const RBTree_Node *node
+)
+{
+  return _RBTree_Next( node, RBT_LEFT );
+}
+
+/**
+ * @brief Returns the successor of a node.
+ *
+ * @param[in] node is the node.
+ *
+ * @retval NULL The successor does not exist.  Otherwise the successor node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
+  const RBTree_Node *node
+)
+{
+  return _RBTree_Next_unprotected( node, RBT_RIGHT );
+}
+
+/**
+ * @copydoc _RBTree_Successor_unprotected()
+ *
+ * The function disables the interrupts protect the operation.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
+  const RBTree_Node *node
+)
+{
+  return _RBTree_Next( node, RBT_RIGHT );
+}
+
+/**
+ * @brief Get the first node (unprotected).
+ *
+ * This function removes the minimum or maximum node from the_rbtree and
+ * returns a pointer to that node.  It does NOT disable interrupts to ensure
+ * the atomicity of the get operation.
+ *
+ * @param[in] the_rbtree is the rbtree to attempt to get the min node from.
+ * @param[in] dir specifies whether to get minimum (0) or maximum (1)
+ *
+ * @return This method returns the min or max node on the rbtree, or NULL.
+ *
+ * @note This routine may return NULL if the RBTree is empty.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
+    RBTree_Control *the_rbtree,
+    RBTree_Direction dir
+    )
+{
+  RBTree_Node *the_node = the_rbtree->first[dir];
+  _RBTree_Extract_unprotected(the_rbtree, the_node);
+  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 );
 }
-#endif
 
 /**@}*/
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif
 /* end of include file */
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
new file mode 100644
index 0000000000..30d55d2fb9
--- /dev/null
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -0,0 +1,217 @@
+/**
+ * @file
+ *
+ * @brief Inlined Routines Associated with Red-Black Trees
+ *
+ * This include file contains the bodies of the routines which are
+ * associated with Red-Black Trees and inlined.
+ *
+ * @note  The routines in this file are ordered from simple
+ *        to complex.  No other RBTree Handler routine is referenced
+ *        unless it has already been defined.
+ */
+
+/*
+ *  Copyright (c) 2010-2012 Gedare Bloom.
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ */
+
+#ifndef _RTEMS_SCORE_RBTREEIMPL_H
+#define _RTEMS_SCORE_RBTREEIMPL_H
+
+#include <rtems/score/rbtree.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @addtogroup ScoreRBTree
+ */
+/**@{**/
+
+/**
+ * @brief Red-black tree visitor.
+ *
+ * @param[in] node The node.
+ * @param[in] dir The direction.
+ * @param[in] visitor_arg The visitor argument.
+ *
+ * @retval true Stop the iteration.
+ * @retval false Continue the iteration.
+ *
+ * @see _RBTree_Iterate_unprotected().
+ */
+typedef bool (*RBTree_Visitor)(
+  const RBTree_Node *node,
+  RBTree_Direction dir,
+  void *visitor_arg
+);
+
+/**
+ * @brief Red-black tree iteration.
+ *
+ * @param[in] rbtree The red-black tree.
+ * @param[in] dir The direction.
+ * @param[in] visitor The visitor.
+ * @param[in] visitor_arg The visitor argument.
+ */
+void _RBTree_Iterate_unprotected(
+  const RBTree_Control *rbtree,
+  RBTree_Direction dir,
+  RBTree_Visitor visitor,
+  void *visitor_arg
+);
+
+/**
+ * @brief Get the direction opposite to @a the_dir.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
+  RBTree_Direction the_dir
+)
+{
+  return (RBTree_Direction) !((int) the_dir);
+}
+
+/**
+ * @brief Is this RBTree control pointer NULL.
+ *
+ * This function returns true if @a the_rbtree is NULL and false otherwise.
+ *
+ * @retval true @a the_rbtree is @c NULL.
+ * @retval false @a the_rbtree is not @c NULL.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
+    const RBTree_Control *the_rbtree
+    )
+{
+  return (the_rbtree == NULL);
+}
+
+/**
+ * @brief Is this node red.
+ *
+ * This function returns true if @a the_node is red and false otherwise.
+ *
+ * @retval true @a the_node is red.
+ * @retval false @a the_node in not red.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
+    const RBTree_Node *the_node
+    )
+{
+  return (the_node && the_node->color == RBT_RED);
+}
+
+/**
+ * @brief Return a pointer to node's grandparent.
+ *
+ * This function returns a pointer to the grandparent of @a the_node if it
+ * exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
+  const RBTree_Node *the_node
+)
+{
+  if(!the_node) return NULL;
+  if(!(the_node->parent)) return NULL;
+  if(!(the_node->parent->parent)) return NULL;
+  if(!(the_node->parent->parent->parent)) return NULL;
+  return(the_node->parent->parent);
+}
+
+/**
+ * @brief Return a pointer to node's sibling.
+ *
+ * This function returns a pointer to the sibling of @a the_node if it
+ * exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
+  const RBTree_Node *the_node
+)
+{
+  if(!the_node) return NULL;
+  if(!(the_node->parent)) return NULL;
+  if(!(the_node->parent->parent)) return NULL;
+
+  if(the_node == the_node->parent->child[RBT_LEFT])
+    return the_node->parent->child[RBT_RIGHT];
+  else
+    return the_node->parent->child[RBT_LEFT];
+}
+
+/**
+ * @brief Return a pointer to node's parent's sibling.
+ *
+ * This function returns a pointer to the sibling of the parent of
+ * @a the_node if it exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
+  const RBTree_Node *the_node
+)
+{
+  if(!the_node) return NULL;
+  if(_RBTree_Grandparent(the_node) == NULL) return NULL;
+
+  return _RBTree_Sibling(the_node->parent);
+}
+
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
+{
+  return compare_result == 0;
+}
+
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
+  int compare_result
+)
+{
+  return compare_result > 0;
+}
+
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
+  int compare_result
+)
+{
+  return compare_result < 0;
+}
+
+/**
+ * @brief Rotate the_node in the direction passed as second argument.
+ *
+ * This routine rotates @a the_node to the direction @a dir, swapping
+ * @a the_node with its child\[@a dir\].
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
+    RBTree_Node *the_node,
+    RBTree_Direction dir
+    )
+{
+  RBTree_Node *c;
+  if (the_node == NULL) return;
+  if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
+
+  c = the_node->child[_RBTree_Opposite_direction(dir)];
+  the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
+
+  if (c->child[dir])
+    c->child[dir]->parent = the_node;
+
+  c->child[dir] = the_node;
+
+  the_node->parent->child[the_node != the_node->parent->child[0]] = c;
+
+  c->parent = the_node->parent;
+  the_node->parent = c;
+}
+
+/** @} */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+/* end of include file */
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
deleted file mode 100644
index 8b4234de57..0000000000
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ /dev/null
@@ -1,507 +0,0 @@
-/**
- * @file
- *
- * @brief Inlined Routines Associated with Red-Black Trees
- *
- * This include file contains the bodies of the routines which are
- * associated with Red-Black Trees and inlined.
- *
- * @note  The routines in this file are ordered from simple
- *        to complex.  No other RBTree Handler routine is referenced
- *        unless it has already been defined.
- */
-
-/*
- *  Copyright (c) 2010-2012 Gedare Bloom.
- *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
- */
-
-#ifndef _RTEMS_SCORE_RBTREE_H
-# error "Never use <rtems/score/rbtree.inl> directly; include <rtems/score/rbtree.h> instead."
-#endif
-
-#ifndef _RTEMS_SCORE_RBTREE_INL
-#define _RTEMS_SCORE_RBTREE_INL
-
-/**
- * @addtogroup ScoreRBTree
- */
-/**@{**/
-
-/**
- * @brief Get the direction opposite to @a the_dir.
- */
-RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
-  RBTree_Direction the_dir
-)
-{
-  return (RBTree_Direction) !((int) the_dir);
-}
-
-/**
- * @brief Set off RBtree.
- *
- * This function sets the parent and child fields of the @a node to NULL
- * indicating the @a node is not part of a rbtree.
- *
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
-    RBTree_Node *node
-    )
-{
-  node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
-}
-
-/**
- * @brief Is the node off RBTree.
- *
- * This function returns true if the @a node is not on a rbtree. A @a node is
- * off rbtree if the parent and child fields are set to NULL.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
-    const RBTree_Node *node
-    )
-{
-  return (node->parent == NULL) &&
-         (node->child[RBT_LEFT] == NULL) &&
-         (node->child[RBT_RIGHT] == NULL);
-}
-
-/**
- * @brief Are two Nodes equal.
- *
- * This function returns true if @a left and @a right are equal,
- * and false otherwise.
- *
- * @retval true @a left and @a right are equal.
- * @retval false @a left and @a right are not equal.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
-    const RBTree_Node *left,
-    const RBTree_Node *right
-    )
-{
-  return left == right;
-}
-
-/**
- * @brief Is this RBTree control pointer NULL.
- *
- * This function returns true if @a the_rbtree is NULL and false otherwise.
- *
- * @retval true @a the_rbtree is @c NULL.
- * @retval false @a the_rbtree is not @c NULL.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
-    const RBTree_Control *the_rbtree
-    )
-{
-  return (the_rbtree == NULL);
-}
-
-/**
- * @brief Is the RBTree node pointer NUL.
- *
- * This function returns true if @a the_node is NULL and false otherwise.
- *
- * @retval true @a the_node is @c NULL.
- * @retval false @a the_node is not @c NULL.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node(
-    const RBTree_Node *the_node
-    )
-{
-  return (the_node == NULL);
-}
-
-
-/**
- * @brief Return pointer to RBTree's root node.
- *
- * This function returns a pointer to the root node of @a the_rbtree.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
-  const RBTree_Control *the_rbtree
-)
-{
-  return the_rbtree->root;
-}
-
-/**
- * @brief Return pointer to RBTree's first node.
- *
- * This function returns a pointer to the first node on @a the_rbtree,
- * where @a dir specifies whether to return the minimum (0) or maximum (1).
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
-  const RBTree_Control *the_rbtree,
-  RBTree_Direction dir
-)
-{
-  return the_rbtree->first[dir];
-}
-
-/**
- * @brief Return pointer to the parent of this node.
- *
- * This function returns a pointer to the parent node of @a the_node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
-  const RBTree_Node *the_node
-)
-{
-  if (!the_node->parent->parent) return NULL;
-  return the_node->parent;
-}
-
-/**
- * @brief Return pointer to the left of this node.
- *
- * This function returns a pointer to the left node of this node.
- *
- * @param[in] the_node is the node to be operated upon.
- *
- * @return This method returns the left node on the rbtree.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
-  const RBTree_Node *the_node
-)
-{
-  return the_node->child[RBT_LEFT];
-}
-
-/**
- * @brief Return pointer to the right of this node.
- *
- * This function returns a pointer to the right node of this node.
- *
- * @param[in] the_node is the node to be operated upon.
- *
- * @return This method returns the right node on the rbtree.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
-  const RBTree_Node *the_node
-)
-{
-  return the_node->child[RBT_RIGHT];
-}
-
-/**
- * @brief Is the RBTree empty.
- *
- * This function returns true if there are no nodes on @a the_rbtree and
- * false otherwise.
- *
- * @param[in] the_rbtree is the rbtree to be operated upon.
- *
- * @retval true There are no nodes on @a the_rbtree.
- * @retval false There are nodes on @a the_rbtree.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
-  const RBTree_Control *the_rbtree
-)
-{
-  return (the_rbtree->root == NULL);
-}
-
-/**
- * @brief Is this the first node on the RBTree.
- *
- * This function returns true if @a the_node is the first node on
- * @a the_rbtree and false otherwise. @a dir specifies whether first means
- * minimum (0) or maximum (1).
- *
- * @retval true @a the_node is the first node on @a the_rbtree.
- * @retval false @a the_node is not the first node on @a the_rbtree.
- *
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
-  const RBTree_Control *the_rbtree,
-  const RBTree_Node *the_node,
-  RBTree_Direction dir
-)
-{
-  return (the_node == _RBTree_First(the_rbtree, dir));
-}
-
-/**
- * @brief Is this node red.
- *
- * This function returns true if @a the_node is red and false otherwise.
- *
- * @retval true @a the_node is red.
- * @retval false @a the_node in not red.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
-    const RBTree_Node *the_node
-    )
-{
-  return (the_node && the_node->color == RBT_RED);
-}
-
-
-/**
- * @brief Does this RBTree have only one node.
- *
- * This function returns true if there is only one node on @a the_rbtree and
- * false otherwise.
- *
- * @retval true @a the_rbtree has only one node.
- * @retval false @a the_rbtree has more than one nodes.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node(
-    const RBTree_Control *the_rbtree
-    )
-{
-  if(!the_rbtree) return false; /* TODO: expected behavior? */
-  return (the_rbtree->root->child[RBT_LEFT] == NULL &&
-          the_rbtree->root->child[RBT_RIGHT] == NULL);
-}
-
-/**
- * @brief Is this node the RBTree root.
- *
- * This function returns true if @a the_node is the root of @a the_rbtree and
- * false otherwise.
- *
- * @retval true @a the_node is the root of @a the_rbtree.
- * @retval false @a the_node is not the root of @a the_rbtree.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
-  const RBTree_Control *the_rbtree,
-  const RBTree_Node    *the_node
-)
-{
-  return (the_node == _RBTree_Root(the_rbtree));
-}
-
-/**
- * @brief Initialize this RBTree as empty.
- *
- * 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
-    )
-{
-  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;
-}
-
-/**
- * @brief Return a pointer to node's grandparent.
- *
- * This function returns a pointer to the grandparent of @a the_node if it
- * exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
-  const RBTree_Node *the_node
-)
-{
-  if(!the_node) return NULL;
-  if(!(the_node->parent)) return NULL;
-  if(!(the_node->parent->parent)) return NULL;
-  if(!(the_node->parent->parent->parent)) return NULL;
-  return(the_node->parent->parent);
-}
-
-/**
- * @brief Return a pointer to node's sibling.
- *
- * This function returns a pointer to the sibling of @a the_node if it
- * exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
-  const RBTree_Node *the_node
-)
-{
-  if(!the_node) return NULL;
-  if(!(the_node->parent)) return NULL;
-  if(!(the_node->parent->parent)) return NULL;
-
-  if(the_node == the_node->parent->child[RBT_LEFT])
-    return the_node->parent->child[RBT_RIGHT];
-  else
-    return the_node->parent->child[RBT_LEFT];
-}
-
-/**
- * @brief Return a pointer to node's parent's sibling.
- *
- * This function returns a pointer to the sibling of the parent of
- * @a the_node if it exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
-  const RBTree_Node *the_node
-)
-{
-  if(!the_node) return NULL;
-  if(_RBTree_Grandparent(the_node) == NULL) return NULL;
-
-  return _RBTree_Sibling(the_node->parent);
-}
-
-/**
- * @brief Find the RBTree_Control header given a node in the tree.
- *
- * This function returns a pointer to the header of the Red Black
- * Tree containing @a the_node if it exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
-    RBTree_Node *the_node
-    )
-{
-  if(!the_node) return NULL;
-  if(!(the_node->parent)) return NULL;
-  while(the_node->parent) the_node = the_node->parent;
-  return (RBTree_Control*)the_node;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
-{
-  return compare_result == 0;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
-  int compare_result
-)
-{
-  return compare_result > 0;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
-  int compare_result
-)
-{
-  return compare_result < 0;
-}
-
-/**
- * @brief Returns the predecessor of a node.
- *
- * @param[in] node is the node.
- *
- * @retval NULL The predecessor does not exist.  Otherwise it returns
- *         the predecessor node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
-  const RBTree_Node *node
-)
-{
-  return _RBTree_Next_unprotected( node, RBT_LEFT );
-}
-
-/**
- * @copydoc _RBTree_Predecessor_unprotected()
- *
- * The function disables the interrupts protect the operation.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
-  const RBTree_Node *node
-)
-{
-  return _RBTree_Next( node, RBT_LEFT );
-}
-
-/**
- * @brief Returns the successor of a node.
- *
- * @param[in] node is the node.
- *
- * @retval NULL The successor does not exist.  Otherwise the successor node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
-  const RBTree_Node *node
-)
-{
-  return _RBTree_Next_unprotected( node, RBT_RIGHT );
-}
-
-/**
- * @copydoc _RBTree_Successor_unprotected()
- *
- * The function disables the interrupts protect the operation.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
-  const RBTree_Node *node
-)
-{
-  return _RBTree_Next( node, RBT_RIGHT );
-}
-
-/**
- * @brief Get the first node (unprotected).
- *
- * This function removes the minimum or maximum node from the_rbtree and
- * returns a pointer to that node.  It does NOT disable interrupts to ensure
- * the atomicity of the get operation.
- *
- * @param[in] the_rbtree is the rbtree to attempt to get the min node from.
- * @param[in] dir specifies whether to get minimum (0) or maximum (1)
- *
- * @return This method returns the min or max node on the rbtree, or NULL.
- *
- * @note This routine may return NULL if the RBTree is empty.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
-    RBTree_Control *the_rbtree,
-    RBTree_Direction dir
-    )
-{
-  RBTree_Node *the_node = the_rbtree->first[dir];
-  _RBTree_Extract_unprotected(the_rbtree, the_node);
-  return the_node;
-}
-
-/**
- * @brief Rotate the_node in the direction passed as second argument.
- *
- * This routine rotates @a the_node to the direction @a dir, swapping
- * @a the_node with its child\[@a dir\].
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
-    RBTree_Node *the_node,
-    RBTree_Direction dir
-    )
-{
-  RBTree_Node *c;
-  if (the_node == NULL) return;
-  if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
-
-  c = the_node->child[_RBTree_Opposite_direction(dir)];
-  the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
-
-  if (c->child[dir])
-    c->child[dir]->parent = the_node;
-
-  c->child[dir] = the_node;
-
-  the_node->parent->child[the_node != the_node->parent->child[0]] = c;
-
-  c->parent = the_node->parent;
-  the_node->parent = c;
-}
-
-/**
- * @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 );
-}
-
-/** @} */
-
-#endif
-/* end of include file */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index dc687dada8..edf4e3ef10 100644
--- a/cpukit/score/preinstall.am
+++ b/cpukit/score/preinstall.am
@@ -143,6 +143,10 @@ $(PROJECT_INCLUDE)/rtems/score/rbtree.h: include/rtems/score/rbtree.h $(PROJECT_
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.h
 
+$(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h: include/rtems/score/rbtreeimpl.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h
+
 $(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h
@@ -315,10 +319,6 @@ $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl: inline/rtems/score/prioritybi
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl
 
-$(PROJECT_INCLUDE)/rtems/score/rbtree.inl: inline/rtems/score/rbtree.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
-	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.inl
-PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.inl
-
 $(PROJECT_INCLUDE)/rtems/score/scheduler.inl: inline/rtems/score/scheduler.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.inl
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.inl
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 3079f10b6e..0f38fbc325 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -10,9 +10,7 @@
 #include "config.h"
 #endif
 
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
 #include <rtems/score/isr.h>
 
 /** @brief  Validate and fix-up tree properties after deleting a node
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 2eb92a5ac5..b485845dbd 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -17,9 +17,7 @@
 #include "config.h"
 #endif
 
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
 #include <rtems/score/isr.h>
 
 RBTree_Node *_RBTree_Find(
diff --git a/cpukit/score/src/rbtreeget.c b/cpukit/score/src/rbtreeget.c
index 1570d472c8..a805a4090f 100644
--- a/cpukit/score/src/rbtreeget.c
+++ b/cpukit/score/src/rbtreeget.c
@@ -17,9 +17,7 @@
 #include "config.h"
 #endif
 
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
 #include <rtems/score/isr.h>
 
 RBTree_Node *_RBTree_Get(
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 57a36b8a1c..0d8e4a6dc4 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -10,9 +10,7 @@
 #include "config.h"
 #endif
 
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
 #include <rtems/score/isr.h>
 
 /** @brief Validate and fix-up tree properties for a new insert/colored node
diff --git a/cpukit/score/src/rbtreeiterate.c b/cpukit/score/src/rbtreeiterate.c
index f6de82b576..880fa2b143 100644
--- a/cpukit/score/src/rbtreeiterate.c
+++ b/cpukit/score/src/rbtreeiterate.c
@@ -24,7 +24,7 @@
   #include "config.h"
 #endif
 
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
 
 void _RBTree_Iterate_unprotected(
   const RBTree_Control *rbtree,
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
index 0aee0434f6..7dd305a3dc 100644
--- a/cpukit/score/src/rbtreenext.c
+++ b/cpukit/score/src/rbtreenext.c
@@ -24,7 +24,7 @@
   #include "config.h"
 #endif
 
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
 #include <rtems/score/isr.h>
 
 RBTree_Node *_RBTree_Next_unprotected(