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.

1 files changed, 3 insertions, 187 deletions

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 );
 }