2 * test-sgen-qsort.c: Unit test for quicksort.
4 * Copyright (C) 2013 Xamarin Inc
6 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
11 #include <sgen/sgen-gc.h>
12 #include <sgen/sgen-qsort.h>
20 compare_ints (const void *pa, const void *pb)
22 int a = *(const int*)pa;
23 int b = *(const int*)pb;
37 compare_teststructs (const void *pa, const void *pb)
39 int a = ((const teststruct_t*)pa)->key;
40 int b = ((const teststruct_t*)pb)->key;
49 compare_teststructs2 (const void *pa, const void *pb)
51 int a = (*((const teststruct_t**)pa))->key;
52 int b = (*((const teststruct_t**)pb))->key;
60 DEF_QSORT_INLINE(test_struct, teststruct_t*, compare_teststructs)
63 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
65 size_t len = nel * width;
66 void *b1 = malloc (len);
67 void *b2 = malloc (len);
69 memcpy (b1, base, len);
70 memcpy (b2, base, len);
72 qsort (b1, nel, width, compar);
73 sgen_qsort (b2, nel, width, compar);
75 /* We can't assert that qsort and sgen_qsort produce the same results
76 * because qsort is not guaranteed to be stable, so they will tend to differ
77 * in adjacent equal elements. Instead, we assert that the array is sorted
78 * according to the comparator.
80 for (size_t i = 0; i < nel - 1; ++i)
81 assert (compar ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
88 compare_sorts2 (void *base, size_t nel)
90 size_t width = sizeof (teststruct_t*);
91 size_t len = nel * width;
92 void *b1 = malloc (len);
93 void *b2 = malloc (len);
95 memcpy (b1, base, len);
96 memcpy (b2, base, len);
98 qsort (b1, nel, sizeof (teststruct_t*), compare_teststructs2);
99 qsort_test_struct ((teststruct_t **)b2, nel);
101 for (size_t i = 0; i < nel - 1; ++i)
102 assert (compare_teststructs2 ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
111 for (i = 1; i < 4000; ++i) {
115 for (j = 0; j < i; ++j)
117 compare_sorts (a, i, sizeof (int), compare_ints);
120 srandom (time (NULL));
121 for (i = 0; i < 2000; ++i) {
122 teststruct_t a [200];
124 for (j = 0; j < 200; ++j) {
125 a [j].key = random ();
126 a [j].val = random ();
129 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
132 srandom (time (NULL));
133 for (i = 0; i < 2000; ++i) {
134 teststruct_t a [200];
135 teststruct_t *b [200];
137 for (j = 0; j < 200; ++j) {
138 a [j].key = random ();
139 a [j].val = random ();
143 compare_sorts2 (b, 200);