source: rtems/testsuites/sptests/sprbtree01/init.c @ ac28f15

5
Last change on this file since ac28f15 was af43554, checked in by Sebastian Huber <sebastian.huber@…>, on 10/26/17 at 11:59:11

tests: Remove TEST_INIT

The TEST_EXTERN is a used only by the system.h style tests and they use
CONFIGURE_INIT appropriately.

Update #3170.
Update #3199.
  • Property mode set to 100644
File size: 70.1 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
1759rtems_task Init( rtems_task_argument ignored )
1760{
1761  rtems_rbtree_control  rbtree1;
1762  rtems_rbtree_node    *p;
1763  test_node            node1, node2;
1764  test_node            search_node;
1765  int                  id;
1766  int i;
1767
1768  TEST_BEGIN();
1769
1770  puts( "Init - Initialize rbtree empty" );
1771  rtems_rbtree_initialize_empty( &rbtree1 );
1772
1773  rtems_rbtree_set_off_tree( &node1.Node );
1774  rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) );
1775
1776  /* verify that the rbtree insert work */
1777  puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
1778  node1.id = 1;
1779  node1.key = 1;
1780  node2.id = 2;
1781  node2.key = 2;
1782  rb_insert_unique( &rbtree1, &node1.Node );
1783  rb_insert_unique( &rbtree1, &node2.Node );
1784
1785  rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
1786
1787  if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1788    puts( "INIT - FAILED TREE CHECK" );
1789
1790  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
1791      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1792    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1793    if ( id > 2 ) {
1794      puts( "INIT - TOO MANY NODES ON RBTREE" );
1795      rtems_test_exit(0);
1796    }
1797    if ( t->id != id ) {
1798      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1799      rtems_test_exit(0);
1800    }
1801
1802    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1803      puts( "INIT - FAILED TREE CHECK" );
1804  }
1805  if (id < 2) {
1806    puts("INIT - NOT ENOUGH NODES ON RBTREE");
1807    rtems_test_exit(0);
1808  }
1809
1810  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
1811  node2.key = node1.key;
1812  rb_insert_unique(&rbtree1, &node1.Node);
1813  p = rb_insert_unique(&rbtree1, &node2.Node);
1814
1815  if (p != &node1.Node)
1816    puts( "INIT - FAILED DUPLICATE INSERT" );
1817
1818  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
1819      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1820    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1821    if ( id > 1 ) {
1822      puts( "INIT - TOO MANY NODES ON RBTREE" );
1823      rtems_test_exit(0);
1824    }
1825    if ( t->id != id ) {
1826      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1827      rtems_test_exit(0);
1828    }
1829
1830    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1831      puts( "INIT - FAILED TREE CHECK" );
1832  }
1833  if (id < 1) {
1834    puts("INIT - NOT ENOUGH NODES ON RBTREE");
1835    rtems_test_exit(0);
1836  }
1837  node2.key = 2;
1838
1839  /* verify that the rbtree is empty */
1840  puts( "INIT - Verify rtems_rbtree_is_empty" );
1841  if(!rtems_rbtree_is_empty(&rbtree1)) {
1842    puts( "INIT - TREE NOT EMPTY" );
1843    rtems_test_exit(0);
1844  }
1845
1846  puts( "INIT - Verify rtems_XXX on an empty tree" );
1847  if(rtems_rbtree_get_min(&rbtree1)) {
1848    puts("INIT - get_min on empty returned non-NULL");
1849    rtems_test_exit(0);
1850  }
1851  if(rtems_rbtree_get_max(&rbtree1)) {
1852    puts("INIT - get_max on empty returned non-NULL");
1853    rtems_test_exit(0);
1854  }
1855  if(rtems_rbtree_peek_min(&rbtree1)) {
1856    puts("INIT - peek_min on empty returned non-NULL");
1857    rtems_test_exit(0);
1858  }
1859  if(rtems_rbtree_peek_max(&rbtree1)) {
1860    puts("INIT - peek_max on empty returned non-NULL");
1861    rtems_test_exit(0);
1862  }
1863
1864
1865  /* verify that the rbtree insert works after a tree is emptied */
1866  puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
1867  node1.id = 2;
1868  node1.key = 2;
1869  node2.id = 1;
1870  node2.key = 1;
1871  rb_insert_unique( &rbtree1, &node1.Node );
1872  rb_insert_unique( &rbtree1, &node2.Node );
1873
1874  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
1875  test_node *t1 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_max(&rbtree1),
1876         test_node,Node);
1877  test_node *t2 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_min(&rbtree1),
1878         test_node,Node);
1879  if (t1->key - t2->key != 1) {
1880    puts( "INIT - Peek Min - Max failed" );
1881    rtems_test_exit(0);
1882  }
1883  p = rtems_rbtree_peek_max(&rbtree1);
1884  rtems_rbtree_extract(&rbtree1, p);
1885  t1 = RTEMS_CONTAINER_OF(p,test_node,Node);
1886  if (t1->key != 2) {
1887    puts( "INIT - rtems_rbtree_extract failed");
1888    rtems_test_exit(0);
1889  }
1890  rb_insert_unique(&rbtree1, p);
1891
1892  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
1893      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1894    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1895    if ( id > 2 ) {
1896      puts( "INIT - TOO MANY NODES ON RBTREE" );
1897      rtems_test_exit(0);
1898    }
1899    if ( t->id != id ) {
1900      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1901      rtems_test_exit(0);
1902    }
1903  }
1904 
1905  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
1906  for (i = 0; i < 100; i++) {
1907    node_array[i].id = i;
1908    node_array[i].key = i;
1909    rb_insert_unique( &rbtree1, &node_array[i].Node );
1910
1911    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1912      puts( "INIT - FAILED TREE CHECK" );
1913  }
1914
1915  puts( "INIT - Removing 100 nodes" );
1916
1917  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1918      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1919    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1920    if ( id > 99 ) {
1921      puts( "INIT - TOO MANY NODES ON RBTREE" );
1922      rtems_test_exit(0);
1923    }
1924    if ( t->id != id ) {
1925      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1926      rtems_test_exit(0);
1927    }
1928
1929    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1930      puts( "INIT - FAILED TREE CHECK" );
1931  }
1932 
1933  if(!rtems_rbtree_is_empty(&rbtree1)) {
1934    puts( "INIT - TREE NOT EMPTY" );
1935    rtems_test_exit(0);
1936  }
1937
1938  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
1939  for (i = 0; i < 100; i++) {
1940    node_array[i].id = 99-i;
1941    node_array[i].key = 99-i;
1942    rb_insert_unique( &rbtree1, &node_array[i].Node );
1943
1944    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1945      puts( "INIT - FAILED TREE CHECK" );
1946  }
1947
1948  puts( "INIT - Removing 100 nodes" );
1949
1950  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1951      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1952    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1953    if ( id > 99 ) {
1954      puts( "INIT - TOO MANY NODES ON RBTREE" );
1955      rtems_test_exit(0);
1956    }
1957    if ( t->id != id ) {
1958      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1959      rtems_test_exit(0);
1960    }
1961
1962    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1963      puts( "INIT - FAILED TREE CHECK" );
1964  }
1965
1966  if(!rtems_rbtree_is_empty(&rbtree1)) {
1967    puts( "INIT - TREE NOT EMPTY" );
1968    rtems_test_exit(0);
1969  }
1970
1971  /* testing rbtree_extract by adding 100 nodes then removing the 20 with
1972   * keys specified by the numbers array, then removing the rest */
1973  puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
1974  for (i = 0; i < 100; i++) {
1975    node_array[i].id = i;
1976    node_array[i].key = i;
1977    rb_insert_unique( &rbtree1, &node_array[i].Node );
1978
1979    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1980      puts( "INIT - FAILED TREE CHECK" );
1981  }
1982
1983  puts( "INIT - Extracting 20 random nodes" );
1984
1985  for (i = 0; i < 20; i++) {
1986    id = numbers[i];
1987    rtems_rbtree_extract( &rbtree1, &node_array[id].Node );
1988    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
1989      puts( "INIT - FAILED TREE CHECK" );
1990  }
1991
1992  puts( "INIT - Removing 80 nodes" );
1993
1994  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ;
1995      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1996    test_node *t = RTEMS_CONTAINER_OF(p, test_node, Node);
1997
1998    while ( id == numbers_sorted[i] ) {
1999      /* skip if expected minimum (id) is in the set of extracted numbers */
2000      id++;
2001      i++;
2002    }
2003
2004    if ( id > 99 ) {
2005      puts( "INIT - TOO MANY NODES ON RBTREE" );
2006      rtems_test_exit(0);
2007    }
2008
2009    if ( t->id != id ) {
2010      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2011      rtems_test_exit(0);
2012    }
2013
2014    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2015      puts( "INIT - FAILED TREE CHECK" );
2016  }
2017
2018  if(!rtems_rbtree_is_empty(&rbtree1)) {
2019    puts( "INIT - TREE NOT EMPTY" );
2020    rtems_test_exit(0);
2021  }
2022
2023  /* Additional rtems_rbtree_extract test which removes a node
2024   * with two children while target node has a left child only. */
2025  for ( i = 0; i < 7; i++ ) {
2026    node_array[i].id = i;
2027    node_array[i].key = i;
2028  }
2029  rb_insert_unique( &rbtree1, &node_array[3].Node );
2030  rb_insert_unique( &rbtree1, &node_array[1].Node );
2031  rb_insert_unique( &rbtree1, &node_array[5].Node );
2032  rb_insert_unique( &rbtree1, &node_array[0].Node );
2033  rb_insert_unique( &rbtree1, &node_array[2].Node );
2034  rb_insert_unique( &rbtree1, &node_array[4].Node );
2035  rb_insert_unique( &rbtree1, &node_array[6].Node );
2036  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
2037  /* node_array[1] has now only a left child. */
2038  if ( !rtems_rbtree_left( &node_array[1].Node ) ||
2039        rtems_rbtree_right( &node_array[1].Node ) )
2040     puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
2041  rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
2042  while( (p = rtems_rbtree_get_max(&rbtree1)) );
2043
2044  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
2045  for (i = 0; i < 100; i++) {
2046    node_array[i].id = 99-i;
2047    node_array[i].key = 99-i;
2048    rb_insert_unique( &rbtree1, &node_array[i].Node );
2049
2050    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2051      puts( "INIT - FAILED TREE CHECK" );
2052  }
2053
2054  puts( "INIT - Removing 100 nodes" );
2055
2056  for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
2057      p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
2058    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2059    if ( id > 99 ) {
2060      puts( "INIT - TOO MANY NODES ON RBTREE" );
2061      rtems_test_exit(0);
2062    }
2063    if ( t->id != 99-id ) {
2064      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2065      rtems_test_exit(0);
2066    }
2067
2068    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2069      puts( "INIT - FAILED TREE CHECK" );
2070  }
2071
2072  if(!rtems_rbtree_is_empty(&rbtree1)) {
2073    puts( "INIT - TREE NOT EMPTY" );
2074    rtems_test_exit(0);
2075  }
2076
2077  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
2078  for (i = 0; i < 100; i++) {
2079    node_array[i].id = i;
2080    node_array[i].key = i;
2081    rb_insert_unique( &rbtree1, &node_array[i].Node );
2082
2083    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2084      puts( "INIT - FAILED TREE CHECK" );
2085  }
2086
2087  puts( "INIT - Verify rtems_rbtree_find" );
2088  search_node.key = 30;
2089  p = rb_find_unique(&rbtree1, &search_node.Node);
2090  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 30) {
2091    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2092    rtems_test_exit(0);
2093  }
2094
2095  puts( "INIT - Verify rtems_rbtree_predecessor/successor");
2096  p = rtems_rbtree_predecessor(p);
2097  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 29) {
2098    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2099    rtems_test_exit(0);
2100  }
2101  p = rb_find_unique(&rbtree1, &search_node.Node);
2102  p = rtems_rbtree_successor(p);
2103  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 31) {
2104    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2105    rtems_test_exit(0);
2106  }
2107
2108  if ( rb_color( rtems_rbtree_root(&rbtree1) ) != BLACK )
2109    puts ( "INIT - ERROR ON RBTREE ROOT IS BLACK MISMATCH" );
2110
2111  puts( "INIT - Removing 100 nodes" );
2112
2113  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
2114      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
2115    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2116    if ( id < 0 ) {
2117      puts( "INIT - TOO MANY NODES ON RBTREE" );
2118      rtems_test_exit(0);
2119    }
2120    if ( t->id != id ) {
2121      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2122      rtems_test_exit(0);
2123    }
2124
2125    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2126      puts( "INIT - FAILED TREE CHECK" );
2127  }
2128
2129  if(!rtems_rbtree_is_empty(&rbtree1)) {
2130    puts( "INIT - TREE NOT EMPTY" );
2131    rtems_test_exit(0);
2132  }
2133
2134  puts("INIT - Insert 20 random numbers");
2135  for (i = 0; i < 20; i++) {
2136    visitor_context ctx = { 0, i + 1, test_insert_trees[ i ] };
2137
2138    node_array[i].id = numbers[i];
2139    node_array[i].key = numbers[i];
2140    rb_insert_unique( &rbtree1, &node_array[i].Node );
2141
2142    _RBTree_Iterate( &rbtree1, visit_nodes, &ctx );
2143    rtems_test_assert( ctx.current == ctx.count );
2144
2145    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2146      puts( "INIT - FAILED TREE CHECK" );
2147  }
2148
2149  puts( "INIT - Removing 20 nodes" );
2150
2151  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2152      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2153    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2154    if ( id > 19 ) {
2155      puts( "INIT - TOO MANY NODES ON RBTREE" );
2156      rtems_test_exit(0);
2157    }
2158    if ( t->id != numbers_sorted[id] ) {
2159      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2160      rtems_test_exit(0);
2161    }
2162
2163    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2164      puts( "INIT - FAILED TREE CHECK" );
2165
2166    if ( id < 19 ) {
2167      visitor_context ctx = { 0, 20 - id - 1, test_remove_trees[ id ] };
2168
2169      _RBTree_Iterate( &rbtree1, visit_nodes, &ctx );
2170      rtems_test_assert( ctx.current == ctx.count );
2171    }
2172  }
2173
2174  if(!rtems_rbtree_is_empty(&rbtree1)) {
2175    puts( "INIT - TREE NOT EMPTY" );
2176    rtems_test_exit(0);
2177  }
2178
2179  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
2180  for (i = 0; i < 100; i++) {
2181    node_array[i].id = i;
2182    node_array[i].key = i;
2183  }
2184  rtems_rbtree_initialize( &rbtree1, &test_compare_function,
2185                           &node_array[0].Node, 100,
2186                           sizeof(test_node), true );
2187
2188  puts( "INIT - Removing 100 nodes" );
2189
2190  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2191      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2192    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2193    if ( id > 99 ) {
2194      puts( "INIT - TOO MANY NODES ON RBTREE" );
2195      rtems_test_exit(0);
2196    }
2197
2198    if ( t->id != id ) {
2199      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2200      rtems_test_exit(0);
2201    }
2202
2203    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2204      puts( "INIT - FAILED TREE CHECK" );
2205  }
2206
2207  if(!rtems_rbtree_is_empty(&rbtree1)) {
2208    puts( "INIT - TREE NOT EMPTY" );
2209    rtems_test_exit(0);
2210  }
2211
2212  /* Initialize the tree for duplicate keys */
2213  puts( "Init - Initialize duplicate rbtree empty" );
2214  rtems_rbtree_initialize_empty( &rbtree1 );
2215
2216  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
2217  for (i = 0; i < 100; i++) {
2218    node_array[i].id = i;
2219    node_array[i].key = i%5;
2220    rb_insert_multi( &rbtree1, &node_array[i].Node );
2221
2222    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2223      puts( "INIT - FAILED TREE CHECK" );
2224  }
2225
2226  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
2227  search_node.key = 2;
2228  p = rb_find_multi(&rbtree1, &search_node.Node);
2229  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 2) {
2230    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2231    rtems_test_exit(0);
2232  }
2233
2234  puts( "INIT - Removing 100 nodes" );
2235
2236  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2237      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2238    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2239    if ( id > 99 ) {
2240      puts( "INIT - TOO MANY NODES ON RBTREE" );
2241      rtems_test_exit(0);
2242    }
2243    if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
2244      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2245      rtems_test_exit(0);
2246    }
2247
2248    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2249      puts( "INIT - FAILED TREE CHECK" );
2250  }
2251
2252  if(!rtems_rbtree_is_empty(&rbtree1)) {
2253    puts( "INIT - TREE NOT EMPTY" );
2254    rtems_test_exit(0);
2255  }
2256
2257  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
2258  for (i = 0; i < 100; i++) {
2259    node_array[i].id = 99-i;
2260    node_array[i].key = (99-i)%5;
2261    rb_insert_multi( &rbtree1, &node_array[i].Node );
2262
2263    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2264      puts( "INIT - FAILED TREE CHECK" );
2265  }
2266
2267  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
2268  search_node.key = 2;
2269  p = rb_find_multi(&rbtree1, &search_node.Node);
2270  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 97) {
2271    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
2272    rtems_test_exit(0);
2273  }
2274
2275  puts( "INIT - Removing 100 nodes" );
2276
2277  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
2278      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
2279    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
2280    if ( id > 99 ) {
2281      puts( "INIT - TOO MANY NODES ON RBTREE" );
2282      rtems_test_exit(0);
2283    }
2284    if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
2285      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
2286      rtems_test_exit(0);
2287    }
2288
2289    if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
2290      puts( "INIT - FAILED TREE CHECK" );
2291  }
2292
2293  if(!rtems_rbtree_is_empty(&rbtree1)) {
2294    puts( "INIT - TREE NOT EMPTY" );
2295    rtems_test_exit(0);
2296  }
2297
2298  test_rbtree_init_one();
2299  test_rbtree_min_max();
2300  test_rbtree_insert_inline();
2301  test_rbtree_random_ops();
2302
2303  TEST_END();
2304  rtems_test_exit(0);
2305}
2306
2307/* configuration information */
2308
2309#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
2310#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
2311
2312#define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION
2313
2314#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
2315#define CONFIGURE_MAXIMUM_TASKS 1
2316
2317#define CONFIGURE_INIT
2318#include <rtems/confdefs.h>
2319
2320/* global variables */
Note: See TracBrowser for help on using the repository browser.