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, 26 insertions, 102 deletions

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