Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
remplace -> replace
[simgrid.git] / testsuite / xbt / heap_bench.c
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <sys/time.h>
4 #include "xbt_heap.h"
5
6 #define MAX_TEST 1000000
7
8 /* Pour le bench */
9 long us_time(void);
10 long us_time(void)
11 {
12    struct timeval start;
13    gettimeofday(&start, NULL);
14    
15    return (start.tv_sec * 1000000 + start.tv_usec);
16 }
17
18 int compare_xbt_heap_float_t (const void *a, const void *b);
19 void test_heap_validity(int size);
20 void test_heap_mean_operation(int size);
21
22 int compare_xbt_heap_float_t (const void *a, const void *b) 
23 {
24   xbt_heap_float_t pa, pb;
25
26   pa=* ((xbt_heap_float_t *)a);
27   pb=* ((xbt_heap_float_t *)b);
28
29   if(pa>pb) return 1;
30   if(pa==pb) return 0;
31   return -1;
32 }
33
34 void test_heap_validity(int size)
35 {
36   xbt_heap_t heap = xbt_heap_new(size,NULL);
37   xbt_heap_float_t *tab = calloc(size,sizeof(xbt_heap_float_t));
38   int i;
39
40   for(i=0; i<size; i++) {
41     tab[i] = (10.0*rand()/(RAND_MAX+1.0));
42     xbt_heap_push(heap, NULL, tab[i]);
43   }
44
45   qsort(tab, size, sizeof(xbt_heap_float_t), compare_xbt_heap_float_t);
46
47   for(i=0; i<size; i++) { 
48     /*     printf(XBT_HEAP_FLOAT_T " ", xbt_heap_maxkey(heap)); */
49     if(xbt_heap_maxkey(heap)!= tab[i]) {
50       fprintf(stderr,"Problem !\n");
51       exit(1);
52     }
53     xbt_heap_pop(heap);
54   }
55   xbt_heap_free(heap);
56   free(tab);
57   printf("Validity test complete!\n");
58 }
59
60 void test_heap_mean_operation(int size)
61 {
62   xbt_heap_t heap = xbt_heap_new(size,NULL);
63   xbt_heap_float_t val;  
64   long date = 0;
65   int i, j;
66
67   date = us_time();
68   for(i=0; i<size; i++)
69     xbt_heap_push(heap, NULL, (10.0*rand()/(RAND_MAX+1.0)));
70   date = us_time()-date;
71   printf("Creation time  %d size heap : %g\n", size, 0.0+date);
72
73   date = us_time();
74   for(j=0; j<MAX_TEST; j++) {
75     val=xbt_heap_maxkey(heap);
76     xbt_heap_pop(heap);
77     xbt_heap_push(heap, NULL, 3.0*val);
78   }
79   date = us_time()-date;
80   printf("Mean access time for a %d size heap : %g\n", size, date*1.0/(MAX_TEST+0.0));
81
82   xbt_heap_free(heap);  
83 }
84
85 int main(int argc, char **argv)
86 {
87   int size;
88   for(size = 100; size < 10000; size*=10) {
89     test_heap_validity(size);
90     test_heap_mean_operation(size);
91   }
92   return 0;
93 }