source: rtems/testsuites/sptests/sprbtree01/init.c @ 611909e

4.115
Last change on this file since 611909e was 611909e, checked in by Joel Sherrill <joel.sherrill@…>, on 08/21/11 at 20:07:23

2011-08-21 Petr Benes <benesp16@…>

PR 1886/cpukit

  • sprbtree01/init.c, sprbtree01/sprbtree01.scn: This patch enables inserting duplicate keys into rbtree. It is possible to turn on this feature when initializing the tree.
  • Property mode set to 100644
File size: 19.3 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.com/license/LICENSE.
7 *
8 *  $Id$
9 */
10
11#include <tmacros.h>
12#include <rtems/rbtree.h>
13
14int numbers[20] = {
1552, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71};
16
17int numbers_sorted[20] = {
18  0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99};
19
20typedef struct {
21  int              id;
22  int              key;
23  rtems_rbtree_node Node;
24} test_node;
25
26int test_compare_function (
27  rtems_rbtree_node* n1,
28  rtems_rbtree_node* n2
29)
30{
31  int key1 = rtems_rbtree_container_of( n1, test_node, Node )->key;
32  int key2 = rtems_rbtree_container_of( n2, test_node, Node )->key;
33
34  if (key1 > key2) return 1;
35  else if (key1 < key2) return -1;
36  else return 0;
37}
38
39/*
40 * recursively checks tree. if the tree is built properly it should only
41 * be a depth of 7 function calls for 100 entries in the tree.
42 */
43int rb_assert ( rtems_rbtree_node *root )
44{
45  int lh, rh;
46
47  if ( root == NULL )
48    return 1;
49  else {
50    rtems_rbtree_node *ln = rtems_rbtree_left(root);
51    rtems_rbtree_node *rn = rtems_rbtree_right(root);
52
53    /* Consecutive red links */
54    if ( root->color == RBT_RED ) {
55      if ((ln && ln->color == RBT_RED)  || (rn && rn->color == RBT_RED)) {
56        puts ( "Red violation" );
57        return -1;
58      }
59    }
60
61      lh = rb_assert ( ln );
62      rh = rb_assert ( rn );
63
64    /* Invalid binary search tree */
65    if ( ( ln != NULL && test_compare_function(ln, root) > 0 )
66        || ( rn != NULL && test_compare_function(rn, root) < 0 ) )
67    {
68      puts ( "Binary tree violation" );
69      return -1;
70    }
71
72    /* Black height mismatch */
73    if ( lh != -1 && rh != -1 && lh != rh ) {
74      puts ( "Black violation" );
75      return -1;
76    }
77
78    /* Only count black links */
79    if ( lh != -1 && rh != -1 )
80      return ( root->color == RBT_RED ) ? lh : lh + 1;
81    else
82      return -1;
83  }
84}
85
86
87
88rtems_task Init(
89    rtems_task_argument ignored
90    )
91{
92  rtems_rbtree_control  rbtree1;
93  rtems_rbtree_node    *p;
94  test_node            node1, node2;
95  test_node            node_array[100];
96  test_node            search_node;
97  int                  id;
98  int i;
99
100  puts( "\n\n*** TEST OF RTEMS RBTREE API ***" );
101
102  puts( "Init - Initialize rbtree empty" );
103  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function,
104                                 RTEMS_RBTREE_UNIQUE );
105
106  if ( !rtems_rbtree_is_unique( &rbtree1 ) )
107    puts( "INIT - FAILED IS UNIQUE CHECK" );
108  if ( rtems_rbtree_is_unique( NULL ) )
109    puts( "INIT - FAILED IS UNIQUE CHECK" );
110
111  /* verify that the rbtree insert work */
112  puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
113  node1.id = 1;
114  node1.key = 1;
115  node2.id = 2;
116  node2.key = 2;
117  rtems_rbtree_insert( &rbtree1, &node1.Node );
118  rtems_rbtree_insert( &rbtree1, &node2.Node );
119
120  p = rtems_rbtree_insert( &rbtree1, NULL );
121  if (p != (void *)(-1))
122    puts( "INIT - FAILED NULL NODE INSERT" );
123
124  _RBTree_Rotate(NULL, RBT_LEFT);
125  i = (node1.Node.parent == &node2.Node);
126  _RBTree_Rotate( &node1.Node,
127                  !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT
128                );
129  if ( (node1.Node.parent == &node2.Node) != i )
130    puts( "INIT - FAILED FALSE ROTATION" );
131
132  if (!rb_assert(rbtree1.root) )
133    puts( "INIT - FAILED TREE CHECK" );
134
135  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
136      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
137    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
138    if ( id > 2 ) {
139      puts( "INIT - TOO MANY NODES ON RBTREE" );
140      rtems_test_exit(0);
141    }
142    if ( t->id != id ) {
143      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
144      rtems_test_exit(0);
145    }
146
147    if (!rb_assert(rbtree1.root) )
148      puts( "INIT - FAILED TREE CHECK" );
149  }
150  if (id < 2) {
151    puts("INIT - NOT ENOUGH NODES ON RBTREE");
152    rtems_test_exit(0);
153  }
154
155  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
156  node2.key = node1.key;
157  rtems_rbtree_insert(&rbtree1, &node1.Node);
158  p = rtems_rbtree_insert(&rbtree1, &node2.Node);
159
160  if (p != &node1.Node)
161    puts( "INIT - FAILED DUPLICATE INSERT" );
162
163  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
164      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
165    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
166    if ( id > 1 ) {
167      puts( "INIT - TOO MANY NODES ON RBTREE" );
168      rtems_test_exit(0);
169    }
170    if ( t->id != id ) {
171      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
172      rtems_test_exit(0);
173    }
174
175    if (!rb_assert(rbtree1.root) )
176      puts( "INIT - FAILED TREE CHECK" );
177  }
178  if (id < 1) {
179    puts("INIT - NOT ENOUGH NODES ON RBTREE");
180    rtems_test_exit(0);
181  }
182  node2.key = 2;
183
184  /* verify that the rbtree is empty */
185  puts( "INIT - Verify rtems_rbtree_is_empty" );
186  if(!rtems_rbtree_is_empty(&rbtree1)) {
187    puts( "INIT - TREE NOT EMPTY" );
188    rtems_test_exit(0);
189  }
190
191  puts( "INIT - Verify rtems_XXX on an empty tree" );
192  if(rtems_rbtree_get_min(&rbtree1)) {
193    puts("INIT - get_min on empty returned non-NULL");
194    rtems_test_exit(0);
195  }
196  if(rtems_rbtree_get_max(&rbtree1)) {
197    puts("INIT - get_max on empty returned non-NULL");
198    rtems_test_exit(0);
199  }
200  if(rtems_rbtree_peek_min(&rbtree1)) {
201    puts("INIT - peek_min on empty returned non-NULL");
202    rtems_test_exit(0);
203  }
204  if(rtems_rbtree_peek_max(&rbtree1)) {
205    puts("INIT - peek_max on empty returned non-NULL");
206    rtems_test_exit(0);
207  }
208
209
210  /* verify that the rbtree insert works after a tree is emptied */
211  puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
212  node1.id = 2;
213  node1.key = 2;
214  node2.id = 1;
215  node2.key = 1;
216  rtems_rbtree_insert( &rbtree1, &node1.Node );
217  rtems_rbtree_insert( &rbtree1, &node2.Node );
218
219  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
220  test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1),
221         test_node,Node);
222  test_node *t2 = rtems_rbtree_container_of(rtems_rbtree_peek_min(&rbtree1),
223         test_node,Node);
224  if (t1->key - t2->key != 1) {
225    puts( "INIT - Peek Min - Max failed" );
226    rtems_test_exit(0);
227  }
228  p = rtems_rbtree_peek_max(&rbtree1);
229  rtems_rbtree_extract(&rbtree1, p);
230  t1 = rtems_rbtree_container_of(p,test_node,Node);
231  if (t1->key != 2) {
232    puts( "INIT - rtems_rbtree_extract failed");
233    rtems_test_exit(0);
234  }
235  rtems_rbtree_insert(&rbtree1, p);
236
237  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
238      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
239    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
240    if ( id > 2 ) {
241      puts( "INIT - TOO MANY NODES ON RBTREE" );
242      rtems_test_exit(0);
243    }
244    if ( t->id != id ) {
245      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
246      rtems_test_exit(0);
247    }
248  }
249 
250  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
251  for (i = 0; i < 100; i++) {
252    node_array[i].id = i;
253    node_array[i].key = i;
254    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
255
256    if (!rb_assert(rbtree1.root) )
257      puts( "INIT - FAILED TREE CHECK" );
258  }
259
260  puts( "INIT - Removing 100 nodes" );
261
262  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
263      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
264    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
265    if ( id > 99 ) {
266      puts( "INIT - TOO MANY NODES ON RBTREE" );
267      rtems_test_exit(0);
268    }
269    if ( t->id != id ) {
270      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
271      rtems_test_exit(0);
272    }
273
274    if (!rb_assert(rbtree1.root) )
275      puts( "INIT - FAILED TREE CHECK" );
276  }
277 
278  if(!rtems_rbtree_is_empty(&rbtree1)) {
279    puts( "INIT - TREE NOT EMPTY" );
280    rtems_test_exit(0);
281  }
282
283  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
284  for (i = 0; i < 100; i++) {
285    node_array[i].id = 99-i;
286    node_array[i].key = 99-i;
287    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
288
289    if (!rb_assert(rbtree1.root) )
290      puts( "INIT - FAILED TREE CHECK" );
291  }
292
293  puts( "INIT - Removing 100 nodes" );
294
295  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
296      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
297    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
298    if ( id > 99 ) {
299      puts( "INIT - TOO MANY NODES ON RBTREE" );
300      rtems_test_exit(0);
301    }
302    if ( t->id != id ) {
303      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
304      rtems_test_exit(0);
305    }
306
307    if (!rb_assert(rbtree1.root) )
308      puts( "INIT - FAILED TREE CHECK" );
309  }
310
311  if(!rtems_rbtree_is_empty(&rbtree1)) {
312    puts( "INIT - TREE NOT EMPTY" );
313    rtems_test_exit(0);
314  }
315
316  /* testing rbtree_extract by adding 100 nodes then removing the 20 with
317   * keys specified by the numbers array, then removing the rest */
318  puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" );
319  for (i = 0; i < 100; i++) {
320    node_array[i].id = i;
321    node_array[i].key = i;
322    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
323
324    if (!rb_assert(rbtree1.root) )
325      puts( "INIT - FAILED TREE CHECK" );
326  }
327
328  puts( "INIT - Extracting 20 random nodes" );
329
330  for (i = 0; i < 20; i++) {
331    id = numbers[i];
332    rtems_rbtree_extract( &rbtree1, &node_array[id].Node );
333    if (!rb_assert(rbtree1.root) )
334      puts( "INIT - FAILED TREE CHECK" );
335  }
336
337  puts( "INIT - Removing 80 nodes" );
338
339  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ;
340      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
341    test_node *t = rtems_rbtree_container_of(p, test_node, Node);
342
343    while ( id == numbers_sorted[i] ) {
344      /* skip if expected minimum (id) is in the set of extracted numbers */
345      id++;
346      i++;
347    }
348
349    if ( id > 99 ) {
350      puts( "INIT - TOO MANY NODES ON RBTREE" );
351      rtems_test_exit(0);
352    }
353
354    if ( t->id != id ) {
355      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
356      rtems_test_exit(0);
357    }
358
359    if (!rb_assert(rbtree1.root) )
360      puts( "INIT - FAILED TREE CHECK" );
361  }
362
363  if(!rtems_rbtree_is_empty(&rbtree1)) {
364    puts( "INIT - TREE NOT EMPTY" );
365    rtems_test_exit(0);
366  }
367
368  /* Additional rtems_rbtree_extract test which removes a node
369   * with two children while target node has a left child only. */
370  for ( i = 0; i < 7; i++ ) {
371    node_array[i].id = i;
372    node_array[i].key = i;
373  }
374  rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
375  rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
376  rtems_rbtree_insert( &rbtree1, &node_array[5].Node );
377  rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
378  rtems_rbtree_insert( &rbtree1, &node_array[2].Node );
379  rtems_rbtree_insert( &rbtree1, &node_array[4].Node );
380  rtems_rbtree_insert( &rbtree1, &node_array[6].Node );
381  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
382  /* node_array[1] has now only a left child. */
383  if ( !node_array[1].Node.child[RBT_LEFT] ||
384        node_array[1].Node.child[RBT_RIGHT] )
385     puts( "INIT - LEFT CHILD ONLY NOT FOUND" );
386  rtems_rbtree_extract( &rbtree1, &node_array[3].Node );
387  while( (p = rtems_rbtree_get_max(&rbtree1)) );
388
389  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
390  for (i = 0; i < 100; i++) {
391    node_array[i].id = 99-i;
392    node_array[i].key = 99-i;
393    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
394
395    if (!rb_assert(rbtree1.root) )
396      puts( "INIT - FAILED TREE CHECK" );
397  }
398
399  puts( "INIT - Removing 100 nodes" );
400
401  for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
402      p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
403    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
404    if ( id > 99 ) {
405      puts( "INIT - TOO MANY NODES ON RBTREE" );
406      rtems_test_exit(0);
407    }
408    if ( t->id != 99-id ) {
409      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
410      rtems_test_exit(0);
411    }
412
413    if (!rb_assert(rbtree1.root) )
414      puts( "INIT - FAILED TREE CHECK" );
415  }
416
417  if(!rtems_rbtree_is_empty(&rbtree1)) {
418    puts( "INIT - TREE NOT EMPTY" );
419    rtems_test_exit(0);
420  }
421
422  puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
423  for (i = 0; i < 100; i++) {
424    node_array[i].id = i;
425    node_array[i].key = i;
426    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
427
428    if (!rb_assert(rbtree1.root) )
429      puts( "INIT - FAILED TREE CHECK" );
430  }
431
432  puts( "INIT - Verify rtems_rbtree_find" );
433  search_node.key = 30;
434  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
435  if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) {
436    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
437    rtems_test_exit(0);
438  }
439
440  puts( "INIT - Verify rtems_rbtree_predecessor/successor");
441  p = rtems_rbtree_predecessor(p);
442  if(p && rtems_rbtree_container_of(p,test_node,Node)->id > 30) {
443    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
444    rtems_test_exit(0);
445  }
446  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
447  p = rtems_rbtree_successor(p);
448  if(p && rtems_rbtree_container_of(p,test_node,Node)->id < 30) {
449    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
450    rtems_test_exit(0);
451  }
452
453  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
454  puts( "INIT - Verify rtems_rbtree_find_header" );
455  if (rtems_rbtree_find_header(p) != &rbtree1) {
456    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
457    rtems_test_exit(0);
458  }
459
460  if ( _RBTree_Sibling( NULL ) != NULL )
461    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
462  if ( _RBTree_Sibling( rbtree1.root ) != NULL )
463    puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
464  if ( _RBTree_Grandparent( NULL ) != NULL )
465    puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" );
466  if ( _RBTree_Is_red( NULL ) != 0 )
467    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
468
469  puts( "INIT - Removing 100 nodes" );
470
471  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
472      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
473    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
474    if ( id < 0 ) {
475      puts( "INIT - TOO MANY NODES ON RBTREE" );
476      rtems_test_exit(0);
477    }
478    if ( t->id != id ) {
479      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
480      rtems_test_exit(0);
481    }
482
483    if (!rb_assert(rbtree1.root) )
484      puts( "INIT - FAILED TREE CHECK" );
485  }
486
487  if(!rtems_rbtree_is_empty(&rbtree1)) {
488    puts( "INIT - TREE NOT EMPTY" );
489    rtems_test_exit(0);
490  }
491
492  if (rtems_rbtree_find_header(&node_array[0].Node) != NULL) {
493    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
494    rtems_test_exit(0);
495  }
496  if (rtems_rbtree_find_header(NULL) != NULL) {
497    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
498    rtems_test_exit(0);
499  }
500
501  puts("INIT - Insert 20 random numbers");
502  for (i = 0; i < 20; i++) {
503    node_array[i].id = numbers[i];
504    node_array[i].key = numbers[i];
505    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
506
507    if (!rb_assert(rbtree1.root) )
508      puts( "INIT - FAILED TREE CHECK" );
509  }
510
511  puts( "INIT - Removing 20 nodes" );
512
513  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
514      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
515    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
516    if ( id > 19 ) {
517      puts( "INIT - TOO MANY NODES ON RBTREE" );
518      rtems_test_exit(0);
519    }
520    if ( t->id != numbers_sorted[id] ) {
521      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
522      rtems_test_exit(0);
523    }
524
525    if (!rb_assert(rbtree1.root) )
526      puts( "INIT - FAILED TREE CHECK" );
527  }
528
529  if(!rtems_rbtree_is_empty(&rbtree1)) {
530    puts( "INIT - TREE NOT EMPTY" );
531    rtems_test_exit(0);
532  }
533
534  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
535  for (i = 0; i < 100; i++) {
536    node_array[i].id = i;
537    node_array[i].key = i;
538  }
539  rtems_rbtree_initialize( &rbtree1, &test_compare_function,
540                           &node_array[0].Node, 100,
541                           sizeof(test_node), RTEMS_RBTREE_UNIQUE );
542
543  puts( "INIT - Removing 100 nodes" );
544
545  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
546      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
547    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
548    if ( id > 99 ) {
549      puts( "INIT - TOO MANY NODES ON RBTREE" );
550      rtems_test_exit(0);
551    }
552
553    if ( t->id != id ) {
554      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
555      rtems_test_exit(0);
556    }
557
558    if (!rb_assert(rbtree1.root) )
559      puts( "INIT - FAILED TREE CHECK" );
560  }
561
562  if(!rtems_rbtree_is_empty(&rbtree1)) {
563    puts( "INIT - TREE NOT EMPTY" );
564    rtems_test_exit(0);
565  }
566
567  /* Initialize the tree for duplicate keys */
568  puts( "Init - Initialize duplicate rbtree empty" );
569  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function,
570                                 RTEMS_RBTREE_DUPLICATE );
571
572  if ( rtems_rbtree_is_unique( &rbtree1 ) )
573    puts( "INIT - FAILED IS UNIQUE CHECK" );
574  if ( rtems_rbtree_is_unique( NULL ) )
575    puts( "INIT - FAILED IS UNIQUE CHECK" );
576
577  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
578  for (i = 0; i < 100; i++) {
579    node_array[i].id = i;
580    node_array[i].key = i%5;
581    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
582
583    if (!rb_assert(rbtree1.root) )
584      puts( "INIT - FAILED TREE CHECK" );
585  }
586
587  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
588  search_node.key = 2;
589  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
590  if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) {
591    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
592    rtems_test_exit(0);
593  }
594
595  puts( "INIT - Removing 100 nodes" );
596
597  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
598      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
599    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
600    if ( id > 99 ) {
601      puts( "INIT - TOO MANY NODES ON RBTREE" );
602      rtems_test_exit(0);
603    }
604    if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
605      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
606      rtems_test_exit(0);
607    }
608
609    if (!rb_assert(rbtree1.root) )
610      puts( "INIT - FAILED TREE CHECK" );
611  }
612
613  if(!rtems_rbtree_is_empty(&rbtree1)) {
614    puts( "INIT - TREE NOT EMPTY" );
615    rtems_test_exit(0);
616  }
617
618  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
619  for (i = 0; i < 100; i++) {
620    node_array[i].id = 99-i;
621    node_array[i].key = (99-i)%5;
622    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
623
624    if (!rb_assert(rbtree1.root) )
625      puts( "INIT - FAILED TREE CHECK" );
626  }
627
628  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
629  search_node.key = 2;
630  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
631  if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) {
632    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
633    rtems_test_exit(0);
634  }
635
636  puts( "INIT - Removing 100 nodes" );
637
638  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
639      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
640    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
641    if ( id > 99 ) {
642      puts( "INIT - TOO MANY NODES ON RBTREE" );
643      rtems_test_exit(0);
644    }
645    if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
646      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
647      rtems_test_exit(0);
648    }
649
650    if (!rb_assert(rbtree1.root) )
651      puts( "INIT - FAILED TREE CHECK" );
652  }
653
654  if(!rtems_rbtree_is_empty(&rbtree1)) {
655    puts( "INIT - TREE NOT EMPTY" );
656    rtems_test_exit(0);
657  }
658
659  puts( "*** END OF RTEMS RBTREE API TEST ***" );
660  rtems_test_exit(0);
661}
662
663/* configuration information */
664
665#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
666#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
667
668#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
669#define CONFIGURE_MAXIMUM_TASKS 1
670
671#define CONFIGURE_INIT
672#include <rtems/confdefs.h>
673
674/* global variables */
Note: See TracBrowser for help on using the repository browser.