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 | |
31 | static int |
32 | compare_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 | |
42 | static int |
43 | compare_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 | } |
52 | G_GNUC_UNUSED static void |
53 | dump (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 | |
67 | static void |
68 | run_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 | |
97 | static void |
98 | test_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 | |
117 | static void |
118 | test_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 | |
151 | static void |
152 | test_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 | |
168 | static void |
169 | test_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 | |
188 | static void |
189 | test_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 | |
205 | static void |
206 | test_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 | |
245 | int |
246 | main (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 | |