/*
* Sherlock Library -- Universal Sorter
*
- * (c) 2001 Martin Mares <mj@ucw.cz>
+ * (c) 2001--2004 Martin Mares <mj@ucw.cz>
+ *
+ * This software may be freely distributed and used according to the terms
+ * of the GNU Lesser General Public License.
*/
/*
* SORT_KEY [*] data type capable of storing a single key
* SORT_PREFIX(x) [*] add a name prefix (used on all global names
* defined by the sorter)
- * SORT_PRESORT include an in-core presorting pass
+ * SORT_PRESORT include an in-core presorting pass. Beware, when in
+ * the pre-sorting mode, it's quite possible that the
+ * comparison function will be called with both arguments
+ * identical.
* 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
+ * anything else than the key. In this case, the sorter
+ * automatically supplies fetch_key, copy_data, fetch_item
+ * and store_item functions. Item size is also expected
+ * to be small.
* SORT_DELETE_INPUT a C expression, if true, the input files are
* deleted as soon as possible
* SORT_INPUT_FILE input is a file with this name
* SORT_INPUT_FB input is a fastbuf stream
+ * (can be safely NULL if you want to treat original
+ * input in a different way by file read functions)
* SORT_INPUT_FBPAIR input is a pair of fastbuf streams
* (not supported by the presorter)
* SORT_OUTPUT_FILE output is a file with this name
- * SORT_OUTPUT_FB output is a fastbuf stream
+ * SORT_OUTPUT_FB output is a temporary fastbuf stream
*
* You also need to define some (usually inline) functions which
* are called by the sorter to process your data:
* write just fetched key k to dest and merge data from
* two records with the same key (k1 and k2 are key occurences
* in the corresponding streams).
- * char * PREFIX_fetch_item(struct fastbuf *f, SORT_KEY *k, char *limit)
+ * byte * PREFIX_fetch_item(struct fastbuf *f, SORT_KEY *k, byte *limit)
* [used only with SORT_PRESORT]
* fetch data belonging to a just fetched key and store
* them to memory following the key, but not over limit.
* Returns a pointer to first byte after the data
- * or NULL if the data don't fit.
- * Important: keys carrying no data must be position
- * independent.
+ * or NULL if the data don't fit. For variable-length
+ * keys, it can use the rest of SORT_KEY and even return
+ * pointer before end of the key.
+ * Important: before PREFIX_fetch_item() succeeds, the key
+ * must be position independent, the sorter can copy it.
* void PREFIX_store_item(struct fastbuf *f, SORT_KEY *k)
* [used only with SORT_PRESORT]
* write key and all its data read with PREFIX_fetch_data
* from the list of items, but not deallocated, so
* the remaining item can freely reference data of the
* other one.
+ *
+ * After including this file, all parameter macros are automatically
+ * undef'd.
*/
/* Declarations of externals from sorter.c */
extern uns sorter_presort_bufsize;
extern uns sorter_stream_bufsize;
-extern uns sorter_pass_counter, sorter_file_counter;
-struct fastbuf *sorter_open_tmp(void);
+extern uns sorter_pass_counter;
#endif /* !SORT_DECLS_READ */
#include "lib/fastbuf.h"
#include <unistd.h>
#include <fcntl.h>
+#include <string.h>
#if !defined(SORT_KEY) || !defined(SORT_PREFIX)
#error Some of the mandatory configuration macros are missing.
#define LESS <=
#endif
+#if defined(SORT_UNIQUE) && defined(DEBUG)
+#define SORT_ASSERT_UNIQUE
+#endif
+
+#ifdef SORT_REGULAR
+
+static inline int
+P(fetch_key)(struct fastbuf *in, SORT_KEY *x)
+{
+ return breadb(in, x, sizeof(*x));
+}
+
+static inline void
+P(copy_data)(struct fastbuf *in UNUSED, struct fastbuf *out, SORT_KEY *x)
+{
+ bwrite(out, x, sizeof(*x));
+}
+
+static inline byte *
+P(fetch_item)(struct fastbuf *in UNUSED, SORT_KEY *x UNUSED, byte *limit UNUSED)
+{
+ return (byte *)(x+1);
+}
+
+static inline void
+P(store_item)(struct fastbuf *out, SORT_KEY *x)
+{
+ bwrite(out, x, sizeof(*x));
+}
+
+#endif
+
+static struct fastbuf *
+P(flush_out)(struct fastbuf *out)
+{
+ if (out)
+ brewind(out);
+ return out;
+}
+
static void
P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
{
struct fastbuf *t;
SWAP(out1, out2, t);
if (!out1)
- out1 = sorter_open_tmp();
+ out1 = bopen_tmp(sorter_stream_bufsize);
run_count++;
}
if (comp LESS 0)
{
P(merge_data)(in1, in2, out1, kin1, kin2);
SWAP(kin1, kprev1, ktmp);
- next1 = P(fetch_key)(in1, kin1); /* FIXME: Re-use other code? */
+ next1 = P(fetch_key)(in1, kin1);
run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
SWAP(kin2, kprev2, ktmp);
next2 = P(fetch_key)(in2, kin2);
run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
kout = kprev2;
}
+#endif
+#ifdef SORT_ASSERT_UNIQUE
+ else if (unlikely(comp == 0))
+ ASSERT(0);
#endif
else
{
log(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));
- if (out1) /* FIXME: What about empty output? */
+ *fb1 = P(flush_out)(out1);
+ *fb2 = P(flush_out)(out2);
+ sorter_pass_counter++;
+}
+
+#ifdef SORT_PRESORT
+
+#if defined(SORT_REGULAR) && !defined(SORT_UNIFY)
+
+/* If we are doing a simple sort on a regular file, we can use a faster presorting strategy */
+
+static SORT_KEY *P(array);
+
+#define ASORT_PREFIX(x) SORT_PREFIX(x##_array)
+#define ASORT_KEY_TYPE SORT_KEY
+#define ASORT_ELT(i) P(array)[i]
+#define ASORT_LT(x,y) (P(compare)(&(x),&(y)) < 0)
+
+#include "lib/arraysort.h"
+
+static void
+P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
+{
+ struct fastbuf *in = *fb1;
+ struct fastbuf *out1 = NULL;
+ struct fastbuf *out2 = NULL;
+ struct fastbuf *tbuf;
+ uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY);
+ uns run_count = 0;
+ SORT_KEY last_out, *array;
+
+ ASSERT(!*fb2);
+ if (buf_items < 2)
+ die("PresortBuffer set too low");
+ P(array) = array = xmalloc(buf_items * sizeof(SORT_KEY));
+
+ for(;;)
{
- bflush(out1);
- bsetpos(out1, 0);
+ uns s = bread(in, array, buf_items * sizeof(SORT_KEY));
+ uns n = s / sizeof(SORT_KEY);
+ ASSERT(!(s % sizeof(SORT_KEY)));
+ if (!n)
+ break;
+ P(sort_array)(n);
+#ifdef SORT_ASSERT_UNIQUE
+ for (uns i=0; i<n-1; i++)
+ if (unlikely(P(compare)(&array[i], &array[i+1]) >= 0))
+ ASSERT(0);
+ ASSERT(!run_count || P(compare)(&last_out, &array[0]));
+#endif
+ if (!run_count || P(compare)(&last_out, &array[0]) > 0)
+ {
+ run_count++;
+ SWAP(out1, out2, tbuf);
+ if (!out1)
+ out1 = bopen_tmp(sorter_stream_bufsize);
+ }
+ last_out = array[n-1];
+ bwrite(out1, array, n * sizeof(SORT_KEY));
}
- if (out2)
+
+ bclose(in);
+ if (sorter_trace)
+ log(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));
+ *fb1 = P(flush_out)(out1);
+ *fb2 = P(flush_out)(out2);
+ xfree(array);
+}
+
+#else
+
+#define SORT_NODE struct P(presort_node)
+
+SORT_NODE {
+ SORT_NODE *next;
+ SORT_KEY key;
+};
+
+static SORT_NODE *
+P(mergesort)(SORT_NODE *x)
+{
+ SORT_NODE *f1, **l1, *f2, **l2, **l;
+
+ l1 = &f1;
+ l2 = &f2;
+ while (x)
{
- bflush(out2);
- bsetpos(out2, 0);
+ *l1 = x;
+ l1 = &x->next;
+ x = x->next;
+ if (!x)
+ break;
+ *l2 = x;
+ l2 = &x->next;
+ x = x->next;
}
- *fb1 = out1;
- *fb2 = out2;
- sorter_pass_counter++;
+ *l1 = *l2 = NULL;
+
+ if (f1 && f1->next)
+ f1 = P(mergesort)(f1);
+ if (f2 && f2->next)
+ f2 = P(mergesort)(f2);
+ l = &x;
+ while (f1 && f2)
+ {
+ if (P(compare)(&f1->key, &f2->key) <= 0)
+ {
+ *l = f1;
+ l = &f1->next;
+ f1 = f1->next;
+ }
+ else
+ {
+ *l = f2;
+ l = &f2->next;
+ f2 = f2->next;
+ }
+ }
+ *l = f1 ? : f2;
+ return x;
+}
+
+static void
+P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
+{
+ struct fastbuf *in = *fb1;
+ struct fastbuf *out1 = NULL;
+ struct fastbuf *out2 = NULL;
+ struct fastbuf *tbuf;
+ byte *buffer, *bufend, *current;
+ SORT_NODE *first, **last, *this, *leftover;
+ int cont = 1;
+ uns run_count = 0;
+ uns giant_count = 0;
+ uns split_count = 0;
+
+ ASSERT(!*fb2);
+ if (sorter_presort_bufsize < 2*sizeof(SORT_NODE))
+ die("PresortBuffer set too low");
+ buffer = xmalloc(sorter_presort_bufsize);
+ bufend = buffer + sorter_presort_bufsize;
+ leftover = NULL;
+ while (cont)
+ {
+ SWAP(out1, out2, tbuf);
+ if (!out1)
+ out1 = bopen_tmp(sorter_stream_bufsize);
+ current = buffer;
+ last = &first;
+ if (leftover)
+ {
+ memmove(buffer, leftover, sizeof(SORT_NODE));
+ this = leftover = (SORT_NODE *) buffer;
+ split_count++;
+ goto get_data;
+ }
+ for(;;)
+ {
+ current = (byte *) ALIGN((addr_int_t) current, CPU_STRUCT_ALIGN);
+ if (current + sizeof(*this) > bufend)
+ break;
+ this = (SORT_NODE *) current;
+ cont = P(fetch_key)(in, &this->key);
+ if (!cont)
+ break;
+ get_data:
+ current = P(fetch_item)(in, &this->key, bufend);
+ if (!current)
+ {
+ if (leftover) /* Single node too large */
+ {
+ P(copy_data)(in, out1, &leftover->key);
+ leftover = NULL;
+ run_count++;
+ giant_count++;
+ }
+ else /* Node will be left over to the next phase */
+ leftover = this;
+ break;
+ }
+ *last = this;
+ last = &this->next;
+ leftover = NULL;
+ }
+ *last = NULL;
+ if (!first)
+ continue;
+
+ first = P(mergesort)(first);
+ run_count++;
+ while (first)
+ {
+#ifdef SORT_UNIFY
+ SORT_NODE *second = first->next;
+ if (second && !P(compare)(&first->key, &second->key))
+ {
+ SORT_KEY *n = P(merge_items)(&first->key, &second->key);
+ if (n == &first->key)
+ first->next = second->next;
+ else if (n)
+ first = first->next;
+ else
+ first = second->next;
+ continue;
+ }
+#endif
+#ifdef SORT_ASSERT_UNIQUE
+ ASSERT(!first->next || P(compare)(&first->key, &first->next->key));
+#endif
+ P(store_item)(out1, &first->key);
+ first = first->next;
+ }
+ }
+
+ bclose(in);
+ if (sorter_trace)
+ log(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));
+ *fb1 = P(flush_out)(out1);
+ *fb2 = P(flush_out)(out2);
+ xfree(buffer);
}
+#endif /* SORT_REGULAR && !SORT_UNIFY */
+
+#endif /* SORT_PRESORT */
+
static
#ifdef SORT_OUTPUT_FB
struct fastbuf *
#ifdef SORT_INPUT_FILE
struct fastbuf *fb1, *fb2;
fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize);
-#ifdef SORT_DELETE_INPUT
- fb1->is_temp_file = SORT_DELETE_INPUT;
-#endif
fb2 = NULL;
#elif defined(SORT_INPUT_FB)
struct fastbuf *fb2 = NULL;
#endif
+#ifdef SORT_DELETE_INPUT
+ bconfig(fb1, BCONFIG_IS_TEMP_FILE, SORT_DELETE_INPUT);
+#endif
sorter_pass_counter = 1;
- do P(pass)(&fb1, &fb2); while (fb1 && fb2);
+#ifdef SORT_PRESORT
+ P(presort)(&fb1, &fb2);
+ if (fb2)
+#endif
+ do P(pass)(&fb1, &fb2); while (fb1 && fb2);
if (!fb1)
- fb1 = fb2;
- fb1->is_temp_file = 0;
+ fb1 = bopen_tmp(sorter_stream_bufsize);
#ifdef SORT_OUTPUT_FB
return fb1;
#else
+ bconfig(fb1, BCONFIG_IS_TEMP_FILE, 0);
if (rename(fb1->name, outname) < 0)
die("rename(%s,%s): %m", fb1->name, outname);
+ bclose(fb1);
#endif
}
#undef P
#undef LESS
#undef SWAP
+#undef SORT_NODE
+#undef SORT_KEY
+#undef SORT_PREFIX
+#undef SORT_UNIFY
+#undef SORT_UNIQUE
+#undef SORT_ASSERT_UNIQUE
+#undef SORT_REGULAR
+#undef SORT_DELETE_INPUT
+#undef SORT_INPUT_FILE
+#undef SORT_INPUT_FB
+#undef SORT_INPUT_FBPAIR
+#undef SORT_OUTPUT_FILE
+#undef SORT_OUTPUT_FB
#endif /* !SORT_DECLARE_ONLY */
projects / libucw.git / blobdiff