]> git.ipfire.org Git - thirdparty/glibc.git/commit
stdlib: The qsort implementation needs to use heapsort in more cases
authorFlorian Weimer <fweimer@redhat.com>
Tue, 21 Nov 2023 15:45:35 +0000 (16:45 +0100)
committerFlorian Weimer <fweimer@redhat.com>
Tue, 21 Nov 2023 15:46:18 +0000 (16:46 +0100)
commit64e4acf24da15c11cb83f933947df3b2e8a700cd
treeb3d8e27747379f2b9e4007740f706a63225387f5
parent55364e1f7dfab372f0710513c4d1c967c4965f71
stdlib: The qsort implementation needs to use heapsort in more cases

The existing logic avoided internal stack overflow.  To avoid
a denial-of-service condition with adversarial input, it is necessary
to fall over to heapsort if tail-recursing deeply, too, which does
not result in a deep stack of pending partitions.

The new test stdlib/tst-qsort5 is based on Douglas McIlroy's paper
on this subject.

Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
stdlib/Makefile
stdlib/qsort.c
stdlib/tst-qsort5.c [new file with mode: 0644]