rbtree: Replace implementation

Use the BSD <sys/tree.h> implementation since it is faster, more
flexible and uses less storage.  See https://github.com/sebhub/rb-bench.

6 files changed, 202 insertions, 578 deletions

diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index b44c09edb5..077f2b181d 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -18,9 +18,8 @@
 #ifndef _RTEMS_SCORE_RBTREE_H
 #define _RTEMS_SCORE_RBTREE_H
 
-#include <stddef.h>
-
-#include <rtems/score/address.h>
+#include <sys/tree.h>
+#include <rtems/score/basedefs.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -40,54 +39,22 @@ extern "C" {
 /**@{*/
 
 /**
- *  @typedef RBTree_Node
+ * @brief Red-black tree node.
  *
- *  This type definition promotes the name for the RBTree Node used by
- *  all RTEMS code.  It is a separate type definition because a forward
- *  reference is required to define it.  See @ref RBTree_Node_struct for
- *  detailed information.
+ * This is used to manage each node (element) which is placed on a red-black
+ * tree.
  */
-typedef struct RBTree_Node_struct RBTree_Node;
+typedef struct RBTree_Node {
+  RB_ENTRY(RBTree_Node) Node;
+} RBTree_Node;
 
 /**
- * This enum type defines the colors available for the RBTree Nodes
- */
-typedef enum {
-  RBT_BLACK,
-  RBT_RED
-} RBTree_Color;
-
-/**
- *  @struct RBTree_Node_struct
- *
- *  This is used to manage each element (node) which is placed
- *  on a RBT.
- *
- *  @note Typically, a more complicated structure will use the
- *        rbtree package.  The more complicated structure will
- *        include a rbtree node as the first element in its
- *        control structure.  It will then call the rbtree package
- *        with a pointer to that node element.  The node pointer
- *        and the higher level structure start at the same address
- *        so the user can cast the pointers back and forth.
+ * @brief Red-black tree control.
  *
+ * This is used to manage a red-black tree.  A red-black tree consists of a
+ * tree of zero or more nodes.
  */
-struct RBTree_Node_struct {
-  /** This points to the node's parent */
-  RBTree_Node *parent;
-  /** child[0] points to the left child, child[1] points to the right child */
-  RBTree_Node *child[2];
-  /** The color of the node. Either red or black */
-  RBTree_Color color;
-};
-
-/**
- *  This type indicates the direction.
- */
-typedef enum {
-  RBT_LEFT=0,
-  RBT_RIGHT=1
-} RBTree_Direction;
+typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
 
 /**
  * @brief Integer type for compare results.
@@ -117,41 +84,13 @@ typedef RBTree_Compare_result ( *RBTree_Compare )(
 );
 
 /**
- *  @struct RBTree_Control
- *
- * This is used to manage a RBT.  A rbtree consists of a tree of zero or more
- * nodes.
- *
- * @note This implementation does not require special checks for
- *   manipulating the root element of the RBT.
- *   To accomplish this the @a RBTree_Control structure can be overlaid
- *   with a @ref RBTree_Node structure to act as a "dummy root",
- *   which has a NULL parent and its left child is the root.
- */
-
-/* the RBTree_Control is actually part of the RBTree structure as an
- * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
- *   permanent_null == parent
- *   root == left
- *   first[0] == right
- */
-typedef struct {
-  /** This points to a NULL. Useful for finding the root. */
-  RBTree_Node *permanent_null;
-  /** This points to the root node of the RBT. */
-  RBTree_Node *root;
-  /** This points to the min and max nodes of this RBT. */
-  RBTree_Node *first[2];
-} RBTree_Control;
-
-/**
- *  @brief RBTree initializer for an empty rbtree with designator @a name.
+ * @brief Initializer for an empty red-black tree with designator @a name.
  */
 #define RBTREE_INITIALIZER_EMPTY( name ) \
-  { NULL, NULL, { NULL, NULL } }
+  RB_INITIALIZER( name )
 
 /**
- *  @brief RBTree definition for an empty rbtree with designator @a name.
+ * @brief Definition for an empty red-black tree with designator @a name.
  */
 #define RBTREE_DEFINE_EMPTY( name ) \
   RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
@@ -201,6 +140,95 @@ RBTree_Node *_RBTree_Insert(
 );
 
 /**
+ * @brief Rebalances the red-black tree after insertion of the node.
+ *
+ * @param[in] the_rbtree The red-black tree control.
+ * @param[in] the_node The most recently inserted node.
+ */
+void _RBTree_Insert_color(
+  RBTree_Control *the_rbtree,
+  RBTree_Node    *the_node
+);
+
+/**
+ * @brief Adds a child node to a parent node.
+ *
+ * @param[in] child The child node.
+ * @param[in] parent The parent node.
+ * @param[in] link The child node link of the parent node.
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Add_child(
+  RBTree_Node  *child,
+  RBTree_Node  *parent,
+  RBTree_Node **link
+)
+{
+  RB_SET( child, parent, Node );
+  *link = child;
+}
+
+/**
+ * @brief Inserts the node into the red-black tree using the specified parent
+ * node and link.
+ *
+ * @param[in] the_rbtree The red-black tree control.
+ * @param[in] the_node The node to insert.
+ * @param[in] parent The parent node.
+ * @param[in] link The child node link of the parent node.
+ *
+ * @code
+ * #include <rtems/score/rbtree.h>
+ *
+ * typedef struct {
+ *   int value;
+ *   RBTree_Node Node;
+ * } Some_Node;
+ *
+ * bool _Some_Less(
+ *   const RBTree_Node *a,
+ *   const RBTree_Node *b
+ * )
+ * {
+ *   const Some_Node *aa = RTEMS_CONTAINER_OF( a, Some_Node, Node );
+ *   const Some_Node *bb = RTEMS_CONTAINER_OF( b, Some_Node, Node );
+ *
+ *   return aa->value < bb->value;
+ * }
+ *
+ * void _Some_Insert(
+ *   RBTree_Control *the_rbtree,
+ *   Some_Node      *the_node
+ * )
+ * {
+ *   RBTree_Node **link = _RBTree_Root_reference( the_rbtree );
+ *   RBTree_Node  *parent = NULL;
+ *
+ *   while ( *link != NULL ) {
+ *     parent = *link;
+ *
+ *     if ( _Some_Less( &the_node->Node, parent ) ) {
+ *       link = _RBTree_Left_reference( parent );
+ *     } else {
+ *       link = _RBTree_Right_reference( parent );
+ *     }
+ *   }
+ *
+ *   _RBTree_Insert_with_parent( the_rbtree, &the_node->Node, parent, link );
+ * }
+ * @endcode
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Insert_with_parent(
+  RBTree_Control  *the_rbtree,
+  RBTree_Node     *the_node,
+  RBTree_Node     *parent,
+  RBTree_Node    **link
+)
+{
+  _RBTree_Add_child( the_node, parent, link );
+  _RBTree_Insert_color( the_rbtree, the_node );
+}
+
+/**
  * @brief Extracts (removes) the node from the red-black tree.
  *
  * This function does not set the node off-tree.  In case this is desired, then
@@ -218,20 +246,6 @@ void _RBTree_Extract(
 );
 
 /**
- * @brief Returns the in-order next node of a node.
- *
- * @param[in] node The node.
- * @param[in] dir The direction.
- *
- * @retval NULL The in-order next node does not exist.
- * @retval otherwise The next node.
- */
-RBTree_Node *_RBTree_Next(
-  const RBTree_Node *node,
-  RBTree_Direction dir
-);
-
-/**
  * @brief Sets a red-black tree node as off-tree.
  *
  * Do not use this function on nodes which are a part of a tree.
@@ -242,7 +256,7 @@ RBTree_Node *_RBTree_Next(
  */
 RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
 {
-  the_node->parent = NULL;
+  RB_COLOR( the_node, Node ) = -1;
 }
 
 /**
@@ -260,7 +274,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
   const RBTree_Node *the_node
 )
 {
-  return the_node->parent == NULL;
+  return RB_COLOR( the_node, Node ) == -1;
 }
 
 /**
@@ -279,21 +293,17 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
   const RBTree_Control *the_rbtree
 )
 {
-  return the_rbtree->root;
+  return RB_ROOT( the_rbtree );
 }
 
 /**
- * @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).
+ * @brief Returns a reference to the root pointer of the red-black tree.
  */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
-  const RBTree_Control *the_rbtree,
-  RBTree_Direction dir
+RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference(
+  RBTree_Control *the_rbtree
 )
 {
-  return the_rbtree->first[dir];
+  return &RB_ROOT( the_rbtree );
 }
 
 /**
@@ -312,7 +322,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
   const RBTree_Node *the_node
 )
 {
-  return the_node->parent;
+  return RB_PARENT( the_node, Node );
 }
 
 /**
@@ -328,7 +338,18 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
   const RBTree_Node *the_node
 )
 {
-  return the_node->child[RBT_LEFT];
+  return RB_LEFT( the_node, Node );
+}
+
+/**
+ * @brief Returns a reference to the left child pointer of the red-black tree
+ * node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference(
+  RBTree_Node *the_node
+)
+{
+  return &RB_LEFT( the_node, Node );
 }
 
 /**
@@ -344,7 +365,18 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
   const RBTree_Node *the_node
 )
 {
-  return the_node->child[RBT_RIGHT];
+  return RB_RIGHT( the_node, Node );
+}
+
+/**
+ * @brief Returns a reference to the right child pointer of the red-black tree
+ * node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference(
+  RBTree_Node *the_node
+)
+{
+  return &RB_RIGHT( the_node, Node );
 }
 
 /**
@@ -362,7 +394,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
   const RBTree_Control *the_rbtree
 )
 {
-  return (the_rbtree->root == NULL);
+  return RB_EMPTY( the_rbtree );
 }
 
 /**
@@ -384,7 +416,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
   const RBTree_Node *the_node
 )
 {
-  return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL;
+  return _RBTree_Parent( the_node ) == NULL;
 }
 
 /**
@@ -396,10 +428,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
   RBTree_Control *the_rbtree
 )
 {
-  the_rbtree->permanent_null   = NULL;
-  the_rbtree->root             = NULL;
-  the_rbtree->first[RBT_LEFT]  = NULL;
-  the_rbtree->first[RBT_RIGHT] = NULL;
+  RB_INIT( the_rbtree );
 }
 
 /**
@@ -410,12 +439,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
  * @retval NULL The red-black tree is empty.
  * @retval node The minimum node.
  */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum(
-  const RBTree_Control *the_rbtree
-)
-{
-  return _RBTree_First( the_rbtree, RBT_LEFT );
-}
+RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );
 
 /**
  * @brief Returns the maximum node of the red-black tree.
@@ -425,12 +449,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum(
  * @retval NULL The red-black tree is empty.
  * @retval node The maximum node.
  */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum(
-  const RBTree_Control *the_rbtree
-)
-{
-  return _RBTree_First( the_rbtree, RBT_RIGHT );
-}
+RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );
 
 /**
  * @brief Returns the predecessor of a node.
@@ -440,12 +459,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum(
  * @retval NULL The predecessor does not exist.  Otherwise it returns
  *         the predecessor node.
  */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
-  const RBTree_Node *node
-)
-{
-  return _RBTree_Next( node, RBT_LEFT );
-}
+RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );
 
 /**
  * @brief Returns the successor of a node.
@@ -454,12 +468,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
  *
  * @retval NULL The successor does not exist.  Otherwise the successor node.
  */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
-  const RBTree_Node *node
-)
-{
-  return _RBTree_Next( node, RBT_RIGHT );
-}
+RBTree_Node *_RBTree_Successor( const RBTree_Node *node );
 
 /**@}*/
 
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
index 607e7ebf84..9c748eb01c 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -62,66 +62,6 @@ void _RBTree_Iterate(
   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 Returns the direction of the node.
- *
- * @param[in] the_node The node of interest.
- * @param[in] parent The parent of the node.  The parent must exist, thus it is
- * invalid to use this function for the root node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction(
-  const RBTree_Node *the_node,
-  const RBTree_Node *parent
-)
-{
-  return (RBTree_Direction) ( the_node != parent->child[ 0 ] );
-}
-
-/**
- * @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 Returns the sibling of the node.
- *
- * @param[in] the_node The node of interest.
- * @param[in] parent The parent of the node.  The parent must exist, thus it is
- * invalid to use this function for the root node.
- *
- * @retval NULL No sibling exists.
- * @retval sibling The sibling of the node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
-  const RBTree_Node *the_node,
-  const RBTree_Node *parent
-)
-{
-  RBTree_Node *left_child = parent->child[ RBT_LEFT ];
-
-  return the_node == left_child ? parent->child[ RBT_RIGHT ] : left_child;
-}
-
 RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
   RBTree_Compare_result compare_result
 )
@@ -143,64 +83,6 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
   return compare_result < 0;
 }
 
-/**
- * @brief Rotates the node in the specified direction.
- *
- * The node is swapped with its child in the opposite direction if it exists.
- *
- * Sub-tree before rotation:
- * @dot
- * digraph state {
- *   parent -> the_node;
- *   the_node -> sibling [label="dir"];
- *   the_node -> child [label="opp_dir"];
- *   child -> grandchild [label="dir"];
- *   child -> grandchildsibling [label="opp_dir"];
- * }
- * @enddot
- *
- * Sub-tree after rotation:
- * @dot
- * digraph state {
- *   parent -> child;
- *   the_node -> sibling [label="dir"];
- *   the_node -> grandchild [label="opp_dir"];
- *   child -> the_node [label="dir"];
- *   child -> grandchildsibling [label="opp_dir"];
- * }
- * @enddot
- *
- * @param[in] the_node The node to rotate.
- * @param[in] dir The rotation direction.
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
-  RBTree_Node      *the_node,
-  RBTree_Direction  dir
-)
-{
-  RBTree_Direction  opp_dir = _RBTree_Opposite_direction( dir );
-  RBTree_Node      *child = the_node->child[ opp_dir ];
-  RBTree_Node      *grandchild;
-  RBTree_Node      *parent;
-
-  if ( child == NULL)
-    return;
-
-  grandchild = child->child[ dir ];
-  the_node->child[ opp_dir ] = grandchild;
-
-  if ( grandchild != NULL )
-    grandchild->parent = the_node;
-
-  child->child[ dir ] = the_node;
-
-  parent = _RBTree_Parent( the_node );
-  parent->child[ _RBTree_Direction( the_node, parent ) ] = child;
-
-  child->parent = parent;
-  the_node->parent = child;
-}
-
 /** @} */
 
 #ifdef __cplusplus
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 1aaba270e7..4d8a8f8eed 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -12,198 +12,14 @@
 
 #include <rtems/score/rbtreeimpl.h>
 
-/** @brief  Validate and fix-up tree properties after deleting a node
- *
- *  This routine is called on a black node, @a the_node, after its deletion.
- *  This function maintains the properties of the red-black tree.
- *
- *  @note It does NOT disable interrupts to ensure the atomicity
- *        of the extract operation.
- */
-static void _RBTree_Extract_validate( RBTree_Node *the_node )
-{
-  RBTree_Node     *parent;
-
-  parent = the_node->parent;
-
-  if ( !parent->parent )
-    return;
-
-  /* continue to correct tree as long as the_node is black and not the root */
-  while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
-    RBTree_Node *sibling = _RBTree_Sibling( the_node, parent );
-
-    /* if sibling is red, switch parent (black) and sibling colors,
-     * then rotate parent left, making the sibling be the_node's grandparent.
-     * Now the_node has a black sibling and red parent. After rotation,
-     * update sibling pointer.
-     */
-    if ( _RBTree_Is_red( sibling ) ) {
-      RBTree_Direction dir = _RBTree_Direction( the_node, parent );
-      RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
-
-      parent->color = RBT_RED;
-      sibling->color = RBT_BLACK;
-      _RBTree_Rotate( parent, dir );
-      sibling = parent->child[ opp_dir ];
-    }
+RB_GENERATE_REMOVE_COLOR( RBTree_Control, RBTree_Node, Node, static )
 
-    /* sibling is black, see if both of its children are also black. */
-    if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) &&
-         !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) {
-      sibling->color = RBT_RED;
-
-      if ( _RBTree_Is_red( parent ) ) {
-        parent->color = RBT_BLACK;
-        break;
-      }
-
-      the_node = parent;   /* done if parent is red */
-      parent = the_node->parent;
-    } else {
-      /* at least one of sibling's children is red. we now proceed in two
-       * cases, either the_node is to the left or the right of the parent.
-       * In both cases, first check if one of sibling's children is black,
-       * and if so rotate in the proper direction and update sibling pointer.
-       * Then switch the sibling and parent colors, and rotate through parent.
-       */
-      RBTree_Direction dir = _RBTree_Direction( the_node, parent );
-      RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
-
-      if (
-        !_RBTree_Is_red( sibling->child[ opp_dir ] )
-      ) {
-        sibling->color = RBT_RED;
-        sibling->child[ dir ]->color = RBT_BLACK;
-        _RBTree_Rotate( sibling, opp_dir );
-        sibling = parent->child[ opp_dir ];
-      }
-
-      sibling->color = parent->color;
-      parent->color = RBT_BLACK;
-      sibling->child[ opp_dir ]->color = RBT_BLACK;
-      _RBTree_Rotate( parent, dir );
-      break; /* done */
-    }
-  } /* while */
-
-  if ( !the_node->parent->parent )
-    the_node->color = RBT_BLACK;
-}
+RB_GENERATE_REMOVE( RBTree_Control, RBTree_Node, Node, static )
 
 void _RBTree_Extract(
   RBTree_Control *the_rbtree,
   RBTree_Node    *the_node
 )
 {
-  RBTree_Node     *leaf, *target;
-  RBTree_Color     victim_color;
-  RBTree_Direction dir;
-
-  /* check if min needs to be updated */
-  if ( the_node == the_rbtree->first[ RBT_LEFT ] ) {
-    RBTree_Node *next;
-    next = _RBTree_Successor( the_node );
-    the_rbtree->first[ RBT_LEFT ] = next;
-  }
-
-  /* Check if max needs to be updated. min=max for 1 element trees so
-   * do not use else if here. */
-  if ( the_node == the_rbtree->first[ RBT_RIGHT ] ) {
-    RBTree_Node *previous;
-    previous = _RBTree_Predecessor( the_node );
-    the_rbtree->first[ RBT_RIGHT ] = previous;
-  }
-
-  /* if the_node has at most one non-null child then it is safe to proceed
-   * check if both children are non-null, if so then we must find a target node
-   * either max in node->child[RBT_LEFT] or min in node->child[RBT_RIGHT],
-   * and replace the_node with the target node. This maintains the binary
-   * search tree property, but may violate the red-black properties.
-   */
-
-  if ( the_node->child[ RBT_LEFT ] && the_node->child[ RBT_RIGHT ] ) {
-    target = the_node->child[ RBT_LEFT ]; /* find max in node->child[RBT_LEFT] */
-
-    while ( target->child[ RBT_RIGHT ] )
-      target = target->child[ RBT_RIGHT ];
-
-    /* if the target node has a child, need to move it up the tree into
-     * target's position (target is the right child of target->parent)
-     * when target vacates it. if there is no child, then target->parent
-     * should become NULL. This may cause the coloring to be violated.
-     * For now we store the color of the node being deleted in victim_color.
-     */
-    leaf = target->child[ RBT_LEFT ];
-
-    if ( leaf ) {
-      leaf->parent = target->parent;
-    } else {
-      /* fix the tree here if the child is a null leaf. */
-      _RBTree_Extract_validate( target );
-    }
-
-    victim_color = target->color;
-    dir = target != target->parent->child[ 0 ];
-    target->parent->child[ dir ] = leaf;
-
-    /* now replace the_node with target */
-    dir = the_node != the_node->parent->child[ 0 ];
-    the_node->parent->child[ dir ] = target;
-
-    /* set target's new children to the original node's children */
-    target->child[ RBT_RIGHT ] = the_node->child[ RBT_RIGHT ];
-
-    if ( the_node->child[ RBT_RIGHT ] )
-      the_node->child[ RBT_RIGHT ]->parent = target;
-
-    target->child[ RBT_LEFT ] = the_node->child[ RBT_LEFT ];
-
-    if ( the_node->child[ RBT_LEFT ] )
-      the_node->child[ RBT_LEFT ]->parent = target;
-
-    /* finally, update the parent node and recolor. target has completely
-     * replaced the_node, and target's child has moved up the tree if needed.
-     * the_node is no longer part of the tree, although it has valid pointers
-     * still.
-     */
-    target->parent = the_node->parent;
-    target->color = the_node->color;
-  } else {
-    /* the_node has at most 1 non-null child. Move the child in to
-     * the_node's location in the tree. This may cause the coloring to be
-     * violated. We will fix it later.
-     * For now we store the color of the node being deleted in victim_color.
-     */
-    leaf = the_node->child[ RBT_LEFT ] ?
-           the_node->child[ RBT_LEFT ] : the_node->child[ RBT_RIGHT ];
-
-    if ( leaf ) {
-      leaf->parent = the_node->parent;
-    } else {
-      /* fix the tree here if the child is a null leaf. */
-      _RBTree_Extract_validate( the_node );
-    }
-
-    victim_color = the_node->color;
-
-    /* remove the_node from the tree */
-    dir = the_node != the_node->parent->child[ 0 ];
-    the_node->parent->child[ dir ] = leaf;
-  }
-
-  /* fix coloring. leaf has moved up the tree. The color of the deleted
-   * node is in victim_color. There are two cases:
-   *   1. Deleted a red node, its child must be black. Nothing must be done.
-   *   2. Deleted a black node, its child must be red. Paint child black.
-   */
-  if ( victim_color == RBT_BLACK ) { /* eliminate case 1 */
-    if ( leaf ) {
-      leaf->color = RBT_BLACK; /* case 2 */
-    }
-  }
-
-  /* set root to black, if it exists */
-  if ( the_rbtree->root )
-    the_rbtree->root->color = RBT_BLACK;
+  RB_REMOVE( RBTree_Control, the_rbtree, the_node );
 }
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 168a108962..f920febd41 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -26,12 +26,11 @@ RBTree_Node *_RBTree_Find(
   bool                  is_unique
 )
 {
-  RBTree_Node *iter_node = the_rbtree->root;
+  RBTree_Node *iter_node = _RBTree_Root( the_rbtree );
   RBTree_Node *found = NULL;
 
   while ( iter_node != NULL ) {
     RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node );
-    RBTree_Direction      dir;
 
     if ( _RBTree_Is_equal( compare_result ) ) {
       found = iter_node;
@@ -40,8 +39,11 @@ RBTree_Node *_RBTree_Find(
         break;
     }
 
-    dir = (RBTree_Direction) _RBTree_Is_greater( compare_result );
-    iter_node = iter_node->child[ dir ];
+    if ( _RBTree_Is_greater( compare_result ) ) {
+      iter_node = _RBTree_Right( iter_node );
+    } else {
+      iter_node = _RBTree_Left( iter_node );
+    }
   }
 
   return found;
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index a7be449420..629fca7795 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -22,68 +22,6 @@ RTEMS_STATIC_ASSERT(
   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
- *  @a the_node being just added to the tree.
- *
- *  @note It does NOT disable interrupts to ensure the atomicity of the
- *        append operation.
- */
-static void _RBTree_Validate_insert( RBTree_Node *the_node )
-{
-  RBTree_Node *parent = _RBTree_Parent( the_node );
-  RBTree_Node *grandparent = _RBTree_Parent( parent );
-
-  /* note: the insert root case is handled already */
-  /* if the parent is black, nothing needs to be done
-   * otherwise may need to loop a few times */
-  while ( parent->color == RBT_RED ) {
-    /* The root is black, so the grandparent must exist */
-    RBTree_Node *uncle = _RBTree_Sibling( parent, grandparent );
-
-    /*
-     * If uncle exists and is red, repaint uncle/parent black and grandparent
-     * red.
-     */
-    if ( uncle != NULL && uncle->color == RBT_RED ) {
-      parent->color = RBT_BLACK;
-      uncle->color = RBT_BLACK;
-      grandparent->color = RBT_RED;
-      the_node = grandparent;
-      parent = _RBTree_Parent( the_node );
-      grandparent = _RBTree_Parent( parent );
-
-      if ( grandparent == NULL )
-        break;
-    } else { /* If uncle does not exist or is black */
-      RBTree_Direction dir = _RBTree_Direction( the_node, parent );
-      RBTree_Direction parentdir = _RBTree_Direction( parent, grandparent );
-
-      /* ensure node is on the same branch direction as parent */
-      if ( dir != parentdir ) {
-        RBTree_Node *oldparent = parent;
-
-        parent = the_node;
-        the_node = oldparent;
-        _RBTree_Rotate( oldparent, parentdir );
-      }
-
-      parent->color = RBT_BLACK;
-      grandparent->color = RBT_RED;
-
-      /* now rotate grandparent in the other branch direction (toward uncle) */
-      _RBTree_Rotate( grandparent, _RBTree_Opposite_direction( parentdir ) );
-
-      grandparent = _RBTree_Parent( parent );
-      break;
-    }
-  }
-
-  if ( grandparent == NULL )
-    the_node->color = RBT_BLACK;
-}
-
 RBTree_Node *_RBTree_Insert(
   RBTree_Control *the_rbtree,
   RBTree_Node    *the_node,
@@ -91,52 +29,38 @@ RBTree_Node *_RBTree_Insert(
   bool            is_unique
 )
 {
-  RBTree_Node *iter_node = the_rbtree->root;
+  RBTree_Node **which = _RBTree_Root_reference( the_rbtree );
+  RBTree_Node  *parent = NULL;
 
-  if ( !iter_node ) { /* special case: first node inserted */
-    the_node->color = RBT_BLACK;
-    the_rbtree->root = the_node;
-    the_rbtree->first[ 0 ] = the_rbtree->first[ 1 ] = the_node;
-    the_node->parent = (RBTree_Node *) the_rbtree;
-    the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL;
-  } else {
-    /* typical binary search tree insert, descend tree to leaf and insert */
-    while ( iter_node ) {
-      RBTree_Compare_result compare_result =
-        ( *compare )( the_node, iter_node );
+  while ( *which != NULL ) {
+    RBTree_Compare_result compare_result;
 
-      if ( is_unique && _RBTree_Is_equal( compare_result ) )
-        return iter_node;
+    parent = *which;
+    compare_result = ( *compare )( the_node, parent );
 
-      RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
+    if ( is_unique && _RBTree_Is_equal( compare_result ) ) {
+      return parent;
+    }
 
-      if ( !iter_node->child[ dir ] ) {
-        the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL;
-        the_node->color = RBT_RED;
-        iter_node->child[ dir ] = the_node;
-        the_node->parent = iter_node;
-        /* update min/max */
-        compare_result = ( *compare )(
-          the_node,
-          _RBTree_First( the_rbtree, dir )
-        );
+    if ( _RBTree_Is_lesser( compare_result ) ) {
+      which = _RBTree_Left_reference( parent );
+    } else {
+      which = _RBTree_Right_reference( parent );
+    }
+  }
 
-        if (
-          ( dir == RBT_LEFT && _RBTree_Is_lesser( compare_result ) )
-            || ( dir == RBT_RIGHT && !_RBTree_Is_lesser( compare_result ) )
-        ) {
-          the_rbtree->first[ dir ] = the_node;
-        }
+  _RBTree_Add_child( the_node, parent, which );
+  _RBTree_Insert_color( the_rbtree, the_node );
 
-        break;
-      } else {
-        iter_node = iter_node->child[ dir ];
-      }
-    } /* while(iter_node) */
+  return NULL;
+}
 
-    /* verify red-black properties */
-    _RBTree_Validate_insert( the_node );
-  }
+RB_GENERATE_INSERT_COLOR( RBTree_Control, RBTree_Node, Node, static )
 
-  return (RBTree_Node *) 0;
+void _RBTree_Insert_color(
+  RBTree_Control *the_rbtree,
+  RBTree_Node    *the_node
+)
+{
+  RBTree_Control_RB_INSERT_COLOR( the_rbtree, the_node );
 }
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
index 2128ae59bf..7096b4b22f 100644
--- a/cpukit/score/src/rbtreenext.c
+++ b/cpukit/score/src/rbtreenext.c
@@ -25,39 +25,30 @@
 #endif
 
 #include <rtems/score/rbtreeimpl.h>
-#include <rtems/score/isr.h>
+#include <rtems/score/basedefs.h>
 
-RBTree_Node *_RBTree_Next(
-  const RBTree_Node *node,
-  RBTree_Direction   dir
-)
+RB_GENERATE_MINMAX( RBTree_Control, RBTree_Node, Node, static )
+
+RB_GENERATE_NEXT( RBTree_Control, RBTree_Node, Node, static )
+
+RB_GENERATE_PREV( RBTree_Control, RBTree_Node, Node, static )
+
+RBTree_Node *_RBTree_Minimum( const RBTree_Control *tree )
+{
+  return RB_MIN( RBTree_Control, RTEMS_DECONST( RBTree_Control *, tree ) );
+}
+
+RBTree_Node *_RBTree_Maximum( const RBTree_Control *tree )
+{
+  return RB_MAX( RBTree_Control, RTEMS_DECONST( RBTree_Control *, tree ) );
+}
+
+RBTree_Node *_RBTree_Successor( const RBTree_Node *node )
+{
+  return RB_NEXT( RBTree_Control, NULL, RTEMS_DECONST( RBTree_Node *, node ) );
+}
+
+RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node )
 {
-  RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
-  RBTree_Node     *current = node->child[ dir ];
-  RBTree_Node     *next = NULL;
-
-  if ( current != NULL ) {
-    next = current;
-
-    while ( ( current = current->child[ opp_dir ] ) != NULL ) {
-      next = current;
-    }
-  } else {
-    RBTree_Node *parent = node->parent;
-
-    if ( parent->parent && node == parent->child[ opp_dir ] ) {
-      next = parent;
-    } else {
-      while ( parent->parent && node == parent->child[ dir ] ) {
-        node = parent;
-        parent = parent->parent;
-      }
-
-      if ( parent->parent ) {
-        next = parent;
-      }
-    }
-  }
-
-  return next;
+  return RB_PREV( RBTree_Control, NULL, RTEMS_DECONST( RBTree_Node *, node ) );
 }