1#undef G_DISABLE_ASSERT
2#undef G_LOG_DOMAIN
3
4#include <time.h>
5#include <stdlib.h>
6
7#include <glib.h>
8
9
10static void
11check_integrity (GQueue *queue)
12{
13 GList *list;
14 GList *last;
15 GList *links;
16 GList *link;
17 guint n;
18
19 g_assert (queue->length < 4000000000u);
20
21 g_assert (g_queue_get_length (queue) == queue->length);
22
23 if (!queue->head)
24 g_assert (!queue->tail);
25 if (!queue->tail)
26 g_assert (!queue->head);
27
28 n = 0;
29 last = NULL;
30 for (list = queue->head; list != NULL; list = list->next)
31 {
32 if (!list->next)
33 last = list;
34 ++n;
35 }
36 g_assert (n == queue->length);
37 g_assert (last == queue->tail);
38
39 n = 0;
40 last = NULL;
41 for (list = queue->tail; list != NULL; list = list->prev)
42 {
43 if (!list->prev)
44 last = list;
45 ++n;
46 }
47 g_assert (n == queue->length);
48 g_assert (last == queue->head);
49
50 links = NULL;
51 for (list = queue->head; list != NULL; list = list->next)
52 links = g_list_prepend (list: links, data: list);
53
54 link = links;
55 for (list = queue->tail; list != NULL; list = list->prev)
56 {
57 g_assert (list == link->data);
58 link = link->next;
59 }
60 g_list_free (list: links);
61
62 links = NULL;
63 for (list = queue->tail; list != NULL; list = list->prev)
64 links = g_list_prepend (list: links, data: list);
65
66 link = links;
67 for (list = queue->head; list != NULL; list = list->next)
68 {
69 g_assert (list == link->data);
70 link = link->next;
71 }
72 g_list_free (list: links);
73}
74
75static gboolean
76rnd_bool (void)
77{
78 return g_random_int_range (begin: 0, end: 2);
79}
80
81static void
82check_max (gpointer elm, gpointer user_data)
83{
84 gint *best = user_data;
85 gint element = GPOINTER_TO_INT (elm);
86
87 if (element > *best)
88 *best = element;
89}
90
91static void
92check_min (gpointer elm, gpointer user_data)
93{
94 gint *best = user_data;
95 gint element = GPOINTER_TO_INT (elm);
96
97 if (element < *best)
98 *best = element;
99}
100
101static gint
102find_min (GQueue *queue)
103{
104 gint min = G_MAXINT;
105
106 g_queue_foreach (queue, func: check_min, user_data: &min);
107
108 return min;
109}
110
111static gint
112find_max (GQueue *queue)
113{
114 gint max = G_MININT;
115
116 g_queue_foreach (queue, func: check_max, user_data: &max);
117
118 return max;
119}
120
121static void
122delete_elm (gpointer elm, gpointer user_data)
123{
124 g_queue_remove (queue: (GQueue *)user_data, data: elm);
125 check_integrity (queue: (GQueue *)user_data);
126}
127
128static void
129delete_all (GQueue *queue)
130{
131 g_queue_foreach (queue, func: delete_elm, user_data: queue);
132}
133
134static int
135compare_int (gconstpointer a, gconstpointer b, gpointer data)
136{
137 int ai = GPOINTER_TO_INT (a);
138 int bi = GPOINTER_TO_INT (b);
139
140 if (ai > bi)
141 return 1;
142 else if (ai == bi)
143 return 0;
144 else
145 return -1;
146}
147
148static gint
149get_random_position (GQueue *queue, gboolean allow_offlist)
150{
151 int n;
152 enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
153
154 if (allow_offlist)
155 where = g_random_int_range (begin: OFF_QUEUE, end: LAST);
156 else
157 where = g_random_int_range (begin: HEAD, end: LAST);
158
159 switch (where)
160 {
161 case OFF_QUEUE:
162 n = g_random_int ();
163 break;
164
165 case HEAD:
166 n = 0;
167 break;
168
169 case TAIL:
170 if (allow_offlist)
171 n = queue->length;
172 else
173 n = queue->length - 1;
174 break;
175
176 case MIDDLE:
177 if (queue->length == 0)
178 n = 0;
179 else
180 n = g_random_int_range (begin: 0, end: queue->length);
181 break;
182
183 default:
184 g_assert_not_reached();
185 n = 100;
186 break;
187
188 }
189
190 return n;
191}
192
193static void
194random_test (gconstpointer d)
195{
196 guint32 seed = GPOINTER_TO_UINT (d);
197
198 typedef enum {
199 IS_EMPTY, GET_LENGTH, REVERSE, COPY,
200 FOREACH, FIND, FIND_CUSTOM, SORT,
201 PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
202 POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
203 PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
204 INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
205 PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
206 POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
207 LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
208 } QueueOp;
209
210#define N_ITERATIONS 500000
211#define N_QUEUES 3
212
213#define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
214
215 typedef struct QueueInfo QueueInfo;
216 struct QueueInfo
217 {
218 GQueue *queue;
219 GList *tail;
220 GList *head;
221 guint length;
222 };
223
224 gint i;
225 QueueOp op;
226 QueueInfo queues[N_QUEUES];
227
228 g_random_set_seed (seed);
229
230 for (i = 0; i < N_QUEUES; ++i)
231 {
232 queues[i].queue = g_queue_new ();
233 queues[i].head = NULL;
234 queues[i].tail = NULL;
235 queues[i].length = 0;
236 }
237
238 for (i = 0; i < N_ITERATIONS; ++i)
239 {
240 int j;
241 QueueInfo *qinf = RANDOM_QUEUE();
242 GQueue *q = qinf->queue;
243 op = g_random_int_range (begin: IS_EMPTY, end: LAST_OP);
244
245 g_assert (qinf->head == q->head);
246 g_assert (qinf->tail == q->tail);
247 g_assert (qinf->length == q->length);
248
249 switch (op)
250 {
251 case IS_EMPTY:
252 {
253 if (g_queue_is_empty (queue: qinf->queue))
254 {
255 g_assert (q->head == NULL);
256 g_assert (q->tail == NULL);
257 g_assert (q->length == 0);
258 }
259 else
260 {
261 g_assert (q->head);
262 g_assert (q->tail);
263 g_assert (q->length > 0);
264 }
265 }
266 break;
267 case GET_LENGTH:
268 {
269 guint l;
270
271 l = g_queue_get_length (queue: q);
272
273 g_assert (qinf->length == q->length);
274 g_assert (qinf->length == l);
275 }
276 break;
277 case REVERSE:
278 g_queue_reverse (queue: q);
279 g_assert (qinf->tail == q->head);
280 g_assert (qinf->head == q->tail);
281 g_assert (qinf->length == q->length);
282 qinf->tail = q->tail;
283 qinf->head = q->head;
284 break;
285 case COPY:
286 {
287 QueueInfo *random_queue = RANDOM_QUEUE();
288 GQueue *new_queue = g_queue_copy (queue: random_queue->queue);
289
290 g_queue_free (queue: qinf->queue);
291 q = qinf->queue = new_queue;
292 qinf->head = new_queue->head;
293 qinf->tail = g_list_last (list: new_queue->head);
294 qinf->length = new_queue->length;
295 }
296 break;
297 case FOREACH:
298 delete_all (queue: q);
299 qinf->head = NULL;
300 qinf->tail = NULL;
301 qinf->length = 0;
302 break;
303 case FIND:
304 {
305 gboolean find_existing = rnd_bool ();
306 int first = find_max (queue: q);
307 int second = find_min (queue: q);
308
309 if (q->length == 0)
310 find_existing = FALSE;
311
312 if (!find_existing)
313 first++;
314 if (!find_existing)
315 second--;
316
317 if (find_existing)
318 {
319 g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
320 g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
321 }
322 else
323 {
324 g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
325 g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
326 }
327 }
328 break;
329 case FIND_CUSTOM:
330 break;
331 case SORT:
332 {
333 if (!g_queue_is_empty (queue: q))
334 {
335 int max = find_max (queue: q);
336 int min = find_min (queue: q);
337 g_queue_remove_all (queue: q, GINT_TO_POINTER (max));
338 check_integrity (queue: q);
339 g_queue_remove_all (queue: q, GINT_TO_POINTER (min));
340 check_integrity (queue: q);
341 g_queue_push_head (queue: q, GINT_TO_POINTER (max));
342 if (max != min)
343 g_queue_push_head (queue: q, GINT_TO_POINTER (min));
344 qinf->length = q->length;
345 }
346
347 check_integrity (queue: q);
348
349 g_queue_sort (queue: q, compare_func: compare_int, NULL);
350
351 check_integrity (queue: q);
352
353 qinf->head = g_queue_find (queue: q, GINT_TO_POINTER (find_min(q)));
354 qinf->tail = g_queue_find (queue: q, GINT_TO_POINTER (find_max(q)));
355
356 g_assert (qinf->tail == q->tail);
357 }
358 break;
359 case PUSH_HEAD:
360 {
361 int x = g_random_int_range (begin: 0, end: 435435);
362 g_queue_push_head (queue: q, GINT_TO_POINTER (x));
363 if (!qinf->head)
364 qinf->tail = qinf->head = q->head;
365 else
366 qinf->head = qinf->head->prev;
367 qinf->length++;
368 }
369 break;
370 case PUSH_TAIL:
371 {
372 int x = g_random_int_range (begin: 0, end: 236546);
373 g_queue_push_tail (queue: q, GINT_TO_POINTER (x));
374 if (!qinf->tail)
375 qinf->tail = qinf->head = q->head;
376 else
377 qinf->tail = qinf->tail->next;
378 qinf->length++;
379 }
380 break;
381 case PUSH_NTH:
382 {
383 int pos = get_random_position (queue: q, TRUE);
384 int x = g_random_int_range (begin: 0, end: 236546);
385 g_queue_push_nth (queue: q, GINT_TO_POINTER (x), n: pos);
386 if (qinf->head && qinf->head->prev)
387 qinf->head = qinf->head->prev;
388 else
389 qinf->head = q->head;
390 if (qinf->tail && qinf->tail->next)
391 qinf->tail = qinf->tail->next;
392 else
393 qinf->tail = g_list_last (list: qinf->head);
394 qinf->length++;
395 }
396 break;
397 case POP_HEAD:
398 if (qinf->head)
399 qinf->head = qinf->head->next;
400 if (!qinf->head)
401 qinf->tail = NULL;
402 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
403 g_queue_pop_head (queue: q);
404 break;
405 case POP_TAIL:
406 if (qinf->tail)
407 qinf->tail = qinf->tail->prev;
408 if (!qinf->tail)
409 qinf->head = NULL;
410 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
411 g_queue_pop_tail (queue: q);
412 break;
413 case POP_NTH:
414 if (!g_queue_is_empty (queue: q))
415 {
416 int n = get_random_position (queue: q, TRUE);
417 gpointer elm = g_queue_peek_nth (queue: q, n);
418
419 if (n == (int) (q->length - 1))
420 qinf->tail = qinf->tail->prev;
421
422 if (n == 0)
423 qinf->head = qinf->head->next;
424
425 if (n >= 0 && (guint) n < q->length)
426 qinf->length--;
427
428 g_assert (elm == g_queue_pop_nth (q, n));
429 }
430 break;
431 case PEEK_HEAD:
432 if (qinf->head)
433 g_assert (qinf->head->data == g_queue_peek_head (q));
434 else
435 g_assert (g_queue_peek_head (q) == NULL);
436 break;
437 case PEEK_TAIL:
438 if (qinf->tail)
439 g_assert (qinf->tail->data == g_queue_peek_tail (q));
440 else
441 g_assert (g_queue_peek_tail (q) == NULL);
442 break;
443 case PEEK_NTH:
444 if (g_queue_is_empty (queue: q))
445 {
446 for (j = -10; j < 10; ++j)
447 g_assert (g_queue_peek_nth (q, j) == NULL);
448 }
449 else
450 {
451 GList *list;
452 int n = get_random_position (queue: q, TRUE);
453 if (n < 0 || (guint) n >= q->length)
454 {
455 g_assert (g_queue_peek_nth (q, n) == NULL);
456 }
457 else
458 {
459 list = qinf->head;
460 for (j = 0; j < n; ++j)
461 list = list->next;
462
463 g_assert (list->data == g_queue_peek_nth (q, n));
464 }
465 }
466 break;
467 case INDEX:
468 case LINK_INDEX:
469 {
470 int x = g_random_int_range (begin: 0, end: 386538);
471 int n;
472 GList *list;
473
474 g_queue_remove_all (queue: q, GINT_TO_POINTER (x));
475 check_integrity (queue: q);
476 g_queue_push_tail (queue: q, GINT_TO_POINTER (x));
477 check_integrity (queue: q);
478 g_queue_sort (queue: q, compare_func: compare_int, NULL);
479 check_integrity (queue: q);
480
481 n = 0;
482 for (list = q->head; list != NULL; list = list->next)
483 {
484 if (list->data == GINT_TO_POINTER (x))
485 break;
486 n++;
487 }
488 g_assert (list);
489 g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
490 g_queue_link_index (q, list));
491 g_assert (g_queue_link_index (q, list) == n);
492
493 qinf->head = q->head;
494 qinf->tail = q->tail;
495 qinf->length = q->length;
496 }
497 break;
498 case REMOVE:
499 if (!g_queue_is_empty (queue: q))
500 g_queue_remove (queue: q, data: qinf->tail->data);
501 /* qinf->head/qinf->tail may be invalid at this point */
502 if (!g_queue_is_empty (queue: q))
503 g_queue_remove (queue: q, data: q->head->data);
504 if (!g_queue_is_empty (queue: q))
505 g_queue_remove (queue: q, data: g_queue_peek_nth (queue: q, n: get_random_position (queue: q, TRUE)));
506
507 qinf->head = q->head;
508 qinf->tail = q->tail;
509 qinf->length = q->length;
510 break;
511 case REMOVE_ALL:
512 if (!g_queue_is_empty (queue: q))
513 g_queue_remove_all (queue: q, data: qinf->tail->data);
514 /* qinf->head/qinf->tail may be invalid at this point */
515 if (!g_queue_is_empty (queue: q))
516 g_queue_remove_all (queue: q, data: q->head->data);
517 if (!g_queue_is_empty (queue: q))
518 g_queue_remove_all (queue: q, data: g_queue_peek_nth (queue: q, n: get_random_position (queue: q, TRUE)));
519
520 qinf->head = q->head;
521 qinf->tail = q->tail;
522 qinf->length = q->length;
523 break;
524 case INSERT_BEFORE:
525 if (!g_queue_is_empty (queue: q))
526 {
527 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
528
529 g_queue_insert_before (queue: q, sibling: qinf->tail, data: x);
530 g_queue_insert_before (queue: q, sibling: qinf->head, data: x);
531 g_queue_insert_before (queue: q, sibling: g_queue_find (queue: q, data: x), data: x);
532 g_queue_insert_before (queue: q, NULL, data: x);
533 }
534 qinf->head = q->head;
535 qinf->tail = q->tail;
536 qinf->length = q->length;
537 break;
538 case INSERT_AFTER:
539 if (!g_queue_is_empty (queue: q))
540 {
541 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
542
543 g_queue_insert_after (queue: q, sibling: qinf->tail, data: x);
544 g_queue_insert_after (queue: q, sibling: qinf->head, data: x);
545 g_queue_insert_after (queue: q, sibling: g_queue_find (queue: q, data: x), data: x);
546 g_queue_insert_after (queue: q, NULL, data: x);
547 }
548 qinf->head = q->head;
549 qinf->tail = q->tail;
550 qinf->length = q->length;
551 break;
552 case INSERT_SORTED:
553 {
554 int max = find_max (queue: q);
555 int min = find_min (queue: q);
556
557 if (g_queue_is_empty (queue: q))
558 {
559 max = 345;
560 min = -12;
561 }
562
563 g_queue_sort (queue: q, compare_func: compare_int, NULL);
564 check_integrity (queue: q);
565 g_queue_insert_sorted (queue: q, GINT_TO_POINTER (max + 1), func: compare_int, NULL);
566 check_integrity (queue: q);
567 g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
568 g_queue_insert_sorted (queue: q, GINT_TO_POINTER (min - 1), func: compare_int, NULL);
569 check_integrity (queue: q);
570 g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
571 qinf->head = q->head;
572 qinf->tail = q->tail;
573 qinf->length = q->length;
574 }
575 break;
576 case PUSH_HEAD_LINK:
577 {
578 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
579 g_queue_push_head_link (queue: q, link_: link);
580 if (!qinf->tail)
581 qinf->tail = link;
582 qinf->head = link;
583 qinf->length++;
584 }
585 break;
586 case PUSH_TAIL_LINK:
587 {
588 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
589 g_queue_push_tail_link (queue: q, link_: link);
590 if (!qinf->head)
591 qinf->head = link;
592 qinf->tail = link;
593 qinf->length++;
594 }
595 break;
596 case PUSH_NTH_LINK:
597 {
598 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
599 gint n = get_random_position (queue: q, TRUE);
600 g_queue_push_nth_link (queue: q, n, link_: link);
601
602 if (qinf->head && qinf->head->prev)
603 qinf->head = qinf->head->prev;
604 else
605 qinf->head = q->head;
606 if (qinf->tail && qinf->tail->next)
607 qinf->tail = qinf->tail->next;
608 else
609 qinf->tail = g_list_last (list: qinf->head);
610 qinf->length++;
611 }
612 break;
613 case POP_HEAD_LINK:
614 if (!g_queue_is_empty (queue: q))
615 {
616 qinf->head = qinf->head->next;
617 if (!qinf->head)
618 qinf->tail = NULL;
619 qinf->length--;
620 g_list_free (list: g_queue_pop_head_link (queue: q));
621 }
622 break;
623 case POP_TAIL_LINK:
624 if (!g_queue_is_empty (queue: q))
625 {
626 qinf->tail = qinf->tail->prev;
627 if (!qinf->tail)
628 qinf->head = NULL;
629 qinf->length--;
630 g_list_free (list: g_queue_pop_tail_link (queue: q));
631 }
632 break;
633 case POP_NTH_LINK:
634 if (g_queue_is_empty (queue: q))
635 g_assert (g_queue_pop_nth_link (q, 200) == NULL);
636 else
637 {
638 int n = get_random_position (queue: q, FALSE);
639
640 if (n == (int) (g_queue_get_length (queue: q) - 1))
641 qinf->tail = qinf->tail->prev;
642
643 if (n == 0)
644 qinf->head = qinf->head->next;
645
646 qinf->length--;
647
648 g_list_free (list: g_queue_pop_nth_link (queue: q, n));
649 }
650 break;
651 case PEEK_HEAD_LINK:
652 if (g_queue_is_empty (queue: q))
653 g_assert (g_queue_peek_head_link (q) == NULL);
654 else
655 g_assert (g_queue_peek_head_link (q) == qinf->head);
656 break;
657 case PEEK_TAIL_LINK:
658 if (g_queue_is_empty (queue: q))
659 g_assert (g_queue_peek_tail_link (q) == NULL);
660 else
661 g_assert (g_queue_peek_tail_link (q) == qinf->tail);
662 break;
663 case PEEK_NTH_LINK:
664 if (g_queue_is_empty(queue: q))
665 g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
666 else
667 {
668 gint n = get_random_position (queue: q, FALSE);
669 GList *link;
670
671 link = q->head;
672 for (j = 0; j < n; ++j)
673 link = link->next;
674
675 g_assert (g_queue_peek_nth_link (q, n) == link);
676 }
677 break;
678 case UNLINK:
679 if (!g_queue_is_empty (queue: q))
680 {
681 gint n = g_random_int_range (begin: 0, end: g_queue_get_length (queue: q));
682 GList *link;
683
684 link = q->head;
685 for (j = 0; j < n; ++j)
686 link = link->next;
687
688 g_queue_unlink (queue: q, link_: link);
689 check_integrity (queue: q);
690
691 g_list_free (list: link);
692
693 qinf->head = q->head;
694 qinf->tail = q->tail;
695 qinf->length--;
696 }
697 break;
698 case DELETE_LINK:
699 if (!g_queue_is_empty (queue: q))
700 {
701 gint n = g_random_int_range (begin: 0, end: g_queue_get_length (queue: q));
702 GList *link;
703
704 link = q->head;
705 for (j = 0; j < n; ++j)
706 link = link->next;
707
708 g_queue_delete_link (queue: q, link_: link);
709 check_integrity (queue: q);
710
711 qinf->head = q->head;
712 qinf->tail = q->tail;
713 qinf->length--;
714 }
715 break;
716 case LAST_OP:
717 default:
718 g_assert_not_reached();
719 break;
720 }
721
722 if (qinf->head != q->head ||
723 qinf->tail != q->tail ||
724 qinf->length != q->length)
725 g_printerr (format: "op: %d\n", op);
726
727 g_assert (qinf->head == q->head);
728 g_assert (qinf->tail == q->tail);
729 g_assert (qinf->length == q->length);
730
731 for (j = 0; j < N_QUEUES; ++j)
732 check_integrity (queue: queues[j].queue);
733 }
734
735 for (i = 0; i < N_QUEUES; ++i)
736 g_queue_free (queue: queues[i].queue);
737}
738
739static void
740remove_item (gpointer data, gpointer q)
741{
742 GQueue *queue = q;
743
744 g_queue_remove (queue, data);
745}
746
747static void
748test_basic (void)
749{
750 GQueue *q;
751 GList *node;
752 gpointer data;
753
754 q = g_queue_new ();
755
756 g_assert (g_queue_is_empty (q));
757 g_queue_push_head (queue: q, GINT_TO_POINTER (2));
758 check_integrity (queue: q);
759 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
760 check_integrity (queue: q);
761 g_assert (!g_queue_is_empty (q));
762 check_integrity (queue: q);
763 g_assert_cmpint (g_list_length (q->head), ==, 1);
764 g_assert (q->head == q->tail);
765 g_queue_push_head (queue: q, GINT_TO_POINTER (1));
766 check_integrity (queue: q);
767 g_assert (q->head->next == q->tail);
768 g_assert (q->tail->prev == q->head);
769 g_assert_cmpint (g_list_length (q->head), ==, 2);
770 check_integrity (queue: q);
771 g_assert (q->tail->data == GINT_TO_POINTER (2));
772 g_assert (q->head->data == GINT_TO_POINTER (1));
773 check_integrity (queue: q);
774 g_queue_push_tail (queue: q, GINT_TO_POINTER (3));
775 g_assert_cmpint (g_list_length (q->head), ==, 3);
776 g_assert (q->head->data == GINT_TO_POINTER (1));
777 g_assert (q->head->next->data == GINT_TO_POINTER (2));
778 g_assert (q->head->next->next == q->tail);
779 g_assert (q->head->next == q->tail->prev);
780 g_assert (q->tail->data == GINT_TO_POINTER (3));
781 g_queue_push_tail (queue: q, GINT_TO_POINTER (4));
782 check_integrity (queue: q);
783 g_assert_cmpint (g_list_length (q->head), ==, 4);
784 g_assert (q->head->data == GINT_TO_POINTER (1));
785 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
786 g_queue_push_tail (queue: q, GINT_TO_POINTER (5));
787 check_integrity (queue: q);
788 g_assert_cmpint (g_list_length (q->head), ==, 5);
789 g_assert (g_queue_is_empty (q) == FALSE);
790 check_integrity (queue: q);
791 g_assert_cmpint (q->length, ==, 5);
792 g_assert (q->head->prev == NULL);
793 g_assert (q->head->data == GINT_TO_POINTER (1));
794 g_assert (q->head->next->data == GINT_TO_POINTER (2));
795 g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
796 g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
797 g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
798 g_assert (q->head->next->next->next->next->next == NULL);
799 g_assert (q->head->next->next->next->next == q->tail);
800 g_assert (q->tail->data == GINT_TO_POINTER (5));
801 g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
802 g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
803 g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
804 g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
805 g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
806 g_assert (q->tail->prev->prev->prev->prev == q->head);
807 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
808 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
809 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
810 check_integrity (queue: q);
811 g_assert_cmpint (g_list_length (q->head), ==, 4);
812 g_assert_cmpint (q->length, ==, 4);
813 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
814 check_integrity (queue: q);
815 g_assert_cmpint (g_list_length (q->head), ==, 3);
816
817 node = g_queue_pop_head_link (queue: q);
818 g_assert (node->data == GINT_TO_POINTER (2));
819 g_list_free_1 (list: node);
820
821 check_integrity (queue: q);
822 g_assert_cmpint (g_list_length (q->head), ==, 2);
823 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
824 check_integrity (queue: q);
825 g_assert_cmpint (g_list_length (q->head), ==, 1);
826 node = g_queue_pop_head_link (queue: q);
827 g_assert (node->data == GINT_TO_POINTER (3));
828 g_list_free_1 (list: node);
829 check_integrity (queue: q);
830 g_assert_cmpint (g_list_length (q->head), ==, 0);
831 g_assert (g_queue_pop_tail (q) == NULL);
832 check_integrity (queue: q);
833 g_assert_cmpint (g_list_length (q->head), ==, 0);
834 g_assert (g_queue_pop_head (q) == NULL);
835 check_integrity (queue: q);
836 g_assert_cmpint (g_list_length (q->head), ==, 0);
837 g_assert (g_queue_is_empty (q));
838 check_integrity (queue: q);
839
840 g_queue_push_head (queue: q, GINT_TO_POINTER (1));
841 check_integrity (queue: q);
842 g_assert_cmpint (g_list_length (q->head), ==, 1);
843 g_assert_cmpint (q->length, ==, 1);
844 g_queue_push_head (queue: q, GINT_TO_POINTER (2));
845 check_integrity (queue: q);
846 g_assert_cmpint (g_list_length (q->head), ==, 2);
847 g_assert_cmpint (q->length, ==, 2);
848 g_queue_push_head (queue: q, GINT_TO_POINTER (3));
849 check_integrity (queue: q);
850 g_assert_cmpint (g_list_length (q->head), ==, 3);
851 g_assert_cmpint (q->length, ==, 3);
852 g_queue_push_head (queue: q, GINT_TO_POINTER (4));
853 check_integrity (queue: q);
854 g_assert_cmpint (g_list_length (q->head), ==, 4);
855 g_assert_cmpint (q->length, ==, 4);
856 g_queue_push_head (queue: q, GINT_TO_POINTER (5));
857 check_integrity (queue: q);
858 g_assert_cmpint (g_list_length (q->head), ==, 5);
859 g_assert_cmpint (q->length, ==, 5);
860 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
861 check_integrity (queue: q);
862 g_assert_cmpint (g_list_length (q->head), ==, 4);
863 node = q->tail;
864 g_assert (node == g_queue_pop_tail_link (q));
865 check_integrity (queue: q);
866 g_list_free_1 (list: node);
867 g_assert_cmpint (g_list_length (q->head), ==, 3);
868 data = q->head->data;
869 g_assert (data == g_queue_pop_head (q));
870 check_integrity (queue: q);
871 g_assert_cmpint (g_list_length (q->head), ==, 2);
872 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
873 check_integrity (queue: q);
874 g_assert_cmpint (g_list_length (q->head), ==, 1);
875 g_assert (q->head == q->tail);
876 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
877 check_integrity (queue: q);
878 g_assert_cmpint (g_list_length (q->head), ==, 0);
879 g_assert (g_queue_pop_head (q) == NULL);
880 check_integrity (queue: q);
881 g_assert (g_queue_pop_head_link (q) == NULL);
882 check_integrity (queue: q);
883 g_assert_cmpint (g_list_length (q->head), ==, 0);
884 g_assert (g_queue_pop_tail_link (q) == NULL);
885 check_integrity (queue: q);
886 g_assert_cmpint (g_list_length (q->head), ==, 0);
887
888 g_queue_reverse (queue: q);
889 check_integrity (queue: q);
890 g_assert_cmpint (g_list_length (q->head), ==, 0);
891 g_queue_free (queue: q);
892}
893
894static void
895test_copy (void)
896{
897 GQueue *q, *q2;
898 gint i;
899
900 q = g_queue_new ();
901 q2 = g_queue_copy (queue: q);
902 check_integrity (queue: q);
903 check_integrity (queue: q2);
904 g_assert_cmpint (g_list_length (q->head), ==, 0);
905 g_assert_cmpint (g_list_length (q2->head), ==, 0);
906 g_queue_sort (queue: q, compare_func: compare_int, NULL);
907 check_integrity (queue: q2);
908 check_integrity (queue: q);
909 g_queue_sort (queue: q2, compare_func: compare_int, NULL);
910 check_integrity (queue: q2);
911 check_integrity (queue: q);
912
913 for (i = 0; i < 200; ++i)
914 {
915 g_queue_push_nth (queue: q, GINT_TO_POINTER (i), n: i);
916 g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
917 check_integrity (queue: q);
918 check_integrity (queue: q2);
919 }
920
921 for (i = 0; i < 200; ++i)
922 {
923 g_queue_remove (queue: q, GINT_TO_POINTER (i));
924 check_integrity (queue: q);
925 check_integrity (queue: q2);
926 }
927
928 for (i = 0; i < 200; ++i)
929 {
930 GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
931
932 g_queue_push_nth_link (queue: q, n: i, link_: l);
933 check_integrity (queue: q);
934 check_integrity (queue: q2);
935 g_queue_reverse (queue: q);
936 check_integrity (queue: q);
937 check_integrity (queue: q2);
938 }
939
940 g_queue_free (queue: q2);
941 q2 = g_queue_copy (queue: q);
942
943 g_queue_foreach (queue: q2, func: remove_item, user_data: q2);
944 check_integrity (queue: q2);
945 check_integrity (queue: q);
946
947 g_queue_free (queue: q);
948 g_queue_free (queue: q2);
949}
950
951static void
952test_off_by_one (void)
953{
954 GQueue *q;
955 GList *node;
956
957 q = g_queue_new ();
958
959 g_queue_push_tail (queue: q, GINT_TO_POINTER (1234));
960 check_integrity (queue: q);
961 node = g_queue_peek_tail_link (queue: q);
962 g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
963 node = g_queue_peek_nth_link (queue: q, n: g_queue_get_length (queue: q));
964 g_assert (node == NULL);
965 node = g_queue_peek_nth_link (queue: q, n: g_queue_get_length (queue: q) - 1);
966 g_assert (node->data == GINT_TO_POINTER (1234));
967 node = g_queue_pop_nth_link (queue: q, n: g_queue_get_length (queue: q));
968 g_assert (node == NULL);
969 node = g_queue_pop_nth_link (queue: q, n: g_queue_get_length (queue: q) - 1);
970 g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
971 g_list_free_1 (list: node);
972
973 g_queue_free (queue: q);
974}
975
976static gint
977find_custom (gconstpointer a, gconstpointer b)
978{
979 return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
980}
981
982static void
983test_find_custom (void)
984{
985 GQueue *q;
986 GList *node;
987 q = g_queue_new ();
988
989 g_queue_push_tail (queue: q, GINT_TO_POINTER (1234));
990 g_queue_push_tail (queue: q, GINT_TO_POINTER (1));
991 g_queue_push_tail (queue: q, GINT_TO_POINTER (2));
992 node = g_queue_find_custom (queue: q, GINT_TO_POINTER (1), func: find_custom);
993 g_assert (node != NULL);
994 node = g_queue_find_custom (queue: q, GINT_TO_POINTER (2), func: find_custom);
995 g_assert (node != NULL);
996 node = g_queue_find_custom (queue: q, GINT_TO_POINTER (3), func: find_custom);
997 g_assert (node == NULL);
998
999 g_queue_free (queue: q);
1000}
1001
1002static void
1003test_static (void)
1004{
1005 GQueue q;
1006 GQueue q2 = G_QUEUE_INIT;
1007
1008 g_queue_init (queue: &q);
1009
1010 check_integrity (queue: &q);
1011 g_assert (g_queue_is_empty (&q));
1012
1013 check_integrity (queue: &q2);
1014 g_assert (g_queue_is_empty (&q2));
1015}
1016
1017static void
1018test_clear (void)
1019{
1020 GQueue *q;
1021 q = g_queue_new ();
1022
1023 g_queue_push_tail (queue: q, GINT_TO_POINTER (1234));
1024 g_queue_push_tail (queue: q, GINT_TO_POINTER (1));
1025 g_queue_push_tail (queue: q, GINT_TO_POINTER (2));
1026 g_assert_cmpint (g_queue_get_length (q), ==, 3);
1027
1028 g_queue_clear (queue: q);
1029 check_integrity (queue: q);
1030 g_assert (g_queue_is_empty (q));
1031
1032 g_queue_free (queue: q);
1033}
1034
1035typedef struct
1036{
1037 gboolean freed;
1038 int x;
1039} QueueItem;
1040
1041static void
1042free_func (gpointer data)
1043{
1044 QueueItem *item = data;
1045
1046 item->freed = TRUE;
1047}
1048
1049static QueueItem *
1050new_item (int x)
1051{
1052 QueueItem *item;
1053
1054 item = g_slice_new (QueueItem);
1055 item->freed = FALSE;
1056 item->x = x;
1057
1058 return item;
1059}
1060
1061static void
1062test_clear_full (void)
1063{
1064 QueueItem *one, *two, *three, *four;
1065 GQueue *queue;
1066
1067 queue = g_queue_new ();
1068 g_queue_push_tail (queue, data: one = new_item (x: 1));
1069 g_queue_push_tail (queue, data: two = new_item (x: 2));
1070 g_queue_push_tail (queue, data: three = new_item (x: 3));
1071 g_queue_push_tail (queue, data: four = new_item (x: 4));
1072
1073 g_assert_cmpint (g_queue_get_length (queue), ==, 4);
1074 g_assert_false (one->freed);
1075 g_assert_false (two->freed);
1076 g_assert_false (three->freed);
1077 g_assert_false (four->freed);
1078
1079 g_queue_clear_full (queue, free_func);
1080
1081 g_assert_true (one->freed);
1082 g_assert_true (two->freed);
1083 g_assert_true (three->freed);
1084 g_assert_true (four->freed);
1085
1086 g_assert_true (g_queue_is_empty (queue));
1087 check_integrity (queue);
1088
1089 g_slice_free (QueueItem, one);
1090 g_slice_free (QueueItem, two);
1091 g_slice_free (QueueItem, three);
1092 g_slice_free (QueueItem, four);
1093 g_queue_free (queue);
1094}
1095
1096/* Check that g_queue_clear_full() called with a NULL free_func is equivalent
1097 * to g_queue_clear(). */
1098static void
1099test_clear_full_noop (void)
1100{
1101 QueueItem *one, *two, *three, *four;
1102 GQueue *queue;
1103
1104 queue = g_queue_new ();
1105 g_queue_push_tail (queue, data: one = new_item (x: 1));
1106 g_queue_push_tail (queue, data: two = new_item (x: 2));
1107 g_queue_push_tail (queue, data: three = new_item (x: 3));
1108 g_queue_push_tail (queue, data: four = new_item (x: 4));
1109
1110 g_assert_cmpint (g_queue_get_length (queue), ==, 4);
1111 g_assert_false (one->freed);
1112 g_assert_false (two->freed);
1113 g_assert_false (three->freed);
1114 g_assert_false (four->freed);
1115
1116 g_queue_clear_full (queue, NULL);
1117
1118 g_assert_true (g_queue_is_empty (queue));
1119 check_integrity (queue);
1120
1121 g_slice_free (QueueItem, one);
1122 g_slice_free (QueueItem, two);
1123 g_slice_free (QueueItem, three);
1124 g_slice_free (QueueItem, four);
1125 g_queue_free (queue);
1126}
1127
1128/* Test g_queue_push_nth_link() with various combinations of position (before,
1129 * in the middle of, or at the end of the queue) and various existing queues
1130 * (empty, single element, multiple elements). */
1131static void
1132test_push_nth_link (void)
1133{
1134 GQueue *q;
1135 q = g_queue_new ();
1136
1137 /* Push onto before the front of an empty queue (which results in it being
1138 * added to the end of the queue). */
1139 g_queue_push_nth_link (queue: q, n: -1, link_: g_list_prepend (NULL, GINT_TO_POINTER (1)));
1140 check_integrity (queue: q);
1141 g_assert_cmpint (g_queue_get_length (q), ==, 1);
1142 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 1);
1143
1144 g_queue_clear (queue: q);
1145
1146 /* Push onto after the rear of an empty queue. */
1147 g_queue_push_nth_link (queue: q, n: 100, link_: g_list_prepend (NULL, GINT_TO_POINTER (2)));
1148 check_integrity (queue: q);
1149 g_assert_cmpint (g_queue_get_length (q), ==, 1);
1150 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 2);
1151
1152 g_queue_clear (queue: q);
1153
1154 /* Push onto the front of an empty queue. */
1155 g_queue_push_nth_link (queue: q, n: 0, link_: g_list_prepend (NULL, GINT_TO_POINTER (3)));
1156 check_integrity (queue: q);
1157 g_assert_cmpint (g_queue_get_length (q), ==, 1);
1158 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 3);
1159
1160 g_queue_clear (queue: q);
1161
1162 /* Push onto before the front of a non-empty queue (which results in it being
1163 * added to the end of the queue). */
1164 g_queue_push_head (queue: q, GINT_TO_POINTER (4));
1165 g_queue_push_nth_link (queue: q, n: -1, link_: g_list_prepend (NULL, GINT_TO_POINTER (5)));
1166 check_integrity (queue: q);
1167 g_assert_cmpint (g_queue_get_length (q), ==, 2);
1168 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 4);
1169 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 5);
1170
1171 g_queue_clear (queue: q);
1172
1173 /* Push onto after the rear of a non-empty queue. */
1174 g_queue_push_head (queue: q, GINT_TO_POINTER (6));
1175 g_queue_push_nth_link (queue: q, n: 100, link_: g_list_prepend (NULL, GINT_TO_POINTER (7)));
1176 check_integrity (queue: q);
1177 g_assert_cmpint (g_queue_get_length (q), ==, 2);
1178 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 6);
1179 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 7);
1180
1181 g_queue_clear (queue: q);
1182
1183 /* Push onto the rear of a non-empty queue. */
1184 g_queue_push_head (queue: q, GINT_TO_POINTER (8));
1185 g_queue_push_nth_link (queue: q, n: 1, link_: g_list_prepend (NULL, GINT_TO_POINTER (9)));
1186 check_integrity (queue: q);
1187 g_assert_cmpint (g_queue_get_length (q), ==, 2);
1188 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 8);
1189 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 9);
1190
1191 g_queue_clear (queue: q);
1192
1193 /* Push onto the front of a non-empty queue. */
1194 g_queue_push_head (queue: q, GINT_TO_POINTER (10));
1195 g_queue_push_nth_link (queue: q, n: 0, link_: g_list_prepend (NULL, GINT_TO_POINTER (11)));
1196 check_integrity (queue: q);
1197 g_assert_cmpint (g_queue_get_length (q), ==, 2);
1198 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 11);
1199 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 10);
1200
1201 g_queue_clear (queue: q);
1202
1203 /* Push into the middle of a non-empty queue. */
1204 g_queue_push_head (queue: q, GINT_TO_POINTER (12));
1205 g_queue_push_head (queue: q, GINT_TO_POINTER (13));
1206 g_queue_push_nth_link (queue: q, n: 1, link_: g_list_prepend (NULL, GINT_TO_POINTER (14)));
1207 check_integrity (queue: q);
1208 g_assert_cmpint (g_queue_get_length (q), ==, 3);
1209 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 13);
1210 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 14);
1211 g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 2)), ==, 12);
1212
1213 g_queue_free (queue: q);
1214}
1215
1216static void
1217test_free_full (void)
1218{
1219 QueueItem *one, *two, *three;
1220 GQueue *queue = NULL;
1221
1222 queue = g_queue_new();
1223 g_queue_push_tail (queue, data: one = new_item (x: 1));
1224 g_queue_push_tail (queue, data: two = new_item (x: 2));
1225 g_queue_push_tail (queue, data: three = new_item (x: 3));
1226 g_assert (!one->freed);
1227 g_assert (!two->freed);
1228 g_assert (!three->freed);
1229 g_queue_free_full (queue, free_func);
1230 g_assert (one->freed);
1231 g_assert (two->freed);
1232 g_assert (three->freed);
1233 g_slice_free (QueueItem, one);
1234 g_slice_free (QueueItem, two);
1235 g_slice_free (QueueItem, three);
1236}
1237
1238static void
1239test_insert_sibling_link (void)
1240{
1241 GQueue q = G_QUEUE_INIT;
1242 GList a = {0};
1243 GList b = {0};
1244 GList c = {0};
1245 GList d = {0};
1246 GList e = {0};
1247
1248 g_queue_push_head_link (queue: &q, link_: &a);
1249 g_queue_insert_after_link (queue: &q, sibling: &a, link_: &d);
1250 g_queue_insert_before_link (queue: &q, sibling: &d, link_: &b);
1251 g_queue_insert_after_link (queue: &q, sibling: &b, link_: &c);
1252 g_queue_insert_after_link (queue: &q, NULL, link_: &e);
1253
1254 g_assert_true (q.head == &e);
1255 g_assert_true (q.tail == &d);
1256
1257 g_assert_null (e.prev);
1258 g_assert_true (e.next == &a);
1259
1260 g_assert_true (a.prev == &e);
1261 g_assert_true (a.next == &b);
1262
1263 g_assert_true (b.prev == &a);
1264 g_assert_true (b.next == &c);
1265
1266 g_assert_true (c.prev == &b);
1267 g_assert_true (c.next == &d);
1268
1269 g_assert_true (d.prev == &c);
1270 g_assert_null (d.next);
1271}
1272
1273int main (int argc, char *argv[])
1274{
1275 guint32 seed;
1276 gchar *path;
1277
1278 g_test_init (argc: &argc, argv: &argv, NULL);
1279
1280 g_test_add_func (testpath: "/queue/basic", test_func: test_basic);
1281 g_test_add_func (testpath: "/queue/copy", test_func: test_copy);
1282 g_test_add_func (testpath: "/queue/off-by-one", test_func: test_off_by_one);
1283 g_test_add_func (testpath: "/queue/find-custom", test_func: test_find_custom);
1284 g_test_add_func (testpath: "/queue/static", test_func: test_static);
1285 g_test_add_func (testpath: "/queue/clear", test_func: test_clear);
1286 g_test_add_func (testpath: "/queue/free-full", test_func: test_free_full);
1287 g_test_add_func (testpath: "/queue/clear-full", test_func: test_clear_full);
1288 g_test_add_func (testpath: "/queue/clear-full/noop", test_func: test_clear_full_noop);
1289 g_test_add_func (testpath: "/queue/insert-sibling-link", test_func: test_insert_sibling_link);
1290 g_test_add_func (testpath: "/queue/push-nth-link", test_func: test_push_nth_link);
1291
1292 seed = g_test_rand_int_range (begin: 0, G_MAXINT);
1293 path = g_strdup_printf (format: "/queue/random/seed:%u", seed);
1294 g_test_add_data_func (testpath: path, GUINT_TO_POINTER (seed), test_func: random_test);
1295 g_free (mem: path);
1296
1297 return g_test_run ();
1298}
1299

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