From 52bafc94397795e196aa516df044994692f4705f Mon Sep 17 00:00:00 2001
From: Rob Austein <sra@hactrn.net>
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(-)
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