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

4.115
Last change on this file since d7a94693 was d7a94693, checked in by Sebastian Huber <sebastian.huber@…>, on 07/21/14 at 16:16:47

rbtree: Remove superfluous NULL pointer checks

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