summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSebastian Huber <sebastian.huber@embedded-brains.de>2015-08-21 05:04:27 +0200
committerSebastian Huber <sebastian.huber@embedded-brains.de>2015-08-31 09:56:55 +0200
commitd7c93070cc48c9cd2ccbade4198ae09c33e80a8b (patch)
tree65f93fdc6b7e34a8816d3ea7114ff952f63e0a05
parentsptests/sprbtree01: Fix random ops test case (diff)
downloadrtems-d7c93070cc48c9cd2ccbade4198ae09c33e80a8b.tar.bz2
sptests/sprbtree01: Avoid internal API
-rw-r--r--testsuites/sptests/sprbtree01/init.c1890
1 files 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" );
}