1#include <glib.h>
2#include <stdlib.h>
3
4#define SIZE 50
5#define NUMBER_MIN 0000
6#define NUMBER_MAX 9999
7
8
9static guint32 array[SIZE];
10
11
12static gint
13sort (gconstpointer p1, gconstpointer p2)
14{
15 gint32 a, b;
16
17 a = GPOINTER_TO_INT (p1);
18 b = GPOINTER_TO_INT (p2);
19
20 return (a > b ? +1 : a == b ? 0 : -1);
21}
22
23/*
24 * glist sort tests
25 */
26static void
27test_list_sort (void)
28{
29 GList *list = NULL;
30 gint i;
31
32 for (i = 0; i < SIZE; i++)
33 list = g_list_append (list, GINT_TO_POINTER (array[i]));
34
35 list = g_list_sort (list, compare_func: sort);
36 for (i = 0; i < SIZE - 1; i++)
37 {
38 gpointer p1, p2;
39
40 p1 = g_list_nth_data (list, n: i);
41 p2 = g_list_nth_data (list, n: i+1);
42
43 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
44 }
45
46 g_list_free (list);
47}
48
49static void
50test_list_sort_with_data (void)
51{
52 GList *list = NULL;
53 gint i;
54
55 for (i = 0; i < SIZE; i++)
56 list = g_list_append (list, GINT_TO_POINTER (array[i]));
57
58 list = g_list_sort_with_data (list, compare_func: (GCompareDataFunc)sort, NULL);
59 for (i = 0; i < SIZE - 1; i++)
60 {
61 gpointer p1, p2;
62
63 p1 = g_list_nth_data (list, n: i);
64 p2 = g_list_nth_data (list, n: i+1);
65
66 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
67 }
68
69 g_list_free (list);
70}
71
72/* Test that the sort is stable. */
73static void
74test_list_sort_stable (void)
75{
76 GList *list = NULL; /* (element-type utf8) */
77 GList *copy = NULL; /* (element-type utf8) */
78 gsize i;
79
80 /* Build a test list, already ordered. */
81 for (i = 0; i < SIZE; i++)
82 list = g_list_append (list, data: g_strdup_printf (format: "%" G_GSIZE_FORMAT, i / 5));
83
84 /* Take a copy and sort it. */
85 copy = g_list_copy (list);
86 copy = g_list_sort (list: copy, compare_func: (GCompareFunc) g_strcmp0);
87
88 /* Compare the two lists, checking pointers are equal to ensure the elements
89 * have been kept stable. */
90 for (i = 0; i < SIZE; i++)
91 {
92 gpointer p1, p2;
93
94 p1 = g_list_nth_data (list, n: i);
95 p2 = g_list_nth_data (list, n: i);
96
97 g_assert (p1 == p2);
98 }
99
100 g_list_free (list: copy);
101 g_list_free_full (list, free_func: g_free);
102}
103
104static void
105test_list_insert_sorted (void)
106{
107 GList *list = NULL;
108 gint i;
109
110 for (i = 0; i < SIZE; i++)
111 list = g_list_insert_sorted (list, GINT_TO_POINTER (array[i]), func: sort);
112
113 for (i = 0; i < SIZE - 1; i++)
114 {
115 gpointer p1, p2;
116
117 p1 = g_list_nth_data (list, n: i);
118 p2 = g_list_nth_data (list, n: i+1);
119
120 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
121 }
122
123 g_list_free (list);
124}
125
126static void
127test_list_insert_sorted_with_data (void)
128{
129 GList *list = NULL;
130 gint i;
131
132 for (i = 0; i < SIZE; i++)
133 list = g_list_insert_sorted_with_data (list,
134 GINT_TO_POINTER (array[i]),
135 func: (GCompareDataFunc)sort,
136 NULL);
137
138 for (i = 0; i < SIZE - 1; i++)
139 {
140 gpointer p1, p2;
141
142 p1 = g_list_nth_data (list, n: i);
143 p2 = g_list_nth_data (list, n: i+1);
144
145 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
146 }
147
148 g_list_free (list);
149}
150
151static void
152test_list_reverse (void)
153{
154 GList *list = NULL;
155 GList *st;
156 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
157 gint i;
158
159 for (i = 0; i < 10; i++)
160 list = g_list_append (list, data: &nums[i]);
161
162 list = g_list_reverse (list);
163
164 for (i = 0; i < 10; i++)
165 {
166 st = g_list_nth (list, n: i);
167 g_assert (*((gint*) st->data) == (9 - i));
168 }
169
170 g_list_free (list);
171}
172
173static void
174test_list_nth (void)
175{
176 GList *list = NULL;
177 GList *st;
178 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
179 gint i;
180
181 for (i = 0; i < 10; i++)
182 list = g_list_append (list, data: &nums[i]);
183
184 for (i = 0; i < 10; i++)
185 {
186 st = g_list_nth (list, n: i);
187 g_assert (*((gint*) st->data) == i);
188 }
189
190 g_list_free (list);
191}
192
193static void
194test_list_concat (void)
195{
196 GList *list1 = NULL;
197 GList *list2 = NULL;
198 GList *st;
199 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
200 gint i;
201
202 for (i = 0; i < 5; i++)
203 {
204 list1 = g_list_append (list: list1, data: &nums[i]);
205 list2 = g_list_append (list: list2, data: &nums[i+5]);
206 }
207
208 g_assert_cmpint (g_list_length (list1), ==, 5);
209 g_assert_cmpint (g_list_length (list2), ==, 5);
210
211 list1 = g_list_concat (list1, list2);
212
213 g_assert_cmpint (g_list_length (list1), ==, 10);
214
215 for (i = 0; i < 10; i++)
216 {
217 st = g_list_nth (list: list1, n: i);
218 g_assert (*((gint*) st->data) == i);
219 }
220
221 list2 = g_list_concat (NULL, list2: list1);
222 g_assert_cmpint (g_list_length (list2), ==, 10);
223
224 list2 = g_list_concat (list1, NULL);
225 g_assert_cmpint (g_list_length (list2), ==, 10);
226
227 list2 = g_list_concat (NULL, NULL);
228 g_assert (list2 == NULL);
229
230 g_list_free (list: list1);
231}
232
233static void
234test_list_remove (void)
235{
236 GList *list = NULL;
237 GList *st;
238 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
239 gint i;
240
241 for (i = 0; i < 10; i++)
242 {
243 list = g_list_append (list, data: &nums[i]);
244 list = g_list_append (list, data: &nums[i]);
245 }
246
247 g_assert_cmpint (g_list_length (list), ==, 20);
248
249 for (i = 0; i < 10; i++)
250 {
251 list = g_list_remove (list, data: &nums[i]);
252 }
253
254 g_assert_cmpint (g_list_length (list), ==, 10);
255
256 for (i = 0; i < 10; i++)
257 {
258 st = g_list_nth (list, n: i);
259 g_assert (*((gint*) st->data) == i);
260 }
261
262 g_list_free (list);
263}
264
265static void
266test_list_remove_all (void)
267{
268 GList *list = NULL;
269 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
270 gint i;
271
272 for (i = 0; i < 10; i++)
273 {
274 list = g_list_append (list, data: &nums[i]);
275 list = g_list_append (list, data: &nums[i]);
276 }
277
278 g_assert_cmpint (g_list_length (list), ==, 20);
279
280 for (i = 0; i < 5; i++)
281 {
282 list = g_list_remove_all (list, data: &nums[2 * i + 1]);
283 list = g_list_remove_all (list, data: &nums[8 - 2 * i]);
284 }
285
286 g_assert_cmpint (g_list_length (list), ==, 0);
287 g_assert (list == NULL);
288}
289
290static void
291test_list_first_last (void)
292{
293 GList *list = NULL;
294 GList *st;
295 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
296 gint i;
297
298 for (i = 0; i < 10; i++)
299 list = g_list_append (list, data: &nums[i]);
300
301 st = g_list_last (list);
302 g_assert (*((gint*) st->data) == 9);
303 st = g_list_nth_prev (list: st, n: 3);
304 g_assert (*((gint*) st->data) == 6);
305 st = g_list_first (list: st);
306 g_assert (*((gint*) st->data) == 0);
307
308 g_list_free (list);
309}
310
311static void
312test_list_insert (void)
313{
314 GList *list = NULL;
315 GList *st;
316 gint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
317 gint i;
318
319 list = g_list_insert_before (NULL, NULL, data: &nums[1]);
320 list = g_list_insert (list, data: &nums[3], position: 1);
321 list = g_list_insert (list, data: &nums[4], position: -1);
322 list = g_list_insert (list, data: &nums[0], position: 0);
323 list = g_list_insert (list, data: &nums[5], position: 100);
324 list = g_list_insert_before (list, NULL, data: &nums[6]);
325 list = g_list_insert_before (list, sibling: list->next->next, data: &nums[2]);
326
327 list = g_list_insert (list, data: &nums[9], position: 7);
328 list = g_list_insert (list, data: &nums[8], position: 7);
329 list = g_list_insert (list, data: &nums[7], position: 7);
330
331 for (i = 0; i < 10; i++)
332 {
333 st = g_list_nth (list, n: i);
334 g_assert (*((gint*) st->data) == i);
335 }
336
337 g_list_free (list);
338}
339
340typedef struct
341{
342 gboolean freed;
343 int x;
344} ListItem;
345
346static void
347free_func (gpointer data)
348{
349 ListItem *item = data;
350
351 item->freed = TRUE;
352}
353
354static ListItem *
355new_item (int x)
356{
357 ListItem *item;
358
359 item = g_slice_new (ListItem);
360 item->freed = FALSE;
361 item->x = x;
362
363 return item;
364}
365
366static void
367test_free_full (void)
368{
369 ListItem *one, *two, *three;
370 GSList *slist = NULL;
371 GList *list = NULL;
372
373 slist = g_slist_prepend (list: slist, data: one = new_item (x: 1));
374 slist = g_slist_prepend (list: slist, data: two = new_item (x: 2));
375 slist = g_slist_prepend (list: slist, data: three = new_item (x: 3));
376 g_assert (!one->freed);
377 g_assert (!two->freed);
378 g_assert (!three->freed);
379 g_slist_free_full (list: slist, free_func);
380 g_assert (one->freed);
381 g_assert (two->freed);
382 g_assert (three->freed);
383 g_slice_free (ListItem, one);
384 g_slice_free (ListItem, two);
385 g_slice_free (ListItem, three);
386
387 list = g_list_prepend (list, data: one = new_item (x: 1));
388 list = g_list_prepend (list, data: two = new_item (x: 2));
389 list = g_list_prepend (list, data: three = new_item (x: 3));
390 g_assert (!one->freed);
391 g_assert (!two->freed);
392 g_assert (!three->freed);
393 g_list_free_full (list, free_func);
394 g_assert (one->freed);
395 g_assert (two->freed);
396 g_assert (three->freed);
397 g_slice_free (ListItem, one);
398 g_slice_free (ListItem, two);
399 g_slice_free (ListItem, three);
400}
401
402static void
403test_list_copy (void)
404{
405 GList *l, *l2;
406 GList *u, *v;
407
408 l = NULL;
409 l = g_list_append (list: l, GINT_TO_POINTER (1));
410 l = g_list_append (list: l, GINT_TO_POINTER (2));
411 l = g_list_append (list: l, GINT_TO_POINTER (3));
412
413 l2 = g_list_copy (list: l);
414
415 for (u = l, v = l2; u && v; u = u->next, v = v->next)
416 {
417 g_assert (u->data == v->data);
418 }
419
420 g_list_free (list: l);
421 g_list_free (list: l2);
422}
423
424static gpointer
425multiply_value (gconstpointer value, gpointer data)
426{
427 return GINT_TO_POINTER (GPOINTER_TO_INT (value) * GPOINTER_TO_INT (data));
428}
429
430static void
431test_list_copy_deep (void)
432{
433 GList *l, *l2;
434 GList *u, *v;
435
436 l = NULL;
437 l = g_list_append (list: l, GINT_TO_POINTER (1));
438 l = g_list_append (list: l, GINT_TO_POINTER (2));
439 l = g_list_append (list: l, GINT_TO_POINTER (3));
440
441 l2 = g_list_copy_deep (list: l, func: multiply_value, GINT_TO_POINTER (2));
442
443 for (u = l, v = l2; u && v; u = u->next, v = v->next)
444 {
445 g_assert_cmpint (GPOINTER_TO_INT (u->data) * 2, ==, GPOINTER_TO_INT (v->data));
446 }
447
448 g_list_free (list: l);
449 g_list_free (list: l2);
450}
451
452static void
453test_delete_link (void)
454{
455 GList *l, *l2;
456
457 l = NULL;
458 l = g_list_append (list: l, GINT_TO_POINTER (1));
459 l = g_list_append (list: l, GINT_TO_POINTER (2));
460 l = g_list_append (list: l, GINT_TO_POINTER (3));
461
462 l2 = l->next;
463
464 l = g_list_delete_link (list: l, link_: l2);
465 g_assert (l->data == GINT_TO_POINTER (1));
466 g_assert (l->next->data == GINT_TO_POINTER (3));
467
468 g_list_free (list: l);
469}
470
471static void
472test_prepend (void)
473{
474 gpointer a = "a";
475 gpointer b = "b";
476 gpointer c = "c";
477 GList *l, *l2;
478
479 l = NULL;
480 l = g_list_prepend (list: l, data: c);
481 l = g_list_prepend (list: l, data: a);
482
483 g_assert (l->data == a);
484 g_assert (l->next->data == c);
485 g_assert (l->next->next == NULL);
486
487 l2 = l->next;
488 l2 = g_list_prepend (list: l2, data: b);
489 g_assert (l2->prev == l);
490
491 g_assert (l->data == a);
492 g_assert (l->next->data == b);
493 g_assert (l->next->next->data == c);
494 g_assert (l->next->next->next == NULL);
495
496 g_list_free (list: l);
497}
498
499static void
500test_position (void)
501{
502 GList *l, *ll;
503
504 l = NULL;
505 l = g_list_append (list: l, data: "a");
506 l = g_list_append (list: l, data: "b");
507 l = g_list_append (list: l, data: "c");
508
509 ll = g_list_find (list: l, data: "a");
510 g_assert_cmpint (g_list_position (l, ll), ==, 0);
511 g_assert_cmpint (g_list_index (l, "a"), ==, 0);
512 ll = g_list_find (list: l, data: "b");
513 g_assert_cmpint (g_list_position (l, ll), ==, 1);
514 g_assert_cmpint (g_list_index (l, "b"), ==, 1);
515 ll = g_list_find (list: l, data: "c");
516 g_assert_cmpint (g_list_position (l, ll), ==, 2);
517 g_assert_cmpint (g_list_index (l, "c"), ==, 2);
518
519 ll = g_list_append (NULL, data: "d");
520 g_assert_cmpint (g_list_position (l, ll), ==, -1);
521 g_assert_cmpint (g_list_index (l, "d"), ==, -1);
522
523 g_list_free (list: l);
524 g_list_free (list: ll);
525}
526
527static void
528test_double_free (void)
529{
530 GList *list, *link;
531 GList intruder = { NULL, (gpointer)0xDEADBEEF, (gpointer)0xDEADBEEF };
532
533 if (g_test_subprocess ())
534 {
535 list = NULL;
536 list = g_list_append (list, data: "a");
537 link = list = g_list_append (list, data: "b");
538 list = g_list_append (list, data: "c");
539
540 list = g_list_remove_link (list, llink: link);
541 link->prev = list;
542 link->next = &intruder;
543 list = g_list_remove_link (list, llink: link);
544
545 g_list_free (list);
546 return;
547 }
548
549 g_test_trap_subprocess (NULL, usec_timeout: 0, test_flags: 0);
550 g_test_trap_assert_failed ();
551 g_test_trap_assert_stderr ("*corrupted double-linked list detected*");
552}
553
554static void
555test_list_insert_before_link (void)
556{
557 GList a = {0};
558 GList b = {0};
559 GList c = {0};
560 GList d = {0};
561 GList e = {0};
562 GList *list;
563
564 list = g_list_insert_before_link (NULL, NULL, link_: &a);
565 g_assert_nonnull (list);
566 g_assert_true (list == &a);
567 g_assert_null (a.prev);
568 g_assert_null (a.next);
569 g_assert_cmpint (g_list_length (list), ==, 1);
570
571 list = g_list_insert_before_link (list, sibling: &a, link_: &b);
572 g_assert_nonnull (list);
573 g_assert_true (list == &b);
574 g_assert_null (b.prev);
575 g_assert_true (b.next == &a);
576 g_assert_true (a.prev == &b);
577 g_assert_null (a.next);
578 g_assert_cmpint (g_list_length (list), ==, 2);
579
580 list = g_list_insert_before_link (list, sibling: &a, link_: &c);
581 g_assert_nonnull (list);
582 g_assert_true (list == &b);
583 g_assert_null (b.prev);
584 g_assert_true (b.next == &c);
585 g_assert_true (c.next == &a);
586 g_assert_true (c.prev == &b);
587 g_assert_true (a.prev == &c);
588 g_assert_null (a.next);
589 g_assert_cmpint (g_list_length (list), ==, 3);
590
591 list = g_list_insert_before_link (list, sibling: &b, link_: &d);
592 g_assert_nonnull (list);
593 g_assert_true (list == &d);
594 g_assert_null (d.prev);
595 g_assert_true (b.prev == &d);
596 g_assert_true (c.prev == &b);
597 g_assert_true (a.prev == &c);
598 g_assert_true (d.next == &b);
599 g_assert_true (b.next == &c);
600 g_assert_true (c.next == &a);
601 g_assert_null (a.next);
602 g_assert_cmpint (g_list_length (list), ==, 4);
603
604 list = g_list_insert_before_link (list, NULL, link_: &e);
605 g_assert_nonnull (list);
606 g_assert_true (list == &d);
607 g_assert_null (d.prev);
608 g_assert_true (b.prev == &d);
609 g_assert_true (c.prev == &b);
610 g_assert_true (a.prev == &c);
611 g_assert_true (d.next == &b);
612 g_assert_true (b.next == &c);
613 g_assert_true (c.next == &a);
614 g_assert_true (a.next == &e);
615 g_assert_true (e.prev == &a);
616 g_assert_null (e.next);
617 g_assert_cmpint (g_list_length (list), ==, 5);
618}
619
620int
621main (int argc, char *argv[])
622{
623 gint i;
624
625 g_test_init (argc: &argc, argv: &argv, NULL);
626
627 /* Create an array of random numbers. */
628 for (i = 0; i < SIZE; i++)
629 array[i] = g_test_rand_int_range (NUMBER_MIN, NUMBER_MAX);
630
631 g_test_add_func (testpath: "/list/sort", test_func: test_list_sort);
632 g_test_add_func (testpath: "/list/sort-with-data", test_func: test_list_sort_with_data);
633 g_test_add_func (testpath: "/list/sort/stable", test_func: test_list_sort_stable);
634 g_test_add_func (testpath: "/list/insert-before-link", test_func: test_list_insert_before_link);
635 g_test_add_func (testpath: "/list/insert-sorted", test_func: test_list_insert_sorted);
636 g_test_add_func (testpath: "/list/insert-sorted-with-data", test_func: test_list_insert_sorted_with_data);
637 g_test_add_func (testpath: "/list/reverse", test_func: test_list_reverse);
638 g_test_add_func (testpath: "/list/nth", test_func: test_list_nth);
639 g_test_add_func (testpath: "/list/concat", test_func: test_list_concat);
640 g_test_add_func (testpath: "/list/remove", test_func: test_list_remove);
641 g_test_add_func (testpath: "/list/remove-all", test_func: test_list_remove_all);
642 g_test_add_func (testpath: "/list/first-last", test_func: test_list_first_last);
643 g_test_add_func (testpath: "/list/insert", test_func: test_list_insert);
644 g_test_add_func (testpath: "/list/free-full", test_func: test_free_full);
645 g_test_add_func (testpath: "/list/copy", test_func: test_list_copy);
646 g_test_add_func (testpath: "/list/copy-deep", test_func: test_list_copy_deep);
647 g_test_add_func (testpath: "/list/delete-link", test_func: test_delete_link);
648 g_test_add_func (testpath: "/list/prepend", test_func: test_prepend);
649 g_test_add_func (testpath: "/list/position", test_func: test_position);
650 g_test_add_func (testpath: "/list/double-free", test_func: test_double_free);
651
652 return g_test_run ();
653}
654

source code of gtk/subprojects/glib/glib/tests/list.c