Split helper functions into their own translation units

7 files changed, 115 insertions, 92 deletions

diff --git a/bsearch.c b/bsearch.c
index 3c94d45..39e0711 100644
--- a/bsearch.c
+++ b/bsearch.c
@@ -1,6 +1,6 @@
 #include <stddef.h>
 
-#include "sorters.h"
+#include "common.h"
 
 /* If a matching element exists, returns index of one of them.
    If none exists, returns index where such an element should be inserted. */
diff --git a/common.h b/common.h
index 4eb5d9c..e6c5662 100644
--- a/common.h
+++ b/common.h
@@ -1,96 +1,19 @@
+#ifndef COMMON_H
+#define COMMON_H
+
 #include <stddef.h>
 #include <stdint.h>
 
-#include "sorters.h"
-
-size_t binary_search(const char *needle, char *haystack, size_t nmel, size_t width, cmpfun cmp);
-
-static void swap(char *a, char *b, size_t width)
-{
-#ifdef __GNUC__
-	typedef uint32_t __attribute__((__may_alias__)) u32;
-
-	if ((uintptr_t)a % 4 == 0 && (uintptr_t)b % 4 == 0) {
-		for (; width >= 4; width -= 4) {
-			uint32_t tmp = *((u32*)a);
-			*((u32*)a) = *((u32*)b);
-			*((u32*)b) = tmp;
-			a += 4;
-			b += 4;
-		}
-	}
-#endif
-
-	while (width--) {
-		char tmp = *a;
-		*a++ = *b;
-		*b++ = tmp;
-	}
-}
-
-/* rotates left */
-static void rotate(char *base, size_t size, size_t shift)
-{
-	int dir = 1;
-	while (shift) {
-		while (2*shift <= size) {
-			swap(base, base + dir*shift, shift);
-			size -= shift;
-			base += shift*dir;
-		}
-		shift = size - shift;
-		base  = dir > 0 ? base + size - shift : base - shift;
-		dir  *= -1;
-	}
-}
-
-static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
-{
-	while (bufnmel && sortnmel) {
-		char  *sorted    = base + bufnmel * width;
-		size_t insertpos = binary_search(base, sorted, sortnmel, width, cmp);
-		if (insertpos > 0) {
-			rotate(base, (bufnmel + insertpos) * width, bufnmel * width);
-		}
+typedef int  (*cmpfun)(const void *, const void *);
+typedef void (*sorterfn)(void *, size_t, size_t, cmpfun);
 
-		base     += (insertpos + 1) * width;
-		bufnmel  -= 1;
-		sortnmel -= insertpos;
-	}
-}
+size_t binary_search(const char *, char *, size_t, size_t, cmpfun);
+void distribute_buffer(char *, size_t, size_t, size_t, cmpfun);
+void swap(char *, char *, size_t);
+void rotate(char *, size_t, size_t);
 
 #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 */
-};
+void sorting_network(char *, size_t, size_t, cmpfun);
 
-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);
-	}
-}
+#endif
diff --git a/distribute.c b/distribute.c
new file mode 100644
index 0000000..d2d1eff
--- /dev/null
+++ b/distribute.c
@@ -0,0 +1,18 @@
+#include <stddef.h>
+
+#include "common.h"
+
+void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
+{
+	while (bufnmel && sortnmel) {
+		char  *sorted    = base + bufnmel * width;
+		size_t insertpos = binary_search(base, sorted, sortnmel, width, cmp);
+		if (insertpos > 0) {
+			rotate(base, (bufnmel + insertpos) * width, bufnmel * width);
+		}
+
+		base     += (insertpos + 1) * width;
+		bufnmel  -= 1;
+		sortnmel -= insertpos;
+	}
+}
diff --git a/rotate.c b/rotate.c
new file mode 100644
index 0000000..5eb7696
--- /dev/null
+++ b/rotate.c
@@ -0,0 +1,19 @@
+#include <stddef.h>
+
+#include "common.h"
+
+/* rotates left */
+void rotate(char *base, size_t size, size_t shift)
+{
+	int dir = 1;
+	while (shift) {
+		while (2*shift <= size) {
+			swap(base, base + dir*shift, shift);
+			size -= shift;
+			base += shift*dir;
+		}
+		shift = size - shift;
+		base  = dir > 0 ? base + size - shift : base - shift;
+		dir  *= -1;
+	}
+}
diff --git a/sorters.h b/sorters.h
index 5461914..0a63a89 100644
--- a/sorters.h
+++ b/sorters.h
@@ -2,9 +2,7 @@
 #define SORTERS_H
 
 #include <stddef.h>
-
-typedef int  (*cmpfun)(const void *, const void *);
-typedef void (*sorterfn)(void *, size_t, size_t, cmpfun);
+#include "common.h"
 
 void musl_smoothsort(void *, size_t, size_t, cmpfun);
 void musl_heapsort(void *, size_t, size_t, cmpfun);
diff --git a/sortnet.c b/sortnet.c
new file mode 100644
index 0000000..fd99a17
--- /dev/null
+++ b/sortnet.c
@@ -0,0 +1,38 @@
+#include <stddef.h>
+#include <stdint.h>
+
+#include "common.h"
+
+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 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/swap.c b/swap.c
new file mode 100644
index 0000000..626abb0
--- /dev/null
+++ b/swap.c
@@ -0,0 +1,27 @@
+#include <stddef.h>
+#include <stdint.h>
+
+#include "common.h"
+
+void swap(char *a, char *b, size_t width)
+{
+#ifdef __GNUC__
+	typedef uint32_t __attribute__((__may_alias__)) u32;
+
+	if ((uintptr_t)a % 4 == 0 && (uintptr_t)b % 4 == 0) {
+		for (; width >= 4; width -= 4) {
+			uint32_t tmp = *((u32*)a);
+			*((u32*)a) = *((u32*)b);
+			*((u32*)b) = tmp;
+			a += 4;
+			b += 4;
+		}
+	}
+#endif
+
+	while (width--) {
+		char tmp = *a;
+		*a++ = *b;
+		*b++ = tmp;
+	}
+}