From c43cb38612192fa45bf7ed981a98bc4ddb86ce75 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Fri, 26 Oct 2012 22:53:50 +0700 Subject: Move estimate_bisect_steps to libgit.a MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This function is used by bisect.c, part of libgit.a while estimate_bisect_steps stays in builtin/rev-list.c. Move it to bisect.a so we won't have undefine reference if a standalone program that uses libgit.a happens to pull it in. Signed-off-by: Nguyễn Thái Ngọc Duy Signed-off-by: Jeff King --- bisect.c | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) (limited to 'bisect.c') diff --git a/bisect.c b/bisect.c index 1aad49b1a6..bd1b7b5dac 100644 --- a/bisect.c +++ b/bisect.c @@ -956,3 +956,41 @@ int bisect_next_all(const char *prefix, int no_checkout) return bisect_checkout(bisect_rev_hex, no_checkout); } +static inline int log2i(int n) +{ + int log2 = 0; + + for (; n > 1; n >>= 1) + log2++; + + return log2; +} + +static inline int exp2i(int n) +{ + return 1 << n; +} + +/* + * Estimate the number of bisect steps left (after the current step) + * + * For any x between 0 included and 2^n excluded, the probability for + * n - 1 steps left looks like: + * + * P(2^n + x) == (2^n - x) / (2^n + x) + * + * and P(2^n + x) < 0.5 means 2^n < 3x + */ +int estimate_bisect_steps(int all) +{ + int n, x, e; + + if (all < 3) + return 0; + + n = log2i(all); + e = exp2i(n); + x = all - e; + + return (e < 3 * x) ? n : n - 1; +} -- cgit v1.2.3