lib/sorter/old-test.c

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