1 /* GtkRBTree tests.
2 *
3 * Copyright (C) 2011, Red Hat, Inc.
4 * Authors: Benjamin Otte <otte@gnome.org>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <locale.h>
21
22 #include <gtk/gtk.h>
23
24 static GQuark number_quark;
25 static GQuark changes_quark;
26
27 static guint
get(GListModel * model,guint position)28 get (GListModel *model,
29 guint position)
30 {
31 GObject *object = g_list_model_get_item (model, position);
32 guint number;
33 g_assert_nonnull (object);
34 number = GPOINTER_TO_UINT (g_object_get_qdata (object, number_quark));
35 g_object_unref (object);
36 return number;
37 }
38
39 static char *
model_to_string(GListModel * model)40 model_to_string (GListModel *model)
41 {
42 GString *string = g_string_new (NULL);
43 guint i;
44
45 for (i = 0; i < g_list_model_get_n_items (model); i++)
46 {
47 if (i > 0)
48 g_string_append (string, " ");
49 g_string_append_printf (string, "%u", get (model, i));
50 }
51
52 return g_string_free (string, FALSE);
53 }
54
55 static void
splice(GListStore * store,guint pos,guint removed,guint * numbers,guint added)56 splice (GListStore *store,
57 guint pos,
58 guint removed,
59 guint *numbers,
60 guint added)
61 {
62 GObject **objects = g_newa (GObject *, added);
63 guint i;
64
65 for (i = 0; i < added; i++)
66 {
67 /* 0 cannot be differentiated from NULL, so don't use it */
68 g_assert_cmpint (numbers[i], !=, 0);
69 objects[i] = g_object_new (G_TYPE_OBJECT, NULL);
70 g_object_set_qdata (objects[i], number_quark, GUINT_TO_POINTER (numbers[i]));
71 }
72
73 g_list_store_splice (store, pos, removed, (gpointer *) objects, added);
74
75 for (i = 0; i < added; i++)
76 g_object_unref (objects[i]);
77 }
78
79 static void
add(GListStore * store,guint number)80 add (GListStore *store,
81 guint number)
82 {
83 GObject *object;
84
85 /* 0 cannot be differentiated from NULL, so don't use it */
86 g_assert_cmpint (number, !=, 0);
87
88 object = g_object_new (G_TYPE_OBJECT, NULL);
89 g_object_set_qdata (object, number_quark, GUINT_TO_POINTER (number));
90 g_list_store_append (store, object);
91 g_object_unref (object);
92 }
93
94 static void
insert(GListStore * store,guint position,guint number)95 insert (GListStore *store,
96 guint position,
97 guint number)
98 {
99 GObject *object;
100
101 /* 0 cannot be differentiated from NULL, so don't use it */
102 g_assert_cmpint (number, !=, 0);
103
104 object = g_object_new (G_TYPE_OBJECT, NULL);
105 g_object_set_qdata (object, number_quark, GUINT_TO_POINTER (number));
106 g_list_store_insert (store, position, object);
107 g_object_unref (object);
108 }
109
110 #define assert_model(model, expected) G_STMT_START{ \
111 char *s = model_to_string (G_LIST_MODEL (model)); \
112 if (!g_str_equal (s, expected)) \
113 g_assertion_message_cmpstr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, \
114 #model " == " #expected, s, "==", expected); \
115 g_free (s); \
116 }G_STMT_END
117
118 #define assert_changes(model, expected) G_STMT_START{ \
119 GString *changes = g_object_get_qdata (G_OBJECT (model), changes_quark); \
120 if (!g_str_equal (changes->str, expected)) \
121 g_assertion_message_cmpstr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, \
122 #model " == " #expected, changes->str, "==", expected); \
123 g_string_set_size (changes, 0); \
124 }G_STMT_END
125
126 #define ignore_changes(model) G_STMT_START{ \
127 GString *changes = g_object_get_qdata (G_OBJECT (model), changes_quark); \
128 g_string_set_size (changes, 0); \
129 }G_STMT_END
130
131 static GListStore *
new_empty_store(void)132 new_empty_store (void)
133 {
134 return g_list_store_new (G_TYPE_OBJECT);
135 }
136
137 static GListStore *
new_store(guint * numbers)138 new_store (guint *numbers)
139 {
140 GListStore *store = new_empty_store ();
141 guint i;
142
143 for (i = 0; numbers[i] != 0; i++)
144 add (store, numbers[i]);
145
146 return store;
147 }
148
149 static void
items_changed(GListModel * model,guint position,guint removed,guint added,GString * changes)150 items_changed (GListModel *model,
151 guint position,
152 guint removed,
153 guint added,
154 GString *changes)
155 {
156 g_assert_true (removed != 0 || added != 0);
157
158 if (changes->len)
159 g_string_append (changes, ", ");
160
161 if (removed == 1 && added == 0)
162 {
163 g_string_append_printf (changes, "-%u", position);
164 }
165 else if (removed == 0 && added == 1)
166 {
167 g_string_append_printf (changes, "+%u", position);
168 }
169 else
170 {
171 g_string_append_printf (changes, "%u", position);
172 if (removed > 0)
173 g_string_append_printf (changes, "-%u", removed);
174 if (added > 0)
175 g_string_append_printf (changes, "+%u", added);
176 }
177 }
178
179 static void
free_changes(gpointer data)180 free_changes (gpointer data)
181 {
182 GString *changes = data;
183
184 /* all changes must have been checked via assert_changes() before */
185 g_assert_cmpstr (changes->str, ==, "");
186
187 g_string_free (changes, TRUE);
188 }
189
190 static int
compare_modulo(gconstpointer first,gconstpointer second,gpointer modulo)191 compare_modulo (gconstpointer first,
192 gconstpointer second,
193 gpointer modulo)
194 {
195 guint mod = GPOINTER_TO_UINT (modulo);
196
197 return (GPOINTER_TO_UINT (g_object_get_qdata (G_OBJECT (first), number_quark)) % mod)
198 - (GPOINTER_TO_UINT (g_object_get_qdata (G_OBJECT (second), number_quark)) % mod);
199 }
200
201 static int
compare(gconstpointer first,gconstpointer second,gpointer unused)202 compare (gconstpointer first,
203 gconstpointer second,
204 gpointer unused)
205 {
206 return GPOINTER_TO_UINT (g_object_get_qdata (G_OBJECT (first), number_quark))
207 - GPOINTER_TO_UINT (g_object_get_qdata (G_OBJECT (second), number_quark));
208 }
209
210 static GtkSortListModel *
new_model(gpointer model)211 new_model (gpointer model)
212 {
213 GtkSortListModel *result;
214 GString *changes;
215
216 g_assert_true (model == NULL || G_IS_LIST_MODEL (model));
217
218 if (model)
219 {
220 GtkSorter *sorter;
221
222 sorter = GTK_SORTER (gtk_custom_sorter_new (compare, NULL, NULL));
223 result = gtk_sort_list_model_new (g_object_ref (model), sorter);
224 }
225 else
226 result = gtk_sort_list_model_new (NULL, NULL);
227
228 changes = g_string_new ("");
229 g_object_set_qdata_full (G_OBJECT(result), changes_quark, changes, free_changes);
230 g_signal_connect (result, "items-changed", G_CALLBACK (items_changed), changes);
231
232 return result;
233 }
234
235 static void
test_create_empty(void)236 test_create_empty (void)
237 {
238 GtkSortListModel *sort;
239
240 sort = new_model (NULL);
241 assert_model (sort, "");
242 assert_changes (sort, "");
243
244 g_object_unref (sort);
245 }
246
247 static void
test_create(void)248 test_create (void)
249 {
250 GtkSortListModel *sort;
251 GListStore *store;
252
253 store = new_store ((guint[]) { 4, 8, 2, 6, 10, 0 });
254 sort = new_model (store);
255 assert_model (sort, "2 4 6 8 10");
256 assert_changes (sort, "");
257
258 g_object_unref (store);
259 assert_model (sort, "2 4 6 8 10");
260 assert_changes (sort, "");
261
262 g_object_unref (sort);
263 }
264
265 static void
test_set_model(void)266 test_set_model (void)
267 {
268 GtkSortListModel *sort;
269 GListStore *store;
270
271 sort = new_model (NULL);
272 assert_model (sort, "");
273 assert_changes (sort, "");
274
275 store = new_store ((guint[]) { 4, 8, 2, 6, 10, 0 });
276 gtk_sort_list_model_set_model (sort, G_LIST_MODEL (store));
277 assert_model (sort, "4 8 2 6 10");
278 assert_changes (sort, "0+5");
279
280 gtk_sort_list_model_set_model (sort, NULL);
281 assert_model (sort, "");
282 assert_changes (sort, "0-5");
283
284 g_object_unref (sort);
285
286
287 sort = new_model (store);
288 assert_model (sort, "2 4 6 8 10");
289 assert_changes (sort, "");
290
291 gtk_sort_list_model_set_model (sort, NULL);
292 assert_model (sort, "");
293 assert_changes (sort, "0-5");
294
295 gtk_sort_list_model_set_model (sort, G_LIST_MODEL (store));
296 assert_model (sort, "2 4 6 8 10");
297 assert_changes (sort, "0+5");
298
299 g_object_unref (store);
300 g_object_unref (sort);
301 }
302
303 static void
test_set_sorter(void)304 test_set_sorter (void)
305 {
306 GtkSortListModel *sort;
307 GtkSorter *sorter;
308 GListStore *store;
309
310 store = new_store ((guint[]) { 4, 8, 2, 6, 10, 0 });
311 sort = new_model (store);
312 assert_model (sort, "2 4 6 8 10");
313 assert_changes (sort, "");
314
315 sorter = GTK_SORTER (gtk_custom_sorter_new (compare_modulo, GUINT_TO_POINTER (5), NULL));
316 gtk_sort_list_model_set_sorter (sort, sorter);
317 g_object_unref (sorter);
318 assert_model (sort, "10 6 2 8 4");
319 assert_changes (sort, "0-5+5");
320
321 gtk_sort_list_model_set_sorter (sort, NULL);
322 assert_model (sort, "4 8 2 6 10");
323 assert_changes (sort, "0-5+5");
324
325 sorter = GTK_SORTER (gtk_custom_sorter_new (compare, NULL, NULL));
326 gtk_sort_list_model_set_sorter (sort, sorter);
327 g_object_unref (sorter);
328 assert_model (sort, "2 4 6 8 10");
329 assert_changes (sort, "0-4+4");
330
331 g_object_unref (store);
332 g_object_unref (sort);
333 }
334
335 static void
test_add_items(void)336 test_add_items (void)
337 {
338 GtkSortListModel *sort;
339 GListStore *store;
340
341 /* add beginning */
342 store = new_store ((guint[]) { 51, 99, 100, 49, 50, 0 });
343 sort = new_model (store);
344 assert_model (sort, "49 50 51 99 100");
345 assert_changes (sort, "");
346 splice (store, 4, 0, (guint[]) { 1, 2 }, 2);
347 assert_model (sort, "1 2 49 50 51 99 100");
348 assert_changes (sort, "0+2");
349 g_object_unref (store);
350 g_object_unref (sort);
351
352 /* add middle */
353 store = new_store ((guint[]) { 99, 100, 1, 2, 0 });
354 sort = new_model (store);
355 assert_model (sort, "1 2 99 100");
356 assert_changes (sort, "");
357 splice (store, 2, 0, (guint[]) { 49, 50, 51 }, 3);
358 assert_model (sort, "1 2 49 50 51 99 100");
359 assert_changes (sort, "2+3");
360 g_object_unref (store);
361 g_object_unref (sort);
362
363 /* add end */
364 store = new_store ((guint[]) { 51, 49, 1, 2, 50, 0 });
365 sort = new_model (store);
366 assert_model (sort, "1 2 49 50 51");
367 assert_changes (sort, "");
368 splice (store, 1, 0, (guint[]) { 99, 100 }, 2);
369 assert_model (sort, "1 2 49 50 51 99 100");
370 assert_changes (sort, "5+2");
371 g_object_unref (store);
372 g_object_unref (sort);
373 }
374
375 static void
test_remove_items(void)376 test_remove_items (void)
377 {
378 GtkSortListModel *sort;
379 GListStore *store;
380
381 /* remove beginning */
382 store = new_store ((guint[]) { 51, 99, 100, 49, 1, 2, 50, 0 });
383 sort = new_model (store);
384 assert_model (sort, "1 2 49 50 51 99 100");
385 assert_changes (sort, "");
386 splice (store, 4, 2, NULL, 0);
387 assert_model (sort, "49 50 51 99 100");
388 assert_changes (sort, "0-2");
389 g_object_unref (store);
390 g_object_unref (sort);
391
392 /* remove middle */
393 store = new_store ((guint[]) { 99, 100, 51, 49, 50, 1, 2, 0 });
394 sort = new_model (store);
395 assert_model (sort, "1 2 49 50 51 99 100");
396 assert_changes (sort, "");
397 splice (store, 2, 3, NULL, 0);
398 assert_model (sort, "1 2 99 100");
399 assert_changes (sort, "2-3");
400 g_object_unref (store);
401 g_object_unref (sort);
402
403 /* remove end */
404 store = new_store ((guint[]) { 51, 99, 100, 49, 1, 2, 50, 0 });
405 sort = new_model (store);
406 assert_model (sort, "1 2 49 50 51 99 100");
407 assert_changes (sort, "");
408 splice (store, 1, 2, NULL, 0);
409 assert_model (sort, "1 2 49 50 51");
410 assert_changes (sort, "5-2");
411 g_object_unref (store);
412 g_object_unref (sort);
413 }
414
415 static void
test_stability(void)416 test_stability (void)
417 {
418 GtkSortListModel *sort;
419 GListStore *store;
420 GtkSorter *sorter;
421
422 store = new_store ((guint[]) { 11, 31, 21, 1, 0 });
423 sort = new_model (store);
424 assert_model (sort, "1 11 21 31");
425 assert_changes (sort, "");
426
427 sorter = GTK_SORTER (gtk_custom_sorter_new (compare_modulo, GUINT_TO_POINTER (5), NULL));
428 gtk_sort_list_model_set_sorter (sort, sorter);
429 g_object_unref (sorter);
430 assert_model (sort, "11 31 21 1");
431 assert_changes (sort, "0-4+4");
432
433 g_object_unref (store);
434 g_object_unref (sort);
435 }
436
437 static GListStore *
new_shuffled_store(guint size)438 new_shuffled_store (guint size)
439 {
440 GListStore *store = new_empty_store ();
441 guint i;
442
443 add (store, 1);
444
445 for (i = 1; i < size; i++)
446 insert (store, g_random_int_range (0, i), i + 1);
447
448 return store;
449 }
450
451 /* Test that we don't crash when things are removed from the
452 * model while it is incrementally sorting.
453 */
454 static void
test_incremental_remove(void)455 test_incremental_remove (void)
456 {
457 GListStore *store;
458 GtkSortListModel *model;
459 GtkSorter *sorter;
460 guint i;
461 GListStore *removed;
462 const guint n_items = 100000;
463
464 store = new_shuffled_store (n_items);
465 model = new_model (NULL);
466 gtk_sort_list_model_set_incremental (model, TRUE);
467
468 gtk_sort_list_model_set_model (model, G_LIST_MODEL (store));
469
470 sorter = GTK_SORTER (gtk_custom_sorter_new (compare, NULL, NULL));
471 gtk_sort_list_model_set_sorter (model, sorter);
472 g_object_unref (sorter);
473
474 removed = g_list_store_new (G_TYPE_OBJECT);
475
476 while (gtk_sort_list_model_get_pending (model) != 0)
477 {
478 g_main_context_iteration (NULL, TRUE);
479
480 /* randomly remove items while the sort is ongoing */
481 if (g_list_model_get_n_items (G_LIST_MODEL (removed)) < 100)
482 {
483 guint position;
484
485 position = g_random_int_range (0, g_list_model_get_n_items (G_LIST_MODEL (store)) - 10);
486 for (i = 0; i < 10; i++)
487 {
488 GObject *item = g_list_model_get_item (G_LIST_MODEL (store), position + i);
489 g_list_store_append (removed, item);
490 g_object_unref (item);
491 }
492 g_list_store_splice (store, position, 10, NULL, 0);
493 }
494 }
495
496 g_assert_cmpuint (gtk_sort_list_model_get_pending (model), ==, 0);
497
498 gtk_sort_list_model_set_incremental (model, FALSE);
499
500 /* add them back */
501 for (i = 0; i < g_list_model_get_n_items (G_LIST_MODEL (removed)); i++)
502 {
503 GObject *item = g_list_model_get_item (G_LIST_MODEL (removed), i);
504 g_list_store_append (store, item);
505 g_object_unref (item);
506 }
507
508 g_assert_cmpuint (g_list_model_get_n_items (G_LIST_MODEL (model)), ==, n_items);
509
510 for (i = 0; i < g_list_model_get_n_items (G_LIST_MODEL (model)); i++)
511 g_assert_cmpuint (i + 1, ==, get (G_LIST_MODEL (model), i));
512
513 ignore_changes (model);
514
515 g_object_unref (store);
516 g_object_unref (model);
517 g_object_unref (removed);
518 }
519
520 static void
test_out_of_bounds_access(void)521 test_out_of_bounds_access (void)
522 {
523 GtkSortListModel *sort;
524 GListStore *store;
525 gpointer item;
526
527 store = new_store ((guint[]) { 4, 8, 2, 6, 10, 0 });
528 sort = new_model (store);
529
530 item = g_list_model_get_item (G_LIST_MODEL (sort), GTK_INVALID_LIST_POSITION);
531 g_assert_null (item);
532
533 g_object_unref (store);
534 g_object_unref (sort);
535 }
536
537 int
main(int argc,char * argv[])538 main (int argc, char *argv[])
539 {
540 (g_test_init) (&argc, &argv, NULL);
541 setlocale (LC_ALL, "C");
542
543 number_quark = g_quark_from_static_string ("Hell and fire was spawned to be released.");
544 changes_quark = g_quark_from_static_string ("What did I see? Can I believe what I saw?");
545
546 g_test_add_func ("/sortlistmodel/create_empty", test_create_empty);
547 g_test_add_func ("/sortlistmodel/create", test_create);
548 g_test_add_func ("/sortlistmodel/set-model", test_set_model);
549 g_test_add_func ("/sortlistmodel/set-sorter", test_set_sorter);
550 #if GLIB_CHECK_VERSION (2, 58, 0) /* g_list_store_splice() is broken before 2.58 */
551 g_test_add_func ("/sortlistmodel/add_items", test_add_items);
552 g_test_add_func ("/sortlistmodel/remove_items", test_remove_items);
553 #endif
554 g_test_add_func ("/sortlistmodel/stability", test_stability);
555 g_test_add_func ("/sortlistmodel/incremental/remove", test_incremental_remove);
556 g_test_add_func ("/sortlistmodel/oob-access", test_out_of_bounds_access);
557
558 return g_test_run ();
559 }
560