diff options
Diffstat (limited to 'testsuites/sptests/sprbtree01/init.c')
-rw-r--r-- | testsuites/sptests/sprbtree01/init.c | 416 |
1 files changed, 416 insertions, 0 deletions
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 */ |