teshsuite/xbt/heap_bench/heap_bench.c

   1 /* A few tests for the xbt_heap module                                      */
   2
   3 /* Copyright (c) 2004-2010, 2012-2015. 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 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include <xbt/xbt_os_time.h>
  12
  13 #include "xbt/heap.h"
  14 #include "xbt/sysdep.h"         /* calloc, printf */
  15
  16 #define MAX_TEST 1000000
  17
  18 int compare_double(const void *a, const void *b);
  19
  20 void test_heap_validity(int size);
  21 void test_heap_mean_operation(int size);
  22 void test_reset_heap(xbt_heap_t * heap, int size);
  23
  24
  25 int compare_double(const void *a, const void *b)
  26 {
  27   double pa, pb;
  28
  29   pa = *((double *) a);
  30   pb = *((double *) b);
  31
  32   if (pa > pb)
  33     return 1;
  34   if (pa == pb)
  35     return 0;
  36   return -1;
  37 }
  38
  39 void test_heap_validity(int size)
  40 {
  41   xbt_heap_t heap = xbt_heap_new(size, NULL);
  42   double *tab = xbt_new0(double, size);
  43
  44   int i;
  45
  46   for (i = 0; i < size; i++) {
  47     tab[i] = (double) (10.0 * rand() / (RAND_MAX + 1.0));
  48     xbt_heap_push(heap, NULL, (double) tab[i]);
  49   }
  50
  51   qsort(tab, size, sizeof(double), compare_double);
  52
  53   for (i = 0; i < size; i++) {
  54     /*     printf("%g" " ", xbt_heap_maxkey(heap)); */
  55     if (xbt_heap_maxkey(heap) != tab[i]) {
  56       fprintf(stderr, "Problem !\n");
  57       exit(1);
  58     }
  59     xbt_heap_pop(heap);
  60   }
  61   xbt_heap_free(heap);
  62   free(tab);
  63   printf("Validity test complete!\n");
  64 }
  65
  66 void test_heap_mean_operation(int size)
  67 {
  68   xbt_heap_t heap = xbt_heap_new(size, NULL);
  69   double val;
  70   double date = 0;
  71   int i, j;
  72
  73   date = xbt_os_time() * 1000000;
  74   for (i = 0; i < size; i++)
  75     xbt_heap_push(heap, NULL, (10.0 * rand() / (RAND_MAX + 1.0)));
  76
  77   date = xbt_os_time() * 1000000 - date;
  78   printf("Creation time  %d size heap : %g\n", size, date);
  79
  80   date = xbt_os_time() * 1000000;
  81   for (j = 0; j < MAX_TEST; j++) {
  82
  83     if (!(j % size) && j)
  84       test_reset_heap(&heap, size);
  85
  86     val = xbt_heap_maxkey(heap);
  87     xbt_heap_pop(heap);
  88     xbt_heap_push(heap, NULL, 3.0 * val);
  89   }
  90   date = xbt_os_time() * 1000000 - date;
  91   printf("Mean access time for a %d size heap : %g\n", size,
  92          date * 1.0 / (MAX_TEST + 0.0));
  93
  94   xbt_heap_free(heap);
  95 }
  96
  97 void test_reset_heap(xbt_heap_t * heap, int size)
  98 {
  99   int i;
 100   xbt_heap_free(*heap);
 101   *heap = xbt_heap_new(size, NULL);
 102
 103   for (i = 0; i < size; i++) {
 104     xbt_heap_push(*heap, NULL, (10.0 * rand() / (RAND_MAX + 1.0)));
 105   }
 106
 107 }
 108
 109 int main(int argc, char **argv)
 110 {
 111   int size;
 112   for (size = 100; size < 10000; size *= 10) {
 113     test_heap_validity(size);
 114     test_heap_mean_operation(size);
 115   }
 116   return 0;
 117 }