2 * UCW Library -- Testing the Old Sorter
4 * (c) 2007 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
11 #include "lib/getopt.h"
13 #include "lib/fastbuf.h"
14 #include "lib/ff-binary.h"
15 #include "lib/hashfunc.h"
24 /*** Time measurement ***/
26 static timestamp_t timer;
39 msg(L_INFO, "Test took %.3fs", get_timer(&timer) / 1000.);
42 /*** Simple 4-byte integer keys ***/
48 static inline int s1_compare(struct key1 *x, struct key1 *y)
54 #define SORT_KEY struct key1
55 #define SORT_PREFIX(x) s1_##x
57 #define SORT_OUTPUT_FB
62 #include "lib/sorter.h"
65 test_int(int mode, u64 size)
67 uns N = size ? nextprime(MIN(size/4, 0xffff0000)) : 0;
69 msg(L_INFO, ">>> Integers (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
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);
80 SORT_XTRACE(2, "Verifying");
81 for (uns i=0; i<N; i++)
85 die("Discrepancy: %u instead of %u", j, i);
90 /*** Longer records with hashes (similar to Shepherd's index records) ***/
98 static inline int s3_compare(struct key3 *x, struct key3 *y)
100 /* FIXME: Maybe unroll manually? */
101 for (uns i=0; i<4; i++)
102 COMPARE(x->hash[i], y->hash[i]);
106 #define SORT_KEY struct key3
107 #define SORT_PREFIX(x) s3_##x
108 #define SORT_INPUT_FB
109 #define SORT_OUTPUT_FB
113 #include "lib/sorter.h"
116 gen_hash_key(int mode, struct key3 *k, uns i)
119 k->payload[0] = 7*i + 13;
120 k->payload[1] = 13*i + 19;
121 k->payload[2] = 19*i + 7;
126 k->hash[1] = k->payload[0];
127 k->hash[2] = k->payload[1];
128 k->hash[3] = k->payload[2];
132 k->hash[1] = k->payload[0];
133 k->hash[2] = k->payload[1];
134 k->hash[3] = k->payload[2];
137 struct MD5Context ctx;
139 MD5Update(&ctx, (byte*) &k->i, 4);
140 MD5Final((byte*) &k->hash, &ctx);
146 test_hashes(int mode, u64 size)
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;
152 struct fastbuf *f = bopen_tmp(65536);
154 for (uns i=0; i<N; i++)
156 gen_hash_key(mode, &k, i);
157 hash_sum += k.hash[3];
158 bwrite(f, &k, sizeof(k));
166 SORT_XTRACE(2, "Verifying");
167 for (uns i=0; i<N; i++)
169 int ok = breadb(f, &k, sizeof(k));
171 if (i && s3_compare(&k, &lastk) <= 0)
173 gen_hash_key(mode, &lastk, k.i);
174 if (memcmp(&k, &lastk, sizeof(k)))
176 hash_sum -= k.hash[3];
182 /*** Variable-length records (strings) with and without var-length data ***/
191 static inline int s4_fetch_key(struct fastbuf *f, struct key4 *x)
197 breadb(f, x->s, len);
201 static inline void s4_copy_data(struct fastbuf *i UNUSED, struct fastbuf *f, struct key4 *x)
204 bwrite(f, x->s, x->len);
207 static inline int s4_compare(struct key4 *x, struct key4 *y)
209 uns l = MIN(x->len, y->len);
210 int c = memcmp(x->s, y->s, l);
213 COMPARE(x->len, y->len);
217 static inline byte *s4_fetch_item(struct fastbuf *f UNUSED, struct key4 *x, byte *limit UNUSED)
219 return &x->s[x->len];
222 static inline void s4_store_item(struct fastbuf *f, struct key4 *x)
224 s4_copy_data(NULL, f, x);
227 #define SORT_KEY struct key4
228 #define SORT_PREFIX(x) s4_##x
229 #define SORT_INPUT_FB
230 #define SORT_OUTPUT_FB
233 #include "lib/sorter.h"
235 #define s4b_compare s4_compare
236 #define s4b_fetch_key s4_fetch_key
238 static inline uns s4_data_size(struct key4 *x)
240 return x->len ? (x->s[0] ^ 0xad) : 0;
243 static inline void s4b_copy_data(struct fastbuf *i, struct fastbuf *f, struct key4 *x)
246 bwrite(f, x->s, x->len);
247 bbcopy(i, f, s4_data_size(x));
250 static inline byte *s4b_fetch_item(struct fastbuf *f, struct key4 *x, byte *limit)
252 byte *d = &x->s[x->len];
253 if (d + s4_data_size(x) > limit)
255 breadb(f, d, s4_data_size(x));
256 return d + s4_data_size(x);
259 static inline void s4b_store_item(struct fastbuf *f, struct key4 *x)
262 bwrite(f, x->s, x->len + s4_data_size(x));
265 #define SORT_KEY struct key4
266 #define SORT_PREFIX(x) s4b_##x
267 #define SORT_INPUT_FB
268 #define SORT_OUTPUT_FB
271 #include "lib/sorter.h"
274 gen_key4(struct key4 *k)
276 k->len = random_max(KEY4_MAX);
277 for (uns i=0; i<k->len; i++)
282 gen_data4(byte *buf, uns len, uns h)
292 test_strings(uns mode, u64 size)
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);
299 struct key4 k, lastk;
300 byte buf[256], buf2[256];
303 struct fastbuf *f = bopen_tmp(65536);
304 for (uns i=0; i<N; i++)
307 s4_copy_data(NULL, f, &k);
308 uns h = hash_block(k.s, k.len);
312 gen_data4(buf, s4_data_size(&k), h);
313 bwrite(f, buf, s4_data_size(&k));
319 f = (mode ? s4b_sort : s4_sort)(f);
322 SORT_XTRACE(2, "Verifying");
323 for (uns i=0; i<N; i++)
325 int ok = s4_fetch_key(f, &k);
327 uns h = hash_block(k.s, k.len);
328 if (mode && s4_data_size(&k))
330 ok = breadb(f, buf, s4_data_size(&k));
332 gen_data4(buf2, s4_data_size(&k), h);
333 ASSERT(!memcmp(buf, buf2, s4_data_size(&k)));
335 if (i && s4_compare(&k, &lastk) < 0)
347 run_test(uns i, u64 size)
352 test_int(0, size); break;
354 test_int(1, size); break;
356 test_int(2, size); break;
362 test_hashes(0, size); break;
364 test_hashes(1, size); break;
366 test_hashes(2, size); break;
368 test_strings(0, size); break;
370 test_strings(1, size); break;
376 main(int argc, char **argv)
383 while ((c = cf_getopt(argc, argv, CF_SHORT_OPTS "s:t:v", CF_NO_LONG_OPTS, NULL)) >= 0)
387 if (cf_parse_u64(optarg, &size))
400 fputs("Usage: sort-test [-v] [-s <size>] [-t <test>]\n", stderr);
409 for (uns i=0; i<TMAX; i++)