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

diff --git a/lib/sorter.h b/lib/sorter.h
index 0ed5e04d..d1f059fc 100644
--- a/lib/sorter.h
+++ b/lib/sorter.h
@@ -21,10 +21,12 @@
  *			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 +43,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
@@ -83,6 +87,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 +102,17 @@ struct fastbuf *sorter_open_tmp(void);
 #define LESS <=
 #endif
 
+static struct fastbuf *
+P(flush_out)(struct fastbuf *out)
+{
+  if (out)
+    {
+      bflush(out);
+      bsetpos(out, 0);
+    }
+  return out;
+}
+
 static void
 P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
 {
@@ -147,7 +163,7 @@ 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);
@@ -175,21 +191,165 @@ 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
+
+#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(out1);
-      bsetpos(out1, 0);
+      *l1 = x;
+      l1 = &x->next;
+      x = x->next;
+      if (!x)
+	break;
+      *l2 = x;
+      l2 = &x->next;
+      x = x->next;
     }
-  if (out2)
+  *l1 = *l2 = NULL;
+
+  if (f1 && f1->next)
+    f1 = P(mergesort)(f1);
+  if (f2 && f2->next)
+    f2 = P(mergesort)(f2);
+  l = &x;
+  while (f1 && f2)
     {
-      bflush(out2);
-      bsetpos(out2, 0);
+      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;
+	}
     }
-  *fb1 = out1;
-  *fb2 = out2;
-  sorter_pass_counter++;
+  *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 = sorter_open_tmp();
+      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
+	  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);
 }
 
+#endif		/* SORT_PRESORT */
+
 static
 #ifdef SORT_OUTPUT_FB
 struct fastbuf *
@@ -216,30 +376,36 @@ 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
+  fb1->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 = sorter_open_tmp();
 
 #ifdef SORT_OUTPUT_FB
   return fb1;
 #else
+  fb1->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
 
 #endif		/* !SORT_DECLARE_ONLY */