sptests/sprbtree01/init.c

0001 /* SPDX-License-Identifier: BSD-2-Clause */
0002
0003 /*
0004  * Copyright (c) 2010 Gedare Bloom.
0005  *
0006  * Redistribution and use in source and binary forms, with or without
0007  * modification, are permitted provided that the following conditions
0008  * are met:
0009  * 1. Redistributions of source code must retain the above copyright
0010  *    notice, this list of conditions and the following disclaimer.
0011  * 2. Redistributions in binary form must reproduce the above copyright
0012  *    notice, this list of conditions and the following disclaimer in the
0013  *    documentation and/or other materials provided with the distribution.
0014  *
0015  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0016  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0017  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0018  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0019  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0020  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0021  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0022  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0023  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0024  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0025  * POSSIBILITY OF SUCH DAMAGE.
0026  */
0027
0028 #ifdef HAVE_CONFIG_H
0029 #include "config.h"
0030 #endif
0031
0032 #include <tmacros.h>
0033 #include <rtems/rbtree.h>
0034 #include <rtems/score/rbtreeimpl.h>
0035
0036 #include <linux/rbtree.h>
0037
0038 const char rtems_test_name[] = "SPRBTREE 1";
0039
0040 /* forward declarations to avoid warnings */
0041 rtems_task Init(rtems_task_argument argument);
0042
0043 static void test_rbtree_init_one(void)
0044 {
0045   RBTree_Control tree;
0046   RBTree_Node    node;
0047
0048   puts( "INIT - Initialize one" );
0049
0050   _RBTree_Initialize_node( &node );
0051   _RBTree_Initialize_one( &tree, &node );
0052   rtems_test_assert( !_RBTree_Is_empty( &tree ) );
0053   rtems_test_assert( _RBTree_Is_root( &node ) );
0054   rtems_test_assert( !_RBTree_Is_node_off_tree( &node ) );
0055   rtems_test_assert( _RBTree_Left( &node ) == NULL );
0056   rtems_test_assert( _RBTree_Right( &node ) == NULL );
0057   rtems_test_assert( _RBTree_Parent( &node ) == NULL );
0058   rtems_test_assert( _RBTree_Successor( &node ) == NULL );
0059   rtems_test_assert( _RBTree_Predecessor( &node ) == NULL );
0060   rtems_test_assert( _RBTree_Minimum( &tree ) == &node );
0061   rtems_test_assert( _RBTree_Maximum( &tree ) == &node );
0062
0063   _RBTree_Extract( &tree, &node );
0064   rtems_test_assert( _RBTree_Is_empty( &tree ) );
0065 }
0066
0067 static const int numbers[20] = {
0068   52, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71
0069 };
0070
0071 static const int numbers_sorted[20] = {
0072   0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99
0073 };
0074
0075 typedef struct {
0076   int              id;
0077   int              key;
0078   rtems_rbtree_node Node;
0079 } test_node;
0080
0081 static test_node node_array[100];
0082
0083 #define RED RTEMS_RB_RED
0084
0085 #define BLACK RTEMS_RB_BLACK
0086
0087 static int rb_color( const rtems_rbtree_node *n )
0088 {
0089   return RTEMS_RB_COLOR( n, Node );
0090 }
0091
0092 static rtems_rbtree_compare_result test_compare_function (
0093   const rtems_rbtree_node *n1,
0094   const rtems_rbtree_node *n2
0095 )
0096 {
0097   int key1 = RTEMS_CONTAINER_OF( n1, test_node, Node )->key;
0098   int key2 = RTEMS_CONTAINER_OF( n2, test_node, Node )->key;
0099
0100   return key1 - key2;
0101 }
0102
0103 static rtems_rbtree_node *rb_insert_unique(
0104   rtems_rbtree_control *rbtree,
0105   rtems_rbtree_node    *node
0106 )
0107 {
0108   return rtems_rbtree_insert( rbtree, node, test_compare_function, true );
0109 }
0110
0111 static rtems_rbtree_node *rb_insert_multi(
0112   rtems_rbtree_control *rbtree,
0113   rtems_rbtree_node    *node
0114 )
0115 {
0116   return rtems_rbtree_insert( rbtree, node, test_compare_function, false );
0117 }
0118
0119 static rtems_rbtree_node *rb_find_unique(
0120   rtems_rbtree_control *rbtree,
0121   rtems_rbtree_node    *node
0122 )
0123 {
0124   return rtems_rbtree_find( rbtree, node, test_compare_function, true );
0125 }
0126
0127 static rtems_rbtree_node *rb_find_multi(
0128   rtems_rbtree_control *rbtree,
0129   rtems_rbtree_node    *node
0130 )
0131 {
0132   return rtems_rbtree_find( rbtree, node, test_compare_function, false );
0133 }
0134
0135 /*
0136  * recursively checks tree. if the tree is built properly it should only
0137  * be a depth of 7 function calls for 100 entries in the tree.
0138  */
0139 static int rb_assert ( rtems_rbtree_node *root )
0140 {
0141   int lh, rh;
0142
0143   if ( root == NULL )
0144     return 1;
0145   else {
0146     rtems_rbtree_node *ln = rtems_rbtree_left(root);
0147     rtems_rbtree_node *rn = rtems_rbtree_right(root);
0148
0149     /* Consecutive red links */
0150     if ( rb_color( root ) == RED ) {
0151       if (
0152         ( ln && rb_color( ln ) == RED )
0153           || ( rn && rb_color( rn ) == RED )
0154       ) {
0155         puts ( "Red violation" );
0156         return -1;
0157       }
0158     }
0159
0160       lh = rb_assert ( ln );
0161       rh = rb_assert ( rn );
0162
0163     /* Invalid binary search tree */
0164     if ( ( ln != NULL && test_compare_function(ln, root) > 0 )
0165         || ( rn != NULL && test_compare_function(rn, root) < 0 ) )
0166     {
0167       puts ( "Binary tree violation" );
0168       return -1;
0169     }
0170
0171     /* Black height mismatch */
0172     if ( lh != -1 && rh != -1 && lh != rh ) {
0173       puts ( "Black violation" );
0174       return -1;
0175     }
0176
0177     /* Only count black links */
0178     if ( lh != -1 && rh != -1 )
0179       return ( rb_color( root ) == RED ) ? lh : lh + 1;
0180     else
0181       return -1;
0182   }
0183 }
0184
0185 static test_node some_nodes[] = {
0186   { .key = 1 },
0187   { .key = 1 },
0188   { .key = 1 },
0189   { .key = 2 },
0190   { .key = 2 },
0191   { .key = 2 }
0192 };
0193
0194 static void min_max_insert(
0195   rtems_rbtree_control *tree,
0196   rtems_rbtree_node    *node,
0197   rtems_rbtree_node    *min,
0198   rtems_rbtree_node    *max
0199 )
0200 {
0201   rb_insert_multi( tree, node );
0202   rtems_test_assert( rb_assert( rtems_rbtree_root( tree ) ) != -1 );
0203   rtems_test_assert( rtems_rbtree_min( tree ) == min );
0204   rtems_test_assert( rtems_rbtree_max( tree ) == max );
0205 }
0206
0207 static void min_max_extract(
0208   rtems_rbtree_control *tree,
0209   rtems_rbtree_node    *node,
0210   rtems_rbtree_node    *min,
0211   rtems_rbtree_node    *max
0212 )
0213 {
0214   rtems_rbtree_extract( tree, node );
0215   rtems_test_assert( rb_assert( rtems_rbtree_root( tree ) ) != -1 );
0216   rtems_test_assert( rtems_rbtree_min( tree ) == min );
0217   rtems_test_assert( rtems_rbtree_max( tree ) == max );
0218 }
0219
0220 static void test_rbtree_min_max(void)
0221 {
0222   rtems_rbtree_control  tree;
0223   rtems_rbtree_node    *node;
0224   rtems_rbtree_node    *min;
0225   rtems_rbtree_node    *max;
0226
0227   puts( "INIT - Verify min/max node updates" );
0228
0229   rtems_rbtree_initialize_empty( &tree );
0230   rtems_test_assert( rb_assert( rtems_rbtree_root( &tree ) ) == 1 );
0231
0232   node = &some_nodes[ 0 ].Node;
0233   min = node;
0234   max = node;
0235   min_max_insert( &tree, node, min, max );
0236
0237   node = &some_nodes[ 1 ].Node;
0238   max = node;
0239   min_max_insert( &tree, node, min, max );
0240
0241   node = &some_nodes[ 2 ].Node;
0242   max = node;
0243   min_max_insert( &tree, node, min, max );
0244
0245   node = &some_nodes[ 3 ].Node;
0246   max = node;
0247   min_max_insert( &tree, node, min, max );
0248
0249   node = &some_nodes[ 4 ].Node;
0250   max = node;
0251   min_max_insert( &tree, node, min, max );
0252
0253   node = &some_nodes[ 5 ].Node;
0254   max = node;
0255   min_max_insert( &tree, node, min, max );
0256
0257   node = &some_nodes[ 1 ].Node;
0258   min_max_extract( &tree, node, min, max );
0259
0260   node = &some_nodes[ 4 ].Node;
0261   min_max_extract( &tree, node, min, max );
0262
0263   node = &some_nodes[ 0 ].Node;
0264   min = &some_nodes[ 2 ].Node;
0265   min_max_extract( &tree, node, min, max );
0266
0267   node = &some_nodes[ 5 ].Node;
0268   max = &some_nodes[ 3 ].Node;
0269   min_max_extract( &tree, node, min, max );
0270
0271   node = &some_nodes[ 2 ].Node;
0272   min = &some_nodes[ 3 ].Node;
0273   min_max_extract( &tree, node, min, max );
0274
0275   node = &some_nodes[ 3 ].Node;
0276   min = NULL;
0277   max = NULL;
0278   min_max_extract( &tree, node, min, max );
0279   rtems_test_assert( rtems_rbtree_is_empty( &tree ) );
0280 }
0281
0282 static bool test_less(
0283   const void        *left,
0284   const RBTree_Node *right
0285 )
0286 {
0287   const int       *the_left;
0288   const test_node *the_right;
0289
0290   the_left = left;
0291   the_right = RTEMS_CONTAINER_OF( right, test_node, Node );
0292
0293   return *the_left < the_right->key;
0294 }
0295
0296 static void test_rbtree_insert_inline( void )
0297 {
0298   RBTree_Control tree;
0299   test_node      a;
0300   test_node      b;
0301   test_node      c;
0302   int            key;
0303   bool           is_new_minimum;
0304
0305   puts( "INIT - Verify _RBTree_Insert_inline" );
0306
0307   a.key = 1;
0308   b.key = 2;
0309   c.key = 3;
0310
0311   _RBTree_Initialize_empty( &tree );
0312   _RBTree_Initialize_node( &a.Node );
0313   _RBTree_Initialize_node( &b.Node );
0314   _RBTree_Initialize_node( &c.Node );
0315
0316   key = b.key;
0317   is_new_minimum = _RBTree_Insert_inline(
0318     &tree,
0319     &b.Node,
0320     &key,
0321     test_less
0322   );
0323   rtems_test_assert( is_new_minimum );
0324
0325   key = c.key;
0326   is_new_minimum = _RBTree_Insert_inline(
0327     &tree,
0328     &c.Node,
0329     &key,
0330     test_less
0331   );
0332   rtems_test_assert( !is_new_minimum );
0333
0334   key = a.key;
0335   is_new_minimum = _RBTree_Insert_inline(
0336     &tree,
0337     &a.Node,
0338     &key,
0339     test_less
0340   );
0341   rtems_test_assert( is_new_minimum );
0342 }
0343
0344 #define TN( i ) &node_array[ i ].Node
0345
0346 typedef struct {
0347   int key;
0348   const rtems_rbtree_node *parent;
0349   const rtems_rbtree_node *left;
0350   const rtems_rbtree_node *right;
0351   int color;
0352 } test_node_description;
0353
0354 static const test_node_description test_insert_tree_0[] = {
0355   { 52, NULL, NULL, NULL , BLACK }
0356 };
0357
0358 static const test_node_description test_insert_tree_1[] = {
0359   { 52, NULL, NULL, TN( 1 ) , BLACK },
0360   { 99, TN( 0 ), NULL, NULL , RED }
0361 };
0362
0363 static const test_node_description test_insert_tree_2[] = {
0364   { 0, TN( 0 ), NULL, NULL , RED },
0365   { 52, NULL, TN( 2 ), TN( 1 ) , BLACK },
0366   { 99, TN( 0 ), NULL, NULL , RED }
0367 };
0368
0369 static const test_node_description test_insert_tree_3[] = {
0370   { 0, TN( 0 ), NULL, NULL , BLACK },
0371   { 52, NULL, TN( 2 ), TN( 1 ) , BLACK },
0372   { 85, TN( 1 ), NULL, NULL , RED },
0373   { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
0374 };
0375
0376 static const test_node_description test_insert_tree_4[] = {
0377   { 0, TN( 0 ), NULL, TN( 4 ) , BLACK },
0378   { 43, TN( 2 ), NULL, NULL , RED },
0379   { 52, NULL, TN( 2 ), TN( 1 ) , BLACK },
0380   { 85, TN( 1 ), NULL, NULL , RED },
0381   { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
0382 };
0383
0384 static const test_node_description test_insert_tree_5[] = {
0385   { 0, TN( 4 ), NULL, NULL , RED },
0386   { 43, TN( 0 ), TN( 2 ), TN( 5 ) , BLACK },
0387   { 44, TN( 4 ), NULL, NULL , RED },
0388   { 52, NULL, TN( 4 ), TN( 1 ) , BLACK },
0389   { 85, TN( 1 ), NULL, NULL , RED },
0390   { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
0391 };
0392
0393 static const test_node_description test_insert_tree_6[] = {
0394   { 0, TN( 4 ), NULL, TN( 6 ) , BLACK },
0395   { 10, TN( 2 ), NULL, NULL , RED },
0396   { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED },
0397   { 44, TN( 4 ), NULL, NULL , BLACK },
0398   { 52, NULL, TN( 4 ), TN( 1 ) , BLACK },
0399   { 85, TN( 1 ), NULL, NULL , RED },
0400   { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
0401 };
0402
0403 static const test_node_description test_insert_tree_7[] = {
0404   { 0, TN( 4 ), NULL, TN( 6 ) , BLACK },
0405   { 10, TN( 2 ), NULL, NULL , RED },
0406   { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED },
0407   { 44, TN( 4 ), NULL, NULL , BLACK },
0408   { 52, NULL, TN( 4 ), TN( 3 ) , BLACK },
0409   { 60, TN( 3 ), NULL, NULL , RED },
0410   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
0411   { 99, TN( 3 ), NULL, NULL , RED }
0412 };
0413
0414 static const test_node_description test_insert_tree_8[] = {
0415   { 0, TN( 4 ), NULL, TN( 6 ) , BLACK },
0416   { 10, TN( 2 ), NULL, NULL , RED },
0417   { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED },
0418   { 44, TN( 4 ), NULL, TN( 8 ) , BLACK },
0419   { 50, TN( 5 ), NULL, NULL , RED },
0420   { 52, NULL, TN( 4 ), TN( 3 ) , BLACK },
0421   { 60, TN( 3 ), NULL, NULL , RED },
0422   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
0423   { 99, TN( 3 ), NULL, NULL , RED }
0424 };
0425
0426 static const test_node_description test_insert_tree_9[] = {
0427   { 0, TN( 6 ), NULL, NULL , RED },
0428   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0429   { 19, TN( 6 ), NULL, NULL , RED },
0430   { 43, TN( 0 ), TN( 6 ), TN( 5 ) , RED },
0431   { 44, TN( 4 ), NULL, TN( 8 ) , BLACK },
0432   { 50, TN( 5 ), NULL, NULL , RED },
0433   { 52, NULL, TN( 4 ), TN( 3 ) , BLACK },
0434   { 60, TN( 3 ), NULL, NULL , RED },
0435   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
0436   { 99, TN( 3 ), NULL, NULL , RED }
0437 };
0438
0439 static const test_node_description test_insert_tree_10[] = {
0440   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0441   { 8, TN( 2 ), NULL, NULL , RED },
0442   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RED },
0443   { 19, TN( 6 ), NULL, NULL , BLACK },
0444   { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
0445   { 44, TN( 0 ), NULL, TN( 8 ) , BLACK },
0446   { 50, TN( 5 ), NULL, NULL , RED },
0447   { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RED },
0448   { 60, TN( 3 ), NULL, NULL , RED },
0449   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
0450   { 99, TN( 3 ), NULL, NULL , RED }
0451 };
0452
0453 static const test_node_description test_insert_tree_11[] = {
0454   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0455   { 8, TN( 2 ), NULL, NULL , RED },
0456   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0457   { 19, TN( 6 ), NULL, NULL , BLACK },
0458   { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
0459   { 44, TN( 0 ), NULL, TN( 8 ) , BLACK },
0460   { 50, TN( 5 ), NULL, NULL , RED },
0461   { 52, TN( 4 ), TN( 5 ), TN( 3 ) , BLACK },
0462   { 60, TN( 3 ), NULL, TN( 11 ) , BLACK },
0463   { 68, TN( 7 ), NULL, NULL , RED },
0464   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
0465   { 99, TN( 3 ), NULL, NULL , BLACK }
0466 };
0467
0468 static const test_node_description test_insert_tree_12[] = {
0469   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0470   { 8, TN( 2 ), NULL, NULL , RED },
0471   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0472   { 19, TN( 6 ), NULL, NULL , BLACK },
0473   { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
0474   { 44, TN( 12 ), NULL, NULL , RED },
0475   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0476   { 50, TN( 12 ), NULL, NULL , RED },
0477   { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK },
0478   { 60, TN( 3 ), NULL, TN( 11 ) , BLACK },
0479   { 68, TN( 7 ), NULL, NULL , RED },
0480   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
0481   { 99, TN( 3 ), NULL, NULL , BLACK }
0482 };
0483
0484 static const test_node_description test_insert_tree_13[] = {
0485   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0486   { 8, TN( 2 ), NULL, NULL , RED },
0487   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0488   { 19, TN( 6 ), NULL, NULL , BLACK },
0489   { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
0490   { 44, TN( 12 ), NULL, NULL , RED },
0491   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0492   { 50, TN( 12 ), NULL, NULL , RED },
0493   { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK },
0494   { 57, TN( 7 ), NULL, NULL , RED },
0495   { 60, TN( 3 ), TN( 13 ), TN( 11 ) , BLACK },
0496   { 68, TN( 7 ), NULL, NULL , RED },
0497   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
0498   { 99, TN( 3 ), NULL, NULL , BLACK }
0499 };
0500
0501 static const test_node_description test_insert_tree_14[] = {
0502   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0503   { 8, TN( 2 ), NULL, NULL , RED },
0504   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0505   { 17, TN( 9 ), NULL, NULL , RED },
0506   { 19, TN( 6 ), TN( 14 ), NULL , BLACK },
0507   { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
0508   { 44, TN( 12 ), NULL, NULL , RED },
0509   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0510   { 50, TN( 12 ), NULL, NULL , RED },
0511   { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK },
0512   { 57, TN( 7 ), NULL, NULL , RED },
0513   { 60, TN( 3 ), TN( 13 ), TN( 11 ) , BLACK },
0514   { 68, TN( 7 ), NULL, NULL , RED },
0515   { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
0516   { 99, TN( 3 ), NULL, NULL , BLACK }
0517 };
0518
0519 static const test_node_description test_insert_tree_15[] = {
0520   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0521   { 8, TN( 2 ), NULL, NULL , RED },
0522   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0523   { 17, TN( 9 ), NULL, NULL , RED },
0524   { 19, TN( 6 ), TN( 14 ), NULL , BLACK },
0525   { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
0526   { 44, TN( 12 ), NULL, NULL , RED },
0527   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0528   { 50, TN( 12 ), NULL, NULL , RED },
0529   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
0530   { 57, TN( 0 ), NULL, NULL , BLACK },
0531   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
0532   { 67, TN( 11 ), NULL, NULL , RED },
0533   { 68, TN( 3 ), TN( 15 ), NULL , BLACK },
0534   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
0535   { 99, TN( 3 ), NULL, NULL , BLACK }
0536 };
0537
0538 static const test_node_description test_insert_tree_16[] = {
0539   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0540   { 8, TN( 2 ), NULL, NULL , RED },
0541   { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
0542   { 17, TN( 9 ), NULL, NULL , RED },
0543   { 19, TN( 6 ), TN( 14 ), NULL , BLACK },
0544   { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
0545   { 44, TN( 12 ), NULL, NULL , RED },
0546   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0547   { 50, TN( 12 ), NULL, NULL , RED },
0548   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
0549   { 57, TN( 0 ), NULL, NULL , BLACK },
0550   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
0551   { 67, TN( 11 ), NULL, NULL , RED },
0552   { 68, TN( 3 ), TN( 15 ), NULL , BLACK },
0553   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
0554   { 90, TN( 1 ), NULL, NULL , RED },
0555   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0556 };
0557
0558 static const test_node_description test_insert_tree_17[] = {
0559   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0560   { 8, TN( 2 ), NULL, NULL , RED },
0561   { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK },
0562   { 12, TN( 14 ), NULL, NULL , RED },
0563   { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
0564   { 19, TN( 14 ), NULL, NULL , RED },
0565   { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
0566   { 44, TN( 12 ), NULL, NULL , RED },
0567   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0568   { 50, TN( 12 ), NULL, NULL , RED },
0569   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
0570   { 57, TN( 0 ), NULL, NULL , BLACK },
0571   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
0572   { 67, TN( 11 ), NULL, NULL , RED },
0573   { 68, TN( 3 ), TN( 15 ), NULL , BLACK },
0574   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
0575   { 90, TN( 1 ), NULL, NULL , RED },
0576   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0577 };
0578
0579 static const test_node_description test_insert_tree_18[] = {
0580   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0581   { 8, TN( 2 ), NULL, NULL , RED },
0582   { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK },
0583   { 12, TN( 14 ), NULL, NULL , RED },
0584   { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
0585   { 19, TN( 14 ), NULL, NULL , RED },
0586   { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
0587   { 44, TN( 12 ), NULL, NULL , RED },
0588   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0589   { 50, TN( 12 ), NULL, NULL , RED },
0590   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
0591   { 57, TN( 0 ), NULL, NULL , BLACK },
0592   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
0593   { 67, TN( 11 ), NULL, NULL , RED },
0594   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , BLACK },
0595   { 77, TN( 11 ), NULL, NULL , RED },
0596   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
0597   { 90, TN( 1 ), NULL, NULL , RED },
0598   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0599 };
0600
0601 static const test_node_description test_insert_tree_19[] = {
0602   { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
0603   { 8, TN( 2 ), NULL, NULL , RED },
0604   { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK },
0605   { 12, TN( 14 ), NULL, NULL , RED },
0606   { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
0607   { 19, TN( 14 ), NULL, NULL , RED },
0608   { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
0609   { 44, TN( 12 ), NULL, NULL , RED },
0610   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0611   { 50, TN( 12 ), NULL, NULL , RED },
0612   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0613   { 57, TN( 0 ), NULL, NULL , BLACK },
0614   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
0615   { 67, TN( 11 ), NULL, NULL , BLACK },
0616   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0617   { 71, TN( 18 ), NULL, NULL , RED },
0618   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0619   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0620   { 90, TN( 1 ), NULL, NULL , RED },
0621   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0622 };
0623
0624 static const test_node_description *const test_insert_trees[] = {
0625   &test_insert_tree_0[ 0 ],
0626   &test_insert_tree_1[ 0 ],
0627   &test_insert_tree_2[ 0 ],
0628   &test_insert_tree_3[ 0 ],
0629   &test_insert_tree_4[ 0 ],
0630   &test_insert_tree_5[ 0 ],
0631   &test_insert_tree_6[ 0 ],
0632   &test_insert_tree_7[ 0 ],
0633   &test_insert_tree_8[ 0 ],
0634   &test_insert_tree_9[ 0 ],
0635   &test_insert_tree_10[ 0 ],
0636   &test_insert_tree_11[ 0 ],
0637   &test_insert_tree_12[ 0 ],
0638   &test_insert_tree_13[ 0 ],
0639   &test_insert_tree_14[ 0 ],
0640   &test_insert_tree_15[ 0 ],
0641   &test_insert_tree_16[ 0 ],
0642   &test_insert_tree_17[ 0 ],
0643   &test_insert_tree_18[ 0 ],
0644   &test_insert_tree_19[ 0 ]
0645 };
0646
0647 static const test_node_description test_remove_tree_0[] = {
0648   { 8, TN( 6 ), NULL, NULL , BLACK },
0649   { 10, TN( 4 ), TN( 10 ), TN( 14 ) , BLACK },
0650   { 12, TN( 14 ), NULL, NULL , RED },
0651   { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
0652   { 19, TN( 14 ), NULL, NULL , RED },
0653   { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
0654   { 44, TN( 12 ), NULL, NULL , RED },
0655   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0656   { 50, TN( 12 ), NULL, NULL , RED },
0657   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0658   { 57, TN( 0 ), NULL, NULL , BLACK },
0659   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
0660   { 67, TN( 11 ), NULL, NULL , BLACK },
0661   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0662   { 71, TN( 18 ), NULL, NULL , RED },
0663   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0664   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0665   { 90, TN( 1 ), NULL, NULL , RED },
0666   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0667 };
0668
0669 static const test_node_description test_remove_tree_1[] = {
0670   { 10, TN( 14 ), NULL, TN( 17 ) , BLACK },
0671   { 12, TN( 6 ), NULL, NULL , RED },
0672   { 17, TN( 4 ), TN( 6 ), TN( 9 ) , BLACK },
0673   { 19, TN( 14 ), NULL, NULL , BLACK },
0674   { 43, NULL, TN( 14 ), TN( 7 ) , BLACK },
0675   { 44, TN( 12 ), NULL, NULL , RED },
0676   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0677   { 50, TN( 12 ), NULL, NULL , RED },
0678   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0679   { 57, TN( 0 ), NULL, NULL , BLACK },
0680   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
0681   { 67, TN( 11 ), NULL, NULL , BLACK },
0682   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0683   { 71, TN( 18 ), NULL, NULL , RED },
0684   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0685   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0686   { 90, TN( 1 ), NULL, NULL , RED },
0687   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0688 };
0689
0690 static const test_node_description test_remove_tree_2[] = {
0691   { 12, TN( 14 ), NULL, NULL , BLACK },
0692   { 17, TN( 4 ), TN( 17 ), TN( 9 ) , BLACK },
0693   { 19, TN( 14 ), NULL, NULL , BLACK },
0694   { 43, NULL, TN( 14 ), TN( 7 ) , BLACK },
0695   { 44, TN( 12 ), NULL, NULL , RED },
0696   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0697   { 50, TN( 12 ), NULL, NULL , RED },
0698   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0699   { 57, TN( 0 ), NULL, NULL , BLACK },
0700   { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
0701   { 67, TN( 11 ), NULL, NULL , BLACK },
0702   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0703   { 71, TN( 18 ), NULL, NULL , RED },
0704   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0705   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0706   { 90, TN( 1 ), NULL, NULL , RED },
0707   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0708 };
0709
0710 static const test_node_description test_remove_tree_3[] = {
0711   { 17, TN( 4 ), NULL, TN( 9 ) , BLACK },
0712   { 19, TN( 14 ), NULL, NULL , RED },
0713   { 43, TN( 7 ), TN( 14 ), TN( 0 ) , BLACK },
0714   { 44, TN( 12 ), NULL, NULL , RED },
0715   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0716   { 50, TN( 12 ), NULL, NULL , RED },
0717   { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RED },
0718   { 57, TN( 0 ), NULL, NULL , BLACK },
0719   { 60, NULL, TN( 4 ), TN( 3 ) , BLACK },
0720   { 67, TN( 11 ), NULL, NULL , BLACK },
0721   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0722   { 71, TN( 18 ), NULL, NULL , RED },
0723   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0724   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0725   { 90, TN( 1 ), NULL, NULL , RED },
0726   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0727 };
0728
0729 static const test_node_description test_remove_tree_4[] = {
0730   { 19, TN( 4 ), NULL, NULL , BLACK },
0731   { 43, TN( 7 ), TN( 9 ), TN( 0 ) , BLACK },
0732   { 44, TN( 12 ), NULL, NULL , RED },
0733   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
0734   { 50, TN( 12 ), NULL, NULL , RED },
0735   { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RED },
0736   { 57, TN( 0 ), NULL, NULL , BLACK },
0737   { 60, NULL, TN( 4 ), TN( 3 ) , BLACK },
0738   { 67, TN( 11 ), NULL, NULL , BLACK },
0739   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0740   { 71, TN( 18 ), NULL, NULL , RED },
0741   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0742   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0743   { 90, TN( 1 ), NULL, NULL , RED },
0744   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0745 };
0746
0747 static const test_node_description test_remove_tree_5[] = {
0748   { 43, TN( 12 ), NULL, TN( 5 ) , BLACK },
0749   { 44, TN( 4 ), NULL, NULL , RED },
0750   { 48, TN( 0 ), TN( 4 ), TN( 8 ) , RED },
0751   { 50, TN( 12 ), NULL, NULL , BLACK },
0752   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0753   { 57, TN( 0 ), NULL, NULL , BLACK },
0754   { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
0755   { 67, TN( 11 ), NULL, NULL , BLACK },
0756   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0757   { 71, TN( 18 ), NULL, NULL , RED },
0758   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0759   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0760   { 90, TN( 1 ), NULL, NULL , RED },
0761   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0762 };
0763
0764 static const test_node_description test_remove_tree_6[] = {
0765   { 44, TN( 12 ), NULL, NULL , BLACK },
0766   { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RED },
0767   { 50, TN( 12 ), NULL, NULL , BLACK },
0768   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0769   { 57, TN( 0 ), NULL, NULL , BLACK },
0770   { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
0771   { 67, TN( 11 ), NULL, NULL , BLACK },
0772   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0773   { 71, TN( 18 ), NULL, NULL , RED },
0774   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0775   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0776   { 90, TN( 1 ), NULL, NULL , RED },
0777   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0778 };
0779
0780 static const test_node_description test_remove_tree_7[] = {
0781   { 48, TN( 0 ), NULL, TN( 8 ) , BLACK },
0782   { 50, TN( 12 ), NULL, NULL , RED },
0783   { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
0784   { 57, TN( 0 ), NULL, NULL , BLACK },
0785   { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
0786   { 67, TN( 11 ), NULL, NULL , BLACK },
0787   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0788   { 71, TN( 18 ), NULL, NULL , RED },
0789   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0790   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0791   { 90, TN( 1 ), NULL, NULL , RED },
0792   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0793 };
0794
0795 static const test_node_description test_remove_tree_8[] = {
0796   { 50, TN( 0 ), NULL, NULL , BLACK },
0797   { 52, TN( 7 ), TN( 8 ), TN( 13 ) , BLACK },
0798   { 57, TN( 0 ), NULL, NULL , BLACK },
0799   { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
0800   { 67, TN( 11 ), NULL, NULL , BLACK },
0801   { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
0802   { 71, TN( 18 ), NULL, NULL , RED },
0803   { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
0804   { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
0805   { 90, TN( 1 ), NULL, NULL , RED },
0806   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0807 };
0808
0809 static const test_node_description test_remove_tree_9[] = {
0810   { 52, TN( 7 ), NULL, TN( 13 ) , BLACK },
0811   { 57, TN( 0 ), NULL, NULL , RED },
0812   { 60, TN( 11 ), TN( 0 ), TN( 15 ) , BLACK },
0813   { 67, TN( 7 ), NULL, NULL , BLACK },
0814   { 68, NULL, TN( 7 ), TN( 3 ) , BLACK },
0815   { 71, TN( 18 ), NULL, NULL , RED },
0816   { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
0817   { 85, TN( 11 ), TN( 18 ), TN( 1 ) , BLACK },
0818   { 90, TN( 1 ), NULL, NULL , RED },
0819   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0820 };
0821
0822 static const test_node_description test_remove_tree_10[] = {
0823   { 57, TN( 7 ), NULL, NULL , BLACK },
0824   { 60, TN( 11 ), TN( 13 ), TN( 15 ) , BLACK },
0825   { 67, TN( 7 ), NULL, NULL , BLACK },
0826   { 68, NULL, TN( 7 ), TN( 3 ) , BLACK },
0827   { 71, TN( 18 ), NULL, NULL , RED },
0828   { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
0829   { 85, TN( 11 ), TN( 18 ), TN( 1 ) , BLACK },
0830   { 90, TN( 1 ), NULL, NULL , RED },
0831   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0832 };
0833
0834 static const test_node_description test_remove_tree_11[] = {
0835   { 60, TN( 11 ), NULL, TN( 15 ) , BLACK },
0836   { 67, TN( 7 ), NULL, NULL , RED },
0837   { 68, NULL, TN( 7 ), TN( 3 ) , BLACK },
0838   { 71, TN( 18 ), NULL, NULL , RED },
0839   { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
0840   { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RED },
0841   { 90, TN( 1 ), NULL, NULL , RED },
0842   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0843 };
0844
0845 static const test_node_description test_remove_tree_12[] = {
0846   { 67, TN( 11 ), NULL, NULL , BLACK },
0847   { 68, NULL, TN( 15 ), TN( 3 ) , BLACK },
0848   { 71, TN( 18 ), NULL, NULL , RED },
0849   { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
0850   { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RED },
0851   { 90, TN( 1 ), NULL, NULL , RED },
0852   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0853 };
0854
0855 static const test_node_description test_remove_tree_13[] = {
0856   { 68, TN( 19 ), NULL, NULL , BLACK },
0857   { 71, TN( 3 ), TN( 11 ), TN( 18 ) , RED },
0858   { 77, TN( 19 ), NULL, NULL , BLACK },
0859   { 85, NULL, TN( 19 ), TN( 1 ) , BLACK },
0860   { 90, TN( 1 ), NULL, NULL , RED },
0861   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0862 };
0863
0864 static const test_node_description test_remove_tree_14[] = {
0865   { 71, TN( 3 ), NULL, TN( 18 ) , BLACK },
0866   { 77, TN( 19 ), NULL, NULL , RED },
0867   { 85, NULL, TN( 19 ), TN( 1 ) , BLACK },
0868   { 90, TN( 1 ), NULL, NULL , RED },
0869   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0870 };
0871
0872 static const test_node_description test_remove_tree_15[] = {
0873   { 77, TN( 3 ), NULL, NULL , BLACK },
0874   { 85, NULL, TN( 18 ), TN( 1 ) , BLACK },
0875   { 90, TN( 1 ), NULL, NULL , RED },
0876   { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
0877 };
0878
0879 static const test_node_description test_remove_tree_16[] = {
0880   { 85, TN( 16 ), NULL, NULL , BLACK },
0881   { 90, NULL, TN( 3 ), TN( 1 ) , BLACK },
0882   { 99, TN( 16 ), NULL, NULL , BLACK }
0883 };
0884
0885 static const test_node_description test_remove_tree_17[] = {
0886   { 90, NULL, NULL, TN( 1 ) , BLACK },
0887   { 99, TN( 16 ), NULL, NULL , RED }
0888 };
0889
0890 static const test_node_description test_remove_tree_18[] = {
0891   { 99, NULL, NULL, NULL , BLACK }
0892 };
0893
0894 static const test_node_description *const test_remove_trees[] = {
0895   &test_remove_tree_0[ 0 ],
0896   &test_remove_tree_1[ 0 ],
0897   &test_remove_tree_2[ 0 ],
0898   &test_remove_tree_3[ 0 ],
0899   &test_remove_tree_4[ 0 ],
0900   &test_remove_tree_5[ 0 ],
0901   &test_remove_tree_6[ 0 ],
0902   &test_remove_tree_7[ 0 ],
0903   &test_remove_tree_8[ 0 ],
0904   &test_remove_tree_9[ 0 ],
0905   &test_remove_tree_10[ 0 ],
0906   &test_remove_tree_11[ 0 ],
0907   &test_remove_tree_12[ 0 ],
0908   &test_remove_tree_13[ 0 ],
0909   &test_remove_tree_14[ 0 ],
0910   &test_remove_tree_15[ 0 ],
0911   &test_remove_tree_16[ 0 ],
0912   &test_remove_tree_17[ 0 ],
0913   &test_remove_tree_18[ 0 ]
0914 };
0915
0916 typedef struct {
0917   int current;
0918   int count;
0919   const test_node_description *tree;
0920 } visitor_context;
0921
0922 static bool visit_nodes(
0923   const RBTree_Node *node,
0924   void              *visitor_arg
0925 )
0926 {
0927   visitor_context *ctx = visitor_arg;
0928   const test_node_description *td = &ctx->tree[ ctx->current ];
0929   const test_node *tn = RTEMS_CONTAINER_OF( node, test_node, Node );
0930
0931   rtems_test_assert( ctx->current < ctx->count );
0932
0933   rtems_test_assert( td->key == tn->key );
0934
0935   if ( td->parent == NULL ) {
0936     rtems_test_assert( rtems_rbtree_is_root( &tn->Node ) );
0937   } else {
0938     rtems_test_assert( td->parent == rtems_rbtree_parent( &tn->Node ) );
0939   }
0940
0941   rtems_test_assert( td->left == rtems_rbtree_left( &tn->Node ) );
0942   rtems_test_assert( td->right == rtems_rbtree_right( &tn->Node ) );
0943   rtems_test_assert( td->color == rb_color( &tn->Node ) );
0944
0945   ++ctx->current;
0946
0947   return false;
0948 }
0949
0950 static const test_node_description random_ops_tree_unique_1[] = {
0951   { 0, NULL, NULL, NULL, BLACK }
0952 };
0953
0954 static const test_node_description random_ops_tree_multiple_1[] = {
0955   { 0, NULL, NULL, NULL, BLACK }
0956 };
0957
0958 static const test_node_description random_ops_tree_unique_2[] = {
0959 };
0960
0961 static const test_node_description random_ops_tree_multiple_2[] = {
0962 };
0963
0964 static const test_node_description random_ops_tree_unique_3[] = {
0965   { 2, NULL, NULL, NULL, BLACK }
0966 };
0967
0968 static const test_node_description random_ops_tree_multiple_3[] = {
0969   { 1, NULL, NULL, NULL, BLACK }
0970 };
0971
0972 static const test_node_description random_ops_tree_unique_4[] = {
0973   { 0, TN(3), NULL, NULL, RED },
0974   { 3, NULL, TN(0), NULL, BLACK }
0975 };
0976
0977 static const test_node_description random_ops_tree_multiple_4[] = {
0978   { 0, NULL, NULL, TN( 3 ), BLACK },
0979   { 1, TN( 0 ), NULL, NULL, RED }
0980 };
0981
0982 static const test_node_description random_ops_tree_unique_5[] = {
0983   { 0, TN( 1 ), NULL, NULL, RED },
0984   { 1, NULL, TN( 0 ), TN( 4 ), BLACK },
0985   { 4, TN( 1 ), NULL, NULL, RED }
0986 };
0987
0988 static const test_node_description random_ops_tree_multiple_5[] = {
0989   { 0, TN( 1 ), NULL, NULL, RED },
0990   { 0, NULL, TN( 0 ), TN( 4 ), BLACK },
0991   { 2, TN( 1 ), NULL, NULL, RED }
0992 };
0993
0994 static const test_node_description random_ops_tree_unique_6[] = {
0995   { 0, TN( 2 ), NULL, NULL, RED },
0996   { 2, NULL, TN( 0 ), NULL, BLACK }
0997 };
0998
0999 static const test_node_description random_ops_tree_multiple_6[] = {
1000   { 0, TN( 2 ), NULL, NULL, RED },
1001   { 1, NULL, TN( 0 ), NULL, BLACK }
1002 };
1003
1004 static const test_node_description random_ops_tree_unique_7[] = {
1005   { 0, TN( 2 ), NULL, TN( 1 ), BLACK },
1006   { 1, TN( 0 ), NULL, NULL, RED },
1007   { 2, NULL, TN( 0 ), TN( 5 ), BLACK },
1008   { 4, TN( 5 ), NULL, NULL, RED },
1009   { 5, TN( 2 ), TN( 4 ), NULL, BLACK }
1010 };
1011
1012 static const test_node_description random_ops_tree_multiple_7[] = {
1013   { 0, TN( 2 ), NULL, TN( 1 ), BLACK },
1014   { 0, TN( 0 ), NULL, NULL, RED },
1015   { 1, NULL, TN( 0 ), TN( 4 ), BLACK },
1016   { 2, TN( 4 ), NULL, NULL, RED },
1017   { 2, TN( 2 ), TN( 5 ), NULL, BLACK }
1018 };
1019
1020 static const test_node_description random_ops_tree_unique_8[] = {
1021   { 0, TN(1), NULL, NULL, BLACK },
1022   { 1, NULL, TN(0), TN(6), BLACK },
1023   { 5, TN(6), NULL, NULL, RED },
1024   { 6, TN(1), TN(5), NULL, BLACK }
1025 };
1026
1027 static const test_node_description random_ops_tree_multiple_8[] = {
1028   { 0, TN( 5 ), NULL, TN( 0 ), BLACK },
1029   { 0, TN( 1 ), NULL, NULL, RED },
1030   { 2, NULL, TN( 1 ), TN( 6 ), BLACK },
1031   { 3, TN( 5 ), NULL, NULL, BLACK }
1032 };
1033
1034 static const test_node_description random_ops_tree_unique_9[] = {
1035   { 1, TN( 2 ), NULL, NULL, BLACK },
1036   { 2, TN( 6 ), TN( 1 ), TN( 4 ), RED },
1037   { 4, TN( 2 ), NULL, TN( 5 ), BLACK },
1038   { 5, TN( 4 ), NULL, NULL, RED },
1039   { 6, NULL, TN( 2 ), TN( 7 ), BLACK },
1040   { 7, TN( 6 ), NULL, TN( 8 ), BLACK },
1041   { 8, TN( 7 ), NULL, NULL, RED }
1042 };
1043
1044 static const test_node_description random_ops_tree_multiple_9[] = {
1045   { 0, TN( 2 ), NULL, NULL, BLACK },
1046   { 1, TN( 6 ), TN( 1 ), TN( 4 ), RED },
1047   { 2, TN( 2 ), NULL, TN( 5 ), BLACK },
1048   { 2, TN( 4 ), NULL, NULL, RED },
1049   { 3, NULL, TN( 2 ), TN( 7 ), BLACK },
1050   { 3, TN( 6 ), NULL, TN( 8 ), BLACK },
1051   { 4, TN( 7 ), NULL, NULL, RED }
1052 };
1053
1054 static const test_node_description random_ops_tree_unique_10[] = {
1055   { 0, TN( 2 ), NULL, NULL, BLACK },
1056   { 2, TN( 6 ), TN( 0 ), TN( 4 ), RED },
1057   { 3, TN( 4 ), NULL, NULL, RED },
1058   { 4, TN( 2 ), TN( 3 ), NULL, BLACK },
1059   { 6, NULL, TN( 2 ), TN( 8 ), BLACK },
1060   { 8, TN( 6 ), NULL, NULL, BLACK }
1061 };
1062
1063 static const test_node_description random_ops_tree_multiple_10[] = {
1064   { 0, TN( 2 ), NULL, NULL, BLACK },
1065   { 1, TN( 6 ), TN( 0 ), TN( 4 ), RED },
1066   { 1, TN( 4 ), NULL, NULL, RED },
1067   { 2, TN( 2 ), TN( 3 ), NULL, BLACK },
1068   { 3, NULL, TN( 2 ), TN( 8 ), BLACK },
1069   { 4, TN( 6 ), NULL, NULL, BLACK }
1070 };
1071
1072 static const test_node_description random_ops_tree_unique_11[] = {
1073   { 2, TN( 6 ), NULL, NULL, BLACK },
1074   { 6, NULL, TN( 2 ), TN( 8 ), BLACK },
1075   { 7, TN( 8 ), NULL, NULL, RED },
1076   { 8, TN( 6 ), TN( 7 ), TN( 9 ), BLACK },
1077   { 9, TN( 8 ), NULL, NULL, RED }
1078 };
1079
1080 static const test_node_description random_ops_tree_multiple_11[] = {
1081   { 1, TN( 6 ), NULL, NULL, BLACK },
1082   { 3, NULL, TN( 2 ), TN( 8 ), BLACK },
1083   { 3, TN( 8 ), NULL, NULL, RED },
1084   { 4, TN( 6 ), TN( 7 ), TN( 9 ), BLACK },
1085   { 4, TN( 8 ), NULL, NULL, RED }
1086 };
1087
1088 static const test_node_description random_ops_tree_unique_12[] = {
1089   { 0, TN( 1 ), NULL, NULL, RED },
1090   { 1, TN( 3 ), TN( 0 ), TN( 2 ), BLACK },
1091   { 2, TN( 1 ), NULL, NULL, RED },
1092   { 3, TN( 5 ), TN( 1 ), TN( 4 ), RED },
1093   { 4, TN( 3 ), NULL, NULL, BLACK },
1094   { 5, NULL, TN( 3 ), TN( 9 ), BLACK },
1095   { 9, TN( 5 ), NULL, TN( 11 ), BLACK },
1096   { 11, TN( 9 ), NULL, NULL, RED }
1097 };
1098
1099 static const test_node_description random_ops_tree_multiple_12[] = {
1100   { 0, TN( 1 ), NULL, NULL, BLACK },
1101   { 0, TN( 5 ), TN( 0 ), TN( 3 ), RED },
1102   { 1, TN( 1 ), NULL, TN( 2 ), BLACK },
1103   { 1, TN( 3 ), NULL, NULL, RED },
1104   { 2, NULL, TN( 1 ), TN( 9 ), BLACK },
1105   { 2, TN( 9 ), NULL, NULL, BLACK },
1106   { 4, TN( 5 ), TN( 4 ), TN( 11 ), RED },
1107   { 5, TN( 9 ), NULL, NULL, BLACK }
1108 };
1109
1110 static const test_node_description random_ops_tree_unique_13[] = {
1111   { 0, TN(1), NULL, NULL, RED },
1112   { 1, TN(3), TN(0), NULL, BLACK },
1113   { 3, TN(8), TN(1), TN(5), RED },
1114   { 4, TN(5), NULL, NULL, RED },
1115   { 5, TN(3), TN(4), TN(6), BLACK },
1116   { 6, TN(5), NULL, NULL, RED },
1117   { 8, NULL, TN(3), TN(11), BLACK },
1118   { 10, TN(11), NULL, NULL, RED },
1119   { 11, TN(8), TN(10), NULL, BLACK }
1120 };
1121
1122 static const test_node_description random_ops_tree_multiple_13[] = {
1123   { 0, TN(0), NULL, NULL, RED },
1124   { 0, TN(3), TN(1), NULL, BLACK },
1125   { 1, TN(6), TN(0), TN(4), RED },
1126   { 2, TN(3), NULL, TN(5), BLACK },
1127   { 2, TN(4), NULL, NULL, RED },
1128   { 3, NULL, TN(3), TN(11), BLACK },
1129   { 4, TN(11), NULL, NULL, RED },
1130   { 5, TN(6), TN(8), TN(10), BLACK },
1131   { 5, TN(11), NULL, NULL, RED }
1132 };
1133
1134 static const test_node_description random_ops_tree_unique_14[] = {
1135   { 3, TN(5), NULL, NULL, RED },
1136   { 5, TN(6), TN(3), NULL, BLACK },
1137   { 6, NULL, TN(5), TN(12), BLACK },
1138   { 8, TN(12), NULL, NULL, BLACK },
1139   { 12, TN(6), TN(8), TN(13), RED },
1140   { 13, TN(12), NULL, NULL, BLACK }
1141 };
1142
1143 static const test_node_description random_ops_tree_multiple_14[] = {
1144   { 1, TN( 5 ), NULL, NULL, RED },
1145   { 2, TN( 6 ), TN( 3 ), NULL, BLACK },
1146   { 3, NULL, TN( 5 ), TN( 13 ), BLACK },
1147   { 4, TN( 13 ), NULL, NULL, BLACK },
1148   { 6, TN( 6 ), TN( 8 ), TN( 12 ), RED },
1149   { 6, TN( 13 ), NULL, NULL, BLACK }
1150 };
1151
1152 static const test_node_description random_ops_tree_unique_15[] = {
1153   { 0, TN(2), NULL, NULL, RED },
1154   { 2, TN(8), TN(0), TN(7), BLACK },
1155   { 7, TN(2), NULL, NULL, RED },
1156   { 8, NULL, TN(2), TN(12), BLACK },
1157   { 9, TN(12), NULL, TN(10), BLACK },
1158   { 10, TN(9), NULL, NULL, RED },
1159   { 12, TN(8), TN(9), TN(13), RED },
1160   { 13, TN(12), NULL, TN(14), BLACK },
1161   { 14, TN(13), NULL, NULL, RED }
1162 };
1163
1164 static const test_node_description random_ops_tree_multiple_15[] = {
1165   { 0, TN(2), NULL, NULL, RED },
1166   { 1, TN(9), TN(0), TN(7), BLACK },
1167   { 3, TN(2), NULL, NULL, RED },
1168   { 4, NULL, TN(2), TN(10), BLACK },
1169   { 4, TN(10), NULL, NULL, BLACK },
1170   { 5, TN(9), TN(8), TN(12), RED },
1171   { 6, TN(12), NULL, NULL, RED },
1172   { 6, TN(10), TN(13), TN(14), BLACK },
1173   { 7, TN(12), NULL, NULL, RED }
1174 };
1175
1176 static const test_node_description random_ops_tree_unique_16[] = {
1177   { 0, TN(5), NULL, TN(3), BLACK },
1178   { 3, TN(0), NULL, NULL, RED },
1179   { 5, TN(10), TN(0), TN(7), RED },
1180   { 7, TN(5), NULL, NULL, BLACK },
1181   { 10, NULL, TN(5), TN(12), BLACK },
1182   { 12, TN(10), NULL, NULL, BLACK }
1183 };
1184
1185 static const test_node_description random_ops_tree_multiple_16[] = {
1186   { 0, TN(5), NULL, TN(3), BLACK },
1187   { 1, TN(0), NULL, NULL, RED },
1188   { 2, TN(10), TN(0), TN(7), RED },
1189   { 3, TN(5), NULL, NULL, BLACK },
1190   { 5, NULL, TN(5), TN(12), BLACK },
1191   { 6, TN(10), NULL, NULL, BLACK }
1192 };
1193
1194 static const test_node_description random_ops_tree_unique_17[] = {
1195   { 0, TN(1), NULL, NULL, RED },
1196   { 1, TN(3), TN(0), NULL, BLACK },
1197   { 3, TN(7), TN(1), TN(5), RED },
1198   { 4, TN(5), NULL, NULL, RED },
1199   { 5, TN(3), TN(4), NULL, BLACK },
1200   { 7, NULL, TN(3), TN(9), BLACK },
1201   { 8, TN(9), NULL, NULL, BLACK },
1202   { 9, TN(7), TN(8), TN(16), RED },
1203   { 16, TN(9), NULL, NULL, BLACK }
1204 };
1205
1206 static const test_node_description random_ops_tree_multiple_17[] = {
1207   { 0, TN(0), NULL, NULL, RED },
1208   { 0, TN(3), TN(1), NULL, BLACK },
1209   { 1, TN(7), TN(0), TN(5), RED },
1210   { 2, TN(3), NULL, TN(4), BLACK },
1211   { 2, TN(5), NULL, NULL, RED },
1212   { 3, NULL, TN(3), TN(8), BLACK },
1213   { 4, TN(8), NULL, NULL, BLACK },
1214   { 4, TN(7), TN(9), TN(16), RED },
1215   { 8, TN(8), NULL, NULL, BLACK }
1216 };
1217
1218 static const test_node_description random_ops_tree_unique_18[] = {
1219   { 0, TN(2), NULL, TN(1), BLACK },
1220   { 1, TN(0), NULL, NULL, RED },
1221   { 2, TN(4), TN(0), TN(3), BLACK },
1222   { 3, TN(2), NULL, NULL, BLACK },
1223   { 4, NULL, TN(2), TN(12), BLACK },
1224   { 5, TN(6), NULL, NULL, RED },
1225   { 6, TN(8), TN(5), TN(7), BLACK },
1226   { 7, TN(6), NULL, NULL, RED },
1227   { 8, TN(12), TN(6), TN(10), RED },
1228   { 9, TN(10), NULL, NULL, RED },
1229   { 10, TN(8), TN(9), NULL, BLACK },
1230   { 12, TN(4), TN(8), TN(17), BLACK },
1231   { 14, TN(17), NULL, NULL, RED },
1232   { 17, TN(12), TN(14), NULL, BLACK }
1233 };
1234
1235 static const test_node_description random_ops_tree_multiple_18[] = {
1236   { 0, TN(3), NULL, TN(1), BLACK },
1237   { 0, TN(0), NULL, NULL, RED },
1238   { 1, TN(4), TN(0), TN(2), BLACK },
1239   { 1, TN(3), NULL, NULL, BLACK },
1240   { 2, NULL, TN(3), TN(12), BLACK },
1241   { 2, TN(6), NULL, NULL, RED },
1242   { 3, TN(8), TN(5), TN(7), BLACK },
1243   { 3, TN(6), NULL, NULL, RED },
1244   { 4, TN(12), TN(6), TN(10), RED },
1245   { 4, TN(10), NULL, NULL, RED },
1246   { 5, TN(8), TN(9), NULL, BLACK },
1247   { 6, TN(4), TN(8), TN(14), BLACK },
1248   { 7, TN(12), NULL, TN(17), BLACK },
1249   { 8, TN(14), NULL, NULL, RED }
1250 };
1251
1252 static const test_node_description random_ops_tree_unique_19[] = {
1253   { 1, TN(2), NULL, NULL, RED },
1254   { 2, TN(6), TN(1), NULL, BLACK },
1255   { 6, TN(11), TN(2), TN(8), BLACK },
1256   { 8, TN(6), NULL, TN(9), BLACK },
1257   { 9, TN(8), NULL, NULL, RED },
1258   { 11, NULL, TN(6), TN(14), BLACK },
1259   { 12, TN(14), NULL, NULL, BLACK },
1260   { 14, TN(11), TN(12), TN(16), BLACK },
1261   { 16, TN(14), NULL, NULL, BLACK }
1262 };
1263
1264 static const test_node_description random_ops_tree_multiple_19[] = {
1265   { 0, TN(2), NULL, NULL, RED },
1266   { 1, TN(6), TN(1), NULL, BLACK },
1267   { 3, TN(11), TN(2), TN(9), BLACK },
1268   { 4, TN(6), NULL, TN(8), BLACK },
1269   { 4, TN(9), NULL, NULL, RED },
1270   { 5, NULL, TN(6), TN(14), BLACK },
1271   { 6, TN(14), NULL, NULL, BLACK },
1272   { 7, TN(11), TN(12), TN(16), BLACK },
1273   { 8, TN(14), NULL, NULL, BLACK }
1274 };
1275
1276 static const test_node_description random_ops_tree_unique_20[] = {
1277   { 0, TN(3), NULL, TN(1), BLACK },
1278   { 1, TN(0), NULL, NULL, RED },
1279   { 3, TN(9), TN(0), TN(7), BLACK },
1280   { 4, TN(7), NULL, NULL, RED },
1281   { 7, TN(3), TN(4), NULL, BLACK },
1282   { 9, NULL, TN(3), TN(12), BLACK },
1283   { 10, TN(12), NULL, NULL, BLACK },
1284   { 12, TN(9), TN(10), TN(17), BLACK },
1285   { 14, TN(17), NULL, NULL, BLACK },
1286   { 17, TN(12), TN(14), TN(18), RED },
1287   { 18, TN(17), NULL, TN(19), BLACK },
1288   { 19, TN(18), NULL, NULL, RED }
1289 };
1290
1291 static const test_node_description random_ops_tree_multiple_20[] = {
1292   { 0, TN(3), NULL, TN(1), BLACK },
1293   { 0, TN(0), NULL, NULL, RED },
1294   { 1, TN(9), TN(0), TN(7), BLACK },
1295   { 2, TN(7), NULL, NULL, RED },
1296   { 3, TN(3), TN(4), NULL, BLACK },
1297   { 4, NULL, TN(3), TN(14), BLACK },
1298   { 5, TN(14), NULL, TN(12), BLACK },
1299   { 6, TN(10), NULL, NULL, RED },
1300   { 7, TN(9), TN(10), TN(18), BLACK },
1301   { 8, TN(18), NULL, NULL, RED },
1302   { 9, TN(14), TN(17), TN(19), BLACK },
1303   { 9, TN(18), NULL, NULL, RED }
1304 };
1305
1306 static const test_node_description random_ops_tree_unique_21[] = {
1307   { 0, TN(3), NULL, TN(1), BLACK },
1308   { 1, TN(0), NULL, NULL, RED },
1309   { 3, TN(11), TN(0), TN(5), BLACK },
1310   { 4, TN(5), NULL, NULL, BLACK },
1311   { 5, TN(3), TN(4), TN(8), RED },
1312   { 8, TN(5), NULL, NULL, BLACK },
1313   { 11, NULL, TN(3), TN(15), BLACK },
1314   { 13, TN(15), NULL, NULL, BLACK },
1315   { 15, TN(11), TN(13), TN(17), BLACK },
1316   { 16, TN(17), NULL, NULL, RED },
1317   { 17, TN(15), TN(16), NULL, BLACK }
1318 };
1319
1320 static const test_node_description random_ops_tree_multiple_21[] = {
1321   { 0, TN(3), NULL, TN(1), BLACK },
1322   { 0, TN(0), NULL, NULL, RED },
1323   { 1, TN(8), TN(0), TN(4), BLACK },
1324   { 2, TN(3), NULL, TN(5), BLACK },
1325   { 2, TN(4), NULL, NULL, RED },
1326   { 4, NULL, TN(3), TN(13), BLACK },
1327   { 5, TN(13), NULL, NULL, BLACK },
1328   { 6, TN(8), TN(11), TN(17), BLACK },
1329   { 7, TN(17), NULL, NULL, BLACK },
1330   { 8, TN(13), TN(15), TN(16), RED },
1331   { 8, TN(17), NULL, NULL, BLACK }
1332 };
1333
1334 static const test_node_description random_ops_tree_unique_22[] = {
1335   { 1, TN(3), NULL, TN(2), BLACK },
1336   { 2, TN(1), NULL, NULL, RED },
1337   { 3, TN(8), TN(1), TN(7), BLACK },
1338   { 4, TN(7), NULL, NULL, RED },
1339   { 7, TN(3), TN(4), NULL, BLACK },
1340   { 8, NULL, TN(3), TN(14), BLACK },
1341   { 10, TN(11), NULL, NULL, RED },
1342   { 11, TN(14), TN(10), NULL, BLACK },
1343   { 14, TN(8), TN(11), TN(18), BLACK },
1344   { 15, TN(18), NULL, NULL, BLACK },
1345   { 18, TN(14), TN(15), TN(21), RED },
1346   { 21, TN(18), NULL, NULL, BLACK }
1347 };
1348
1349 static const test_node_description random_ops_tree_multiple_22[] = {
1350   { 0, TN(3), NULL, NULL, BLACK },
1351   { 1, TN(8), TN(1), TN(4), BLACK },
1352   { 1, TN(4), NULL, NULL, BLACK },
1353   { 2, TN(3), TN(2), TN(7), RED },
1354   { 3, TN(4), NULL, NULL, BLACK },
1355   { 4, NULL, TN(3), TN(14), BLACK },
1356   { 5, TN(14), NULL, TN(10), BLACK },
1357   { 5, TN(11), NULL, NULL, RED },
1358   { 7, TN(8), TN(11), TN(18), BLACK },
1359   { 7, TN(18), NULL, NULL, BLACK },
1360   { 9, TN(14), TN(15), TN(21), RED },
1361   { 10, TN(18), NULL, NULL, BLACK }
1362 };
1363
1364 static const test_node_description random_ops_tree_unique_23[] = {
1365   { 0, TN(2), NULL, NULL, RED },
1366   { 2, TN(8), TN(0), TN(7), BLACK },
1367   { 7, TN(2), NULL, NULL, RED },
1368   { 8, TN(12), TN(2), TN(11), BLACK },
1369   { 11, TN(8), NULL, NULL, BLACK },
1370   { 12, NULL, TN(8), TN(17), BLACK },
1371   { 13, TN(15), NULL, TN(14), BLACK },
1372   { 14, TN(13), NULL, NULL, RED },
1373   { 15, TN(17), TN(13), TN(16), RED },
1374   { 16, TN(15), NULL, NULL, BLACK },
1375   { 17, TN(12), TN(15), TN(20), BLACK },
1376   { 20, TN(17), NULL, TN(21), BLACK },
1377   { 21, TN(20), NULL, NULL, RED }
1378 };
1379
1380 static const test_node_description random_ops_tree_multiple_23[] = {
1381   { 0, TN(2), NULL, NULL, RED },
1382   { 1, TN(8), TN(0), TN(7), BLACK },
1383   { 3, TN(2), NULL, NULL, RED },
1384   { 4, TN(12), TN(2), TN(11), BLACK },
1385   { 5, TN(8), NULL, NULL, BLACK },
1386   { 6, NULL, TN(8), TN(17), BLACK },
1387   { 6, TN(15), NULL, NULL, BLACK },
1388   { 7, TN(17), TN(13), TN(16), RED },
1389   { 7, TN(16), NULL, NULL, RED },
1390   { 8, TN(15), TN(14), NULL, BLACK },
1391   { 8, TN(12), TN(15), TN(20), BLACK },
1392   { 10, TN(17), NULL, TN(21), BLACK },
1393   { 10, TN(20), NULL, NULL, RED }
1394 };
1395
1396 static const test_node_description random_ops_tree_unique_24[] = {
1397   { 4, TN(6), NULL, TN(5), BLACK },
1398   { 5, TN(4), NULL, NULL, RED },
1399   { 6, TN(14), TN(4), TN(10), BLACK },
1400   { 8, TN(10), NULL, NULL, RED },
1401   { 10, TN(6), TN(8), NULL, BLACK },
1402   { 14, NULL, TN(6), TN(20), BLACK },
1403   { 15, TN(16), NULL, NULL, RED },
1404   { 16, TN(20), TN(15), NULL, BLACK },
1405   { 20, TN(14), TN(16), TN(22), BLACK },
1406   { 22, TN(20), NULL, NULL, BLACK }
1407 };
1408
1409 static const test_node_description random_ops_tree_multiple_24[] = {
1410   { 2, TN(6), NULL, TN(5), BLACK },
1411   { 2, TN(4), NULL, NULL, RED },
1412   { 3, TN(14), TN(4), TN(10), BLACK },
1413   { 4, TN(10), NULL, NULL, RED },
1414   { 5, TN(6), TN(8), NULL, BLACK },
1415   { 7, NULL, TN(6), TN(20), BLACK },
1416   { 7, TN(16), NULL, NULL, RED },
1417   { 8, TN(20), TN(15), NULL, BLACK },
1418   { 10, TN(14), TN(16), TN(22), BLACK },
1419   { 11, TN(20), NULL, NULL, BLACK }
1420 };
1421
1422 static const test_node_description random_ops_tree_unique_25[] = {
1423   { 0, TN(1), NULL, NULL, RED },
1424   { 1, TN(3), TN(0), NULL, BLACK },
1425   { 3, TN(13), TN(1), TN(5), BLACK },
1426   { 4, TN(5), NULL, NULL, BLACK },
1427   { 5, TN(3), TN(4), TN(6), RED },
1428   { 6, TN(5), NULL, TN(9), BLACK },
1429   { 9, TN(6), NULL, NULL, RED },
1430   { 13, NULL, TN(3), TN(19), BLACK },
1431   { 14, TN(15), NULL, NULL, RED },
1432   { 15, TN(16), TN(14), NULL, BLACK },
1433   { 16, TN(19), TN(15), TN(17), RED },
1434   { 17, TN(16), NULL, NULL, BLACK },
1435   { 19, TN(13), TN(16), TN(23), BLACK },
1436   { 23, TN(19), NULL, TN(24), BLACK },
1437   { 24, TN(23), NULL, NULL, RED }
1438 };
1439
1440 static const test_node_description random_ops_tree_multiple_25[] = {
1441   { 0, TN(3), NULL, TN(1), BLACK },
1442   { 0, TN(0), NULL, NULL, RED },
1443   { 1, TN(13), TN(0), TN(4), BLACK },
1444   { 2, TN(4), NULL, NULL, BLACK },
1445   { 2, TN(3), TN(5), TN(6), RED },
1446   { 3, TN(4), NULL, TN(9), BLACK },
1447   { 4, TN(6), NULL, NULL, RED },
1448   { 6, NULL, TN(3), TN(19), BLACK },
1449   { 7, TN(17), NULL, TN(14), BLACK },
1450   { 7, TN(15), NULL, NULL, RED },
1451   { 8, TN(19), TN(15), TN(16), RED },
1452   { 8, TN(17), NULL, NULL, BLACK },
1453   { 9, TN(13), TN(17), TN(23), BLACK },
1454   { 11, TN(19), NULL, TN(24), BLACK },
1455   { 12, TN(23), NULL, NULL, RED }
1456 };
1457
1458 static const test_node_description random_ops_tree_unique_26[] = {
1459   { 0, TN(1), NULL, NULL, RED },
1460   { 1, TN(3), TN(0), NULL, BLACK },
1461   { 3, TN(11), TN(1), TN(9), BLACK },
1462   { 6, TN(9), NULL, NULL, RED },
1463   { 9, TN(3), TN(6), TN(10), BLACK },
1464   { 10, TN(9), NULL, NULL, RED },
1465   { 11, NULL, TN(3), TN(14), BLACK },
1466   { 12, TN(14), NULL, TN(13), BLACK },
1467   { 13, TN(12), NULL, NULL, RED },
1468   { 14, TN(11), TN(12), TN(20), BLACK },
1469   { 18, TN(20), NULL, NULL, BLACK },
1470   { 20, TN(14), TN(18), TN(23), RED },
1471   { 21, TN(23), NULL, NULL, RED },
1472   { 23, TN(20), TN(21), NULL, BLACK }
1473 };
1474
1475 static const test_node_description random_ops_tree_multiple_26[] = {
1476   { 0, TN(3), NULL, TN(0), BLACK },
1477   { 0, TN(1), NULL, NULL, RED },
1478   { 1, TN(9), TN(1), TN(6), BLACK },
1479   { 3, TN(3), NULL, NULL, BLACK },
1480   { 4, NULL, TN(3), TN(14), BLACK },
1481   { 5, TN(12), NULL, TN(10), BLACK },
1482   { 5, TN(11), NULL, NULL, RED },
1483   { 6, TN(14), TN(11), TN(13), RED },
1484   { 6, TN(12), NULL, NULL, BLACK },
1485   { 7, TN(9), TN(12), TN(20), BLACK },
1486   { 9, TN(20), NULL, NULL, BLACK },
1487   { 10, TN(14), TN(18), TN(23), RED },
1488   { 10, TN(23), NULL, NULL, RED },
1489   { 11, TN(20), TN(21), NULL, BLACK }
1490 };
1491
1492 static const test_node_description random_ops_tree_unique_27[] = {
1493   { 3, TN(8), NULL, NULL, BLACK },
1494   { 8, TN(19), TN(3), TN(17), BLACK },
1495   { 12, TN(17), NULL, NULL, RED },
1496   { 17, TN(8), TN(12), NULL, BLACK },
1497   { 19, NULL, TN(8), TN(24), BLACK },
1498   { 20, TN(21), NULL, NULL, RED },
1499   { 21, TN(24), TN(20), TN(23), BLACK },
1500   { 23, TN(21), NULL, NULL, RED },
1501   { 24, TN(19), TN(21), TN(25), BLACK },
1502   { 25, TN(24), NULL, TN(26), BLACK },
1503   { 26, TN(25), NULL, NULL, RED }
1504 };
1505
1506 static const test_node_description random_ops_tree_multiple_27[] = {
1507   { 1, TN(8), NULL, NULL, BLACK },
1508   { 4, TN(19), TN(3), TN(17), BLACK },
1509   { 6, TN(17), NULL, NULL, RED },
1510   { 8, TN(8), TN(12), NULL, BLACK },
1511   { 9, NULL, TN(8), TN(25), BLACK },
1512   { 10, TN(21), NULL, NULL, RED },
1513   { 10, TN(25), TN(20), TN(23), BLACK },
1514   { 11, TN(21), NULL, NULL, RED },
1515   { 12, TN(19), TN(21), TN(24), BLACK },
1516   { 12, TN(25), NULL, TN(26), BLACK },
1517   { 13, TN(24), NULL, NULL, RED }
1518 };
1519
1520 static const test_node_description random_ops_tree_unique_28[] = {
1521   { 0, TN(5), NULL, NULL, BLACK },
1522   { 5, TN(13), TN(0), TN(7), RED },
1523   { 7, TN(5), NULL, NULL, BLACK },
1524   { 13, NULL, TN(5), TN(17), BLACK },
1525   { 15, TN(17), NULL, NULL, BLACK },
1526   { 17, TN(13), TN(15), TN(26), RED },
1527   { 21, TN(26), NULL, NULL, RED },
1528   { 26, TN(17), TN(21), NULL, BLACK }
1529 };
1530
1531 static const test_node_description random_ops_tree_multiple_28[] = {
1532   { 0, TN(5), NULL, NULL, BLACK },
1533   { 2, TN(13), TN(0), TN(7), RED },
1534   { 3, TN(5), NULL, NULL, BLACK },
1535   { 6, NULL, TN(5), TN(17), BLACK },
1536   { 7, TN(17), NULL, NULL, BLACK },
1537   { 8, TN(13), TN(15), TN(26), RED },
1538   { 10, TN(26), NULL, NULL, RED },
1539   { 13, TN(17), TN(21), NULL, BLACK }
1540 };
1541
1542 static const test_node_description random_ops_tree_unique_29[] = {
1543   { 0, TN(3), NULL, TN(1), BLACK },
1544   { 1, TN(0), NULL, NULL, RED },
1545   { 3, TN(12), TN(0), TN(6), BLACK },
1546   { 4, TN(6), NULL, NULL, BLACK },
1547   { 6, TN(3), TN(4), TN(8), RED },
1548   { 7, TN(8), NULL, NULL, RED },
1549   { 8, TN(6), TN(7), TN(11), BLACK },
1550   { 11, TN(8), NULL, NULL, RED },
1551   { 12, NULL, TN(3), TN(17), BLACK },
1552   { 13, TN(17), NULL, TN(14), BLACK },
1553   { 14, TN(13), NULL, NULL, RED },
1554   { 17, TN(12), TN(13), TN(25), BLACK },
1555   { 22, TN(25), NULL, NULL, RED },
1556   { 25, TN(17), TN(22), TN(27), BLACK },
1557   { 27, TN(25), NULL, NULL, RED }
1558 };
1559
1560 static const test_node_description random_ops_tree_multiple_29[] = {
1561   { 0, TN(3), NULL, TN(1), BLACK },
1562   { 0, TN(0), NULL, NULL, RED },
1563   { 1, TN(11), TN(0), TN(6), BLACK },
1564   { 2, TN(6), NULL, NULL, BLACK },
1565   { 3, TN(3), TN(4), TN(7), RED },
1566   { 3, TN(6), NULL, TN(8), BLACK },
1567   { 4, TN(7), NULL, NULL, RED },
1568   { 5, NULL, TN(3), TN(22), BLACK },
1569   { 6, TN(12), NULL, NULL, BLACK },
1570   { 6, TN(22), TN(13), TN(17), RED },
1571   { 7, TN(17), NULL, NULL, RED },
1572   { 8, TN(12), TN(14), NULL, BLACK },
1573   { 11, TN(11), TN(12), TN(25), BLACK },
1574   { 12, TN(22), NULL, TN(27), BLACK },
1575   { 13, TN(25), NULL, NULL, RED }
1576 };
1577
1578 static const test_node_description random_ops_tree_unique_30[] = {
1579   { 0, TN(4), NULL, NULL, RED },
1580   { 4, TN(6), TN(0), NULL, BLACK },
1581   { 6, TN(13), TN(4), TN(9), RED },
1582   { 8, TN(9), NULL, NULL, RED },
1583   { 9, TN(6), TN(8), TN(12), BLACK },
1584   { 12, TN(9), NULL, NULL, RED },
1585   { 13, NULL, TN(6), TN(18), BLACK },
1586   { 14, TN(16), NULL, NULL, RED },
1587   { 16, TN(18), TN(14), TN(17), BLACK },
1588   { 17, TN(16), NULL, NULL, RED },
1589   { 18, TN(13), TN(16), TN(27), RED },
1590   { 20, TN(27), NULL, NULL, RED },
1591   { 27, TN(18), TN(20), TN(28), BLACK },
1592   { 28, TN(27), NULL, NULL, RED }
1593 };
1594
1595 static const test_node_description random_ops_tree_multiple_30[] = {
1596   { 0, TN(4), NULL, NULL, BLACK },
1597   { 2, TN(13), TN(0), TN(9), RED },
1598   { 3, TN(9), NULL, NULL, RED },
1599   { 4, TN(4), TN(6), TN(8), BLACK },
1600   { 4, TN(9), NULL, NULL, RED },
1601   { 6, TN(14), TN(4), TN(12), BLACK },
1602   { 6, TN(13), NULL, NULL, BLACK },
1603   { 7, NULL, TN(13), TN(18), BLACK },
1604   { 8, TN(18), NULL, TN(16), BLACK },
1605   { 8, TN(17), NULL, NULL, RED },
1606   { 9, TN(14), TN(17), TN(27), BLACK },
1607   { 10, TN(27), NULL, NULL, RED },
1608   { 13, TN(18), TN(20), TN(28), BLACK },
1609   { 14, TN(27), NULL, NULL, RED }
1610 };
1611
1612 static const test_node_description random_ops_tree_unique_31[] = {
1613   { 0, TN(2), NULL, NULL, RED },
1614   { 2, TN(5), TN(0), NULL, BLACK },
1615   { 5, TN(11), TN(2), TN(9), BLACK },
1616   { 7, TN(9), NULL, NULL, RED },
1617   { 9, TN(5), TN(7), NULL, BLACK },
1618   { 11, NULL, TN(5), TN(21), BLACK },
1619   { 14, TN(16), NULL, NULL, RED },
1620   { 16, TN(21), TN(14), TN(18), BLACK },
1621   { 18, TN(16), NULL, NULL, RED },
1622   { 21, TN(11), TN(16), TN(30), BLACK },
1623   { 30, TN(21), NULL, NULL, BLACK }
1624 };
1625
1626 static const test_node_description random_ops_tree_multiple_31[] = {
1627   { 0, TN(2), NULL, NULL, RED },
1628   { 1, TN(5), TN(0), NULL, BLACK },
1629   { 2, TN(11), TN(2), TN(9), BLACK },
1630   { 3, TN(9), NULL, NULL, RED },
1631   { 4, TN(5), TN(7), NULL, BLACK },
1632   { 5, NULL, TN(5), TN(21), BLACK },
1633   { 7, TN(16), NULL, NULL, RED },
1634   { 8, TN(21), TN(14), TN(18), BLACK },
1635   { 9, TN(16), NULL, NULL, RED },
1636   { 10, TN(11), TN(16), TN(30), BLACK },
1637   { 15, TN(21), NULL, NULL, BLACK }
1638 };
1639
1640 #define RANDOM_OPS_TREE( i ) \
1641   { &random_ops_tree_multiple_ ## i[ 0 ], &random_ops_tree_unique_ ## i[ 0 ] }
1642
1643 static const test_node_description *const random_ops_trees[][2] = {
1644   RANDOM_OPS_TREE( 1 ),
1645   RANDOM_OPS_TREE( 2 ),
1646   RANDOM_OPS_TREE( 3 ),
1647   RANDOM_OPS_TREE( 4 ),
1648   RANDOM_OPS_TREE( 5 ),
1649   RANDOM_OPS_TREE( 6 ),
1650   RANDOM_OPS_TREE( 7 ),
1651   RANDOM_OPS_TREE( 8 ),
1652   RANDOM_OPS_TREE( 9 ),
1653   RANDOM_OPS_TREE( 10 ),
1654   RANDOM_OPS_TREE( 11 ),
1655   RANDOM_OPS_TREE( 12 ),
1656   RANDOM_OPS_TREE( 13 ),
1657   RANDOM_OPS_TREE( 14 ),
1658   RANDOM_OPS_TREE( 15 ),
1659   RANDOM_OPS_TREE( 16 ),
1660   RANDOM_OPS_TREE( 17 ),
1661   RANDOM_OPS_TREE( 18 ),
1662   RANDOM_OPS_TREE( 19 ),
1663   RANDOM_OPS_TREE( 20 ),
1664   RANDOM_OPS_TREE( 21 ),
1665   RANDOM_OPS_TREE( 22 ),
1666   RANDOM_OPS_TREE( 23 ),
1667   RANDOM_OPS_TREE( 24 ),
1668   RANDOM_OPS_TREE( 25 ),
1669   RANDOM_OPS_TREE( 26 ),
1670   RANDOM_OPS_TREE( 27 ),
1671   RANDOM_OPS_TREE( 28 ),
1672   RANDOM_OPS_TREE( 29 ),
1673   RANDOM_OPS_TREE( 30 ),
1674   RANDOM_OPS_TREE( 31 )
1675 };
1676
1677 #define RANDOM_OPS_TREE_COUNT( i ) \
1678   { \
1679     RTEMS_ARRAY_SIZE( random_ops_tree_multiple_ ## i ), \
1680     RTEMS_ARRAY_SIZE( random_ops_tree_unique_ ## i ) \
1681   }
1682
1683 static const size_t random_ops_tree_counts[][2] = {
1684   RANDOM_OPS_TREE_COUNT( 1 ),
1685   RANDOM_OPS_TREE_COUNT( 2 ),
1686   RANDOM_OPS_TREE_COUNT( 3 ),
1687   RANDOM_OPS_TREE_COUNT( 4 ),
1688   RANDOM_OPS_TREE_COUNT( 5 ),
1689   RANDOM_OPS_TREE_COUNT( 6 ),
1690   RANDOM_OPS_TREE_COUNT( 7 ),
1691   RANDOM_OPS_TREE_COUNT( 8 ),
1692   RANDOM_OPS_TREE_COUNT( 9 ),
1693   RANDOM_OPS_TREE_COUNT( 10 ),
1694   RANDOM_OPS_TREE_COUNT( 11 ),
1695   RANDOM_OPS_TREE_COUNT( 12 ),
1696   RANDOM_OPS_TREE_COUNT( 13 ),
1697   RANDOM_OPS_TREE_COUNT( 14 ),
1698   RANDOM_OPS_TREE_COUNT( 15 ),
1699   RANDOM_OPS_TREE_COUNT( 16 ),
1700   RANDOM_OPS_TREE_COUNT( 17 ),
1701   RANDOM_OPS_TREE_COUNT( 18 ),
1702   RANDOM_OPS_TREE_COUNT( 19 ),
1703   RANDOM_OPS_TREE_COUNT( 20 ),
1704   RANDOM_OPS_TREE_COUNT( 21 ),
1705   RANDOM_OPS_TREE_COUNT( 22 ),
1706   RANDOM_OPS_TREE_COUNT( 23 ),
1707   RANDOM_OPS_TREE_COUNT( 24 ),
1708   RANDOM_OPS_TREE_COUNT( 25 ),
1709   RANDOM_OPS_TREE_COUNT( 26 ),
1710   RANDOM_OPS_TREE_COUNT( 27 ),
1711   RANDOM_OPS_TREE_COUNT( 28 ),
1712   RANDOM_OPS_TREE_COUNT( 29 ),
1713   RANDOM_OPS_TREE_COUNT( 30 ),
1714   RANDOM_OPS_TREE_COUNT( 31 )
1715 };
1716
1717 static uint32_t simple_random( uint32_t v )
1718 {
1719   v *= 1664525;
1720   v += 1013904223;
1721
1722   return v;
1723 }
1724
1725 static void random_ops( size_t n, bool unique )
1726 {
1727   visitor_context ctx = {
1728     0,
1729     random_ops_tree_counts[ n - 1 ][ unique ],
1730     random_ops_trees[ n - 1 ][ unique ]
1731   };
1732   rtems_rbtree_control tree;
1733   test_node *nodes = &node_array[ 0 ];
1734   size_t m = n * n * n;
1735   size_t s = unique ? 1 : 2;
1736   uint32_t v = 0xdeadbeef;
1737   size_t i;
1738
1739   rtems_rbtree_initialize_empty( &tree );
1740
1741   memset( nodes, 0, n * sizeof( *nodes ) );
1742
1743   for ( i = 0; i < n; ++i ) {
1744     nodes[ i ].key = (int) ( i / s );
1745   }
1746
1747   for ( i = 0; i < m; ++i ) {
1748     size_t j = ( v >> 13 ) % n;
1749     test_node *tn = &nodes[ j ];
1750
1751     if ( tn->id == 0 ) {
1752       tn->id = 1;
1753       rtems_rbtree_insert( &tree, &tn->Node, test_compare_function, unique );
1754     } else {
1755       tn->id = 0;
1756       rtems_rbtree_extract( &tree, &tn->Node );
1757     }
1758
1759     rtems_test_assert( rb_assert( rtems_rbtree_root( &tree ) ) != -1 );
1760
1761     v = simple_random( v );
1762   }
1763
1764   _RBTree_Iterate( &tree, visit_nodes, &ctx );
1765   rtems_test_assert( ctx.current == ctx.count );
1766 }
1767
1768 static void test_rbtree_random_ops( void )
1769 {
1770   size_t n;
1771
1772   puts( "INIT - Random operations" );
1773
1774   for ( n = 0; n < RTEMS_ARRAY_SIZE( random_ops_trees ); ++n ) {
1775     random_ops( n + 1, true );
1776     random_ops( n + 1, false );
1777   }
1778 }
1779
1780 typedef struct {
1781   rtems_rbtree_node *parent;
1782   rtems_rbtree_node *left;
1783   rtems_rbtree_node *right;
1784 } postorder_node_description;
1785
1786 static const postorder_node_description postorder_tree_1[] = {
1787   { NULL, NULL, NULL }
1788 };
1789
1790 /*
1791  *   TN_1
1792  *   /
1793  * TN_0
1794  */
1795 static const postorder_node_description postorder_tree_2[] = {
1796   { TN( 1 ), NULL, NULL },
1797   { NULL, TN( 0 ), NULL }
1798 };
1799
1800 /*
1801  * TN_1
1802  *     \
1803  *    TN_0
1804  */
1805 static const postorder_node_description postorder_tree_3[] = {
1806   { TN( 1 ), NULL, NULL },
1807   { NULL, NULL, TN( 0 ) }
1808 };
1809
1810 /*
1811  *    TN_2
1812  *   /    \
1813  * TN_0  TN_1
1814  */
1815 static const postorder_node_description postorder_tree_4[] = {
1816   { TN( 2 ), NULL, NULL },
1817   { TN( 2 ), NULL, NULL },
1818   { NULL, TN( 0 ), TN( 1 ) }
1819 };
1820
1821 /*
1822  *       TN_3
1823  *      /
1824  *    TN_2
1825  *   /    \
1826  * TN_0  TN_1
1827  */
1828 static const postorder_node_description postorder_tree_5[] = {
1829   { TN( 2 ), NULL, NULL },
1830   { TN( 2 ), NULL, NULL },
1831   { TN( 3 ), TN( 0 ), TN( 1 ) },
1832   { NULL, TN( 2 ), NULL }
1833 };
1834
1835 /*
1836  *      TN_10
1837  *     /      \
1838  *    TN_6     TN_9
1839  *   /    \        \
1840  * TN_0  TN_5       TN_8
1841  *      /    \      /
1842  *    TN_2   TN_4  TN_7
1843  *   /      /
1844  * TN_1   TN_3
1845  */
1846 static const postorder_node_description postorder_tree_6[] = {
1847   { TN( 6 ), NULL, NULL },
1848   { TN( 2 ), NULL, NULL },
1849   { TN( 5 ), TN( 1 ), NULL },
1850   { TN( 4 ), NULL, NULL },
1851   { TN( 5 ), TN( 3 ), NULL },
1852   { TN( 6 ), TN( 2 ), TN( 4 ) },
1853   { TN( 10 ), TN( 0 ), TN( 5 ) },
1854   { TN( 8 ), NULL, NULL },
1855   { TN( 9 ), TN( 7 ), NULL },
1856   { TN( 10 ), NULL, TN( 8 ) },
1857   { NULL, TN( 6 ), TN( 9 ) }
1858 };
1859
1860 /*
1861  *      TN_5
1862  *     /
1863  *    TN_4
1864  *   /
1865  * TN_3
1866  *     \
1867  *    TN_2
1868  *        \
1869  *       TN_1
1870  *      /
1871  *    TN_0
1872  */
1873 static const postorder_node_description postorder_tree_7[] = {
1874   { TN( 1 ), NULL, NULL },
1875   { TN( 2 ), TN( 0 ), NULL },
1876   { TN( 3 ), NULL, TN( 1 ) },
1877   { TN( 4 ), NULL, TN( 2 ) },
1878   { TN( 5 ), TN( 3 ), NULL },
1879   { NULL, TN( 0 ), NULL }
1880 };
1881
1882 typedef struct {
1883   const postorder_node_description *tree;
1884   size_t                            node_count;
1885 } postorder_tree;
1886
1887 #define POSTORDER_TREE( idx ) \
1888   { postorder_tree_##idx, RTEMS_ARRAY_SIZE( postorder_tree_##idx ) }
1889
1890 static const postorder_tree postorder_trees[] = {
1891   { NULL, 0 },
1892   POSTORDER_TREE( 1 ),
1893   POSTORDER_TREE( 2 ),
1894   POSTORDER_TREE( 3 ),
1895   POSTORDER_TREE( 4 ),
1896   POSTORDER_TREE( 5 ),
1897   POSTORDER_TREE( 6 ),
1898   POSTORDER_TREE( 7 )
1899 };
1900
1901 static void postorder_tree_init(
1902   RBTree_Control       *tree,
1903   const postorder_tree *pt
1904 )
1905 {
1906   size_t i;
1907
1908   memset( node_array, 0, pt->node_count * sizeof( node_array[ 0 ] ) );
1909
1910   if ( pt->node_count > 0 ) {
1911     _RBTree_Initialize_node( TN( 0 ) );
1912     _RBTree_Initialize_one( tree, TN( 0 ) );
1913   } else {
1914     _RBTree_Initialize_empty( tree );
1915   }
1916
1917   for ( i = 0; i < pt->node_count; ++i ) {
1918     const postorder_node_description *pnd;
1919
1920     pnd = &pt->tree[ i ];
1921     RTEMS_RB_PARENT( TN( i ), Node) = pnd->parent;
1922     RTEMS_RB_LEFT( TN( i ), Node) = pnd->left;
1923     RTEMS_RB_RIGHT( TN( i ), Node) = pnd->right;
1924   }
1925 }
1926
1927 static void postorder_tree_check(
1928   RBTree_Control       *tree,
1929   const postorder_tree *pt
1930 )
1931 {
1932   test_node *node;
1933   test_node *next;
1934   size_t i;
1935
1936   node = _RBTree_Postorder_first( tree, offsetof( test_node, Node ) );
1937
1938   for ( i = 0; i < pt->node_count; ++i ) {
1939     rtems_test_assert( node == &node_array[ i ] );
1940     node = _RBTree_Postorder_next( &node->Node, offsetof( test_node, Node ) );
1941   }
1942
1943   rtems_test_assert( node == NULL );
1944
1945   i = 0;
1946   next = NULL;
1947
1948   rbtree_postorder_for_each_entry_safe( node, next, tree, Node ) {
1949     rtems_test_assert( node == &node_array[ i ] );
1950
1951     if ( i < pt->node_count - 1 ) {
1952       rtems_test_assert( next == &node_array[ i + 1 ] );
1953     } else {
1954       rtems_test_assert( next == NULL );
1955     }
1956
1957     ++i;
1958   }
1959
1960   rtems_test_assert( i == pt->node_count );
1961   rtems_test_assert( node == NULL );
1962   rtems_test_assert( next == NULL );
1963 }
1964
1965 static void test_rbtree_postorder( void )
1966 {
1967   RBTree_Control tree;
1968   size_t         i;
1969
1970   puts( "INIT - Postorder operations" );
1971
1972   for ( i = 0; i < RTEMS_ARRAY_SIZE( postorder_trees ); ++i ) {
1973     const postorder_tree *pt;
1974
1975     pt = &postorder_trees[ i ];
1976     postorder_tree_init( &tree, pt );
1977     postorder_tree_check( &tree, pt );
1978   }
1979 }
1980
1981 rtems_task Init( rtems_task_argument ignored )
1982 {
1983   rtems_rbtree_control  rbtree1;
1984   rtems_rbtree_node    *p;
1985   test_node            node1, node2;
1986   test_node            search_node;
1987   int                  id;
1988   int i;
1989
1990   TEST_BEGIN();
1991
1992   puts( "Init - Initialize rbtree empty" );
1993   rtems_rbtree_initialize_empty( &rbtree1 );
1994
1995   rtems_rbtree_set_off_tree( &node1.Node );
1996   rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) );
1997
1998   /* verify that the rbtree insert work */
1999   puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
2000   node1.id = 1;
2001   node1.key = 1;
2002   node2.id = 2;
2003   node2.key = 2;
2004   rb_insert_unique( &rbtree1, &node1.Node );
2005   rb_insert_unique( &rbtree1, &node2.Node );
2006
2007   rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
2008
2009   if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2010     puts( "INIT - FAILED TREE CHECK" );
2011
2012   for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
2013       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2014     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2015     if ( id > 2 ) {
2016       puts( "INIT - TOO MANY NODES ON RBTREE" );
2017       rtems_test_exit(0);
2018     }
2019     if ( t->id != id ) {
2020       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2021       rtems_test_exit(0);
2022     }
2023
2024     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2025       puts( "INIT - FAILED TREE CHECK" );
2026   }
2027   if (id < 2) {
2028     puts("INIT - NOT ENOUGH NODES ON RBTREE");
2029     rtems_test_exit(0);
2030   }
2031
2032   puts("INIT - Verify rtems_rbtree_insert with the same value twice");
2033   node2.key = node1.key;
2034   rb_insert_unique(&rbtree1, &node1.Node);
2035   p = rb_insert_unique(&rbtree1, &node2.Node);
2036
2037   if (p != &node1.Node)
2038     puts( "INIT - FAILED DUPLICATE INSERT" );
2039
2040   for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
2041       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2042     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2043     if ( id > 1 ) {
2044       puts( "INIT - TOO MANY NODES ON RBTREE" );
2045       rtems_test_exit(0);
2046     }
2047     if ( t->id != id ) {
2048       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2049       rtems_test_exit(0);
2050     }
2051
2052     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2053       puts( "INIT - FAILED TREE CHECK" );
2054   }
2055   if (id < 1) {
2056     puts("INIT - NOT ENOUGH NODES ON RBTREE");
2057     rtems_test_exit(0);
2058   }
2059   node2.key = 2;
2060
2061   /* verify that the rbtree is empty */
2062   puts( "INIT - Verify rtems_rbtree_is_empty" );
2063   if(!rtems_rbtree_is_empty(&rbtree1)) {
2064     puts( "INIT - TREE NOT EMPTY" );
2065     rtems_test_exit(0);
2066   }
2067
2068   puts( "INIT - Verify rtems_XXX on an empty tree" );
2069   if(rtems_rbtree_get_min(&rbtree1)) {
2070     puts("INIT - get_min on empty returned non-NULL");
2071     rtems_test_exit(0);
2072   }
2073   if(rtems_rbtree_get_max(&rbtree1)) {
2074     puts("INIT - get_max on empty returned non-NULL");
2075     rtems_test_exit(0);
2076   }
2077   if(rtems_rbtree_peek_min(&rbtree1)) {
2078     puts("INIT - peek_min on empty returned non-NULL");
2079     rtems_test_exit(0);
2080   }
2081   if(rtems_rbtree_peek_max(&rbtree1)) {
2082     puts("INIT - peek_max on empty returned non-NULL");
2083     rtems_test_exit(0);
2084   }
2085
2086
2087   /* verify that the rbtree insert works after a tree is emptied */
2088   puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
2089   node1.id = 2;
2090   node1.key = 2;
2091   node2.id = 1;
2092   node2.key = 1;
2093   rb_insert_unique( &rbtree1, &node1.Node );
2094   rb_insert_unique( &rbtree1, &node2.Node );
2095
2096   puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
2097   test_node *t1 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_max(&rbtree1),
2098          test_node,Node);
2099   test_node *t2 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_min(&rbtree1),
2100          test_node,Node);
2101   if (t1->key - t2->key != 1) {
2102     puts( "INIT - Peek Min - Max failed" );
2103     rtems_test_exit(0);
2104   }
2105   p = rtems_rbtree_peek_max(&rbtree1);
2106   rtems_rbtree_extract(&rbtree1, p);
2107   t1 = RTEMS_CONTAINER_OF(p,test_node,Node);
2108   if (t1->key != 2) {
2109     puts( "INIT - rtems_rbtree_extract failed");
2110     rtems_test_exit(0);
2111   }
2112   rb_insert_unique(&rbtree1, p);
2113
2114   for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
2115       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2116     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2117     if ( id > 2 ) {
2118       puts( "INIT - TOO MANY NODES ON RBTREE" );
2119       rtems_test_exit(0);
2120     }
2121     if ( t->id != id ) {
2122       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2123       rtems_test_exit(0);
2124     }
2125   }
2126
2127   puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
2128   for (i = 0; i < 100; i++) {
2129     node_array[i].id = i;
2130     node_array[i].key = i;
2131     rb_insert_unique( &rbtree1, &node_array[i].Node );
2132
2133     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2134       puts( "INIT - FAILED TREE CHECK" );
2135   }
2136
2137   puts( "INIT - Removing 100 nodes" );
2138
2139   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2140       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2141     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2142     if ( id > 99 ) {
2143       puts( "INIT - TOO MANY NODES ON RBTREE" );
2144       rtems_test_exit(0);
2145     }
2146     if ( t->id != id ) {
2147       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2148       rtems_test_exit(0);
2149     }
2150
2151     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2152       puts( "INIT - FAILED TREE CHECK" );
2153   }
2154
2155   if(!rtems_rbtree_is_empty(&rbtree1)) {
2156     puts( "INIT - TREE NOT EMPTY" );
2157     rtems_test_exit(0);
2158   }
2159
2160   puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
2161   for (i = 0; i < 100; i++) {
2162     node_array[i].id = 99-i;
2163     node_array[i].key = 99-i;
2164     rb_insert_unique( &rbtree1, &node_array[i].Node );
2165
2166     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2167       puts( "INIT - FAILED TREE CHECK" );
2168   }
2169
2170   puts( "INIT - Removing 100 nodes" );
2171
2172   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2173       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2174     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2175     if ( id > 99 ) {
2176       puts( "INIT - TOO MANY NODES ON RBTREE" );
2177       rtems_test_exit(0);
2178     }
2179     if ( t->id != id ) {
2180       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2181       rtems_test_exit(0);
2182     }
2183
2184     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2185       puts( "INIT - FAILED TREE CHECK" );
2186   }
2187
2188   if(!rtems_rbtree_is_empty(&rbtree1)) {
2189     puts( "INIT - TREE NOT EMPTY" );
2190     rtems_test_exit(0);
2191   }
2192
2193   /* testing rbtree_extract by adding 100 nodes then removing the 20 with
2194    * keys specified by the numbers array, then removing the rest */
2195   puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
2196   for (i = 0; i < 100; i++) {
2197     node_array[i].id = i;
2198     node_array[i].key = i;
2199     rb_insert_unique( &rbtree1, &node_array[i].Node );
2200
2201     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2202       puts( "INIT - FAILED TREE CHECK" );
2203   }
2204
2205   puts( "INIT - Extracting 20 random nodes" );
2206
2207   for (i = 0; i < 20; i++) {
2208     id = numbers[i];
2209     rtems_rbtree_extract( &rbtree1, &node_array[id].Node );
2210     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2211       puts( "INIT - FAILED TREE CHECK" );
2212   }
2213
2214   puts( "INIT - Removing 80 nodes" );
2215
2216   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ;
2217       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2218     test_node *t = RTEMS_CONTAINER_OF(p, test_node, Node);
2219
2220     while ( id == numbers_sorted[i] ) {
2221       /* skip if expected minimum (id) is in the set of extracted numbers */
2222       id++;
2223       i++;
2224     }
2225
2226     if ( id > 99 ) {
2227       puts( "INIT - TOO MANY NODES ON RBTREE" );
2228       rtems_test_exit(0);
2229     }
2230
2231     if ( t->id != id ) {
2232       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2233       rtems_test_exit(0);
2234     }
2235
2236     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2237       puts( "INIT - FAILED TREE CHECK" );
2238   }
2239
2240   if(!rtems_rbtree_is_empty(&rbtree1)) {
2241     puts( "INIT - TREE NOT EMPTY" );
2242     rtems_test_exit(0);
2243   }
2244
2245   /* Additional rtems_rbtree_extract test which removes a node
2246    * with two children while target node has a left child only. */
2247   for ( i = 0; i < 7; i++ ) {
2248     node_array[i].id = i;
2249     node_array[i].key = i;
2250   }
2251   rb_insert_unique( &rbtree1, &node_array[3].Node );
2252   rb_insert_unique( &rbtree1, &node_array[1].Node );
2253   rb_insert_unique( &rbtree1, &node_array[5].Node );
2254   rb_insert_unique( &rbtree1, &node_array[0].Node );
2255   rb_insert_unique( &rbtree1, &node_array[2].Node );
2256   rb_insert_unique( &rbtree1, &node_array[4].Node );
2257   rb_insert_unique( &rbtree1, &node_array[6].Node );
2258   rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
2259   /* node_array[1] has now only a left child. */
2260   if ( !rtems_rbtree_left( &node_array[1].Node ) ||
2261         rtems_rbtree_right( &node_array[1].Node ) )
2262      puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
2263   rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
2264   while( (p = rtems_rbtree_get_max(&rbtree1)) );
2265
2266   puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
2267   for (i = 0; i < 100; i++) {
2268     node_array[i].id = 99-i;
2269     node_array[i].key = 99-i;
2270     rb_insert_unique( &rbtree1, &node_array[i].Node );
2271
2272     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2273       puts( "INIT - FAILED TREE CHECK" );
2274   }
2275
2276   puts( "INIT - Removing 100 nodes" );
2277
2278   for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
2279       p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
2280     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2281     if ( id > 99 ) {
2282       puts( "INIT - TOO MANY NODES ON RBTREE" );
2283       rtems_test_exit(0);
2284     }
2285     if ( t->id != 99-id ) {
2286       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2287       rtems_test_exit(0);
2288     }
2289
2290     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2291       puts( "INIT - FAILED TREE CHECK" );
2292   }
2293
2294   if(!rtems_rbtree_is_empty(&rbtree1)) {
2295     puts( "INIT - TREE NOT EMPTY" );
2296     rtems_test_exit(0);
2297   }
2298
2299   puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
2300   for (i = 0; i < 100; i++) {
2301     node_array[i].id = i;
2302     node_array[i].key = i;
2303     rb_insert_unique( &rbtree1, &node_array[i].Node );
2304
2305     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2306       puts( "INIT - FAILED TREE CHECK" );
2307   }
2308
2309   puts( "INIT - Verify rtems_rbtree_find" );
2310   search_node.key = 30;
2311   p = rb_find_unique(&rbtree1, &search_node.Node);
2312   if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 30) {
2313     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2314     rtems_test_exit(0);
2315   }
2316
2317   puts( "INIT - Verify rtems_rbtree_predecessor/successor");
2318   p = rtems_rbtree_predecessor(p);
2319   if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 29) {
2320     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2321     rtems_test_exit(0);
2322   }
2323   p = rb_find_unique(&rbtree1, &search_node.Node);
2324   p = rtems_rbtree_successor(p);
2325   if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 31) {
2326     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2327     rtems_test_exit(0);
2328   }
2329
2330   if ( rb_color( rtems_rbtree_root(&rbtree1) ) != BLACK )
2331     puts ( "INIT - ERROR ON RBTREE ROOT IS BLACK MISMATCH" );
2332
2333   puts( "INIT - Removing 100 nodes" );
2334
2335   for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
2336       p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
2337     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2338     if ( id < 0 ) {
2339       puts( "INIT - TOO MANY NODES ON RBTREE" );
2340       rtems_test_exit(0);
2341     }
2342     if ( t->id != id ) {
2343       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2344       rtems_test_exit(0);
2345     }
2346
2347     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2348       puts( "INIT - FAILED TREE CHECK" );
2349   }
2350
2351   if(!rtems_rbtree_is_empty(&rbtree1)) {
2352     puts( "INIT - TREE NOT EMPTY" );
2353     rtems_test_exit(0);
2354   }
2355
2356   puts("INIT - Insert 20 random numbers");
2357   for (i = 0; i < 20; i++) {
2358     visitor_context ctx = { 0, i + 1, test_insert_trees[ i ] };
2359
2360     node_array[i].id = numbers[i];
2361     node_array[i].key = numbers[i];
2362     rb_insert_unique( &rbtree1, &node_array[i].Node );
2363
2364     _RBTree_Iterate( &rbtree1, visit_nodes, &ctx );
2365     rtems_test_assert( ctx.current == ctx.count );
2366
2367     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2368       puts( "INIT - FAILED TREE CHECK" );
2369   }
2370
2371   puts( "INIT - Removing 20 nodes" );
2372
2373   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2374       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2375     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2376     if ( id > 19 ) {
2377       puts( "INIT - TOO MANY NODES ON RBTREE" );
2378       rtems_test_exit(0);
2379     }
2380     if ( t->id != numbers_sorted[id] ) {
2381       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2382       rtems_test_exit(0);
2383     }
2384
2385     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2386       puts( "INIT - FAILED TREE CHECK" );
2387
2388     if ( id < 19 ) {
2389       visitor_context ctx = { 0, 20 - id - 1, test_remove_trees[ id ] };
2390
2391       _RBTree_Iterate( &rbtree1, visit_nodes, &ctx );
2392       rtems_test_assert( ctx.current == ctx.count );
2393     }
2394   }
2395
2396   if(!rtems_rbtree_is_empty(&rbtree1)) {
2397     puts( "INIT - TREE NOT EMPTY" );
2398     rtems_test_exit(0);
2399   }
2400
2401   puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
2402   for (i = 0; i < 100; i++) {
2403     node_array[i].id = i;
2404     node_array[i].key = i;
2405   }
2406   rtems_rbtree_initialize( &rbtree1, &test_compare_function,
2407                            &node_array[0].Node, 100,
2408                            sizeof(test_node), true );
2409
2410   puts( "INIT - Removing 100 nodes" );
2411
2412   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2413       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2414     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2415     if ( id > 99 ) {
2416       puts( "INIT - TOO MANY NODES ON RBTREE" );
2417       rtems_test_exit(0);
2418     }
2419
2420     if ( t->id != id ) {
2421       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2422       rtems_test_exit(0);
2423     }
2424
2425     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2426       puts( "INIT - FAILED TREE CHECK" );
2427   }
2428
2429   if(!rtems_rbtree_is_empty(&rbtree1)) {
2430     puts( "INIT - TREE NOT EMPTY" );
2431     rtems_test_exit(0);
2432   }
2433
2434   /* Initialize the tree for duplicate keys */
2435   puts( "Init - Initialize duplicate rbtree empty" );
2436   rtems_rbtree_initialize_empty( &rbtree1 );
2437
2438   puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
2439   for (i = 0; i < 100; i++) {
2440     node_array[i].id = i;
2441     node_array[i].key = i%5;
2442     rb_insert_multi( &rbtree1, &node_array[i].Node );
2443
2444     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2445       puts( "INIT - FAILED TREE CHECK" );
2446   }
2447
2448   puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
2449   search_node.key = 2;
2450   p = rb_find_multi(&rbtree1, &search_node.Node);
2451   if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 2) {
2452     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2453     rtems_test_exit(0);
2454   }
2455
2456   puts( "INIT - Removing 100 nodes" );
2457
2458   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2459       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2460     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2461     if ( id > 99 ) {
2462       puts( "INIT - TOO MANY NODES ON RBTREE" );
2463       rtems_test_exit(0);
2464     }
2465     if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
2466       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2467       rtems_test_exit(0);
2468     }
2469
2470     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2471       puts( "INIT - FAILED TREE CHECK" );
2472   }
2473
2474   if(!rtems_rbtree_is_empty(&rbtree1)) {
2475     puts( "INIT - TREE NOT EMPTY" );
2476     rtems_test_exit(0);
2477   }
2478
2479   puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
2480   for (i = 0; i < 100; i++) {
2481     node_array[i].id = 99-i;
2482     node_array[i].key = (99-i)%5;
2483     rb_insert_multi( &rbtree1, &node_array[i].Node );
2484
2485     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2486       puts( "INIT - FAILED TREE CHECK" );
2487   }
2488
2489   puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
2490   search_node.key = 2;
2491   p = rb_find_multi(&rbtree1, &search_node.Node);
2492   if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 97) {
2493     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2494     rtems_test_exit(0);
2495   }
2496
2497   puts( "INIT - Removing 100 nodes" );
2498
2499   for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2500       p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2501     test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2502     if ( id > 99 ) {
2503       puts( "INIT - TOO MANY NODES ON RBTREE" );
2504       rtems_test_exit(0);
2505     }
2506     if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
2507       puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2508       rtems_test_exit(0);
2509     }
2510
2511     if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2512       puts( "INIT - FAILED TREE CHECK" );
2513   }
2514
2515   if(!rtems_rbtree_is_empty(&rbtree1)) {
2516     puts( "INIT - TREE NOT EMPTY" );
2517     rtems_test_exit(0);
2518   }
2519
2520   test_rbtree_postorder();
2521   test_rbtree_init_one();
2522   test_rbtree_min_max();
2523   test_rbtree_insert_inline();
2524   test_rbtree_random_ops();
2525
2526   TEST_END();
2527   rtems_test_exit(0);
2528 }
2529
2530 /* configuration information */
2531
2532 #define CONFIGURE_APPLICATION_NEEDS_SIMPLE_CONSOLE_DRIVER
2533 #define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
2534
2535 #define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION
2536
2537 #define CONFIGURE_RTEMS_INIT_TASKS_TABLE
2538 #define CONFIGURE_MAXIMUM_TASKS 1
2539
2540 #define CONFIGURE_INIT
2541 #include <rtems/confdefs.h>
2542
2543 /* global variables */