1/*
2 * Copyright © 2020 Benjamin Otte
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18#include <locale.h>
19
20#include <gtk/gtk.h>
21
22#include "gtk/timsort/gtktimsortprivate.h"
23
24#if !GLIB_CHECK_VERSION (2, 67, 3)
25# define g_memdup2(mem,size) g_memdup((mem), (size))
26#endif
27
28#define assert_sort_equal(a, b, size, n) \
29 g_assert_cmpmem (a, sizeof (size) * n, b, sizeof (size) * n)
30
31static int
32compare_int (gconstpointer a,
33 gconstpointer b,
34 gpointer unused)
35{
36 int ia = *(const int *) a;
37 int ib = *(const int *) b;
38
39 return ia < ib ? -1 : (ia > ib);
40}
41
42static int
43compare_pointer (gconstpointer a,
44 gconstpointer b,
45 gpointer unused)
46{
47 gpointer pa = *(const gpointer *) a;
48 gpointer pb = *(const gpointer *) b;
49
50 return pa < pb ? -1 : (pa > pb);
51}
52G_GNUC_UNUSED static void
53dump (int *a,
54 gsize n)
55{
56 gsize i;
57
58 for (i = 0; i < n; i++)
59 {
60 if (i)
61 g_print(format: ", ");
62 g_print (format: "%d", a[i]);
63 }
64 g_print (format: "\n");
65}
66
67static void
68run_comparison (gpointer a,
69 gsize n,
70 gsize element_size,
71 GCompareDataFunc compare_func,
72 gpointer data)
73{
74 gint64 start, mid, end;
75 gpointer b;
76
77 g_assert_cmpint (n, <=, G_MAXSIZE / element_size);
78
79 b = g_memdup2 (mem: a, byte_size: element_size * n);
80
81 start = g_get_monotonic_time ();
82 gtk_tim_sort (base: a, size: n, element_size, compare_func, user_data: data);
83 mid = g_get_monotonic_time ();
84 g_qsort_with_data (pbase: b, total_elems: n, size: element_size, compare_func, user_data: data);
85 end = g_get_monotonic_time ();
86
87 g_test_message (format: "%zu items in %uus vs %uus (%u%%)",
88 n,
89 (guint) (mid - start),
90 (guint) (end - mid),
91 (guint) (100 * (mid - start) / MAX (1, end - mid)));
92 assert_sort_equal (a, b, int, n);
93
94 g_free (mem: b);
95}
96
97static void
98test_integers (void)
99{
100 int *a;
101 gsize i, n, run;
102
103 a = g_new (int, 1000);
104
105 for (run = 0; run < 10; run++)
106 {
107 n = g_test_rand_int_range (begin: 0, end: 1000);
108 for (i = 0; i < n; i++)
109 a[i] = g_test_rand_int ();
110
111 run_comparison (a, n, element_size: sizeof (int), compare_func: compare_int, NULL);
112 }
113
114 g_free (mem: a);
115}
116
117static void
118test_integers_runs (void)
119{
120 int *a;
121 gsize i, j, n, run;
122
123 a = g_new (int, 1000);
124
125 for (run = 0; run < 10; run++)
126 {
127 n = g_test_rand_int_range (begin: 0, end: 1000);
128 for (i = 0; i < n; i++)
129 {
130 a[i] = g_test_rand_int ();
131 j = i + g_test_rand_int_range (begin: 0, end: 20);
132 j = MIN (n, j);
133 if (g_test_rand_bit ())
134 {
135 for (i++; i < j; i++)
136 a[i] = a[i - 1] + 1;
137 }
138 else
139 {
140 for (i++; i < j; i++)
141 a[i] = a[i - 1] - 1;
142 }
143 }
144
145 run_comparison (a, n, element_size: sizeof (int), compare_func: compare_int, NULL);
146 }
147
148 g_free (mem: a);
149}
150
151static void
152test_integers_huge (void)
153{
154 int *a;
155 gsize i, n;
156
157 n = g_test_rand_int_range (begin: 2 * 1000 * 1000, end: 5 * 1000 * 1000);
158
159 a = g_new (int, n);
160 for (i = 0; i < n; i++)
161 a[i] = g_test_rand_int ();
162
163 run_comparison (a, n, element_size: sizeof (int), compare_func: compare_int, NULL);
164
165 g_free (mem: a);
166}
167
168static void
169test_pointers (void)
170{
171 gpointer *a;
172 gsize i, n, run;
173
174 a = g_new (gpointer, 1000);
175
176 for (run = 0; run < 10; run++)
177 {
178 n = g_test_rand_int_range (begin: 0, end: 1000);
179 for (i = 0; i < n; i++)
180 a[i] = GINT_TO_POINTER (g_test_rand_int ());
181
182 run_comparison (a, n, element_size: sizeof (gpointer), compare_func: compare_pointer, NULL);
183 }
184
185 g_free (mem: a);
186}
187
188static void
189test_pointers_huge (void)
190{
191 gpointer *a;
192 gsize i, n;
193
194 n = g_test_rand_int_range (begin: 2 * 1000 * 1000, end: 5 * 1000 * 1000);
195
196 a = g_new (gpointer, n);
197 for (i = 0; i < n; i++)
198 a[i] = GINT_TO_POINTER (g_test_rand_int ());
199
200 run_comparison (a, n, element_size: sizeof (gpointer), compare_func: compare_pointer, NULL);
201
202 g_free (mem: a);
203}
204
205static void
206test_steps (void)
207{
208 GtkTimSortRun change;
209 GtkTimSort sort;
210 int *a, *b;
211 gsize i, n;
212
213 n = g_test_rand_int_range (begin: 20 * 1000, end: 50 * 1000);
214
215 a = g_new (int, n);
216 for (i = 0; i < n; i++)
217 a[i] = g_test_rand_int ();
218 b = g_memdup2 (mem: a, byte_size: sizeof (int) * n);
219
220 gtk_tim_sort_init (self: &sort, base: a, size: n, element_size: sizeof (int), compare_func: compare_int, NULL);
221 gtk_tim_sort_set_max_merge_size (self: &sort, max_merge_size: g_test_rand_int_range (begin: 512, end: 2048));
222
223 while (gtk_tim_sort_step (self: &sort, out_change: &change))
224 {
225 if (change.len)
226 {
227 int *a_start = change.base;
228 int *b_start = b + ((int *) change.base - a);
229 g_assert_cmpint (a_start[0], !=, b_start[0]);
230 g_assert_cmpint (a_start[change.len - 1], !=, b_start[change.len - 1]);
231 memcpy (dest: b_start, src: a_start, n: change.len * sizeof (int));
232 }
233
234 assert_sort_equal (a, b, int, n);
235 }
236
237 g_qsort_with_data (pbase: b, total_elems: n, size: sizeof (int), compare_func: compare_int, NULL);
238 assert_sort_equal (a, b, int, n);
239
240 gtk_tim_sort_finish (self: &sort);
241 g_free (mem: b);
242 g_free (mem: a);
243}
244
245int
246main (int argc, char *argv[])
247{
248 (g_test_init) (argc: &argc, argv: &argv, NULL);
249 setlocale (LC_ALL, locale: "C");
250
251 g_test_add_func (testpath: "/timsort/integers", test_func: test_integers);
252 g_test_add_func (testpath: "/timsort/integers/runs", test_func: test_integers_runs);
253 g_test_add_func (testpath: "/timsort/integers/huge", test_func: test_integers_huge);
254 g_test_add_func (testpath: "/timsort/pointers", test_func: test_pointers);
255 g_test_add_func (testpath: "/timsort/pointers/huge", test_func: test_pointers_huge);
256 g_test_add_func (testpath: "/timsort/steps", test_func: test_steps);
257
258 return g_test_run ();
259}
260

source code of gtk/testsuite/gtk/timsort.c