From 40a6ba5c0a5f544bed9c11dc30b751e05a435b1e Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 26 Oct 2014 23:33:50 -0500 Subject: Split helper functions into their own translation units --- bsearch.c | 2 +- common.h | 99 +++++++----------------------------------------------------- distribute.c | 18 +++++++++++ rotate.c | 19 ++++++++++++ sorters.h | 4 +-- sortnet.c | 38 +++++++++++++++++++++++ swap.c | 27 +++++++++++++++++ 7 files changed, 115 insertions(+), 92 deletions(-) create mode 100644 distribute.c create mode 100644 rotate.c create mode 100644 sortnet.c create mode 100644 swap.c diff --git a/bsearch.c b/bsearch.c index 3c94d45..39e0711 100644 --- a/bsearch.c +++ b/bsearch.c @@ -1,6 +1,6 @@ #include -#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 #include -#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 + +#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 + +#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 - -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 +#include + +#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 +#include + +#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; + } +} -- cgit v1.2.3