[2020-02] Start a dedicated thread for MERP crash reporting (#21126)
[mono-project.git] / mono / unit-tests / test-sgen-qsort.c
blob0633c6e14d391fc286541a7691d4e5eada11f307
1 /*
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.
7 */
9 #include "config.h"
11 #define HAVE_SGEN_GC
13 #include <mono/sgen/sgen-gc.h>
14 #include <mono/sgen/sgen-qsort.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <time.h>
19 #include <assert.h>
21 static int
22 compare_ints (const void *pa, const void *pb)
24 int a = *(const int*)pa;
25 int b = *(const int*)pb;
26 if (a < b)
27 return -1;
28 if (a == b)
29 return 0;
30 return 1;
33 typedef struct {
34 int key;
35 int val;
36 } teststruct_t;
38 static int
39 compare_teststructs (const void *pa, const void *pb)
41 int a = ((const teststruct_t*)pa)->key;
42 int b = ((const teststruct_t*)pb)->key;
43 if (a < b)
44 return -1;
45 if (a == b)
46 return 0;
47 return 1;
50 static int
51 compare_teststructs2 (const void *pa, const void *pb)
53 int a = (*((const teststruct_t**)pa))->key;
54 int b = (*((const teststruct_t**)pb))->key;
55 if (a < b)
56 return -1;
57 if (a == b)
58 return 0;
59 return 1;
62 DEF_QSORT_INLINE(test_struct, teststruct_t*, compare_teststructs)
64 static void
65 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
67 size_t len = nel * width;
68 void *b1 = malloc (len);
69 void *b2 = malloc (len);
71 memcpy (b1, base, len);
72 memcpy (b2, base, len);
74 mono_qsort (b1, nel, width, compar);
75 sgen_qsort (b2, nel, width, compar);
77 /* We can't assert that qsort and sgen_qsort produce the same results
78 * because qsort is not guaranteed to be stable, so they will tend to differ
79 * in adjacent equal elements. Instead, we assert that the array is sorted
80 * according to the comparator.
82 for (size_t i = 0; i < nel - 1; ++i)
83 assert (compar ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
85 free (b1);
86 free (b2);
89 static void
90 compare_sorts2 (void *base, size_t nel)
92 size_t width = sizeof (teststruct_t*);
93 size_t len = nel * width;
94 void *b1 = malloc (len);
95 void *b2 = malloc (len);
97 memcpy (b1, base, len);
98 memcpy (b2, base, len);
100 qsort (b1, nel, sizeof (teststruct_t*), compare_teststructs2);
101 qsort_test_struct ((teststruct_t **)b2, nel);
103 for (size_t i = 0; i < nel - 1; ++i)
104 assert (compare_teststructs2 ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
106 free (b1);
107 free (b2);
110 #ifdef __cplusplus
111 extern "C"
112 #endif
114 test_sgen_qsort_main (void);
117 test_sgen_qsort_main (void)
119 int i;
120 for (i = 1; i < 4000; ++i) {
121 int a [i];
122 int j;
124 for (j = 0; j < i; ++j)
125 a [j] = i - j - 1;
126 compare_sorts (a, i, sizeof (int), compare_ints);
129 srandom (time (NULL));
130 for (i = 0; i < 2000; ++i) {
131 teststruct_t a [200];
132 int j;
133 for (j = 0; j < 200; ++j) {
134 a [j].key = random ();
135 a [j].val = random ();
138 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
141 srandom (time (NULL));
142 for (i = 0; i < 2000; ++i) {
143 teststruct_t a [200];
144 teststruct_t *b [200];
145 int j;
146 for (j = 0; j < 200; ++j) {
147 a [j].key = random ();
148 a [j].val = random ();
149 b [j] = &a[j];
152 compare_sorts2 (b, 200);
154 return 0;