source: rtems/testsuites/sptests/sprbtree01/init.c @ 888edf6

4.115
Last change on this file since 888edf6 was 888edf6, checked in by Sebastian Huber <sebastian.huber@…>, on 08/05/14 at 11:52:45

sptests/sprbtree01: Reduce stack usage

  • Property mode set to 100644
File size: 21.7 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
225rtems_task Init( rtems_task_argument ignored )
226{
227  rtems_rbtree_control  rbtree1;
228  rtems_rbtree_node    *p;
229  test_node            node1, node2;
230  test_node            search_node;
231  int                  id;
232  int i;
233
234  TEST_BEGIN();
235
236  puts( "Init - Initialize rbtree empty" );
237  rtems_rbtree_initialize_empty( &rbtree1 );
238
239  rtems_rbtree_set_off_tree( &node1.Node );
240  rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) );
241
242  /* verify that the rbtree insert work */
243  puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
244  node1.id = 1;
245  node1.key = 1;
246  node2.id = 2;
247  node2.key = 2;
248  rb_insert_unique( &rbtree1, &node1.Node );
249  rb_insert_unique( &rbtree1, &node2.Node );
250
251  rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
252
253  _RBTree_Rotate(NULL, RBT_LEFT);
254  i = (node1.Node.parent == &node2.Node);
255  _RBTree_Rotate( &node1.Node,
256                  !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT
257                );
258  if ( (node1.Node.parent == &node2.Node) != i )
259    puts( "INIT - FAILED FALSE ROTATION" );
260
261  if (!rb_assert(rbtree1.root) )
262    puts( "INIT - FAILED TREE CHECK" );
263
264  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
265      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
266    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
267    if ( id > 2 ) {
268      puts( "INIT - TOO MANY NODES ON RBTREE" );
269      rtems_test_exit(0);
270    }
271    if ( t->id != id ) {
272      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
273      rtems_test_exit(0);
274    }
275
276    if (!rb_assert(rbtree1.root) )
277      puts( "INIT - FAILED TREE CHECK" );
278  }
279  if (id < 2) {
280    puts("INIT - NOT ENOUGH NODES ON RBTREE");
281    rtems_test_exit(0);
282  }
283
284  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
285  node2.key = node1.key;
286  rb_insert_unique(&rbtree1, &node1.Node);
287  p = rb_insert_unique(&rbtree1, &node2.Node);
288
289  if (p != &node1.Node)
290    puts( "INIT - FAILED DUPLICATE INSERT" );
291
292  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
293      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
294    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
295    if ( id > 1 ) {
296      puts( "INIT - TOO MANY NODES ON RBTREE" );
297      rtems_test_exit(0);
298    }
299    if ( t->id != id ) {
300      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
301      rtems_test_exit(0);
302    }
303
304    if (!rb_assert(rbtree1.root) )
305      puts( "INIT - FAILED TREE CHECK" );
306  }
307  if (id < 1) {
308    puts("INIT - NOT ENOUGH NODES ON RBTREE");
309    rtems_test_exit(0);
310  }
311  node2.key = 2;
312
313  /* verify that the rbtree is empty */
314  puts( "INIT - Verify rtems_rbtree_is_empty" );
315  if(!rtems_rbtree_is_empty(&rbtree1)) {
316    puts( "INIT - TREE NOT EMPTY" );
317    rtems_test_exit(0);
318  }
319
320  puts( "INIT - Verify rtems_XXX on an empty tree" );
321  if(rtems_rbtree_get_min(&rbtree1)) {
322    puts("INIT - get_min on empty returned non-NULL");
323    rtems_test_exit(0);
324  }
325  if(rtems_rbtree_get_max(&rbtree1)) {
326    puts("INIT - get_max on empty returned non-NULL");
327    rtems_test_exit(0);
328  }
329  if(rtems_rbtree_peek_min(&rbtree1)) {
330    puts("INIT - peek_min on empty returned non-NULL");
331    rtems_test_exit(0);
332  }
333  if(rtems_rbtree_peek_max(&rbtree1)) {
334    puts("INIT - peek_max on empty returned non-NULL");
335    rtems_test_exit(0);
336  }
337
338
339  /* verify that the rbtree insert works after a tree is emptied */
340  puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
341  node1.id = 2;
342  node1.key = 2;
343  node2.id = 1;
344  node2.key = 1;
345  rb_insert_unique( &rbtree1, &node1.Node );
346  rb_insert_unique( &rbtree1, &node2.Node );
347
348  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
349  test_node *t1 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_max(&rbtree1),
350         test_node,Node);
351  test_node *t2 = RTEMS_CONTAINER_OF(rtems_rbtree_peek_min(&rbtree1),
352         test_node,Node);
353  if (t1->key - t2->key != 1) {
354    puts( "INIT - Peek Min - Max failed" );
355    rtems_test_exit(0);
356  }
357  p = rtems_rbtree_peek_max(&rbtree1);
358  rtems_rbtree_extract(&rbtree1, p);
359  t1 = RTEMS_CONTAINER_OF(p,test_node,Node);
360  if (t1->key != 2) {
361    puts( "INIT - rtems_rbtree_extract failed");
362    rtems_test_exit(0);
363  }
364  rtems_test_assert( !rtems_rbtree_is_node_off_tree( p ) );
365  rb_insert_unique(&rbtree1, p);
366
367  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
368      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
369    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
370    if ( id > 2 ) {
371      puts( "INIT - TOO MANY NODES ON RBTREE" );
372      rtems_test_exit(0);
373    }
374    if ( t->id != id ) {
375      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
376      rtems_test_exit(0);
377    }
378  }
379 
380  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
381  for (i = 0; i < 100; i++) {
382    node_array[i].id = i;
383    node_array[i].key = i;
384    rb_insert_unique( &rbtree1, &node_array[i].Node );
385
386    if (!rb_assert(rbtree1.root) )
387      puts( "INIT - FAILED TREE CHECK" );
388  }
389
390  puts( "INIT - Removing 100 nodes" );
391
392  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
393      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
394    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
395    if ( id > 99 ) {
396      puts( "INIT - TOO MANY NODES ON RBTREE" );
397      rtems_test_exit(0);
398    }
399    if ( t->id != id ) {
400      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
401      rtems_test_exit(0);
402    }
403
404    if (!rb_assert(rbtree1.root) )
405      puts( "INIT - FAILED TREE CHECK" );
406  }
407 
408  if(!rtems_rbtree_is_empty(&rbtree1)) {
409    puts( "INIT - TREE NOT EMPTY" );
410    rtems_test_exit(0);
411  }
412
413  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
414  for (i = 0; i < 100; i++) {
415    node_array[i].id = 99-i;
416    node_array[i].key = 99-i;
417    rb_insert_unique( &rbtree1, &node_array[i].Node );
418
419    if (!rb_assert(rbtree1.root) )
420      puts( "INIT - FAILED TREE CHECK" );
421  }
422
423  puts( "INIT - Removing 100 nodes" );
424
425  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
426      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
427    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
428    if ( id > 99 ) {
429      puts( "INIT - TOO MANY NODES ON RBTREE" );
430      rtems_test_exit(0);
431    }
432    if ( t->id != id ) {
433      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
434      rtems_test_exit(0);
435    }
436
437    if (!rb_assert(rbtree1.root) )
438      puts( "INIT - FAILED TREE CHECK" );
439  }
440
441  if(!rtems_rbtree_is_empty(&rbtree1)) {
442    puts( "INIT - TREE NOT EMPTY" );
443    rtems_test_exit(0);
444  }
445
446  /* testing rbtree_extract by adding 100 nodes then removing the 20 with
447   * keys specified by the numbers array, then removing the rest */
448  puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
449  for (i = 0; i < 100; i++) {
450    node_array[i].id = i;
451    node_array[i].key = i;
452    rb_insert_unique( &rbtree1, &node_array[i].Node );
453
454    if (!rb_assert(rbtree1.root) )
455      puts( "INIT - FAILED TREE CHECK" );
456  }
457
458  puts( "INIT - Extracting 20 random nodes" );
459
460  for (i = 0; i < 20; i++) {
461    id = numbers[i];
462    rtems_rbtree_extract( &rbtree1, &node_array[id].Node );
463    if (!rb_assert(rbtree1.root) )
464      puts( "INIT - FAILED TREE CHECK" );
465  }
466
467  puts( "INIT - Removing 80 nodes" );
468
469  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ;
470      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
471    test_node *t = RTEMS_CONTAINER_OF(p, test_node, Node);
472
473    while ( id == numbers_sorted[i] ) {
474      /* skip if expected minimum (id) is in the set of extracted numbers */
475      id++;
476      i++;
477    }
478
479    if ( id > 99 ) {
480      puts( "INIT - TOO MANY NODES ON RBTREE" );
481      rtems_test_exit(0);
482    }
483
484    if ( t->id != id ) {
485      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
486      rtems_test_exit(0);
487    }
488
489    if (!rb_assert(rbtree1.root) )
490      puts( "INIT - FAILED TREE CHECK" );
491  }
492
493  if(!rtems_rbtree_is_empty(&rbtree1)) {
494    puts( "INIT - TREE NOT EMPTY" );
495    rtems_test_exit(0);
496  }
497
498  /* Additional rtems_rbtree_extract test which removes a node
499   * with two children while target node has a left child only. */
500  for ( i = 0; i < 7; i++ ) {
501    node_array[i].id = i;
502    node_array[i].key = i;
503  }
504  rb_insert_unique( &rbtree1, &node_array[3].Node );
505  rb_insert_unique( &rbtree1, &node_array[1].Node );
506  rb_insert_unique( &rbtree1, &node_array[5].Node );
507  rb_insert_unique( &rbtree1, &node_array[0].Node );
508  rb_insert_unique( &rbtree1, &node_array[2].Node );
509  rb_insert_unique( &rbtree1, &node_array[4].Node );
510  rb_insert_unique( &rbtree1, &node_array[6].Node );
511  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
512  /* node_array[1] has now only a left child. */
513  if ( !node_array[1].Node.child[RBT_LEFT] ||
514        node_array[1].Node.child[RBT_RIGHT] )
515     puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
516  rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
517  while( (p = rtems_rbtree_get_max(&rbtree1)) );
518
519  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
520  for (i = 0; i < 100; i++) {
521    node_array[i].id = 99-i;
522    node_array[i].key = 99-i;
523    rb_insert_unique( &rbtree1, &node_array[i].Node );
524
525    if (!rb_assert(rbtree1.root) )
526      puts( "INIT - FAILED TREE CHECK" );
527  }
528
529  puts( "INIT - Removing 100 nodes" );
530
531  for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
532      p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
533    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
534    if ( id > 99 ) {
535      puts( "INIT - TOO MANY NODES ON RBTREE" );
536      rtems_test_exit(0);
537    }
538    if ( t->id != 99-id ) {
539      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
540      rtems_test_exit(0);
541    }
542
543    if (!rb_assert(rbtree1.root) )
544      puts( "INIT - FAILED TREE CHECK" );
545  }
546
547  if(!rtems_rbtree_is_empty(&rbtree1)) {
548    puts( "INIT - TREE NOT EMPTY" );
549    rtems_test_exit(0);
550  }
551
552  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
553  for (i = 0; i < 100; i++) {
554    node_array[i].id = i;
555    node_array[i].key = i;
556    rb_insert_unique( &rbtree1, &node_array[i].Node );
557
558    if (!rb_assert(rbtree1.root) )
559      puts( "INIT - FAILED TREE CHECK" );
560  }
561
562  puts( "INIT - Verify rtems_rbtree_find" );
563  search_node.key = 30;
564  p = rb_find_unique(&rbtree1, &search_node.Node);
565  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 30) {
566    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
567    rtems_test_exit(0);
568  }
569
570  puts( "INIT - Verify rtems_rbtree_predecessor/successor");
571  p = rtems_rbtree_predecessor(p);
572  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 29) {
573    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
574    rtems_test_exit(0);
575  }
576  p = rb_find_unique(&rbtree1, &search_node.Node);
577  p = rtems_rbtree_successor(p);
578  if(p && RTEMS_CONTAINER_OF(p,test_node,Node)->id != 31) {
579    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
580    rtems_test_exit(0);
581  }
582
583  p = rb_find_unique(&rbtree1, &search_node.Node);
584  puts( "INIT - Verify rtems_rbtree_find_control" );
585  if (rtems_rbtree_find_control(p) != &rbtree1) {
586    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
587    rtems_test_exit(0);
588  }
589
590  if ( _RBTree_Sibling( NULL ) != NULL )
591    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
592  if ( _RBTree_Sibling( rbtree1.root ) != NULL )
593    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
594  if ( _RBTree_Grandparent( NULL ) != NULL )
595    puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" );
596  if ( _RBTree_Is_red( NULL ) != 0 )
597    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
598  if ( _RBTree_Is_red( rbtree1.root ) != 0 )
599    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
600
601  puts( "INIT - Removing 100 nodes" );
602
603  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
604      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
605    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
606    if ( id < 0 ) {
607      puts( "INIT - TOO MANY NODES ON RBTREE" );
608      rtems_test_exit(0);
609    }
610    if ( t->id != id ) {
611      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
612      rtems_test_exit(0);
613    }
614
615    if (!rb_assert(rbtree1.root) )
616      puts( "INIT - FAILED TREE CHECK" );
617  }
618
619  if(!rtems_rbtree_is_empty(&rbtree1)) {
620    puts( "INIT - TREE NOT EMPTY" );
621    rtems_test_exit(0);
622  }
623
624  puts("INIT - Insert 20 random numbers");
625  for (i = 0; i < 20; i++) {
626    node_array[i].id = numbers[i];
627    node_array[i].key = numbers[i];
628    rb_insert_unique( &rbtree1, &node_array[i].Node );
629
630    if (!rb_assert(rbtree1.root) )
631      puts( "INIT - FAILED TREE CHECK" );
632  }
633
634  puts( "INIT - Removing 20 nodes" );
635
636  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
637      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
638    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
639    if ( id > 19 ) {
640      puts( "INIT - TOO MANY NODES ON RBTREE" );
641      rtems_test_exit(0);
642    }
643    if ( t->id != numbers_sorted[id] ) {
644      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
645      rtems_test_exit(0);
646    }
647
648    if (!rb_assert(rbtree1.root) )
649      puts( "INIT - FAILED TREE CHECK" );
650  }
651
652  if(!rtems_rbtree_is_empty(&rbtree1)) {
653    puts( "INIT - TREE NOT EMPTY" );
654    rtems_test_exit(0);
655  }
656
657  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
658  for (i = 0; i < 100; i++) {
659    node_array[i].id = i;
660    node_array[i].key = i;
661  }
662  rtems_rbtree_initialize( &rbtree1, &test_compare_function,
663                           &node_array[0].Node, 100,
664                           sizeof(test_node), true );
665
666  puts( "INIT - Removing 100 nodes" );
667
668  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
669      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
670    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
671    if ( id > 99 ) {
672      puts( "INIT - TOO MANY NODES ON RBTREE" );
673      rtems_test_exit(0);
674    }
675
676    if ( t->id != id ) {
677      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
678      rtems_test_exit(0);
679    }
680
681    if (!rb_assert(rbtree1.root) )
682      puts( "INIT - FAILED TREE CHECK" );
683  }
684
685  if(!rtems_rbtree_is_empty(&rbtree1)) {
686    puts( "INIT - TREE NOT EMPTY" );
687    rtems_test_exit(0);
688  }
689
690  /* Initialize the tree for duplicate keys */
691  puts( "Init - Initialize duplicate rbtree empty" );
692  rtems_rbtree_initialize_empty( &rbtree1 );
693
694  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
695  for (i = 0; i < 100; i++) {
696    node_array[i].id = i;
697    node_array[i].key = i%5;
698    rb_insert_multi( &rbtree1, &node_array[i].Node );
699
700    if (!rb_assert(rbtree1.root) )
701      puts( "INIT - FAILED TREE CHECK" );
702  }
703
704  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
705  search_node.key = 2;
706  p = rb_find_multi(&rbtree1, &search_node.Node);
707  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 2) {
708    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
709    rtems_test_exit(0);
710  }
711
712  puts( "INIT - Removing 100 nodes" );
713
714  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
715      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
716    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
717    if ( id > 99 ) {
718      puts( "INIT - TOO MANY NODES ON RBTREE" );
719      rtems_test_exit(0);
720    }
721    if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
722      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
723      rtems_test_exit(0);
724    }
725
726    if (!rb_assert(rbtree1.root) )
727      puts( "INIT - FAILED TREE CHECK" );
728  }
729
730  if(!rtems_rbtree_is_empty(&rbtree1)) {
731    puts( "INIT - TREE NOT EMPTY" );
732    rtems_test_exit(0);
733  }
734
735  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
736  for (i = 0; i < 100; i++) {
737    node_array[i].id = 99-i;
738    node_array[i].key = (99-i)%5;
739    rb_insert_multi( &rbtree1, &node_array[i].Node );
740
741    if (!rb_assert(rbtree1.root) )
742      puts( "INIT - FAILED TREE CHECK" );
743  }
744
745  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
746  search_node.key = 2;
747  p = rb_find_multi(&rbtree1, &search_node.Node);
748  if(RTEMS_CONTAINER_OF(p,test_node,Node)->id != 97) {
749    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
750    rtems_test_exit(0);
751  }
752
753  puts( "INIT - Removing 100 nodes" );
754
755  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
756      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
757    test_node *t = RTEMS_CONTAINER_OF(p,test_node,Node);
758    if ( id > 99 ) {
759      puts( "INIT - TOO MANY NODES ON RBTREE" );
760      rtems_test_exit(0);
761    }
762    if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
763      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
764      rtems_test_exit(0);
765    }
766
767    if (!rb_assert(rbtree1.root) )
768      puts( "INIT - FAILED TREE CHECK" );
769  }
770
771  if(!rtems_rbtree_is_empty(&rbtree1)) {
772    puts( "INIT - TREE NOT EMPTY" );
773    rtems_test_exit(0);
774  }
775
776  test_rbtree_min_max();
777
778  TEST_END();
779  rtems_test_exit(0);
780}
781
782/* configuration information */
783
784#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
785#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
786
787#define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION
788
789#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
790#define CONFIGURE_MAXIMUM_TASKS 1
791
792#define CONFIGURE_INIT
793#include <rtems/confdefs.h>
794
795/* global variables */
Note: See TracBrowser for help on using the repository browser.