X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fsorter.h;h=15ff9bf7b16bc0378b8231a579cd7035ea8dd088;hb=d775f3ca9c8619bc1f0d2f98a9518fed60fe6658;hp=4c42d7788d90b04771e8ed31840705acdd25ef7a;hpb=75eea53f8050dc1482de088b3cbd081b2511c5a4;p=libucw.git diff --git a/lib/sorter.h b/lib/sorter.h index 4c42d778..15ff9bf7 100644 --- a/lib/sorter.h +++ b/lib/sorter.h @@ -1,7 +1,8 @@ /* - * Sherlock Library -- Universal Sorter + * UCW Library -- Universal Sorter * - * (c) 2001--2003 Martin Mares + * (c) 2001--2004 Martin Mares + * (c) 2004 Robert Spalek * * This software may be freely distributed and used according to the terms * of the GNU Lesser General Public License. @@ -18,12 +19,20 @@ * 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 pre-sorting pass. Beware, when in + * the pre-sorting mode, it's quite possible that the + * comparison function will be called with both arguments + * identical. + * 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 * anything else than the key. In this case, the sorter * automatically supplies fetch_key, copy_data, fetch_item - * and store_item functions. + * 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 @@ -111,6 +120,10 @@ extern uns sorter_pass_counter; #define LESS <= #endif +#if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS) +#define SORT_ASSERT_UNIQUE +#endif + #ifdef SORT_REGULAR static inline int @@ -143,15 +156,16 @@ static struct fastbuf * P(flush_out)(struct fastbuf *out) { if (out) - { - bflush(out); - bsetpos(out, 0); - } + brewind(out); 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; @@ -182,7 +196,10 @@ P(pass)(struct fastbuf **fb1, struct fastbuf **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++; @@ -207,6 +224,10 @@ P(pass)(struct fastbuf **fb1, struct fastbuf **fb2) run2 = next2 && (P(compare)(kprev2, kin2) LESS 0); kout = kprev2; } +#endif +#ifdef SORT_ASSERT_UNIQUE + else if (unlikely(comp == 0)) + ASSERT(0); #endif else { @@ -231,10 +252,81 @@ P(pass)(struct fastbuf **fb1, struct fastbuf **fb2) *fb1 = P(flush_out)(out1); *fb2 = P(flush_out)(out2); sorter_pass_counter++; + return run_count; } #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(;;) + { + 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= 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++; +#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); + } + last_out = array[n-1]; + bwrite(out1, array, n * sizeof(SORT_KEY)); + } + + 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 { @@ -308,7 +400,10 @@ P(presort)(struct fastbuf **fb1, struct fastbuf **fb2) leftover = NULL; while (cont) { - SWAP(out1, out2, tbuf); +#ifdef SORT_UP_TO + if (sorter_presort_bufsize < SORT_UP_TO) +#endif + SWAP(out1, out2, tbuf); if (!out1) out1 = bopen_tmp(sorter_stream_bufsize); current = buffer; @@ -369,6 +464,9 @@ P(presort)(struct fastbuf **fb1, struct fastbuf **fb2) 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; @@ -386,6 +484,8 @@ P(presort)(struct fastbuf **fb1, struct fastbuf **fb2) xfree(buffer); } +#endif /* SORT_REGULAR && !SORT_UNIFY */ + #endif /* SORT_PRESORT */ static @@ -427,7 +527,27 @@ struct fastbuf *fb1, struct fastbuf *fb2 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); @@ -448,6 +568,8 @@ struct fastbuf *fb1, struct fastbuf *fb2 #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 @@ -455,5 +577,7 @@ struct fastbuf *fb1, struct fastbuf *fb2 #undef SORT_INPUT_FBPAIR #undef SORT_OUTPUT_FILE #undef SORT_OUTPUT_FB +#undef SORT_PRESORT +#undef SORT_UP_TO #endif /* !SORT_DECLARE_ONLY */