about summary refs log tree commit diff
diff options
context:
space:
mode:
authorFangrui Song <i@maskray.me>2018-07-21 17:34:00 -0700
committerRich Felker <dalias@aerifal.cx>2018-07-23 15:14:29 -0400
commit3d8322c7ad659210a4c8770ef455ca729ce7f395 (patch)
tree25de8d1283cf1945c34aa5ccf444c46846a846da
parentf2c6dbe2442027ed8fe0fa869918e41f495534d8 (diff)
downloadmusl-3d8322c7ad659210a4c8770ef455ca729ce7f395.tar.gz
musl-3d8322c7ad659210a4c8770ef455ca729ce7f395.tar.xz
musl-3d8322c7ad659210a4c8770ef455ca729ce7f395.zip
bsearch: simplify and optimize
maintainer's note: the key observation here is that the compared
element is the first slot of the second ceil(half) of the array, and
thus can be removed for further comparison when it does not match, so
that we descend into the second ceil(half)-1 rather than ceil(half)
elements. this change ensures that nel strictly decreases with each
iteration, so that the case of != but nel==1 does not need to be
special-cased anymore.
-rw-r--r--src/stdlib/bsearch.c12
1 files changed, 6 insertions, 6 deletions
diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c
index 61d89367..fe050ea3 100644
--- a/src/stdlib/bsearch.c
+++ b/src/stdlib/bsearch.c
@@ -7,13 +7,13 @@ void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (
 	while (nel > 0) {
 		try = (char *)base + width*(nel/2);
 		sign = cmp(key, try);
-		if (!sign) return try;
-		else if (nel == 1) break;
-		else if (sign < 0)
+		if (sign < 0) {
 			nel /= 2;
-		else {
-			base = try;
-			nel -= nel/2;
+		} else if (sign > 0) {
+			base = (char *)try + width;
+			nel -= nel/2+1;
+		} else {
+			return try;
 		}
 	}
 	return NULL;