From 142b3b810ff03b93884cccf9c83d1e0de686dad8 Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Mon, 4 Apr 2011 18:45:38 +0000 Subject: 2011-04-04 Gedare Bloom 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. --- testsuites/sptests/ChangeLog | 7 + testsuites/sptests/Makefile.am | 4 +- testsuites/sptests/configure.ac | 1 + testsuites/sptests/sprbtree01/.cvsignore | 2 + testsuites/sptests/sprbtree01/Makefile.am | 28 ++ testsuites/sptests/sprbtree01/init.c | 416 +++++++++++++++++++++++++++ testsuites/sptests/sprbtree01/sprbtree01.doc | 25 ++ testsuites/sptests/sprbtree01/sprbtree01.scn | 19 ++ 8 files changed, 500 insertions(+), 2 deletions(-) create mode 100644 testsuites/sptests/sprbtree01/.cvsignore create mode 100644 testsuites/sptests/sprbtree01/Makefile.am create mode 100644 testsuites/sptests/sprbtree01/init.c create mode 100644 testsuites/sptests/sprbtree01/sprbtree01.doc create mode 100644 testsuites/sptests/sprbtree01/sprbtree01.scn (limited to 'testsuites/sptests') 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 + + 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 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 +#include + +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 + +/* 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 *** -- cgit v1.2.3