X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fsorter.h;h=c2da83113646d0d1762786e491e67c731f9e02c7;hb=5bb0345810e5d0097488fffd1216b9ed0b4b9d05;hp=0ed5e04d1f13fd6a59e51640b2d6c935e9dc4675;hpb=23f2f5abfec1098ce98afa88b8308b869d59216c;p=libucw.git

diff --git a/lib/sorter.h b/lib/sorter.h
index 0ed5e04d..c2da8311 100644
--- a/lib/sorter.h
+++ b/lib/sorter.h
@@ -1,7 +1,10 @@
 /*
  *	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.
  */
 
 /*
@@ -15,16 +18,27 @@
  *  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:
@@ -41,14 +55,16 @@
  *			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
@@ -60,6 +76,9 @@
  *			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 */
@@ -71,8 +90,7 @@ extern uns sorter_trace;
 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 */
 
@@ -83,6 +101,7 @@ struct fastbuf *sorter_open_tmp(void);
 #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.
@@ -97,6 +116,46 @@ struct fastbuf *sorter_open_tmp(void);
 #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)
 {
@@ -131,7 +190,7 @@ 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)
@@ -147,13 +206,17 @@ P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
 	{
 	  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
 	{
@@ -175,21 +238,238 @@ P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
     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 *
@@ -216,30 +496,48 @@ struct fastbuf *fb1, struct fastbuf *fb2
 #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 */