lib/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 "lib/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 void check(void)
  42 {
  43   uns i;
  44   for (i=0; i<N; i++)
  45     if (ASORT_ELT(i) != i)
  46       printf("error at pos %d: %08x != %08x\n", i, ASORT_ELT(i), i);
  47 }
  48
  49 static int qs_comp(const struct elt *X, const struct elt *Y)
  50 {
  51   if (X->key < Y->key)
  52     return -1;
  53   else if (X->key > Y->key)
  54     return 1;
  55   else
  56     return 0;
  57 }
  58
  59 #define ASORT_PREFIX(x) as_##x
  60 #include "lib/arraysort.h"
  61
  62 int main(void)
  63 {
  64   generate();
  65   init_timer();
  66   qsort(array, N, sizeof(array[0]), (int (*)(const void *, const void *)) qs_comp);
  67   printf("qsort: %d ms\n", get_timer());
  68   check();
  69   generate();
  70   init_timer();
  71   as_sort(N);
  72   printf("asort: %d ms\n", get_timer());
  73   check();
  74   return 0;
  75 }