diff options
author | Rob Austein <sra@hactrn.net> | 2016-09-09 22:28:22 -0400 |
---|---|---|
committer | Rob Austein <sra@hactrn.net> | 2016-09-09 22:28:22 -0400 |
commit | 52bafc94397795e196aa516df044994692f4705f (patch) | |
tree | cf2902e30be32df79be41edd470f4c11fe17ef97 | |
parent | d56ce9ab6cfd874b0bbcba204b33af4e7e762517 (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.c | 4 |
1 files changed, 2 insertions, 2 deletions
@@ -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; } |