source: rtems/testsuites/sptests/sprbtree01/init.c @ 64939bc

4.11
Last change on this file since 64939bc was 64939bc, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 12, 2014 at 7:22:22 PM

rbtree: Reduce RBTree_Control size

Remove compare function and is unique indicator from the control
structure. Rename RBTree_Compare_function to RBTree_Compare. Rename
rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++
compatible initializers. Add compare function and is unique indicator
to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
rtems_rbtree_insert(). Remove _RBTree_Is_unique() and
rtems_rbtree_is_unique(). Remove compare function and is unique
indicator from _RBTree_Initialize_empty() and
rtems_rbtree_initialize_empty().

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