[PATCH 1/2] tests: Introduce virqsortmock
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>
---
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