diff options
| -rw-r--r-- | bsearch.c | 24 | ||||
| -rw-r--r-- | common.h | 23 |
2 files changed, 26 insertions, 21 deletions
diff --git a/bsearch.c b/bsearch.c new file mode 100644 index 0000000..3c94d45 --- /dev/null +++ b/bsearch.c @@ -0,0 +1,24 @@ +#include <stddef.h> + +#include "sorters.h" + +/* If a matching element exists, returns index of one of them. + If none exists, returns index where such an element should be inserted. */ +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; +} @@ -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) { |