#include #include #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) { while (bufnmel) { char *sorted = base + bufnmel * width; size_t insertpos = binary_search(base, sorted, sortnmel, width, cmp); while (insertpos < sortnmel && !cmp(base, sorted + insertpos * width)) { insertpos++; } if (insertpos > 0) { rotate(base, bufnmel + insertpos, width, bufnmel); } base += (insertpos + 1) * width; bufnmel -= 1; sortnmel -= insertpos; } } #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); } }