While glibc provides qsort(), which usually is just a mergesort, until sorting arrays so huge that temporary array used by mergesort would not fit into physical memory (which in our case is never), we are not guaranteed it'll use mergesort. The advantage of mergesort is clear - it's stable. IOW, if we have an array of values parsed from XML, qsort() it and produce some output based on those values, we can then compare the output with some expected output, line by line. But with newer glibc this is all history. After [1], qsort() is no longer mergesort but introsort instead, which is not stable and thus unusable for our test suite. Provide an alternative implementation for qsort() and let it do bubblesort. We don't really have huge arrays to sort and thus O(n^2) time complexity is bearable. 1: https://sourceware.org/git/?p=glibc.git;a=commitdiff;h=03bf8357e8291857a435afcc3048e0b697b6cc04 Signed-off-by: Michal Privoznik <mprivozn@xxxxxxxxxx> --- tests/meson.build | 1 + tests/virqsortmock.c | 58 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 59 insertions(+) create mode 100644 tests/virqsortmock.c diff --git a/tests/meson.build b/tests/meson.build index e1cd57654a..d0167363eb 100644 --- a/tests/meson.build +++ b/tests/meson.build @@ -88,6 +88,7 @@ mock_libs = [ { 'name': 'virpcimock' }, { 'name': 'virportallocatormock' }, { 'name': 'virprocessmock' }, + { 'name': 'virqsortmock' }, { 'name': 'virrandommock' }, ] diff --git a/tests/virqsortmock.c b/tests/virqsortmock.c new file mode 100644 index 0000000000..c16197f908 --- /dev/null +++ b/tests/virqsortmock.c @@ -0,0 +1,58 @@ +/* + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see + * <http://www.gnu.org/licenses/>. + */ + +#include <config.h> + +#include <stdlib.h> + +#define SWAP_WITH_SIZE(a, b, size) \ +do { \ + size_t __size = (size); \ + char *__a = (a); \ + char *__b = (b); \ + do { \ + char __tmp = *__a; \ + *__a++ = *__b; \ + *__b++ = __tmp; \ + } while (--__size > 0); \ +} while (0) + +void qsort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + int xchg = 0; + + if (size < 2) + return; + + do { + size_t i = 0; + char *a = base; + char *b = base; + + xchg = 0; + + for (i = 0; i < nmemb - 1; i++) { + a = b; + b += size; + + if (compar(a, b) > 0) { + SWAP_WITH_SIZE(a, b, size); + xchg = 1; + } + } + } while (xchg); +} -- 2.41.0 _______________________________________________ Devel mailing list -- devel@xxxxxxxxxxxxxxxxx To unsubscribe send an email to devel-leave@xxxxxxxxxxxxxxxxx
