diff options
Diffstat (limited to 'common.h')
| -rw-r--r-- | common.h | 99 |
1 files changed, 11 insertions, 88 deletions
@@ -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 |