X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fsorter%2Fsorter.h;h=c8924840135d2f0d0337d093d8c1160bea41f21a;hb=a5ff98a53789157a6c96e58b2385bb898d688a22;hp=89cf9f0df7f4e5b5160658d5a0b99f8747943ff7;hpb=ae3892dc4f3c3a759315969e2ab5156f034707b2;p=libucw.git diff --git a/lib/sorter/sorter.h b/lib/sorter/sorter.h index 89cf9f0d..c8924840 100644 --- a/lib/sorter/sorter.h +++ b/lib/sorter/sorter.h @@ -46,6 +46,7 @@ * 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): * @@ -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,14 @@ 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 +#define SORT_LONG_HASH +#else +typedef uns P(hash_t); +#endif + #ifdef SORT_INT static inline int P(compare) (P(key) *x, P(key) *y) { @@ -132,7 +147,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,17 +187,26 @@ static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf #endif } -#if defined(SORT_VAR_KEY) || defined(SORT_VAR_DATA) || defined(SORT_UNIFY) +#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_HASH_BITS) || defined(SORT_INT) +#define SORT_INTERNAL_RADIX +#include "lib/sorter/s-radix.h" +#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" - -#if defined(SORT_HASH_BITS) || defined(SORT_INT) -#include "lib/sorter/s-radix.h" -#endif +#include "lib/sorter/s-multiway.h" static struct fastbuf *P(sort)( #ifdef SORT_INPUT_FILE @@ -196,7 +220,7 @@ static struct fastbuf *P(sort)( struct fastbuf *out #endif #ifdef SORT_INT - , uns int_range + , u64 int_range #endif ) { @@ -204,7 +228,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; @@ -219,6 +243,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); @@ -235,7 +263,7 @@ static struct fastbuf *P(sort)( 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 @@ -243,38 +271,41 @@ static struct fastbuf *P(sort)( 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; } -#undef SORT_PREFIX -#undef SORT_KEY -#undef SORT_KEY_REGULAR -#undef SORT_KEY_SIZE +#undef SORT_ASSERT_UNIQUE #undef SORT_DATA_SIZE -#undef SORT_VAR_KEY -#undef SORT_VAR_DATA -#undef SORT_INT +#undef SORT_DELETE_INPUT #undef SORT_HASH_BITS -#undef SORT_UNIFY -#undef SORT_INPUT_FILE #undef SORT_INPUT_FB +#undef SORT_INPUT_FILE +#undef SORT_INPUT_PIPE #undef SORT_INPUT_PRESORT -#undef SORT_OUTPUT_FILE +#undef SORT_INT +#undef SORT_INT64 +#undef SORT_INTERNAL_RADIX +#undef SORT_KEY +#undef SORT_KEY_REGULAR +#undef SORT_KEY_SIZE +#undef SORT_LONG_HASH #undef SORT_OUTPUT_FB +#undef SORT_OUTPUT_FILE #undef SORT_OUTPUT_THIS_FB +#undef SORT_PREFIX +#undef SORT_UNIFY +#undef SORT_UNIFY_WORKSPACE #undef SORT_UNIQUE -#undef SORT_ASSERT_UNIQUE +#undef SORT_VAR_DATA +#undef SORT_VAR_KEY #undef SWAP #undef LESS #undef P -/* FIXME: Check that we undef everything we should. */