2 * test-sgen-qsort.c: Unit test for quicksort.
4 * Copyright (C) 2013 Xamarin Inc
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License 2.0 as published by the Free Software Foundation;
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
15 * You should have received a copy of the GNU Library General Public
16 * License 2.0 along with this library; if not, write to the Free
17 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 #include <sgen/sgen-gc.h>
23 #include <sgen/sgen-qsort.h>
31 compare_ints (const void *pa, const void *pb)
33 int a = *(const int*)pa;
34 int b = *(const int*)pb;
48 compare_teststructs (const void *pa, const void *pb)
50 int a = ((const teststruct_t*)pa)->key;
51 int b = ((const teststruct_t*)pb)->key;
60 compare_teststructs2 (const void *pa, const void *pb)
62 int a = (*((const teststruct_t**)pa))->key;
63 int b = (*((const teststruct_t**)pb))->key;
71 DEF_QSORT_INLINE(test_struct, teststruct_t*, compare_teststructs)
74 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
76 size_t len = nel * width;
77 void *b1 = malloc (len);
78 void *b2 = malloc (len);
80 memcpy (b1, base, len);
81 memcpy (b2, base, len);
83 qsort (b1, nel, width, compar);
84 sgen_qsort (b2, nel, width, compar);
86 assert (!memcmp (b1, b2, len));
93 compare_sorts2 (void *base, size_t nel)
95 size_t len = nel * sizeof (teststruct_t*);
96 void *b1 = malloc (len);
97 void *b2 = malloc (len);
99 memcpy (b1, base, len);
100 memcpy (b2, base, len);
102 qsort (b1, nel, sizeof (teststruct_t*), compare_teststructs2);
103 qsort_test_struct ((teststruct_t **)b2, nel);
105 assert (!memcmp (b1, b2, len));
114 for (i = 1; i < 4000; ++i) {
118 for (j = 0; j < i; ++j)
120 compare_sorts (a, i, sizeof (int), compare_ints);
123 srandom (time (NULL));
124 for (i = 0; i < 2000; ++i) {
125 teststruct_t a [200];
127 for (j = 0; j < 200; ++j) {
128 a [j].key = random ();
129 a [j].val = random ();
132 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
135 srandom (time (NULL));
136 for (i = 0; i < 2000; ++i) {
137 teststruct_t a [200];
138 teststruct_t *b [200];
140 for (j = 0; j < 200; ++j) {
141 a [j].key = random ();
142 a [j].val = random ();
146 compare_sorts2 (b, 200);