| Message ID | 87leb9bl3k.fsf@oldenburg.str.redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | stdlib: Avoid element self-comparisons in qsort | expand |
On 07/11/23 13:10, Florian Weimer wrote: > This improves compatibility with applications which assume that qsort > does not invoke the comparison function with equal pointer arguments. > > The newly introduced branches should be predictable, as leading to a > call to the comparison function. If the prediction fails, we avoid > calling the function. > > Tested on x86_64-linux-gnu. I don't know if it papers over the LLVM > problem, but the line number in the posted backtrace for the assertion > failure points to the first while statement that the patch changes. > > Thanks, > Florian > LGTM, thanks. Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org> > --- > stdlib/qsort.c | 8 +++++--- > 1 file changed, 5 insertions(+), 3 deletions(-) > > diff --git a/stdlib/qsort.c b/stdlib/qsort.c > index fd32a165e7..ad110e8a89 100644 > --- a/stdlib/qsort.c > +++ b/stdlib/qsort.c > @@ -136,7 +136,7 @@ siftdown (void *base, size_t size, size_t k, size_t n, > if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) > j++; > > - if (cmp (base + (k * size), base + (j * size), arg) >= 0) > + if (j == k || cmp (base + (k * size), base + (j * size), arg) >= 0) > break; > > do_swap (base + (size * j), base + (k * size), size, swap_type); > @@ -332,10 +332,12 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, > that this algorithm runs much faster than others. */ > do > { > - while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) > + while (left_ptr != mid > + && (*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) > left_ptr += size; > > - while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) > + while (right_ptr != mid > + && (*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) > right_ptr -= size; > > if (left_ptr < right_ptr) > > base-commit: 5dd3bda59c2d9da138f0d98808d087cdb95cdc17 >
diff --git a/stdlib/qsort.c b/stdlib/qsort.c index fd32a165e7..ad110e8a89 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -136,7 +136,7 @@ siftdown (void *base, size_t size, size_t k, size_t n, if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) j++; - if (cmp (base + (k * size), base + (j * size), arg) >= 0) + if (j == k || cmp (base + (k * size), base + (j * size), arg) >= 0) break; do_swap (base + (size * j), base + (k * size), size, swap_type); @@ -332,10 +332,12 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, that this algorithm runs much faster than others. */ do { - while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) + while (left_ptr != mid + && (*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) left_ptr += size; - while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) + while (right_ptr != mid + && (*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) right_ptr -= size; if (left_ptr < right_ptr)