2011-08-02 Petr Benes <benesp16@fel.cvut.cz>

	PR 1862/testing
	* sprbtree01/init.c, sprbtree01/sprbtree01.scn: Improve test coverage.

2 files changed, 92 insertions, 6 deletions

diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 4f21d09d74..59b380f595 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -96,6 +96,18 @@ rtems_task Init(
   rtems_rbtree_insert( &rbtree1, &node1.Node );
   rtems_rbtree_insert( &rbtree1, &node2.Node );
 
+  p = _RBTree_Insert_unprotected( &rbtree1, NULL );
+  if (p != (void *)(-1))
+    puts( "INIT - FAILED NULL NODE INSERT" );
+
+  _RBTree_Rotate(NULL, RBT_LEFT);
+  i = (node1.Node.parent == &node2.Node);
+  _RBTree_Rotate( &node1.Node,
+                  !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT
+                );
+  if ( (node1.Node.parent == &node2.Node) != i )
+    puts( "INIT - FAILED FALSE ROTATION" );
+
   if (!rb_assert(rbtree1.root) )
     puts( "INIT - FAILED TREE CHECK" );
 
@@ -324,6 +336,27 @@ rtems_task Init(
     rtems_test_exit(0);
   }
 
+  /* Additional rtems_rbtree_extract test which removes a node
+   * with two children while target node has a left child only. */
+  for ( i = 0; i < 7; i++ ) {
+    node_array[i].id = i;
+    node_array[i].Node.value = i;
+  }
+  rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
+  rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
+  rtems_rbtree_insert( &rbtree1, &node_array[5].Node );
+  rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
+  rtems_rbtree_insert( &rbtree1, &node_array[2].Node );
+  rtems_rbtree_insert( &rbtree1, &node_array[4].Node );
+  rtems_rbtree_insert( &rbtree1, &node_array[6].Node );
+  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
+  /* node_array[1] has now only a left child. */
+  if ( !node_array[1].Node.child[RBT_LEFT] ||
+        node_array[1].Node.child[RBT_RIGHT] )
+     puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
+  rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
+  while( (p = rtems_rbtree_get_max(&rbtree1)) );
+
   puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
   for (i = 0; i < 100; i++) {
     node_array[i].id = 99-i;
@@ -368,32 +401,39 @@ rtems_task Init(
   }
 
   puts( "INIT - Verify rtems_rbtree_find" );
-  p = rtems_rbtree_find(&rbtree1, 50);
-  if(rtems_rbtree_container_of(p,test_node,Node)->id != 50) {
+  p = rtems_rbtree_find(&rbtree1, 30);
+  if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) {
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);
   }
 
   puts( "INIT - Verify rtems_rbtree_predecessor/successor");
   p = rtems_rbtree_predecessor(p);
-  if(p && rtems_rbtree_container_of(p,test_node,Node)->id > 50) {
+  if(p && rtems_rbtree_container_of(p,test_node,Node)->id > 30) {
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);
   }
-  p = rtems_rbtree_find(&rbtree1, 50);
+  p = rtems_rbtree_find(&rbtree1, 30);
   p = rtems_rbtree_successor(p);
-  if(p && rtems_rbtree_container_of(p,test_node,Node)->id < 50) {
+  if(p && rtems_rbtree_container_of(p,test_node,Node)->id < 30) {
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);
   }
 
-  p = rtems_rbtree_find(&rbtree1, 50);
+  p = rtems_rbtree_find(&rbtree1, 30);
   puts( "INIT - Verify rtems_rbtree_find_header" );
   if (rtems_rbtree_find_header(p) != &rbtree1) {
     puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
     rtems_test_exit(0);
   }
 
+  if ( _RBTree_Sibling( NULL ) != NULL )
+    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
+  if ( _RBTree_Sibling( rbtree1.root ) != NULL )
+    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
+  if ( _RBTree_Grandparent( NULL ) != NULL )
+    puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" );
+
   puts( "INIT - Removing 100 nodes" );
 
   for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
@@ -417,6 +457,15 @@ rtems_task Init(
     rtems_test_exit(0);
   }
 
+  if (rtems_rbtree_find_header(p) != NULL) {
+    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
+    rtems_test_exit(0);
+  }
+  if (rtems_rbtree_find_header(NULL) != NULL) {
+    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
+    rtems_test_exit(0);
+  }
+
   puts("INIT - Insert 20 random numbers");
   for (i = 0; i < 20; i++) {
     node_array[i].id = numbers[i];
@@ -450,6 +499,38 @@ rtems_task Init(
     rtems_test_exit(0);
   }
 
+  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
+  for (i = 0; i < 100; i++) {
+    node_array[i].id = i;
+    node_array[i].Node.value = i;
+  }
+  rtems_rbtree_initialize( &rbtree1, &node_array[0].Node, 100,
+                           sizeof(test_node));
+
+  puts( "INIT - Removing 100 nodes" );
+
+  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+    if ( id > 99 ) {
+      puts( "INIT - TOO MANY NODES ON RBTREE" );
+      rtems_test_exit(0);
+    }
+
+    if ( t->id != id ) {
+      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+      rtems_test_exit(0);
+    }
+
+    if (!rb_assert(rbtree1.root) )
+      puts( "INIT - FAILED TREE CHECK" );
+  }
+
+  if(!rtems_rbtree_is_empty(&rbtree1)) {
+    puts( "INIT - TREE NOT EMPTY" );
+    rtems_test_exit(0);
+  }
+
   puts( "*** END OF RTEMS RBTREE API TEST ***" );
   rtems_test_exit(0);
 }
diff --git a/testsuites/sptests/sprbtree01/sprbtree01.scn b/testsuites/sptests/sprbtree01/sprbtree01.scn
index 6d9fbe80b0..3060a96f7e 100644
--- a/testsuites/sptests/sprbtree01/sprbtree01.scn
+++ b/testsuites/sptests/sprbtree01/sprbtree01.scn
@@ -17,6 +17,11 @@ INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]
 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_header
 INIT - Removing 100 nodes
+INIT - Insert 20 random numbers
+INIT - Removing 20 nodes
+INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]
+INIT - Removing 100 nodes
 *** END OF RTEMS RBTREE API TEST ***