summaryrefslogtreecommitdiff
path: root/string-list.c
diff options
context:
space:
mode:
authorDerrick Stolee <dstolee@microsoft.com>2017-10-08 18:29:37 (GMT)
committerJunio C Hamano <gitster@pobox.com>2017-10-09 23:57:24 (GMT)
commit19716b21a4255ecc7148b54ab2c78039c59f25bf (patch)
tree5f1cecbffc543c64e7c4c4f371d204424e1ce1bb /string-list.c
parent217f2767cbcb562872437eed4dec62e00846d90c (diff)
downloadgit-19716b21a4255ecc7148b54ab2c78039c59f25bf.zip
git-19716b21a4255ecc7148b54ab2c78039c59f25bf.tar.gz
git-19716b21a4255ecc7148b54ab2c78039c59f25bf.tar.bz2
cleanup: fix possible overflow errors in binary search
A common mistake when writing binary search is to allow possible integer overflow by using the simple average: mid = (min + max) / 2; Instead, use the overflow-safe version: mid = min + (max - min) / 2; This translation is safe since the operation occurs inside a loop conditioned on "min < max". The included changes were found using the following git grep: git grep '/ *2;' '*.c' Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Reviewed-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'string-list.c')
-rw-r--r--string-list.c2
1 files changed, 1 insertions, 1 deletions
diff --git a/string-list.c b/string-list.c
index 806b4c8..a0cf0cf 100644
--- a/string-list.c
+++ b/string-list.c
@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,
compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
while (left + 1 < right) {
- int middle = (left + right) / 2;
+ int middle = left + (right - left) / 2;
int compare = cmp(string, list->items[middle].string);
if (compare < 0)
right = middle;