diff options
| -rw-r--r-- | bsearch.c | 2 | ||||
| -rw-r--r-- | common.h | 99 | ||||
| -rw-r--r-- | distribute.c | 18 | ||||
| -rw-r--r-- | rotate.c | 19 | ||||
| -rw-r--r-- | sorters.h | 4 | ||||
| -rw-r--r-- | sortnet.c | 38 | ||||
| -rw-r--r-- | swap.c | 27 |
7 files changed, 115 insertions, 92 deletions
@@ -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. */ @@ -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; + } +} @@ -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); + } +} @@ -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; + } +} |