summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bsearch.c2
-rw-r--r--common.h99
-rw-r--r--distribute.c18
-rw-r--r--rotate.c19
-rw-r--r--sorters.h4
-rw-r--r--sortnet.c38
-rw-r--r--swap.c27
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;
+ }
+}