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

4.11
Last change on this file since c499856 was c499856, checked in by Chris Johns <chrisj@…>, on Mar 20, 2014 at 9:10:47 PM

Change all references of rtems.com to rtems.org.

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