X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=inline;f=lib%2Fsorter%2Fsorter.h;h=675a3d5b14fd21a0dbf5bd79f678c2a4e119e24c;hb=46aa3f9c9f6fbda755d067dfea672f9e2bf1af73;hp=d9ae7a00db4572bbd09d92810e53d7c6458b1856;hpb=557dc31fa097cfe3b8fdbc087e27da6db7317819;p=libucw.git diff --git a/lib/sorter/sorter.h b/lib/sorter/sorter.h index d9ae7a00..675a3d5b 100644 --- a/lib/sorter/sorter.h +++ b/lib/sorter/sorter.h @@ -46,13 +46,14 @@ * is supplied automatically and the sorting function gets an extra * parameter specifying a range of the integers. The better the range * fits, the faster we sort. Sets up SORT_HASH_xxx automatically. + * SORT_INT64(key) the same for 64-bit integers. * * Hashing (optional, but it can speed sorting up): * * SORT_HASH_BITS signals that a monotone hashing function returning a given number of * bits is available. Monotone hash is a function f such that f(x) < f(y) * implies x < y and which is approximately uniformly distributed. - * uns PREFIX_hash(SORT_KEY *a, SORT_KEY *b) + * uns PREFIX_hash(SORT_KEY *a) * * Unification: * @@ -60,10 +61,14 @@ * void PREFIX_write_merged(struct fastbuf *f, SORT_KEY **keys, void **data, uns n, void *buf) * takes n records in memory with keys which compare equal and writes * a single record to the given fastbuf. `buf' points to a buffer which - * is guaranteed to hold all given records. + * is guaranteed to hold the sum of workspace requirements (see below) + * over all given records. The function is allowed to modify all its inputs. * void PREFIX_copy_merged(SORT_KEY **keys, struct fastbuf **data, uns n, struct fastbuf *dest) * takes n records with keys in memory and data in fastbufs and writes - * a single record. + * a single record. Used only if SORT_DATA_SIZE or SORT_UNIFY_WORKSPACE is defined. + * SORT_UNIFY_WORKSPACE(key) + * gets a key and returns the amount of workspace required when merging + * the given record. Defaults to 0. * * Input (choose one of these): * @@ -71,10 +76,12 @@ * SORT_INPUT_FB seekable fastbuf stream * SORT_INPUT_PIPE non-seekable fastbuf stream * SORT_INPUT_PRESORT custom presorter. Calls function - * int PREFIX_presort(struct fastbuf *dest, void *buf, size_t bufsize); + * int PREFIX_presort(struct fastbuf *dest, void *buf, size_t bufsize) * to get successive batches of pre-sorted data. * The function is passed a page-aligned presorting buffer. * It returns 1 on success or 0 on EOF. + * SORT_DELETE_INPUT A C expression, if true, then the input files are deleted + * as soon as possible. * * Output (chose one of these): * @@ -88,7 +95,7 @@ * * The function generated: * - * PREFIX_SORT(, [,]), where: + * PREFIX_sort(, [,]), where: * = input file name/fastbuf or NULL * = output file name/fastbuf or NULL * = maximum integer value for the SORT_INT mode @@ -121,6 +128,13 @@ typedef SORT_KEY P(key); #error Missing definition of sorting key. #endif +#ifdef SORT_INT64 +typedef u64 P(hash_t); +#define SORT_INT SORT_INT64 +#else +typedef uns P(hash_t); +#endif + #ifdef SORT_INT static inline int P(compare) (P(key) *x, P(key) *y) { @@ -132,7 +146,7 @@ static inline int P(compare) (P(key) *x, P(key) *y) } #ifndef SORT_HASH_BITS -static inline int P(hash) (P(key) *x) +static inline P(hash_t) P(hash) (P(key) *x) { return SORT_INT((*x)); } @@ -172,8 +186,25 @@ static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf #endif } +#if defined(SORT_UNIFY) && !defined(SORT_VAR_DATA) && !defined(SORT_UNIFY_WORKSPACE) +static inline void P(copy_merged)(P(key) **keys, struct fastbuf **data UNUSED, uns n, struct fastbuf *dest) +{ + P(write_merged)(dest, keys, NULL, n, NULL); +} +#endif + +#if defined(SORT_VAR_KEY) || defined(SORT_VAR_DATA) || defined(SORT_UNIFY_WORKSPACE) #include "lib/sorter/s-internal.h" +#else +#include "lib/sorter/s-fixint.h" +#endif + #include "lib/sorter/s-twoway.h" +#include "lib/sorter/s-multiway.h" + +#if defined(SORT_HASH_BITS) || defined(SORT_INT) +#include "lib/sorter/s-radix.h" +#endif static struct fastbuf *P(sort)( #ifdef SORT_INPUT_FILE @@ -187,7 +218,7 @@ static struct fastbuf *P(sort)( struct fastbuf *out #endif #ifdef SORT_INT - , uns int_range + , u64 int_range #endif ) { @@ -195,7 +226,7 @@ static struct fastbuf *P(sort)( bzero(&ctx, sizeof(ctx)); #ifdef SORT_INPUT_FILE - ctx.in_fb = bopen(in, O_RDONLY, sorter_stream_bufsize); + ctx.in_fb = bopen_file(in, O_RDONLY, &sorter_fb_params); ctx.in_size = bfilesize(ctx.in_fb); #elif defined(SORT_INPUT_FB) ctx.in_fb = in; @@ -210,6 +241,10 @@ static struct fastbuf *P(sort)( #else #error No input given. #endif +#ifdef SORT_DELETE_INPUT + if (SORT_DELETE_INPUT) + bconfig(ctx.in_fb, BCONFIG_IS_TEMP_FILE, 1); +#endif #ifdef SORT_OUTPUT_FB ASSERT(!out); @@ -223,22 +258,23 @@ static struct fastbuf *P(sort)( #ifdef SORT_HASH_BITS ctx.hash_bits = SORT_HASH_BITS; + ctx.radix_split = P(radix_split); #elif defined(SORT_INT) ctx.hash_bits = 0; - while (ctx.hash_bits < 32 && (int_range >> ctx.hash_bits)) + while (ctx.hash_bits < 64 && (int_range >> ctx.hash_bits)) ctx.hash_bits++; + ctx.radix_split = P(radix_split); #endif ctx.internal_sort = P(internal); + ctx.internal_estimate = P(internal_estimate); ctx.twoway_merge = P(twoway_merge); + ctx.multiway_merge = P(multiway_merge); sorter_run(&ctx); #ifdef SORT_OUTPUT_FILE - if (rename(ctx.out_fb->name, out) < 0) - die("Cannot rename %s to %s: %m", ctx.out_fb->name, out); - bconfig(ctx.out_fb, BCONFIG_IS_TEMP_FILE, 0); - bclose(ctx.out_fb); + bfix_tmp_file(ctx.out_fb, out); ctx.out_fb = NULL; #endif return ctx.out_fb; @@ -252,8 +288,10 @@ static struct fastbuf *P(sort)( #undef SORT_VAR_KEY #undef SORT_VAR_DATA #undef SORT_INT +#undef SORT_INT64 #undef SORT_HASH_BITS #undef SORT_UNIFY +#undef SORT_UNIFY_WORKSPACE #undef SORT_INPUT_FILE #undef SORT_INPUT_FB #undef SORT_INPUT_PRESORT @@ -262,6 +300,7 @@ static struct fastbuf *P(sort)( #undef SORT_OUTPUT_THIS_FB #undef SORT_UNIQUE #undef SORT_ASSERT_UNIQUE +#undef SORT_DELETE_INPUT #undef SWAP #undef LESS #undef P