]> mj.ucw.cz Git - libucw.git/blob - lib/asort-test.c
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
[libucw.git] / 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   timestamp_t timer;
65
66   generate();
67   init_timer(&timer);
68   qsort(array, N, sizeof(array[0]), (int (*)(const void *, const void *)) qs_comp);
69   printf("qsort: %d ms\n", get_timer(&timer));
70   check();
71   generate();
72   init_timer(&timer);
73   as_sort(N);
74   printf("asort: %d ms\n", get_timer(&timer));
75   check();
76   return 0;
77 }