[rtems commit] score: Improve _RBTree_Insert_inline()

[Sebastian Huber]

Module:    rtems
Branch:    master
Commit:    55faa447686f632bf1b98827cdec37a44bd69da2
Changeset: http://git.rtems.org/rtems/commit/?id=55faa447686f632bf1b98827cdec37a44bd69da2

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Fri Aug 12 11:16:45 2016 +0200

score: Improve _RBTree_Insert_inline()

Return if the inserted node is the new minimum node or not.

---

 cpukit/score/include/rtems/score/rbtree.h    | 10 ++++-
 testsuites/sptests/sprbtree01/init.c         | 63 ++++++++++++++++++++++++++++
 testsuites/sptests/sprbtree01/sprbtree01.doc |  1 +
 testsuites/sptests/sprbtree01/sprbtree01.scn |  2 +-
 4 files changed, 74 insertions(+), 2 deletions(-)

diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index e94560e..a5a6cf3 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -451,8 +451,12 @@ void _RBTree_Replace_node(
  *   the key is stored in a local variable.
  * @param less Must return true if the specified key is less than the key of
  *   the node, otherwise false.
+ *
+ * @retval true The inserted node is the new minimum node according to the
+ *   specified less order function.
+ * @retval false Otherwise.
  */
-RTEMS_INLINE_ROUTINE void _RBTree_Insert_inline(
+RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline(
   RBTree_Control *the_rbtree,
   RBTree_Node    *the_node,
   const void     *key,
@@ -461,9 +465,11 @@ RTEMS_INLINE_ROUTINE void _RBTree_Insert_inline(
 {
   RBTree_Node **link;
   RBTree_Node  *parent;
+  bool          is_new_minimum;
 
   link = _RBTree_Root_reference( the_rbtree );
   parent = NULL;
+  is_new_minimum = true;
 
   while ( *link != NULL ) {
     parent = *link;
@@ -472,11 +478,13 @@ RTEMS_INLINE_ROUTINE void _RBTree_Insert_inline(
       link = _RBTree_Left_reference( parent );
     } else {
       link = _RBTree_Right_reference( parent );
+      is_new_minimum = false;
     }
   }
 
   _RBTree_Add_child( the_node, parent, link );
   _RBTree_Insert_color( the_rbtree, the_node );
+  return is_new_minimum;
 }
 
 /**
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index fd3737c..0543508 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -234,6 +234,68 @@ static void test_rbtree_min_max(void)
   rtems_test_assert( rtems_rbtree_is_empty( &tree ) );
 }
 
+static bool test_less(
+  const void        *left,
+  const RBTree_Node *right
+)
+{
+  const int       *the_left;
+  const test_node *the_right;
+
+  the_left = left;
+  the_right = RTEMS_CONTAINER_OF( right, test_node, Node );
+
+  return *the_left < the_right->key;
+}
+
+static void test_rbtree_insert_inline( void )
+{
+  RBTree_Control tree;
+  test_node      a;
+  test_node      b;
+  test_node      c;
+  int            key;
+  bool           is_new_minimum;
+
+  puts( "INIT - Verify _RBTree_Insert_inline" );
+
+  a.key = 1;
+  b.key = 2;
+  c.key = 3;
+
+  _RBTree_Initialize_empty( &tree );
+  _RBTree_Initialize_node( &a.Node );
+  _RBTree_Initialize_node( &b.Node );
+  _RBTree_Initialize_node( &c.Node );
+
+  key = b.key;
+  is_new_minimum = _RBTree_Insert_inline(
+    &tree,
+    &b.Node,
+    &key,
+    test_less
+  );
+  rtems_test_assert( is_new_minimum );
+
+  key = c.key;
+  is_new_minimum = _RBTree_Insert_inline(
+    &tree,
+    &c.Node,
+    &key,
+    test_less
+  );
+  rtems_test_assert( !is_new_minimum );
+
+  key = a.key;
+  is_new_minimum = _RBTree_Insert_inline(
+    &tree,
+    &a.Node,
+    &key,
+    test_less
+  );
+  rtems_test_assert( is_new_minimum );
+}
+
 #define TN( i ) &node_array[ i ].Node
 
 typedef struct {
@@ -2210,6 +2272,7 @@ rtems_task Init( rtems_task_argument ignored )
   }
 
   test_rbtree_min_max();
+  test_rbtree_insert_inline();
   test_rbtree_random_ops();
 
   TEST_END();
diff --git a/testsuites/sptests/sprbtree01/sprbtree01.doc b/testsuites/sptests/sprbtree01/sprbtree01.doc
index 0fb3b3a..bffb562 100644
--- a/testsuites/sptests/sprbtree01/sprbtree01.doc
+++ b/testsuites/sptests/sprbtree01/sprbtree01.doc
@@ -16,6 +16,7 @@ directives:
   rtems_rbtree_insert
   rtems_rbtree_get
   rtems_rbtree_peek
+  _RBTree_Insert_inline
 
 concepts:
 
diff --git a/testsuites/sptests/sprbtree01/sprbtree01.scn b/testsuites/sptests/sprbtree01/sprbtree01.scn
index a18a17f..9cf21f3 100644
--- a/testsuites/sptests/sprbtree01/sprbtree01.scn
+++ b/testsuites/sptests/sprbtree01/sprbtree01.scn
@@ -18,7 +18,6 @@ INIT - Removing 100 nodes
 INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]
 INIT - Verify rtems_rbtree_find
 INIT - Verify rtems_rbtree_predecessor/successor
-INIT - Verify rtems_rbtree_find_control
 INIT - Removing 100 nodes
 INIT - Insert 20 random numbers
 INIT - Removing 20 nodes
@@ -32,5 +31,6 @@ INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]
 INIT - Verify rtems_rbtree_find in a duplicate tree
 INIT - Removing 100 nodes
 INIT - Verify min/max node updates
+INIT - Verify _RBTree_Insert_inline
 INIT - Random operations
 *** END OF TEST SPRBTREE 1 ***