[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 22 Jul 2018 14:51:31 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: [PATCH] bsearch: simplify and optimize
On Sat, Jul 21, 2018 at 05:47:32PM -0700, Fāng-ruì Sòng wrote:
> >From 64d86f96fa404dbaa40de8a1979ecadca6add4ca Mon Sep 17 00:00:00 2001
> From: Fangrui Song <i@...kray.me>
> Date: Sat, 21 Jul 2018 17:34:00 -0700
> Subject: [PATCH] bsearch: simplify and optimize
>
> ---
> src/stdlib/bsearch.c | 13 ++++++-------
> 1 file changed, 6 insertions(+), 7 deletions(-)
>
> diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c
> index 61d89367..2a998cc6 100644
> --- a/src/stdlib/bsearch.c
> +++ b/src/stdlib/bsearch.c
> @@ -7,14 +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;
> }
The change here looks correct -- what it's doing is observing that the
compared element is the first slot of the second ceil(half) of the
array, and thus can be removed for further comparison, 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.
Only change I would make is minor style: generally when if/else
construct uses braces for one case, we use them for all. If there are
no other objections I can apply this change when merging.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
