2 * UCW Library -- Universal Sorter
4 * (c) 2001--2007 Martin Mares <mj@ucw.cz>
5 * (c) 2004 Robert Spalek <robert@ucw.cz>
7 * This software may be freely distributed and used according to the terms
8 * of the GNU Lesser General Public License.
12 * This is not a normal header file, but a generator of sorting
13 * routines. Each time you include it with parameters set in the
14 * corresponding preprocessor macros, it generates a file sorter
15 * with the parameters given.
17 * FIXME: explain the basics (keys and data, callbacks etc.)
19 * Basic parameters and callbacks:
21 * SORT_PREFIX(x) add a name prefix (used on all global names
22 * defined by the sorter)
24 * SORT_KEY data type capable of storing a single key.
25 * SORT_KEY_REGULAR data type holding a single key both in memory and on disk;
26 * in this case, bread() and bwrite() is used to read/write keys
27 * and it's also assumed that the keys are not very long.
28 * int PREFIX_compare(SORT_KEY *a, SORT_KEY *b)
29 * compares two keys, result like strcmp(). Mandatory.
30 * int PREFIX_read_key(struct fastbuf *f, SORT_KEY *k)
31 * reads a key from a fastbuf, returns nonzero=ok, 0=EOF.
32 * Mandatory unless SORT_KEY_REGULAR is defined.
33 * void PREFIX_write_key(struct fastbuf *f, SORT_KEY *k)
34 * writes a key to a fastbuf. Mandatory unless SORT_KEY_REGULAR.
36 * SORT_KEY_SIZE(key) returns the real size of a key (a SORT_KEY type in memory
37 * can be truncated to this number of bytes without any harm;
38 * used to save memory when the keys have variable sizes).
39 * Default: always store the whole SORT_KEY.
40 * SORT_DATA_SIZE(key) gets a key and returns the amount of data following it.
41 * Default: records consist of keys only.
45 * SORT_INT(key) We are sorting by an integer value. In this mode, PREFIX_compare
46 * is supplied automatically and the sorting function gets an extra
47 * parameter specifying a range of the integers. The better the range
48 * fits, the faster we sort. Sets up SORT_HASH_xxx automatically.
49 * SORT_INT64(key) the same for 64-bit integers.
51 * Hashing (optional, but it can speed sorting up):
53 * SORT_HASH_BITS signals that a monotone hashing function returning a given number of
54 * bits is available. Monotone hash is a function f such that f(x) < f(y)
55 * implies x < y and which is approximately uniformly distributed.
56 * uns PREFIX_hash(SORT_KEY *a)
60 * SORT_UNIFY merge items with identical keys, needs the following functions:
61 * void PREFIX_write_merged(struct fastbuf *f, SORT_KEY **keys, void **data, uns n, void *buf)
62 * takes n records in memory with keys which compare equal and writes
63 * a single record to the given fastbuf. `buf' points to a buffer which
64 * is guaranteed to hold the sum of workspace requirements (see below)
65 * over all given records. The function is allowed to modify all its inputs.
66 * void PREFIX_copy_merged(SORT_KEY **keys, struct fastbuf **data, uns n, struct fastbuf *dest)
67 * takes n records with keys in memory and data in fastbufs and writes
68 * a single record. Used only if SORT_DATA_SIZE or SORT_UNIFY_WORKSPACE is defined.
69 * SORT_UNIFY_WORKSPACE(key)
70 * gets a key and returns the amount of workspace required when merging
71 * the given record. Defaults to 0.
73 * Input (choose one of these):
75 * SORT_INPUT_FILE file of a given name
76 * SORT_INPUT_FB seekable fastbuf stream
77 * SORT_INPUT_PIPE non-seekable fastbuf stream
78 * SORT_INPUT_PRESORT custom presorter. Calls function
79 * int PREFIX_presort(struct fastbuf *dest, void *buf, size_t bufsize)
80 * to get successive batches of pre-sorted data.
81 * The function is passed a page-aligned presorting buffer.
82 * It returns 1 on success or 0 on EOF.
83 * SORT_DELETE_INPUT A C expression, if true, then the input files are deleted
84 * as soon as possible.
86 * Output (chose one of these):
88 * SORT_OUTPUT_FILE file of a given name
89 * SORT_OUTPUT_FB temporary fastbuf stream
90 * SORT_OUTPUT_THIS_FB a given fastbuf stream which can already contain a header
94 * SORT_UNIQUE all items have distinct keys (checked in debug mode)
96 * The function generated:
98 * <outfb> PREFIX_sort(<in>, <out> [,<range>]), where:
99 * <in> = input file name/fastbuf or NULL
100 * <out> = output file name/fastbuf or NULL
101 * <range> = maximum integer value for the SORT_INT mode
102 * <outfb> = output fastbuf (in SORT_OUTPUT_FB mode)
104 * After including this file, all parameter macros are automatically
108 #include "lib/sorter/common.h"
109 #include "lib/fastbuf.h"
113 #define P(x) SORT_PREFIX(x)
115 #ifdef SORT_KEY_REGULAR
116 typedef SORT_KEY_REGULAR P(key);
117 static inline int P(read_key) (struct fastbuf *f, P(key) *k)
119 return breadb(f, k, sizeof(P(key)));
121 static inline void P(write_key) (struct fastbuf *f, P(key) *k)
123 bwrite(f, k, sizeof(P(key)));
125 #elif defined(SORT_KEY)
126 typedef SORT_KEY P(key);
128 #error Missing definition of sorting key.
132 typedef u64 P(hash_t);
133 #define SORT_INT SORT_INT64
134 #define SORT_LONG_HASH
136 typedef uns P(hash_t);
140 static inline int P(compare) (P(key) *x, P(key) *y)
142 if (SORT_INT(*x) < SORT_INT(*y))
144 if (SORT_INT(*x) > SORT_INT(*y))
149 #ifndef SORT_HASH_BITS
150 static inline P(hash_t) P(hash) (P(key) *x)
152 return SORT_INT((*x));
162 #define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0)
164 #if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS)
165 #define SORT_ASSERT_UNIQUE
171 #define SORT_KEY_SIZE(key) sizeof(key)
174 #ifdef SORT_DATA_SIZE
175 #define SORT_VAR_DATA
177 #define SORT_DATA_SIZE(key) 0
180 static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf *out)
182 P(write_key)(out, key);
184 bbcopy(in, out, SORT_DATA_SIZE(*key));
190 #if defined(SORT_UNIFY) && !defined(SORT_VAR_DATA) && !defined(SORT_UNIFY_WORKSPACE)
191 static inline void P(copy_merged)(P(key) **keys, struct fastbuf **data UNUSED, uns n, struct fastbuf *dest)
193 P(write_merged)(dest, keys, NULL, n, NULL);
197 #if defined(SORT_HASH_BITS) || defined(SORT_INT)
198 #define SORT_INTERNAL_RADIX
199 #include "lib/sorter/s-radix.h"
202 #if defined(SORT_VAR_KEY) || defined(SORT_VAR_DATA) || defined(SORT_UNIFY_WORKSPACE)
203 #include "lib/sorter/s-internal.h"
205 #include "lib/sorter/s-fixint.h"
208 #include "lib/sorter/s-twoway.h"
209 #include "lib/sorter/s-multiway.h"
211 static struct fastbuf *P(sort)(
212 #ifdef SORT_INPUT_FILE
217 #ifdef SORT_OUTPUT_FILE
227 struct sort_context ctx;
228 bzero(&ctx, sizeof(ctx));
230 #ifdef SORT_INPUT_FILE
231 ctx.in_fb = bopen_file(in, O_RDONLY, &sorter_fb_params);
232 ctx.in_size = bfilesize(ctx.in_fb);
233 #elif defined(SORT_INPUT_FB)
235 ctx.in_size = bfilesize(in);
236 #elif defined(SORT_INPUT_PIPE)
238 ctx.in_size = ~(u64)0;
239 #elif defined(SORT_INPUT_PRESORT)
241 ctx.custom_presort = P(presort);
242 ctx.in_size = ~(u64)0;
244 #error No input given.
246 #ifdef SORT_DELETE_INPUT
247 if (SORT_DELETE_INPUT)
248 bconfig(ctx.in_fb, BCONFIG_IS_TEMP_FILE, 1);
251 #ifdef SORT_OUTPUT_FB
253 #elif defined(SORT_OUTPUT_THIS_FB)
255 #elif defined(SORT_OUTPUT_FILE)
256 /* Just assume fastbuf output and rename the fastbuf later */
258 #error No output given.
261 #ifdef SORT_HASH_BITS
262 ctx.hash_bits = SORT_HASH_BITS;
263 ctx.radix_split = P(radix_split);
264 #elif defined(SORT_INT)
266 while (ctx.hash_bits < 64 && (int_range >> ctx.hash_bits))
268 ctx.radix_split = P(radix_split);
271 ctx.internal_sort = P(internal);
272 ctx.internal_estimate = P(internal_estimate);
273 ctx.twoway_merge = P(twoway_merge);
274 ctx.multiway_merge = P(multiway_merge);
278 #ifdef SORT_OUTPUT_FILE
279 bfix_tmp_file(ctx.out_fb, out);
287 #undef SORT_KEY_REGULAR
289 #undef SORT_DATA_SIZE
294 #undef SORT_HASH_BITS
296 #undef SORT_UNIFY_WORKSPACE
297 #undef SORT_INPUT_FILE
299 #undef SORT_INPUT_PRESORT
300 #undef SORT_OUTPUT_FILE
301 #undef SORT_OUTPUT_FB
302 #undef SORT_OUTPUT_THIS_FB
304 #undef SORT_ASSERT_UNIQUE
305 #undef SORT_DELETE_INPUT
306 #undef SORT_INTERNAL_RADIX
307 #undef SORT_LONG_HASH
311 /* FIXME: Check that we undef everything we should. */