+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
+ 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_PRESORT */
+