/*
- * Sherlock Library -- Universal Sorter
+ * UCW Library -- Universal Sorter
*
* (c) 2001--2004 Martin Mares <mj@ucw.cz>
+ * (c) 2004 Robert Spalek <robert@ucw.cz>
*
* This software may be freely distributed and used according to the terms
* of the GNU Lesser General Public License.
* the pre-sorting mode, it's quite possible that the
* comparison function will be called with both arguments
* identical.
- * SORT_PRESORT_ONLY a C expression which, if evaluated to non-zero, makes
- * the sorter stop after the pre-sorting pass, resulting
- * in a file which is not necessarily sorted, but which
- * contains long runs. Implies SORT_PRESORT.
+ * 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
* 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 1=ok, 0=eof
+ * 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.
* undef'd.
*/
-/* Declarations of externals from sorter.c */
-
-#ifndef SORT_DECLS_READ
-#define SORT_DECLS_READ
-
-extern uns sorter_trace;
-extern uns sorter_presort_bufsize;
-extern uns sorter_stream_bufsize;
-
-extern uns sorter_pass_counter;
-
-#endif /* !SORT_DECLS_READ */
-
-/* The sorter proper */
-
-#ifndef SORT_DECLARE_ONLY
-
+#include "lib/sorter-globals.h"
#include "lib/fastbuf.h"
#include <unistd.h>
#include <fcntl.h>
#define LESS <=
#endif
-#if defined(SORT_UNIQUE) && defined(DEBUG)
+#if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS)
#define SORT_ASSERT_UNIQUE
#endif
-#ifdef SORT_PRESORT_ONLY
-#undef SORT_PRESORT
-#define SORT_PRESORT
-#else
-#define SORT_PRESORT_ONLY 0
-#endif
-
#ifdef SORT_REGULAR
static inline int
return out;
}
-static void
-P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
+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;
if (!kout || !(P(compare)(kout, ktmp) LESS 0))
{
struct fastbuf *t;
- SWAP(out1, out2, t);
+#ifdef SORT_UP_TO
+ if (!stop_sorting)
+#endif
+ SWAP(out1, out2, t);
if (!out1)
out1 = bopen_tmp(sorter_stream_bufsize);
run_count++;
bclose(in1);
bclose(in2);
if (sorter_trace)
- log(L_INFO, "Pass %d: %d runs, %d+%d KB", sorter_pass_counter, run_count,
+ 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
struct fastbuf *tbuf;
uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY);
uns run_count = 0;
- SORT_KEY last_out, *array;
+ SORT_KEY last_out = { }, *array;
ASSERT(!*fb2);
if (buf_items < 2)
if (!run_count || P(compare)(&last_out, &array[0]) > 0)
{
run_count++;
- SWAP(out1, out2, tbuf);
+#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);
}
bclose(in);
if (sorter_trace)
- log(L_INFO, "Pass 0: %d runs, %d+%d KB",
+ 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));
leftover = NULL;
while (cont)
{
- if (!(SORT_PRESORT_ONLY))
+#ifdef SORT_UP_TO
+ if (sorter_presort_bufsize < SORT_UP_TO)
+#endif
SWAP(out1, out2, tbuf);
if (!out1)
out1 = bopen_tmp(sorter_stream_bufsize);
}
for(;;)
{
- current = (byte *) ALIGN((addr_int_t) current, CPU_STRUCT_ALIGN);
+ current = (byte *) ALIGN_TO((uintptr_t) current, CPU_STRUCT_ALIGN);
if (current + sizeof(*this) > bufend)
break;
this = (SORT_NODE *) current;
bclose(in);
if (sorter_trace)
- log(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB",
+ 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));
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);
#undef SORT_OUTPUT_FILE
#undef SORT_OUTPUT_FB
#undef SORT_PRESORT
-#undef SORT_PRESORT_ONLY
-
-#endif /* !SORT_DECLARE_ONLY */
+#undef SORT_UP_TO
projects / libucw.git / blobdiff