stdlib: Avoid another self-comparison in qsort
Checks
Context |
Check |
Description |
redhat-pt-bot/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
redhat-pt-bot/TryBot-32bit |
success
|
Build for i686
|
linaro-tcwg-bot/tcwg_glibc_build--master-arm |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_check--master-arm |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 |
success
|
Testing passed
|
Commit Message
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(-)
base-commit: 323f367cc46b80224d39b082adf7be74b49ed843
Comments
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
>
* 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
@@ -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;