source: rtems/testsuites/sptests/sprbtree01/init.c @ 509e8d7f

5
Last change on this file since 509e8d7f was 509e8d7f, checked in by Sebastian Huber <sebastian.huber@…>, on 08/18/15 at 04:21:17

rbtree: Delete rtems_rbtree_find_control()

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