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