source: rtems/testsuites/sptests/sprbtree01/init.c @ 6539bea

Last change on this file since 6539bea was 6539bea, checked in by Sebastian Huber <sebastian.huber@…>, on Jun 29, 2018 at 6:00:28 PM

score: Add postorder tree iteration support

Update #3465.

  • Property mode set to 100644
File size: 73.8 KB
Line 
1/*
2 * Copyright (c) 2010 Gedare Bloom.
3 *
4 *  The license and distribution terms for this file may be
5 *  found in the file LICENSE in this distribution or at
6 *  http://www.rtems.org/license/LICENSE.
7 */
8
9#ifdef HAVE_CONFIG_H
10#include "config.h"
11#endif
12
13#include <tmacros.h>
14#include <rtems/rbtree.h>
15#include <rtems/score/rbtreeimpl.h>
16
17const char rtems_test_name[] = "SPRBTREE 1";
18
19/* forward declarations to avoid warnings */
20rtems_task Init(rtems_task_argument argument);
21
22static void test_rbtree_init_one(void)
23{
24  RBTree_Control tree;
25  RBTree_Node    node;
26
27  puts( "INIT - Initialize one" );
28
29  _RBTree_Initialize_node( &node );
30  _RBTree_Initialize_one( &tree, &node );
31  rtems_test_assert( !_RBTree_Is_empty( &tree ) );
32  rtems_test_assert( _RBTree_Is_root( &node ) );
33  rtems_test_assert( !_RBTree_Is_node_off_tree( &node ) );
34  rtems_test_assert( _RBTree_Left( &node ) == NULL );
35  rtems_test_assert( _RBTree_Right( &node ) == NULL );
36  rtems_test_assert( _RBTree_Parent( &node ) == NULL );
37  rtems_test_assert( _RBTree_Successor( &node ) == NULL );
38  rtems_test_assert( _RBTree_Predecessor( &node ) == NULL );
39  rtems_test_assert( _RBTree_Minimum( &tree ) == &node );
40  rtems_test_assert( _RBTree_Maximum( &tree ) == &node );
41
42  _RBTree_Extract( &tree, &node );
43  rtems_test_assert( _RBTree_Is_empty( &tree ) );
44}
45
46static const int numbers[20] = {
47  52, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71
48};
49
50static const int numbers_sorted[20] = {
51  0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99
52};
53
54typedef struct {
55  int              id;
56  int              key;
57  rtems_rbtree_node Node;
58} test_node;
59
60static test_node node_array[100];
61
62#define RED RB_RED
63
64#define BLACK RB_BLACK
65
66static int rb_color( const rtems_rbtree_node *n )
67{
68  return RB_COLOR( n, Node );
69}
70
71static rtems_rbtree_compare_result test_compare_function (
72  const rtems_rbtree_node *n1,
73  const rtems_rbtree_node *n2
74)
75{
76  int key1 = RTEMS_CONTAINER_OF( n1, test_node, Node )->key;
77  int key2 = RTEMS_CONTAINER_OF( n2, test_node, Node )->key;
78
79  return key1 - key2;
80}
81
82static rtems_rbtree_node *rb_insert_unique(
83  rtems_rbtree_control *rbtree,
84  rtems_rbtree_node    *node
85)
86{
87  return rtems_rbtree_insert( rbtree, node, test_compare_function, true );
88}
89
90static rtems_rbtree_node *rb_insert_multi(
91  rtems_rbtree_control *rbtree,
92  rtems_rbtree_node    *node
93)
94{
95  return rtems_rbtree_insert( rbtree, node, test_compare_function, false );
96}
97
98static rtems_rbtree_node *rb_find_unique(
99  rtems_rbtree_control *rbtree,
100  rtems_rbtree_node    *node
101)
102{
103  return rtems_rbtree_find( rbtree, node, test_compare_function, true );
104}
105
106static rtems_rbtree_node *rb_find_multi(
107  rtems_rbtree_control *rbtree,
108  rtems_rbtree_node    *node
109)
110{
111  return rtems_rbtree_find( rbtree, node, test_compare_function, false );
112}
113
114/*
115 * recursively checks tree. if the tree is built properly it should only
116 * be a depth of 7 function calls for 100 entries in the tree.
117 */
118static int rb_assert ( rtems_rbtree_node *root )
119{
120  int lh, rh;
121
122  if ( root == NULL )
123    return 1;
124  else {
125    rtems_rbtree_node *ln = rtems_rbtree_left(root);
126    rtems_rbtree_node *rn = rtems_rbtree_right(root);
127
128    /* Consecutive red links */
129    if ( rb_color( root ) == RED ) {
130      if (
131        ( ln && rb_color( ln ) == RED )
132          || ( rn && rb_color( rn ) == RED )
133      ) {
134        puts ( "Red violation" );
135        return -1;
136      }
137    }
138
139      lh = rb_assert ( ln );
140      rh = rb_assert ( rn );
141
142    /* Invalid binary search tree */
143    if ( ( ln != NULL && test_compare_function(ln, root) > 0 )
144        || ( rn != NULL && test_compare_function(rn, root) < 0 ) )
145    {
146      puts ( "Binary tree violation" );
147      return -1;
148    }
149
150    /* Black height mismatch */
151    if ( lh != -1 && rh != -1 && lh != rh ) {
152      puts ( "Black violation" );
153      return -1;
154    }
155
156    /* Only count black links */
157    if ( lh != -1 && rh != -1 )
158      return ( rb_color( root ) == RED ) ? lh : lh + 1;
159    else
160      return -1;
161  }
162}
163
164static test_node some_nodes[] = {
165  { .key = 1 },
166  { .key = 1 },
167  { .key = 1 },
168  { .key = 2 },
169  { .key = 2 },
170  { .key = 2 }
171};
172
173static void min_max_insert(
174  rtems_rbtree_control *tree,
175  rtems_rbtree_node    *node,
176  rtems_rbtree_node    *min,
177  rtems_rbtree_node    *max
178)
179{
180  rb_insert_multi( tree, node );
181  rtems_test_assert( rb_assert( rtems_rbtree_root( tree ) ) != -1 );
182  rtems_test_assert( rtems_rbtree_min( tree ) == min );
183  rtems_test_assert( rtems_rbtree_max( tree ) == max );
184}
185
186static void min_max_extract(
187  rtems_rbtree_control *tree,
188  rtems_rbtree_node    *node,
189  rtems_rbtree_node    *min,
190  rtems_rbtree_node    *max
191)
192{
193  rtems_rbtree_extract( tree, node );
194  rtems_test_assert( rb_assert( rtems_rbtree_root( tree ) ) != -1 );
195  rtems_test_assert( rtems_rbtree_min( tree ) == min );
196  rtems_test_assert( rtems_rbtree_max( tree ) == max );
197}
198
199static void test_rbtree_min_max(void)
200{
201  rtems_rbtree_control  tree;
202  rtems_rbtree_node    *node;
203  rtems_rbtree_node    *min;
204  rtems_rbtree_node    *max;
205
206  puts( "INIT - Verify min/max node updates" );
207
208  rtems_rbtree_initialize_empty( &tree );
209  rtems_test_assert( rb_assert( rtems_rbtree_root( &tree ) ) == 1 );
210
211  node = &some_nodes[ 0 ].Node;
212  min = node;
213  max = node;
214  min_max_insert( &tree, node, min, max );
215
216  node = &some_nodes[ 1 ].Node;
217  max = node;
218  min_max_insert( &tree, node, min, max );
219
220  node = &some_nodes[ 2 ].Node;
221  max = node;
222  min_max_insert( &tree, node, min, max );
223
224  node = &some_nodes[ 3 ].Node;
225  max = node;
226  min_max_insert( &tree, node, min, max );
227
228  node = &some_nodes[ 4 ].Node;
229  max = node;
230  min_max_insert( &tree, node, min, max );
231
232  node = &some_nodes[ 5 ].Node;
233  max = node;
234  min_max_insert( &tree, node, min, max );
235
236  node = &some_nodes[ 1 ].Node;
237  min_max_extract( &tree, node, min, max );
238
239  node = &some_nodes[ 4 ].Node;
240  min_max_extract( &tree, node, min, max );
241
242  node = &some_nodes[ 0 ].Node;
243  min = &some_nodes[ 2 ].Node;
244  min_max_extract( &tree, node, min, max );
245
246  node = &some_nodes[ 5 ].Node;
247  max = &some_nodes[ 3 ].Node;
248  min_max_extract( &tree, node, min, max );
249
250  node = &some_nodes[ 2 ].Node;
251  min = &some_nodes[ 3 ].Node;
252  min_max_extract( &tree, node, min, max );
253
254  node = &some_nodes[ 3 ].Node;
255  min = NULL;
256  max = NULL;
257  min_max_extract( &tree, node, min, max );
258  rtems_test_assert( rtems_rbtree_is_empty( &tree ) );
259}
260
261static bool test_less(
262  const void        *left,
263  const RBTree_Node *right
264)
265{
266  const int       *the_left;
267  const test_node *the_right;
268
269  the_left = left;
270  the_right = RTEMS_CONTAINER_OF( right, test_node, Node );
271
272  return *the_left < the_right->key;
273}
274
275static void test_rbtree_insert_inline( void )
276{
277  RBTree_Control tree;
278  test_node      a;
279  test_node      b;
280  test_node      c;
281  int            key;
282  bool           is_new_minimum;
283
284  puts( "INIT - Verify _RBTree_Insert_inline" );
285
286  a.key = 1;
287  b.key = 2;
288  c.key = 3;
289
290  _RBTree_Initialize_empty( &tree );
291  _RBTree_Initialize_node( &a.Node );
292  _RBTree_Initialize_node( &b.Node );
293  _RBTree_Initialize_node( &c.Node );
294
295  key = b.key;
296  is_new_minimum = _RBTree_Insert_inline(
297    &tree,
298    &b.Node,
299    &key,
300    test_less
301  );
302  rtems_test_assert( is_new_minimum );
303
304  key = c.key;
305  is_new_minimum = _RBTree_Insert_inline(
306    &tree,
307    &c.Node,
308    &key,
309    test_less
310  );
311  rtems_test_assert( !is_new_minimum );
312
313  key = a.key;
314  is_new_minimum = _RBTree_Insert_inline(
315    &tree,
316    &a.Node,
317    &key,
318    test_less
319  );
320  rtems_test_assert( is_new_minimum );
321}
322
323#define TN( i ) &node_array[ i ].Node
324
325typedef struct {
326  int key;
327  const rtems_rbtree_node *parent;
328  const rtems_rbtree_node *left;
329  const rtems_rbtree_node *right;
330  int color;
331} test_node_description;
332
333static const test_node_description test_insert_tree_0[] = {
334  { 52, NULL, NULL, NULL , BLACK }
335};
336
337static const test_node_description test_insert_tree_1[] = {
338  { 52, NULL, NULL, TN( 1 ) , BLACK },
339  { 99, TN( 0 ), NULL, NULL , RED }
340};
341
342static const test_node_description test_insert_tree_2[] = {
343  { 0, TN( 0 ), NULL, NULL , RED },
344  { 52, NULL, TN( 2 ), TN( 1 ) , BLACK },
345  { 99, TN( 0 ), NULL, NULL , RED }
346};
347
348static const test_node_description test_insert_tree_3[] = {
349  { 0, TN( 0 ), NULL, NULL , BLACK },
350  { 52, NULL, TN( 2 ), TN( 1 ) , BLACK },
351  { 85, TN( 1 ), NULL, NULL , RED },
352  { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
353};
354
355static const test_node_description test_insert_tree_4[] = {
356  { 0, TN( 0 ), NULL, TN( 4 ) , BLACK },
357  { 43, TN( 2 ), NULL, NULL , RED },
358  { 52, NULL, TN( 2 ), TN( 1 ) , BLACK },
359  { 85, TN( 1 ), NULL, NULL , RED },
360  { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
361};
362
363static const test_node_description test_insert_tree_5[] = {
364  { 0, TN( 4 ), NULL, NULL , RED },
365  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , BLACK },
366  { 44, TN( 4 ), NULL, NULL , RED },
367  { 52, NULL, TN( 4 ), TN( 1 ) , BLACK },
368  { 85, TN( 1 ), NULL, NULL , RED },
369  { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
370};
371
372static const test_node_description test_insert_tree_6[] = {
373  { 0, TN( 4 ), NULL, TN( 6 ) , BLACK },
374  { 10, TN( 2 ), NULL, NULL , RED },
375  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED },
376  { 44, TN( 4 ), NULL, NULL , BLACK },
377  { 52, NULL, TN( 4 ), TN( 1 ) , BLACK },
378  { 85, TN( 1 ), NULL, NULL , RED },
379  { 99, TN( 0 ), TN( 3 ), NULL , BLACK }
380};
381
382static const test_node_description test_insert_tree_7[] = {
383  { 0, TN( 4 ), NULL, TN( 6 ) , BLACK },
384  { 10, TN( 2 ), NULL, NULL , RED },
385  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED },
386  { 44, TN( 4 ), NULL, NULL , BLACK },
387  { 52, NULL, TN( 4 ), TN( 3 ) , BLACK },
388  { 60, TN( 3 ), NULL, NULL , RED },
389  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
390  { 99, TN( 3 ), NULL, NULL , RED }
391};
392
393static const test_node_description test_insert_tree_8[] = {
394  { 0, TN( 4 ), NULL, TN( 6 ) , BLACK },
395  { 10, TN( 2 ), NULL, NULL , RED },
396  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RED },
397  { 44, TN( 4 ), NULL, TN( 8 ) , BLACK },
398  { 50, TN( 5 ), NULL, NULL , RED },
399  { 52, NULL, TN( 4 ), TN( 3 ) , BLACK },
400  { 60, TN( 3 ), NULL, NULL , RED },
401  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
402  { 99, TN( 3 ), NULL, NULL , RED }
403};
404
405static const test_node_description test_insert_tree_9[] = {
406  { 0, TN( 6 ), NULL, NULL , RED },
407  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
408  { 19, TN( 6 ), NULL, NULL , RED },
409  { 43, TN( 0 ), TN( 6 ), TN( 5 ) , RED },
410  { 44, TN( 4 ), NULL, TN( 8 ) , BLACK },
411  { 50, TN( 5 ), NULL, NULL , RED },
412  { 52, NULL, TN( 4 ), TN( 3 ) , BLACK },
413  { 60, TN( 3 ), NULL, NULL , RED },
414  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
415  { 99, TN( 3 ), NULL, NULL , RED }
416};
417
418static const test_node_description test_insert_tree_10[] = {
419  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
420  { 8, TN( 2 ), NULL, NULL , RED },
421  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RED },
422  { 19, TN( 6 ), NULL, NULL , BLACK },
423  { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
424  { 44, TN( 0 ), NULL, TN( 8 ) , BLACK },
425  { 50, TN( 5 ), NULL, NULL , RED },
426  { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RED },
427  { 60, TN( 3 ), NULL, NULL , RED },
428  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , BLACK },
429  { 99, TN( 3 ), NULL, NULL , RED }
430};
431
432static const test_node_description test_insert_tree_11[] = {
433  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
434  { 8, TN( 2 ), NULL, NULL , RED },
435  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
436  { 19, TN( 6 ), NULL, NULL , BLACK },
437  { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
438  { 44, TN( 0 ), NULL, TN( 8 ) , BLACK },
439  { 50, TN( 5 ), NULL, NULL , RED },
440  { 52, TN( 4 ), TN( 5 ), TN( 3 ) , BLACK },
441  { 60, TN( 3 ), NULL, TN( 11 ) , BLACK },
442  { 68, TN( 7 ), NULL, NULL , RED },
443  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
444  { 99, TN( 3 ), NULL, NULL , BLACK }
445};
446
447static const test_node_description test_insert_tree_12[] = {
448  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
449  { 8, TN( 2 ), NULL, NULL , RED },
450  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
451  { 19, TN( 6 ), NULL, NULL , BLACK },
452  { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
453  { 44, TN( 12 ), NULL, NULL , RED },
454  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
455  { 50, TN( 12 ), NULL, NULL , RED },
456  { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK },
457  { 60, TN( 3 ), NULL, TN( 11 ) , BLACK },
458  { 68, TN( 7 ), NULL, NULL , RED },
459  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
460  { 99, TN( 3 ), NULL, NULL , BLACK }
461};
462
463static const test_node_description test_insert_tree_13[] = {
464  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
465  { 8, TN( 2 ), NULL, NULL , RED },
466  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
467  { 19, TN( 6 ), NULL, NULL , BLACK },
468  { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
469  { 44, TN( 12 ), NULL, NULL , RED },
470  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
471  { 50, TN( 12 ), NULL, NULL , RED },
472  { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK },
473  { 57, TN( 7 ), NULL, NULL , RED },
474  { 60, TN( 3 ), TN( 13 ), TN( 11 ) , BLACK },
475  { 68, TN( 7 ), NULL, NULL , RED },
476  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
477  { 99, TN( 3 ), NULL, NULL , BLACK }
478};
479
480static const test_node_description test_insert_tree_14[] = {
481  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
482  { 8, TN( 2 ), NULL, NULL , RED },
483  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
484  { 17, TN( 9 ), NULL, NULL , RED },
485  { 19, TN( 6 ), TN( 14 ), NULL , BLACK },
486  { 43, NULL, TN( 6 ), TN( 0 ) , BLACK },
487  { 44, TN( 12 ), NULL, NULL , RED },
488  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
489  { 50, TN( 12 ), NULL, NULL , RED },
490  { 52, TN( 4 ), TN( 12 ), TN( 3 ) , BLACK },
491  { 57, TN( 7 ), NULL, NULL , RED },
492  { 60, TN( 3 ), TN( 13 ), TN( 11 ) , BLACK },
493  { 68, TN( 7 ), NULL, NULL , RED },
494  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RED },
495  { 99, TN( 3 ), NULL, NULL , BLACK }
496};
497
498static const test_node_description test_insert_tree_15[] = {
499  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
500  { 8, TN( 2 ), NULL, NULL , RED },
501  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
502  { 17, TN( 9 ), NULL, NULL , RED },
503  { 19, TN( 6 ), TN( 14 ), NULL , BLACK },
504  { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
505  { 44, TN( 12 ), NULL, NULL , RED },
506  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
507  { 50, TN( 12 ), NULL, NULL , RED },
508  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
509  { 57, TN( 0 ), NULL, NULL , BLACK },
510  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
511  { 67, TN( 11 ), NULL, NULL , RED },
512  { 68, TN( 3 ), TN( 15 ), NULL , BLACK },
513  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
514  { 99, TN( 3 ), NULL, NULL , BLACK }
515};
516
517static const test_node_description test_insert_tree_16[] = {
518  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
519  { 8, TN( 2 ), NULL, NULL , RED },
520  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , BLACK },
521  { 17, TN( 9 ), NULL, NULL , RED },
522  { 19, TN( 6 ), TN( 14 ), NULL , BLACK },
523  { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
524  { 44, TN( 12 ), NULL, NULL , RED },
525  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
526  { 50, TN( 12 ), NULL, NULL , RED },
527  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
528  { 57, TN( 0 ), NULL, NULL , BLACK },
529  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
530  { 67, TN( 11 ), NULL, NULL , RED },
531  { 68, TN( 3 ), TN( 15 ), NULL , BLACK },
532  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
533  { 90, TN( 1 ), NULL, NULL , RED },
534  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
535};
536
537static const test_node_description test_insert_tree_17[] = {
538  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
539  { 8, TN( 2 ), NULL, NULL , RED },
540  { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK },
541  { 12, TN( 14 ), NULL, NULL , RED },
542  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
543  { 19, TN( 14 ), NULL, NULL , RED },
544  { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
545  { 44, TN( 12 ), NULL, NULL , RED },
546  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
547  { 50, TN( 12 ), NULL, NULL , RED },
548  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
549  { 57, TN( 0 ), NULL, NULL , BLACK },
550  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
551  { 67, TN( 11 ), NULL, NULL , RED },
552  { 68, TN( 3 ), TN( 15 ), NULL , BLACK },
553  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
554  { 90, TN( 1 ), NULL, NULL , RED },
555  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
556};
557
558static const test_node_description test_insert_tree_18[] = {
559  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
560  { 8, TN( 2 ), NULL, NULL , RED },
561  { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK },
562  { 12, TN( 14 ), NULL, NULL , RED },
563  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
564  { 19, TN( 14 ), NULL, NULL , RED },
565  { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
566  { 44, TN( 12 ), NULL, NULL , RED },
567  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
568  { 50, TN( 12 ), NULL, NULL , RED },
569  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RED },
570  { 57, TN( 0 ), NULL, NULL , BLACK },
571  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , BLACK },
572  { 67, TN( 11 ), NULL, NULL , RED },
573  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , BLACK },
574  { 77, TN( 11 ), NULL, NULL , RED },
575  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RED },
576  { 90, TN( 1 ), NULL, NULL , RED },
577  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
578};
579
580static const test_node_description test_insert_tree_19[] = {
581  { 0, TN( 6 ), NULL, TN( 10 ) , BLACK },
582  { 8, TN( 2 ), NULL, NULL , RED },
583  { 10, TN( 4 ), TN( 2 ), TN( 14 ) , BLACK },
584  { 12, TN( 14 ), NULL, NULL , RED },
585  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
586  { 19, TN( 14 ), NULL, NULL , RED },
587  { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
588  { 44, TN( 12 ), NULL, NULL , RED },
589  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
590  { 50, TN( 12 ), NULL, NULL , RED },
591  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
592  { 57, TN( 0 ), NULL, NULL , BLACK },
593  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
594  { 67, TN( 11 ), NULL, NULL , BLACK },
595  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
596  { 71, TN( 18 ), NULL, NULL , RED },
597  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
598  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
599  { 90, TN( 1 ), NULL, NULL , RED },
600  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
601};
602
603static const test_node_description *const test_insert_trees[] = {
604  &test_insert_tree_0[ 0 ],
605  &test_insert_tree_1[ 0 ],
606  &test_insert_tree_2[ 0 ],
607  &test_insert_tree_3[ 0 ],
608  &test_insert_tree_4[ 0 ],
609  &test_insert_tree_5[ 0 ],
610  &test_insert_tree_6[ 0 ],
611  &test_insert_tree_7[ 0 ],
612  &test_insert_tree_8[ 0 ],
613  &test_insert_tree_9[ 0 ],
614  &test_insert_tree_10[ 0 ],
615  &test_insert_tree_11[ 0 ],
616  &test_insert_tree_12[ 0 ],
617  &test_insert_tree_13[ 0 ],
618  &test_insert_tree_14[ 0 ],
619  &test_insert_tree_15[ 0 ],
620  &test_insert_tree_16[ 0 ],
621  &test_insert_tree_17[ 0 ],
622  &test_insert_tree_18[ 0 ],
623  &test_insert_tree_19[ 0 ]
624};
625
626static const test_node_description test_remove_tree_0[] = {
627  { 8, TN( 6 ), NULL, NULL , BLACK },
628  { 10, TN( 4 ), TN( 10 ), TN( 14 ) , BLACK },
629  { 12, TN( 14 ), NULL, NULL , RED },
630  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , BLACK },
631  { 19, TN( 14 ), NULL, NULL , RED },
632  { 43, NULL, TN( 6 ), TN( 7 ) , BLACK },
633  { 44, TN( 12 ), NULL, NULL , RED },
634  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
635  { 50, TN( 12 ), NULL, NULL , RED },
636  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
637  { 57, TN( 0 ), NULL, NULL , BLACK },
638  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
639  { 67, TN( 11 ), NULL, NULL , BLACK },
640  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
641  { 71, TN( 18 ), NULL, NULL , RED },
642  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
643  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
644  { 90, TN( 1 ), NULL, NULL , RED },
645  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
646};
647
648static const test_node_description test_remove_tree_1[] = {
649  { 10, TN( 14 ), NULL, TN( 17 ) , BLACK },
650  { 12, TN( 6 ), NULL, NULL , RED },
651  { 17, TN( 4 ), TN( 6 ), TN( 9 ) , BLACK },
652  { 19, TN( 14 ), NULL, NULL , BLACK },
653  { 43, NULL, TN( 14 ), TN( 7 ) , BLACK },
654  { 44, TN( 12 ), NULL, NULL , RED },
655  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
656  { 50, TN( 12 ), NULL, NULL , RED },
657  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
658  { 57, TN( 0 ), NULL, NULL , BLACK },
659  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
660  { 67, TN( 11 ), NULL, NULL , BLACK },
661  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
662  { 71, TN( 18 ), NULL, NULL , RED },
663  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
664  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
665  { 90, TN( 1 ), NULL, NULL , RED },
666  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
667};
668
669static const test_node_description test_remove_tree_2[] = {
670  { 12, TN( 14 ), NULL, NULL , BLACK },
671  { 17, TN( 4 ), TN( 17 ), TN( 9 ) , BLACK },
672  { 19, TN( 14 ), NULL, NULL , BLACK },
673  { 43, NULL, TN( 14 ), TN( 7 ) , BLACK },
674  { 44, TN( 12 ), NULL, NULL , RED },
675  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
676  { 50, TN( 12 ), NULL, NULL , RED },
677  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
678  { 57, TN( 0 ), NULL, NULL , BLACK },
679  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RED },
680  { 67, TN( 11 ), NULL, NULL , BLACK },
681  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
682  { 71, TN( 18 ), NULL, NULL , RED },
683  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
684  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
685  { 90, TN( 1 ), NULL, NULL , RED },
686  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
687};
688
689static const test_node_description test_remove_tree_3[] = {
690  { 17, TN( 4 ), NULL, TN( 9 ) , BLACK },
691  { 19, TN( 14 ), NULL, NULL , RED },
692  { 43, TN( 7 ), TN( 14 ), TN( 0 ) , BLACK },
693  { 44, TN( 12 ), NULL, NULL , RED },
694  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
695  { 50, TN( 12 ), NULL, NULL , RED },
696  { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RED },
697  { 57, TN( 0 ), NULL, NULL , BLACK },
698  { 60, NULL, TN( 4 ), TN( 3 ) , BLACK },
699  { 67, TN( 11 ), NULL, NULL , BLACK },
700  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
701  { 71, TN( 18 ), NULL, NULL , RED },
702  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
703  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
704  { 90, TN( 1 ), NULL, NULL , RED },
705  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
706};
707
708static const test_node_description test_remove_tree_4[] = {
709  { 19, TN( 4 ), NULL, NULL , BLACK },
710  { 43, TN( 7 ), TN( 9 ), TN( 0 ) , BLACK },
711  { 44, TN( 12 ), NULL, NULL , RED },
712  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , BLACK },
713  { 50, TN( 12 ), NULL, NULL , RED },
714  { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RED },
715  { 57, TN( 0 ), NULL, NULL , BLACK },
716  { 60, NULL, TN( 4 ), TN( 3 ) , BLACK },
717  { 67, TN( 11 ), NULL, NULL , BLACK },
718  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
719  { 71, TN( 18 ), NULL, NULL , RED },
720  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
721  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
722  { 90, TN( 1 ), NULL, NULL , RED },
723  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
724};
725
726static const test_node_description test_remove_tree_5[] = {
727  { 43, TN( 12 ), NULL, TN( 5 ) , BLACK },
728  { 44, TN( 4 ), NULL, NULL , RED },
729  { 48, TN( 0 ), TN( 4 ), TN( 8 ) , RED },
730  { 50, TN( 12 ), NULL, NULL , BLACK },
731  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
732  { 57, TN( 0 ), NULL, NULL , BLACK },
733  { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
734  { 67, TN( 11 ), NULL, NULL , BLACK },
735  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
736  { 71, TN( 18 ), NULL, NULL , RED },
737  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
738  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
739  { 90, TN( 1 ), NULL, NULL , RED },
740  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
741};
742
743static const test_node_description test_remove_tree_6[] = {
744  { 44, TN( 12 ), NULL, NULL , BLACK },
745  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RED },
746  { 50, TN( 12 ), NULL, NULL , BLACK },
747  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
748  { 57, TN( 0 ), NULL, NULL , BLACK },
749  { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
750  { 67, TN( 11 ), NULL, NULL , BLACK },
751  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
752  { 71, TN( 18 ), NULL, NULL , RED },
753  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
754  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
755  { 90, TN( 1 ), NULL, NULL , RED },
756  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
757};
758
759static const test_node_description test_remove_tree_7[] = {
760  { 48, TN( 0 ), NULL, TN( 8 ) , BLACK },
761  { 50, TN( 12 ), NULL, NULL , RED },
762  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , BLACK },
763  { 57, TN( 0 ), NULL, NULL , BLACK },
764  { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
765  { 67, TN( 11 ), NULL, NULL , BLACK },
766  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
767  { 71, TN( 18 ), NULL, NULL , RED },
768  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
769  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
770  { 90, TN( 1 ), NULL, NULL , RED },
771  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
772};
773
774static const test_node_description test_remove_tree_8[] = {
775  { 50, TN( 0 ), NULL, NULL , BLACK },
776  { 52, TN( 7 ), TN( 8 ), TN( 13 ) , BLACK },
777  { 57, TN( 0 ), NULL, NULL , BLACK },
778  { 60, NULL, TN( 0 ), TN( 3 ) , BLACK },
779  { 67, TN( 11 ), NULL, NULL , BLACK },
780  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RED },
781  { 71, TN( 18 ), NULL, NULL , RED },
782  { 77, TN( 11 ), TN( 19 ), NULL , BLACK },
783  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , BLACK },
784  { 90, TN( 1 ), NULL, NULL , RED },
785  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
786};
787
788static const test_node_description test_remove_tree_9[] = {
789  { 52, TN( 7 ), NULL, TN( 13 ) , BLACK },
790  { 57, TN( 0 ), NULL, NULL , RED },
791  { 60, TN( 11 ), TN( 0 ), TN( 15 ) , BLACK },
792  { 67, TN( 7 ), NULL, NULL , BLACK },
793  { 68, NULL, TN( 7 ), TN( 3 ) , BLACK },
794  { 71, TN( 18 ), NULL, NULL , RED },
795  { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
796  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , BLACK },
797  { 90, TN( 1 ), NULL, NULL , RED },
798  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
799};
800
801static const test_node_description test_remove_tree_10[] = {
802  { 57, TN( 7 ), NULL, NULL , BLACK },
803  { 60, TN( 11 ), TN( 13 ), TN( 15 ) , BLACK },
804  { 67, TN( 7 ), NULL, NULL , BLACK },
805  { 68, NULL, TN( 7 ), TN( 3 ) , BLACK },
806  { 71, TN( 18 ), NULL, NULL , RED },
807  { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
808  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , BLACK },
809  { 90, TN( 1 ), NULL, NULL , RED },
810  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
811};
812
813static const test_node_description test_remove_tree_11[] = {
814  { 60, TN( 11 ), NULL, TN( 15 ) , BLACK },
815  { 67, TN( 7 ), NULL, NULL , RED },
816  { 68, NULL, TN( 7 ), TN( 3 ) , BLACK },
817  { 71, TN( 18 ), NULL, NULL , RED },
818  { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
819  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RED },
820  { 90, TN( 1 ), NULL, NULL , RED },
821  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
822};
823
824static const test_node_description test_remove_tree_12[] = {
825  { 67, TN( 11 ), NULL, NULL , BLACK },
826  { 68, NULL, TN( 15 ), TN( 3 ) , BLACK },
827  { 71, TN( 18 ), NULL, NULL , RED },
828  { 77, TN( 3 ), TN( 19 ), NULL , BLACK },
829  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RED },
830  { 90, TN( 1 ), NULL, NULL , RED },
831  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
832};
833
834static const test_node_description test_remove_tree_13[] = {
835  { 68, TN( 19 ), NULL, NULL , BLACK },
836  { 71, TN( 3 ), TN( 11 ), TN( 18 ) , RED },
837  { 77, TN( 19 ), NULL, NULL , BLACK },
838  { 85, NULL, TN( 19 ), TN( 1 ) , BLACK },
839  { 90, TN( 1 ), NULL, NULL , RED },
840  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
841};
842
843static const test_node_description test_remove_tree_14[] = {
844  { 71, TN( 3 ), NULL, TN( 18 ) , BLACK },
845  { 77, TN( 19 ), NULL, NULL , RED },
846  { 85, NULL, TN( 19 ), TN( 1 ) , BLACK },
847  { 90, TN( 1 ), NULL, NULL , RED },
848  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
849};
850
851static const test_node_description test_remove_tree_15[] = {
852  { 77, TN( 3 ), NULL, NULL , BLACK },
853  { 85, NULL, TN( 18 ), TN( 1 ) , BLACK },
854  { 90, TN( 1 ), NULL, NULL , RED },
855  { 99, TN( 3 ), TN( 16 ), NULL , BLACK }
856};
857
858static const test_node_description test_remove_tree_16[] = {
859  { 85, TN( 16 ), NULL, NULL , BLACK },
860  { 90, NULL, TN( 3 ), TN( 1 ) , BLACK },
861  { 99, TN( 16 ), NULL, NULL , BLACK }
862};
863
864static const test_node_description test_remove_tree_17[] = {
865  { 90, NULL, NULL, TN( 1 ) , BLACK },
866  { 99, TN( 16 ), NULL, NULL , RED }
867};
868
869static const test_node_description test_remove_tree_18[] = {
870  { 99, NULL, NULL, NULL , BLACK }
871};
872
873static const test_node_description *const test_remove_trees[] = {
874  &test_remove_tree_0[ 0 ],
875  &test_remove_tree_1[ 0 ],
876  &test_remove_tree_2[ 0 ],
877  &test_remove_tree_3[ 0 ],
878  &test_remove_tree_4[ 0 ],
879  &test_remove_tree_5[ 0 ],
880  &test_remove_tree_6[ 0 ],
881  &test_remove_tree_7[ 0 ],
882  &test_remove_tree_8[ 0 ],
883  &test_remove_tree_9[ 0 ],
884  &test_remove_tree_10[ 0 ],
885  &test_remove_tree_11[ 0 ],
886  &test_remove_tree_12[ 0 ],
887  &test_remove_tree_13[ 0 ],
888  &test_remove_tree_14[ 0 ],
889  &test_remove_tree_15[ 0 ],
890  &test_remove_tree_16[ 0 ],
891  &test_remove_tree_17[ 0 ],
892  &test_remove_tree_18[ 0 ]
893};
894
895typedef struct {
896  int current;
897  int count;
898  const test_node_description *tree;
899} visitor_context;
900
901static bool visit_nodes(
902  const RBTree_Node *node,
903  void              *visitor_arg
904)
905{
906  visitor_context *ctx = visitor_arg;
907  const test_node_description *td = &ctx->tree[ ctx->current ];
908  const test_node *tn = RTEMS_CONTAINER_OF( node, test_node, Node );
909
910  rtems_test_assert( ctx->current < ctx->count );
911
912  rtems_test_assert( td->key == tn->key );
913
914  if ( td->parent == NULL ) {
915    rtems_test_assert( rtems_rbtree_is_root( &tn->Node ) );
916  } else {
917    rtems_test_assert( td->parent == rtems_rbtree_parent( &tn->Node ) );
918  }
919
920  rtems_test_assert( td->left == rtems_rbtree_left( &tn->Node ) );
921  rtems_test_assert( td->right == rtems_rbtree_right( &tn->Node ) );
922  rtems_test_assert( td->color == rb_color( &tn->Node ) );
923
924  ++ctx->current;
925
926  return false;
927}
928
929static const test_node_description random_ops_tree_unique_1[] = {
930  { 0, NULL, NULL, NULL, BLACK }
931};
932
933static const test_node_description random_ops_tree_multiple_1[] = {
934  { 0, NULL, NULL, NULL, BLACK }
935};
936
937static const test_node_description random_ops_tree_unique_2[] = {
938};
939
940static const test_node_description random_ops_tree_multiple_2[] = {
941};
942
943static const test_node_description random_ops_tree_unique_3[] = {
944  { 2, NULL, NULL, NULL, BLACK }
945};
946
947static const test_node_description random_ops_tree_multiple_3[] = {
948  { 1, NULL, NULL, NULL, BLACK }
949};
950
951static const test_node_description random_ops_tree_unique_4[] = {
952  { 0, TN(3), NULL, NULL, RED },
953  { 3, NULL, TN(0), NULL, BLACK }
954};
955
956static const test_node_description random_ops_tree_multiple_4[] = {
957  { 0, NULL, NULL, TN( 3 ), BLACK },
958  { 1, TN( 0 ), NULL, NULL, RED }
959};
960
961static const test_node_description random_ops_tree_unique_5[] = {
962  { 0, TN( 1 ), NULL, NULL, RED },
963  { 1, NULL, TN( 0 ), TN( 4 ), BLACK },
964  { 4, TN( 1 ), NULL, NULL, RED }
965};
966
967static const test_node_description random_ops_tree_multiple_5[] = {
968  { 0, TN( 1 ), NULL, NULL, RED },
969  { 0, NULL, TN( 0 ), TN( 4 ), BLACK },
970  { 2, TN( 1 ), NULL, NULL, RED }
971};
972
973static const test_node_description random_ops_tree_unique_6[] = {
974  { 0, TN( 2 ), NULL, NULL, RED },
975  { 2, NULL, TN( 0 ), NULL, BLACK }
976};
977
978static const test_node_description random_ops_tree_multiple_6[] = {
979  { 0, TN( 2 ), NULL, NULL, RED },
980  { 1, NULL, TN( 0 ), NULL, BLACK }
981};
982
983static const test_node_description random_ops_tree_unique_7[] = {
984  { 0, TN( 2 ), NULL, TN( 1 ), BLACK },
985  { 1, TN( 0 ), NULL, NULL, RED },
986  { 2, NULL, TN( 0 ), TN( 5 ), BLACK },
987  { 4, TN( 5 ), NULL, NULL, RED },
988  { 5, TN( 2 ), TN( 4 ), NULL, BLACK }
989};
990
991static const test_node_description random_ops_tree_multiple_7[] = {
992  { 0, TN( 2 ), NULL, TN( 1 ), BLACK },
993  { 0, TN( 0 ), NULL, NULL, RED },
994  { 1, NULL, TN( 0 ), TN( 4 ), BLACK },
995  { 2, TN( 4 ), NULL, NULL, RED },
996  { 2, TN( 2 ), TN( 5 ), NULL, BLACK }
997};
998
999static const test_node_description random_ops_tree_unique_8[] = {
1000  { 0, TN(1), NULL, NULL, BLACK },
1001  { 1, NULL, TN(0), TN(6), BLACK },
1002  { 5, TN(6), NULL, NULL, RED },
1003  { 6, TN(1), TN(5), NULL, BLACK }
1004};
1005
1006static const test_node_description random_ops_tree_multiple_8[] = {
1007  { 0, TN( 5 ), NULL, TN( 0 ), BLACK },
1008  { 0, TN( 1 ), NULL, NULL, RED },
1009  { 2, NULL, TN( 1 ), TN( 6 ), BLACK },
1010  { 3, TN( 5 ), NULL, NULL, BLACK }
1011};
1012
1013static const test_node_description random_ops_tree_unique_9[] = {
1014  { 1, TN( 2 ), NULL, NULL, BLACK },
1015  { 2, TN( 6 ), TN( 1 ), TN( 4 ), RED },
1016  { 4, TN( 2 ), NULL, TN( 5 ), BLACK },
1017  { 5, TN( 4 ), NULL, NULL, RED },
1018  { 6, NULL, TN( 2 ), TN( 7 ), BLACK },
1019  { 7, TN( 6 ), NULL, TN( 8 ), BLACK },
1020  { 8, TN( 7 ), NULL, NULL, RED }
1021};
1022
1023static const test_node_description random_ops_tree_multiple_9[] = {
1024  { 0, TN( 2 ), NULL, NULL, BLACK },
1025  { 1, TN( 6 ), TN( 1 ), TN( 4 ), RED },
1026  { 2, TN( 2 ), NULL, TN( 5 ), BLACK },
1027  { 2, TN( 4 ), NULL, NULL, RED },
1028  { 3, NULL, TN( 2 ), TN( 7 ), BLACK },
1029  { 3, TN( 6 ), NULL, TN( 8 ), BLACK },
1030  { 4, TN( 7 ), NULL, NULL, RED }
1031};
1032
1033static const test_node_description random_ops_tree_unique_10[] = {
1034  { 0, TN( 2 ), NULL, NULL, BLACK },
1035  { 2, TN( 6 ), TN( 0 ), TN( 4 ), RED },
1036  { 3, TN( 4 ), NULL, NULL, RED },
1037  { 4, TN( 2 ), TN( 3 ), NULL, BLACK },
1038  { 6, NULL, TN( 2 ), TN( 8 ), BLACK },
1039  { 8, TN( 6 ), NULL, NULL, BLACK }
1040};
1041
1042static const test_node_description random_ops_tree_multiple_10[] = {
1043  { 0, TN( 2 ), NULL, NULL, BLACK },
1044  { 1, TN( 6 ), TN( 0 ), TN( 4 ), RED },
1045  { 1, TN( 4 ), NULL, NULL, RED },
1046  { 2, TN( 2 ), TN( 3 ), NULL, BLACK },
1047  { 3, NULL, TN( 2 ), TN( 8 ), BLACK },
1048  { 4, TN( 6 ), NULL, NULL, BLACK }
1049};
1050
1051static const test_node_description random_ops_tree_unique_11[] = {
1052  { 2, TN( 6 ), NULL, NULL, BLACK },
1053  { 6, NULL, TN( 2 ), TN( 8 ), BLACK },
1054  { 7, TN( 8 ), NULL, NULL, RED },
1055  { 8, TN( 6 ), TN( 7 ), TN( 9 ), BLACK },
1056  { 9, TN( 8 ), NULL, NULL, RED }
1057};
1058
1059static const test_node_description random_ops_tree_multiple_11[] = {
1060  { 1, TN( 6 ), NULL, NULL, BLACK },
1061  { 3, NULL, TN( 2 ), TN( 8 ), BLACK },
1062  { 3, TN( 8 ), NULL, NULL, RED },
1063  { 4, TN( 6 ), TN( 7 ), TN( 9 ), BLACK },
1064  { 4, TN( 8 ), NULL, NULL, RED }
1065};
1066
1067static const test_node_description random_ops_tree_unique_12[] = {
1068  { 0, TN( 1 ), NULL, NULL, RED },
1069  { 1, TN( 3 ), TN( 0 ), TN( 2 ), BLACK },
1070  { 2, TN( 1 ), NULL, NULL, RED },
1071  { 3, TN( 5 ), TN( 1 ), TN( 4 ), RED },
1072  { 4, TN( 3 ), NULL, NULL, BLACK },
1073  { 5, NULL, TN( 3 ), TN( 9 ), BLACK },
1074  { 9, TN( 5 ), NULL, TN( 11 ), BLACK },
1075  { 11, TN( 9 ), NULL, NULL, RED }
1076};
1077
1078static const test_node_description random_ops_tree_multiple_12[] = {
1079  { 0, TN( 1 ), NULL, NULL, BLACK },
1080  { 0, TN( 5 ), TN( 0 ), TN( 3 ), RED },
1081  { 1, TN( 1 ), NULL, TN( 2 ), BLACK },
1082  { 1, TN( 3 ), NULL, NULL, RED },
1083  { 2, NULL, TN( 1 ), TN( 9 ), BLACK },
1084  { 2, TN( 9 ), NULL, NULL, BLACK },
1085  { 4, TN( 5 ), TN( 4 ), TN( 11 ), RED },
1086  { 5, TN( 9 ), NULL, NULL, BLACK }
1087};
1088
1089static const test_node_description random_ops_tree_unique_13[] = {
1090  { 0, TN(1), NULL, NULL, RED },
1091  { 1, TN(3), TN(0), NULL, BLACK },
1092  { 3, TN(8), TN(1), TN(5), RED },
1093  { 4, TN(5), NULL, NULL, RED },
1094  { 5, TN(3), TN(4), TN(6), BLACK },
1095  { 6, TN(5), NULL, NULL, RED },
1096  { 8, NULL, TN(3), TN(11), BLACK },
1097  { 10, TN(11), NULL, NULL, RED },
1098  { 11, TN(8), TN(10), NULL, BLACK }
1099};
1100
1101static const test_node_description random_ops_tree_multiple_13[] = {
1102  { 0, TN(0), NULL, NULL, RED },
1103  { 0, TN(3), TN(1), NULL, BLACK },
1104  { 1, TN(6), TN(0), TN(4), RED },
1105  { 2, TN(3), NULL, TN(5), BLACK },
1106  { 2, TN(4), NULL, NULL, RED },
1107  { 3, NULL, TN(3), TN(11), BLACK },
1108  { 4, TN(11), NULL, NULL, RED },
1109  { 5, TN(6), TN(8), TN(10), BLACK },
1110  { 5, TN(11), NULL, NULL, RED }
1111};
1112
1113static const test_node_description random_ops_tree_unique_14[] = {
1114  { 3, TN(5), NULL, NULL, RED },
1115  { 5, TN(6), TN(3), NULL, BLACK },
1116  { 6, NULL, TN(5), TN(12), BLACK },
1117  { 8, TN(12), NULL, NULL, BLACK },
1118  { 12, TN(6), TN(8), TN(13), RED },
1119  { 13, TN(12), NULL, NULL, BLACK }
1120};
1121
1122static const test_node_description random_ops_tree_multiple_14[] = {
1123  { 1, TN( 5 ), NULL, NULL, RED },
1124  { 2, TN( 6 ), TN( 3 ), NULL, BLACK },
1125  { 3, NULL, TN( 5 ), TN( 13 ), BLACK },
1126  { 4, TN( 13 ), NULL, NULL, BLACK },
1127  { 6, TN( 6 ), TN( 8 ), TN( 12 ), RED },
1128  { 6, TN( 13 ), NULL, NULL, BLACK }
1129};
1130
1131static const test_node_description random_ops_tree_unique_15[] = {
1132  { 0, TN(2), NULL, NULL, RED },
1133  { 2, TN(8), TN(0), TN(7), BLACK },
1134  { 7, TN(2), NULL, NULL, RED },
1135  { 8, NULL, TN(2), TN(12), BLACK },
1136  { 9, TN(12), NULL, TN(10), BLACK },
1137  { 10, TN(9), NULL, NULL, RED },
1138  { 12, TN(8), TN(9), TN(13), RED },
1139  { 13, TN(12), NULL, TN(14), BLACK },
1140  { 14, TN(13), NULL, NULL, RED }
1141};
1142
1143static const test_node_description random_ops_tree_multiple_15[] = {
1144  { 0, TN(2), NULL, NULL, RED },
1145  { 1, TN(9), TN(0), TN(7), BLACK },
1146  { 3, TN(2), NULL, NULL, RED },
1147  { 4, NULL, TN(2), TN(10), BLACK },
1148  { 4, TN(10), NULL, NULL, BLACK },
1149  { 5, TN(9), TN(8), TN(12), RED },
1150  { 6, TN(12), NULL, NULL, RED },
1151  { 6, TN(10), TN(13), TN(14), BLACK },
1152  { 7, TN(12), NULL, NULL, RED }
1153};
1154
1155static const test_node_description random_ops_tree_unique_16[] = {
1156  { 0, TN(5), NULL, TN(3), BLACK },
1157  { 3, TN(0), NULL, NULL, RED },
1158  { 5, TN(10), TN(0), TN(7), RED },
1159  { 7, TN(5), NULL, NULL, BLACK },
1160  { 10, NULL, TN(5), TN(12), BLACK },
1161  { 12, TN(10), NULL, NULL, BLACK }
1162};
1163
1164static const test_node_description random_ops_tree_multiple_16[] = {
1165  { 0, TN(5), NULL, TN(3), BLACK },
1166  { 1, TN(0), NULL, NULL, RED },
1167  { 2, TN(10), TN(0), TN(7), RED },
1168  { 3, TN(5), NULL, NULL, BLACK },
1169  { 5, NULL, TN(5), TN(12), BLACK },
1170  { 6, TN(10), NULL, NULL, BLACK }
1171};
1172
1173static const test_node_description random_ops_tree_unique_17[] = {
1174  { 0, TN(1), NULL, NULL, RED },
1175  { 1, TN(3), TN(0), NULL, BLACK },
1176  { 3, TN(7), TN(1), TN(5), RED },
1177  { 4, TN(5), NULL, NULL, RED },
1178  { 5, TN(3), TN(4), NULL, BLACK },
1179  { 7, NULL, TN(3), TN(9), BLACK },
1180  { 8, TN(9), NULL, NULL, BLACK },
1181  { 9, TN(7), TN(8), TN(16), RED },
1182  { 16, TN(9), NULL, NULL, BLACK }
1183};
1184
1185static const test_node_description random_ops_tree_multiple_17[] = {
1186  { 0, TN(0), NULL, NULL, RED },
1187  { 0, TN(3), TN(1), NULL, BLACK },
1188  { 1, TN(7), TN(0), TN(5), RED },
1189  { 2, TN(3), NULL, TN(4), BLACK },
1190  { 2, TN(5), NULL, NULL, RED },
1191  { 3, NULL, TN(3), TN(8), BLACK },
1192  { 4, TN(8), NULL, NULL, BLACK },
1193  { 4, TN(7), TN(9), TN(16), RED },
1194  { 8, TN(8), NULL, NULL, BLACK }
1195};
1196
1197static const test_node_description random_ops_tree_unique_18[] = {
1198  { 0, TN(2), NULL, TN(1), BLACK },
1199  { 1, TN(0), NULL, NULL, RED },
1200  { 2, TN(4), TN(0), TN(3), BLACK },
1201  { 3, TN(2), NULL, NULL, BLACK },
1202  { 4, NULL, TN(2), TN(12), BLACK },
1203  { 5, TN(6), NULL, NULL, RED },
1204  { 6, TN(8), TN(5), TN(7), BLACK },
1205  { 7, TN(6), NULL, NULL, RED },
1206  { 8, TN(12), TN(6), TN(10), RED },
1207  { 9, TN(10), NULL, NULL, RED },
1208  { 10, TN(8), TN(9), NULL, BLACK },
1209  { 12, TN(4), TN(8), TN(17), BLACK },
1210  { 14, TN(17), NULL, NULL, RED },
1211  { 17, TN(12), TN(14), NULL, BLACK }
1212};
1213
1214static const test_node_description random_ops_tree_multiple_18[] = {
1215  { 0, TN(3), NULL, TN(1), BLACK },
1216  { 0, TN(0), NULL, NULL, RED },
1217  { 1, TN(4), TN(0), TN(2), BLACK },
1218  { 1, TN(3), NULL, NULL, BLACK },
1219  { 2, NULL, TN(3), TN(12), BLACK },
1220  { 2, TN(6), NULL, NULL, RED },
1221  { 3, TN(8), TN(5), TN(7), BLACK },
1222  { 3, TN(6), NULL, NULL, RED },
1223  { 4, TN(12), TN(6), TN(10), RED },
1224  { 4, TN(10), NULL, NULL, RED },
1225  { 5, TN(8), TN(9), NULL, BLACK },
1226  { 6, TN(4), TN(8), TN(14), BLACK },
1227  { 7, TN(12), NULL, TN(17), BLACK },
1228  { 8, TN(14), NULL, NULL, RED }
1229};
1230
1231static const test_node_description random_ops_tree_unique_19[] = {
1232  { 1, TN(2), NULL, NULL, RED },
1233  { 2, TN(6), TN(1), NULL, BLACK },
1234  { 6, TN(11), TN(2), TN(8), BLACK },
1235  { 8, TN(6), NULL, TN(9), BLACK },
1236  { 9, TN(8), NULL, NULL, RED },
1237  { 11, NULL, TN(6), TN(14), BLACK },
1238  { 12, TN(14), NULL, NULL, BLACK },
1239  { 14, TN(11), TN(12), TN(16), BLACK },
1240  { 16, TN(14), NULL, NULL, BLACK }
1241};
1242
1243static const test_node_description random_ops_tree_multiple_19[] = {
1244  { 0, TN(2), NULL, NULL, RED },
1245  { 1, TN(6), TN(1), NULL, BLACK },
1246  { 3, TN(11), TN(2), TN(9), BLACK },
1247  { 4, TN(6), NULL, TN(8), BLACK },
1248  { 4, TN(9), NULL, NULL, RED },
1249  { 5, NULL, TN(6), TN(14), BLACK },
1250  { 6, TN(14), NULL, NULL, BLACK },
1251  { 7, TN(11), TN(12), TN(16), BLACK },
1252  { 8, TN(14), NULL, NULL, BLACK }
1253};
1254
1255static const test_node_description random_ops_tree_unique_20[] = {
1256  { 0, TN(3), NULL, TN(1), BLACK },
1257  { 1, TN(0), NULL, NULL, RED },
1258  { 3, TN(9), TN(0), TN(7), BLACK },
1259  { 4, TN(7), NULL, NULL, RED },
1260  { 7, TN(3), TN(4), NULL, BLACK },
1261  { 9, NULL, TN(3), TN(12), BLACK },
1262  { 10, TN(12), NULL, NULL, BLACK },
1263  { 12, TN(9), TN(10), TN(17), BLACK },
1264  { 14, TN(17), NULL, NULL, BLACK },
1265  { 17, TN(12), TN(14), TN(18), RED },
1266  { 18, TN(17), NULL, TN(19), BLACK },
1267  { 19, TN(18), NULL, NULL, RED }
1268};
1269
1270static const test_node_description random_ops_tree_multiple_20[] = {
1271  { 0, TN(3), NULL, TN(1), BLACK },
1272  { 0, TN(0), NULL, NULL, RED },
1273  { 1, TN(9), TN(0), TN(7), BLACK },
1274  { 2, TN(7), NULL, NULL, RED },
1275  { 3, TN(3), TN(4), NULL, BLACK },
1276  { 4, NULL, TN(3), TN(14), BLACK },
1277  { 5, TN(14), NULL, TN(12), BLACK },
1278  { 6, TN(10), NULL, NULL, RED },
1279  { 7, TN(9), TN(10), TN(18), BLACK },
1280  { 8, TN(18), NULL, NULL, RED },
1281  { 9, TN(14), TN(17), TN(19), BLACK },
1282  { 9, TN(18), NULL, NULL, RED }
1283};
1284
1285static const test_node_description random_ops_tree_unique_21[] = {
1286  { 0, TN(3), NULL, TN(1), BLACK },
1287  { 1, TN(0), NULL, NULL, RED },
1288  { 3, TN(11), TN(0), TN(5), BLACK },
1289  { 4, TN(5), NULL, NULL, BLACK },
1290  { 5, TN(3), TN(4), TN(8), RED },
1291  { 8, TN(5), NULL, NULL, BLACK },
1292  { 11, NULL, TN(3), TN(15), BLACK },
1293  { 13, TN(15), NULL, NULL, BLACK },
1294  { 15, TN(11), TN(13), TN(17), BLACK },
1295  { 16, TN(17), NULL, NULL, RED },
1296  { 17, TN(15), TN(16), NULL, BLACK }
1297};
1298
1299static const test_node_description random_ops_tree_multiple_21[] = {
1300  { 0, TN(3), NULL, TN(1), BLACK },
1301  { 0, TN(0), NULL, NULL, RED },
1302  { 1, TN(8), TN(0), TN(4), BLACK },
1303  { 2, TN(3), NULL, TN(5), BLACK },
1304  { 2, TN(4), NULL, NULL, RED },
1305  { 4, NULL, TN(3), TN(13), BLACK },
1306  { 5, TN(13), NULL, NULL, BLACK },
1307  { 6, TN(8), TN(11), TN(17), BLACK },
1308  { 7, TN(17), NULL, NULL, BLACK },
1309  { 8, TN(13), TN(15), TN(16), RED },
1310  { 8, TN(17), NULL, NULL, BLACK }
1311};
1312
1313static const test_node_description random_ops_tree_unique_22[] = {
1314  { 1, TN(3), NULL, TN(2), BLACK },
1315  { 2, TN(1), NULL, NULL, RED },
1316  { 3, TN(8), TN(1), TN(7), BLACK },
1317  { 4, TN(7), NULL, NULL, RED },
1318  { 7, TN(3), TN(4), NULL, BLACK },
1319  { 8, NULL, TN(3), TN(14), BLACK },
1320  { 10, TN(11), NULL, NULL, RED },
1321  { 11, TN(14), TN(10), NULL, BLACK },
1322  { 14, TN(8), TN(11), TN(18), BLACK },
1323  { 15, TN(18), NULL, NULL, BLACK },
1324  { 18, TN(14), TN(15), TN(21), RED },
1325  { 21, TN(18), NULL, NULL, BLACK }
1326};
1327
1328static const test_node_description random_ops_tree_multiple_22[] = {
1329  { 0, TN(3), NULL, NULL, BLACK },
1330  { 1, TN(8), TN(1), TN(4), BLACK },
1331  { 1, TN(4), NULL, NULL, BLACK },
1332  { 2, TN(3), TN(2), TN(7), RED },
1333  { 3, TN(4), NULL, NULL, BLACK },
1334  { 4, NULL, TN(3), TN(14), BLACK },
1335  { 5, TN(14), NULL, TN(10), BLACK },
1336  { 5, TN(11), NULL, NULL, RED },
1337  { 7, TN(8), TN(11), TN(18), BLACK },
1338  { 7, TN(18), NULL, NULL, BLACK },
1339  { 9, TN(14), TN(15), TN(21), RED },
1340  { 10, TN(18), NULL, NULL, BLACK }
1341};
1342
1343static const test_node_description random_ops_tree_unique_23[] = {
1344  { 0, TN(2), NULL, NULL, RED },
1345  { 2, TN(8), TN(0), TN(7), BLACK },
1346  { 7, TN(2), NULL, NULL, RED },
1347  { 8, TN(12), TN(2), TN(11), BLACK },
1348  { 11, TN(8), NULL, NULL, BLACK },
1349  { 12, NULL, TN(8), TN(17), BLACK },
1350  { 13, TN(15), NULL, TN(14), BLACK },
1351  { 14, TN(13), NULL, NULL, RED },
1352  { 15, TN(17), TN(13), TN(16), RED },
1353  { 16, TN(15), NULL, NULL, BLACK },
1354  { 17, TN(12), TN(15), TN(20), BLACK },
1355  { 20, TN(17), NULL, TN(21), BLACK },
1356  { 21, TN(20), NULL, NULL, RED }
1357};
1358
1359static const test_node_description random_ops_tree_multiple_23[] = {
1360  { 0, TN(2), NULL, NULL, RED },
1361  { 1, TN(8), TN(0), TN(7), BLACK },
1362  { 3, TN(2), NULL, NULL, RED },
1363  { 4, TN(12), TN(2), TN(11), BLACK },
1364  { 5, TN(8), NULL, NULL, BLACK },
1365  { 6, NULL, TN(8), TN(17), BLACK },
1366  { 6, TN(15), NULL, NULL, BLACK },
1367  { 7, TN(17), TN(13), TN(16), RED },
1368  { 7, TN(16), NULL, NULL, RED },
1369  { 8, TN(15), TN(14), NULL, BLACK },
1370  { 8, TN(12), TN(15), TN(20), BLACK },
1371  { 10, TN(17), NULL, TN(21), BLACK },
1372  { 10, TN(20), NULL, NULL, RED }
1373};
1374
1375static const test_node_description random_ops_tree_unique_24[] = {
1376  { 4, TN(6), NULL, TN(5), BLACK },
1377  { 5, TN(4), NULL, NULL, RED },
1378  { 6, TN(14), TN(4), TN(10), BLACK },
1379  { 8, TN(10), NULL, NULL, RED },
1380  { 10, TN(6), TN(8), NULL, BLACK },
1381  { 14, NULL, TN(6), TN(20), BLACK },
1382  { 15, TN(16), NULL, NULL, RED },
1383  { 16, TN(20), TN(15), NULL, BLACK },
1384  { 20, TN(14), TN(16), TN(22), BLACK },
1385  { 22, TN(20), NULL, NULL, BLACK }
1386};
1387
1388static const test_node_description random_ops_tree_multiple_24[] = {
1389  { 2, TN(6), NULL, TN(5), BLACK },
1390  { 2, TN(4), NULL, NULL, RED },
1391  { 3, TN(14), TN(4), TN(10), BLACK },
1392  { 4, TN(10), NULL, NULL, RED },
1393  { 5, TN(6), TN(8), NULL, BLACK },
1394  { 7, NULL, TN(6), TN(20), BLACK },
1395  { 7, TN(16), NULL, NULL, RED },
1396  { 8, TN(20), TN(15), NULL, BLACK },
1397  { 10, TN(14), TN(16), TN(22), BLACK },
1398  { 11, TN(20), NULL, NULL, BLACK }
1399};
1400
1401static const test_node_description random_ops_tree_unique_25[] = {
1402  { 0, TN(1), NULL, NULL, RED },
1403  { 1, TN(3), TN(0), NULL, BLACK },
1404  { 3, TN(13), TN(1), TN(5), BLACK },
1405  { 4, TN(5), NULL, NULL, BLACK },
1406  { 5, TN(3), TN(4), TN(6), RED },
1407  { 6, TN(5), NULL, TN(9), BLACK },
1408  { 9, TN(6), NULL, NULL, RED },
1409  { 13, NULL, TN(3), TN(19), BLACK },
1410  { 14, TN(15), NULL, NULL, RED },
1411  { 15, TN(16), TN(14), NULL, BLACK },
1412  { 16, TN(19), TN(15), TN(17), RED },
1413  { 17, TN(16), NULL, NULL, BLACK },
1414  { 19, TN(13), TN(16), TN(23), BLACK },
1415  { 23, TN(19), NULL, TN(24), BLACK },
1416  { 24, TN(23), NULL, NULL, RED }
1417};
1418
1419static const test_node_description random_ops_tree_multiple_25[] = {
1420  { 0, TN(3), NULL, TN(1), BLACK },
1421  { 0, TN(0), NULL, NULL, RED },
1422  { 1, TN(13), TN(0), TN(4), BLACK },
1423  { 2, TN(4), NULL, NULL, BLACK },
1424  { 2, TN(3), TN(5), TN(6), RED },
1425  { 3, TN(4), NULL, TN(9), BLACK },
1426  { 4, TN(6), NULL, NULL, RED },
1427  { 6, NULL, TN(3), TN(19), BLACK },
1428  { 7, TN(17), NULL, TN(14), BLACK },
1429  { 7, TN(15), NULL, NULL, RED },
1430  { 8, TN(19), TN(15), TN(16), RED },
1431  { 8, TN(17), NULL, NULL, BLACK },
1432  { 9, TN(13), TN(17), TN(23), BLACK },
1433  { 11, TN(19), NULL, TN(24), BLACK },
1434  { 12, TN(23), NULL, NULL, RED }
1435};
1436
1437static const test_node_description random_ops_tree_unique_26[] = {
1438  { 0, TN(1), NULL, NULL, RED },
1439  { 1, TN(3), TN(0), NULL, BLACK },
1440  { 3, TN(11), TN(1), TN(9), BLACK },
1441  { 6, TN(9), NULL, NULL, RED },
1442  { 9, TN(3), TN(6), TN(10), BLACK },
1443  { 10, TN(9), NULL, NULL, RED },
1444  { 11, NULL, TN(3), TN(14), BLACK },
1445  { 12, TN(14), NULL, TN(13), BLACK },
1446  { 13, TN(12), NULL, NULL, RED },
1447  { 14, TN(11), TN(12), TN(20), BLACK },
1448  { 18, TN(20), NULL, NULL, BLACK },
1449  { 20, TN(14), TN(18), TN(23), RED },
1450  { 21, TN(23), NULL, NULL, RED },
1451  { 23, TN(20), TN(21), NULL, BLACK }
1452};
1453
1454static const test_node_description random_ops_tree_multiple_26[] = {
1455  { 0, TN(3), NULL, TN(0), BLACK },
1456  { 0, TN(1), NULL, NULL, RED },
1457  { 1, TN(9), TN(1), TN(6), BLACK },
1458  { 3, TN(3), NULL, NULL, BLACK },
1459  { 4, NULL, TN(3), TN(14), BLACK },
1460  { 5, TN(12), NULL, TN(10), BLACK },
1461  { 5, TN(11), NULL, NULL, RED },
1462  { 6, TN(14), TN(11), TN(13), RED },
1463  { 6, TN(12), NULL, NULL, BLACK },
1464  { 7, TN(9), TN(12), TN(20), BLACK },
1465  { 9, TN(20), NULL, NULL, BLACK },
1466  { 10, TN(14), TN(18), TN(23), RED },
1467  { 10, TN(23), NULL, NULL, RED },
1468  { 11, TN(20), TN(21), NULL, BLACK }
1469};
1470
1471static const test_node_description random_ops_tree_unique_27[] = {
1472  { 3, TN(8), NULL, NULL, BLACK },
1473  { 8, TN(19), TN(3), TN(17), BLACK },
1474  { 12, TN(17), NULL, NULL, RED },
1475  { 17, TN(8), TN(12), NULL, BLACK },
1476  { 19, NULL, TN(8), TN(24), BLACK },
1477  { 20, TN(21), NULL, NULL, RED },
1478  { 21, TN(24), TN(20), TN(23), BLACK },
1479  { 23, TN(21), NULL, NULL, RED },
1480  { 24, TN(19), TN(21), TN(25), BLACK },
1481  { 25, TN(24), NULL, TN(26), BLACK },
1482  { 26, TN(25), NULL, NULL, RED }
1483};
1484
1485static const test_node_description random_ops_tree_multiple_27[] = {
1486  { 1, TN(8), NULL, NULL, BLACK },
1487  { 4, TN(19), TN(3), TN(17), BLACK },
1488  { 6, TN(17), NULL, NULL, RED },
1489  { 8, TN(8), TN(12), NULL, BLACK },
1490  { 9, NULL, TN(8), TN(25), BLACK },
1491  { 10, TN(21), NULL, NULL, RED },
1492  { 10, TN(25), TN(20), TN(23), BLACK },
1493  { 11, TN(21), NULL, NULL, RED },
1494  { 12, TN(19), TN(21), TN(24), BLACK },
1495  { 12, TN(25), NULL, TN(26), BLACK },
1496  { 13, TN(24), NULL, NULL, RED }
1497};
1498
1499static const test_node_description random_ops_tree_unique_28[] = {
1500  { 0, TN(5), NULL, NULL, BLACK },
1501  { 5, TN(13), TN(0), TN(7), RED },
1502  { 7, TN(5), NULL, NULL, BLACK },
1503  { 13, NULL, TN(5), TN(17), BLACK },
1504  { 15, TN(17), NULL, NULL, BLACK },
1505  { 17, TN(13), TN(15), TN(26), RED },
1506  { 21, TN(26), NULL, NULL, RED },
1507  { 26, TN(17), TN(21), NULL, BLACK }
1508};
1509
1510static const test_node_description random_ops_tree_multiple_28[] = {
1511  { 0, TN(5), NULL, NULL, BLACK },
1512  { 2, TN(13), TN(0), TN(7), RED },
1513  { 3, TN(5), NULL, NULL, BLACK },
1514  { 6, NULL, TN(5), TN(17), BLACK },
1515  { 7, TN(17), NULL, NULL, BLACK },
1516  { 8, TN(13), TN(15), TN(26), RED },
1517  { 10, TN(26), NULL, NULL, RED },
1518  { 13, TN(17), TN(21), NULL, BLACK }
1519};
1520
1521static const test_node_description random_ops_tree_unique_29[] = {
1522  { 0, TN(3), NULL, TN(1), BLACK },
1523  { 1, TN(0), NULL, NULL, RED },
1524  { 3, TN(12), TN(0), TN(6), BLACK },
1525  { 4, TN(6), NULL, NULL, BLACK },
1526  { 6, TN(3), TN(4), TN(8), RED },
1527  { 7, TN(8), NULL, NULL, RED },
1528  { 8, TN(6), TN(7), TN(11), BLACK },
1529  { 11, TN(8), NULL, NULL, RED },
1530  { 12, NULL, TN(3), TN(17), BLACK },
1531  { 13, TN(17), NULL, TN(14), BLACK },
1532  { 14, TN(13), NULL, NULL, RED },
1533  { 17, TN(12), TN(13), TN(25), BLACK },
1534  { 22, TN(25), NULL, NULL, RED },
1535  { 25, TN(17), TN(22), TN(27), BLACK },
1536  { 27, TN(25), NULL, NULL, RED }
1537};
1538
1539static const test_node_description random_ops_tree_multiple_29[] = {
1540  { 0, TN(3), NULL, TN(1), BLACK },
1541  { 0, TN(0), NULL, NULL, RED },
1542  { 1, TN(11), TN(0), TN(6), BLACK },
1543  { 2, TN(6), NULL, NULL, BLACK },
1544  { 3, TN(3), TN(4), TN(7), RED },
1545  { 3, TN(6), NULL, TN(8), BLACK },
1546  { 4, TN(7), NULL, NULL, RED },
1547  { 5, NULL, TN(3), TN(22), BLACK },
1548  { 6, TN(12), NULL, NULL, BLACK },
1549  { 6, TN(22), TN(13), TN(17), RED },
1550  { 7, TN(17), NULL, NULL, RED },
1551  { 8, TN(12), TN(14), NULL, BLACK },
1552  { 11, TN(11), TN(12), TN(25), BLACK },
1553  { 12, TN(22), NULL, TN(27), BLACK },
1554  { 13, TN(25), NULL, NULL, RED }
1555};
1556
1557static const test_node_description random_ops_tree_unique_30[] = {
1558  { 0, TN(4), NULL, NULL, RED },
1559  { 4, TN(6), TN(0), NULL, BLACK },
1560  { 6, TN(13), TN(4), TN(9), RED },
1561  { 8, TN(9), NULL, NULL, RED },
1562  { 9, TN(6), TN(8), TN(12), BLACK },
1563  { 12, TN(9), NULL, NULL, RED },
1564  { 13, NULL, TN(6), TN(18), BLACK },
1565  { 14, TN(16), NULL, NULL, RED },
1566  { 16, TN(18), TN(14), TN(17), BLACK },
1567  { 17, TN(16), NULL, NULL, RED },
1568  { 18, TN(13), TN(16), TN(27), RED },
1569  { 20, TN(27), NULL, NULL, RED },
1570  { 27, TN(18), TN(20), TN(28), BLACK },
1571  { 28, TN(27), NULL, NULL, RED }
1572};
1573
1574static const test_node_description random_ops_tree_multiple_30[] = {
1575  { 0, TN(4), NULL, NULL, BLACK },
1576  { 2, TN(13), TN(0), TN(9), RED },
1577  { 3, TN(9), NULL, NULL, RED },
1578  { 4, TN(4), TN(6), TN(8), BLACK },
1579  { 4, TN(9), NULL, NULL, RED },
1580  { 6, TN(14), TN(4), TN(12), BLACK },
1581  { 6, TN(13), NULL, NULL, BLACK },
1582  { 7, NULL, TN(13), TN(18), BLACK },
1583  { 8, TN(18), NULL, TN(16), BLACK },
1584  { 8, TN(17), NULL, NULL, RED },
1585  { 9, TN(14), TN(17), TN(27), BLACK },
1586  { 10, TN(27), NULL, NULL, RED },
1587  { 13, TN(18), TN(20), TN(28), BLACK },
1588  { 14, TN(27), NULL, NULL, RED }
1589};
1590
1591static const test_node_description random_ops_tree_unique_31[] = {
1592  { 0, TN(2), NULL, NULL, RED },
1593  { 2, TN(5), TN(0), NULL, BLACK },
1594  { 5, TN(11), TN(2), TN(9), BLACK },
1595  { 7, TN(9), NULL, NULL, RED },
1596  { 9, TN(5), TN(7), NULL, BLACK },
1597  { 11, NULL, TN(5), TN(21), BLACK },
1598  { 14, TN(16), NULL, NULL, RED },
1599  { 16, TN(21), TN(14), TN(18), BLACK },
1600  { 18, TN(16), NULL, NULL, RED },
1601  { 21, TN(11), TN(16), TN(30), BLACK },
1602  { 30, TN(21), NULL, NULL, BLACK }
1603};
1604
1605static const test_node_description random_ops_tree_multiple_31[] = {
1606  { 0, TN(2), NULL, NULL, RED },
1607  { 1, TN(5), TN(0), NULL, BLACK },
1608  { 2, TN(11), TN(2), TN(9), BLACK },
1609  { 3, TN(9), NULL, NULL, RED },
1610  { 4, TN(5), TN(7), NULL, BLACK },
1611  { 5, NULL, TN(5), TN(21), BLACK },
1612  { 7, TN(16), NULL, NULL, RED },
1613  { 8, TN(21), TN(14), TN(18), BLACK },
1614  { 9, TN(16), NULL, NULL, RED },
1615  { 10, TN(11), TN(16), TN(30), BLACK },
1616  { 15, TN(21), NULL, NULL, BLACK }
1617};
1618
1619#define RANDOM_OPS_TREE( i ) \
1620  { &random_ops_tree_multiple_ ## i[ 0 ], &random_ops_tree_unique_ ## i[ 0 ] }
1621
1622static const test_node_description *const random_ops_trees[][2] = {
1623  RANDOM_OPS_TREE( 1 ),
1624  RANDOM_OPS_TREE( 2 ),
1625  RANDOM_OPS_TREE( 3 ),
1626  RANDOM_OPS_TREE( 4 ),
1627  RANDOM_OPS_TREE( 5 ),
1628  RANDOM_OPS_TREE( 6 ),
1629  RANDOM_OPS_TREE( 7 ),
1630  RANDOM_OPS_TREE( 8 ),
1631  RANDOM_OPS_TREE( 9 ),
1632  RANDOM_OPS_TREE( 10 ),
1633  RANDOM_OPS_TREE( 11 ),
1634  RANDOM_OPS_TREE( 12 ),
1635  RANDOM_OPS_TREE( 13 ),
1636  RANDOM_OPS_TREE( 14 ),
1637  RANDOM_OPS_TREE( 15 ),
1638  RANDOM_OPS_TREE( 16 ),
1639  RANDOM_OPS_TREE( 17 ),
1640  RANDOM_OPS_TREE( 18 ),
1641  RANDOM_OPS_TREE( 19 ),
1642  RANDOM_OPS_TREE( 20 ),
1643  RANDOM_OPS_TREE( 21 ),
1644  RANDOM_OPS_TREE( 22 ),
1645  RANDOM_OPS_TREE( 23 ),
1646  RANDOM_OPS_TREE( 24 ),
1647  RANDOM_OPS_TREE( 25 ),
1648  RANDOM_OPS_TREE( 26 ),
1649  RANDOM_OPS_TREE( 27 ),
1650  RANDOM_OPS_TREE( 28 ),
1651  RANDOM_OPS_TREE( 29 ),
1652  RANDOM_OPS_TREE( 30 ),
1653  RANDOM_OPS_TREE( 31 )
1654};
1655
1656#define RANDOM_OPS_TREE_COUNT( i ) \
1657  { \
1658    RTEMS_ARRAY_SIZE( random_ops_tree_multiple_ ## i ), \
1659    RTEMS_ARRAY_SIZE( random_ops_tree_unique_ ## i ) \
1660  }
1661
1662static const size_t random_ops_tree_counts[][2] = {
1663  RANDOM_OPS_TREE_COUNT( 1 ),
1664  RANDOM_OPS_TREE_COUNT( 2 ),
1665  RANDOM_OPS_TREE_COUNT( 3 ),
1666  RANDOM_OPS_TREE_COUNT( 4 ),
1667  RANDOM_OPS_TREE_COUNT( 5 ),
1668  RANDOM_OPS_TREE_COUNT( 6 ),
1669  RANDOM_OPS_TREE_COUNT( 7 ),
1670  RANDOM_OPS_TREE_COUNT( 8 ),
1671  RANDOM_OPS_TREE_COUNT( 9 ),
1672  RANDOM_OPS_TREE_COUNT( 10 ),
1673  RANDOM_OPS_TREE_COUNT( 11 ),
1674  RANDOM_OPS_TREE_COUNT( 12 ),
1675  RANDOM_OPS_TREE_COUNT( 13 ),
1676  RANDOM_OPS_TREE_COUNT( 14 ),
1677  RANDOM_OPS_TREE_COUNT( 15 ),
1678  RANDOM_OPS_TREE_COUNT( 16 ),
1679  RANDOM_OPS_TREE_COUNT( 17 ),
1680  RANDOM_OPS_TREE_COUNT( 18 ),
1681  RANDOM_OPS_TREE_COUNT( 19 ),
1682  RANDOM_OPS_TREE_COUNT( 20 ),
1683  RANDOM_OPS_TREE_COUNT( 21 ),
1684  RANDOM_OPS_TREE_COUNT( 22 ),
1685  RANDOM_OPS_TREE_COUNT( 23 ),
1686  RANDOM_OPS_TREE_COUNT( 24 ),
1687  RANDOM_OPS_TREE_COUNT( 25 ),
1688  RANDOM_OPS_TREE_COUNT( 26 ),
1689  RANDOM_OPS_TREE_COUNT( 27 ),
1690  RANDOM_OPS_TREE_COUNT( 28 ),
1691  RANDOM_OPS_TREE_COUNT( 29 ),
1692  RANDOM_OPS_TREE_COUNT( 30 ),
1693  RANDOM_OPS_TREE_COUNT( 31 )
1694};
1695
1696static uint32_t simple_random( uint32_t v )
1697{
1698  v *= 1664525;
1699  v += 1013904223;
1700
1701  return v;
1702}
1703
1704static void random_ops( size_t n, bool unique )
1705{
1706  visitor_context ctx = {
1707    0,
1708    random_ops_tree_counts[ n - 1 ][ unique ],
1709    random_ops_trees[ n - 1 ][ unique ]
1710  };
1711  rtems_rbtree_control tree;
1712  test_node *nodes = &node_array[ 0 ];
1713  size_t m = n * n * n;
1714  size_t s = unique ? 1 : 2;
1715  uint32_t v = 0xdeadbeef;
1716  size_t i;
1717
1718  rtems_rbtree_initialize_empty( &tree );
1719
1720  memset( nodes, 0, n * sizeof( *nodes ) );
1721
1722  for ( i = 0; i < n; ++i ) {
1723    nodes[ i ].key = (int) ( i / s );
1724  }
1725
1726  for ( i = 0; i < m; ++i ) {
1727    size_t j = ( v >> 13 ) % n;
1728    test_node *tn = &nodes[ j ];
1729
1730    if ( tn->id == 0 ) {
1731      tn->id = 1;
1732      rtems_rbtree_insert( &tree, &tn->Node, test_compare_function, unique );
1733    } else {
1734      tn->id = 0;
1735      rtems_rbtree_extract( &tree, &tn->Node );
1736    }
1737
1738    rtems_test_assert( rb_assert( rtems_rbtree_root( &tree ) ) != -1 );
1739
1740    v = simple_random( v );
1741  }
1742
1743  _RBTree_Iterate( &tree, visit_nodes, &ctx );
1744  rtems_test_assert( ctx.current == ctx.count );
1745}
1746
1747static void test_rbtree_random_ops( void )
1748{
1749  size_t n;
1750
1751  puts( "INIT - Random operations" );
1752
1753  for ( n = 0; n < RTEMS_ARRAY_SIZE( random_ops_trees ); ++n ) {
1754    random_ops( n + 1, true );
1755    random_ops( n + 1, false );
1756  }
1757}
1758
1759typedef struct {
1760  rtems_rbtree_node *parent;
1761  rtems_rbtree_node *left;
1762  rtems_rbtree_node *right;
1763} postorder_node_description;
1764
1765static const postorder_node_description postorder_tree_1[] = {
1766  { NULL, NULL, NULL }
1767};
1768
1769/*
1770 *   TN_1
1771 *   /
1772 * TN_0
1773 */
1774static const postorder_node_description postorder_tree_2[] = {
1775  { TN( 1 ), NULL, NULL },
1776  { NULL, TN( 0 ), NULL }
1777};
1778
1779/*
1780 * TN_1
1781 *     \
1782 *    TN_0
1783 */
1784static const postorder_node_description postorder_tree_3[] = {
1785  { TN( 1 ), NULL, NULL },
1786  { NULL, NULL, TN( 0 ) }
1787};
1788
1789/*
1790 *    TN_2
1791 *   /    \
1792 * TN_0  TN_1
1793 */
1794static const postorder_node_description postorder_tree_4[] = {
1795  { TN( 2 ), NULL, NULL },
1796  { TN( 2 ), NULL, NULL },
1797  { NULL, TN( 0 ), TN( 1 ) }
1798};
1799
1800/*
1801 *       TN_3
1802 *      /
1803 *    TN_2
1804 *   /    \
1805 * TN_0  TN_1
1806 */
1807static const postorder_node_description postorder_tree_5[] = {
1808  { TN( 2 ), NULL, NULL },
1809  { TN( 2 ), NULL, NULL },
1810  { TN( 3 ), TN( 0 ), TN( 1 ) },
1811  { NULL, TN( 2 ), NULL }
1812};
1813
1814/*
1815 *      TN_10
1816 *     /      \
1817 *    TN_6     TN_9
1818 *   /    \        \
1819 * TN_0  TN_5       TN_8
1820 *      /    \      /
1821 *    TN_2   TN_4  TN_7
1822 *   /      /
1823 * TN_1   TN_3
1824 */
1825static const postorder_node_description postorder_tree_6[] = {
1826  { TN( 6 ), NULL, NULL },
1827  { TN( 2 ), NULL, NULL },
1828  { TN( 5 ), TN( 1 ), NULL },
1829  { TN( 4 ), NULL, NULL },
1830  { TN( 5 ), TN( 3 ), NULL },
1831  { TN( 6 ), TN( 2 ), TN( 4 ) },
1832  { TN( 10 ), TN( 0 ), TN( 5 ) },
1833  { TN( 8 ), NULL, NULL },
1834  { TN( 9 ), TN( 7 ), NULL },
1835  { TN( 10 ), NULL, TN( 8 ) },
1836  { NULL, TN( 6 ), TN( 9 ) }
1837};
1838
1839/*
1840 *      TN_5
1841 *     /
1842 *    TN_4
1843 *   /
1844 * TN_3
1845 *     \
1846 *    TN_2
1847 *        \
1848 *       TN_1
1849 *      /
1850 *    TN_0
1851 */
1852static const postorder_node_description postorder_tree_7[] = {
1853  { TN( 1 ), NULL, NULL },
1854  { TN( 2 ), TN( 0 ), NULL },
1855  { TN( 3 ), NULL, TN( 1 ) },
1856  { TN( 4 ), NULL, TN( 2 ) },
1857  { TN( 5 ), TN( 3 ), NULL },
1858  { NULL, TN( 0 ), NULL }
1859};
1860
1861typedef struct {
1862  const postorder_node_description *tree;
1863  size_t                            node_count;
1864} postorder_tree;
1865
1866#define POSTORDER_TREE( idx ) \
1867  { postorder_tree_##idx, RTEMS_ARRAY_SIZE( postorder_tree_##idx ) }
1868
1869static const postorder_tree postorder_trees[] = {
1870  { NULL, 0 },
1871  POSTORDER_TREE( 1 ),
1872  POSTORDER_TREE( 2 ),
1873  POSTORDER_TREE( 3 ),
1874  POSTORDER_TREE( 4 ),
1875  POSTORDER_TREE( 5 ),
1876  POSTORDER_TREE( 6 ),
1877  POSTORDER_TREE( 7 )
1878};
1879
1880static void postorder_tree_init(
1881  RBTree_Control       *tree,
1882  const postorder_tree *pt
1883)
1884{
1885  size_t i;
1886
1887  memset( node_array, 0, pt->node_count * sizeof( node_array[ 0 ] ) );
1888
1889  if ( pt->node_count > 0 ) {
1890    _RBTree_Initialize_node( TN( 0 ) );
1891    _RBTree_Initialize_one( tree, TN( 0 ) );
1892  } else {
1893    _RBTree_Initialize_empty( tree );
1894  }
1895
1896  for ( i = 0; i < pt->node_count; ++i ) {
1897    const postorder_node_description *pnd;
1898
1899    pnd = &pt->tree[ i ];
1900    RB_PARENT( TN( i ), Node) = pnd->parent;
1901    RB_LEFT( TN( i ), Node) = pnd->left;
1902    RB_RIGHT( TN( i ), Node) = pnd->right;
1903  }
1904}
1905
1906static void postorder_tree_check(
1907  RBTree_Control       *tree,
1908  const postorder_tree *pt
1909)
1910{
1911  test_node *node;
1912  size_t i;
1913
1914  node = _RBTree_Postorder_first( tree, offsetof( test_node, Node ) );
1915
1916  for ( i = 0; i < pt->node_count; ++i ) {
1917    rtems_test_assert( node == &node_array[ i ] );
1918    node = _RBTree_Postorder_next( &node->Node, offsetof( test_node, Node ) );
1919  }
1920
1921  rtems_test_assert( node == NULL );
1922}
1923
1924static void test_rbtree_postorder( void )
1925{
1926  RBTree_Control tree;
1927  size_t         i;
1928
1929  puts( "INIT - Postorder operations" );
1930
1931  for ( i = 0; i < RTEMS_ARRAY_SIZE( postorder_trees ); ++i ) {
1932    const postorder_tree *pt;
1933
1934    pt = &postorder_trees[ i ];
1935    postorder_tree_init( &tree, pt );
1936    postorder_tree_check( &tree, pt );
1937  }
1938}
1939
1940rtems_task Init( rtems_task_argument ignored )
1941{
1942  rtems_rbtree_control  rbtree1;
1943  rtems_rbtree_node    *p;
1944  test_node            node1, node2;
1945  test_node            search_node;
1946  int                  id;
1947  int i;
1948
1949  TEST_BEGIN();
1950
1951  puts( "Init - Initialize rbtree empty" );
1952  rtems_rbtree_initialize_empty( &rbtree1 );
1953
1954  rtems_rbtree_set_off_tree( &node1.Node );
1955  rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) );
1956
1957  /* verify that the rbtree insert work */
1958  puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
1959  node1.id = 1;
1960  node1.key = 1;
1961  node2.id = 2;
1962  node2.key = 2;
1963  rb_insert_unique( &rbtree1, &node1.Node );
1964  rb_insert_unique( &rbtree1, &node2.Node );
1965
1966  rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
1967
1968  if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1969    puts( "INIT - FAILED TREE CHECK" );
1970
1971  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
1972      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1973    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1974    if ( id > 2 ) {
1975      puts( "INIT - TOO MANY NODES ON RBTREE" );
1976      rtems_test_exit(0);
1977    }
1978    if ( t->id != id ) {
1979      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1980      rtems_test_exit(0);
1981    }
1982
1983    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1984      puts( "INIT - FAILED TREE CHECK" );
1985  }
1986  if (id < 2) {
1987    puts("INIT - NOT ENOUGH NODES ON RBTREE");
1988    rtems_test_exit(0);
1989  }
1990
1991  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
1992  node2.key = node1.key;
1993  rb_insert_unique(&rbtree1, &node1.Node);
1994  p = rb_insert_unique(&rbtree1, &node2.Node);
1995
1996  if (p != &node1.Node)
1997    puts( "INIT - FAILED DUPLICATE INSERT" );
1998
1999  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
2000      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2001    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2002    if ( id > 1 ) {
2003      puts( "INIT - TOO MANY NODES ON RBTREE" );
2004      rtems_test_exit(0);
2005    }
2006    if ( t->id != id ) {
2007      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2008      rtems_test_exit(0);
2009    }
2010
2011    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2012      puts( "INIT - FAILED TREE CHECK" );
2013  }
2014  if (id < 1) {
2015    puts("INIT - NOT ENOUGH NODES ON RBTREE");
2016    rtems_test_exit(0);
2017  }
2018  node2.key = 2;
2019
2020  /* verify that the rbtree is empty */
2021  puts( "INIT - Verify rtems_rbtree_is_empty" );
2022  if(!rtems_rbtree_is_empty(&rbtree1)) {
2023    puts( "INIT - TREE NOT EMPTY" );
2024    rtems_test_exit(0);
2025  }
2026
2027  puts( "INIT - Verify rtems_XXX on an empty tree" );
2028  if(rtems_rbtree_get_min(&rbtree1)) {
2029    puts("INIT - get_min on empty returned non-NULL");
2030    rtems_test_exit(0);
2031  }
2032  if(rtems_rbtree_get_max(&rbtree1)) {
2033    puts("INIT - get_max on empty returned non-NULL");
2034    rtems_test_exit(0);
2035  }
2036  if(rtems_rbtree_peek_min(&rbtree1)) {
2037    puts("INIT - peek_min on empty returned non-NULL");
2038    rtems_test_exit(0);
2039  }
2040  if(rtems_rbtree_peek_max(&rbtree1)) {
2041    puts("INIT - peek_max on empty returned non-NULL");
2042    rtems_test_exit(0);
2043  }
2044
2045
2046  /* verify that the rbtree insert works after a tree is emptied */
2047  puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
2048  node1.id = 2;
2049  node1.key = 2;
2050  node2.id = 1;
2051  node2.key = 1;
2052  rb_insert_unique( &rbtree1, &node1.Node );
2053  rb_insert_unique( &rbtree1, &node2.Node );
2054
2055  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
2056  test_node *t1 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_max(&rbtree1),
2057         test_node,Node);
2058  test_node *t2 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_min(&rbtree1),
2059         test_node,Node);
2060  if (t1->key - t2->key != 1) {
2061    puts( "INIT - Peek Min - Max failed" );
2062    rtems_test_exit(0);
2063  }
2064  p = rtems_rbtree_peek_max(&rbtree1);
2065  rtems_rbtree_extract(&rbtree1, p);
2066  t1 = RTEMS_CONTAINER_OF(p,test_node,Node);
2067  if (t1->key != 2) {
2068    puts( "INIT - rtems_rbtree_extract failed");
2069    rtems_test_exit(0);
2070  }
2071  rb_insert_unique(&rbtree1, p);
2072
2073  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
2074      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2075    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2076    if ( id > 2 ) {
2077      puts( "INIT - TOO MANY NODES ON RBTREE" );
2078      rtems_test_exit(0);
2079    }
2080    if ( t->id != id ) {
2081      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2082      rtems_test_exit(0);
2083    }
2084  }
2085 
2086  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
2087  for (i = 0; i < 100; i++) {
2088    node_array[i].id = i;
2089    node_array[i].key = i;
2090    rb_insert_unique( &rbtree1, &node_array[i].Node );
2091
2092    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2093      puts( "INIT - FAILED TREE CHECK" );
2094  }
2095
2096  puts( "INIT - Removing 100 nodes" );
2097
2098  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2099      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2100    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2101    if ( id > 99 ) {
2102      puts( "INIT - TOO MANY NODES ON RBTREE" );
2103      rtems_test_exit(0);
2104    }
2105    if ( t->id != id ) {
2106      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2107      rtems_test_exit(0);
2108    }
2109
2110    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2111      puts( "INIT - FAILED TREE CHECK" );
2112  }
2113 
2114  if(!rtems_rbtree_is_empty(&rbtree1)) {
2115    puts( "INIT - TREE NOT EMPTY" );
2116    rtems_test_exit(0);
2117  }
2118
2119  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
2120  for (i = 0; i < 100; i++) {
2121    node_array[i].id = 99-i;
2122    node_array[i].key = 99-i;
2123    rb_insert_unique( &rbtree1, &node_array[i].Node );
2124
2125    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2126      puts( "INIT - FAILED TREE CHECK" );
2127  }
2128
2129  puts( "INIT - Removing 100 nodes" );
2130
2131  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2132      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2133    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2134    if ( id > 99 ) {
2135      puts( "INIT - TOO MANY NODES ON RBTREE" );
2136      rtems_test_exit(0);
2137    }
2138    if ( t->id != id ) {
2139      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2140      rtems_test_exit(0);
2141    }
2142
2143    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2144      puts( "INIT - FAILED TREE CHECK" );
2145  }
2146
2147  if(!rtems_rbtree_is_empty(&rbtree1)) {
2148    puts( "INIT - TREE NOT EMPTY" );
2149    rtems_test_exit(0);
2150  }
2151
2152  /* testing rbtree_extract by adding 100 nodes then removing the 20 with
2153   * keys specified by the numbers array, then removing the rest */
2154  puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
2155  for (i = 0; i < 100; i++) {
2156    node_array[i].id = i;
2157    node_array[i].key = i;
2158    rb_insert_unique( &rbtree1, &node_array[i].Node );
2159
2160    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2161      puts( "INIT - FAILED TREE CHECK" );
2162  }
2163
2164  puts( "INIT - Extracting 20 random nodes" );
2165
2166  for (i = 0; i < 20; i++) {
2167    id = numbers[i];
2168    rtems_rbtree_extract( &rbtree1, &node_array[id].Node );
2169    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2170      puts( "INIT - FAILED TREE CHECK" );
2171  }
2172
2173  puts( "INIT - Removing 80 nodes" );
2174
2175  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ;
2176      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2177    test_node *t = RTEMS_CONTAINER_OF(p, test_node, Node);
2178
2179    while ( id == numbers_sorted[i] ) {
2180      /* skip if expected minimum (id) is in the set of extracted numbers */
2181      id++;
2182      i++;
2183    }
2184
2185    if ( id > 99 ) {
2186      puts( "INIT - TOO MANY NODES ON RBTREE" );
2187      rtems_test_exit(0);
2188    }
2189
2190    if ( t->id != id ) {
2191      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2192      rtems_test_exit(0);
2193    }
2194
2195    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2196      puts( "INIT - FAILED TREE CHECK" );
2197  }
2198
2199  if(!rtems_rbtree_is_empty(&rbtree1)) {
2200    puts( "INIT - TREE NOT EMPTY" );
2201    rtems_test_exit(0);
2202  }
2203
2204  /* Additional rtems_rbtree_extract test which removes a node
2205   * with two children while target node has a left child only. */
2206  for ( i = 0; i < 7; i++ ) {
2207    node_array[i].id = i;
2208    node_array[i].key = i;
2209  }
2210  rb_insert_unique( &rbtree1, &node_array[3].Node );
2211  rb_insert_unique( &rbtree1, &node_array[1].Node );
2212  rb_insert_unique( &rbtree1, &node_array[5].Node );
2213  rb_insert_unique( &rbtree1, &node_array[0].Node );
2214  rb_insert_unique( &rbtree1, &node_array[2].Node );
2215  rb_insert_unique( &rbtree1, &node_array[4].Node );
2216  rb_insert_unique( &rbtree1, &node_array[6].Node );
2217  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
2218  /* node_array[1] has now only a left child. */
2219  if ( !rtems_rbtree_left( &node_array[1].Node ) ||
2220        rtems_rbtree_right( &node_array[1].Node ) )
2221     puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
2222  rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
2223  while( (p = rtems_rbtree_get_max(&rbtree1)) );
2224
2225  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
2226  for (i = 0; i < 100; i++) {
2227    node_array[i].id = 99-i;
2228    node_array[i].key = 99-i;
2229    rb_insert_unique( &rbtree1, &node_array[i].Node );
2230
2231    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2232      puts( "INIT - FAILED TREE CHECK" );
2233  }
2234
2235  puts( "INIT - Removing 100 nodes" );
2236
2237  for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
2238      p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
2239    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2240    if ( id > 99 ) {
2241      puts( "INIT - TOO MANY NODES ON RBTREE" );
2242      rtems_test_exit(0);
2243    }
2244    if ( t->id != 99-id ) {
2245      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2246      rtems_test_exit(0);
2247    }
2248
2249    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2250      puts( "INIT - FAILED TREE CHECK" );
2251  }
2252
2253  if(!rtems_rbtree_is_empty(&rbtree1)) {
2254    puts( "INIT - TREE NOT EMPTY" );
2255    rtems_test_exit(0);
2256  }
2257
2258  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
2259  for (i = 0; i < 100; i++) {
2260    node_array[i].id = i;
2261    node_array[i].key = i;
2262    rb_insert_unique( &rbtree1, &node_array[i].Node );
2263
2264    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2265      puts( "INIT - FAILED TREE CHECK" );
2266  }
2267
2268  puts( "INIT - Verify rtems_rbtree_find" );
2269  search_node.key = 30;
2270  p = rb_find_unique(&rbtree1, &search_node.Node);
2271  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 30) {
2272    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2273    rtems_test_exit(0);
2274  }
2275
2276  puts( "INIT - Verify rtems_rbtree_predecessor/successor");
2277  p = rtems_rbtree_predecessor(p);
2278  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 29) {
2279    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2280    rtems_test_exit(0);
2281  }
2282  p = rb_find_unique(&rbtree1, &search_node.Node);
2283  p = rtems_rbtree_successor(p);
2284  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 31) {
2285    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2286    rtems_test_exit(0);
2287  }
2288
2289  if ( rb_color( rtems_rbtree_root(&rbtree1) ) != BLACK )
2290    puts ( "INIT - ERROR ON RBTREE ROOT IS BLACK MISMATCH" );
2291
2292  puts( "INIT - Removing 100 nodes" );
2293
2294  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
2295      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
2296    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2297    if ( id < 0 ) {
2298      puts( "INIT - TOO MANY NODES ON RBTREE" );
2299      rtems_test_exit(0);
2300    }
2301    if ( t->id != id ) {
2302      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2303      rtems_test_exit(0);
2304    }
2305
2306    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2307      puts( "INIT - FAILED TREE CHECK" );
2308  }
2309
2310  if(!rtems_rbtree_is_empty(&rbtree1)) {
2311    puts( "INIT - TREE NOT EMPTY" );
2312    rtems_test_exit(0);
2313  }
2314
2315  puts("INIT - Insert 20 random numbers");
2316  for (i = 0; i < 20; i++) {
2317    visitor_context ctx = { 0, i + 1, test_insert_trees[ i ] };
2318
2319    node_array[i].id = numbers[i];
2320    node_array[i].key = numbers[i];
2321    rb_insert_unique( &rbtree1, &node_array[i].Node );
2322
2323    _RBTree_Iterate( &rbtree1, visit_nodes, &ctx );
2324    rtems_test_assert( ctx.current == ctx.count );
2325
2326    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2327      puts( "INIT - FAILED TREE CHECK" );
2328  }
2329
2330  puts( "INIT - Removing 20 nodes" );
2331
2332  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2333      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2334    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2335    if ( id > 19 ) {
2336      puts( "INIT - TOO MANY NODES ON RBTREE" );
2337      rtems_test_exit(0);
2338    }
2339    if ( t->id != numbers_sorted[id] ) {
2340      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2341      rtems_test_exit(0);
2342    }
2343
2344    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2345      puts( "INIT - FAILED TREE CHECK" );
2346
2347    if ( id < 19 ) {
2348      visitor_context ctx = { 0, 20 - id - 1, test_remove_trees[ id ] };
2349
2350      _RBTree_Iterate( &rbtree1, visit_nodes, &ctx );
2351      rtems_test_assert( ctx.current == ctx.count );
2352    }
2353  }
2354
2355  if(!rtems_rbtree_is_empty(&rbtree1)) {
2356    puts( "INIT - TREE NOT EMPTY" );
2357    rtems_test_exit(0);
2358  }
2359
2360  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
2361  for (i = 0; i < 100; i++) {
2362    node_array[i].id = i;
2363    node_array[i].key = i;
2364  }
2365  rtems_rbtree_initialize( &rbtree1, &test_compare_function,
2366                           &node_array[0].Node, 100,
2367                           sizeof(test_node), true );
2368
2369  puts( "INIT - Removing 100 nodes" );
2370
2371  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2372      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2373    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2374    if ( id > 99 ) {
2375      puts( "INIT - TOO MANY NODES ON RBTREE" );
2376      rtems_test_exit(0);
2377    }
2378
2379    if ( t->id != id ) {
2380      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2381      rtems_test_exit(0);
2382    }
2383
2384    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2385      puts( "INIT - FAILED TREE CHECK" );
2386  }
2387
2388  if(!rtems_rbtree_is_empty(&rbtree1)) {
2389    puts( "INIT - TREE NOT EMPTY" );
2390    rtems_test_exit(0);
2391  }
2392
2393  /* Initialize the tree for duplicate keys */
2394  puts( "Init - Initialize duplicate rbtree empty" );
2395  rtems_rbtree_initialize_empty( &rbtree1 );
2396
2397  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
2398  for (i = 0; i < 100; i++) {
2399    node_array[i].id = i;
2400    node_array[i].key = i%5;
2401    rb_insert_multi( &rbtree1, &node_array[i].Node );
2402
2403    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2404      puts( "INIT - FAILED TREE CHECK" );
2405  }
2406
2407  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
2408  search_node.key = 2;
2409  p = rb_find_multi(&rbtree1, &search_node.Node);
2410  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 2) {
2411    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2412    rtems_test_exit(0);
2413  }
2414
2415  puts( "INIT - Removing 100 nodes" );
2416
2417  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2418      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2419    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2420    if ( id > 99 ) {
2421      puts( "INIT - TOO MANY NODES ON RBTREE" );
2422      rtems_test_exit(0);
2423    }
2424    if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
2425      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2426      rtems_test_exit(0);
2427    }
2428
2429    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2430      puts( "INIT - FAILED TREE CHECK" );
2431  }
2432
2433  if(!rtems_rbtree_is_empty(&rbtree1)) {
2434    puts( "INIT - TREE NOT EMPTY" );
2435    rtems_test_exit(0);
2436  }
2437
2438  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
2439  for (i = 0; i < 100; i++) {
2440    node_array[i].id = 99-i;
2441    node_array[i].key = (99-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 != 97) {
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 != ( (((99-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  test_rbtree_postorder();
2480  test_rbtree_init_one();
2481  test_rbtree_min_max();
2482  test_rbtree_insert_inline();
2483  test_rbtree_random_ops();
2484
2485  TEST_END();
2486  rtems_test_exit(0);
2487}
2488
2489/* configuration information */
2490
2491#define CONFIGURE_APPLICATION_NEEDS_SIMPLE_CONSOLE_DRIVER
2492#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
2493
2494#define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION
2495
2496#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
2497#define CONFIGURE_MAXIMUM_TASKS 1
2498
2499#define CONFIGURE_INIT
2500#include <rtems/confdefs.h>
2501
2502/* global variables */
Note: See TracBrowser for help on using the repository browser.