lib/sorter/sort-test.c

   1 /*
   2  *      UCW Library -- Testing the Sorter
   3  *
   4  *      (c) 2007 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 #include "lib/getopt.h"
  12 #include "lib/fastbuf.h"
  13 #include "lib/md5.h"
  14
  15 #include <stdlib.h>
  16 #include <stdio.h>
  17 #include <string.h>
  18 #include <fcntl.h>
  19
  20 /*** Simple 4-byte integer keys ***/
  21
  22 struct key1 {
  23   u32 x;
  24 };
  25
  26 #define SORT_KEY_REGULAR struct key1
  27 #define SORT_PREFIX(x) s1_##x
  28 #define SORT_INPUT_FB
  29 #define SORT_OUTPUT_FB
  30 #define SORT_UNIQUE
  31 #define SORT_INT(k) (k).x
  32
  33 #include "lib/sorter/sorter.h"
  34
  35 static void
  36 test_int(int mode, uns N)
  37 {
  38   N = nextprime(N);
  39   uns K = N/4*3;
  40   log(L_INFO, "Integers (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
  41
  42   struct fastbuf *f = bopen_tmp(65536);
  43   for (uns i=0; i<N; i++)
  44     bputl(f, (mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N);
  45   brewind(f);
  46
  47   log(L_INFO, "Sorting");
  48   f = s1_sort(f, NULL, N-1);
  49
  50   log(L_INFO, "Verifying");
  51   for (uns i=0; i<N; i++)
  52     {
  53       uns j = bgetl(f);
  54       if (i != j)
  55         die("Discrepancy: %d instead of %d", j, i);
  56     }
  57   bclose(f);
  58 }
  59
  60 /*** Integers with merging, but no data ***/
  61
  62 struct key2 {
  63   u32 x;
  64   u32 cnt;
  65 };
  66
  67 static inline void s2_write_merged(struct fastbuf *f, struct key2 **k, void **d UNUSED, uns n, void *buf UNUSED)
  68 {
  69   for (uns i=1; i<n; i++)
  70     k[0]->cnt += k[i]->cnt;
  71   bwrite(f, k[0], sizeof(struct key2));
  72 }
  73
  74 static inline void s2_copy_merged(struct key2 **k, struct fastbuf **d UNUSED, uns n, struct fastbuf *dest)
  75 {
  76   for (uns i=1; i<n; i++)
  77     k[0]->cnt += k[i]->cnt;
  78   bwrite(dest, k[0], sizeof(struct key2));
  79 }
  80
  81 #define SORT_KEY_REGULAR struct key2
  82 #define SORT_PREFIX(x) s2_##x
  83 #define SORT_INPUT_FB
  84 #define SORT_OUTPUT_FB
  85 #define SORT_UNIFY
  86 #define SORT_INT(k) (k).x
  87
  88 #include "lib/sorter/sorter.h"
  89
  90 static void
  91 test_counted(int mode, uns N)
  92 {
  93   N = nextprime(N/4);
  94   uns K = N/4*3;
  95   log(L_INFO, "Counted integers (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
  96
  97   struct fastbuf *f = bopen_tmp(65536);
  98   for (uns i=0; i<2*N; i++)
  99     for (uns j=0; j<2; j++)
 100       {
 101         bputl(f, (mode==0) ? (i%N) : (mode==1) ? N-1-(i%N) : ((u64)i * K + 17) % N);
 102         bputl(f, 1);
 103       }
 104   brewind(f);
 105
 106   log(L_INFO, "Sorting");
 107   f = s2_sort(f, NULL, N-1);
 108
 109   log(L_INFO, "Verifying");
 110   for (uns i=0; i<N; i++)
 111     {
 112       uns j = bgetl(f);
 113       if (i != j)
 114         die("Discrepancy: %d instead of %d", j, i);
 115       uns k = bgetl(f);
 116       if (k != 4)
 117         die("Discrepancy: %d has count %d instead of 4", j, k);
 118     }
 119   bclose(f);
 120 }
 121
 122 /*** Longer records with hashes (similar to Shepherd's index records) ***/
 123
 124 struct key3 {
 125   u32 hash[4];
 126   u32 i;
 127   u32 payload[3];
 128 };
 129
 130 static inline int s3_compare(struct key3 *x, struct key3 *y)
 131 {
 132   /* FIXME: Maybe unroll manually? */
 133   for (uns i=0; i<4; i++)
 134     if (x->hash[i] < y->hash[i])
 135       return -1;
 136     else if (x->hash[i] > y->hash[i])
 137       return 1;
 138   return 0;
 139 }
 140
 141 static inline uns s3_hash(struct key3 *x)
 142 {
 143   return x->hash[0];
 144 }
 145
 146 #define SORT_KEY_REGULAR struct key3
 147 #define SORT_PREFIX(x) s3_##x
 148 #define SORT_INPUT_FB
 149 #define SORT_OUTPUT_FB
 150 #define SORT_HASH_BITS 32
 151
 152 #include "lib/sorter/sorter.h"
 153
 154 static void
 155 gen_hash_key(int mode, struct key3 *k, uns i)
 156 {
 157   k->i = i;
 158   k->payload[0] = 7*i + 13;
 159   k->payload[1] = 13*i + 19;
 160   k->payload[2] = 19*i + 7;
 161   switch (mode)
 162     {
 163     case 0:
 164       k->hash[0] = i;
 165       k->hash[1] = k->payload[0];
 166       k->hash[2] = k->payload[1];
 167       k->hash[3] = k->payload[2];
 168       break;
 169     case 1:
 170       k->hash[0] = ~i;
 171       k->hash[1] = k->payload[0];
 172       k->hash[2] = k->payload[1];
 173       k->hash[3] = k->payload[2];
 174       break;
 175     default: ;
 176       struct MD5Context ctx;
 177       MD5Init(&ctx);
 178       MD5Update(&ctx, (byte*) &k->i, 4);
 179       MD5Final((byte*) &k->hash, &ctx);
 180       break;
 181     }
 182 }
 183
 184 static void
 185 test_hashes(int mode, uns N)
 186 {
 187   log(L_INFO, "Hashes (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
 188   struct key3 k, lastk;
 189
 190   struct fastbuf *f = bopen_tmp(65536);
 191   uns hash_sum = 0;
 192   for (uns i=0; i<N; i++)
 193     {
 194       gen_hash_key(mode, &k, i);
 195       hash_sum += k.hash[3];
 196       bwrite(f, &k, sizeof(k));
 197     }
 198   brewind(f);
 199
 200   log(L_INFO, "Sorting");
 201   f = s3_sort(f, NULL);
 202
 203   log(L_INFO, "Verifying");
 204   for (uns i=0; i<N; i++)
 205     {
 206       int ok = breadb(f, &k, sizeof(k));
 207       ASSERT(ok);
 208       if (i && s3_compare(&k, &lastk) <= 0)
 209         ASSERT(0);
 210       gen_hash_key(mode, &lastk, k.i);
 211       if (memcmp(&k, &lastk, sizeof(k)))
 212         ASSERT(0);
 213       hash_sum -= k.hash[3];
 214     }
 215   ASSERT(!hash_sum);
 216   bclose(f);
 217 }
 218
 219 int
 220 main(int argc, char **argv)
 221 {
 222   log_init(NULL);
 223   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 ||
 224       optind != argc)
 225   {
 226     fputs("This program supports only the following command-line arguments:\n" CF_USAGE, stderr);
 227     exit(1);
 228   }
 229
 230   uns N = 1000000;
 231   test_int(0, N);
 232   test_int(1, N);
 233   test_int(2, N);
 234   test_counted(0, N);
 235   test_counted(1, N);
 236   test_counted(2, N);
 237   test_hashes(0, N);
 238   test_hashes(1, N);
 239   test_hashes(2, N);
 240
 241   return 0;
 242 }