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
9 static guint32 array[SIZE];
10
11
12 static gint
13 sort (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 */
26 static void
27 test_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, sort);
36 for (i = 0; i < SIZE - 1; i++)
37 {
38 gpointer p1, p2;
39
40 p1 = g_list_nth_data (list, i);
41 p2 = g_list_nth_data (list, i+1);
42
43 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
44 }
45
46 g_list_free (list);
47 }
48
49 static void
50 test_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, (GCompareDataFunc)sort, NULL);
59 for (i = 0; i < SIZE - 1; i++)
60 {
61 gpointer p1, p2;
62
63 p1 = g_list_nth_data (list, i);
64 p2 = g_list_nth_data (list, 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. */
73 static void
74 test_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, g_strdup_printf ("%" G_GSIZE_FORMAT, i / 5));
83
84 /* Take a copy and sort it. */
85 copy = g_list_copy (list);
86 copy = g_list_sort (copy, (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, i);
95 p2 = g_list_nth_data (list, i);
96
97 g_assert (p1 == p2);
98 }
99
100 g_list_free (copy);
101 g_list_free_full (list, g_free);
102 }
103
104 static void
105 test_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]), sort);
112
113 for (i = 0; i < SIZE - 1; i++)
114 {
115 gpointer p1, p2;
116
117 p1 = g_list_nth_data (list, i);
118 p2 = g_list_nth_data (list, i+1);
119
120 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
121 }
122
123 g_list_free (list);
124 }
125
126 static void
127 test_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 (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, i);
143 p2 = g_list_nth_data (list, i+1);
144
145 g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
146 }
147
148 g_list_free (list);
149 }
150
151 static void
152 test_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, &nums[i]);
161
162 list = g_list_reverse (list);
163
164 for (i = 0; i < 10; i++)
165 {
166 st = g_list_nth (list, i);
167 g_assert (*((gint*) st->data) == (9 - i));
168 }
169
170 g_list_free (list);
171 }
172
173 static void
174 test_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, &nums[i]);
183
184 for (i = 0; i < 10; i++)
185 {
186 st = g_list_nth (list, i);
187 g_assert (*((gint*) st->data) == i);
188 }
189
190 g_list_free (list);
191 }
192
193 static void
194 test_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 (list1, &nums[i]);
205 list2 = g_list_append (list2, &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 (list1, i);
218 g_assert (*((gint*) st->data) == i);
219 }
220
221 list2 = g_list_concat (NULL, 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 (list1);
231 }
232
233 static void
234 test_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, &nums[i]);
244 list = g_list_append (list, &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, &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, i);
259 g_assert (*((gint*) st->data) == i);
260 }
261
262 g_list_free (list);
263 }
264
265 static void
266 test_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, &nums[i]);
275 list = g_list_append (list, &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, &nums[2 * i + 1]);
283 list = g_list_remove_all (list, &nums[8 - 2 * i]);
284 }
285
286 g_assert_cmpint (g_list_length (list), ==, 0);
287 g_assert (list == NULL);
288 }
289
290 static void
291 test_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, &nums[i]);
300
301 st = g_list_last (list);
302 g_assert (*((gint*) st->data) == 9);
303 st = g_list_nth_prev (st, 3);
304 g_assert (*((gint*) st->data) == 6);
305 st = g_list_first (st);
306 g_assert (*((gint*) st->data) == 0);
307
308 g_list_free (list);
309 }
310
311 static void
312 test_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, &nums[1]);
320 list = g_list_insert (list, &nums[3], 1);
321 list = g_list_insert (list, &nums[4], -1);
322 list = g_list_insert (list, &nums[0], 0);
323 list = g_list_insert (list, &nums[5], 100);
324 list = g_list_insert_before (list, NULL, &nums[6]);
325 list = g_list_insert_before (list, list->next->next, &nums[2]);
326
327 list = g_list_insert (list, &nums[9], 7);
328 list = g_list_insert (list, &nums[8], 7);
329 list = g_list_insert (list, &nums[7], 7);
330
331 for (i = 0; i < 10; i++)
332 {
333 st = g_list_nth (list, i);
334 g_assert (*((gint*) st->data) == i);
335 }
336
337 g_list_free (list);
338 }
339
340 typedef struct
341 {
342 gboolean freed;
343 int x;
344 } ListItem;
345
346 static void
347 free_func (gpointer data)
348 {
349 ListItem *item = data;
350
351 item->freed = TRUE;
352 }
353
354 static ListItem *
355 new_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
366 static void
367 test_free_full (void)
368 {
369 ListItem *one, *two, *three;
370 GSList *slist = NULL;
371 GList *list = NULL;
372
373 slist = g_slist_prepend (slist, one = new_item (1));
374 slist = g_slist_prepend (slist, two = new_item (2));
375 slist = g_slist_prepend (slist, three = new_item (3));
376 g_assert (!one->freed);
377 g_assert (!two->freed);
378 g_assert (!three->freed);
379 g_slist_free_full (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, one = new_item (1));
388 list = g_list_prepend (list, two = new_item (2));
389 list = g_list_prepend (list, three = new_item (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
402 static void
403 test_list_copy (void)
404 {
405 GList *l, *l2;
406 GList *u, *v;
407
408 l = NULL;
409 l = g_list_append (l, GINT_TO_POINTER (1));
410 l = g_list_append (l, GINT_TO_POINTER (2));
411 l = g_list_append (l, GINT_TO_POINTER (3));
412
413 l2 = g_list_copy (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 (l);
421 g_list_free (l2);
422 }
423
424 static gpointer
425 multiply_value (gconstpointer value, gpointer data)
426 {
427 return GINT_TO_POINTER (GPOINTER_TO_INT (value) * GPOINTER_TO_INT (data));
428 }
429
430 static void
431 test_list_copy_deep (void)
432 {
433 GList *l, *l2;
434 GList *u, *v;
435
436 l = NULL;
437 l = g_list_append (l, GINT_TO_POINTER (1));
438 l = g_list_append (l, GINT_TO_POINTER (2));
439 l = g_list_append (l, GINT_TO_POINTER (3));
440
441 l2 = g_list_copy_deep (l, 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 (l);
449 g_list_free (l2);
450 }
451
452 static void
453 test_delete_link (void)
454 {
455 GList *l, *l2;
456
457 l = NULL;
458 l = g_list_append (l, GINT_TO_POINTER (1));
459 l = g_list_append (l, GINT_TO_POINTER (2));
460 l = g_list_append (l, GINT_TO_POINTER (3));
461
462 l2 = l->next;
463
464 l = g_list_delete_link (l, 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 (l);
469 }
470
471 static void
472 test_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 (l, c);
481 l = g_list_prepend (l, 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 (l2, 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 (l);
497 }
498
499 static void
500 test_position (void)
501 {
502 GList *l, *ll;
503 char *a = "a";
504 char *b = "b";
505 char *c = "c";
506 char *d = "d";
507
508 l = NULL;
509 l = g_list_append (l, a);
510 l = g_list_append (l, b);
511 l = g_list_append (l, c);
512
513 ll = g_list_find (l, a);
514 g_assert_cmpint (g_list_position (l, ll), ==, 0);
515 g_assert_cmpint (g_list_index (l, a), ==, 0);
516 ll = g_list_find (l, b);
517 g_assert_cmpint (g_list_position (l, ll), ==, 1);
518 g_assert_cmpint (g_list_index (l, b), ==, 1);
519 ll = g_list_find (l, c);
520 g_assert_cmpint (g_list_position (l, ll), ==, 2);
521 g_assert_cmpint (g_list_index (l, c), ==, 2);
522
523 ll = g_list_append (NULL, d);
524 g_assert_cmpint (g_list_position (l, ll), ==, -1);
525 g_assert_cmpint (g_list_index (l, d), ==, -1);
526
527 g_list_free (l);
528 g_list_free (ll);
529 }
530
531 static void
532 test_double_free (void)
533 {
534 GList *list, *link;
535 // Casts to size_t first ensure compilers won't warn about pointer casts that change size
536 // MSVC's C4312 warning with /Wp64
537 GList intruder = { NULL, (gpointer)(size_t)0xDEADBEEF, (gpointer)(size_t)0xDEADBEEF };
538
539 if (g_test_subprocess ())
540 {
541 list = NULL;
542 list = g_list_append (list, "a");
543 link = list = g_list_append (list, "b");
544 list = g_list_append (list, "c");
545
546 list = g_list_remove_link (list, link);
547 link->prev = list;
548 link->next = &intruder;
549 list = g_list_remove_link (list, link);
550
551 g_list_free (list);
552 return;
553 }
554
555 g_test_trap_subprocess (NULL, 0, G_TEST_SUBPROCESS_DEFAULT);
556 g_test_trap_assert_failed ();
557 g_test_trap_assert_stderr ("*corrupted double-linked list detected*");
558 }
559
560 static void
561 test_list_insert_before_link (void)
562 {
563 GList a = {0};
564 GList b = {0};
565 GList c = {0};
566 GList d = {0};
567 GList e = {0};
568 GList *list;
569
570 list = g_list_insert_before_link (NULL, NULL, &a);
571 g_assert_nonnull (list);
572 g_assert_true (list == &a);
573 g_assert_null (a.prev);
574 g_assert_null (a.next);
575 g_assert_cmpint (g_list_length (list), ==, 1);
576
577 list = g_list_insert_before_link (list, &a, &b);
578 g_assert_nonnull (list);
579 g_assert_true (list == &b);
580 g_assert_null (b.prev);
581 g_assert_true (b.next == &a);
582 g_assert_true (a.prev == &b);
583 g_assert_null (a.next);
584 g_assert_cmpint (g_list_length (list), ==, 2);
585
586 list = g_list_insert_before_link (list, &a, &c);
587 g_assert_nonnull (list);
588 g_assert_true (list == &b);
589 g_assert_null (b.prev);
590 g_assert_true (b.next == &c);
591 g_assert_true (c.next == &a);
592 g_assert_true (c.prev == &b);
593 g_assert_true (a.prev == &c);
594 g_assert_null (a.next);
595 g_assert_cmpint (g_list_length (list), ==, 3);
596
597 list = g_list_insert_before_link (list, &b, &d);
598 g_assert_nonnull (list);
599 g_assert_true (list == &d);
600 g_assert_null (d.prev);
601 g_assert_true (b.prev == &d);
602 g_assert_true (c.prev == &b);
603 g_assert_true (a.prev == &c);
604 g_assert_true (d.next == &b);
605 g_assert_true (b.next == &c);
606 g_assert_true (c.next == &a);
607 g_assert_null (a.next);
608 g_assert_cmpint (g_list_length (list), ==, 4);
609
610 list = g_list_insert_before_link (list, NULL, &e);
611 g_assert_nonnull (list);
612 g_assert_true (list == &d);
613 g_assert_null (d.prev);
614 g_assert_true (b.prev == &d);
615 g_assert_true (c.prev == &b);
616 g_assert_true (a.prev == &c);
617 g_assert_true (d.next == &b);
618 g_assert_true (b.next == &c);
619 g_assert_true (c.next == &a);
620 g_assert_true (a.next == &e);
621 g_assert_true (e.prev == &a);
622 g_assert_null (e.next);
623 g_assert_cmpint (g_list_length (list), ==, 5);
624 }
625
626 int
627 main (int argc, char *argv[])
628 {
629 gint i;
630
631 g_test_init (&argc, &argv, NULL);
632
633 /* Create an array of random numbers. */
634 for (i = 0; i < SIZE; i++)
635 array[i] = g_test_rand_int_range (NUMBER_MIN, NUMBER_MAX);
636
637 g_test_add_func ("/list/sort", test_list_sort);
638 g_test_add_func ("/list/sort-with-data", test_list_sort_with_data);
639 g_test_add_func ("/list/sort/stable", test_list_sort_stable);
640 g_test_add_func ("/list/insert-before-link", test_list_insert_before_link);
641 g_test_add_func ("/list/insert-sorted", test_list_insert_sorted);
642 g_test_add_func ("/list/insert-sorted-with-data", test_list_insert_sorted_with_data);
643 g_test_add_func ("/list/reverse", test_list_reverse);
644 g_test_add_func ("/list/nth", test_list_nth);
645 g_test_add_func ("/list/concat", test_list_concat);
646 g_test_add_func ("/list/remove", test_list_remove);
647 g_test_add_func ("/list/remove-all", test_list_remove_all);
648 g_test_add_func ("/list/first-last", test_list_first_last);
649 g_test_add_func ("/list/insert", test_list_insert);
650 g_test_add_func ("/list/free-full", test_free_full);
651 g_test_add_func ("/list/copy", test_list_copy);
652 g_test_add_func ("/list/copy-deep", test_list_copy_deep);
653 g_test_add_func ("/list/delete-link", test_delete_link);
654 g_test_add_func ("/list/prepend", test_prepend);
655 g_test_add_func ("/list/position", test_position);
656 g_test_add_func ("/list/double-free", test_double_free);
657
658 return g_test_run ();
659 }