* [PATCH] stdlib: Avoid another self-comparison in qsort
@ 2023-11-15 6:28 Florian Weimer
2023-11-16 13:45 ` Adhemerval Zanella Netto
0 siblings, 1 reply; 3+ messages in thread
From: Florian Weimer @ 2023-11-15 6:28 UTC (permalink / raw)
To: libc-alpha; +Cc: Adhemerval Zanella
In the insertion phase, we could run off the start of the array if the
comparison function never runs zero. In that case, it never finds the
initial element that terminates the iteration.
Tested on i686-linux-gnu and x86_64-linux-gnu.
---
stdlib/qsort.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index ad110e8a89..1ea31ff424 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -217,7 +217,7 @@ insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
while ((run_ptr += size) <= end_ptr)
{
tmp_ptr = run_ptr - size;
- while (cmp (run_ptr, tmp_ptr, arg) < 0)
+ while (tmp_ptr != base_ptr && cmp (run_ptr, tmp_ptr, arg) < 0)
tmp_ptr -= size;
tmp_ptr += size;
base-commit: 323f367cc46b80224d39b082adf7be74b49ed843
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] stdlib: Avoid another self-comparison in qsort
2023-11-15 6:28 [PATCH] stdlib: Avoid another self-comparison in qsort Florian Weimer
@ 2023-11-16 13:45 ` Adhemerval Zanella Netto
2023-11-16 19:18 ` Florian Weimer
0 siblings, 1 reply; 3+ messages in thread
From: Adhemerval Zanella Netto @ 2023-11-16 13:45 UTC (permalink / raw)
To: Florian Weimer, libc-alpha
On 15/11/23 03:28, Florian Weimer wrote:
> In the insertion phase, we could run off the start of the array if the
> comparison function never runs zero. In that case, it never finds the
> initial element that terminates the iteration.
>
> Tested on i686-linux-gnu and x86_64-linux-gnu.
LGTM, thanks.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
>
> ---
> stdlib/qsort.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index ad110e8a89..1ea31ff424 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -217,7 +217,7 @@ insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
> while ((run_ptr += size) <= end_ptr)
> {
> tmp_ptr = run_ptr - size;
> - while (cmp (run_ptr, tmp_ptr, arg) < 0)
> + while (tmp_ptr != base_ptr && cmp (run_ptr, tmp_ptr, arg) < 0)
> tmp_ptr -= size;
>
> tmp_ptr += size;
>
> base-commit: 323f367cc46b80224d39b082adf7be74b49ed843
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] stdlib: Avoid another self-comparison in qsort
2023-11-16 13:45 ` Adhemerval Zanella Netto
@ 2023-11-16 19:18 ` Florian Weimer
0 siblings, 0 replies; 3+ messages in thread
From: Florian Weimer @ 2023-11-16 19:18 UTC (permalink / raw)
To: Adhemerval Zanella Netto; +Cc: libc-alpha
* Adhemerval Zanella Netto:
>> ---
>> stdlib/qsort.c | 2 +-
>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
>> index ad110e8a89..1ea31ff424 100644
>> --- a/stdlib/qsort.c
>> +++ b/stdlib/qsort.c
>> @@ -217,7 +217,7 @@ insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
>> while ((run_ptr += size) <= end_ptr)
>> {
>> tmp_ptr = run_ptr - size;
>> - while (cmp (run_ptr, tmp_ptr, arg) < 0)
>> + while (tmp_ptr != base_ptr && cmp (run_ptr, tmp_ptr, arg) < 0)
>> tmp_ptr -= size;
>>
>> tmp_ptr += size;
Hmm, shouldn't the new condition be run_ptr != tmp_ptr, so that we avoid
a pointless cmp call in more cases?
Thanks,
Florian
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-11-16 19:18 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-11-15 6:28 [PATCH] stdlib: Avoid another self-comparison in qsort Florian Weimer
2023-11-16 13:45 ` Adhemerval Zanella Netto
2023-11-16 19:18 ` Florian Weimer
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).