From 52bafc94397795e196aa516df044994692f4705f Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Fri, 9 Sep 2016 22:28:22 -0400 Subject: Portable fix for ks_find() fencepost error. Binary search of an array is a notorious example of a simple algorithm which is hard to get exactly right. The variant we're using is nice because it automatically computes the correct insertion point when a key doesn't exist, but runs into one of the portability corner cases of signed integer arithemtic in C. Rather than leave a landmine waiting to explode if somebody builds this code on a platform where (-1 >> 1) != -1, we test for the corner case explictly and accept the miniscule performance hit (which will be lost in other noise anyway). --- ks_index.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'ks_index.c') diff --git a/ks_index.c b/ks_index.c index c093a0a..f506a32 100644 --- a/ks_index.c +++ b/ks_index.c @@ -56,8 +56,8 @@ static int ks_find(const hal_ks_index_t * const ksi, int hi = ksi->used; for (;;) { - int m = (lo + hi) >> 1; - if (m == lo) { + int m = (lo + hi) / 2; + if (hi == 0 || m == lo) { *where = hi; return 0; } -- cgit v1.2.3