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
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14
  15 #define N 4000037                       /* a prime */
  16
  17 struct elt {
  18   u32 key;
  19   u32 x, y;
  20 };
  21
  22 static struct elt array[N];
  23
  24 #define ASORT_KEY_TYPE u32
  25 #define ASORT_ELT(i) array[i].key
  26 #define ASORT_SWAP(i,j) do { struct elt e=array[j]; array[j]=array[i]; array[i]=e; } while(0)
  27
  28 static void generate(void)
  29 {
  30   uns i;
  31   for (i=0; i<N; i++)
  32 #if 0
  33     ASORT_ELT(i) = N-i-1;
  34 #elif 0
  35     ASORT_ELT(i) = i;
  36 #else
  37     ASORT_ELT(i) = (i ? ASORT_ELT(i-1)+1944833754 : 3141592) % N;
  38 #endif
  39 }
  40
  41 static int errors = 0;
  42
  43 static void check(void)
  44 {
  45   uns i;
  46   for (i=0; i<N; i++)
  47     if (ASORT_ELT(i) != i)
  48     {
  49       printf("error at pos %d: %08x != %08x\n", i, ASORT_ELT(i), i);
  50       errors = 1;
  51     }
  52 }
  53
  54 static int qs_comp(const struct elt *X, const struct elt *Y)
  55 {
  56   if (X->key < Y->key)
  57     return -1;
  58   else if (X->key > Y->key)
  59     return 1;
  60   else
  61     return 0;
  62 }
  63
  64 #define ASORT_PREFIX(x) as_##x
  65 #include "ucw/arraysort.h"
  66
  67 int main(void)
  68 {
  69   timestamp_t timer;
  70
  71   generate();
  72   init_timer(&timer);
  73   qsort(array, N, sizeof(array[0]), (int (*)(const void *, const void *)) qs_comp);
  74   printf("qsort: %d ms\n", get_timer(&timer));
  75   check();
  76   generate();
  77   init_timer(&timer);
  78   as_sort(N);
  79   printf("asort: %d ms\n", get_timer(&timer));
  80   check();
  81   return errors;
  82 }