diff mbox series

stdlib: Avoid another self-comparison in qsort

Message ID 87o7fvttrs.fsf@oldenburg.str.redhat.com
State Superseded
Headers
Series 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

Florian Weimer Nov. 15, 2023, 6:28 a.m. UTC 
  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

Adhemerval Zanella Netto Nov. 16, 2023, 1:45 p.m. UTC | #1 
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
>
Florian Weimer Nov. 16, 2023, 7:18 p.m. UTC | #2 
* 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
diff mbox series

Patch

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;