From d7c93070cc48c9cd2ccbade4198ae09c33e80a8b Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 21 Aug 2015 05:04:27 +0200 Subject: sptests/sprbtree01: Avoid internal API --- testsuites/sptests/sprbtree01/init.c | 1890 +++++++++++++++++----------------- 1 file changed, 951 insertions(+), 939 deletions(-) diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index 669ed979aa..102b6c43a6 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -35,6 +35,15 @@ typedef struct { static test_node node_array[100]; +#define RED RBT_RED + +#define BLACK RBT_BLACK + +static int rb_color( const rtems_rbtree_node *n ) +{ + return n->color; +} + static rtems_rbtree_compare_result test_compare_function ( const rtems_rbtree_node *n1, const rtems_rbtree_node *n2 @@ -93,8 +102,11 @@ static int rb_assert ( rtems_rbtree_node *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)) { + if ( rb_color( root ) == RED ) { + if ( + ( ln && rb_color( ln ) == RED ) + || ( rn && rb_color( rn ) == RED ) + ) { puts ( "Red violation" ); return -1; } @@ -119,7 +131,7 @@ static int rb_assert ( rtems_rbtree_node *root ) /* Only count black links */ if ( lh != -1 && rh != -1 ) - return ( root->color == RBT_RED ) ? lh : lh + 1; + return ( rb_color( root ) == RED ) ? lh : lh + 1; else return -1; } @@ -142,9 +154,9 @@ static void min_max_insert( ) { rb_insert_multi( tree, node ); - rtems_test_assert( rb_assert( tree->root ) != -1 ); - rtems_test_assert( tree->first[ 0 ] == min ); - rtems_test_assert( tree->first[ 1 ] == max ); + rtems_test_assert( rb_assert( rtems_rbtree_root( tree ) ) != -1 ); + rtems_test_assert( rtems_rbtree_min( tree ) == min ); + rtems_test_assert( rtems_rbtree_max( tree ) == max ); } static void min_max_extract( @@ -155,9 +167,9 @@ static void min_max_extract( ) { rtems_rbtree_extract( tree, node ); - rtems_test_assert( rb_assert( tree->root ) != -1 ); - rtems_test_assert( tree->first[ 0 ] == min ); - rtems_test_assert( tree->first[ 1 ] == max ); + rtems_test_assert( rb_assert( rtems_rbtree_root( tree ) ) != -1 ); + rtems_test_assert( rtems_rbtree_min( tree ) == min ); + rtems_test_assert( rtems_rbtree_max( tree ) == max ); } static void test_rbtree_min_max(void) @@ -170,7 +182,7 @@ static void test_rbtree_min_max(void) puts( "INIT - Verify min/max node updates" ); rtems_rbtree_initialize_empty( &tree ); - rtems_test_assert( rb_assert( tree.root ) == 1 ); + rtems_test_assert( rb_assert( rtems_rbtree_root( &tree ) ) == 1 ); node = &some_nodes[ 0 ].Node; min = node; @@ -233,273 +245,273 @@ typedef struct { } test_node_description; static const test_node_description test_insert_tree_0[] = { - { 52, NULL, NULL, NULL , RBT_BLACK } + { 52, NULL, NULL, NULL , BLACK } }; static const test_node_description test_insert_tree_1[] = { - { 52, NULL, NULL, TN( 1 ) , RBT_BLACK }, - { 99, TN( 0 ), NULL, NULL , RBT_RED } + { 52, NULL, NULL, TN( 1 ) , BLACK }, + { 99, TN( 0 ), NULL, NULL , RED } }; static const test_node_description test_insert_tree_2[] = { - { 0, TN( 0 ), NULL, NULL , RBT_RED }, - { 52, NULL, TN( 2 ), TN( 1 ) , RBT_BLACK }, - { 99, TN( 0 ), NULL, NULL , RBT_RED } + { 0, TN( 0 ), NULL, NULL , RED }, + { 52, NULL, TN( 2 ), TN( 1 ) , BLACK }, + { 99, TN( 0 ), NULL, NULL , RED } }; static const test_node_description test_insert_tree_3[] = { - { 0, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 52, NULL, TN( 2 ), TN( 1 ) , RBT_BLACK }, - { 85, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK } + { 0, TN( 0 ), NULL, NULL , BLACK }, + { 52, NULL, TN( 2 ), TN( 1 ) , BLACK }, + { 85, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 0 ), TN( 3 ), NULL , BLACK } }; static const test_node_description test_insert_tree_4[] = { - { 0, TN( 0 ), NULL, TN( 4 ) , RBT_BLACK }, - { 43, TN( 2 ), NULL, NULL , RBT_RED }, - { 52, NULL, TN( 2 ), TN( 1 ) , RBT_BLACK }, - { 85, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK } + { 0, TN( 0 ), NULL, TN( 4 ) , BLACK }, + { 43, TN( 2 ), NULL, NULL , RED }, + { 52, NULL, TN( 2 ), TN( 1 ) , BLACK }, + { 85, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 0 ), TN( 3 ), NULL , BLACK } }; static const test_node_description test_insert_tree_5[] = { - { 0, TN( 4 ), NULL, NULL , RBT_RED }, - { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_BLACK }, - { 44, TN( 4 ), NULL, NULL , RBT_RED }, - { 52, NULL, TN( 4 ), TN( 1 ) , RBT_BLACK }, - { 85, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK } + { 0, TN( 4 ), NULL, NULL , RED }, + { 43, TN( 0 ), TN( 2 ), TN( 5 ) , BLACK }, + { 44, TN( 4 ), NULL, NULL , RED }, + { 52, NULL, TN( 4 ), TN( 1 ) , BLACK }, + { 85, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 0 ), TN( 3 ), NULL , BLACK } }; static const test_node_description test_insert_tree_6[] = { - { 0, TN( 4 ), NULL, TN( 6 ) , RBT_BLACK }, - { 10, TN( 2 ), NULL, NULL , RBT_RED }, - { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_RED }, - { 44, TN( 4 ), NULL, NULL , RBT_BLACK }, - { 52, NULL, TN( 4 ), TN( 1 ) , RBT_BLACK }, - { 85, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK } + { 0, TN( 4 ), NULL, TN( 6 ) , BLACK }, + { 10, TN( 2 ), NULL, NULL , RED }, + { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED }, + { 44, TN( 4 ), NULL, NULL , BLACK }, + { 52, NULL, TN( 4 ), TN( 1 ) , BLACK }, + { 85, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 0 ), TN( 3 ), NULL , BLACK } }; static const test_node_description test_insert_tree_7[] = { - { 0, TN( 4 ), NULL, TN( 6 ) , RBT_BLACK }, - { 10, TN( 2 ), NULL, NULL , RBT_RED }, - { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_RED }, - { 44, TN( 4 ), NULL, NULL , RBT_BLACK }, - { 52, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK }, - { 60, TN( 3 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK }, - { 99, TN( 3 ), NULL, NULL , RBT_RED } + { 0, TN( 4 ), NULL, TN( 6 ) , BLACK }, + { 10, TN( 2 ), NULL, NULL , RED }, + { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED }, + { 44, TN( 4 ), NULL, NULL , BLACK }, + { 52, NULL, TN( 4 ), TN( 3 ) , BLACK }, + { 60, TN( 3 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK }, + { 99, TN( 3 ), NULL, NULL , RED } }; static const test_node_description test_insert_tree_8[] = { - { 0, TN( 4 ), NULL, TN( 6 ) , RBT_BLACK }, - { 10, TN( 2 ), NULL, NULL , RBT_RED }, - { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_RED }, - { 44, TN( 4 ), NULL, TN( 8 ) , RBT_BLACK }, - { 50, TN( 5 ), NULL, NULL , RBT_RED }, - { 52, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK }, - { 60, TN( 3 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK }, - { 99, TN( 3 ), NULL, NULL , RBT_RED } + { 0, TN( 4 ), NULL, TN( 6 ) , BLACK }, + { 10, TN( 2 ), NULL, NULL , RED }, + { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED }, + { 44, TN( 4 ), NULL, TN( 8 ) , BLACK }, + { 50, TN( 5 ), NULL, NULL , RED }, + { 52, NULL, TN( 4 ), TN( 3 ) , BLACK }, + { 60, TN( 3 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK }, + { 99, TN( 3 ), NULL, NULL , RED } }; static const test_node_description test_insert_tree_9[] = { - { 0, TN( 6 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 6 ), NULL, NULL , RBT_RED }, - { 43, TN( 0 ), TN( 6 ), TN( 5 ) , RBT_RED }, - { 44, TN( 4 ), NULL, TN( 8 ) , RBT_BLACK }, - { 50, TN( 5 ), NULL, NULL , RBT_RED }, - { 52, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK }, - { 60, TN( 3 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK }, - { 99, TN( 3 ), NULL, NULL , RBT_RED } + { 0, TN( 6 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 19, TN( 6 ), NULL, NULL , RED }, + { 43, TN( 0 ), TN( 6 ), TN( 5 ) , RED }, + { 44, TN( 4 ), NULL, TN( 8 ) , BLACK }, + { 50, TN( 5 ), NULL, NULL , RED }, + { 52, NULL, TN( 4 ), TN( 3 ) , BLACK }, + { 60, TN( 3 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK }, + { 99, TN( 3 ), NULL, NULL , RED } }; static const test_node_description test_insert_tree_10[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_RED }, - { 19, TN( 6 ), NULL, NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 0 ), NULL, TN( 8 ) , RBT_BLACK }, - { 50, TN( 5 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RBT_RED }, - { 60, TN( 3 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK }, - { 99, TN( 3 ), NULL, NULL , RBT_RED } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RED }, + { 19, TN( 6 ), NULL, NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 0 ) , BLACK }, + { 44, TN( 0 ), NULL, TN( 8 ) , BLACK }, + { 50, TN( 5 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RED }, + { 60, TN( 3 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK }, + { 99, TN( 3 ), NULL, NULL , RED } }; static const test_node_description test_insert_tree_11[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 6 ), NULL, NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 0 ), NULL, TN( 8 ) , RBT_BLACK }, - { 50, TN( 5 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RBT_BLACK }, - { 60, TN( 3 ), NULL, TN( 11 ) , RBT_BLACK }, - { 68, TN( 7 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED }, - { 99, TN( 3 ), NULL, NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 19, TN( 6 ), NULL, NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 0 ) , BLACK }, + { 44, TN( 0 ), NULL, TN( 8 ) , BLACK }, + { 50, TN( 5 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 5 ), TN( 3 ) , BLACK }, + { 60, TN( 3 ), NULL, TN( 11 ) , BLACK }, + { 68, TN( 7 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED }, + { 99, TN( 3 ), NULL, NULL , BLACK } }; static const test_node_description test_insert_tree_12[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 6 ), NULL, NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 12 ), TN( 3 ) , RBT_BLACK }, - { 60, TN( 3 ), NULL, TN( 11 ) , RBT_BLACK }, - { 68, TN( 7 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED }, - { 99, TN( 3 ), NULL, NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 19, TN( 6 ), NULL, NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 0 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK }, + { 60, TN( 3 ), NULL, TN( 11 ) , BLACK }, + { 68, TN( 7 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED }, + { 99, TN( 3 ), NULL, NULL , BLACK } }; static const test_node_description test_insert_tree_13[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 6 ), NULL, NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 12 ), TN( 3 ) , RBT_BLACK }, - { 57, TN( 7 ), NULL, NULL , RBT_RED }, - { 60, TN( 3 ), TN( 13 ), TN( 11 ) , RBT_BLACK }, - { 68, TN( 7 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED }, - { 99, TN( 3 ), NULL, NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 19, TN( 6 ), NULL, NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 0 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK }, + { 57, TN( 7 ), NULL, NULL , RED }, + { 60, TN( 3 ), TN( 13 ), TN( 11 ) , BLACK }, + { 68, TN( 7 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED }, + { 99, TN( 3 ), NULL, NULL , BLACK } }; static const test_node_description test_insert_tree_14[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 17, TN( 9 ), NULL, NULL , RBT_RED }, - { 19, TN( 6 ), TN( 14 ), NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 12 ), TN( 3 ) , RBT_BLACK }, - { 57, TN( 7 ), NULL, NULL , RBT_RED }, - { 60, TN( 3 ), TN( 13 ), TN( 11 ) , RBT_BLACK }, - { 68, TN( 7 ), NULL, NULL , RBT_RED }, - { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED }, - { 99, TN( 3 ), NULL, NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 17, TN( 9 ), NULL, NULL , RED }, + { 19, TN( 6 ), TN( 14 ), NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 0 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK }, + { 57, TN( 7 ), NULL, NULL , RED }, + { 60, TN( 3 ), TN( 13 ), TN( 11 ) , BLACK }, + { 68, TN( 7 ), NULL, NULL , RED }, + { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED }, + { 99, TN( 3 ), NULL, NULL , BLACK } }; static const test_node_description test_insert_tree_15[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 17, TN( 9 ), NULL, NULL , RBT_RED }, - { 19, TN( 6 ), TN( 14 ), NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_RED }, - { 68, TN( 3 ), TN( 15 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED }, - { 99, TN( 3 ), NULL, NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 17, TN( 9 ), NULL, NULL , RED }, + { 19, TN( 6 ), TN( 14 ), NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , RED }, + { 68, TN( 3 ), TN( 15 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED }, + { 99, TN( 3 ), NULL, NULL , BLACK } }; static const test_node_description test_insert_tree_16[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK }, - { 17, TN( 9 ), NULL, NULL , RBT_RED }, - { 19, TN( 6 ), TN( 14 ), NULL , RBT_BLACK }, - { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_RED }, - { 68, TN( 3 ), TN( 15 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK }, + { 17, TN( 9 ), NULL, NULL , RED }, + { 19, TN( 6 ), TN( 14 ), NULL , BLACK }, + { 43, NULL, TN( 6 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , RED }, + { 68, TN( 3 ), TN( 15 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_insert_tree_17[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 14 ) , RBT_BLACK }, - { 12, TN( 14 ), NULL, NULL , RBT_RED }, - { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_RED }, - { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_RED }, - { 68, TN( 3 ), TN( 15 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK }, + { 12, TN( 14 ), NULL, NULL , RED }, + { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , RED }, + { 43, NULL, TN( 6 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , RED }, + { 68, TN( 3 ), TN( 15 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_insert_tree_18[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 14 ) , RBT_BLACK }, - { 12, TN( 14 ), NULL, NULL , RBT_RED }, - { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_RED }, - { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_RED }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_BLACK }, - { 77, TN( 11 ), NULL, NULL , RBT_RED }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK }, + { 12, TN( 14 ), NULL, NULL , RED }, + { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , RED }, + { 43, NULL, TN( 6 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , RED }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , BLACK }, + { 77, TN( 11 ), NULL, NULL , RED }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_insert_tree_19[] = { - { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK }, - { 8, TN( 2 ), NULL, NULL , RBT_RED }, - { 10, TN( 4 ), TN( 2 ), TN( 14 ) , RBT_BLACK }, - { 12, TN( 14 ), NULL, NULL , RBT_RED }, - { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_RED }, - { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 0, TN( 6 ), NULL, TN( 10 ) , BLACK }, + { 8, TN( 2 ), NULL, NULL , RED }, + { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK }, + { 12, TN( 14 ), NULL, NULL , RED }, + { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , RED }, + { 43, NULL, TN( 6 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description *const test_insert_trees[] = { @@ -526,250 +538,250 @@ static const test_node_description *const test_insert_trees[] = { }; static const test_node_description test_remove_tree_0[] = { - { 8, TN( 6 ), NULL, NULL , RBT_BLACK }, - { 10, TN( 4 ), TN( 10 ), TN( 14 ) , RBT_BLACK }, - { 12, TN( 14 ), NULL, NULL , RBT_RED }, - { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_RED }, - { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 8, TN( 6 ), NULL, NULL , BLACK }, + { 10, TN( 4 ), TN( 10 ), TN( 14 ) , BLACK }, + { 12, TN( 14 ), NULL, NULL , RED }, + { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , RED }, + { 43, NULL, TN( 6 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_1[] = { - { 10, TN( 14 ), NULL, TN( 17 ) , RBT_BLACK }, - { 12, TN( 6 ), NULL, NULL , RBT_RED }, - { 17, TN( 4 ), TN( 6 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_BLACK }, - { 43, NULL, TN( 14 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 10, TN( 14 ), NULL, TN( 17 ) , BLACK }, + { 12, TN( 6 ), NULL, NULL , RED }, + { 17, TN( 4 ), TN( 6 ), TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , BLACK }, + { 43, NULL, TN( 14 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_2[] = { - { 12, TN( 14 ), NULL, NULL , RBT_BLACK }, - { 17, TN( 4 ), TN( 17 ), TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_BLACK }, - { 43, NULL, TN( 14 ), TN( 7 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 12, TN( 14 ), NULL, NULL , BLACK }, + { 17, TN( 4 ), TN( 17 ), TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , BLACK }, + { 43, NULL, TN( 14 ), TN( 7 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_3[] = { - { 17, TN( 4 ), NULL, TN( 9 ) , RBT_BLACK }, - { 19, TN( 14 ), NULL, NULL , RBT_RED }, - { 43, TN( 7 ), TN( 14 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RBT_RED }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 17, TN( 4 ), NULL, TN( 9 ) , BLACK }, + { 19, TN( 14 ), NULL, NULL , RED }, + { 43, TN( 7 ), TN( 14 ), TN( 0 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RED }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, NULL, TN( 4 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_4[] = { - { 19, TN( 4 ), NULL, NULL , RBT_BLACK }, - { 43, TN( 7 ), TN( 9 ), TN( 0 ) , RBT_BLACK }, - { 44, TN( 12 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RBT_RED }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 19, TN( 4 ), NULL, NULL , BLACK }, + { 43, TN( 7 ), TN( 9 ), TN( 0 ) , BLACK }, + { 44, TN( 12 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RED }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, NULL, TN( 4 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_5[] = { - { 43, TN( 12 ), NULL, TN( 5 ) , RBT_BLACK }, - { 44, TN( 4 ), NULL, NULL , RBT_RED }, - { 48, TN( 0 ), TN( 4 ), TN( 8 ) , RBT_RED }, - { 50, TN( 12 ), NULL, NULL , RBT_BLACK }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 43, TN( 12 ), NULL, TN( 5 ) , BLACK }, + { 44, TN( 4 ), NULL, NULL , RED }, + { 48, TN( 0 ), TN( 4 ), TN( 8 ) , RED }, + { 50, TN( 12 ), NULL, NULL , BLACK }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, NULL, TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_6[] = { - { 44, TN( 12 ), NULL, NULL , RBT_BLACK }, - { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_RED }, - { 50, TN( 12 ), NULL, NULL , RBT_BLACK }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 44, TN( 12 ), NULL, NULL , BLACK }, + { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RED }, + { 50, TN( 12 ), NULL, NULL , BLACK }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, NULL, TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_7[] = { - { 48, TN( 0 ), NULL, TN( 8 ) , RBT_BLACK }, - { 50, TN( 12 ), NULL, NULL , RBT_RED }, - { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 48, TN( 0 ), NULL, TN( 8 ) , BLACK }, + { 50, TN( 12 ), NULL, NULL , RED }, + { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, NULL, TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_8[] = { - { 50, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 52, TN( 7 ), TN( 8 ), TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_BLACK }, - { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK }, - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 50, TN( 0 ), NULL, NULL , BLACK }, + { 52, TN( 7 ), TN( 8 ), TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , BLACK }, + { 60, NULL, TN( 0 ), TN( 3 ) , BLACK }, + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 11 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_9[] = { - { 52, TN( 7 ), NULL, TN( 13 ) , RBT_BLACK }, - { 57, TN( 0 ), NULL, NULL , RBT_RED }, - { 60, TN( 11 ), TN( 0 ), TN( 15 ) , RBT_BLACK }, - { 67, TN( 7 ), NULL, NULL , RBT_BLACK }, - { 68, NULL, TN( 7 ), TN( 3 ) , RBT_BLACK }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 52, TN( 7 ), NULL, TN( 13 ) , BLACK }, + { 57, TN( 0 ), NULL, NULL , RED }, + { 60, TN( 11 ), TN( 0 ), TN( 15 ) , BLACK }, + { 67, TN( 7 ), NULL, NULL , BLACK }, + { 68, NULL, TN( 7 ), TN( 3 ) , BLACK }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 3 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 11 ), TN( 18 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_10[] = { - { 57, TN( 7 ), NULL, NULL , RBT_BLACK }, - { 60, TN( 11 ), TN( 13 ), TN( 15 ) , RBT_BLACK }, - { 67, TN( 7 ), NULL, NULL , RBT_BLACK }, - { 68, NULL, TN( 7 ), TN( 3 ) , RBT_BLACK }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 57, TN( 7 ), NULL, NULL , BLACK }, + { 60, TN( 11 ), TN( 13 ), TN( 15 ) , BLACK }, + { 67, TN( 7 ), NULL, NULL , BLACK }, + { 68, NULL, TN( 7 ), TN( 3 ) , BLACK }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 3 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 11 ), TN( 18 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_11[] = { - { 60, TN( 11 ), NULL, TN( 15 ) , RBT_BLACK }, - { 67, TN( 7 ), NULL, NULL , RBT_RED }, - { 68, NULL, TN( 7 ), TN( 3 ) , RBT_BLACK }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_RED }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 60, TN( 11 ), NULL, TN( 15 ) , BLACK }, + { 67, TN( 7 ), NULL, NULL , RED }, + { 68, NULL, TN( 7 ), TN( 3 ) , BLACK }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 3 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RED }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_12[] = { - { 67, TN( 11 ), NULL, NULL , RBT_BLACK }, - { 68, NULL, TN( 15 ), TN( 3 ) , RBT_BLACK }, - { 71, TN( 18 ), NULL, NULL , RBT_RED }, - { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK }, - { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_RED }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 67, TN( 11 ), NULL, NULL , BLACK }, + { 68, NULL, TN( 15 ), TN( 3 ) , BLACK }, + { 71, TN( 18 ), NULL, NULL , RED }, + { 77, TN( 3 ), TN( 19 ), NULL , BLACK }, + { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RED }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_13[] = { - { 68, TN( 19 ), NULL, NULL , RBT_BLACK }, - { 71, TN( 3 ), TN( 11 ), TN( 18 ) , RBT_RED }, - { 77, TN( 19 ), NULL, NULL , RBT_BLACK }, - { 85, NULL, TN( 19 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 68, TN( 19 ), NULL, NULL , BLACK }, + { 71, TN( 3 ), TN( 11 ), TN( 18 ) , RED }, + { 77, TN( 19 ), NULL, NULL , BLACK }, + { 85, NULL, TN( 19 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_14[] = { - { 71, TN( 3 ), NULL, TN( 18 ) , RBT_BLACK }, - { 77, TN( 19 ), NULL, NULL , RBT_RED }, - { 85, NULL, TN( 19 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 71, TN( 3 ), NULL, TN( 18 ) , BLACK }, + { 77, TN( 19 ), NULL, NULL , RED }, + { 85, NULL, TN( 19 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_15[] = { - { 77, TN( 3 ), NULL, NULL , RBT_BLACK }, - { 85, NULL, TN( 18 ), TN( 1 ) , RBT_BLACK }, - { 90, TN( 1 ), NULL, NULL , RBT_RED }, - { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK } + { 77, TN( 3 ), NULL, NULL , BLACK }, + { 85, NULL, TN( 18 ), TN( 1 ) , BLACK }, + { 90, TN( 1 ), NULL, NULL , RED }, + { 99, TN( 3 ), TN( 16 ), NULL , BLACK } }; static const test_node_description test_remove_tree_16[] = { - { 85, TN( 16 ), NULL, NULL , RBT_BLACK }, - { 90, NULL, TN( 3 ), TN( 1 ) , RBT_BLACK }, - { 99, TN( 16 ), NULL, NULL , RBT_BLACK } + { 85, TN( 16 ), NULL, NULL , BLACK }, + { 90, NULL, TN( 3 ), TN( 1 ) , BLACK }, + { 99, TN( 16 ), NULL, NULL , BLACK } }; static const test_node_description test_remove_tree_17[] = { - { 90, NULL, NULL, TN( 1 ) , RBT_BLACK }, - { 99, TN( 16 ), NULL, NULL , RBT_RED } + { 90, NULL, NULL, TN( 1 ) , BLACK }, + { 99, TN( 16 ), NULL, NULL , RED } }; static const test_node_description test_remove_tree_18[] = { - { 99, NULL, NULL, NULL , RBT_BLACK } + { 99, NULL, NULL, NULL , BLACK } }; static const test_node_description *const test_remove_trees[] = { @@ -822,7 +834,7 @@ static bool visit_nodes( rtems_test_assert( td->left == rtems_rbtree_left( &tn->Node ) ); rtems_test_assert( td->right == rtems_rbtree_right( &tn->Node ) ); - rtems_test_assert( td->color == tn->Node.color ); + rtems_test_assert( td->color == rb_color( &tn->Node ) ); ++ctx->current; @@ -830,11 +842,11 @@ static bool visit_nodes( } static const test_node_description random_ops_tree_unique_1[] = { - { 0, NULL, NULL, NULL, RBT_BLACK } + { 0, NULL, NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_1[] = { - { 0, NULL, NULL, NULL, RBT_BLACK } + { 0, NULL, NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_2[] = { @@ -844,679 +856,679 @@ static const test_node_description random_ops_tree_multiple_2[] = { }; static const test_node_description random_ops_tree_unique_3[] = { - { 2, NULL, NULL, NULL, RBT_BLACK } + { 2, NULL, NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_3[] = { - { 1, NULL, NULL, NULL, RBT_BLACK } + { 1, NULL, NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_4[] = { - { 0, NULL, NULL, TN( 3 ), RBT_BLACK }, - { 3, TN( 0 ), NULL, NULL, RBT_RED } + { 0, NULL, NULL, TN( 3 ), BLACK }, + { 3, TN( 0 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_4[] = { - { 0, NULL, NULL, TN( 3 ), RBT_BLACK }, - { 1, TN( 0 ), NULL, NULL, RBT_RED } + { 0, NULL, NULL, TN( 3 ), BLACK }, + { 1, TN( 0 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_5[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, NULL, TN( 0 ), TN( 4 ), RBT_BLACK }, - { 4, TN( 1 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, NULL, TN( 0 ), TN( 4 ), BLACK }, + { 4, TN( 1 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_5[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 0, NULL, TN( 0 ), TN( 4 ), RBT_BLACK }, - { 2, TN( 1 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, RED }, + { 0, NULL, TN( 0 ), TN( 4 ), BLACK }, + { 2, TN( 1 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_6[] = { - { 0, TN( 2 ), NULL, NULL, RBT_RED }, - { 2, NULL, TN( 0 ), NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, RED }, + { 2, NULL, TN( 0 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_6[] = { - { 0, TN( 2 ), NULL, NULL, RBT_RED }, - { 1, NULL, TN( 0 ), NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, RED }, + { 1, NULL, TN( 0 ), NULL, BLACK } }; static const test_node_description random_ops_tree_unique_7[] = { - { 0, TN( 2 ), NULL, TN( 1 ), RBT_BLACK }, - { 1, TN( 0 ), NULL, NULL, RBT_RED }, - { 2, NULL, TN( 0 ), TN( 5 ), RBT_BLACK }, - { 4, TN( 5 ), NULL, NULL, RBT_RED }, - { 5, TN( 2 ), TN( 4 ), NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, TN( 1 ), BLACK }, + { 1, TN( 0 ), NULL, NULL, RED }, + { 2, NULL, TN( 0 ), TN( 5 ), BLACK }, + { 4, TN( 5 ), NULL, NULL, RED }, + { 5, TN( 2 ), TN( 4 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_7[] = { - { 0, TN( 2 ), NULL, TN( 1 ), RBT_BLACK }, - { 0, TN( 0 ), NULL, NULL, RBT_RED }, - { 1, NULL, TN( 0 ), TN( 4 ), RBT_BLACK }, - { 2, TN( 4 ), NULL, NULL, RBT_RED }, - { 2, TN( 2 ), TN( 5 ), NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, TN( 1 ), BLACK }, + { 0, TN( 0 ), NULL, NULL, RED }, + { 1, NULL, TN( 0 ), TN( 4 ), BLACK }, + { 2, TN( 4 ), NULL, NULL, RED }, + { 2, TN( 2 ), TN( 5 ), NULL, BLACK } }; static const test_node_description random_ops_tree_unique_8[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 5 ), TN( 0 ), NULL, RBT_BLACK }, - { 5, NULL, TN( 1 ), TN( 6 ), RBT_BLACK }, - { 6, TN( 5 ), NULL, NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 5 ), TN( 0 ), NULL, BLACK }, + { 5, NULL, TN( 1 ), TN( 6 ), BLACK }, + { 6, TN( 5 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_8[] = { - { 0, TN( 5 ), NULL, TN( 0 ), RBT_BLACK }, - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 2, NULL, TN( 1 ), TN( 6 ), RBT_BLACK }, - { 3, TN( 5 ), NULL, NULL, RBT_BLACK } + { 0, TN( 5 ), NULL, TN( 0 ), BLACK }, + { 0, TN( 1 ), NULL, NULL, RED }, + { 2, NULL, TN( 1 ), TN( 6 ), BLACK }, + { 3, TN( 5 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_9[] = { - { 1, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 6 ), TN( 1 ), TN( 4 ), RBT_RED }, - { 4, TN( 2 ), NULL, TN( 5 ), RBT_BLACK }, - { 5, TN( 4 ), NULL, NULL, RBT_RED }, - { 6, NULL, TN( 2 ), TN( 7 ), RBT_BLACK }, - { 7, TN( 6 ), NULL, TN( 8 ), RBT_BLACK }, - { 8, TN( 7 ), NULL, NULL, RBT_RED } + { 1, TN( 2 ), NULL, NULL, BLACK }, + { 2, TN( 6 ), TN( 1 ), TN( 4 ), RED }, + { 4, TN( 2 ), NULL, TN( 5 ), BLACK }, + { 5, TN( 4 ), NULL, NULL, RED }, + { 6, NULL, TN( 2 ), TN( 7 ), BLACK }, + { 7, TN( 6 ), NULL, TN( 8 ), BLACK }, + { 8, TN( 7 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_9[] = { - { 0, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 6 ), TN( 1 ), TN( 4 ), RBT_RED }, - { 2, TN( 2 ), NULL, TN( 5 ), RBT_BLACK }, - { 2, TN( 4 ), NULL, NULL, RBT_RED }, - { 3, NULL, TN( 2 ), TN( 7 ), RBT_BLACK }, - { 3, TN( 6 ), NULL, TN( 8 ), RBT_BLACK }, - { 4, TN( 7 ), NULL, NULL, RBT_RED } + { 0, TN( 2 ), NULL, NULL, BLACK }, + { 1, TN( 6 ), TN( 1 ), TN( 4 ), RED }, + { 2, TN( 2 ), NULL, TN( 5 ), BLACK }, + { 2, TN( 4 ), NULL, NULL, RED }, + { 3, NULL, TN( 2 ), TN( 7 ), BLACK }, + { 3, TN( 6 ), NULL, TN( 8 ), BLACK }, + { 4, TN( 7 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_10[] = { - { 0, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 6 ), TN( 0 ), TN( 4 ), RBT_RED }, - { 3, TN( 4 ), NULL, NULL, RBT_RED }, - { 4, TN( 2 ), TN( 3 ), NULL, RBT_BLACK }, - { 6, NULL, TN( 2 ), TN( 8 ), RBT_BLACK }, - { 8, TN( 6 ), NULL, NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, BLACK }, + { 2, TN( 6 ), TN( 0 ), TN( 4 ), RED }, + { 3, TN( 4 ), NULL, NULL, RED }, + { 4, TN( 2 ), TN( 3 ), NULL, BLACK }, + { 6, NULL, TN( 2 ), TN( 8 ), BLACK }, + { 8, TN( 6 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_10[] = { - { 0, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 6 ), TN( 0 ), TN( 4 ), RBT_RED }, - { 1, TN( 4 ), NULL, NULL, RBT_RED }, - { 2, TN( 2 ), TN( 3 ), NULL, RBT_BLACK }, - { 3, NULL, TN( 2 ), TN( 8 ), RBT_BLACK }, - { 4, TN( 6 ), NULL, NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, BLACK }, + { 1, TN( 6 ), TN( 0 ), TN( 4 ), RED }, + { 1, TN( 4 ), NULL, NULL, RED }, + { 2, TN( 2 ), TN( 3 ), NULL, BLACK }, + { 3, NULL, TN( 2 ), TN( 8 ), BLACK }, + { 4, TN( 6 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_11[] = { - { 2, TN( 6 ), NULL, NULL, RBT_BLACK }, - { 6, NULL, TN( 2 ), TN( 8 ), RBT_BLACK }, - { 7, TN( 8 ), NULL, NULL, RBT_RED }, - { 8, TN( 6 ), TN( 7 ), TN( 9 ), RBT_BLACK }, - { 9, TN( 8 ), NULL, NULL, RBT_RED } + { 2, TN( 6 ), NULL, NULL, BLACK }, + { 6, NULL, TN( 2 ), TN( 8 ), BLACK }, + { 7, TN( 8 ), NULL, NULL, RED }, + { 8, TN( 6 ), TN( 7 ), TN( 9 ), BLACK }, + { 9, TN( 8 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_11[] = { - { 1, TN( 6 ), NULL, NULL, RBT_BLACK }, - { 3, NULL, TN( 2 ), TN( 8 ), RBT_BLACK }, - { 3, TN( 8 ), NULL, NULL, RBT_RED }, - { 4, TN( 6 ), TN( 7 ), TN( 9 ), RBT_BLACK }, - { 4, TN( 8 ), NULL, NULL, RBT_RED } + { 1, TN( 6 ), NULL, NULL, BLACK }, + { 3, NULL, TN( 2 ), TN( 8 ), BLACK }, + { 3, TN( 8 ), NULL, NULL, RED }, + { 4, TN( 6 ), TN( 7 ), TN( 9 ), BLACK }, + { 4, TN( 8 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_12[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 3 ), TN( 0 ), TN( 2 ), RBT_BLACK }, - { 2, TN( 1 ), NULL, NULL, RBT_RED }, - { 3, TN( 5 ), TN( 1 ), TN( 4 ), RBT_RED }, - { 4, TN( 3 ), NULL, NULL, RBT_BLACK }, - { 5, NULL, TN( 3 ), TN( 9 ), RBT_BLACK }, - { 9, TN( 5 ), NULL, TN( 11 ), RBT_BLACK }, - { 11, TN( 9 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 3 ), TN( 0 ), TN( 2 ), BLACK }, + { 2, TN( 1 ), NULL, NULL, RED }, + { 3, TN( 5 ), TN( 1 ), TN( 4 ), RED }, + { 4, TN( 3 ), NULL, NULL, BLACK }, + { 5, NULL, TN( 3 ), TN( 9 ), BLACK }, + { 9, TN( 5 ), NULL, TN( 11 ), BLACK }, + { 11, TN( 9 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_12[] = { - { 0, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 0, TN( 5 ), TN( 0 ), TN( 3 ), RBT_RED }, - { 1, TN( 1 ), NULL, TN( 2 ), RBT_BLACK }, - { 1, TN( 3 ), NULL, NULL, RBT_RED }, - { 2, NULL, TN( 1 ), TN( 9 ), RBT_BLACK }, - { 2, TN( 9 ), NULL, NULL, RBT_BLACK }, - { 4, TN( 5 ), TN( 4 ), TN( 11 ), RBT_RED }, - { 5, TN( 9 ), NULL, NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, BLACK }, + { 0, TN( 5 ), TN( 0 ), TN( 3 ), RED }, + { 1, TN( 1 ), NULL, TN( 2 ), BLACK }, + { 1, TN( 3 ), NULL, NULL, RED }, + { 2, NULL, TN( 1 ), TN( 9 ), BLACK }, + { 2, TN( 9 ), NULL, NULL, BLACK }, + { 4, TN( 5 ), TN( 4 ), TN( 11 ), RED }, + { 5, TN( 9 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_13[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 3 ), TN( 0 ), NULL, RBT_BLACK }, - { 3, NULL, TN( 1 ), TN( 8 ), RBT_BLACK }, - { 4, TN( 5 ), NULL, NULL, RBT_RED }, - { 5, TN( 8 ), TN( 4 ), TN( 6 ), RBT_BLACK }, - { 6, TN( 5 ), NULL, NULL, RBT_RED }, - { 8, TN( 3 ), TN( 5 ), TN( 11 ), RBT_RED }, - { 10, TN( 11 ), NULL, NULL, RBT_RED }, - { 11, TN( 8 ), TN( 10 ), NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 3 ), TN( 0 ), NULL, BLACK }, + { 3, NULL, TN( 1 ), TN( 8 ), BLACK }, + { 4, TN( 5 ), NULL, NULL, RED }, + { 5, TN( 8 ), TN( 4 ), TN( 6 ), BLACK }, + { 6, TN( 5 ), NULL, NULL, RED }, + { 8, TN( 3 ), TN( 5 ), TN( 11 ), RED }, + { 10, TN( 11 ), NULL, NULL, RED }, + { 11, TN( 8 ), TN( 10 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_13[] = { - { 0, TN( 0 ), NULL, NULL, RBT_BLACK }, - { 0, TN( 4 ), TN( 1 ), TN( 3 ), RBT_RED }, - { 1, TN( 0 ), NULL, NULL, RBT_BLACK }, - { 2, NULL, TN( 0 ), TN( 8 ), RBT_BLACK }, - { 2, TN( 6 ), NULL, NULL, RBT_RED }, - { 3, TN( 8 ), TN( 5 ), NULL, RBT_BLACK }, - { 4, TN( 4 ), TN( 6 ), TN( 11 ), RBT_RED }, - { 5, TN( 8 ), NULL, TN( 10 ), RBT_BLACK }, - { 5, TN( 11 ), NULL, NULL, RBT_RED } + { 0, TN( 0 ), NULL, NULL, BLACK }, + { 0, TN( 4 ), TN( 1 ), TN( 3 ), RED }, + { 1, TN( 0 ), NULL, NULL, BLACK }, + { 2, NULL, TN( 0 ), TN( 8 ), BLACK }, + { 2, TN( 6 ), NULL, NULL, RED }, + { 3, TN( 8 ), TN( 5 ), NULL, BLACK }, + { 4, TN( 4 ), TN( 6 ), TN( 11 ), RED }, + { 5, TN( 8 ), NULL, TN( 10 ), BLACK }, + { 5, TN( 11 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_14[] = { - { 3, TN( 6 ), NULL, TN( 5 ), RBT_BLACK }, - { 5, TN( 3 ), NULL, NULL, RBT_RED }, - { 6, NULL, TN( 3 ), TN( 12 ), RBT_BLACK }, - { 8, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 12, TN( 6 ), TN( 8 ), TN( 13 ), RBT_RED }, - { 13, TN( 12 ), NULL, NULL, RBT_BLACK } + { 3, TN( 6 ), NULL, TN( 5 ), BLACK }, + { 5, TN( 3 ), NULL, NULL, RED }, + { 6, NULL, TN( 3 ), TN( 12 ), BLACK }, + { 8, TN( 12 ), NULL, NULL, BLACK }, + { 12, TN( 6 ), TN( 8 ), TN( 13 ), RED }, + { 13, TN( 12 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_14[] = { - { 1, TN( 5 ), NULL, NULL, RBT_RED }, - { 2, TN( 6 ), TN( 3 ), NULL, RBT_BLACK }, - { 3, NULL, TN( 5 ), TN( 13 ), RBT_BLACK }, - { 4, TN( 13 ), NULL, NULL, RBT_BLACK }, - { 6, TN( 6 ), TN( 8 ), TN( 12 ), RBT_RED }, - { 6, TN( 13 ), NULL, NULL, RBT_BLACK } + { 1, TN( 5 ), NULL, NULL, RED }, + { 2, TN( 6 ), TN( 3 ), NULL, BLACK }, + { 3, NULL, TN( 5 ), TN( 13 ), BLACK }, + { 4, TN( 13 ), NULL, NULL, BLACK }, + { 6, TN( 6 ), TN( 8 ), TN( 12 ), RED }, + { 6, TN( 13 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_15[] = { - { 0, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 9 ), TN( 0 ), TN( 8 ), RBT_BLACK }, - { 7, TN( 8 ), NULL, NULL, RBT_RED }, - { 8, TN( 2 ), TN( 7 ), NULL, RBT_BLACK }, - { 9, NULL, TN( 2 ), TN( 12 ), RBT_BLACK }, - { 10, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 12, TN( 9 ), TN( 10 ), TN( 13 ), RBT_BLACK }, - { 13, TN( 12 ), NULL, TN( 14 ), RBT_BLACK }, - { 14, TN( 13 ), NULL, NULL, RBT_RED } + { 0, TN( 2 ), NULL, NULL, BLACK }, + { 2, TN( 9 ), TN( 0 ), TN( 8 ), BLACK }, + { 7, TN( 8 ), NULL, NULL, RED }, + { 8, TN( 2 ), TN( 7 ), NULL, BLACK }, + { 9, NULL, TN( 2 ), TN( 12 ), BLACK }, + { 10, TN( 12 ), NULL, NULL, BLACK }, + { 12, TN( 9 ), TN( 10 ), TN( 13 ), BLACK }, + { 13, TN( 12 ), NULL, TN( 14 ), BLACK }, + { 14, TN( 13 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_15[] = { - { 0, TN( 2 ), NULL, NULL, RBT_RED }, - { 1, TN( 9 ), TN( 0 ), TN( 7 ), RBT_BLACK }, - { 3, TN( 2 ), NULL, NULL, RBT_RED }, - { 4, NULL, TN( 2 ), TN( 13 ), RBT_BLACK }, - { 4, TN( 13 ), NULL, TN( 10 ), RBT_BLACK }, - { 5, TN( 8 ), NULL, NULL, RBT_RED }, - { 6, TN( 9 ), TN( 8 ), TN( 12 ), RBT_RED }, - { 6, TN( 13 ), NULL, TN( 14 ), RBT_BLACK }, - { 7, TN( 12 ), NULL, NULL, RBT_RED } + { 0, TN( 2 ), NULL, NULL, RED }, + { 1, TN( 9 ), TN( 0 ), TN( 7 ), BLACK }, + { 3, TN( 2 ), NULL, NULL, RED }, + { 4, NULL, TN( 2 ), TN( 13 ), BLACK }, + { 4, TN( 13 ), NULL, TN( 10 ), BLACK }, + { 5, TN( 8 ), NULL, NULL, RED }, + { 6, TN( 9 ), TN( 8 ), TN( 12 ), RED }, + { 6, TN( 13 ), NULL, TN( 14 ), BLACK }, + { 7, TN( 12 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_16[] = { - { 0, TN( 5 ), NULL, TN( 3 ), RBT_BLACK }, - { 3, TN( 0 ), NULL, NULL, RBT_RED }, - { 5, NULL, TN( 0 ), TN( 10 ), RBT_BLACK }, - { 7, TN( 10 ), NULL, NULL, RBT_BLACK }, - { 10, TN( 5 ), TN( 7 ), TN( 12 ), RBT_RED }, - { 12, TN( 10 ), NULL, NULL, RBT_BLACK } + { 0, TN( 5 ), NULL, TN( 3 ), BLACK }, + { 3, TN( 0 ), NULL, NULL, RED }, + { 5, NULL, TN( 0 ), TN( 10 ), BLACK }, + { 7, TN( 10 ), NULL, NULL, BLACK }, + { 10, TN( 5 ), TN( 7 ), TN( 12 ), RED }, + { 12, TN( 10 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_16[] = { - { 0, TN( 3 ), NULL, NULL, RBT_RED }, - { 1, TN( 7 ), TN( 0 ), TN( 5 ), RBT_BLACK }, - { 2, TN( 3 ), NULL, NULL, RBT_RED }, - { 3, NULL, TN( 3 ), TN( 12 ), RBT_BLACK }, - { 5, TN( 12 ), NULL, NULL, RBT_RED }, - { 6, TN( 7 ), TN( 10 ), NULL, RBT_BLACK } + { 0, TN( 3 ), NULL, NULL, RED }, + { 1, TN( 7 ), TN( 0 ), TN( 5 ), BLACK }, + { 2, TN( 3 ), NULL, NULL, RED }, + { 3, NULL, TN( 3 ), TN( 12 ), BLACK }, + { 5, TN( 12 ), NULL, NULL, RED }, + { 6, TN( 7 ), TN( 10 ), NULL, BLACK } }; static const test_node_description random_ops_tree_unique_17[] = { - { 0, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 5 ), TN( 0 ), TN( 3 ), RBT_BLACK }, - { 3, TN( 1 ), NULL, TN( 4 ), RBT_BLACK }, - { 4, TN( 3 ), NULL, NULL, RBT_RED }, - { 5, NULL, TN( 1 ), TN( 9 ), RBT_BLACK }, - { 7, TN( 9 ), NULL, TN( 8 ), RBT_BLACK }, - { 8, TN( 7 ), NULL, NULL, RBT_RED }, - { 9, TN( 5 ), TN( 7 ), TN( 16 ), RBT_BLACK }, - { 16, TN( 9 ), NULL, NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, BLACK }, + { 1, TN( 5 ), TN( 0 ), TN( 3 ), BLACK }, + { 3, TN( 1 ), NULL, TN( 4 ), BLACK }, + { 4, TN( 3 ), NULL, NULL, RED }, + { 5, NULL, TN( 1 ), TN( 9 ), BLACK }, + { 7, TN( 9 ), NULL, TN( 8 ), BLACK }, + { 8, TN( 7 ), NULL, NULL, RED }, + { 9, TN( 5 ), TN( 7 ), TN( 16 ), BLACK }, + { 16, TN( 9 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_17[] = { - { 0, TN( 0 ), NULL, NULL, RBT_BLACK }, - { 0, TN( 5 ), TN( 1 ), TN( 3 ), RBT_BLACK }, - { 1, TN( 0 ), NULL, NULL, RBT_BLACK }, - { 2, NULL, TN( 0 ), TN( 9 ), RBT_BLACK }, - { 2, TN( 9 ), NULL, TN( 7 ), RBT_BLACK }, - { 3, TN( 4 ), NULL, NULL, RBT_RED }, - { 4, TN( 5 ), TN( 4 ), TN( 16 ), RBT_BLACK }, - { 4, TN( 16 ), NULL, NULL, RBT_RED }, - { 8, TN( 9 ), TN( 8 ), NULL, RBT_BLACK } + { 0, TN( 0 ), NULL, NULL, BLACK }, + { 0, TN( 5 ), TN( 1 ), TN( 3 ), BLACK }, + { 1, TN( 0 ), NULL, NULL, BLACK }, + { 2, NULL, TN( 0 ), TN( 9 ), BLACK }, + { 2, TN( 9 ), NULL, TN( 7 ), BLACK }, + { 3, TN( 4 ), NULL, NULL, RED }, + { 4, TN( 5 ), TN( 4 ), TN( 16 ), BLACK }, + { 4, TN( 16 ), NULL, NULL, RED }, + { 8, TN( 9 ), TN( 8 ), NULL, BLACK } }; static const test_node_description random_ops_tree_unique_18[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 3 ), TN( 0 ), TN( 2 ), RBT_BLACK }, - { 2, TN( 1 ), NULL, NULL, RBT_RED }, - { 3, TN( 6 ), TN( 1 ), TN( 4 ), RBT_BLACK }, - { 4, TN( 3 ), NULL, TN( 5 ), RBT_BLACK }, - { 5, TN( 4 ), NULL, NULL, RBT_RED }, - { 6, NULL, TN( 3 ), TN( 14 ), RBT_BLACK }, - { 7, TN( 8 ), NULL, NULL, RBT_RED }, - { 8, TN( 10 ), TN( 7 ), TN( 9 ), RBT_BLACK }, - { 9, TN( 8 ), NULL, NULL, RBT_RED }, - { 10, TN( 14 ), TN( 8 ), TN( 12 ), RBT_RED }, - { 12, TN( 10 ), NULL, NULL, RBT_BLACK }, - { 14, TN( 6 ), TN( 10 ), TN( 17 ), RBT_BLACK }, - { 17, TN( 14 ), NULL, NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 3 ), TN( 0 ), TN( 2 ), BLACK }, + { 2, TN( 1 ), NULL, NULL, RED }, + { 3, TN( 6 ), TN( 1 ), TN( 4 ), BLACK }, + { 4, TN( 3 ), NULL, TN( 5 ), BLACK }, + { 5, TN( 4 ), NULL, NULL, RED }, + { 6, NULL, TN( 3 ), TN( 14 ), BLACK }, + { 7, TN( 8 ), NULL, NULL, RED }, + { 8, TN( 10 ), TN( 7 ), TN( 9 ), BLACK }, + { 9, TN( 8 ), NULL, NULL, RED }, + { 10, TN( 14 ), TN( 8 ), TN( 12 ), RED }, + { 12, TN( 10 ), NULL, NULL, BLACK }, + { 14, TN( 6 ), TN( 10 ), TN( 17 ), BLACK }, + { 17, TN( 14 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_18[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 0, TN( 2 ), TN( 0 ), TN( 3 ), RBT_BLACK }, - { 1, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 6 ), TN( 1 ), TN( 4 ), RBT_BLACK }, - { 2, TN( 2 ), NULL, TN( 5 ), RBT_BLACK }, - { 2, TN( 4 ), NULL, NULL, RBT_RED }, - { 3, NULL, TN( 2 ), TN( 12 ), RBT_BLACK }, - { 3, TN( 8 ), NULL, NULL, RBT_RED }, - { 4, TN( 9 ), TN( 7 ), NULL, RBT_BLACK }, - { 4, TN( 12 ), TN( 8 ), TN( 10 ), RBT_RED }, - { 5, TN( 9 ), NULL, NULL, RBT_BLACK }, - { 6, TN( 6 ), TN( 9 ), TN( 14 ), RBT_BLACK }, - { 7, TN( 12 ), NULL, TN( 17 ), RBT_BLACK }, - { 8, TN( 14 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, RED }, + { 0, TN( 2 ), TN( 0 ), TN( 3 ), BLACK }, + { 1, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 6 ), TN( 1 ), TN( 4 ), BLACK }, + { 2, TN( 2 ), NULL, TN( 5 ), BLACK }, + { 2, TN( 4 ), NULL, NULL, RED }, + { 3, NULL, TN( 2 ), TN( 12 ), BLACK }, + { 3, TN( 8 ), NULL, NULL, RED }, + { 4, TN( 9 ), TN( 7 ), NULL, BLACK }, + { 4, TN( 12 ), TN( 8 ), TN( 10 ), RED }, + { 5, TN( 9 ), NULL, NULL, BLACK }, + { 6, TN( 6 ), TN( 9 ), TN( 14 ), BLACK }, + { 7, TN( 12 ), NULL, TN( 17 ), BLACK }, + { 8, TN( 14 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_19[] = { - { 1, TN( 2 ), NULL, NULL, RBT_RED }, - { 2, TN( 6 ), TN( 1 ), NULL, RBT_BLACK }, - { 6, TN( 9 ), TN( 2 ), TN( 8 ), RBT_BLACK }, - { 8, TN( 6 ), NULL, NULL, RBT_BLACK }, - { 9, NULL, TN( 6 ), TN( 12 ), RBT_BLACK }, - { 11, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 12, TN( 9 ), TN( 11 ), TN( 16 ), RBT_BLACK }, - { 14, TN( 16 ), NULL, NULL, RBT_RED }, - { 16, TN( 12 ), TN( 14 ), NULL, RBT_BLACK } + { 1, TN( 2 ), NULL, NULL, RED }, + { 2, TN( 6 ), TN( 1 ), NULL, BLACK }, + { 6, TN( 9 ), TN( 2 ), TN( 8 ), BLACK }, + { 8, TN( 6 ), NULL, NULL, BLACK }, + { 9, NULL, TN( 6 ), TN( 12 ), BLACK }, + { 11, TN( 12 ), NULL, NULL, BLACK }, + { 12, TN( 9 ), TN( 11 ), TN( 16 ), BLACK }, + { 14, TN( 16 ), NULL, NULL, RED }, + { 16, TN( 12 ), TN( 14 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_19[] = { - { 0, TN( 2 ), NULL, NULL, RBT_RED }, - { 1, TN( 6 ), TN( 1 ), NULL, RBT_BLACK }, - { 3, TN( 8 ), TN( 2 ), TN( 9 ), RBT_BLACK }, - { 4, TN( 6 ), NULL, NULL, RBT_BLACK }, - { 4, NULL, TN( 6 ), TN( 12 ), RBT_BLACK }, - { 5, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 6, TN( 8 ), TN( 11 ), TN( 16 ), RBT_BLACK }, - { 7, TN( 16 ), NULL, NULL, RBT_RED }, - { 8, TN( 12 ), TN( 14 ), NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, RED }, + { 1, TN( 6 ), TN( 1 ), NULL, BLACK }, + { 3, TN( 8 ), TN( 2 ), TN( 9 ), BLACK }, + { 4, TN( 6 ), NULL, NULL, BLACK }, + { 4, NULL, TN( 6 ), TN( 12 ), BLACK }, + { 5, TN( 12 ), NULL, NULL, BLACK }, + { 6, TN( 8 ), TN( 11 ), TN( 16 ), BLACK }, + { 7, TN( 16 ), NULL, NULL, RED }, + { 8, TN( 12 ), TN( 14 ), NULL, BLACK } }; static const test_node_description random_ops_tree_unique_20[] = { - { 0, TN( 3 ), NULL, TN( 1 ), RBT_BLACK }, - { 1, TN( 0 ), NULL, NULL, RBT_RED }, - { 3, TN( 9 ), TN( 0 ), TN( 4 ), RBT_RED }, - { 4, TN( 3 ), NULL, TN( 7 ), RBT_BLACK }, - { 7, TN( 4 ), NULL, NULL, RBT_RED }, - { 9, NULL, TN( 3 ), TN( 14 ), RBT_BLACK }, - { 10, TN( 14 ), NULL, TN( 12 ), RBT_BLACK }, - { 12, TN( 10 ), NULL, NULL, RBT_RED }, - { 14, TN( 9 ), TN( 10 ), TN( 18 ), RBT_RED }, - { 17, TN( 18 ), NULL, NULL, RBT_RED }, - { 18, TN( 14 ), TN( 17 ), TN( 19 ), RBT_BLACK }, - { 19, TN( 18 ), NULL, NULL, RBT_RED } + { 0, TN( 3 ), NULL, TN( 1 ), BLACK }, + { 1, TN( 0 ), NULL, NULL, RED }, + { 3, TN( 9 ), TN( 0 ), TN( 4 ), RED }, + { 4, TN( 3 ), NULL, TN( 7 ), BLACK }, + { 7, TN( 4 ), NULL, NULL, RED }, + { 9, NULL, TN( 3 ), TN( 14 ), BLACK }, + { 10, TN( 14 ), NULL, TN( 12 ), BLACK }, + { 12, TN( 10 ), NULL, NULL, RED }, + { 14, TN( 9 ), TN( 10 ), TN( 18 ), RED }, + { 17, TN( 18 ), NULL, NULL, RED }, + { 18, TN( 14 ), TN( 17 ), TN( 19 ), BLACK }, + { 19, TN( 18 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_20[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 0, TN( 4 ), TN( 0 ), TN( 3 ), RBT_BLACK }, - { 1, TN( 1 ), NULL, NULL, RBT_RED }, - { 2, TN( 9 ), TN( 1 ), TN( 7 ), RBT_BLACK }, - { 3, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 4, NULL, TN( 4 ), TN( 12 ), RBT_BLACK }, - { 5, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 6, TN( 9 ), TN( 10 ), TN( 17 ), RBT_BLACK }, - { 7, TN( 17 ), NULL, NULL, RBT_BLACK }, - { 8, TN( 12 ), TN( 14 ), TN( 18 ), RBT_RED }, - { 9, TN( 17 ), NULL, TN( 19 ), RBT_BLACK }, - { 9, TN( 18 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, RED }, + { 0, TN( 4 ), TN( 0 ), TN( 3 ), BLACK }, + { 1, TN( 1 ), NULL, NULL, RED }, + { 2, TN( 9 ), TN( 1 ), TN( 7 ), BLACK }, + { 3, TN( 4 ), NULL, NULL, BLACK }, + { 4, NULL, TN( 4 ), TN( 12 ), BLACK }, + { 5, TN( 12 ), NULL, NULL, BLACK }, + { 6, TN( 9 ), TN( 10 ), TN( 17 ), BLACK }, + { 7, TN( 17 ), NULL, NULL, BLACK }, + { 8, TN( 12 ), TN( 14 ), TN( 18 ), RED }, + { 9, TN( 17 ), NULL, TN( 19 ), BLACK }, + { 9, TN( 18 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_21[] = { - { 0, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 8 ), TN( 0 ), TN( 4 ), RBT_BLACK }, - { 3, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 4, TN( 1 ), TN( 3 ), TN( 5 ), RBT_RED }, - { 5, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 8, NULL, TN( 1 ), TN( 13 ), RBT_BLACK }, - { 11, TN( 13 ), NULL, NULL, RBT_BLACK }, - { 13, TN( 8 ), TN( 11 ), TN( 16 ), RBT_BLACK }, - { 15, TN( 16 ), NULL, NULL, RBT_BLACK }, - { 16, TN( 13 ), TN( 15 ), TN( 17 ), RBT_RED }, - { 17, TN( 16 ), NULL, NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, BLACK }, + { 1, TN( 8 ), TN( 0 ), TN( 4 ), BLACK }, + { 3, TN( 4 ), NULL, NULL, BLACK }, + { 4, TN( 1 ), TN( 3 ), TN( 5 ), RED }, + { 5, TN( 4 ), NULL, NULL, BLACK }, + { 8, NULL, TN( 1 ), TN( 13 ), BLACK }, + { 11, TN( 13 ), NULL, NULL, BLACK }, + { 13, TN( 8 ), TN( 11 ), TN( 16 ), BLACK }, + { 15, TN( 16 ), NULL, NULL, BLACK }, + { 16, TN( 13 ), TN( 15 ), TN( 17 ), RED }, + { 17, TN( 16 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_21[] = { - { 0, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 0, TN( 8 ), TN( 0 ), TN( 4 ), RBT_BLACK }, - { 1, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 1 ), TN( 3 ), TN( 5 ), RBT_RED }, - { 2, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 4, NULL, TN( 1 ), TN( 13 ), RBT_BLACK }, - { 5, TN( 13 ), NULL, NULL, RBT_BLACK }, - { 6, TN( 8 ), TN( 11 ), TN( 17 ), RBT_BLACK }, - { 7, TN( 17 ), NULL, NULL, RBT_BLACK }, - { 8, TN( 13 ), TN( 15 ), TN( 16 ), RBT_RED }, - { 8, TN( 17 ), NULL, NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, BLACK }, + { 0, TN( 8 ), TN( 0 ), TN( 4 ), BLACK }, + { 1, TN( 4 ), NULL, NULL, BLACK }, + { 2, TN( 1 ), TN( 3 ), TN( 5 ), RED }, + { 2, TN( 4 ), NULL, NULL, BLACK }, + { 4, NULL, TN( 1 ), TN( 13 ), BLACK }, + { 5, TN( 13 ), NULL, NULL, BLACK }, + { 6, TN( 8 ), TN( 11 ), TN( 17 ), BLACK }, + { 7, TN( 17 ), NULL, NULL, BLACK }, + { 8, TN( 13 ), TN( 15 ), TN( 16 ), RED }, + { 8, TN( 17 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_22[] = { - { 1, TN( 3 ), NULL, TN( 2 ), RBT_BLACK }, - { 2, TN( 1 ), NULL, NULL, RBT_RED }, - { 3, TN( 8 ), TN( 1 ), TN( 4 ), RBT_BLACK }, - { 4, TN( 3 ), NULL, TN( 7 ), RBT_BLACK }, - { 7, TN( 4 ), NULL, NULL, RBT_RED }, - { 8, NULL, TN( 3 ), TN( 14 ), RBT_BLACK }, - { 10, TN( 11 ), NULL, NULL, RBT_RED }, - { 11, TN( 14 ), TN( 10 ), NULL, RBT_BLACK }, - { 14, TN( 8 ), TN( 11 ), TN( 18 ), RBT_BLACK }, - { 15, TN( 18 ), NULL, NULL, RBT_BLACK }, - { 18, TN( 14 ), TN( 15 ), TN( 21 ), RBT_RED }, - { 21, TN( 18 ), NULL, NULL, RBT_BLACK } + { 1, TN( 3 ), NULL, TN( 2 ), BLACK }, + { 2, TN( 1 ), NULL, NULL, RED }, + { 3, TN( 8 ), TN( 1 ), TN( 4 ), BLACK }, + { 4, TN( 3 ), NULL, TN( 7 ), BLACK }, + { 7, TN( 4 ), NULL, NULL, RED }, + { 8, NULL, TN( 3 ), TN( 14 ), BLACK }, + { 10, TN( 11 ), NULL, NULL, RED }, + { 11, TN( 14 ), TN( 10 ), NULL, BLACK }, + { 14, TN( 8 ), TN( 11 ), TN( 18 ), BLACK }, + { 15, TN( 18 ), NULL, NULL, BLACK }, + { 18, TN( 14 ), TN( 15 ), TN( 21 ), RED }, + { 21, TN( 18 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_22[] = { - { 0, TN( 3 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 8 ), TN( 1 ), TN( 4 ), RBT_BLACK }, - { 1, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 3 ), TN( 2 ), TN( 7 ), RBT_RED }, - { 3, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 4, NULL, TN( 3 ), TN( 14 ), RBT_BLACK }, - { 5, TN( 14 ), NULL, TN( 10 ), RBT_BLACK }, - { 5, TN( 11 ), NULL, NULL, RBT_RED }, - { 7, TN( 8 ), TN( 11 ), TN( 18 ), RBT_BLACK }, - { 7, TN( 18 ), NULL, NULL, RBT_BLACK }, - { 9, TN( 14 ), TN( 15 ), TN( 21 ), RBT_RED }, - { 10, TN( 18 ), NULL, NULL, RBT_BLACK } + { 0, TN( 3 ), NULL, NULL, BLACK }, + { 1, TN( 8 ), TN( 1 ), TN( 4 ), BLACK }, + { 1, TN( 4 ), NULL, NULL, BLACK }, + { 2, TN( 3 ), TN( 2 ), TN( 7 ), RED }, + { 3, TN( 4 ), NULL, NULL, BLACK }, + { 4, NULL, TN( 3 ), TN( 14 ), BLACK }, + { 5, TN( 14 ), NULL, TN( 10 ), BLACK }, + { 5, TN( 11 ), NULL, NULL, RED }, + { 7, TN( 8 ), TN( 11 ), TN( 18 ), BLACK }, + { 7, TN( 18 ), NULL, NULL, BLACK }, + { 9, TN( 14 ), TN( 15 ), TN( 21 ), RED }, + { 10, TN( 18 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_unique_23[] = { - { 0, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 8 ), TN( 0 ), TN( 7 ), RBT_BLACK }, - { 7, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 8, NULL, TN( 2 ), TN( 16 ), RBT_BLACK }, - { 11, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 12, TN( 16 ), TN( 11 ), TN( 14 ), RBT_RED }, - { 13, TN( 14 ), NULL, NULL, RBT_RED }, - { 14, TN( 12 ), TN( 13 ), TN( 15 ), RBT_BLACK }, - { 15, TN( 14 ), NULL, NULL, RBT_RED }, - { 16, TN( 8 ), TN( 12 ), TN( 20 ), RBT_BLACK }, - { 17, TN( 20 ), NULL, NULL, RBT_RED }, - { 20, TN( 16 ), TN( 17 ), TN( 21 ), RBT_BLACK }, - { 21, TN( 20 ), NULL, NULL, RBT_RED } + { 0, TN( 2 ), NULL, NULL, BLACK }, + { 2, TN( 8 ), TN( 0 ), TN( 7 ), BLACK }, + { 7, TN( 2 ), NULL, NULL, BLACK }, + { 8, NULL, TN( 2 ), TN( 16 ), BLACK }, + { 11, TN( 12 ), NULL, NULL, BLACK }, + { 12, TN( 16 ), TN( 11 ), TN( 14 ), RED }, + { 13, TN( 14 ), NULL, NULL, RED }, + { 14, TN( 12 ), TN( 13 ), TN( 15 ), BLACK }, + { 15, TN( 14 ), NULL, NULL, RED }, + { 16, TN( 8 ), TN( 12 ), TN( 20 ), BLACK }, + { 17, TN( 20 ), NULL, NULL, RED }, + { 20, TN( 16 ), TN( 17 ), TN( 21 ), BLACK }, + { 21, TN( 20 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_23[] = { - { 0, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 8 ), TN( 0 ), TN( 7 ), RBT_RED }, - { 3, TN( 2 ), NULL, NULL, RBT_BLACK }, - { 4, TN( 12 ), TN( 2 ), TN( 11 ), RBT_BLACK }, - { 5, TN( 8 ), NULL, NULL, RBT_BLACK }, - { 6, NULL, TN( 8 ), TN( 17 ), RBT_BLACK }, - { 6, TN( 15 ), NULL, NULL, RBT_BLACK }, - { 7, TN( 17 ), TN( 13 ), TN( 16 ), RBT_RED }, - { 7, TN( 16 ), NULL, NULL, RBT_RED }, - { 8, TN( 15 ), TN( 14 ), NULL, RBT_BLACK }, - { 8, TN( 12 ), TN( 15 ), TN( 20 ), RBT_BLACK }, - { 10, TN( 17 ), NULL, TN( 21 ), RBT_BLACK }, - { 10, TN( 20 ), NULL, NULL, RBT_RED } + { 0, TN( 2 ), NULL, NULL, BLACK }, + { 1, TN( 8 ), TN( 0 ), TN( 7 ), RED }, + { 3, TN( 2 ), NULL, NULL, BLACK }, + { 4, TN( 12 ), TN( 2 ), TN( 11 ), BLACK }, + { 5, TN( 8 ), NULL, NULL, BLACK }, + { 6, NULL, TN( 8 ), TN( 17 ), BLACK }, + { 6, TN( 15 ), NULL, NULL, BLACK }, + { 7, TN( 17 ), TN( 13 ), TN( 16 ), RED }, + { 7, TN( 16 ), NULL, NULL, RED }, + { 8, TN( 15 ), TN( 14 ), NULL, BLACK }, + { 8, TN( 12 ), TN( 15 ), TN( 20 ), BLACK }, + { 10, TN( 17 ), NULL, TN( 21 ), BLACK }, + { 10, TN( 20 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_24[] = { - { 4, TN( 5 ), NULL, NULL, RBT_BLACK }, - { 5, TN( 8 ), TN( 4 ), TN( 6 ), RBT_RED }, - { 6, TN( 5 ), NULL, NULL, RBT_BLACK }, - { 8, TN( 14 ), TN( 5 ), TN( 10 ), RBT_BLACK }, - { 10, TN( 8 ), NULL, NULL, RBT_BLACK }, - { 14, NULL, TN( 8 ), TN( 20 ), RBT_BLACK }, - { 15, TN( 16 ), NULL, NULL, RBT_RED }, - { 16, TN( 20 ), TN( 15 ), NULL, RBT_BLACK }, - { 20, TN( 14 ), TN( 16 ), TN( 22 ), RBT_BLACK }, - { 22, TN( 20 ), NULL, NULL, RBT_BLACK } + { 4, TN( 5 ), NULL, NULL, BLACK }, + { 5, TN( 8 ), TN( 4 ), TN( 6 ), RED }, + { 6, TN( 5 ), NULL, NULL, BLACK }, + { 8, TN( 14 ), TN( 5 ), TN( 10 ), BLACK }, + { 10, TN( 8 ), NULL, NULL, BLACK }, + { 14, NULL, TN( 8 ), TN( 20 ), BLACK }, + { 15, TN( 16 ), NULL, NULL, RED }, + { 16, TN( 20 ), TN( 15 ), NULL, BLACK }, + { 20, TN( 14 ), TN( 16 ), TN( 22 ), BLACK }, + { 22, TN( 20 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_24[] = { - { 2, TN( 6 ), NULL, TN( 5 ), RBT_BLACK }, - { 2, TN( 4 ), NULL, NULL, RBT_RED }, - { 3, TN( 10 ), TN( 4 ), TN( 8 ), RBT_BLACK }, - { 4, TN( 6 ), NULL, NULL, RBT_BLACK }, - { 5, NULL, TN( 6 ), TN( 16 ), RBT_BLACK }, - { 7, TN( 16 ), NULL, TN( 15 ), RBT_BLACK }, - { 7, TN( 14 ), NULL, NULL, RBT_RED }, - { 8, TN( 10 ), TN( 14 ), TN( 22 ), RBT_BLACK }, - { 10, TN( 22 ), NULL, NULL, RBT_RED }, - { 11, TN( 16 ), TN( 20 ), NULL, RBT_BLACK } + { 2, TN( 6 ), NULL, TN( 5 ), BLACK }, + { 2, TN( 4 ), NULL, NULL, RED }, + { 3, TN( 10 ), TN( 4 ), TN( 8 ), BLACK }, + { 4, TN( 6 ), NULL, NULL, BLACK }, + { 5, NULL, TN( 6 ), TN( 16 ), BLACK }, + { 7, TN( 16 ), NULL, TN( 15 ), BLACK }, + { 7, TN( 14 ), NULL, NULL, RED }, + { 8, TN( 10 ), TN( 14 ), TN( 22 ), BLACK }, + { 10, TN( 22 ), NULL, NULL, RED }, + { 11, TN( 16 ), TN( 20 ), NULL, BLACK } }; static const test_node_description random_ops_tree_unique_25[] = { - { 0, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 1, TN( 13 ), TN( 0 ), TN( 4 ), RBT_BLACK }, - { 3, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 4, TN( 1 ), TN( 3 ), TN( 6 ), RBT_RED }, - { 5, TN( 6 ), NULL, NULL, RBT_RED }, - { 6, TN( 4 ), TN( 5 ), TN( 9 ), RBT_BLACK }, - { 9, TN( 6 ), NULL, NULL, RBT_RED }, - { 13, NULL, TN( 1 ), TN( 19 ), RBT_BLACK }, - { 14, TN( 15 ), NULL, NULL, RBT_RED }, - { 15, TN( 16 ), TN( 14 ), NULL, RBT_BLACK }, - { 16, TN( 19 ), TN( 15 ), TN( 17 ), RBT_RED }, - { 17, TN( 16 ), NULL, NULL, RBT_BLACK }, - { 19, TN( 13 ), TN( 16 ), TN( 23 ), RBT_BLACK }, - { 23, TN( 19 ), NULL, TN( 24 ), RBT_BLACK }, - { 24, TN( 23 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, BLACK }, + { 1, TN( 13 ), TN( 0 ), TN( 4 ), BLACK }, + { 3, TN( 4 ), NULL, NULL, BLACK }, + { 4, TN( 1 ), TN( 3 ), TN( 6 ), RED }, + { 5, TN( 6 ), NULL, NULL, RED }, + { 6, TN( 4 ), TN( 5 ), TN( 9 ), BLACK }, + { 9, TN( 6 ), NULL, NULL, RED }, + { 13, NULL, TN( 1 ), TN( 19 ), BLACK }, + { 14, TN( 15 ), NULL, NULL, RED }, + { 15, TN( 16 ), TN( 14 ), NULL, BLACK }, + { 16, TN( 19 ), TN( 15 ), TN( 17 ), RED }, + { 17, TN( 16 ), NULL, NULL, BLACK }, + { 19, TN( 13 ), TN( 16 ), TN( 23 ), BLACK }, + { 23, TN( 19 ), NULL, TN( 24 ), BLACK }, + { 24, TN( 23 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_25[] = { - { 0, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 0, TN( 5 ), TN( 0 ), TN( 3 ), RBT_RED }, - { 1, TN( 1 ), NULL, NULL, RBT_BLACK }, - { 2, TN( 13 ), TN( 1 ), TN( 6 ), RBT_BLACK }, - { 2, TN( 6 ), NULL, NULL, RBT_RED }, - { 3, TN( 5 ), TN( 4 ), TN( 9 ), RBT_BLACK }, - { 4, TN( 6 ), NULL, NULL, RBT_RED }, - { 6, NULL, TN( 5 ), TN( 19 ), RBT_BLACK }, - { 7, TN( 17 ), NULL, TN( 14 ), RBT_BLACK }, - { 7, TN( 15 ), NULL, NULL, RBT_RED }, - { 8, TN( 19 ), TN( 15 ), TN( 16 ), RBT_RED }, - { 8, TN( 17 ), NULL, NULL, RBT_BLACK }, - { 9, TN( 13 ), TN( 17 ), TN( 23 ), RBT_BLACK }, - { 11, TN( 19 ), NULL, TN( 24 ), RBT_BLACK }, - { 12, TN( 23 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, BLACK }, + { 0, TN( 5 ), TN( 0 ), TN( 3 ), RED }, + { 1, TN( 1 ), NULL, NULL, BLACK }, + { 2, TN( 13 ), TN( 1 ), TN( 6 ), BLACK }, + { 2, TN( 6 ), NULL, NULL, RED }, + { 3, TN( 5 ), TN( 4 ), TN( 9 ), BLACK }, + { 4, TN( 6 ), NULL, NULL, RED }, + { 6, NULL, TN( 5 ), TN( 19 ), BLACK }, + { 7, TN( 17 ), NULL, TN( 14 ), BLACK }, + { 7, TN( 15 ), NULL, NULL, RED }, + { 8, TN( 19 ), TN( 15 ), TN( 16 ), RED }, + { 8, TN( 17 ), NULL, NULL, BLACK }, + { 9, TN( 13 ), TN( 17 ), TN( 23 ), BLACK }, + { 11, TN( 19 ), NULL, TN( 24 ), BLACK }, + { 12, TN( 23 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_26[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 6 ), TN( 0 ), TN( 3 ), RBT_BLACK }, - { 3, TN( 1 ), NULL, NULL, RBT_RED }, - { 6, TN( 11 ), TN( 1 ), TN( 9 ), RBT_BLACK }, - { 9, TN( 6 ), NULL, TN( 10 ), RBT_BLACK }, - { 10, TN( 9 ), NULL, NULL, RBT_RED }, - { 11, NULL, TN( 6 ), TN( 14 ), RBT_BLACK }, - { 12, TN( 14 ), NULL, TN( 13 ), RBT_BLACK }, - { 13, TN( 12 ), NULL, NULL, RBT_RED }, - { 14, TN( 11 ), TN( 12 ), TN( 20 ), RBT_BLACK }, - { 18, TN( 20 ), NULL, NULL, RBT_BLACK }, - { 20, TN( 14 ), TN( 18 ), TN( 23 ), RBT_RED }, - { 21, TN( 23 ), NULL, NULL, RBT_RED }, - { 23, TN( 20 ), TN( 21 ), NULL, RBT_BLACK } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 6 ), TN( 0 ), TN( 3 ), BLACK }, + { 3, TN( 1 ), NULL, NULL, RED }, + { 6, TN( 11 ), TN( 1 ), TN( 9 ), BLACK }, + { 9, TN( 6 ), NULL, TN( 10 ), BLACK }, + { 10, TN( 9 ), NULL, NULL, RED }, + { 11, NULL, TN( 6 ), TN( 14 ), BLACK }, + { 12, TN( 14 ), NULL, TN( 13 ), BLACK }, + { 13, TN( 12 ), NULL, NULL, RED }, + { 14, TN( 11 ), TN( 12 ), TN( 20 ), BLACK }, + { 18, TN( 20 ), NULL, NULL, BLACK }, + { 20, TN( 14 ), TN( 18 ), TN( 23 ), RED }, + { 21, TN( 23 ), NULL, NULL, RED }, + { 23, TN( 20 ), TN( 21 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_26[] = { - { 0, TN( 0 ), NULL, NULL, RBT_RED }, - { 0, TN( 6 ), TN( 1 ), TN( 3 ), RBT_BLACK }, - { 1, TN( 0 ), NULL, NULL, RBT_RED }, - { 3, TN( 12 ), TN( 0 ), TN( 11 ), RBT_BLACK }, - { 4, TN( 11 ), NULL, NULL, RBT_RED }, - { 5, TN( 6 ), TN( 9 ), TN( 10 ), RBT_BLACK }, - { 5, TN( 11 ), NULL, NULL, RBT_RED }, - { 6, NULL, TN( 6 ), TN( 18 ), RBT_BLACK }, - { 6, TN( 14 ), NULL, NULL, RBT_RED }, - { 7, TN( 18 ), TN( 13 ), NULL, RBT_BLACK }, - { 9, TN( 12 ), TN( 14 ), TN( 21 ), RBT_BLACK }, - { 10, TN( 21 ), NULL, NULL, RBT_RED }, - { 10, TN( 18 ), TN( 20 ), TN( 23 ), RBT_BLACK }, - { 11, TN( 21 ), NULL, NULL, RBT_RED } + { 0, TN( 0 ), NULL, NULL, RED }, + { 0, TN( 6 ), TN( 1 ), TN( 3 ), BLACK }, + { 1, TN( 0 ), NULL, NULL, RED }, + { 3, TN( 12 ), TN( 0 ), TN( 11 ), BLACK }, + { 4, TN( 11 ), NULL, NULL, RED }, + { 5, TN( 6 ), TN( 9 ), TN( 10 ), BLACK }, + { 5, TN( 11 ), NULL, NULL, RED }, + { 6, NULL, TN( 6 ), TN( 18 ), BLACK }, + { 6, TN( 14 ), NULL, NULL, RED }, + { 7, TN( 18 ), TN( 13 ), NULL, BLACK }, + { 9, TN( 12 ), TN( 14 ), TN( 21 ), BLACK }, + { 10, TN( 21 ), NULL, NULL, RED }, + { 10, TN( 18 ), TN( 20 ), TN( 23 ), BLACK }, + { 11, TN( 21 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_27[] = { - { 3, TN( 8 ), NULL, NULL, RBT_BLACK }, - { 8, TN( 19 ), TN( 3 ), TN( 17 ), RBT_RED }, - { 12, TN( 17 ), NULL, NULL, RBT_RED }, - { 17, TN( 8 ), TN( 12 ), NULL, RBT_BLACK }, - { 19, NULL, TN( 8 ), TN( 23 ), RBT_BLACK }, - { 20, TN( 23 ), NULL, TN( 21 ), RBT_BLACK }, - { 21, TN( 20 ), NULL, NULL, RBT_RED }, - { 23, TN( 19 ), TN( 20 ), TN( 25 ), RBT_RED }, - { 24, TN( 25 ), NULL, NULL, RBT_RED }, - { 25, TN( 23 ), TN( 24 ), TN( 26 ), RBT_BLACK }, - { 26, TN( 25 ), NULL, NULL, RBT_RED } + { 3, TN( 8 ), NULL, NULL, BLACK }, + { 8, TN( 19 ), TN( 3 ), TN( 17 ), RED }, + { 12, TN( 17 ), NULL, NULL, RED }, + { 17, TN( 8 ), TN( 12 ), NULL, BLACK }, + { 19, NULL, TN( 8 ), TN( 23 ), BLACK }, + { 20, TN( 23 ), NULL, TN( 21 ), BLACK }, + { 21, TN( 20 ), NULL, NULL, RED }, + { 23, TN( 19 ), TN( 20 ), TN( 25 ), RED }, + { 24, TN( 25 ), NULL, NULL, RED }, + { 25, TN( 23 ), TN( 24 ), TN( 26 ), BLACK }, + { 26, TN( 25 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_27[] = { - { 1, TN( 8 ), NULL, NULL, RBT_BLACK }, - { 4, TN( 19 ), TN( 3 ), TN( 17 ), RBT_RED }, - { 6, TN( 17 ), NULL, NULL, RBT_RED }, - { 8, TN( 8 ), TN( 12 ), NULL, RBT_BLACK }, - { 9, NULL, TN( 8 ), TN( 23 ), RBT_BLACK }, - { 10, TN( 23 ), NULL, TN( 21 ), RBT_BLACK }, - { 10, TN( 20 ), NULL, NULL, RBT_RED }, - { 11, TN( 19 ), TN( 20 ), TN( 24 ), RBT_RED }, - { 12, TN( 24 ), NULL, NULL, RBT_RED }, - { 12, TN( 23 ), TN( 25 ), TN( 26 ), RBT_BLACK }, - { 13, TN( 24 ), NULL, NULL, RBT_RED } + { 1, TN( 8 ), NULL, NULL, BLACK }, + { 4, TN( 19 ), TN( 3 ), TN( 17 ), RED }, + { 6, TN( 17 ), NULL, NULL, RED }, + { 8, TN( 8 ), TN( 12 ), NULL, BLACK }, + { 9, NULL, TN( 8 ), TN( 23 ), BLACK }, + { 10, TN( 23 ), NULL, TN( 21 ), BLACK }, + { 10, TN( 20 ), NULL, NULL, RED }, + { 11, TN( 19 ), TN( 20 ), TN( 24 ), RED }, + { 12, TN( 24 ), NULL, NULL, RED }, + { 12, TN( 23 ), TN( 25 ), TN( 26 ), BLACK }, + { 13, TN( 24 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_28[] = { - { 0, TN( 5 ), NULL, NULL, RBT_BLACK }, - { 5, TN( 13 ), TN( 0 ), TN( 7 ), RBT_RED }, - { 7, TN( 5 ), NULL, NULL, RBT_BLACK }, - { 13, NULL, TN( 5 ), TN( 17 ), RBT_BLACK }, - { 15, TN( 17 ), NULL, NULL, RBT_BLACK }, - { 17, TN( 13 ), TN( 15 ), TN( 26 ), RBT_RED }, - { 21, TN( 26 ), NULL, NULL, RBT_RED }, - { 26, TN( 17 ), TN( 21 ), NULL, RBT_BLACK } + { 0, TN( 5 ), NULL, NULL, BLACK }, + { 5, TN( 13 ), TN( 0 ), TN( 7 ), RED }, + { 7, TN( 5 ), NULL, NULL, BLACK }, + { 13, NULL, TN( 5 ), TN( 17 ), BLACK }, + { 15, TN( 17 ), NULL, NULL, BLACK }, + { 17, TN( 13 ), TN( 15 ), TN( 26 ), RED }, + { 21, TN( 26 ), NULL, NULL, RED }, + { 26, TN( 17 ), TN( 21 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_28[] = { - { 0, TN( 5 ), NULL, NULL, RBT_RED }, - { 2, TN( 7 ), TN( 0 ), NULL, RBT_BLACK }, - { 3, NULL, TN( 5 ), TN( 15 ), RBT_BLACK }, - { 6, TN( 15 ), NULL, NULL, RBT_BLACK }, - { 7, TN( 7 ), TN( 13 ), TN( 21 ), RBT_RED }, - { 8, TN( 21 ), NULL, NULL, RBT_RED }, - { 10, TN( 15 ), TN( 17 ), TN( 26 ), RBT_BLACK }, - { 13, TN( 21 ), NULL, NULL, RBT_RED } + { 0, TN( 5 ), NULL, NULL, RED }, + { 2, TN( 7 ), TN( 0 ), NULL, BLACK }, + { 3, NULL, TN( 5 ), TN( 15 ), BLACK }, + { 6, TN( 15 ), NULL, NULL, BLACK }, + { 7, TN( 7 ), TN( 13 ), TN( 21 ), RED }, + { 8, TN( 21 ), NULL, NULL, RED }, + { 10, TN( 15 ), TN( 17 ), TN( 26 ), BLACK }, + { 13, TN( 21 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_29[] = { - { 0, TN( 1 ), NULL, NULL, RBT_RED }, - { 1, TN( 4 ), TN( 0 ), TN( 3 ), RBT_BLACK }, - { 3, TN( 1 ), NULL, NULL, RBT_RED }, - { 4, TN( 11 ), TN( 1 ), TN( 7 ), RBT_BLACK }, - { 6, TN( 7 ), NULL, NULL, RBT_RED }, - { 7, TN( 4 ), TN( 6 ), TN( 8 ), RBT_BLACK }, - { 8, TN( 7 ), NULL, NULL, RBT_RED }, - { 11, NULL, TN( 4 ), TN( 13 ), RBT_BLACK }, - { 12, TN( 13 ), NULL, NULL, RBT_BLACK }, - { 13, TN( 11 ), TN( 12 ), TN( 22 ), RBT_BLACK }, - { 14, TN( 17 ), NULL, NULL, RBT_RED }, - { 17, TN( 22 ), TN( 14 ), NULL, RBT_BLACK }, - { 22, TN( 13 ), TN( 17 ), TN( 25 ), RBT_RED }, - { 25, TN( 22 ), NULL, TN( 27 ), RBT_BLACK }, - { 27, TN( 25 ), NULL, NULL, RBT_RED } + { 0, TN( 1 ), NULL, NULL, RED }, + { 1, TN( 4 ), TN( 0 ), TN( 3 ), BLACK }, + { 3, TN( 1 ), NULL, NULL, RED }, + { 4, TN( 11 ), TN( 1 ), TN( 7 ), BLACK }, + { 6, TN( 7 ), NULL, NULL, RED }, + { 7, TN( 4 ), TN( 6 ), TN( 8 ), BLACK }, + { 8, TN( 7 ), NULL, NULL, RED }, + { 11, NULL, TN( 4 ), TN( 13 ), BLACK }, + { 12, TN( 13 ), NULL, NULL, BLACK }, + { 13, TN( 11 ), TN( 12 ), TN( 22 ), BLACK }, + { 14, TN( 17 ), NULL, NULL, RED }, + { 17, TN( 22 ), TN( 14 ), NULL, BLACK }, + { 22, TN( 13 ), TN( 17 ), TN( 25 ), RED }, + { 25, TN( 22 ), NULL, TN( 27 ), BLACK }, + { 27, TN( 25 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_multiple_29[] = { - { 0, TN( 3 ), NULL, TN( 1 ), RBT_BLACK }, - { 0, TN( 0 ), NULL, NULL, RBT_RED }, - { 1, TN( 11 ), TN( 0 ), TN( 6 ), RBT_BLACK }, - { 2, TN( 6 ), NULL, NULL, RBT_BLACK }, - { 3, TN( 3 ), TN( 4 ), TN( 7 ), RBT_RED }, - { 3, TN( 6 ), NULL, TN( 8 ), RBT_BLACK }, - { 4, TN( 7 ), NULL, NULL, RBT_RED }, - { 5, NULL, TN( 3 ), TN( 12 ), RBT_BLACK }, - { 6, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 6, TN( 11 ), TN( 13 ), TN( 22 ), RBT_BLACK }, - { 7, TN( 17 ), NULL, NULL, RBT_RED }, - { 8, TN( 22 ), TN( 14 ), NULL, RBT_BLACK }, - { 11, TN( 12 ), TN( 17 ), TN( 25 ), RBT_RED }, - { 12, TN( 22 ), NULL, TN( 27 ), RBT_BLACK }, - { 13, TN( 25 ), NULL, NULL, RBT_RED } + { 0, TN( 3 ), NULL, TN( 1 ), BLACK }, + { 0, TN( 0 ), NULL, NULL, RED }, + { 1, TN( 11 ), TN( 0 ), TN( 6 ), BLACK }, + { 2, TN( 6 ), NULL, NULL, BLACK }, + { 3, TN( 3 ), TN( 4 ), TN( 7 ), RED }, + { 3, TN( 6 ), NULL, TN( 8 ), BLACK }, + { 4, TN( 7 ), NULL, NULL, RED }, + { 5, NULL, TN( 3 ), TN( 12 ), BLACK }, + { 6, TN( 12 ), NULL, NULL, BLACK }, + { 6, TN( 11 ), TN( 13 ), TN( 22 ), BLACK }, + { 7, TN( 17 ), NULL, NULL, RED }, + { 8, TN( 22 ), TN( 14 ), NULL, BLACK }, + { 11, TN( 12 ), TN( 17 ), TN( 25 ), RED }, + { 12, TN( 22 ), NULL, TN( 27 ), BLACK }, + { 13, TN( 25 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_30[] = { - { 0, TN( 4 ), NULL, NULL, RBT_BLACK }, - { 4, TN( 12 ), TN( 0 ), TN( 8 ), RBT_RED }, - { 6, TN( 8 ), NULL, NULL, RBT_RED }, - { 8, TN( 4 ), TN( 6 ), TN( 9 ), RBT_BLACK }, - { 9, TN( 8 ), NULL, NULL, RBT_RED }, - { 12, TN( 14 ), TN( 4 ), TN( 13 ), RBT_BLACK }, - { 13, TN( 12 ), NULL, NULL, RBT_BLACK }, - { 14, NULL, TN( 12 ), TN( 17 ), RBT_BLACK }, - { 16, TN( 17 ), NULL, NULL, RBT_BLACK }, - { 17, TN( 14 ), TN( 16 ), TN( 20 ), RBT_BLACK }, - { 18, TN( 20 ), NULL, NULL, RBT_BLACK }, - { 20, TN( 17 ), TN( 18 ), TN( 28 ), RBT_RED }, - { 27, TN( 28 ), NULL, NULL, RBT_RED }, - { 28, TN( 20 ), TN( 27 ), NULL, RBT_BLACK } + { 0, TN( 4 ), NULL, NULL, BLACK }, + { 4, TN( 12 ), TN( 0 ), TN( 8 ), RED }, + { 6, TN( 8 ), NULL, NULL, RED }, + { 8, TN( 4 ), TN( 6 ), TN( 9 ), BLACK }, + { 9, TN( 8 ), NULL, NULL, RED }, + { 12, TN( 14 ), TN( 4 ), TN( 13 ), BLACK }, + { 13, TN( 12 ), NULL, NULL, BLACK }, + { 14, NULL, TN( 12 ), TN( 17 ), BLACK }, + { 16, TN( 17 ), NULL, NULL, BLACK }, + { 17, TN( 14 ), TN( 16 ), TN( 20 ), BLACK }, + { 18, TN( 20 ), NULL, NULL, BLACK }, + { 20, TN( 17 ), TN( 18 ), TN( 28 ), RED }, + { 27, TN( 28 ), NULL, NULL, RED }, + { 28, TN( 20 ), TN( 27 ), NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_30[] = { - { 0, TN( 4 ), NULL, NULL, RBT_RED }, - { 2, TN( 6 ), TN( 0 ), NULL, RBT_BLACK }, - { 3, TN( 12 ), TN( 4 ), TN( 8 ), RBT_RED }, - { 4, TN( 8 ), NULL, NULL, RBT_RED }, - { 4, TN( 6 ), TN( 9 ), TN( 13 ), RBT_BLACK }, - { 6, TN( 8 ), NULL, NULL, RBT_RED }, - { 6, NULL, TN( 6 ), TN( 18 ), RBT_BLACK }, - { 7, TN( 17 ), NULL, NULL, RBT_RED }, - { 8, TN( 18 ), TN( 14 ), TN( 16 ), RBT_BLACK }, - { 8, TN( 17 ), NULL, NULL, RBT_RED }, - { 9, TN( 12 ), TN( 17 ), TN( 27 ), RBT_RED }, - { 10, TN( 27 ), NULL, NULL, RBT_RED }, - { 13, TN( 18 ), TN( 20 ), TN( 28 ), RBT_BLACK }, - { 14, TN( 27 ), NULL, NULL, RBT_RED } + { 0, TN( 4 ), NULL, NULL, RED }, + { 2, TN( 6 ), TN( 0 ), NULL, BLACK }, + { 3, TN( 12 ), TN( 4 ), TN( 8 ), RED }, + { 4, TN( 8 ), NULL, NULL, RED }, + { 4, TN( 6 ), TN( 9 ), TN( 13 ), BLACK }, + { 6, TN( 8 ), NULL, NULL, RED }, + { 6, NULL, TN( 6 ), TN( 18 ), BLACK }, + { 7, TN( 17 ), NULL, NULL, RED }, + { 8, TN( 18 ), TN( 14 ), TN( 16 ), BLACK }, + { 8, TN( 17 ), NULL, NULL, RED }, + { 9, TN( 12 ), TN( 17 ), TN( 27 ), RED }, + { 10, TN( 27 ), NULL, NULL, RED }, + { 13, TN( 18 ), TN( 20 ), TN( 28 ), BLACK }, + { 14, TN( 27 ), NULL, NULL, RED } }; static const test_node_description random_ops_tree_unique_31[] = { - { 0, TN( 2 ), NULL, NULL, RBT_RED }, - { 2, TN( 5 ), TN( 0 ), NULL, RBT_BLACK }, - { 5, TN( 14 ), TN( 2 ), TN( 9 ), RBT_BLACK }, - { 7, TN( 9 ), NULL, NULL, RBT_RED }, - { 9, TN( 5 ), TN( 7 ), TN( 11 ), RBT_BLACK }, - { 11, TN( 9 ), NULL, NULL, RBT_RED }, - { 14, NULL, TN( 5 ), TN( 21 ), RBT_BLACK }, - { 16, TN( 21 ), NULL, TN( 18 ), RBT_BLACK }, - { 18, TN( 16 ), NULL, NULL, RBT_RED }, - { 21, TN( 14 ), TN( 16 ), TN( 30 ), RBT_BLACK }, - { 30, TN( 21 ), NULL, NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, RED }, + { 2, TN( 5 ), TN( 0 ), NULL, BLACK }, + { 5, TN( 14 ), TN( 2 ), TN( 9 ), BLACK }, + { 7, TN( 9 ), NULL, NULL, RED }, + { 9, TN( 5 ), TN( 7 ), TN( 11 ), BLACK }, + { 11, TN( 9 ), NULL, NULL, RED }, + { 14, NULL, TN( 5 ), TN( 21 ), BLACK }, + { 16, TN( 21 ), NULL, TN( 18 ), BLACK }, + { 18, TN( 16 ), NULL, NULL, RED }, + { 21, TN( 14 ), TN( 16 ), TN( 30 ), BLACK }, + { 30, TN( 21 ), NULL, NULL, BLACK } }; static const test_node_description random_ops_tree_multiple_31[] = { - { 0, TN( 2 ), NULL, NULL, RBT_RED }, - { 1, TN( 5 ), TN( 0 ), NULL, RBT_BLACK }, - { 2, TN( 11 ), TN( 2 ), TN( 9 ), RBT_BLACK }, - { 3, TN( 9 ), NULL, NULL, RBT_RED }, - { 4, TN( 5 ), TN( 7 ), NULL, RBT_BLACK }, - { 5, NULL, TN( 5 ), TN( 21 ), RBT_BLACK }, - { 7, TN( 16 ), NULL, NULL, RBT_RED }, - { 8, TN( 21 ), TN( 14 ), TN( 18 ), RBT_BLACK }, - { 9, TN( 16 ), NULL, NULL, RBT_RED }, - { 10, TN( 11 ), TN( 16 ), TN( 30 ), RBT_BLACK }, - { 15, TN( 21 ), NULL, NULL, RBT_BLACK } + { 0, TN( 2 ), NULL, NULL, RED }, + { 1, TN( 5 ), TN( 0 ), NULL, BLACK }, + { 2, TN( 11 ), TN( 2 ), TN( 9 ), BLACK }, + { 3, TN( 9 ), NULL, NULL, RED }, + { 4, TN( 5 ), TN( 7 ), NULL, BLACK }, + { 5, NULL, TN( 5 ), TN( 21 ), BLACK }, + { 7, TN( 16 ), NULL, NULL, RED }, + { 8, TN( 21 ), TN( 14 ), TN( 18 ), BLACK }, + { 9, TN( 16 ), NULL, NULL, RED }, + { 10, TN( 11 ), TN( 16 ), TN( 30 ), BLACK }, + { 15, TN( 21 ), NULL, NULL, BLACK } }; #define RANDOM_OPS_TREE( i ) \ @@ -1638,7 +1650,7 @@ static void random_ops( size_t n, bool unique ) rtems_rbtree_extract( &tree, &tn->Node ); } - rtems_test_assert( rb_assert( tree.root ) != -1 ); + rtems_test_assert( rb_assert( rtems_rbtree_root( &tree ) ) != -1 ); v = simple_random( v ); } @@ -1694,7 +1706,7 @@ rtems_task Init( rtems_task_argument ignored ) if ( (node1.Node.parent == &node2.Node) != i ) puts( "INIT - FAILED FALSE ROTATION" ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; @@ -1709,7 +1721,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } if (id < 2) { @@ -1737,7 +1749,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } if (id < 1) { @@ -1819,7 +1831,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = i; rb_insert_unique( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1837,7 +1849,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1852,7 +1864,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = 99-i; rb_insert_unique( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1870,7 +1882,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1887,7 +1899,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = i; rb_insert_unique( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1896,7 +1908,7 @@ rtems_task Init( rtems_task_argument ignored ) for (i = 0; i < 20; i++) { id = numbers[i]; rtems_rbtree_extract( &rbtree1, &node_array[id].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1922,7 +1934,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1946,8 +1958,8 @@ rtems_task Init( rtems_task_argument ignored ) rb_insert_unique( &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] ) + if ( !rtems_rbtree_left( &node_array[1].Node ) || + rtems_rbtree_right( &node_array[1].Node ) ) puts( "INIT - LEFT CHILD ONLY NOT FOUND" ); rtems_rbtree_extract( &rbtree1, &node_array[3].Node ); while( (p = rtems_rbtree_get_max(&rbtree1)) ); @@ -1958,7 +1970,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = 99-i; rb_insert_unique( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1976,7 +1988,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -1991,7 +2003,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = i; rb_insert_unique( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2042,7 +2054,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2062,7 +2074,7 @@ rtems_task Init( rtems_task_argument ignored ) _RBTree_Iterate( &rbtree1, RBT_RIGHT, visit_nodes, &ctx ); rtems_test_assert( ctx.current == ctx.count ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2080,7 +2092,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); if ( id < 19 ) { @@ -2120,7 +2132,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2139,7 +2151,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = i%5; rb_insert_multi( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2165,7 +2177,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2180,7 +2192,7 @@ rtems_task Init( rtems_task_argument ignored ) node_array[i].key = (99-i)%5; rb_insert_multi( &rbtree1, &node_array[i].Node ); - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } @@ -2206,7 +2218,7 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if (!rb_assert(rbtree1.root) ) + if (!rb_assert(rtems_rbtree_root(&rbtree1)) ) puts( "INIT - FAILED TREE CHECK" ); } -- cgit v1.2.3