source: rtems/testsuites/sptests/sprbtree01/init.c @ 4752550f

4.115
Last change on this file since 4752550f was 4752550f, checked in by Sebastian Huber <sebastian.huber@…>, on 07/23/14 at 11:19:09

rbtree: Simplify _RBTree_Rotate()

Add and use _RBTree_Direction().

  • Property mode set to 100644
File size: 44.5 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->id );
816  rtems_test_assert( td->key == tn->key );
817
818  if ( td->parent == NULL ) {
819    rtems_test_assert( td->parent == tn->Node.parent->parent );
820  } else {
821    rtems_test_assert( td->parent == tn->Node.parent );
822  }
823
824  rtems_test_assert( td->left == tn->Node.child[ RBT_LEFT ] );
825  rtems_test_assert( td->right == tn->Node.child[ RBT_RIGHT ] );
826  rtems_test_assert( td->color == tn->Node.color );
827
828  ++ctx->current;
829
830  return false;
831}
832
833rtems_task Init( rtems_task_argument ignored )
834{
835  rtems_rbtree_control  rbtree1;
836  rtems_rbtree_node    *p;
837  test_node            node1, node2;
838  test_node            search_node;
839  int                  id;
840  int i;
841
842  TEST_BEGIN();
843
844  puts( "Init - Initialize rbtree empty" );
845  rtems_rbtree_initialize_empty( &rbtree1 );
846
847  rtems_rbtree_set_off_tree( &node1.Node );
848  rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) );
849
850  /* verify that the rbtree insert work */
851  puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
852  node1.id = 1;
853  node1.key = 1;
854  node2.id = 2;
855  node2.key = 2;
856  rb_insert_unique( &rbtree1, &node1.Node );
857  rb_insert_unique( &rbtree1, &node2.Node );
858
859  rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
860
861  i = (node1.Node.parent == &node2.Node);
862  _RBTree_Rotate( &node1.Node,
863                  !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT
864                );
865  if ( (node1.Node.parent == &node2.Node) != i )
866    puts( "INIT - FAILED FALSE ROTATION" );
867
868  if (!rb_assert(rbtree1.root) )
869    puts( "INIT - FAILED TREE CHECK" );
870
871  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
872      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
873    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
874    if ( id > 2 ) {
875      puts( "INIT - TOO MANY NODES ON RBTREE" );
876      rtems_test_exit(0);
877    }
878    if ( t->id != id ) {
879      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
880      rtems_test_exit(0);
881    }
882
883    if (!rb_assert(rbtree1.root) )
884      puts( "INIT - FAILED TREE CHECK" );
885  }
886  if (id < 2) {
887    puts("INIT - NOT ENOUGH NODES ON RBTREE");
888    rtems_test_exit(0);
889  }
890
891  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
892  node2.key = node1.key;
893  rb_insert_unique(&rbtree1, &node1.Node);
894  p = rb_insert_unique(&rbtree1, &node2.Node);
895
896  if (p != &node1.Node)
897    puts( "INIT - FAILED DUPLICATE INSERT" );
898
899  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
900      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
901    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
902    if ( id > 1 ) {
903      puts( "INIT - TOO MANY NODES ON RBTREE" );
904      rtems_test_exit(0);
905    }
906    if ( t->id != id ) {
907      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
908      rtems_test_exit(0);
909    }
910
911    if (!rb_assert(rbtree1.root) )
912      puts( "INIT - FAILED TREE CHECK" );
913  }
914  if (id < 1) {
915    puts("INIT - NOT ENOUGH NODES ON RBTREE");
916    rtems_test_exit(0);
917  }
918  node2.key = 2;
919
920  /* verify that the rbtree is empty */
921  puts( "INIT - Verify rtems_rbtree_is_empty" );
922  if(!rtems_rbtree_is_empty(&rbtree1)) {
923    puts( "INIT - TREE NOT EMPTY" );
924    rtems_test_exit(0);
925  }
926
927  puts( "INIT - Verify rtems_XXX on an empty tree" );
928  if(rtems_rbtree_get_min(&rbtree1)) {
929    puts("INIT - get_min on empty returned non-NULL");
930    rtems_test_exit(0);
931  }
932  if(rtems_rbtree_get_max(&rbtree1)) {
933    puts("INIT - get_max on empty returned non-NULL");
934    rtems_test_exit(0);
935  }
936  if(rtems_rbtree_peek_min(&rbtree1)) {
937    puts("INIT - peek_min on empty returned non-NULL");
938    rtems_test_exit(0);
939  }
940  if(rtems_rbtree_peek_max(&rbtree1)) {
941    puts("INIT - peek_max on empty returned non-NULL");
942    rtems_test_exit(0);
943  }
944
945
946  /* verify that the rbtree insert works after a tree is emptied */
947  puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
948  node1.id = 2;
949  node1.key = 2;
950  node2.id = 1;
951  node2.key = 1;
952  rb_insert_unique( &rbtree1, &node1.Node );
953  rb_insert_unique( &rbtree1, &node2.Node );
954
955  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
956  test_node *t1 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_max(&rbtree1),
957         test_node,Node);
958  test_node *t2 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_min(&rbtree1),
959         test_node,Node);
960  if (t1->key - t2->key != 1) {
961    puts( "INIT - Peek Min - Max failed" );
962    rtems_test_exit(0);
963  }
964  p = rtems_rbtree_peek_max(&rbtree1);
965  rtems_rbtree_extract(&rbtree1, p);
966  t1 = RTEMS_CONTAINER_OF(p,test_node,Node);
967  if (t1->key != 2) {
968    puts( "INIT - rtems_rbtree_extract failed");
969    rtems_test_exit(0);
970  }
971  rtems_test_assert( !rtems_rbtree_is_node_off_tree( p ) );
972  rb_insert_unique(&rbtree1, p);
973
974  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
975      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
976    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
977    if ( id > 2 ) {
978      puts( "INIT - TOO MANY NODES ON RBTREE" );
979      rtems_test_exit(0);
980    }
981    if ( t->id != id ) {
982      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
983      rtems_test_exit(0);
984    }
985  }
986 
987  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
988  for (i = 0; i < 100; i++) {
989    node_array[i].id = i;
990    node_array[i].key = i;
991    rb_insert_unique( &rbtree1, &node_array[i].Node );
992
993    if (!rb_assert(rbtree1.root) )
994      puts( "INIT - FAILED TREE CHECK" );
995  }
996
997  puts( "INIT - Removing 100 nodes" );
998
999  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1000      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1001    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1002    if ( id > 99 ) {
1003      puts( "INIT - TOO MANY NODES ON RBTREE" );
1004      rtems_test_exit(0);
1005    }
1006    if ( t->id != id ) {
1007      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1008      rtems_test_exit(0);
1009    }
1010
1011    if (!rb_assert(rbtree1.root) )
1012      puts( "INIT - FAILED TREE CHECK" );
1013  }
1014 
1015  if(!rtems_rbtree_is_empty(&rbtree1)) {
1016    puts( "INIT - TREE NOT EMPTY" );
1017    rtems_test_exit(0);
1018  }
1019
1020  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
1021  for (i = 0; i < 100; i++) {
1022    node_array[i].id = 99-i;
1023    node_array[i].key = 99-i;
1024    rb_insert_unique( &rbtree1, &node_array[i].Node );
1025
1026    if (!rb_assert(rbtree1.root) )
1027      puts( "INIT - FAILED TREE CHECK" );
1028  }
1029
1030  puts( "INIT - Removing 100 nodes" );
1031
1032  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1033      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1034    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1035    if ( id > 99 ) {
1036      puts( "INIT - TOO MANY NODES ON RBTREE" );
1037      rtems_test_exit(0);
1038    }
1039    if ( t->id != id ) {
1040      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1041      rtems_test_exit(0);
1042    }
1043
1044    if (!rb_assert(rbtree1.root) )
1045      puts( "INIT - FAILED TREE CHECK" );
1046  }
1047
1048  if(!rtems_rbtree_is_empty(&rbtree1)) {
1049    puts( "INIT - TREE NOT EMPTY" );
1050    rtems_test_exit(0);
1051  }
1052
1053  /* testing rbtree_extract by adding 100 nodes then removing the 20 with
1054   * keys specified by the numbers array, then removing the rest */
1055  puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
1056  for (i = 0; i < 100; i++) {
1057    node_array[i].id = i;
1058    node_array[i].key = i;
1059    rb_insert_unique( &rbtree1, &node_array[i].Node );
1060
1061    if (!rb_assert(rbtree1.root) )
1062      puts( "INIT - FAILED TREE CHECK" );
1063  }
1064
1065  puts( "INIT - Extracting 20 random nodes" );
1066
1067  for (i = 0; i < 20; i++) {
1068    id = numbers[i];
1069    rtems_rbtree_extract( &rbtree1, &node_array[id].Node );
1070    if (!rb_assert(rbtree1.root) )
1071      puts( "INIT - FAILED TREE CHECK" );
1072  }
1073
1074  puts( "INIT - Removing 80 nodes" );
1075
1076  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ;
1077      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1078    test_node *t = RTEMS_CONTAINER_OF(p, test_node, Node);
1079
1080    while ( id == numbers_sorted[i] ) {
1081      /* skip if expected minimum (id) is in the set of extracted numbers */
1082      id++;
1083      i++;
1084    }
1085
1086    if ( id > 99 ) {
1087      puts( "INIT - TOO MANY NODES ON RBTREE" );
1088      rtems_test_exit(0);
1089    }
1090
1091    if ( t->id != id ) {
1092      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1093      rtems_test_exit(0);
1094    }
1095
1096    if (!rb_assert(rbtree1.root) )
1097      puts( "INIT - FAILED TREE CHECK" );
1098  }
1099
1100  if(!rtems_rbtree_is_empty(&rbtree1)) {
1101    puts( "INIT - TREE NOT EMPTY" );
1102    rtems_test_exit(0);
1103  }
1104
1105  /* Additional rtems_rbtree_extract test which removes a node
1106   * with two children while target node has a left child only. */
1107  for ( i = 0; i < 7; i++ ) {
1108    node_array[i].id = i;
1109    node_array[i].key = i;
1110  }
1111  rb_insert_unique( &rbtree1, &node_array[3].Node );
1112  rb_insert_unique( &rbtree1, &node_array[1].Node );
1113  rb_insert_unique( &rbtree1, &node_array[5].Node );
1114  rb_insert_unique( &rbtree1, &node_array[0].Node );
1115  rb_insert_unique( &rbtree1, &node_array[2].Node );
1116  rb_insert_unique( &rbtree1, &node_array[4].Node );
1117  rb_insert_unique( &rbtree1, &node_array[6].Node );
1118  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
1119  /* node_array[1] has now only a left child. */
1120  if ( !node_array[1].Node.child[RBT_LEFT] ||
1121        node_array[1].Node.child[RBT_RIGHT] )
1122     puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
1123  rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
1124  while( (p = rtems_rbtree_get_max(&rbtree1)) );
1125
1126  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
1127  for (i = 0; i < 100; i++) {
1128    node_array[i].id = 99-i;
1129    node_array[i].key = 99-i;
1130    rb_insert_unique( &rbtree1, &node_array[i].Node );
1131
1132    if (!rb_assert(rbtree1.root) )
1133      puts( "INIT - FAILED TREE CHECK" );
1134  }
1135
1136  puts( "INIT - Removing 100 nodes" );
1137
1138  for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
1139      p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
1140    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1141    if ( id > 99 ) {
1142      puts( "INIT - TOO MANY NODES ON RBTREE" );
1143      rtems_test_exit(0);
1144    }
1145    if ( t->id != 99-id ) {
1146      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1147      rtems_test_exit(0);
1148    }
1149
1150    if (!rb_assert(rbtree1.root) )
1151      puts( "INIT - FAILED TREE CHECK" );
1152  }
1153
1154  if(!rtems_rbtree_is_empty(&rbtree1)) {
1155    puts( "INIT - TREE NOT EMPTY" );
1156    rtems_test_exit(0);
1157  }
1158
1159  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
1160  for (i = 0; i < 100; i++) {
1161    node_array[i].id = i;
1162    node_array[i].key = i;
1163    rb_insert_unique( &rbtree1, &node_array[i].Node );
1164
1165    if (!rb_assert(rbtree1.root) )
1166      puts( "INIT - FAILED TREE CHECK" );
1167  }
1168
1169  puts( "INIT - Verify rtems_rbtree_find" );
1170  search_node.key = 30;
1171  p = rb_find_unique(&rbtree1, &search_node.Node);
1172  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 30) {
1173    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
1174    rtems_test_exit(0);
1175  }
1176
1177  puts( "INIT - Verify rtems_rbtree_predecessor/successor");
1178  p = rtems_rbtree_predecessor(p);
1179  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 29) {
1180    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
1181    rtems_test_exit(0);
1182  }
1183  p = rb_find_unique(&rbtree1, &search_node.Node);
1184  p = rtems_rbtree_successor(p);
1185  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 31) {
1186    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
1187    rtems_test_exit(0);
1188  }
1189
1190  p = rb_find_unique(&rbtree1, &search_node.Node);
1191  puts( "INIT - Verify rtems_rbtree_find_control" );
1192  if (rtems_rbtree_find_control(p) != &rbtree1) {
1193    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
1194    rtems_test_exit(0);
1195  }
1196
1197  if ( _RBTree_Sibling( NULL ) != NULL )
1198    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
1199  if ( _RBTree_Sibling( rbtree1.root ) != NULL )
1200    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
1201  if ( _RBTree_Grandparent( NULL ) != NULL )
1202    puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" );
1203  if ( _RBTree_Is_red( NULL ) != 0 )
1204    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
1205  if ( _RBTree_Is_red( rbtree1.root ) != 0 )
1206    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
1207
1208  puts( "INIT - Removing 100 nodes" );
1209
1210  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
1211      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
1212    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1213    if ( id < 0 ) {
1214      puts( "INIT - TOO MANY NODES ON RBTREE" );
1215      rtems_test_exit(0);
1216    }
1217    if ( t->id != id ) {
1218      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1219      rtems_test_exit(0);
1220    }
1221
1222    if (!rb_assert(rbtree1.root) )
1223      puts( "INIT - FAILED TREE CHECK" );
1224  }
1225
1226  if(!rtems_rbtree_is_empty(&rbtree1)) {
1227    puts( "INIT - TREE NOT EMPTY" );
1228    rtems_test_exit(0);
1229  }
1230
1231  puts("INIT - Insert 20 random numbers");
1232  for (i = 0; i < 20; i++) {
1233    visitor_context ctx = { 0, i + 1, test_insert_trees[ i ] };
1234
1235    node_array[i].id = numbers[i];
1236    node_array[i].key = numbers[i];
1237    rb_insert_unique( &rbtree1, &node_array[i].Node );
1238
1239    _RBTree_Iterate( &rbtree1, RBT_RIGHT, visit_nodes, &ctx );
1240    rtems_test_assert( ctx.current == ctx.count );
1241
1242    if (!rb_assert(rbtree1.root) )
1243      puts( "INIT - FAILED TREE CHECK" );
1244  }
1245
1246  puts( "INIT - Removing 20 nodes" );
1247
1248  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1249      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1250    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1251    if ( id > 19 ) {
1252      puts( "INIT - TOO MANY NODES ON RBTREE" );
1253      rtems_test_exit(0);
1254    }
1255    if ( t->id != numbers_sorted[id] ) {
1256      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1257      rtems_test_exit(0);
1258    }
1259
1260    if (!rb_assert(rbtree1.root) )
1261      puts( "INIT - FAILED TREE CHECK" );
1262
1263    if ( id < 19 ) {
1264      visitor_context ctx = { 0, 20 - id - 1, test_remove_trees[ id ] };
1265
1266      _RBTree_Iterate( &rbtree1, RBT_RIGHT, visit_nodes, &ctx );
1267      rtems_test_assert( ctx.current == ctx.count );
1268    }
1269  }
1270
1271  if(!rtems_rbtree_is_empty(&rbtree1)) {
1272    puts( "INIT - TREE NOT EMPTY" );
1273    rtems_test_exit(0);
1274  }
1275
1276  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
1277  for (i = 0; i < 100; i++) {
1278    node_array[i].id = i;
1279    node_array[i].key = i;
1280  }
1281  rtems_rbtree_initialize( &rbtree1, &test_compare_function,
1282                           &node_array[0].Node, 100,
1283                           sizeof(test_node), true );
1284
1285  puts( "INIT - Removing 100 nodes" );
1286
1287  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1288      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1289    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1290    if ( id > 99 ) {
1291      puts( "INIT - TOO MANY NODES ON RBTREE" );
1292      rtems_test_exit(0);
1293    }
1294
1295    if ( t->id != id ) {
1296      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1297      rtems_test_exit(0);
1298    }
1299
1300    if (!rb_assert(rbtree1.root) )
1301      puts( "INIT - FAILED TREE CHECK" );
1302  }
1303
1304  if(!rtems_rbtree_is_empty(&rbtree1)) {
1305    puts( "INIT - TREE NOT EMPTY" );
1306    rtems_test_exit(0);
1307  }
1308
1309  /* Initialize the tree for duplicate keys */
1310  puts( "Init - Initialize duplicate rbtree empty" );
1311  rtems_rbtree_initialize_empty( &rbtree1 );
1312
1313  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
1314  for (i = 0; i < 100; i++) {
1315    node_array[i].id = i;
1316    node_array[i].key = i%5;
1317    rb_insert_multi( &rbtree1, &node_array[i].Node );
1318
1319    if (!rb_assert(rbtree1.root) )
1320      puts( "INIT - FAILED TREE CHECK" );
1321  }
1322
1323  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
1324  search_node.key = 2;
1325  p = rb_find_multi(&rbtree1, &search_node.Node);
1326  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 2) {
1327    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
1328    rtems_test_exit(0);
1329  }
1330
1331  puts( "INIT - Removing 100 nodes" );
1332
1333  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1334      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1335    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1336    if ( id > 99 ) {
1337      puts( "INIT - TOO MANY NODES ON RBTREE" );
1338      rtems_test_exit(0);
1339    }
1340    if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
1341      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1342      rtems_test_exit(0);
1343    }
1344
1345    if (!rb_assert(rbtree1.root) )
1346      puts( "INIT - FAILED TREE CHECK" );
1347  }
1348
1349  if(!rtems_rbtree_is_empty(&rbtree1)) {
1350    puts( "INIT - TREE NOT EMPTY" );
1351    rtems_test_exit(0);
1352  }
1353
1354  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
1355  for (i = 0; i < 100; i++) {
1356    node_array[i].id = 99-i;
1357    node_array[i].key = (99-i)%5;
1358    rb_insert_multi( &rbtree1, &node_array[i].Node );
1359
1360    if (!rb_assert(rbtree1.root) )
1361      puts( "INIT - FAILED TREE CHECK" );
1362  }
1363
1364  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
1365  search_node.key = 2;
1366  p = rb_find_multi(&rbtree1, &search_node.Node);
1367  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 97) {
1368    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
1369    rtems_test_exit(0);
1370  }
1371
1372  puts( "INIT - Removing 100 nodes" );
1373
1374  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
1375      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
1376    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
1377    if ( id > 99 ) {
1378      puts( "INIT - TOO MANY NODES ON RBTREE" );
1379      rtems_test_exit(0);
1380    }
1381    if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
1382      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
1383      rtems_test_exit(0);
1384    }
1385
1386    if (!rb_assert(rbtree1.root) )
1387      puts( "INIT - FAILED TREE CHECK" );
1388  }
1389
1390  if(!rtems_rbtree_is_empty(&rbtree1)) {
1391    puts( "INIT - TREE NOT EMPTY" );
1392    rtems_test_exit(0);
1393  }
1394
1395  test_rbtree_min_max();
1396
1397  TEST_END();
1398  rtems_test_exit(0);
1399}
1400
1401/* configuration information */
1402
1403#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
1404#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
1405
1406#define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION
1407
1408#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
1409#define CONFIGURE_MAXIMUM_TASKS 1
1410
1411#define CONFIGURE_INIT
1412#include <rtems/confdefs.h>
1413
1414/* global variables */
Note: See TracBrowser for help on using the repository browser.