Merge remote branch 'gvdb/master'
[platform/upstream/glib.git] / tests / queue-test.c
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
10 static gboolean verbose = FALSE;
11
12
13 static void
14 check_integrity (GQueue *queue)
15 {
16   GList *list;
17   GList *last;
18   GList *links;
19   GList *link;
20   gint n;
21   
22   g_assert (queue->length < 4000000000u);
23   
24   g_assert (g_queue_get_length (queue) == queue->length);
25   
26   if (!queue->head)
27     g_assert (!queue->tail);
28   if (!queue->tail)
29     g_assert (!queue->head);
30   
31   n = 0;
32   last = NULL;
33   for (list = queue->head; list != NULL; list = list->next)
34     {
35       if (!list->next)
36         last = list;
37       ++n;
38     }
39   g_assert (n == queue->length); 
40   g_assert (last == queue->tail);
41   
42   n = 0;
43   last = NULL;
44   for (list = queue->tail; list != NULL; list = list->prev)
45     {
46       if (!list->prev)
47         last = list;
48       ++n;
49     }
50   g_assert (n == queue->length);
51   g_assert (last == queue->head);
52   
53   links = NULL;
54   for (list = queue->head; list != NULL; list = list->next)
55     links = g_list_prepend (links, list);
56   
57   link = links;
58   for (list = queue->tail; list != NULL; list = list->prev)
59     {
60       g_assert (list == link->data);
61       link = link->next;
62     }
63   g_list_free (links);
64   
65   links = NULL;
66   for (list = queue->tail; list != NULL; list = list->prev)
67     links = g_list_prepend (links, list);
68   
69   link = links;
70   for (list = queue->head; list != NULL; list = list->next)
71     {
72       g_assert (list == link->data);
73       link = link->next;
74     }
75   g_list_free (links);
76 }
77
78 static gboolean
79 rnd_bool (void)
80 {
81   return g_random_int_range (0, 2);
82 }
83
84 static void
85 check_max (gpointer elm, gpointer user_data)
86 {
87   gint *best = user_data;
88   gint element = GPOINTER_TO_INT (elm);
89
90   if (element > *best)
91     *best = element;
92 }
93
94 static void
95 check_min (gpointer elm, gpointer user_data)
96 {
97   gint *best = user_data;
98   gint element = GPOINTER_TO_INT (elm);
99
100   if (element < *best)
101     *best = element;
102 }
103
104 static gint
105 find_min (GQueue *queue)
106 {
107   gint min = G_MAXINT;
108
109   g_queue_foreach (queue, check_min, &min);
110
111   return min;
112 }
113
114 static gint
115 find_max (GQueue *queue)
116 {
117   gint max = G_MININT;
118   
119   g_queue_foreach (queue, check_max, &max);
120
121   return max;
122 }
123
124 static void
125 delete_elm (gpointer elm, gpointer user_data)
126 {
127   g_queue_remove ((GQueue *)user_data, elm);
128   check_integrity ((GQueue *)user_data);
129 }
130
131 static void
132 delete_all (GQueue *queue)
133 {
134   g_queue_foreach (queue, delete_elm, queue);
135 }
136
137 static int
138 compare_int (gconstpointer a, gconstpointer b, gpointer data)
139 {
140   int ai = GPOINTER_TO_INT (a);
141   int bi = GPOINTER_TO_INT (b);
142
143   if (ai > bi)
144     return 1;
145   else if (ai == bi)
146     return 0;
147   else
148     return -1;
149 }
150
151 static gint
152 get_random_position (GQueue *queue, gboolean allow_offlist)
153 {
154   int n;
155   enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
156
157   if (allow_offlist)
158     where = g_random_int_range (OFF_QUEUE, LAST);
159   else
160     where = g_random_int_range (HEAD, LAST);
161
162   switch (where)
163     {
164     case OFF_QUEUE:
165       n = g_random_int ();
166       break;
167
168     case HEAD:
169       n = 0;
170       break;
171
172     case TAIL:
173       if (allow_offlist)
174         n = queue->length;
175       else
176         n = queue->length - 1;
177       break;
178
179     case MIDDLE:
180       if (queue->length == 0)
181         n = 0;
182       else
183         n = g_random_int_range (0, queue->length);
184       break;
185
186     default:
187       g_assert_not_reached();
188       n = 100;
189       break;
190
191     }
192
193   return n;
194 }
195
196 static void
197 random_test (int seed)
198 {
199   typedef enum {
200     IS_EMPTY, GET_LENGTH, REVERSE, COPY,
201     FOREACH, FIND, FIND_CUSTOM, SORT,
202     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
203     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
204     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
205     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
206     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
207     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
208     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
209   } QueueOp;
210
211 #define N_ITERATIONS 500000
212 #define N_QUEUES 3
213
214 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
215
216   typedef struct QueueInfo QueueInfo;
217   struct QueueInfo
218   {
219     GQueue *queue;
220     GList *tail;
221     GList *head;
222     guint length;
223   };
224   
225   gint i;
226   QueueOp op;
227   QueueInfo queues[N_QUEUES];
228
229   if (verbose)
230     g_print ("seed: %d\n", seed);
231
232   g_random_set_seed (seed);
233   
234   for (i = 0; i < N_QUEUES; ++i)
235     {
236       queues[i].queue = g_queue_new ();
237       queues[i].head = NULL;
238       queues[i].tail = NULL;
239       queues[i].length = 0;
240     }
241   
242   for (i = 0; i < N_ITERATIONS; ++i)
243     {
244       int j;
245       QueueInfo *qinf = RANDOM_QUEUE();
246       GQueue *q = qinf->queue;
247       op = g_random_int_range (IS_EMPTY, LAST_OP);
248
249       g_assert (qinf->head == q->head);
250       g_assert (qinf->tail == q->tail);
251       g_assert (qinf->length == q->length);
252       
253       switch (op)
254         {
255         case IS_EMPTY:
256           {
257             if (g_queue_is_empty (qinf->queue))
258               {
259                 g_assert (q->head == NULL);
260                 g_assert (q->tail == NULL);
261                 g_assert (q->length == 0);
262               }
263             else
264               {
265                 g_assert (q->head);
266                 g_assert (q->tail);
267                 g_assert (q->length > 0);
268               }
269           }
270           break;
271         case GET_LENGTH:
272           {
273             int l;
274             
275             l = g_queue_get_length (q);
276             
277             g_assert (qinf->length == q->length);
278             g_assert (qinf->length == l);
279           }
280           break;
281         case REVERSE:
282           g_queue_reverse (q);
283           g_assert (qinf->tail == q->head);
284           g_assert (qinf->head == q->tail);
285           g_assert (qinf->length == q->length);
286           qinf->tail = q->tail;
287           qinf->head = q->head;
288           break;
289         case COPY:
290           {
291             QueueInfo *random_queue = RANDOM_QUEUE();
292             GQueue *new_queue = g_queue_copy (random_queue->queue);
293             
294             g_queue_free (qinf->queue);
295             q = qinf->queue = new_queue;
296             qinf->head = new_queue->head;
297             qinf->tail = g_list_last (new_queue->head);
298             qinf->length = new_queue->length;
299           }
300           break;
301         case FOREACH:
302           delete_all (q);
303           qinf->head = NULL;
304           qinf->tail = NULL;
305           qinf->length = 0;
306           break;
307         case FIND:
308           {
309             gboolean find_existing = rnd_bool ();
310             int first = find_max (q);
311             int second = find_min (q);
312
313             if (q->length == 0)
314               find_existing = FALSE;
315             
316             if (!find_existing)
317               first++;
318             if (!find_existing)
319               second--;
320
321             if (find_existing)
322               {
323                 g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
324                 g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
325               }
326             else
327               {
328                 g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
329                 g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
330               }
331           }
332           break;
333         case FIND_CUSTOM:
334           break;
335         case SORT:
336           {
337             if (!g_queue_is_empty (q))
338               {
339                 int max = find_max (q);
340                 int min = find_min (q);
341                 g_queue_remove_all (q, GINT_TO_POINTER (max));
342                 check_integrity (q);
343                 g_queue_remove_all (q, GINT_TO_POINTER (min));
344                 check_integrity (q);
345                 g_queue_push_head (q, GINT_TO_POINTER (max));
346                 if (max != min)
347                   g_queue_push_head (q, GINT_TO_POINTER (min));
348                 qinf->length = q->length;
349               }
350
351             check_integrity (q);
352             
353             g_queue_sort (q, compare_int, NULL);
354
355             check_integrity (q);
356             
357             qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
358             qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
359
360             g_assert (qinf->tail == q->tail);
361           }
362           break;
363         case PUSH_HEAD:
364           {
365             int x = g_random_int_range (0, 435435);
366             g_queue_push_head (q, GINT_TO_POINTER (x));
367             if (!qinf->head)
368               qinf->tail = qinf->head = q->head;
369             else
370               qinf->head = qinf->head->prev;
371             qinf->length++;
372           }
373           break;
374         case PUSH_TAIL:
375           {
376             int x = g_random_int_range (0, 236546);
377             g_queue_push_tail (q, GINT_TO_POINTER (x));
378             if (!qinf->tail)
379               qinf->tail = qinf->head = q->head;
380             else
381               qinf->tail = qinf->tail->next;
382             qinf->length++;
383           }
384           break;
385         case PUSH_NTH:
386           {
387             int pos = get_random_position (q, TRUE);
388             int x = g_random_int_range (0, 236546);
389             g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
390             if (qinf->head && qinf->head->prev)
391               qinf->head = qinf->head->prev;
392             else
393               qinf->head = q->head;
394             if (qinf->tail && qinf->tail->next)
395               qinf->tail = qinf->tail->next;
396             else
397               qinf->tail = g_list_last (qinf->head);
398             qinf->length++;
399           }
400           break;
401         case POP_HEAD:
402           if (qinf->head)
403             qinf->head = qinf->head->next;
404           if (!qinf->head)
405             qinf->tail = NULL;
406           qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
407           g_queue_pop_head (q);
408           break;
409         case POP_TAIL:
410           if (qinf->tail)
411             qinf->tail = qinf->tail->prev;
412           if (!qinf->tail)
413             qinf->head = NULL;
414           qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
415           g_queue_pop_tail (q);
416           break;
417         case POP_NTH:
418           if (!g_queue_is_empty (q))
419             {
420               int n = get_random_position (q, TRUE);
421               gpointer elm = g_queue_peek_nth (q, n);
422
423               if (n == q->length - 1)
424                 qinf->tail = qinf->tail->prev;
425               
426               if (n == 0)
427                 qinf->head = qinf->head->next;
428
429               if (n >= 0 && n < q->length)
430                 qinf->length--;
431               
432               g_assert (elm == g_queue_pop_nth (q, n));
433             }
434           break;
435         case PEEK_HEAD:
436           if (qinf->head)
437             g_assert (qinf->head->data == g_queue_peek_head (q));
438           else
439             g_assert (g_queue_peek_head (q) == NULL);
440           break;
441         case PEEK_TAIL:
442           if (qinf->head)
443             g_assert (qinf->tail->data == g_queue_peek_tail (q));
444           else
445             g_assert (g_queue_peek_tail (q) == NULL);
446           break;
447         case PEEK_NTH:
448           if (g_queue_is_empty (q))
449             {
450               for (j = -10; j < 10; ++j)
451                 g_assert (g_queue_peek_nth (q, j) == NULL);
452             }
453           else
454             {
455               GList *list;
456               int n = get_random_position (q, TRUE);
457               if (n < 0 || n >= q->length)
458                 {
459                   g_assert (g_queue_peek_nth (q, n) == NULL);
460                 }
461               else
462                 {
463                   list = qinf->head;
464                   for (j = 0; j < n; ++j)
465                     list = list->next;
466                   
467                   g_assert (list->data == g_queue_peek_nth (q, n));
468                 }
469             }
470           break;
471         case INDEX:
472         case LINK_INDEX:
473           {
474             int x = g_random_int_range (0, 386538);
475             int n;
476             GList *list;
477
478             g_queue_remove_all (q, GINT_TO_POINTER (x));
479             check_integrity (q);
480             g_queue_push_tail (q, GINT_TO_POINTER (x));
481             check_integrity (q);
482             g_queue_sort (q, compare_int, NULL);
483             check_integrity (q);
484
485             n = 0;
486             for (list = q->head; list != NULL; list = list->next)
487               {
488                 if (list->data == GINT_TO_POINTER (x))
489                   break;
490                 n++;
491               }
492             g_assert (list);
493             g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
494                       g_queue_link_index (q, list));
495             g_assert (g_queue_link_index (q, list) == n);
496
497             qinf->head = q->head;
498             qinf->tail = q->tail;
499             qinf->length = q->length;
500           }
501           break;
502         case REMOVE:
503           if (!g_queue_is_empty (q))
504             g_queue_remove (q, qinf->tail->data);
505           if (!g_queue_is_empty (q))
506             g_queue_remove (q, qinf->head->data);
507           if (!g_queue_is_empty (q))
508             g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
509
510           qinf->head = q->head;
511           qinf->tail = q->tail;
512           qinf->length = q->length;
513           break;
514         case REMOVE_ALL:
515           if (!g_queue_is_empty (q))
516             g_queue_remove_all (q, qinf->tail->data);
517           if (!g_queue_is_empty (q))
518             g_queue_remove_all (q, qinf->head->data);
519           if (!g_queue_is_empty (q))
520             g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
521
522           qinf->head = q->head;
523           qinf->tail = q->tail;
524           qinf->length = q->length;
525           break;
526         case INSERT_BEFORE:
527           if (!g_queue_is_empty (q))
528             {
529               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
530               
531               g_queue_insert_before (q, qinf->tail, x);
532               g_queue_insert_before (q, qinf->head, x);
533               g_queue_insert_before (q, g_queue_find (q, x), x);
534             }
535           qinf->head = q->head;
536           qinf->tail = q->tail;
537           qinf->length = q->length;
538           break;
539         case INSERT_AFTER:
540           if (!g_queue_is_empty (q))
541             {
542               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
543               
544               g_queue_insert_after (q, qinf->tail, x);
545               g_queue_insert_after (q, qinf->head, x);
546               g_queue_insert_after (q, g_queue_find (q, x), 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 (q);
555             int min = find_min (q);
556
557             if (g_queue_is_empty (q))
558               {
559                 max = 345;
560                 min = -12;
561               }
562             
563             g_queue_sort (q, compare_int, NULL);
564             check_integrity (q);
565             g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
566             check_integrity (q);
567             g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
568             g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
569             check_integrity (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 (q, 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 (q, 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 (q, TRUE);
600             g_queue_push_nth_link (q, n, 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 (qinf->head);
610             qinf->length++;
611           }
612           break;
613         case POP_HEAD_LINK:
614           if (!g_queue_is_empty (q))
615             {
616               qinf->head = qinf->head->next;
617               if (!qinf->head)
618                 qinf->tail = NULL;
619               qinf->length--;
620               g_list_free (g_queue_pop_head_link (q));
621             }
622           break;
623         case POP_TAIL_LINK:
624           if (!g_queue_is_empty (q))
625             {
626               qinf->tail = qinf->tail->prev;
627               if (!qinf->tail)
628                 qinf->head = NULL;
629               qinf->length--;
630               g_list_free (g_queue_pop_tail_link (q));
631             }
632           break;
633         case POP_NTH_LINK:
634           if (g_queue_is_empty (q))
635             g_assert (g_queue_pop_nth_link (q, 200) == NULL);
636           else
637             {
638               int n = get_random_position (q, FALSE);
639               
640               if (n == g_queue_get_length (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 (g_queue_pop_nth_link (q, n));
649             }
650           break;
651         case PEEK_HEAD_LINK:
652           if (g_queue_is_empty (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 (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(q))
665             g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
666           else
667             {
668               gint n = get_random_position (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 (q))
680             {
681               gint n = g_random_int_range (0, g_queue_get_length (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 (q, link);
689               check_integrity (q);
690
691               g_list_free (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 (q))
700             {
701               gint n = g_random_int_range (0, g_queue_get_length (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 (q, link);
709               check_integrity (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_print ("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 (queues[j].queue);
733     }
734   
735   for (i = 0; i < N_QUEUES; ++i)
736     g_queue_free (queues[i].queue);
737 }
738
739 static void
740 remove_item (gpointer data, gpointer q)
741 {
742   GQueue *queue = q;
743   
744   g_queue_remove (queue, data);
745 }
746
747 int main(int argc, gchar *args[])
748 {
749   GQueue *q, *q2;
750   GList *node;
751   gpointer data;
752   int i;
753   
754   if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v')
755     verbose = TRUE;
756
757   q = g_queue_new ();
758   
759   g_assert (g_queue_is_empty (q) == TRUE);
760   
761   g_queue_push_head (q, GINT_TO_POINTER (2));
762   check_integrity (q);
763   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
764   check_integrity (q);
765   g_assert (g_queue_is_empty (q) == FALSE);
766   check_integrity (q);
767   g_assert (g_list_length (q->head) == 1);
768   g_assert (q->head == q->tail);
769   g_queue_push_head (q, GINT_TO_POINTER (1));
770   check_integrity (q);
771   g_assert (q->head->next == q->tail);
772   g_assert (q->tail->prev == q->head);
773   g_assert (g_list_length (q->head) == 2);
774   check_integrity (q);
775   g_assert (q->tail->data == GINT_TO_POINTER (2));
776   g_assert (q->head->data == GINT_TO_POINTER (1));
777   check_integrity (q);
778   g_queue_push_tail (q, GINT_TO_POINTER (3));
779   g_assert (g_list_length (q->head) == 3);
780   g_assert (q->head->data == GINT_TO_POINTER (1));
781   g_assert (q->head->next->data == GINT_TO_POINTER (2));
782   g_assert (q->head->next->next == q->tail);
783   g_assert (q->head->next == q->tail->prev);
784   g_assert (q->tail->data == GINT_TO_POINTER (3));
785   g_queue_push_tail (q, GINT_TO_POINTER (4));
786   check_integrity (q);
787   g_assert (g_list_length (q->head) == 4);
788   g_assert (q->head->data == GINT_TO_POINTER (1));
789   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
790   g_queue_push_tail (q, GINT_TO_POINTER (5));
791   check_integrity (q);
792   g_assert (g_list_length (q->head) == 5);
793   
794   g_assert (g_queue_is_empty (q) == FALSE);
795   check_integrity (q);
796   
797   g_assert (q->length == 5);
798   g_assert (q->head->prev == NULL);
799   g_assert (q->head->data == GINT_TO_POINTER (1));
800   g_assert (q->head->next->data == GINT_TO_POINTER (2));
801   g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
802   g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
803   g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
804   g_assert (q->head->next->next->next->next->next == NULL);
805   g_assert (q->head->next->next->next->next == q->tail);
806   g_assert (q->tail->data == GINT_TO_POINTER (5));
807   g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
808   g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
809   g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
810   g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
811   g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
812   g_assert (q->tail->prev->prev->prev->prev == q->head);
813   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
814   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
815   
816   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
817   check_integrity (q);
818   g_assert (g_list_length (q->head) == 4 && q->length == 4);
819   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
820   check_integrity (q);
821   g_assert (g_list_length (q->head) == 3);
822   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
823   check_integrity (q);
824   g_assert (g_list_length (q->head) == 2);
825   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
826   check_integrity (q);
827   g_assert (g_list_length (q->head) == 1);
828   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
829   check_integrity (q);
830   g_assert (g_list_length (q->head) == 0);
831   g_assert (g_queue_pop_tail (q) == NULL);
832   check_integrity (q);
833   g_assert (g_list_length (q->head) == 0);
834   g_assert (g_queue_pop_head (q) == NULL);
835   check_integrity (q);
836   g_assert (g_list_length (q->head) == 0);
837   
838   g_assert (g_queue_is_empty (q) == TRUE);
839   check_integrity (q);
840   
841   /************************/
842   
843   g_queue_push_head (q, GINT_TO_POINTER (1));
844   check_integrity (q);
845   g_assert (g_list_length (q->head) == 1 && 1 == q->length);
846   g_queue_push_head (q, GINT_TO_POINTER (2));
847   check_integrity (q);
848   g_assert (g_list_length (q->head) == 2 && 2 == q->length);
849   g_queue_push_head (q, GINT_TO_POINTER (3));
850   check_integrity (q);
851   g_assert (g_list_length (q->head) == 3 && 3 == q->length);
852   g_queue_push_head (q, GINT_TO_POINTER (4));
853   check_integrity (q);
854   g_assert (g_list_length (q->head) == 4 && 4 == q->length);
855   g_queue_push_head (q, GINT_TO_POINTER (5));
856   check_integrity (q);
857   g_assert (g_list_length (q->head) == 5 && 5 == q->length);
858   
859   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
860   check_integrity (q);
861   g_assert (g_list_length (q->head) == 4);
862   node = q->tail;
863   g_assert (node == g_queue_pop_tail_link (q));
864   check_integrity (q);
865   g_assert (g_list_length (q->head) == 3);
866   data = q->head->data;
867   g_assert (data == g_queue_pop_head (q));
868   check_integrity (q);
869   g_assert (g_list_length (q->head) == 2);
870   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
871   check_integrity (q);
872   g_assert (g_list_length (q->head) == 1);
873   g_assert (q->head == q->tail);
874   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
875   check_integrity (q);
876   g_assert (g_list_length (q->head) == 0);
877   g_assert (g_queue_pop_head (q) == NULL);
878   check_integrity (q);
879   g_assert (g_queue_pop_head_link (q) == NULL);
880   check_integrity (q);
881   g_assert (g_list_length (q->head) == 0);
882   g_assert (g_queue_pop_tail_link (q) == NULL);
883   check_integrity (q);
884   g_assert (g_list_length (q->head) == 0);
885   
886   /* */
887   g_queue_reverse (q);
888   check_integrity (q);
889   g_assert (g_list_length (q->head) == 0);
890   
891   q2 = g_queue_copy (q);
892   check_integrity (q);
893   check_integrity (q2);
894   g_assert (g_list_length (q->head) == 0);
895   g_assert (g_list_length (q2->head) == 0);
896   g_queue_sort (q, compare_int, NULL);
897   check_integrity (q2);
898   check_integrity (q);
899   g_queue_sort (q2, compare_int, NULL);
900   check_integrity (q2);
901   check_integrity (q);
902   
903   for (i = 0; i < 200; ++i)
904     {
905       g_queue_push_nth (q, GINT_TO_POINTER (i), i);
906       g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
907       check_integrity (q);
908       check_integrity (q2);
909     }
910   
911   for (i = 0; i < 200; ++i)
912     {
913       g_queue_remove (q, GINT_TO_POINTER (i));
914       check_integrity (q);
915       check_integrity (q2);
916     }
917   
918   for (i = 0; i < 200; ++i)
919     {
920       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
921       
922       g_queue_push_nth_link (q, i, l);
923       check_integrity (q);
924       check_integrity (q2);
925       g_queue_reverse (q);
926       check_integrity (q);
927       check_integrity (q2);
928     }
929   
930   g_queue_free (q2);
931   q2 = g_queue_copy (q);
932   
933   g_queue_foreach (q2, remove_item, q2);
934   check_integrity (q2);
935   check_integrity (q);
936
937   /* some checks for off by one errors */  
938   g_queue_push_tail (q, GINT_TO_POINTER (1234));
939   check_integrity (q);
940   node = g_queue_peek_tail_link (q);
941   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
942   node = g_queue_peek_nth_link (q, g_queue_get_length (q));
943   g_assert (node == NULL);
944   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
945   g_assert (node->data == GINT_TO_POINTER (1234));
946   node = g_queue_pop_nth_link (q, g_queue_get_length (q));
947   g_assert (node == NULL);
948   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
949   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
950   
951   g_queue_free (q);
952
953   if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v')
954     random_test (strtol (args[2], NULL, 0));    
955   if (argc > 1)
956     random_test (strtol (args[1], NULL, 0));
957   else
958     random_test (time (0));  
959
960   return 0;
961 }
962