diff options
| -rw-r--r-- | common.h | 107 | ||||
| -rw-r--r-- | grailsort.c | 117 | ||||
| -rw-r--r-- | sorters.h | 5 | ||||
| -rw-r--r-- | wikisort.c | 104 |
4 files changed, 123 insertions, 210 deletions
diff --git a/common.h b/common.h new file mode 100644 index 0000000..984d890 --- /dev/null +++ b/common.h @@ -0,0 +1,107 @@ +#include <stddef.h> +#include <stdint.h> + +#include "sorters.h" + +static void swap(char *a, char *b, size_t width) +{ + while (width--) { + char tmp = *a; + *a++ = *b; + *b++ = tmp; + } +} + +static void reverse(char *base, size_t nmel, size_t width) +{ + char *last = base + (nmel - 1) * width; + while (last > base) { + swap(base, last, width); + base += width; + last -= width; + } +} + +/* rotates left */ +static void rotate(char *base, size_t nmel, size_t width, size_t shift) +{ + reverse(base, shift, width); + reverse(base + shift * width, nmel - shift, width); + reverse(base, nmel, width); +} + +/* If a matching element exists, returns index of one of them. + If none exists, returns index where such an element should be inserted. */ +static size_t binary_search(const char *needle, char *haystack, size_t nmel, size_t width, cmpfun cmp) +{ + size_t baseidx = 0; + while (nmel) { + size_t tryidx = baseidx + nmel / 2; + char *try = haystack + tryidx * width; + int sign = cmp(try, needle); + if (!sign) return tryidx; + else if (sign < 0) { + baseidx = tryidx + 1; + nmel -= nmel / 2 + 1; + } + else { + nmel /= 2; + } + } + return baseidx; +} + +static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp) +{ + char *sorted = base + bufnmel * width; + while (bufnmel) { + char *last = sorted - width; + size_t equals; + for (equals = 1; equals < bufnmel; equals++) { + if (cmp(last, last - equals * width)) break; + } + + size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp); + rotate(sorted - equals * width, insertpos + equals, width, equals); + + bufnmel -= equals; + sortnmel += equals; + sorted -= equals * width; + } +} + +#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 */ +}; + +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); + } +} diff --git a/grailsort.c b/grailsort.c index c7a4074..5edf40b 100644 --- a/grailsort.c +++ b/grailsort.c @@ -3,59 +3,19 @@ #include <stdint.h> #include "sorters.h" +#include "common.h" #define TAIL(base,nmel,width) ((base) + ((nmel) - 1) * (width)) -static void swap(char *a, char *b, size_t width) -{ - while (width--) { - char tmp = *a; - *a++ = *b; - *b++ = tmp; - } -} - -static void reverse(char *base, size_t nmel, size_t width) -{ - char *last = base + (nmel - 1) * width; - while (last > base) { - swap(base, last, width); - base += width; - last -= width; - } -} - -/* rotates left */ -static void rotate(char *base, size_t nmel, size_t width, size_t shift) -{ - reverse(base, shift, width); - reverse(base + shift * width, nmel - shift, width); - reverse(base, nmel, width); -} - -/* If a matching element exists, returns index of one of them. - If none exists, returns index where such an element should be inserted. */ -static size_t binary_search(const char *needle, char *haystack, - size_t nmel, size_t width, cmpfun cmp) +/* get index of last block whose head is less than the previous block's tail */ +static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp) { - size_t baseidx = 0; - while (nmel) { - size_t tryidx = baseidx + nmel / 2; - char *try = haystack + tryidx * width; - int sign = cmp(try, needle); - if (!sign) return tryidx; - else if (sign < 0) { - baseidx = tryidx + 1; - nmel -= nmel / 2 + 1; - } - else { - nmel /= 2; - } - } - return baseidx; + for (char *cur = TAIL(base, bcount, bwidth); --bcount; cur -= bwidth) + if (cmp(cur - width, cur) > 0) break; + return bcount; } -static size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) +size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) { char *a = buf; char *b = base + anmel * width; @@ -82,72 +42,11 @@ static size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t wi return sorted; } -/* get index of last block whose head is less than the previous block's tail */ -static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp) -{ - for (char *cur = TAIL(base, bcount, bwidth); --bcount; cur -= bwidth) - if (cmp(cur - width, cur) > 0) break; - return bcount; -} - -static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp) -{ - char *sorted = base + bufnmel * width; - while (bufnmel) { - char *last = sorted - width; - size_t equals; - for (equals = 1; equals < bufnmel; equals++) { - if (cmp(last, last - equals * width)) break; - } - - size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp); - rotate(sorted - equals * width, insertpos + equals, width, equals); - - bufnmel -= equals; - sortnmel += equals; - sorted -= equals * width; - } -} - -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 }; - -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); - } -} - void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) { char *base = unsorted; - if (nmel <= 8) { + if (nmel <= MAX_SORTNET) { sorting_network(base, nmel, width, cmp); return; } @@ -1,3 +1,6 @@ +#ifndef SORTERS_H +#define SORTERS_H + #include <stddef.h> void assert_sorted(int *buffer, size_t size); @@ -17,3 +20,5 @@ extern const struct sorter { const char *name; sorterfn func; } sorters[]; + +#endif @@ -1,42 +1,14 @@ #include <math.h> #include <stddef.h> -#include <stdint.h> -#include <string.h> #include "sorters.h" +#include "common.h" struct array { char *base; size_t nmel; }; -static void swap(char *a, char *b, size_t width) -{ - while (width--) { - char tmp = *a; - *a++ = *b; - *b++ = tmp; - } -} - -static void reverse(char *base, size_t nmel, size_t width) -{ - char *last = base + (nmel - 1) * width; - while (last > base) { - swap(base, last, width); - base += width; - last -= width; - } -} - -/* rotates left */ -static void rotate(char *base, size_t nmel, size_t width, size_t shift) -{ - reverse(base, shift, width); - reverse(base + shift * width, nmel - shift, width); - reverse(base, nmel, width); -} - /* buf must be large enough to hold as->nmel elements */ static void merge_blocks(char *buf, struct array *as, size_t bs_nmel, size_t width, cmpfun cmp) { @@ -69,28 +41,6 @@ static char *find_min_block(char *base, size_t count, size_t bwidth, size_t widt return min; } -/* If a matching element exists, returns index of one of them. - If none exists, returns index where such an element should be inserted. */ -static size_t binary_search(const char *needle, char *haystack, - size_t nmel, size_t width, cmpfun cmp) -{ - size_t baseidx = 0; - while (nmel) { - size_t tryidx = baseidx + nmel / 2; - char *try = haystack + tryidx * width; - int sign = cmp(try, needle); - if (!sign) return tryidx; - else if (sign < 0) { - baseidx = tryidx + 1; - nmel -= nmel / 2 + 1; - } - else { - nmel /= 2; - } - } - return baseidx; -} - static size_t roll(struct array *a, struct array *b, size_t bwidth, size_t width, char **mina, cmpfun cmp) { @@ -106,60 +56,12 @@ static size_t roll(struct array *a, struct array *b, return iters; } -static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp) -{ - char *sorted = base + bufnmel * width; - while (bufnmel) { - char *last = sorted - width; - size_t equals; - for (equals = 1; equals < bufnmel; equals++) { - if (cmp(last, last - equals * width)) break; - } - - size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp); - rotate(sorted - equals * width, insertpos + equals, width, equals); - - bufnmel -= equals; - sortnmel += equals; - sorted -= equals * width; - } -} - -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 wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) { char *base = unsorted; - /* use a sorting network for small inputs */ - if (nmel <= 8) { - 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); - } + if (nmel <= MAX_SORTNET) { + sorting_network(base, nmel, width, cmp); return; } |