source: rtems/testsuites/sptests/sprbtree01/init.c @ 6c0301d

4.11
Last change on this file since 6c0301d was 6c0301d, checked in by Sebastian Huber <sebastian.huber@…>, on Mar 25, 2014 at 7:06:21 AM

tests/sptests: Use <rtems/test.h>

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