testsuite/xbt/heap_bench.c

   1 /* A few tests for the xbt_heap module                                      */
   2
   3 /* Copyright (c) 2004-2010, 2012. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #ifdef __BORLANDC__
  10 #pragma hdrstop
  11 #endif
  12
  13 #include <stdlib.h>
  14 #include <stdio.h>
  15 #include <xbt/xbt_os_time.h>
  16
  17 #include "xbt/heap.h"
  18 #include "xbt/sysdep.h"         /* calloc, printf */
  19
  20 #define MAX_TEST 1000000
  21
  22 #ifdef __BORLANDC__
  23 int _XBT_CALL compare_double(const void *a, const void *b);
  24 #else
  25 int compare_double(const void *a, const void *b);
  26 #endif
  27
  28 void test_heap_validity(int size);
  29 void test_heap_mean_operation(int size);
  30 void test_reset_heap(xbt_heap_t * heap, int size);
  31
  32
  33 int compare_double(const void *a, const void *b)
  34 {
  35   double pa, pb;
  36
  37   pa = *((double *) a);
  38   pb = *((double *) b);
  39
  40   if (pa > pb)
  41     return 1;
  42   if (pa == pb)
  43     return 0;
  44   return -1;
  45 }
  46
  47 void test_heap_validity(int size)
  48 {
  49   xbt_heap_t heap = xbt_heap_new(size, NULL);
  50   double *tab = xbt_new0(double, size);
  51
  52   int i;
  53
  54   for (i = 0; i < size; i++) {
  55     tab[i] = (double) (10.0 * rand() / (RAND_MAX + 1.0));
  56     xbt_heap_push(heap, NULL, (double) tab[i]);
  57   }
  58
  59   qsort(tab, size, sizeof(double), compare_double);
  60
  61   for (i = 0; i < size; i++) {
  62     /*     printf("%lg" " ", xbt_heap_maxkey(heap)); */
  63     if (xbt_heap_maxkey(heap) != tab[i]) {
  64       fprintf(stderr, "Problem !\n");
  65       exit(1);
  66     }
  67     xbt_heap_pop(heap);
  68   }
  69   xbt_heap_free(heap);
  70   free(tab);
  71   printf("Validity test complete!\n");
  72 }
  73
  74 void test_heap_mean_operation(int size)
  75 {
  76   xbt_heap_t heap = xbt_heap_new(size, NULL);
  77   double val;
  78   double date = 0;
  79   int i, j;
  80
  81   date = xbt_os_time() * 1000000;
  82   for (i = 0; i < size; i++)
  83     xbt_heap_push(heap, NULL, (10.0 * rand() / (RAND_MAX + 1.0)));
  84
  85   date = xbt_os_time() * 1000000 - date;
  86   printf("Creation time  %d size heap : %g\n", size, date);
  87
  88   date = xbt_os_time() * 1000000;
  89   for (j = 0; j < MAX_TEST; j++) {
  90
  91     if (!(j % size) && j)
  92       test_reset_heap(&heap, size);
  93
  94     val = xbt_heap_maxkey(heap);
  95     xbt_heap_pop(heap);
  96     xbt_heap_push(heap, NULL, 3.0 * val);
  97   }
  98   date = xbt_os_time() * 1000000 - date;
  99   printf("Mean access time for a %d size heap : %g\n", size,
 100          date * 1.0 / (MAX_TEST + 0.0));
 101
 102   xbt_heap_free(heap);
 103 }
 104
 105 void test_reset_heap(xbt_heap_t * heap, int size)
 106 {
 107   int i;
 108   xbt_heap_free(*heap);
 109   *heap = xbt_heap_new(size, NULL);
 110
 111   for (i = 0; i < size; i++) {
 112     xbt_heap_push(*heap, NULL, (10.0 * rand() / (RAND_MAX + 1.0)));
 113   }
 114
 115 }
 116
 117 #ifdef __BORLANDC__
 118 #pragma argsused
 119 #endif
 120
 121 int main(int argc, char **argv)
 122 {
 123   int size;
 124   for (size = 100; size < 10000; size *= 10) {
 125     test_heap_validity(size);
 126     test_heap_mean_operation(size);
 127   }
 128   return 0;
 129 }