Most of sorting an array in memory is wired up.

Signed-off-by: Gediminas Jakutis <gediminas@varciai.lt>

5 files changed, 75 insertions, 24 deletions

diff --git a/src/cache.c b/src/cache.c
index 0c99322..f8a2026 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -47,8 +47,10 @@ int cache_populate(struct stream * const in)
 				break;
 			}
 		}
+	} else if (in->type == stream_in) {
+		try(1, err, ENOSYS, "populating cache from file is a TODO");
 	} else {
-		/* TODO */
+		try(1, err, EINVAL, "cannot populate a non-reading stream cache");
 	}
 
 err:
@@ -92,7 +94,7 @@ int cache_block_copy(struct stream const * const src, struct stream * const dest
 
 	try(src->settings->access != cached || dest->settings->access != cached, err, EINVAL, "cannot cache-copy between uncached streams");
 	try(!src->cache, err, EINVAL, "no cache to transfer");
-	try(!(src->n < dest->settings->to), err, EINVAL, "invalid copy size");
+	try(src->n > dest->settings->to, err, EINVAL, "invalid copy size");
 	try(!dest->cache, err, EINVAL, "no cache to transfer to");
 
 	memcpy(dest->cache, src->cache_a + dest->settings->ss, (dest->settings->to - dest->settings->ss) * dest->settings->stride);
@@ -109,7 +111,7 @@ int cache_list_copy(struct stream * const src, struct stream * const dest)
 
 	try(src->settings->access != cached || dest->settings->access != cached, err, EINVAL, "cannot cache-copy between uncached streams");
 	try(!src->cache, err, EINVAL, "no cache to transfer");
-	try(!(src->n < dest->settings->to), err, EINVAL, "invalid copy size");
+	try(!(src->n > dest->settings->to), err, EINVAL, "invalid copy size");
 	try(!dest->cache, err, EINVAL, "no cache to transfer to");
 
 	while ((tmp = get(src))) {
@@ -125,18 +127,38 @@ err:
 int cache_block_split(struct stream * const src, struct stream * const A, struct stream * const B)
 {
 	int ret = 0;
+	struct settings tmp_settings;
 
 	try(src->n < 2, err, EINVAL, "cannot split single element stream.");
 
-	/* copy everything, then change whatever's neccesary */
-	*A = *B = *src;
-
-	A->n = A->n / 2 + A->n % 2;
-	B->n = B->n / 2;
+	/* setting up minimal stream basics */
+	A->n = src->n / 2;
+	B->n = src->n / 2 + (src->n & 1ul);
 	A->index = B->index = 0;
-	B->cache_a = B->cache_a + A->n;
-	B->cache_l = (struct entry_l *) B->cache_a;
-	B->cache = (char *) B->cache_a;
+	A->parentid = B->parentid = random(); /* generate random parent ID that needs to match between children */
+	A->type = B->type = stream_invalid; /* disallow any stream operations other than split/merge on children */
+	A->fd = B->fd = -1; /* if we're splitting, these are for holding cache only */
+	/* we only care about these three functions for these temporary streams */
+	A->get_next_element_cache = B->get_next_element_cache = src->get_next_element_cache;
+	A->place_next_element_cache = B->place_next_element_cache = src->place_next_element_cache;
+	A->split = B->split = src->split;
+
+	tmp_settings = *src->settings;
+	A->settings = B->settings = &tmp_settings;
+
+	/* setting up A */
+	tmp_settings.ss = 0;
+	tmp_settings.to = A->n;
+	try_s((ret = cache_create(A)), err);
+	try_s((ret = cache_block_copy(src, A)), err);
+
+	/* setting up B */
+	tmp_settings.ss = A->n;
+	tmp_settings.to = src->n;
+	try_s((ret = cache_create(B)), err);
+	try_s((ret = cache_block_copy(src, B)), err);
+
+	A->settings = B->settings = &tmp_settings;
 
 err:
 	return ret;
diff --git a/src/defs.h b/src/defs.h
index 5f1a733..8396015 100644
--- a/src/defs.h
+++ b/src/defs.h
@@ -97,12 +97,11 @@ enum streamtype {
 };
 
 struct stream {
-	struct stream *parent;
+	long int parentid;
 	size_t n;
 	int fd;
 	enum streamtype type;
 	char *name;
-	size_t stride;
 	size_t index;
 	struct entry_l *pnode; /* "previous" node */
 	struct entry_l *cnode; /* "current" node */
diff --git a/src/main.c b/src/main.c
index 390be6a..c2d24ce 100644
--- a/src/main.c
+++ b/src/main.c
@@ -12,6 +12,7 @@
 #include "defs.h"
 #include "cache.h"
 #include "datagen.h"
+#include "mergesort.h"
 
 static struct settings settings = {0};
 
@@ -64,11 +65,11 @@ int main(int argc, char **argv)
 			}
 			break;
 		case mode_generate:
-				try_s((ret = cache_transfer(&file_in, &file_out)), out);
-				break;
+			try_s((ret = cache_transfer(&file_in, &file_out)), out);
+			break;
 		case mode_normal:
-				/* TODO */
-				;
+			try_s((ret = cache_create(&file_out)), out);
+			try_s((ret = merge_sort(&file_in, &file_out)), out);
 		}
 
 	} else { /* uncached */
@@ -175,21 +176,23 @@ int load_io_functions(struct settings const * const s, struct stream * const in)
 
 	if (in->type == stream_out) {
 		if (s->format == array) {
-			/* TODO */
-		} else {
+			in->get_next_element_cache = cached_get_array;
+			in->place_next_element_cache = cached_put_array;
+		} else { /* if (s->format == list */
 			/* TODO */
 		}
 	} else if (in->type == stream_in) { /* reading streams do not support dumping */
 		if (s->format == array) {
-			/* TODO */
-		} else {
+			in->get_next_element_cache = cached_get_array;
+			in->place_next_element_cache = cached_put_array;
+		} else { /* if (s->format == list */
 			/* TODO */
 		}
 	} else if (in->type == stream_randread) { /* data generation streams do not support dumping nor any cache I/O beyond initial data generation */
 		if (s->format == array) {
 			in->get_next_element_direct = gen_get_array;
 			in->place_next_element_cache = cached_put_array;
-		} else {
+		} else { /* if (s->format == list */
 			in->get_next_element_direct = gen_get_list;
 			in->place_next_element_cache = cached_put_list;
 		}
diff --git a/src/mergesort.c b/src/mergesort.c
index 2562d9d..c431b31 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -5,15 +5,41 @@
 #include <errno.h>
 #include <stdlib.h>
 #include "defs.h"
+#include "io.h"
 #include "mergesort.h"
 
+/* 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. */
+	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 */
+		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 */
+	}
+
+	for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) {
+		stream_close(tmp + i);
+	}
+
+err:
+	return ret;
+}
+
 int merge(struct stream * const dest, struct stream * const A, struct stream * const B)
 {
-	int ret;
+	int ret = 0;
 	struct entry_l *a;
 	struct entry_l *b;
 
-	try(A->parent != B->parent, err, EINVAL, "cannot merge blocks: uncommon parent!");
+	try(A->parentid != B->parentid, err, EINVAL, "cannot merge blocks: uncommon parent!");
 
 	a = get(A);
 	b = get(B);
diff --git a/src/mergesort.h b/src/mergesort.h
index 8ac3ab5..ea66a8b 100644
--- a/src/mergesort.h
+++ b/src/mergesort.h
@@ -7,6 +7,7 @@
 
 #include "defs.h"
 
+int merge_sort(struct stream * const src, struct stream * const dest);
 int merge(struct stream * const dest, struct stream * const A, struct stream * const B);
 
 #endif /* ALGOS_MERGESORT_H_INCLUDED */