From 29712a5098842ea3930ec00ddd1c0b9d264ba9b5 Mon Sep 17 00:00:00 2001
From: Gediminas Jakutis <gediminas@varciai.lt>
Date: Sun, 21 Feb 2021 13:16:54 +0200
Subject: in-memory array sorting: GET!

lists need a bit more work and after that, in-file should shortly
follow.

Signed-off-by: Gediminas Jakutis <gediminas@varciai.lt>
---
 src/mergesort.c | 32 +++++++++++++++++++-------------
 1 file changed, 19 insertions(+), 13 deletions(-)

(limited to 'src/mergesort.c')

diff --git a/src/mergesort.c b/src/mergesort.c
index c431b31..7391544 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -5,42 +5,49 @@
 #include <errno.h>
 #include <stdlib.h>
 #include "defs.h"
-#include "io.h"
+#include "stream.h"
 #include "mergesort.h"
 
+static int merge(struct stream * const dest, struct stream * const A, struct stream * const B);
+
 /* bottom-up variantas */
 
 int merge_sort(struct stream * const src, struct stream * const dest)
 {
 	int ret = 0;
-	struct stream tmp[4]; /* I can't into stream reuse, hence four. A yeet, followed by a dab. */
+	struct stream tmp[4] = {0}; /* I can't into stream reuse, hence four. A yeet, followed by a dab. */
 	size_t i;
 
 	try(!src || !dest, err, EINVAL, "cannot sort what's not there");
 
-	if (src->n > 1) { /* stream of size one is inherently sorted */
+	try_s((ret = stream_shallow_copy(src, dest)), err);
+
+	if (src->n > 1) {
 		src->split(src, tmp, tmp + 2); /* split stream in half */
-		merge_sort(tmp + 1, tmp); /* recurse-sort first half */
-		merge_sort(tmp + 3, tmp + 2); /* recurse-sort second half */
-		merge(dest, tmp, tmp + 2); /* merge the two halves back */
-	}
+		merge_sort(tmp, tmp + 1); /* recurse-sort first half */
+		merge_sort(tmp + 2, tmp + 3); /* recurse-sort second half */
+		merge(dest, tmp + 1, tmp + 3); /* merge the two halves back */
+		dest->rewind(dest);
 
-	for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) {
-		stream_close(tmp + i);
+		for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) {
+			stream_close(tmp + i);
+		}
+	} else { /* stream of size one is inherently sorted, simply src with dest */
+		*tmp = *dest;
+		*dest = *src;
+		*src = *tmp;
 	}
 
 err:
 	return ret;
 }
 
-int merge(struct stream * const dest, struct stream * const A, struct stream * const B)
+static int merge(struct stream * const dest, struct stream * const A, struct stream * const B)
 {
 	int ret = 0;
 	struct entry_l *a;
 	struct entry_l *b;
 
-	try(A->parentid != B->parentid, err, EINVAL, "cannot merge blocks: uncommon parent!");
-
 	a = get(A);
 	b = get(B);
 
@@ -54,7 +61,6 @@ int merge(struct stream * const dest, struct stream * const A, struct stream * c
 		}
 	}
 
-err:
 	return ret;
 }
 
-- 
cgit v1.2.3