aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRob Austein <sra@hactrn.net>2016-09-09 22:28:22 -0400
committerRob Austein <sra@hactrn.net>2016-09-09 22:28:22 -0400
commit52bafc94397795e196aa516df044994692f4705f (patch)
treecf2902e30be32df79be41edd470f4c11fe17ef97
parentd56ce9ab6cfd874b0bbcba204b33af4e7e762517 (diff)
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).
-rw-r--r--ks_index.c4
1 files 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;
}