From a1f74b39f32118bc29bd83e73564143000aeb951 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 8 Sep 2007 16:20:16 +0200 Subject: [PATCH] The old sorter is gone. --- lib/Makefile | 5 +- lib/sort-test.c | 90 ------- lib/sorter-globals.h | 19 -- lib/sorter.c | 13 - lib/sorter.h | 562 ------------------------------------------ lib/sorter/Makefile | 8 +- lib/sorter/old-test.c | 413 ------------------------------- 7 files changed, 8 insertions(+), 1102 deletions(-) delete mode 100644 lib/sort-test.c delete mode 100644 lib/sorter-globals.h delete mode 100644 lib/sorter.c delete mode 100644 lib/sorter.h delete mode 100644 lib/sorter/old-test.c diff --git a/lib/Makefile b/lib/Makefile index c204d6e6..2ee53e14 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -12,7 +12,7 @@ LIBUCW_MODS= \ threads \ alloc alloc_str realloc bigalloc mempool mempool-str mempool-fmt eltpool \ mmap pagecache partmap hashfunc \ - lists slists simple-lists sorter bitsig \ + lists slists simple-lists bitsig \ log log-file proctitle \ conf-alloc conf-dump conf-input conf-intr conf-journal conf-parse conf-section \ ipaccess \ @@ -38,7 +38,7 @@ LIBUCW_MODS= \ LIBUCW_INCLUDES= \ lib.h config.h threads.h \ mempool.h pagecache.h \ - sorter.h sorter-globals.h arraysort.h \ + arraysort.h \ lists.h clists.h slists.h simple-lists.h \ unaligned.h prefetch.h \ bbuf.h gbuf.h bitarray.h bitsig.h \ @@ -89,7 +89,6 @@ $(o)/lib/lizard.o: CFLAGS += $(COPT2) -funroll-loops $(o)/lib/db-test: $(o)/lib/db-test.o $(LIBUCW) $(o)/lib/db-tool: $(o)/lib/db-tool.o $(LIBUCW) $(o)/lib/conf-test: $(o)/lib/conf-test.o $(LIBUCW) -$(o)/lib/sort-test: $(o)/lib/sort-test.o $(LIBUCW) $(o)/lib/lfs-test: $(o)/lib/lfs-test.o $(LIBUCW) $(o)/lib/hash-test: $(o)/lib/hash-test.o $(LIBUCW) $(o)/lib/str-test: $(o)/lib/str-test.o $(LIBUCW) diff --git a/lib/sort-test.c b/lib/sort-test.c deleted file mode 100644 index c3a48c8c..00000000 --- a/lib/sort-test.c +++ /dev/null @@ -1,90 +0,0 @@ -/* Test for sorting routines */ - -#include "lib/lib.h" -#include "lib/getopt.h" -#include "lib/fastbuf.h" - -#include -#include -#include - -struct key { - char line[4096]; -}; - -#define SORT_KEY struct key -#define SORT_PREFIX(x) s_##x -#define SORT_PRESORT -#define SORT_INPUT_FILE -#define SORT_OUTPUT_FILE -#define SORT_UNIFY - -static inline int -s_compare(struct key *a, struct key *b) -{ - return strcmp(a->line, b->line); -} - -static inline int -s_fetch_key(struct fastbuf *f, struct key *a) -{ - return !!bgets(f, a->line, sizeof(a->line)); -} - -static inline void -s_copy_data(struct fastbuf *src UNUSED, struct fastbuf *dest, struct key *k) -{ - bputsn(dest, k->line); -} - -static inline byte * -s_fetch_item(struct fastbuf *src UNUSED, struct key *k, byte *limit UNUSED) -{ - byte *end = (byte *) k->line + strlen(k->line) + 1; -#if 0 /* Testing splits */ - uns r = random_max(10000); - if (end + r <= limit) - return end + r; - else - return NULL; -#else - return end; -#endif -} - -static inline void -s_store_item(struct fastbuf *f, struct key *k) -{ - s_copy_data(NULL, f, k); -} - -#ifdef SORT_UNIFY -static inline void -s_merge_data(struct fastbuf *src1 UNUSED, struct fastbuf *src2 UNUSED, struct fastbuf *dest, struct key *k1, struct key *k2 UNUSED) -{ - s_copy_data(NULL, dest, k1); -} - -static inline struct key * -s_merge_items(struct key *a, struct key *b UNUSED) -{ - return a; -} -#endif - -#include "lib/sorter.h" - -int -main(int argc, char **argv) -{ - log_init(NULL); - if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || - optind != argc - 2) - { - fputs("This program supports only the following command-line arguments:\n" CF_USAGE, stderr); - exit(1); - } - - s_sort(argv[optind], argv[optind+1]); - return 0; -} diff --git a/lib/sorter-globals.h b/lib/sorter-globals.h deleted file mode 100644 index de649b34..00000000 --- a/lib/sorter-globals.h +++ /dev/null @@ -1,19 +0,0 @@ -/* - * UCW Library -- Universal Sorter: Global Variables - * - * (c) 2001--2004 Martin Mares - * (c) 2004 Robert Spalek - * - * This software may be freely distributed and used according to the terms - * of the GNU Lesser General Public License. - */ - -#ifndef _UCW_SORTER_GLOBALS_H -#define _UCW_SORTER_GLOBALS_H - -/* The old sorter shares configuration with the new one */ -#include "lib/sorter/common.h" - -extern uns sorter_pass_counter; - -#endif diff --git a/lib/sorter.c b/lib/sorter.c deleted file mode 100644 index 20db9ef1..00000000 --- a/lib/sorter.c +++ /dev/null @@ -1,13 +0,0 @@ -/* - * UCW Library -- Universal Sorter - * - * (c) 2001--2002 Martin Mares - * - * This software may be freely distributed and used according to the terms - * of the GNU Lesser General Public License. - */ - -#include "lib/lib.h" -#include "lib/sorter-globals.h" - -uns sorter_pass_counter; diff --git a/lib/sorter.h b/lib/sorter.h deleted file mode 100644 index 4cc8c995..00000000 --- a/lib/sorter.h +++ /dev/null @@ -1,562 +0,0 @@ -/* - * UCW Library -- Universal Sorter - * - * (c) 2001--2004 Martin Mares - * (c) 2004 Robert Spalek - * - * This software may be freely distributed and used according to the terms - * of the GNU Lesser General Public License. - */ - -/* - * This is not a normal header file, it's a generator of sorting - * routines. Each time you include it with parameters set in the - * corresponding preprocessor macros, it generates a file sorter - * with the parameters given. - * - * Recognized parameter macros: (those marked with [*] are mandatory) - * - * SORT_KEY [*] data type capable of storing a single key - * SORT_PREFIX(x) [*] add a name prefix (used on all global names - * defined by the sorter) - * SORT_PRESORT include an in-core pre-sorting pass. Beware, when in - * the pre-sorting mode, it's quite possible that the - * comparison function will be called with both arguments - * identical. - * SORT_UP_TO a C expression, if defined, sorting is stopped after the - * average run length in the file exceeds the value of this - * expression (in bytes) - * SORT_UNIFY merge items with identical keys - * SORT_UNIQUE all items have distinct keys (checked in debug mode) - * SORT_REGULAR all items are equally long and they don't contain - * anything else than the key. In this case, the sorter - * automatically supplies fetch_key, copy_data, fetch_item - * and store_item functions. Item size is also expected - * to be small. - * SORT_DELETE_INPUT a C expression, if true, the input files are - * deleted as soon as possible - * SORT_INPUT_FILE input is a file with this name - * SORT_INPUT_FB input is a fastbuf stream - * (can be safely NULL if you want to treat original - * input in a different way by file read functions) - * SORT_INPUT_FBPAIR input is a pair of fastbuf streams - * (not supported by the presorter) - * SORT_OUTPUT_FILE output is a file with this name - * SORT_OUTPUT_FB output is a temporary fastbuf stream - * - * You also need to define some (usually inline) functions which - * are called by the sorter to process your data: - * - * int PREFIX_compare(SORT_KEY *a, *b) - * compare two keys, result like strcmp - * int PREFIX_fetch_key(struct fastbuf *f, SORT_KEY *k) - * fetch next key, returns nonzero=ok, 0=eof - * void PREFIX_copy_data(struct fastbuf *src, *dest, SORT_KEY *k) - * write just fetched key k to dest and copy all data - * belonging to this key from src to dest. - * void PREFIX_merge_data(struct fastbuf *src1, *src2, *dest, SORT_KEY *k1, *k2) - * [used only in case SORT_UNIFY is defined] - * write just fetched key k to dest and merge data from - * two records with the same key (k1 and k2 are key occurences - * in the corresponding streams). - * byte * PREFIX_fetch_item(struct fastbuf *f, SORT_KEY *k, byte *limit) - * [used only with SORT_PRESORT] - * fetch data belonging to a just fetched key and store - * them to memory following the key, but not over limit. - * Returns a pointer to first byte after the data - * or NULL if the data don't fit. For variable-length - * keys, it can use the rest of SORT_KEY and even return - * pointer before end of the key. - * Important: before PREFIX_fetch_item() succeeds, the key - * must be position independent, the sorter can copy it. - * void PREFIX_store_item(struct fastbuf *f, SORT_KEY *k) - * [used only with SORT_PRESORT] - * write key and all its data read with PREFIX_fetch_data - * to the stream given. - * SORT_KEY * PREFIX_merge_items(SORT_KEY *a, SORT_KEY *b) - * [used only with SORT_PRESORT && SORT_UNIFY] - * merge two items with the same key, returns pointer - * to at most one of the items, the rest will be removed - * from the list of items, but not deallocated, so - * the remaining item can freely reference data of the - * other one. - * - * After including this file, all parameter macros are automatically - * undef'd. - */ - -#include "lib/sorter-globals.h" -#include "lib/fastbuf.h" -#include -#include -#include - -#if !defined(SORT_KEY) || !defined(SORT_PREFIX) -#error Some of the mandatory configuration macros are missing. -#endif - -#define P(x) SORT_PREFIX(x) -#define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0) - -#if defined(SORT_UNIFY) || defined(SORT_UNIQUE) -#define LESS < -#else -#define LESS <= -#endif - -#if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS) -#define SORT_ASSERT_UNIQUE -#endif - -#ifdef SORT_REGULAR - -static inline int -P(fetch_key)(struct fastbuf *in, SORT_KEY *x) -{ - return breadb(in, x, sizeof(*x)); -} - -static inline void -P(copy_data)(struct fastbuf *in UNUSED, struct fastbuf *out, SORT_KEY *x) -{ - bwrite(out, x, sizeof(*x)); -} - -static inline byte * -P(fetch_item)(struct fastbuf *in UNUSED, SORT_KEY *x UNUSED, byte *limit UNUSED) -{ - return (byte *)(x+1); -} - -static inline void -P(store_item)(struct fastbuf *out, SORT_KEY *x) -{ - bwrite(out, x, sizeof(*x)); -} - -#endif - -static struct fastbuf * -P(flush_out)(struct fastbuf *out) -{ - if (out) - brewind(out); - return out; -} - -static uns -P(pass)(struct fastbuf **fb1, struct fastbuf **fb2 -#ifdef SORT_UP_TO - , uns stop_sorting -#endif -) -{ - struct fastbuf *in1 = *fb1; - struct fastbuf *in2 = *fb2; - struct fastbuf *out1 = NULL; - struct fastbuf *out2 = NULL; - SORT_KEY kbuf1, kbuf2, kbuf3, kbuf4; - SORT_KEY *kin1 = &kbuf1; - SORT_KEY *kprev1 = &kbuf2; - SORT_KEY *kin2 = &kbuf3; - SORT_KEY *kprev2 = &kbuf4; - SORT_KEY *kout = NULL; - SORT_KEY *ktmp; - int next1, next2, comp; - int run1, run2; - uns run_count = 0; - - run1 = next1 = in1 ? P(fetch_key)(in1, kin1) : 0; - run2 = next2 = in2 ? P(fetch_key)(in2, kin2) : 0; - while (next1 || next2) - { - if (!run1) - comp = 1; - else if (!run2) - comp = -1; - else - comp = P(compare)(kin1, kin2); - ktmp = (comp <= 0) ? kin1 : kin2; - if (!kout || !(P(compare)(kout, ktmp) LESS 0)) - { - struct fastbuf *t; -#ifdef SORT_UP_TO - if (!stop_sorting) -#endif - SWAP(out1, out2, t); - if (!out1) - out1 = bopen_tmp(sorter_stream_bufsize); - run_count++; - } - if (comp LESS 0) - { - P(copy_data)(in1, out1, kin1); - SWAP(kin1, kprev1, ktmp); - next1 = P(fetch_key)(in1, kin1); - run1 = next1 && (P(compare)(kprev1, kin1) LESS 0); - kout = kprev1; - } -#ifdef SORT_UNIFY - else if (comp == 0) - { - P(merge_data)(in1, in2, out1, kin1, kin2); - SWAP(kin1, kprev1, ktmp); - next1 = P(fetch_key)(in1, kin1); - run1 = next1 && (P(compare)(kprev1, kin1) LESS 0); - SWAP(kin2, kprev2, ktmp); - next2 = P(fetch_key)(in2, kin2); - run2 = next2 && (P(compare)(kprev2, kin2) LESS 0); - kout = kprev2; - } -#endif -#ifdef SORT_ASSERT_UNIQUE - else if (unlikely(comp == 0)) - ASSERT(0); -#endif - else - { - P(copy_data)(in2, out1, kin2); - SWAP(kin2, kprev2, ktmp); - next2 = P(fetch_key)(in2, kin2); - run2 = next2 && (P(compare)(kprev2, kin2) LESS 0); - kout = kprev2; - } - if (!run1 && !run2) - { - run1 = next1; - run2 = next2; - } - } - bclose(in1); - bclose(in2); - if (sorter_trace) - msg(L_INFO, "Pass %d: %d runs, %d+%d KB", sorter_pass_counter, run_count, - (out1 ? (int)((btell(out1) + 1023) / 1024) : 0), - (out2 ? (int)((btell(out2) + 1023) / 1024) : 0)); - *fb1 = P(flush_out)(out1); - *fb2 = P(flush_out)(out2); - sorter_pass_counter++; - return run_count; -} - -#ifdef SORT_PRESORT - -#if defined(SORT_REGULAR) && !defined(SORT_UNIFY) - -/* If we are doing a simple sort on a regular file, we can use a faster presorting strategy */ - -static SORT_KEY *P(array); - -#define ASORT_PREFIX(x) SORT_PREFIX(x##_array) -#define ASORT_KEY_TYPE SORT_KEY -#define ASORT_ELT(i) P(array)[i] -#define ASORT_LT(x,y) (P(compare)(&(x),&(y)) < 0) - -#include "lib/arraysort.h" - -static void -P(presort)(struct fastbuf **fb1, struct fastbuf **fb2) -{ - struct fastbuf *in = *fb1; - struct fastbuf *out1 = NULL; - struct fastbuf *out2 = NULL; - struct fastbuf *tbuf; - uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY); - uns run_count = 0; - SORT_KEY last_out = { }, *array; - - ASSERT(!*fb2); - if (buf_items < 2) - die("PresortBuffer set too low"); - P(array) = array = xmalloc(buf_items * sizeof(SORT_KEY)); - - for(;;) - { - uns s = bread(in, array, buf_items * sizeof(SORT_KEY)); - uns n = s / sizeof(SORT_KEY); - ASSERT(!(s % sizeof(SORT_KEY))); - if (!n) - break; - P(sort_array)(n); -#ifdef SORT_ASSERT_UNIQUE - for (uns i=0; i= 0)) - ASSERT(0); - ASSERT(!run_count || P(compare)(&last_out, &array[0])); -#endif - if (!run_count || P(compare)(&last_out, &array[0]) > 0) - { - run_count++; -#ifdef SORT_UP_TO - if (sorter_presort_bufsize < (uns) SORT_UP_TO) -#endif - SWAP(out1, out2, tbuf); - if (!out1) - out1 = bopen_tmp(sorter_stream_bufsize); - } - last_out = array[n-1]; - bwrite(out1, array, n * sizeof(SORT_KEY)); - } - - bclose(in); - if (sorter_trace) - msg(L_INFO, "Pass 0: %d runs, %d+%d KB", - run_count, - (out1 ? (int)((btell(out1) + 1023) / 1024) : 0), - (out2 ? (int)((btell(out2) + 1023) / 1024) : 0)); - *fb1 = P(flush_out)(out1); - *fb2 = P(flush_out)(out2); - xfree(array); -} - -#else - -#define SORT_NODE struct P(presort_node) - -SORT_NODE { - SORT_NODE *next; - SORT_KEY key; -}; - -static SORT_NODE * -P(mergesort)(SORT_NODE *x) -{ - SORT_NODE *f1, **l1, *f2, **l2, **l; - - l1 = &f1; - l2 = &f2; - while (x) - { - *l1 = x; - l1 = &x->next; - x = x->next; - if (!x) - break; - *l2 = x; - l2 = &x->next; - x = x->next; - } - *l1 = *l2 = NULL; - - if (f1 && f1->next) - f1 = P(mergesort)(f1); - if (f2 && f2->next) - f2 = P(mergesort)(f2); - l = &x; - while (f1 && f2) - { - if (P(compare)(&f1->key, &f2->key) <= 0) - { - *l = f1; - l = &f1->next; - f1 = f1->next; - } - else - { - *l = f2; - l = &f2->next; - f2 = f2->next; - } - } - *l = f1 ? : f2; - return x; -} - -static void -P(presort)(struct fastbuf **fb1, struct fastbuf **fb2) -{ - struct fastbuf *in = *fb1; - struct fastbuf *out1 = NULL; - struct fastbuf *out2 = NULL; - struct fastbuf *tbuf; - byte *buffer, *bufend, *current; - SORT_NODE *first, **last, *this, *leftover; - int cont = 1; - uns run_count = 0; - uns giant_count = 0; - uns split_count = 0; - - ASSERT(!*fb2); - if (sorter_presort_bufsize < 2*sizeof(SORT_NODE)) - die("PresortBuffer set too low"); - buffer = xmalloc(sorter_presort_bufsize); - bufend = buffer + sorter_presort_bufsize; - leftover = NULL; - while (cont) - { -#ifdef SORT_UP_TO - if (sorter_presort_bufsize < SORT_UP_TO) -#endif - SWAP(out1, out2, tbuf); - if (!out1) - out1 = bopen_tmp(sorter_stream_bufsize); - current = buffer; - last = &first; - if (leftover) - { - memmove(buffer, leftover, sizeof(SORT_NODE)); - this = leftover = (SORT_NODE *) buffer; - split_count++; - goto get_data; - } - for(;;) - { - current = (byte *) ALIGN_TO((uintptr_t) current, CPU_STRUCT_ALIGN); - if (current + sizeof(*this) > bufend) - break; - this = (SORT_NODE *) current; - cont = P(fetch_key)(in, &this->key); - if (!cont) - break; - get_data: - current = P(fetch_item)(in, &this->key, bufend); - if (!current) - { - if (leftover) /* Single node too large */ - { - P(copy_data)(in, out1, &leftover->key); - leftover = NULL; - run_count++; - giant_count++; - } - else /* Node will be left over to the next phase */ - leftover = this; - break; - } - *last = this; - last = &this->next; - leftover = NULL; - } - *last = NULL; - if (!first) - continue; - - first = P(mergesort)(first); - run_count++; - while (first) - { -#ifdef SORT_UNIFY - SORT_NODE *second = first->next; - if (second && !P(compare)(&first->key, &second->key)) - { - SORT_KEY *n = P(merge_items)(&first->key, &second->key); - if (n == &first->key) - first->next = second->next; - else if (n) - first = first->next; - else - first = second->next; - continue; - } -#endif -#ifdef SORT_ASSERT_UNIQUE - ASSERT(!first->next || P(compare)(&first->key, &first->next->key)); -#endif - P(store_item)(out1, &first->key); - first = first->next; - } - } - - bclose(in); - if (sorter_trace) - msg(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB", - run_count, giant_count, split_count, - (out1 ? (int)((btell(out1) + 1023) / 1024) : 0), - (out2 ? (int)((btell(out2) + 1023) / 1024) : 0)); - *fb1 = P(flush_out)(out1); - *fb2 = P(flush_out)(out2); - xfree(buffer); -} - -#endif /* SORT_REGULAR && !SORT_UNIFY */ - -#endif /* SORT_PRESORT */ - -static -#ifdef SORT_OUTPUT_FB -struct fastbuf * -#elif defined(SORT_OUTPUT_FILE) -void -#else -#error No output defined. -#endif -P(sort)( -#ifdef SORT_INPUT_FILE -byte *inname -#elif defined(SORT_INPUT_FB) -struct fastbuf *fb1 -#elif defined(SORT_INPUT_FBPAIR) -struct fastbuf *fb1, struct fastbuf *fb2 -#else -#error No input defined. -#endif -#ifdef SORT_OUTPUT_FILE -,byte *outname -#endif -) -{ -#ifdef SORT_INPUT_FILE - struct fastbuf *fb1, *fb2; - fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize); - fb2 = NULL; -#elif defined(SORT_INPUT_FB) - struct fastbuf *fb2 = NULL; -#endif - -#ifdef SORT_DELETE_INPUT - bconfig(fb1, BCONFIG_IS_TEMP_FILE, SORT_DELETE_INPUT); -#endif - sorter_pass_counter = 1; -#ifdef SORT_PRESORT - P(presort)(&fb1, &fb2); - if (fb2) -#endif -#ifndef SORT_UP_TO - do P(pass)(&fb1, &fb2); while (fb1 && fb2); -#else - { - sh_off_t run_count, max_run_count = 0; - if (fb1) - max_run_count += bfilesize(fb1); - if (fb2) - max_run_count += bfilesize(fb2); -#ifdef SORT_PRESORT - run_count = max_run_count / sorter_presort_bufsize; -#else - run_count = max_run_count; -#endif - if (SORT_UP_TO) - max_run_count /= SORT_UP_TO; - do - run_count = P(pass)(&fb1, &fb2, (run_count+1)/2 <= max_run_count); - while (fb1 && fb2); - } -#endif - if (!fb1) - fb1 = bopen_tmp(sorter_stream_bufsize); - -#ifdef SORT_OUTPUT_FB - return fb1; -#else - bfix_tmp_file(fb1, outname); -#endif -} - -#undef P -#undef LESS -#undef SWAP -#undef SORT_NODE -#undef SORT_KEY -#undef SORT_PREFIX -#undef SORT_UNIFY -#undef SORT_UNIQUE -#undef SORT_ASSERT_UNIQUE -#undef SORT_REGULAR -#undef SORT_DELETE_INPUT -#undef SORT_INPUT_FILE -#undef SORT_INPUT_FB -#undef SORT_INPUT_FBPAIR -#undef SORT_OUTPUT_FILE -#undef SORT_OUTPUT_FB -#undef SORT_PRESORT -#undef SORT_UP_TO diff --git a/lib/sorter/Makefile b/lib/sorter/Makefile index 7dfa34de..a9b94307 100644 --- a/lib/sorter/Makefile +++ b/lib/sorter/Makefile @@ -3,7 +3,11 @@ DIRS+=lib/sorter LIBUCW_MODS+=$(addprefix sorter/, config govern sbuck array) -PROGS+=$(o)/lib/sorter/sort-test $(o)/lib/sorter/old-test +#LIBUCW_INCLUDES+=$(addprefix sorter/, array.h common.h s-fixint.h \ +# s-internal.h s-multiway.h s-radix.h s-twoway.h sorter.h) + +ifdef CONFIG_DEBUG_TOOLS +PROGS+=$(o)/lib/sorter/sort-test +endif $(o)/lib/sorter/sort-test: $(o)/lib/sorter/sort-test.o $(LIBUCW) -$(o)/lib/sorter/old-test: $(o)/lib/sorter/old-test.o $(LIBUCW) diff --git a/lib/sorter/old-test.c b/lib/sorter/old-test.c deleted file mode 100644 index bc108f58..00000000 --- a/lib/sorter/old-test.c +++ /dev/null @@ -1,413 +0,0 @@ -/* - * UCW Library -- Testing the Old Sorter - * - * (c) 2007 Martin Mares - * - * This software may be freely distributed and used according to the terms - * of the GNU Lesser General Public License. - */ - -#include "lib/lib.h" -#include "lib/getopt.h" -#include "lib/conf.h" -#include "lib/fastbuf.h" -#include "lib/ff-binary.h" -#include "lib/hashfunc.h" -#include "lib/md5.h" - -#include -#include -#include -#include -#include - -/*** Time measurement ***/ - -static timestamp_t timer; - -static void -start(void) -{ - sync(); - init_timer(&timer); -} - -static void -stop(void) -{ - sync(); - msg(L_INFO, "Test took %.3fs", get_timer(&timer) / 1000.); -} - -/*** Simple 4-byte integer keys ***/ - -struct key1 { - u32 x; -}; - -static inline int s1_compare(struct key1 *x, struct key1 *y) -{ - COMPARE(x->x, y->x); - return 0; -} - -#define SORT_KEY struct key1 -#define SORT_PREFIX(x) s1_##x -#define SORT_INPUT_FB -#define SORT_OUTPUT_FB -#define SORT_UNIQUE -#define SORT_REGULAR -#define SORT_PRESORT - -#include "lib/sorter.h" - -static void -test_int(int mode, u64 size) -{ - uns N = size ? nextprime(MIN(size/4, 0xffff0000)) : 0; - uns K = N/4*3; - msg(L_INFO, ">>> Integers (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N); - - struct fastbuf *f = bopen_tmp(65536); - for (uns i=0; ihash[i], y->hash[i]); - return 0; -} - -#define SORT_KEY struct key3 -#define SORT_PREFIX(x) s3_##x -#define SORT_INPUT_FB -#define SORT_OUTPUT_FB -#define SORT_REGULAR -#define SORT_PRESORT - -#include "lib/sorter.h" - -static void -gen_hash_key(int mode, struct key3 *k, uns i) -{ - k->i = i; - k->payload[0] = 7*i + 13; - k->payload[1] = 13*i + 19; - k->payload[2] = 19*i + 7; - switch (mode) - { - case 0: - k->hash[0] = i; - k->hash[1] = k->payload[0]; - k->hash[2] = k->payload[1]; - k->hash[3] = k->payload[2]; - break; - case 1: - k->hash[0] = ~i; - k->hash[1] = k->payload[0]; - k->hash[2] = k->payload[1]; - k->hash[3] = k->payload[2]; - break; - default: ; - struct MD5Context ctx; - MD5Init(&ctx); - MD5Update(&ctx, (byte*) &k->i, 4); - MD5Final((byte*) &k->hash, &ctx); - break; - } -} - -static void -test_hashes(int mode, u64 size) -{ - uns N = MIN(size / sizeof(struct key3), 0xffffffff); - msg(L_INFO, ">>> Hashes (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N); - struct key3 k, lastk; - - struct fastbuf *f = bopen_tmp(65536); - uns hash_sum = 0; - for (uns i=0; ilen = len; - breadb(f, x->s, len); - return 1; -} - -static inline void s4_copy_data(struct fastbuf *i UNUSED, struct fastbuf *f, struct key4 *x) -{ - bputl(f, x->len); - bwrite(f, x->s, x->len); -} - -static inline int s4_compare(struct key4 *x, struct key4 *y) -{ - uns l = MIN(x->len, y->len); - int c = memcmp(x->s, y->s, l); - if (c) - return c; - COMPARE(x->len, y->len); - return 0; -} - -static inline byte *s4_fetch_item(struct fastbuf *f UNUSED, struct key4 *x, byte *limit UNUSED) -{ - return &x->s[x->len]; -} - -static inline void s4_store_item(struct fastbuf *f, struct key4 *x) -{ - s4_copy_data(NULL, f, x); -} - -#define SORT_KEY struct key4 -#define SORT_PREFIX(x) s4_##x -#define SORT_INPUT_FB -#define SORT_OUTPUT_FB -#define SORT_PRESORT - -#include "lib/sorter.h" - -#define s4b_compare s4_compare -#define s4b_fetch_key s4_fetch_key - -static inline uns s4_data_size(struct key4 *x) -{ - return x->len ? (x->s[0] ^ 0xad) : 0; -} - -static inline void s4b_copy_data(struct fastbuf *i, struct fastbuf *f, struct key4 *x) -{ - bputl(f, x->len); - bwrite(f, x->s, x->len); - bbcopy(i, f, s4_data_size(x)); -} - -static inline byte *s4b_fetch_item(struct fastbuf *f, struct key4 *x, byte *limit) -{ - byte *d = &x->s[x->len]; - if (d + s4_data_size(x) > limit) - return NULL; - breadb(f, d, s4_data_size(x)); - return d + s4_data_size(x); -} - -static inline void s4b_store_item(struct fastbuf *f, struct key4 *x) -{ - bputl(f, x->len); - bwrite(f, x->s, x->len + s4_data_size(x)); -} - -#define SORT_KEY struct key4 -#define SORT_PREFIX(x) s4b_##x -#define SORT_INPUT_FB -#define SORT_OUTPUT_FB -#define SORT_PRESORT - -#include "lib/sorter.h" - -static void -gen_key4(struct key4 *k) -{ - k->len = random_max(KEY4_MAX); - for (uns i=0; ilen; i++) - k->s[i] = random(); -} - -static void -gen_data4(byte *buf, uns len, uns h) -{ - while (len--) - { - *buf++ = h >> 24; - h = h*259309 + 17; - } -} - -static void -test_strings(uns mode, u64 size) -{ - uns avg_item_size = KEY4_MAX/2 + 4 + (mode ? 128 : 0); - uns N = MIN(size / avg_item_size, 0xffffffff); - msg(L_INFO, ">>> Strings %s(N=%u)", (mode ? "with data " : ""), N); - srand(1); - - struct key4 k, lastk; - byte buf[256], buf2[256]; - uns sum = 0; - - struct fastbuf *f = bopen_tmp(65536); - for (uns i=0; i= 0) - switch (c) - { - case 's': - if (cf_parse_u64(optarg, &size)) - goto usage; - break; - case 't': - t = atol(optarg); - if (t >= TMAX) - goto usage; - break; - case 'v': - sorter_trace++; - break; - default: - usage: - fputs("Usage: sort-test [-v] [-s ] [-t ]\n", stderr); - exit(1); - } - if (optind != argc) - goto usage; - - if (t != ~0U) - run_test(t, size); - else - for (uns i=0; i