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