2011-04-04 Gedare Bloom <giddyup44@yahoo.com>

	PR 1641/cpukit
	* Makefile.am, configure.ac: Create testcase for red black tree.
	* sprbtree01/init.c, sprbtree01/Makefile.am, sprbtree01/sprbtree01.doc,
	sprbtree01/sprbtree01.scn: New files.

8 files changed, 500 insertions, 2 deletions

diff --git a/testsuites/sptests/ChangeLog b/testsuites/sptests/ChangeLog
index 14e6e5e367..9823102e88 100644
--- a/testsuites/sptests/ChangeLog
+++ b/testsuites/sptests/ChangeLog
@@ -1,3 +1,10 @@
+2011-04-04	Gedare Bloom <giddyup44@yahoo.com>
+
+	PR 1641/cpukit
+	* Makefile.am, configure.ac: Create testcase for red black tree.
+	* sprbtree01/init.c, sprbtree01/Makefile.am, sprbtree01/sprbtree01.doc,
+	sprbtree01/sprbtree01.scn: New files.
+
 2011-03-16	Jennifer Averett <jennifer.averett@OARcorp.com>
 
 	PR 1729/cpukit
diff --git a/testsuites/sptests/Makefile.am b/testsuites/sptests/Makefile.am
index eee0654712..c61c975b5f 100644
--- a/testsuites/sptests/Makefile.am
+++ b/testsuites/sptests/Makefile.am
@@ -16,8 +16,8 @@ SUBDIRS = \
     sp60      sp62 sp63 sp64 sp65 sp66 sp67 sp68 sp69 \
     sp70 sp71 sp72 sp73 \
     spassoc01 spchain spclockget spcoverage spobjgetnext \
-    spnotepad01 spprintk spprivenv01 spsize spstkalloc spthreadq01 \
-    spwatchdog spwkspace \
+    spnotepad01 spprintk spprivenv01 sprbtree01 spsize spstkalloc \
+		spthreadq01 spwatchdog spwkspace \
     sperror01 sperror02 sperror03 \
     spfatal01 spfatal02 spfatal03 spfatal04 spfatal05 spfatal06 spfatal07 \
     spfatal08 spfatal09 spfatal10 spfatal11 spfatal12 spfatal13 spfatal14 \
diff --git a/testsuites/sptests/configure.ac b/testsuites/sptests/configure.ac
index d53fc011a7..fff03defdd 100644
--- a/testsuites/sptests/configure.ac
+++ b/testsuites/sptests/configure.ac
@@ -160,6 +160,7 @@ spnotepad01/Makefile
 spobjgetnext/Makefile
 spprintk/Makefile
 spprivenv01/Makefile
+sprbtree01/Makefile
 spsimplesched01/Makefile
 spsimplesched02/Makefile
 spsimplesched03/Makefile
diff --git a/testsuites/sptests/sprbtree01/.cvsignore b/testsuites/sptests/sprbtree01/.cvsignore
new file mode 100644
index 0000000000..282522db03
--- /dev/null
+++ b/testsuites/sptests/sprbtree01/.cvsignore
@@ -0,0 +1,2 @@
+Makefile
+Makefile.in
diff --git a/testsuites/sptests/sprbtree01/Makefile.am b/testsuites/sptests/sprbtree01/Makefile.am
new file mode 100644
index 0000000000..e1763a5b04
--- /dev/null
+++ b/testsuites/sptests/sprbtree01/Makefile.am
@@ -0,0 +1,28 @@
+##
+## $Id$
+##
+
+MANAGERS = all
+
+rtems_tests_PROGRAMS = sprbtree01
+sprbtree01_SOURCES = init.c
+
+dist_rtems_tests_DATA = sprbtree01.scn
+dist_rtems_tests_DATA += sprbtree01.doc
+
+include $(RTEMS_ROOT)/make/custom/@RTEMS_BSP@.cfg
+include $(top_srcdir)/../automake/compile.am
+include $(top_srcdir)/../automake/leaf.am
+
+sprbtree01_LDADD = $(MANAGERS_NOT_WANTED:%=$(PROJECT_LIB)/no-%.rel)
+
+AM_CPPFLAGS += -I$(top_srcdir)/../support/include
+
+LINK_OBJS = $(sprbtree01_OBJECTS) $(sprbtree01_LDADD)
+LINK_LIBS = $(sprbtree01_LDLIBS)
+
+sprbtree01$(EXEEXT): $(sprbtree01_OBJECTS) $(sprbtree01_DEPENDENCIES)
+	@rm -f sprbtree01$(EXEEXT)
+	$(make-exe)
+
+include $(top_srcdir)/../automake/local.am
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
new file mode 100644
index 0000000000..b7e71ce0eb
--- /dev/null
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -0,0 +1,416 @@
+/*
+ * Copyright (c) 2010 Gedare Bloom.
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#include <tmacros.h>
+#include <rtems/rbtree.h>
+
+int numbers[20] = {
+52, 99, 5, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71};
+
+int numbers_sorted[20] = {
+  5, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99};
+
+typedef struct {
+  int              id;
+  rtems_rbtree_node Node;
+} test_node;
+
+/* 
+ * recursively checks tree. if the tree is built properly it should only 
+ * be a depth of 7 function calls for 100 entries in the tree. 
+ */
+int rb_assert ( rtems_rbtree_node *root )
+{
+  int lh, rh;
+
+  if ( root == NULL )
+    return 1;
+  else {
+    rtems_rbtree_node *ln = rtems_rbtree_left(root);
+    rtems_rbtree_node *rn = rtems_rbtree_right(root);
+
+    /* Consecutive red links */
+    if ( root->color == RBT_RED ) {
+      if ((ln && ln->color == RBT_RED)  || (rn && rn->color == RBT_RED)) {
+        puts ( "Red violation" );
+        return -1;
+      }
+    }
+
+      lh = rb_assert ( ln );
+      rh = rb_assert ( rn );
+
+    /* Invalid binary search tree */
+    if ( ( ln != NULL && ln->value >= root->value )
+        || ( rn != NULL && rn->value <= root->value ) )
+    {
+      puts ( "Binary tree violation" );
+      return -1;
+    }
+
+    /* Black height mismatch */
+    if ( lh != -1 && rh != -1 && lh != rh ) {
+      puts ( "Black violation" );
+      return -1;
+    }
+
+    /* Only count black links */
+    if ( lh != -1 && rh != -1 )
+      return ( root->color == RBT_RED ) ? lh : lh + 1;
+    else
+      return -1;
+  }
+}
+
+
+
+rtems_task Init(
+    rtems_task_argument ignored
+    )
+{
+  rtems_rbtree_control  rbtree1;
+  rtems_rbtree_node    *p;
+  test_node            node1, node2;
+  test_node            node_array[100];
+  int                  id;
+  int i;
+
+  puts( "\n\n*** TEST OF RTEMS RBTREE API ***" );
+
+  puts( "Init - Initialize rbtree empty" );
+  rtems_rbtree_initialize_empty( &rbtree1 );
+  
+  /* verify that the rbtree insert work */
+  puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
+  node1.id = 1;
+  node1.Node.value = 1;
+  node2.id = 2;
+  node2.Node.value = 2;
+  rtems_rbtree_insert( &rbtree1, &node1.Node );
+  rtems_rbtree_insert( &rbtree1, &node2.Node );
+
+  if (!rb_assert(rbtree1.root) )
+    puts( "INIT - FAILED TREE CHECK" );
+
+  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
+      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+    if ( id > 2 ) {
+      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 (id < 2) {
+    puts("INIT - NOT ENOUGH NODES ON RBTREE");
+    rtems_test_exit(0);
+  }
+
+  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
+  node2.Node.value = node1.Node.value;
+  rtems_rbtree_insert(&rbtree1, &node1.Node);
+  rtems_rbtree_insert(&rbtree1, &node2.Node);
+  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
+      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+    if ( id > 1 ) {
+      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 (id < 1) {
+    puts("INIT - NOT ENOUGH NODES ON RBTREE");
+    rtems_test_exit(0);
+  }
+  node2.Node.value = 2;
+
+  /* verify that the rbtree is empty */
+  puts( "INIT - Verify rtems_rbtree_is_empty" );
+  if(!rtems_rbtree_is_empty(&rbtree1)) {
+    puts( "INIT - TREE NOT EMPTY" );
+    rtems_test_exit(0);
+  }
+
+  puts( "INIT - Verify rtems_XXX on an empty tree" );
+  if(rtems_rbtree_get_min(&rbtree1)) {
+    puts("INIT - get_min on empty returned non-NULL");
+    rtems_test_exit(0);
+  }
+  if(rtems_rbtree_get_max(&rbtree1)) {
+    puts("INIT - get_max on empty returned non-NULL");
+    rtems_test_exit(0);
+  }
+  if(rtems_rbtree_peek_min(&rbtree1)) {
+    puts("INIT - peek_min on empty returned non-NULL");
+    rtems_test_exit(0);
+  }
+  if(rtems_rbtree_peek_max(&rbtree1)) {
+    puts("INIT - peek_max on empty returned non-NULL");
+    rtems_test_exit(0);
+  }
+
+
+  /* verify that the rbtree insert works after a tree is emptied */
+  puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
+  node1.id = 2;
+  node1.Node.value = 2;
+  node2.id = 1;
+  node2.Node.value = 1;
+  rtems_rbtree_insert( &rbtree1, &node1.Node );
+  rtems_rbtree_insert( &rbtree1, &node2.Node );
+
+  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
+  if(rtems_rbtree_peek_max(&rbtree1)->value - 
+      rtems_rbtree_peek_min(&rbtree1)->value != 1) {
+    puts( "INIT - Peek Min - Max failed" );
+    rtems_test_exit(0);
+  }
+  p = rtems_rbtree_peek_max(&rbtree1);
+  rtems_rbtree_extract(&rbtree1, p);
+  if (p->value != 2) {
+    puts( "INIT - rtems_rbtree_extract failed");
+    rtems_test_exit(0);
+  }
+  rtems_rbtree_insert(&rbtree1, p);
+
+  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
+      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+    if ( id > 2 ) {
+      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);
+    }
+  }
+  
+  puts( "INIT - Verify rtems_rbtree_insert 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_insert( &rbtree1, &node_array[i].Node );
+
+    if (!rb_assert(rbtree1.root) )
+      puts( "INIT - FAILED TREE CHECK" );
+  }
+
+  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( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
+  for (i = 0; i < 100; i++) {
+    node_array[i].id = 99-i;
+    node_array[i].Node.value = 99-i;
+    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+    if (!rb_assert(rbtree1.root) )
+      puts( "INIT - FAILED TREE CHECK" );
+  }
+
+  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( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
+  for (i = 0; i < 100; i++) {
+    node_array[i].id = 99-i;
+    node_array[i].Node.value = 99-i;
+    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+    if (!rb_assert(rbtree1.root) )
+      puts( "INIT - FAILED TREE CHECK" );
+  }
+
+  puts( "INIT - Removing 100 nodes" );
+
+  for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
+      p = rtems_rbtree_get_max(&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 != 99-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( "INIT - Verify rtems_rbtree_get_max 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_insert( &rbtree1, &node_array[i].Node );
+
+    if (!rb_assert(rbtree1.root) )
+      puts( "INIT - FAILED TREE CHECK" );
+  }
+
+  puts( "INIT - Verify rtems_rbtree_find" );
+  p = rtems_rbtree_find(&rbtree1, 50);
+  if(rtems_rbtree_container_of(p,test_node,Node)->id != 50) {
+    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) {
+    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+    rtems_test_exit(0);
+  }
+  p = rtems_rbtree_find(&rbtree1, 50);
+  p = rtems_rbtree_successor(p);
+  if(p && rtems_rbtree_container_of(p,test_node,Node)->id < 50) {
+    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+    rtems_test_exit(0);
+  }
+
+  p = rtems_rbtree_find(&rbtree1, 50);
+  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);
+  }
+
+  puts( "INIT - Removing 100 nodes" );
+
+  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
+      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
+    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+    if ( id < 0 ) {
+      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("INIT - Insert 20 random numbers");
+  for (i = 0; i < 20; i++) {
+    node_array[i].id = numbers[i];
+    node_array[i].Node.value = numbers[i];
+    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+    if (!rb_assert(rbtree1.root) )
+      puts( "INIT - FAILED TREE CHECK" );
+  }
+
+  puts( "INIT - Removing 20 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 > 19 ) {
+      puts( "INIT - TOO MANY NODES ON RBTREE" );
+      rtems_test_exit(0);
+    }
+    if ( t->id != numbers_sorted[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);
+}
+
+/* configuration information */
+
+#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
+#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
+
+#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
+#define CONFIGURE_MAXIMUM_TASKS 1
+
+#define CONFIGURE_INIT
+#include <rtems/confdefs.h>
+
+/* global variables */
diff --git a/testsuites/sptests/sprbtree01/sprbtree01.doc b/testsuites/sptests/sprbtree01/sprbtree01.doc
new file mode 100644
index 0000000000..908d4e5ab3
--- /dev/null
+++ b/testsuites/sptests/sprbtree01/sprbtree01.doc
@@ -0,0 +1,25 @@
+#
+#  $Id$
+#
+#  COPYRIGHT (c) 1989-2009.
+#  On-Line Applications Research Corporation (OAR).
+#
+#  The license and distribution terms for this file may be
+#  found in the file LICENSE in this distribution or at
+#  http://www.rtems.com/license/LICENSE.
+#
+
+This file describes the directives and concepts tested by this test set.
+
+test set name:  sprbtree01
+
+directives:
+
+  rtems_rbtree_initialize_empty
+  rtems_rbtree_insert
+  rtems_rbtree_get
+  rtems_rbtree_peek
+
+concepts:
+
++ Ensure that the rbtree operations listed above behave as defined.
diff --git a/testsuites/sptests/sprbtree01/sprbtree01.scn b/testsuites/sptests/sprbtree01/sprbtree01.scn
new file mode 100644
index 0000000000..c1b1b3161f
--- /dev/null
+++ b/testsuites/sptests/sprbtree01/sprbtree01.scn
@@ -0,0 +1,19 @@
+*** TEST OF RTEMS RBTREE API ***
+Init - Initialize rbtree empty
+INIT - Verify rtems_rbtree_insert with two nodes
+INIT - Verify rtems_rbtree_insert with the same value twice
+INIT - Verify rtems_rbtree_is_empty
+INIT - Verify rtems_XXX on an empty tree
+INIT - Verify rtems_rbtree_insert after empty tree
+INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract
+INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]
+INIT - Removing 100 nodes
+INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]
+INIT - Removing 100 nodes
+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_find_header
+INIT - Removing 100 nodes
+*** END OF RTEMS RBTREE API TEST ***