source: rtems/testsuites/sptests/sprbtree01/init.c @ 9ccdb1d

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