2 * Sherlock Library -- Universal Sorter
4 * (c) 2001--2004 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 * This is not a normal header file, it's a generator of sorting
12 * routines. Each time you include it with parameters set in the
13 * corresponding preprocessor macros, it generates a file sorter
14 * with the parameters given.
16 * Recognized parameter macros: (those marked with [*] are mandatory)
18 * SORT_KEY [*] data type capable of storing a single key
19 * SORT_PREFIX(x) [*] add a name prefix (used on all global names
20 * defined by the sorter)
21 * SORT_PRESORT include an in-core pre-sorting pass. Beware, when in
22 * the pre-sorting mode, it's quite possible that the
23 * comparison function will be called with both arguments
25 * SORT_PRESORT_ONLY a C expression which, if evaluated to non-zero, makes
26 * the sorter stop after the pre-sorting pass, resulting
27 * in a file which is not necessarily sorted, but which
28 * contains long runs. Implies SORT_PRESORT.
29 * SORT_UNIFY merge items with identical keys
30 * SORT_UNIQUE all items have distinct keys (checked in debug mode)
31 * SORT_REGULAR all items are equally long and they don't contain
32 * anything else than the key. In this case, the sorter
33 * automatically supplies fetch_key, copy_data, fetch_item
34 * and store_item functions. Item size is also expected
36 * SORT_DELETE_INPUT a C expression, if true, the input files are
37 * deleted as soon as possible
38 * SORT_INPUT_FILE input is a file with this name
39 * SORT_INPUT_FB input is a fastbuf stream
40 * (can be safely NULL if you want to treat original
41 * input in a different way by file read functions)
42 * SORT_INPUT_FBPAIR input is a pair of fastbuf streams
43 * (not supported by the presorter)
44 * SORT_OUTPUT_FILE output is a file with this name
45 * SORT_OUTPUT_FB output is a temporary fastbuf stream
47 * You also need to define some (usually inline) functions which
48 * are called by the sorter to process your data:
50 * int PREFIX_compare(SORT_KEY *a, *b)
51 * compare two keys, result like strcmp
52 * int PREFIX_fetch_key(struct fastbuf *f, SORT_KEY *k)
53 * fetch next key, returns 1=ok, 0=eof
54 * void PREFIX_copy_data(struct fastbuf *src, *dest, SORT_KEY *k)
55 * write just fetched key k to dest and copy all data
56 * belonging to this key from src to dest.
57 * void PREFIX_merge_data(struct fastbuf *src1, *src2, *dest, SORT_KEY *k1, *k2)
58 * [used only in case SORT_UNIFY is defined]
59 * write just fetched key k to dest and merge data from
60 * two records with the same key (k1 and k2 are key occurences
61 * in the corresponding streams).
62 * byte * PREFIX_fetch_item(struct fastbuf *f, SORT_KEY *k, byte *limit)
63 * [used only with SORT_PRESORT]
64 * fetch data belonging to a just fetched key and store
65 * them to memory following the key, but not over limit.
66 * Returns a pointer to first byte after the data
67 * or NULL if the data don't fit. For variable-length
68 * keys, it can use the rest of SORT_KEY and even return
69 * pointer before end of the key.
70 * Important: before PREFIX_fetch_item() succeeds, the key
71 * must be position independent, the sorter can copy it.
72 * void PREFIX_store_item(struct fastbuf *f, SORT_KEY *k)
73 * [used only with SORT_PRESORT]
74 * write key and all its data read with PREFIX_fetch_data
75 * to the stream given.
76 * SORT_KEY * PREFIX_merge_items(SORT_KEY *a, SORT_KEY *b)
77 * [used only with SORT_PRESORT && SORT_UNIFY]
78 * merge two items with the same key, returns pointer
79 * to at most one of the items, the rest will be removed
80 * from the list of items, but not deallocated, so
81 * the remaining item can freely reference data of the
84 * After including this file, all parameter macros are automatically
88 /* Declarations of externals from sorter.c */
90 #ifndef SORT_DECLS_READ
91 #define SORT_DECLS_READ
93 extern uns sorter_trace;
94 extern uns sorter_presort_bufsize;
95 extern uns sorter_stream_bufsize;
97 extern uns sorter_pass_counter;
99 #endif /* !SORT_DECLS_READ */
101 /* The sorter proper */
103 #ifndef SORT_DECLARE_ONLY
105 #include "lib/fastbuf.h"
110 #if !defined(SORT_KEY) || !defined(SORT_PREFIX)
111 #error Some of the mandatory configuration macros are missing.
114 #define P(x) SORT_PREFIX(x)
115 #define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0)
117 #if defined(SORT_UNIFY) || defined(SORT_UNIQUE)
123 #if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS)
124 #define SORT_ASSERT_UNIQUE
127 #ifdef SORT_PRESORT_ONLY
131 #define SORT_PRESORT_ONLY 0
137 P(fetch_key)(struct fastbuf *in, SORT_KEY *x)
139 return breadb(in, x, sizeof(*x));
143 P(copy_data)(struct fastbuf *in UNUSED, struct fastbuf *out, SORT_KEY *x)
145 bwrite(out, x, sizeof(*x));
149 P(fetch_item)(struct fastbuf *in UNUSED, SORT_KEY *x UNUSED, byte *limit UNUSED)
151 return (byte *)(x+1);
155 P(store_item)(struct fastbuf *out, SORT_KEY *x)
157 bwrite(out, x, sizeof(*x));
162 static struct fastbuf *
163 P(flush_out)(struct fastbuf *out)
171 P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
173 struct fastbuf *in1 = *fb1;
174 struct fastbuf *in2 = *fb2;
175 struct fastbuf *out1 = NULL;
176 struct fastbuf *out2 = NULL;
177 SORT_KEY kbuf1, kbuf2, kbuf3, kbuf4;
178 SORT_KEY *kin1 = &kbuf1;
179 SORT_KEY *kprev1 = &kbuf2;
180 SORT_KEY *kin2 = &kbuf3;
181 SORT_KEY *kprev2 = &kbuf4;
182 SORT_KEY *kout = NULL;
184 int next1, next2, comp;
188 run1 = next1 = in1 ? P(fetch_key)(in1, kin1) : 0;
189 run2 = next2 = in2 ? P(fetch_key)(in2, kin2) : 0;
190 while (next1 || next2)
197 comp = P(compare)(kin1, kin2);
198 ktmp = (comp <= 0) ? kin1 : kin2;
199 if (!kout || !(P(compare)(kout, ktmp) LESS 0))
204 out1 = bopen_tmp(sorter_stream_bufsize);
209 P(copy_data)(in1, out1, kin1);
210 SWAP(kin1, kprev1, ktmp);
211 next1 = P(fetch_key)(in1, kin1);
212 run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
218 P(merge_data)(in1, in2, out1, kin1, kin2);
219 SWAP(kin1, kprev1, ktmp);
220 next1 = P(fetch_key)(in1, kin1);
221 run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
222 SWAP(kin2, kprev2, ktmp);
223 next2 = P(fetch_key)(in2, kin2);
224 run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
228 #ifdef SORT_ASSERT_UNIQUE
229 else if (unlikely(comp == 0))
234 P(copy_data)(in2, out1, kin2);
235 SWAP(kin2, kprev2, ktmp);
236 next2 = P(fetch_key)(in2, kin2);
237 run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
249 log(L_INFO, "Pass %d: %d runs, %d+%d KB", sorter_pass_counter, run_count,
250 (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
251 (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
252 *fb1 = P(flush_out)(out1);
253 *fb2 = P(flush_out)(out2);
254 sorter_pass_counter++;
259 #if defined(SORT_REGULAR) && !defined(SORT_UNIFY)
261 /* If we are doing a simple sort on a regular file, we can use a faster presorting strategy */
263 static SORT_KEY *P(array);
265 #define ASORT_PREFIX(x) SORT_PREFIX(x##_array)
266 #define ASORT_KEY_TYPE SORT_KEY
267 #define ASORT_ELT(i) P(array)[i]
268 #define ASORT_LT(x,y) (P(compare)(&(x),&(y)) < 0)
270 #include "lib/arraysort.h"
273 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
275 struct fastbuf *in = *fb1;
276 struct fastbuf *out1 = NULL;
277 struct fastbuf *out2 = NULL;
278 struct fastbuf *tbuf;
279 uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY);
281 SORT_KEY last_out, *array;
285 die("PresortBuffer set too low");
286 P(array) = array = xmalloc(buf_items * sizeof(SORT_KEY));
290 uns s = bread(in, array, buf_items * sizeof(SORT_KEY));
291 uns n = s / sizeof(SORT_KEY);
292 ASSERT(!(s % sizeof(SORT_KEY)));
296 #ifdef SORT_ASSERT_UNIQUE
297 for (uns i=0; i<n-1; i++)
298 if (unlikely(P(compare)(&array[i], &array[i+1]) >= 0))
300 ASSERT(!run_count || P(compare)(&last_out, &array[0]));
302 if (!run_count || P(compare)(&last_out, &array[0]) > 0)
305 SWAP(out1, out2, tbuf);
307 out1 = bopen_tmp(sorter_stream_bufsize);
309 last_out = array[n-1];
310 bwrite(out1, array, n * sizeof(SORT_KEY));
315 log(L_INFO, "Pass 0: %d runs, %d+%d KB",
317 (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
318 (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
319 *fb1 = P(flush_out)(out1);
320 *fb2 = P(flush_out)(out2);
326 #define SORT_NODE struct P(presort_node)
334 P(mergesort)(SORT_NODE *x)
336 SORT_NODE *f1, **l1, *f2, **l2, **l;
354 f1 = P(mergesort)(f1);
356 f2 = P(mergesort)(f2);
360 if (P(compare)(&f1->key, &f2->key) <= 0)
378 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
380 struct fastbuf *in = *fb1;
381 struct fastbuf *out1 = NULL;
382 struct fastbuf *out2 = NULL;
383 struct fastbuf *tbuf;
384 byte *buffer, *bufend, *current;
385 SORT_NODE *first, **last, *this, *leftover;
392 if (sorter_presort_bufsize < 2*sizeof(SORT_NODE))
393 die("PresortBuffer set too low");
394 buffer = xmalloc(sorter_presort_bufsize);
395 bufend = buffer + sorter_presort_bufsize;
399 if (!(SORT_PRESORT_ONLY))
400 SWAP(out1, out2, tbuf);
402 out1 = bopen_tmp(sorter_stream_bufsize);
407 memmove(buffer, leftover, sizeof(SORT_NODE));
408 this = leftover = (SORT_NODE *) buffer;
414 current = (byte *) ALIGN((addr_int_t) current, CPU_STRUCT_ALIGN);
415 if (current + sizeof(*this) > bufend)
417 this = (SORT_NODE *) current;
418 cont = P(fetch_key)(in, &this->key);
422 current = P(fetch_item)(in, &this->key, bufend);
425 if (leftover) /* Single node too large */
427 P(copy_data)(in, out1, &leftover->key);
432 else /* Node will be left over to the next phase */
444 first = P(mergesort)(first);
449 SORT_NODE *second = first->next;
450 if (second && !P(compare)(&first->key, &second->key))
452 SORT_KEY *n = P(merge_items)(&first->key, &second->key);
453 if (n == &first->key)
454 first->next = second->next;
458 first = second->next;
462 #ifdef SORT_ASSERT_UNIQUE
463 ASSERT(!first->next || P(compare)(&first->key, &first->next->key));
465 P(store_item)(out1, &first->key);
472 log(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB",
473 run_count, giant_count, split_count,
474 (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
475 (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
476 *fb1 = P(flush_out)(out1);
477 *fb2 = P(flush_out)(out2);
481 #endif /* SORT_REGULAR && !SORT_UNIFY */
483 #endif /* SORT_PRESORT */
486 #ifdef SORT_OUTPUT_FB
488 #elif defined(SORT_OUTPUT_FILE)
491 #error No output defined.
494 #ifdef SORT_INPUT_FILE
496 #elif defined(SORT_INPUT_FB)
498 #elif defined(SORT_INPUT_FBPAIR)
499 struct fastbuf *fb1, struct fastbuf *fb2
501 #error No input defined.
503 #ifdef SORT_OUTPUT_FILE
508 #ifdef SORT_INPUT_FILE
509 struct fastbuf *fb1, *fb2;
510 fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize);
512 #elif defined(SORT_INPUT_FB)
513 struct fastbuf *fb2 = NULL;
516 #ifdef SORT_DELETE_INPUT
517 bconfig(fb1, BCONFIG_IS_TEMP_FILE, SORT_DELETE_INPUT);
519 sorter_pass_counter = 1;
521 P(presort)(&fb1, &fb2);
524 do P(pass)(&fb1, &fb2); while (fb1 && fb2);
526 fb1 = bopen_tmp(sorter_stream_bufsize);
528 #ifdef SORT_OUTPUT_FB
531 bconfig(fb1, BCONFIG_IS_TEMP_FILE, 0);
532 if (rename(fb1->name, outname) < 0)
533 die("rename(%s,%s): %m", fb1->name, outname);
546 #undef SORT_ASSERT_UNIQUE
548 #undef SORT_DELETE_INPUT
549 #undef SORT_INPUT_FILE
551 #undef SORT_INPUT_FBPAIR
552 #undef SORT_OUTPUT_FILE
553 #undef SORT_OUTPUT_FB
555 #undef SORT_PRESORT_ONLY
557 #endif /* !SORT_DECLARE_ONLY */