Move wikisort/grailsort common code to a shared header

4 files changed, 123 insertions, 210 deletions

diff --git a/common.h b/common.h
new file mode 100644
index 0000000..984d890
--- /dev/null
+++ b/common.h
@@ -0,0 +1,107 @@
+#include <stddef.h>
+#include <stdint.h>
+
+#include "sorters.h"
+
+static void swap(char *a, char *b, size_t width)
+{
+	while (width--) {
+		char tmp = *a;
+		*a++ = *b;
+		*b++ = tmp;
+	}
+}
+
+static void reverse(char *base, size_t nmel, size_t width)
+{
+	char *last = base + (nmel - 1) * width;
+	while (last > base) {
+		swap(base, last, width);
+		base += width;
+		last -= width;
+	}
+}
+
+/* rotates left */
+static void rotate(char *base, size_t nmel, size_t width, size_t shift)
+{
+	reverse(base, shift, width);
+	reverse(base + shift * width, nmel - shift, width);
+	reverse(base, nmel, width);
+}
+
+/* If a matching element exists, returns index of one of them.
+   If none exists, returns index where such an element should be inserted. */
+static size_t binary_search(const char *needle, char *haystack, size_t nmel, size_t width, cmpfun cmp)
+{
+	size_t baseidx = 0;
+	while (nmel) {
+		size_t tryidx = baseidx + nmel / 2;
+		char *try = haystack + tryidx * width;
+		int sign = cmp(try, needle);
+		if (!sign) return tryidx;
+		else if (sign < 0) {
+			baseidx = tryidx + 1;
+			nmel -= nmel / 2 + 1;
+		}
+		else {
+			nmel /= 2;
+		}
+	}
+	return baseidx;
+}
+
+static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
+{
+	char *sorted = base + bufnmel * width;
+	while (bufnmel) {
+		char *last = sorted - width;
+		size_t equals;
+		for (equals = 1; equals < bufnmel; equals++) {
+			if (cmp(last, last - equals * width)) break;
+		}
+
+		size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp);
+		rotate(sorted - equals * width, insertpos + equals, width, equals);
+
+		bufnmel  -= equals;
+		sortnmel += equals;
+		sorted   -= equals * width;
+	}
+}
+
+#define MAX_SORTNET 8
+
+static const uint8_t sortnet[][2] = {
+	/* 0: index =  0 */
+	/* 1: index =  0 */
+	/* 2: index =  0 */
+	{0,1},
+	/* 3: index =  1 */
+	{0,1}, {0,2}, {1,2},
+	/* 4: index =  4 */
+	{0,1}, {2,3}, {0,2}, {1,3}, {1,2},
+	/* 5: index =  9 */
+	{0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2},
+	/* 6: index = 18 */
+	{1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4},
+	{1,3}, {2,3},
+	/* 7: index = 30 */
+	{1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4},
+	{1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3},
+	/* 8: index = 46 */
+	{0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6},
+	{0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4},
+	/* 9: index = 65, if we used a sorting network this large */
+};
+
+static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };
+
+static void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp)
+{
+	for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
+		char *elem1 = base + sortnet[i][0] * width;
+		char *elem2 = base + sortnet[i][1] * width;
+		if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
+	}
+}
diff --git a/grailsort.c b/grailsort.c
index c7a4074..5edf40b 100644
--- a/grailsort.c
+++ b/grailsort.c
@@ -3,59 +3,19 @@
 #include <stdint.h>
 
 #include "sorters.h"
+#include "common.h"
 
 #define TAIL(base,nmel,width) ((base) + ((nmel) - 1) * (width))
 
-static void swap(char *a, char *b, size_t width)
-{
-	while (width--) {
-		char tmp = *a;
-		*a++ = *b;
-		*b++ = tmp;
-	}
-}
-
-static void reverse(char *base, size_t nmel, size_t width)
-{
-	char *last = base + (nmel - 1) * width;
-	while (last > base) {
-		swap(base, last, width);
-		base += width;
-		last -= width;
-	}
-}
-
-/* rotates left */
-static void rotate(char *base, size_t nmel, size_t width, size_t shift)
-{
-	reverse(base, shift, width);
-	reverse(base + shift * width, nmel - shift, width);
-	reverse(base, nmel, width);
-}
-
-/* If a matching element exists, returns index of one of them.
-   If none exists, returns index where such an element should be inserted. */
-static size_t binary_search(const char *needle, char *haystack,
-	size_t nmel, size_t width, cmpfun cmp)
+/* get index of last block whose head is less than the previous block's tail */
+static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp)
 {
-	size_t baseidx = 0;
-	while (nmel) {
-		size_t tryidx = baseidx + nmel / 2;
-		char *try = haystack + tryidx * width;
-		int sign = cmp(try, needle);
-		if (!sign) return tryidx;
-		else if (sign < 0) {
-			baseidx = tryidx + 1;
-			nmel -= nmel / 2 + 1;
-		}
-		else {
-			nmel /= 2;
-		}
-	}
-	return baseidx;
+	for (char *cur = TAIL(base, bcount, bwidth); --bcount; cur -= bwidth)
+		if (cmp(cur - width, cur) > 0) break;
+	return bcount;
 }
 
-static size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t width, cmpfun cmp)
+size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t width, cmpfun cmp)
 {
 	char *a = buf;
 	char *b = base + anmel * width;
@@ -82,72 +42,11 @@ static size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t wi
 	return sorted;
 }
 
-/* get index of last block whose head is less than the previous block's tail */
-static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp)
-{
-	for (char *cur = TAIL(base, bcount, bwidth); --bcount; cur -= bwidth)
-		if (cmp(cur - width, cur) > 0) break;
-	return bcount;
-}
-
-static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
-{
-	char *sorted = base + bufnmel * width;
-	while (bufnmel) {
-		char *last = sorted - width;
-		size_t equals;
-		for (equals = 1; equals < bufnmel; equals++) {
-			if (cmp(last, last - equals * width)) break;
-		}
-
-		size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp);
-		rotate(sorted - equals * width, insertpos + equals, width, equals);
-
-		bufnmel  -= equals;
-		sortnmel += equals;
-		sorted   -= equals * width;
-	}
-}
-
-static const uint8_t sortnet[][2] = {
-	/* 0: index =  0 */
-	/* 1: index =  0 */
-	/* 2: index =  0 */
-	{0,1},
-	/* 3: index =  1 */
-	{0,1}, {0,2}, {1,2},
-	/* 4: index =  4 */
-	{0,1}, {2,3}, {0,2}, {1,3}, {1,2},
-	/* 5: index =  9 */
-	{0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2},
-	/* 6: index = 18 */
-	{1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4},
-	{1,3}, {2,3},
-	/* 7: index = 30 */
-	{1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4},
-	{1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3},
-	/* 8: index = 46 */
-	{0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6},
-	{0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4},
-	/* 9: index = 65, if we used a sorting network this large */
-};
-
-static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };
-
-static void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp)
-{
-	for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
-		char *elem1 = base + sortnet[i][0] * width;
-		char *elem2 = base + sortnet[i][1] * width;
-		if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
-	}
-}
-
 void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 {
 	char *base = unsorted;
 
-	if (nmel <= 8) {
+	if (nmel <= MAX_SORTNET) {
 		sorting_network(base, nmel, width, cmp);
 		return;
 	}
diff --git a/sorters.h b/sorters.h
index 76c5443..dbaf59e 100644
--- a/sorters.h
+++ b/sorters.h
@@ -1,3 +1,6 @@
+#ifndef SORTERS_H
+#define SORTERS_H
+
 #include <stddef.h>
 
 void assert_sorted(int *buffer, size_t size);
@@ -17,3 +20,5 @@ extern const struct sorter {
 	const char *name;
 	sorterfn func;
 } sorters[];
+
+#endif
diff --git a/wikisort.c b/wikisort.c
index ba4db55..b04b3ff 100644
--- a/wikisort.c
+++ b/wikisort.c
@@ -1,42 +1,14 @@
 #include <math.h>
 #include <stddef.h>
-#include <stdint.h>
-#include <string.h>
 
 #include "sorters.h"
+#include "common.h"
 
 struct array {
 	char  *base;
 	size_t nmel;
 };
 
-static void swap(char *a, char *b, size_t width)
-{
-	while (width--) {
-		char tmp = *a;
-		*a++ = *b;
-		*b++ = tmp;
-	}
-}
-
-static void reverse(char *base, size_t nmel, size_t width)
-{
-	char *last = base + (nmel - 1) * width;
-	while (last > base) {
-		swap(base, last, width);
-		base += width;
-		last -= width;
-	}
-}
-
-/* rotates left */
-static void rotate(char *base, size_t nmel, size_t width, size_t shift)
-{
-	reverse(base, shift, width);
-	reverse(base + shift * width, nmel - shift, width);
-	reverse(base, nmel, width);
-}
-
 /* buf must be large enough to hold as->nmel elements */
 static void merge_blocks(char *buf, struct array *as, size_t bs_nmel, size_t width, cmpfun cmp)
 {
@@ -69,28 +41,6 @@ static char *find_min_block(char *base, size_t count, size_t bwidth, size_t widt
 	return min;
 }
 
-/* If a matching element exists, returns index of one of them.
-   If none exists, returns index where such an element should be inserted. */
-static size_t binary_search(const char *needle, char *haystack,
-	size_t nmel, size_t width, cmpfun cmp)
-{
-	size_t baseidx = 0;
-	while (nmel) {
-		size_t tryidx = baseidx + nmel / 2;
-		char *try = haystack + tryidx * width;
-		int sign = cmp(try, needle);
-		if (!sign) return tryidx;
-		else if (sign < 0) {
-			baseidx = tryidx + 1;
-			nmel -= nmel / 2 + 1;
-		}
-		else {
-			nmel /= 2;
-		}
-	}
-	return baseidx;
-}
-
 static size_t roll(struct array *a, struct array *b,
 	size_t bwidth, size_t width, char **mina, cmpfun cmp)
 {
@@ -106,60 +56,12 @@ static size_t roll(struct array *a, struct array *b,
 	return iters;
 }
 
-static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
-{
-	char *sorted = base + bufnmel * width;
-	while (bufnmel) {
-		char *last = sorted - width;
-		size_t equals;
-		for (equals = 1; equals < bufnmel; equals++) {
-			if (cmp(last, last - equals * width)) break;
-		}
-
-		size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp);
-		rotate(sorted - equals * width, insertpos + equals, width, equals);
-
-		bufnmel  -= equals;
-		sortnmel += equals;
-		sorted   -= equals * width;
-	}
-}
-
-static const uint8_t sortnet[][2] = {
-	/* 0: index =  0 */
-	/* 1: index =  0 */
-	/* 2: index =  0 */
-	{0,1},
-	/* 3: index =  1 */
-	{0,1}, {0,2}, {1,2},
-	/* 4: index =  4 */
-	{0,1}, {2,3}, {0,2}, {1,3}, {1,2},
-	/* 5: index =  9 */
-	{0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2},
-	/* 6: index = 18 */
-	{1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4},
-	{1,3}, {2,3},
-	/* 7: index = 30 */
-	{1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4},
-	{1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3},
-	/* 8: index = 46 */
-	{0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6},
-	{0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4},
-	/* 9: index = 65, if we used a sorting network this large */
-};
-static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };
-
 void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 {
 	char *base = unsorted;
 
-	/* use a sorting network for small inputs */
-	if (nmel <= 8) {
-		for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
-			char *elem1 = base + sortnet[i][0] * width;
-			char *elem2 = base + sortnet[i][1] * width;
-			if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
-		}
+	if (nmel <= MAX_SORTNET) {
+		sorting_network(base, nmel, width, cmp);
 		return;
 	}