ucw/asort-test.c

   1 /*
   2  *      UCW Library -- Universal Array Sorter Test and Benchmark
   3  *
   4  *      (c) 2003 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include <ucw/lib.h>
  11 #include <ucw/time.h>
  12
  13 #include <stdlib.h>
  14 #include <stdio.h>
  15
  16 #define N 4000037                       /* a prime */
  17
  18 struct elt {
  19   u32 key;
  20   u32 x, y;
  21 };
  22
  23 static struct elt array[N];
  24
  25 #define ASORT_KEY_TYPE u32
  26 #define ASORT_ELT(i) array[i].key
  27 #define ASORT_SWAP(i,j) do { struct elt e=array[j]; array[j]=array[i]; array[i]=e; } while(0)
  28
  29 static void generate(void)
  30 {
  31   uint i;
  32   for (i=0; i<N; i++)
  33 #if 0
  34     ASORT_ELT(i) = N-i-1;
  35 #elif 0
  36     ASORT_ELT(i) = i;
  37 #else
  38     ASORT_ELT(i) = (i ? ASORT_ELT(i-1)+1944833754 : 3141592) % N;
  39 #endif
  40 }
  41
  42 static int errors = 0;
  43
  44 static void check(void)
  45 {
  46   uint i;
  47   for (i=0; i<N; i++)
  48     if (ASORT_ELT(i) != i)
  49     {
  50       printf("error at pos %d: %08x != %08x\n", i, ASORT_ELT(i), i);
  51       errors = 1;
  52     }
  53 }
  54
  55 static int qs_comp(const struct elt *X, const struct elt *Y)
  56 {
  57   if (X->key < Y->key)
  58     return -1;
  59   else if (X->key > Y->key)
  60     return 1;
  61   else
  62     return 0;
  63 }
  64
  65 #define ASORT_PREFIX(x) as_##x
  66 #include <ucw/sorter/array-simple.h>
  67
  68 int main(void)
  69 {
  70   timestamp_t timer;
  71
  72   generate();
  73   init_timer(&timer);
  74   qsort(array, N, sizeof(array[0]), (int (*)(const void *, const void *)) qs_comp);
  75   printf("qsort: %d ms\n", get_timer(&timer));
  76   check();
  77   generate();
  78   init_timer(&timer);
  79   as_sort(N);
  80   printf("asort: %d ms\n", get_timer(&timer));
  81   check();
  82   return errors;
  83 }