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/hashfunc.h"
  14 #include "lib/md5.h"
  15
  16 #include <stdlib.h>
  17 #include <stdio.h>
  18 #include <string.h>
  19 #include <fcntl.h>
  20
  21 /*** Simple 4-byte integer keys ***/
  22
  23 struct key1 {
  24   u32 x;
  25 };
  26
  27 #define SORT_KEY_REGULAR struct key1
  28 #define SORT_PREFIX(x) s1_##x
  29 #define SORT_INPUT_FB
  30 #define SORT_OUTPUT_FB
  31 #define SORT_UNIQUE
  32 #define SORT_INT(k) (k).x
  33
  34 #include "lib/sorter/sorter.h"
  35
  36 static void
  37 test_int(int mode, uns N)
  38 {
  39   N = nextprime(N);
  40   uns K = N/4*3;
  41   log(L_INFO, "Integers (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
  42
  43   struct fastbuf *f = bopen_tmp(65536);
  44   for (uns i=0; i<N; i++)
  45     bputl(f, (mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N);
  46   brewind(f);
  47
  48   log(L_INFO, "Sorting");
  49   f = s1_sort(f, NULL, N-1);
  50
  51   log(L_INFO, "Verifying");
  52   for (uns i=0; i<N; i++)
  53     {
  54       uns j = bgetl(f);
  55       if (i != j)
  56         die("Discrepancy: %d instead of %d", j, i);
  57     }
  58   bclose(f);
  59 }
  60
  61 /*** Integers with merging, but no data ***/
  62
  63 struct key2 {
  64   u32 x;
  65   u32 cnt;
  66 };
  67
  68 static inline void s2_write_merged(struct fastbuf *f, struct key2 **k, void **d UNUSED, uns n, void *buf UNUSED)
  69 {
  70   for (uns i=1; i<n; i++)
  71     k[0]->cnt += k[i]->cnt;
  72   bwrite(f, k[0], sizeof(struct key2));
  73 }
  74
  75 static inline void s2_copy_merged(struct key2 **k, struct fastbuf **d UNUSED, uns n, struct fastbuf *dest)
  76 {
  77   for (uns i=1; i<n; i++)
  78     k[0]->cnt += k[i]->cnt;
  79   bwrite(dest, k[0], sizeof(struct key2));
  80 }
  81
  82 #define SORT_KEY_REGULAR struct key2
  83 #define SORT_PREFIX(x) s2_##x
  84 #define SORT_INPUT_FB
  85 #define SORT_OUTPUT_FB
  86 #define SORT_UNIFY
  87 #define SORT_INT(k) (k).x
  88
  89 #include "lib/sorter/sorter.h"
  90
  91 static void
  92 test_counted(int mode, uns N)
  93 {
  94   N = nextprime(N/4);
  95   uns K = N/4*3;
  96   log(L_INFO, "Counted integers (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
  97
  98   struct fastbuf *f = bopen_tmp(65536);
  99   for (uns i=0; i<2*N; i++)
 100     for (uns j=0; j<2; j++)
 101       {
 102         bputl(f, (mode==0) ? (i%N) : (mode==1) ? N-1-(i%N) : ((u64)i * K + 17) % N);
 103         bputl(f, 1);
 104       }
 105   brewind(f);
 106
 107   log(L_INFO, "Sorting");
 108   f = s2_sort(f, NULL, N-1);
 109
 110   log(L_INFO, "Verifying");
 111   for (uns i=0; i<N; i++)
 112     {
 113       uns j = bgetl(f);
 114       if (i != j)
 115         die("Discrepancy: %d instead of %d", j, i);
 116       uns k = bgetl(f);
 117       if (k != 4)
 118         die("Discrepancy: %d has count %d instead of 4", j, k);
 119     }
 120   bclose(f);
 121 }
 122
 123 /*** Longer records with hashes (similar to Shepherd's index records) ***/
 124
 125 struct key3 {
 126   u32 hash[4];
 127   u32 i;
 128   u32 payload[3];
 129 };
 130
 131 static inline int s3_compare(struct key3 *x, struct key3 *y)
 132 {
 133   /* FIXME: Maybe unroll manually? */
 134   for (uns i=0; i<4; i++)
 135     COMPARE(x->hash[i], y->hash[i]);
 136   return 0;
 137 }
 138
 139 static inline uns s3_hash(struct key3 *x)
 140 {
 141   return x->hash[0];
 142 }
 143
 144 #define SORT_KEY_REGULAR struct key3
 145 #define SORT_PREFIX(x) s3_##x
 146 #define SORT_INPUT_FB
 147 #define SORT_OUTPUT_FB
 148 #define SORT_HASH_BITS 32
 149
 150 #include "lib/sorter/sorter.h"
 151
 152 static void
 153 gen_hash_key(int mode, struct key3 *k, uns i)
 154 {
 155   k->i = i;
 156   k->payload[0] = 7*i + 13;
 157   k->payload[1] = 13*i + 19;
 158   k->payload[2] = 19*i + 7;
 159   switch (mode)
 160     {
 161     case 0:
 162       k->hash[0] = i;
 163       k->hash[1] = k->payload[0];
 164       k->hash[2] = k->payload[1];
 165       k->hash[3] = k->payload[2];
 166       break;
 167     case 1:
 168       k->hash[0] = ~i;
 169       k->hash[1] = k->payload[0];
 170       k->hash[2] = k->payload[1];
 171       k->hash[3] = k->payload[2];
 172       break;
 173     default: ;
 174       struct MD5Context ctx;
 175       MD5Init(&ctx);
 176       MD5Update(&ctx, (byte*) &k->i, 4);
 177       MD5Final((byte*) &k->hash, &ctx);
 178       break;
 179     }
 180 }
 181
 182 static void
 183 test_hashes(int mode, uns N)
 184 {
 185   log(L_INFO, "Hashes (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
 186   struct key3 k, lastk;
 187
 188   struct fastbuf *f = bopen_tmp(65536);
 189   uns hash_sum = 0;
 190   for (uns i=0; i<N; i++)
 191     {
 192       gen_hash_key(mode, &k, i);
 193       hash_sum += k.hash[3];
 194       bwrite(f, &k, sizeof(k));
 195     }
 196   brewind(f);
 197
 198   log(L_INFO, "Sorting");
 199   f = s3_sort(f, NULL);
 200
 201   log(L_INFO, "Verifying");
 202   for (uns i=0; i<N; i++)
 203     {
 204       int ok = breadb(f, &k, sizeof(k));
 205       ASSERT(ok);
 206       if (i && s3_compare(&k, &lastk) <= 0)
 207         ASSERT(0);
 208       gen_hash_key(mode, &lastk, k.i);
 209       if (memcmp(&k, &lastk, sizeof(k)))
 210         ASSERT(0);
 211       hash_sum -= k.hash[3];
 212     }
 213   ASSERT(!hash_sum);
 214   bclose(f);
 215 }
 216
 217 /*** Variable-length records (strings) with and without var-length data ***/
 218
 219 #define KEY4_MAX 256
 220
 221 struct key4 {
 222   uns len;
 223   byte s[KEY4_MAX];
 224 };
 225
 226 static inline int s4_compare(struct key4 *x, struct key4 *y)
 227 {
 228   uns l = MIN(x->len, y->len);
 229   int c = memcmp(x->s, y->s, l);
 230   if (c)
 231     return c;
 232   COMPARE(x->len, y->len);
 233   return 0;
 234 }
 235
 236 static inline int s4_read_key(struct fastbuf *f, struct key4 *x)
 237 {
 238   x->len = bgetl(f);
 239   if (x->len == 0xffffffff)
 240     return 0;
 241   ASSERT(x->len < KEY4_MAX);
 242   breadb(f, x->s, x->len);
 243   return 1;
 244 }
 245
 246 static inline void s4_write_key(struct fastbuf *f, struct key4 *x)
 247 {
 248   ASSERT(x->len < KEY4_MAX);
 249   bputl(f, x->len);
 250   bwrite(f, x->s, x->len);
 251 }
 252
 253 #define SORT_KEY struct key4
 254 #define SORT_PREFIX(x) s4_##x
 255 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
 256 #define SORT_INPUT_FB
 257 #define SORT_OUTPUT_FB
 258
 259 #include "lib/sorter/sorter.h"
 260
 261 #define s4b_compare s4_compare
 262 #define s4b_read_key s4_read_key
 263 #define s4b_write_key s4_write_key
 264
 265 static inline uns s4_data_size(struct key4 *x)
 266 {
 267   return x->len ? (x->s[0] ^ 0xad) : 0;
 268 }
 269
 270 #define SORT_KEY struct key4
 271 #define SORT_PREFIX(x) s4b_##x
 272 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
 273 #define SORT_DATA_SIZE(x) s4_data_size(&(x))
 274 #define SORT_INPUT_FB
 275 #define SORT_OUTPUT_FB
 276
 277 #include "lib/sorter/sorter.h"
 278
 279 static void
 280 gen_key4(struct key4 *k)
 281 {
 282   k->len = random_max(KEY4_MAX);
 283   for (uns i=0; i<k->len; i++)
 284     k->s[i] = random();
 285 }
 286
 287 static void
 288 gen_data4(byte *buf, uns len, uns h)
 289 {
 290   while (len--)
 291     {
 292       *buf++ = h >> 24;
 293       h = h*259309 + 17;
 294     }
 295 }
 296
 297 static void
 298 test_strings(uns mode, uns N)
 299 {
 300   log(L_INFO, "Strings %s(N=%d)", (mode ? "with data " : ""), N);
 301   srand(1);
 302
 303   struct key4 k, lastk;
 304   byte buf[256], buf2[256];
 305   uns sum = 0;
 306
 307   struct fastbuf *f = bopen_tmp(65536);
 308   for (uns i=0; i<N; i++)
 309     {
 310       gen_key4(&k);
 311       s4_write_key(f, &k);
 312       uns h = hash_block(k.s, k.len);
 313       sum += h;
 314       if (mode)
 315         {
 316           gen_data4(buf, s4_data_size(&k), h);
 317           bwrite(f, buf, s4_data_size(&k));
 318         }
 319     }
 320   brewind(f);
 321
 322   log(L_INFO, "Sorting");
 323   f = (mode ? s4b_sort : s4_sort)(f, NULL);
 324
 325   log(L_INFO, "Verifying");
 326   for (uns i=0; i<N; i++)
 327     {
 328       int ok = s4_read_key(f, &k);
 329       ASSERT(ok);
 330       uns h = hash_block(k.s, k.len);
 331       if (mode && s4_data_size(&k))
 332         {
 333           ok = breadb(f, buf, s4_data_size(&k));
 334           ASSERT(ok);
 335           gen_data4(buf2, s4_data_size(&k), h);
 336           ASSERT(!memcmp(buf, buf2, s4_data_size(&k)));
 337         }
 338       if (i && s4_compare(&k, &lastk) < 0)
 339         ASSERT(0);
 340       sum -= h;
 341       lastk = k;
 342     }
 343   ASSERT(!sum);
 344   bclose(f);
 345 }
 346
 347 int
 348 main(int argc, char **argv)
 349 {
 350   log_init(NULL);
 351   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 ||
 352       optind != argc)
 353   {
 354     fputs("This program supports only the following command-line arguments:\n" CF_USAGE, stderr);
 355     exit(1);
 356   }
 357
 358   uns N = 100000;
 359 #if 0
 360   test_int(0, N);
 361   test_int(1, N);
 362   test_int(2, N);
 363   test_counted(0, N);
 364   test_counted(1, N);
 365   test_counted(2, N);
 366   test_hashes(0, N);
 367   test_hashes(1, N);
 368   test_hashes(2, N);
 369   test_strings(0, N);
 370 #endif
 371   test_strings(1, N);
 372
 373   return 0;
 374 }