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=03bf8357e8291857a4... Signed-off-by: Michal Privoznik <mprivozn(a)redhat.com&gt; --- 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

On Wed, Nov 22, 2023 at 11:49:55AM +0100, Michal Privoznik wrote: Aside from the test suite, I'm not too happy with the idea that our ordering of applying rules is non-deterministic :-( There is a well defined ordering for rules - the order in which the user/app listed them in the virNWFilterDef XML document. We have to override this for sorting by priority, but when priority matches, IMHO we should honour the XML rules ordering. I have no idea how hard that is to achieve though, as the place where we do the qsort() seems quite remote from the place where we know the XML doc ordering. With regards, Daniel -- |: https://berrange.com -o- https://www.flickr.com/photos/dberrange :| |: https://libvirt.org -o- https://fstop138.berrange.com :| |: https://entangle-photo.org -o- https://www.instagram.com/dberrange :|