From 54d463c220a76592165dcedc4639bf6f35b7d01c Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Thu, 17 Jul 2014 21:21:20 -0500 Subject: Factor out binary_search --- bsearch.c | 24 ++++++++++++++++++++++++ common.h | 23 ++--------------------- 2 files changed, 26 insertions(+), 21 deletions(-) create mode 100644 bsearch.c 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 + +#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; +} diff --git a/common.h b/common.h index 5580dbe..8969f1d 100644 --- a/common.h +++ b/common.h @@ -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) { -- cgit v1.2.3