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

4.115
Last change on this file since b767683a was b767683a, checked in by Sebastian Huber <sebastian.huber@…>, on 07/22/14 at 20:49:09

rbtree: Rename find header in find control

Simplify _RBTree_Find_control(). Avoid superfluous NULL pointer checks.

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