source: rtems/testsuites/sptests/sprbtree01/init.c @ c976c70

4.115
Last change on this file since c976c70 was c976c70, checked in by Joel Sherrill <joel.sherrill@…>, on 09/27/11 at 00:59:30

2011-09-26 Petr Benes <benesp16@…>

PR 1923/testing

  • spcbssched02/spcbssched02.scn, spcbssched02/system.h, spcbssched03/init.c, spcbssched03/system.h, spedfsched02/system.h, spedfsched03/system.h, sprbtree01/init.c: Improve coverage.
  • Property mode set to 100644
File size: 19.4 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  if ( _RBTree_Is_red( rbtree1.root ) != 0 )
469    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
470
471  puts( "INIT - Removing 100 nodes" );
472
473  for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
474      p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
475    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
476    if ( id < 0 ) {
477      puts( "INIT - TOO MANY NODES ON RBTREE" );
478      rtems_test_exit(0);
479    }
480    if ( t->id != id ) {
481      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
482      rtems_test_exit(0);
483    }
484
485    if (!rb_assert(rbtree1.root) )
486      puts( "INIT - FAILED TREE CHECK" );
487  }
488
489  if(!rtems_rbtree_is_empty(&rbtree1)) {
490    puts( "INIT - TREE NOT EMPTY" );
491    rtems_test_exit(0);
492  }
493
494  if (rtems_rbtree_find_header(&node_array[0].Node) != NULL) {
495    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
496    rtems_test_exit(0);
497  }
498  if (rtems_rbtree_find_header(NULL) != NULL) {
499    puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
500    rtems_test_exit(0);
501  }
502
503  puts("INIT - Insert 20 random numbers");
504  for (i = 0; i < 20; i++) {
505    node_array[i].id = numbers[i];
506    node_array[i].key = numbers[i];
507    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
508
509    if (!rb_assert(rbtree1.root) )
510      puts( "INIT - FAILED TREE CHECK" );
511  }
512
513  puts( "INIT - Removing 20 nodes" );
514
515  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
516      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
517    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
518    if ( id > 19 ) {
519      puts( "INIT - TOO MANY NODES ON RBTREE" );
520      rtems_test_exit(0);
521    }
522    if ( t->id != numbers_sorted[id] ) {
523      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
524      rtems_test_exit(0);
525    }
526
527    if (!rb_assert(rbtree1.root) )
528      puts( "INIT - FAILED TREE CHECK" );
529  }
530
531  if(!rtems_rbtree_is_empty(&rbtree1)) {
532    puts( "INIT - TREE NOT EMPTY" );
533    rtems_test_exit(0);
534  }
535
536  puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" );
537  for (i = 0; i < 100; i++) {
538    node_array[i].id = i;
539    node_array[i].key = i;
540  }
541  rtems_rbtree_initialize( &rbtree1, &test_compare_function,
542                           &node_array[0].Node, 100,
543                           sizeof(test_node), RTEMS_RBTREE_UNIQUE );
544
545  puts( "INIT - Removing 100 nodes" );
546
547  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
548      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
549    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
550    if ( id > 99 ) {
551      puts( "INIT - TOO MANY NODES ON RBTREE" );
552      rtems_test_exit(0);
553    }
554
555    if ( t->id != id ) {
556      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
557      rtems_test_exit(0);
558    }
559
560    if (!rb_assert(rbtree1.root) )
561      puts( "INIT - FAILED TREE CHECK" );
562  }
563
564  if(!rtems_rbtree_is_empty(&rbtree1)) {
565    puts( "INIT - TREE NOT EMPTY" );
566    rtems_test_exit(0);
567  }
568
569  /* Initialize the tree for duplicate keys */
570  puts( "Init - Initialize duplicate rbtree empty" );
571  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function,
572                                 RTEMS_RBTREE_DUPLICATE );
573
574  if ( rtems_rbtree_is_unique( &rbtree1 ) )
575    puts( "INIT - FAILED IS UNIQUE CHECK" );
576  if ( rtems_rbtree_is_unique( NULL ) )
577    puts( "INIT - FAILED IS UNIQUE CHECK" );
578
579  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
580  for (i = 0; i < 100; i++) {
581    node_array[i].id = i;
582    node_array[i].key = i%5;
583    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
584
585    if (!rb_assert(rbtree1.root) )
586      puts( "INIT - FAILED TREE CHECK" );
587  }
588
589  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
590  search_node.key = 2;
591  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
592  if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) {
593    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
594    rtems_test_exit(0);
595  }
596
597  puts( "INIT - Removing 100 nodes" );
598
599  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
600      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
601    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
602    if ( id > 99 ) {
603      puts( "INIT - TOO MANY NODES ON RBTREE" );
604      rtems_test_exit(0);
605    }
606    if ( t->id != ( ((id*5)%100) + (id/20) ) ) {
607      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
608      rtems_test_exit(0);
609    }
610
611    if (!rb_assert(rbtree1.root) )
612      puts( "INIT - FAILED TREE CHECK" );
613  }
614
615  if(!rtems_rbtree_is_empty(&rbtree1)) {
616    puts( "INIT - TREE NOT EMPTY" );
617    rtems_test_exit(0);
618  }
619
620  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
621  for (i = 0; i < 100; i++) {
622    node_array[i].id = 99-i;
623    node_array[i].key = (99-i)%5;
624    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
625
626    if (!rb_assert(rbtree1.root) )
627      puts( "INIT - FAILED TREE CHECK" );
628  }
629
630  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
631  search_node.key = 2;
632  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
633  if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) {
634    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
635    rtems_test_exit(0);
636  }
637
638  puts( "INIT - Removing 100 nodes" );
639
640  for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
641      p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
642    test_node *t = rtems_rbtree_container_of(p,test_node,Node);
643    if ( id > 99 ) {
644      puts( "INIT - TOO MANY NODES ON RBTREE" );
645      rtems_test_exit(0);
646    }
647    if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) {
648      puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
649      rtems_test_exit(0);
650    }
651
652    if (!rb_assert(rbtree1.root) )
653      puts( "INIT - FAILED TREE CHECK" );
654  }
655
656  if(!rtems_rbtree_is_empty(&rbtree1)) {
657    puts( "INIT - TREE NOT EMPTY" );
658    rtems_test_exit(0);
659  }
660
661  puts( "*** END OF RTEMS RBTREE API TEST ***" );
662  rtems_test_exit(0);
663}
664
665/* configuration information */
666
667#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
668#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
669
670#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
671#define CONFIGURE_MAXIMUM_TASKS 1
672
673#define CONFIGURE_INIT
674#include <rtems/confdefs.h>
675
676/* global variables */
Note: See TracBrowser for help on using the repository browser.