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
check_integrity(GQueue * queue)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
rnd_bool(void)79 rnd_bool (void)
80 {
81 return g_random_int_range (0, 2);
82 }
83
84 static void
check_max(gpointer elm,gpointer user_data)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
check_min(gpointer elm,gpointer user_data)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
find_min(GQueue * queue)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
find_max(GQueue * queue)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
delete_elm(gpointer elm,gpointer user_data)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
delete_all(GQueue * queue)132 delete_all (GQueue *queue)
133 {
134 g_queue_foreach (queue, delete_elm, queue);
135 }
136
137 static int
compare_int(gconstpointer a,gconstpointer b,gpointer data)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
get_random_position(GQueue * queue,gboolean allow_offlist)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
random_test(int seed)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
remove_item(gpointer data,gpointer q)740 remove_item (gpointer data, gpointer q)
741 {
742 GQueue *queue = q;
743
744 g_queue_remove (queue, data);
745 }
746
main(int argc,gchar * args[])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
963