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