diff options
Diffstat (limited to 'common.h')
-rw-r--r-- | common.h | 23 |
1 files changed, 2 insertions, 21 deletions
@@ -3,6 +3,8 @@ #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) { while (width--) { @@ -30,27 +32,6 @@ static void rotate(char *base, size_t nmel, size_t width, size_t shift) 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) { |