source: rtems/testsuites/sptests/sprbtree01/init.c @ 8abbbdde

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

rbtree: Do not set node off-tree in extract

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