1 #undef G_DISABLE_ASSERT
13 check_integrity (GQueue *queue)
21 g_assert (queue->length < 4000000000u);
23 g_assert (g_queue_get_length (queue) == queue->length);
26 g_assert (!queue->tail);
28 g_assert (!queue->head);
32 for (list = queue->head; list != NULL; list = list->next)
38 g_assert (n == queue->length);
39 g_assert (last == queue->tail);
43 for (list = queue->tail; list != NULL; list = list->prev)
49 g_assert (n == queue->length);
50 g_assert (last == queue->head);
53 for (list = queue->head; list != NULL; list = list->next)
54 links = g_list_prepend (links, list);
57 for (list = queue->tail; list != NULL; list = list->prev)
59 g_assert (list == link->data);
65 for (list = queue->tail; list != NULL; list = list->prev)
66 links = g_list_prepend (links, list);
69 for (list = queue->head; list != NULL; list = list->next)
71 g_assert (list == link->data);
80 return g_random_int_range (0, 2);
84 check_max (gpointer elm, gpointer user_data)
86 gint *best = user_data;
87 gint element = GPOINTER_TO_INT (elm);
94 check_min (gpointer elm, gpointer user_data)
96 gint *best = user_data;
97 gint element = GPOINTER_TO_INT (elm);
104 find_min (GQueue *queue)
108 g_queue_foreach (queue, check_min, &min);
114 find_max (GQueue *queue)
118 g_queue_foreach (queue, check_max, &max);
124 delete_elm (gpointer elm, gpointer user_data)
126 g_queue_remove ((GQueue *)user_data, elm);
127 check_integrity ((GQueue *)user_data);
131 delete_all (GQueue *queue)
133 g_queue_foreach (queue, delete_elm, queue);
137 compare_int (gconstpointer a, gconstpointer b, gpointer data)
139 int ai = GPOINTER_TO_INT (a);
140 int bi = GPOINTER_TO_INT (b);
151 get_random_position (GQueue *queue, gboolean allow_offlist)
154 enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
157 where = g_random_int_range (OFF_QUEUE, LAST);
159 where = g_random_int_range (HEAD, LAST);
175 n = queue->length - 1;
179 if (queue->length == 0)
182 n = g_random_int_range (0, queue->length);
186 g_assert_not_reached();
196 random_test (int seed)
199 IS_EMPTY, GET_LENGTH, REVERSE, COPY,
200 FOREACH, FIND, FIND_CUSTOM, SORT,
201 PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
202 POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
203 PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
204 INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
205 PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
206 POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
207 LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
210 #define N_ITERATIONS 500000
213 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
215 typedef struct QueueInfo QueueInfo;
226 QueueInfo queues[N_QUEUES];
228 g_print ("seed: %d\n", seed);
229 g_random_set_seed (seed);
231 for (i = 0; i < N_QUEUES; ++i)
233 queues[i].queue = g_queue_new ();
234 queues[i].head = NULL;
235 queues[i].tail = NULL;
236 queues[i].length = 0;
239 for (i = 0; i < N_ITERATIONS; ++i)
242 QueueInfo *qinf = RANDOM_QUEUE();
243 GQueue *q = qinf->queue;
244 op = g_random_int_range (IS_EMPTY, LAST_OP);
246 g_assert (qinf->head == q->head);
247 g_assert (qinf->tail == q->tail);
248 g_assert (qinf->length == q->length);
254 if (g_queue_is_empty (qinf->queue))
256 g_assert (q->head == NULL);
257 g_assert (q->tail == NULL);
258 g_assert (q->length == 0);
264 g_assert (q->length > 0);
272 l = g_queue_get_length (q);
274 g_assert (qinf->length == q->length);
275 g_assert (qinf->length == l);
280 g_assert (qinf->tail == q->head);
281 g_assert (qinf->head == q->tail);
282 g_assert (qinf->length == q->length);
283 qinf->tail = q->tail;
284 qinf->head = q->head;
288 QueueInfo *random_queue = RANDOM_QUEUE();
289 GQueue *new_queue = g_queue_copy (random_queue->queue);
291 g_queue_free (qinf->queue);
292 q = qinf->queue = new_queue;
293 qinf->head = new_queue->head;
294 qinf->tail = g_list_last (new_queue->head);
295 qinf->length = new_queue->length;
306 gboolean find_existing = rnd_bool ();
307 int first = find_max (q);
308 int second = find_min (q);
311 find_existing = FALSE;
320 g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
321 g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
325 g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
326 g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
334 if (!g_queue_is_empty (q))
336 int max = find_max (q);
337 int min = find_min (q);
338 g_queue_remove_all (q, GINT_TO_POINTER (max));
340 g_queue_remove_all (q, GINT_TO_POINTER (min));
342 g_queue_push_head (q, GINT_TO_POINTER (max));
344 g_queue_push_head (q, GINT_TO_POINTER (min));
345 qinf->length = q->length;
350 g_queue_sort (q, compare_int, NULL);
354 qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
355 qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
357 g_assert (qinf->tail == q->tail);
362 int x = g_random_int_range (0, 435435);
363 g_queue_push_head (q, GINT_TO_POINTER (x));
365 qinf->tail = qinf->head = q->head;
367 qinf->head = qinf->head->prev;
373 int x = g_random_int_range (0, 236546);
374 g_queue_push_tail (q, GINT_TO_POINTER (x));
376 qinf->tail = qinf->head = q->head;
378 qinf->tail = qinf->tail->next;
384 int pos = get_random_position (q, TRUE);
385 int x = g_random_int_range (0, 236546);
386 g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
387 if (qinf->head && qinf->head->prev)
388 qinf->head = qinf->head->prev;
390 qinf->head = q->head;
391 if (qinf->tail && qinf->tail->next)
392 qinf->tail = qinf->tail->next;
394 qinf->tail = g_list_last (qinf->head);
400 qinf->head = qinf->head->next;
403 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
404 g_queue_pop_head (q);
408 qinf->tail = qinf->tail->prev;
411 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
412 g_queue_pop_tail (q);
415 if (!g_queue_is_empty (q))
417 int n = get_random_position (q, TRUE);
418 gpointer elm = g_queue_peek_nth (q, n);
420 if (n == q->length - 1)
421 qinf->tail = qinf->tail->prev;
424 qinf->head = qinf->head->next;
426 if (n >= 0 && n < q->length)
429 g_assert (elm == g_queue_pop_nth (q, n));
434 g_assert (qinf->head->data == g_queue_peek_head (q));
436 g_assert (g_queue_peek_head (q) == NULL);
440 g_assert (qinf->tail->data == g_queue_peek_tail (q));
442 g_assert (g_queue_peek_tail (q) == NULL);
445 if (g_queue_is_empty (q))
447 for (j = -10; j < 10; ++j)
448 g_assert (g_queue_peek_nth (q, j) == NULL);
453 int n = get_random_position (q, TRUE);
454 if (n < 0 || n >= q->length)
456 g_assert (g_queue_peek_nth (q, n) == NULL);
461 for (j = 0; j < n; ++j)
464 g_assert (list->data == g_queue_peek_nth (q, n));
471 int x = g_random_int_range (0, 386538);
475 g_queue_remove_all (q, GINT_TO_POINTER (x));
477 g_queue_push_tail (q, GINT_TO_POINTER (x));
479 g_queue_sort (q, compare_int, NULL);
483 for (list = q->head; list != NULL; list = list->next)
485 if (list->data == GINT_TO_POINTER (x))
490 g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
491 g_queue_link_index (q, list));
492 g_assert (g_queue_link_index (q, list) == n);
494 qinf->head = q->head;
495 qinf->tail = q->tail;
496 qinf->length = q->length;
500 if (!g_queue_is_empty (q))
501 g_queue_remove (q, qinf->tail->data);
502 if (!g_queue_is_empty (q))
503 g_queue_remove (q, qinf->head->data);
504 if (!g_queue_is_empty (q))
505 g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
507 qinf->head = q->head;
508 qinf->tail = q->tail;
509 qinf->length = q->length;
512 if (!g_queue_is_empty (q))
513 g_queue_remove_all (q, qinf->tail->data);
514 if (!g_queue_is_empty (q))
515 g_queue_remove_all (q, qinf->head->data);
516 if (!g_queue_is_empty (q))
517 g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
519 qinf->head = q->head;
520 qinf->tail = q->tail;
521 qinf->length = q->length;
524 if (!g_queue_is_empty (q))
526 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
528 g_queue_insert_before (q, qinf->tail, x);
529 g_queue_insert_before (q, qinf->head, x);
530 g_queue_insert_before (q, g_queue_find (q, x), x);
532 qinf->head = q->head;
533 qinf->tail = q->tail;
534 qinf->length = q->length;
537 if (!g_queue_is_empty (q))
539 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
541 g_queue_insert_after (q, qinf->tail, x);
542 g_queue_insert_after (q, qinf->head, x);
543 g_queue_insert_after (q, g_queue_find (q, x), x);
545 qinf->head = q->head;
546 qinf->tail = q->tail;
547 qinf->length = q->length;
551 int max = find_max (q);
552 int min = find_min (q);
554 if (g_queue_is_empty (q))
560 g_queue_sort (q, compare_int, NULL);
562 g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
564 g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
565 g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
567 g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
568 qinf->head = q->head;
569 qinf->tail = q->tail;
570 qinf->length = q->length;
575 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
576 g_queue_push_head_link (q, link);
585 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
586 g_queue_push_tail_link (q, link);
595 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
596 gint n = get_random_position (q, TRUE);
597 g_queue_push_nth_link (q, n, link);
599 if (qinf->head && qinf->head->prev)
600 qinf->head = qinf->head->prev;
602 qinf->head = q->head;
603 if (qinf->tail && qinf->tail->next)
604 qinf->tail = qinf->tail->next;
606 qinf->tail = g_list_last (qinf->head);
611 if (!g_queue_is_empty (q))
613 qinf->head = qinf->head->next;
617 g_list_free (g_queue_pop_head_link (q));
621 if (!g_queue_is_empty (q))
623 qinf->tail = qinf->tail->prev;
627 g_list_free (g_queue_pop_tail_link (q));
631 if (g_queue_is_empty (q))
632 g_assert (g_queue_pop_nth_link (q, 200) == NULL);
635 int n = get_random_position (q, FALSE);
637 if (n == g_queue_get_length (q) - 1)
638 qinf->tail = qinf->tail->prev;
641 qinf->head = qinf->head->next;
645 g_list_free (g_queue_pop_nth_link (q, n));
649 if (g_queue_is_empty (q))
650 g_assert (g_queue_peek_head_link (q) == NULL);
652 g_assert (g_queue_peek_head_link (q) == qinf->head);
655 if (g_queue_is_empty (q))
656 g_assert (g_queue_peek_tail_link (q) == NULL);
658 g_assert (g_queue_peek_tail_link (q) == qinf->tail);
661 if (g_queue_is_empty(q))
662 g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
665 gint n = get_random_position (q, FALSE);
669 for (j = 0; j < n; ++j)
672 g_assert (g_queue_peek_nth_link (q, n) == link);
676 if (!g_queue_is_empty (q))
678 gint n = g_random_int_range (0, g_queue_get_length (q));
682 for (j = 0; j < n; ++j)
685 g_queue_unlink (q, link);
690 qinf->head = q->head;
691 qinf->tail = q->tail;
696 if (!g_queue_is_empty (q))
698 gint n = g_random_int_range (0, g_queue_get_length (q));
702 for (j = 0; j < n; ++j)
705 g_queue_delete_link (q, link);
708 qinf->head = q->head;
709 qinf->tail = q->tail;
715 g_assert_not_reached();
719 if (qinf->head != q->head ||
720 qinf->tail != q->tail ||
721 qinf->length != q->length)
722 g_print ("op: %d\n", op);
724 g_assert (qinf->head == q->head);
725 g_assert (qinf->tail == q->tail);
726 g_assert (qinf->length == q->length);
728 for (j = 0; j < N_QUEUES; ++j)
729 check_integrity (queues[j].queue);
732 for (i = 0; i < N_QUEUES; ++i)
733 g_queue_free (queues[i].queue);
737 remove_item (gpointer data, gpointer q)
741 g_queue_remove (queue, data);
744 int main(int argc, gchar *args[])
753 g_assert (g_queue_is_empty (q) == TRUE);
755 g_queue_push_head (q, GINT_TO_POINTER (2));
757 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
759 g_assert (g_queue_is_empty (q) == FALSE);
761 g_assert (g_list_length (q->head) == 1);
762 g_assert (q->head == q->tail);
763 g_queue_push_head (q, GINT_TO_POINTER (1));
765 g_assert (q->head->next == q->tail);
766 g_assert (q->tail->prev == q->head);
767 g_assert (g_list_length (q->head) == 2);
769 g_assert (q->tail->data == GINT_TO_POINTER (2));
770 g_assert (q->head->data == GINT_TO_POINTER (1));
772 g_queue_push_tail (q, GINT_TO_POINTER (3));
773 g_assert (g_list_length (q->head) == 3);
774 g_assert (q->head->data == GINT_TO_POINTER (1));
775 g_assert (q->head->next->data == GINT_TO_POINTER (2));
776 g_assert (q->head->next->next == q->tail);
777 g_assert (q->head->next == q->tail->prev);
778 g_assert (q->tail->data == GINT_TO_POINTER (3));
779 g_queue_push_tail (q, GINT_TO_POINTER (4));
781 g_assert (g_list_length (q->head) == 4);
782 g_assert (q->head->data == GINT_TO_POINTER (1));
783 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
784 g_queue_push_tail (q, GINT_TO_POINTER (5));
786 g_assert (g_list_length (q->head) == 5);
788 g_assert (g_queue_is_empty (q) == FALSE);
791 g_assert (q->length == 5);
792 g_assert (q->head->prev == NULL);
793 g_assert (q->head->data == GINT_TO_POINTER (1));
794 g_assert (q->head->next->data == GINT_TO_POINTER (2));
795 g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
796 g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
797 g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
798 g_assert (q->head->next->next->next->next->next == NULL);
799 g_assert (q->head->next->next->next->next == q->tail);
800 g_assert (q->tail->data == GINT_TO_POINTER (5));
801 g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
802 g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
803 g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
804 g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
805 g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
806 g_assert (q->tail->prev->prev->prev->prev == q->head);
807 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
808 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
810 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
812 g_assert (g_list_length (q->head) == 4 && q->length == 4);
813 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
815 g_assert (g_list_length (q->head) == 3);
816 g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
818 g_assert (g_list_length (q->head) == 2);
819 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
821 g_assert (g_list_length (q->head) == 1);
822 g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
824 g_assert (g_list_length (q->head) == 0);
825 g_assert (g_queue_pop_tail (q) == NULL);
827 g_assert (g_list_length (q->head) == 0);
828 g_assert (g_queue_pop_head (q) == NULL);
830 g_assert (g_list_length (q->head) == 0);
832 g_assert (g_queue_is_empty (q) == TRUE);
835 /************************/
837 g_queue_push_head (q, GINT_TO_POINTER (1));
839 g_assert (g_list_length (q->head) == 1 && 1 == q->length);
840 g_queue_push_head (q, GINT_TO_POINTER (2));
842 g_assert (g_list_length (q->head) == 2 && 2 == q->length);
843 g_queue_push_head (q, GINT_TO_POINTER (3));
845 g_assert (g_list_length (q->head) == 3 && 3 == q->length);
846 g_queue_push_head (q, GINT_TO_POINTER (4));
848 g_assert (g_list_length (q->head) == 4 && 4 == q->length);
849 g_queue_push_head (q, GINT_TO_POINTER (5));
851 g_assert (g_list_length (q->head) == 5 && 5 == q->length);
853 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
855 g_assert (g_list_length (q->head) == 4);
857 g_assert (node == g_queue_pop_tail_link (q));
859 g_assert (g_list_length (q->head) == 3);
860 data = q->head->data;
861 g_assert (data == g_queue_pop_head (q));
863 g_assert (g_list_length (q->head) == 2);
864 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
866 g_assert (g_list_length (q->head) == 1);
867 g_assert (q->head == q->tail);
868 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
870 g_assert (g_list_length (q->head) == 0);
871 g_assert (g_queue_pop_head (q) == NULL);
873 g_assert (g_queue_pop_head_link (q) == NULL);
875 g_assert (g_list_length (q->head) == 0);
876 g_assert (g_queue_pop_tail_link (q) == NULL);
878 g_assert (g_list_length (q->head) == 0);
883 g_assert (g_list_length (q->head) == 0);
885 q2 = g_queue_copy (q);
887 check_integrity (q2);
888 g_assert (g_list_length (q->head) == 0);
889 g_assert (g_list_length (q2->head) == 0);
890 g_queue_sort (q, compare_int, NULL);
891 check_integrity (q2);
893 g_queue_sort (q2, compare_int, NULL);
894 check_integrity (q2);
897 for (i = 0; i < 200; ++i)
899 g_queue_push_nth (q, GINT_TO_POINTER (i), i);
900 g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
902 check_integrity (q2);
905 for (i = 0; i < 200; ++i)
907 g_queue_remove (q, GINT_TO_POINTER (i));
909 check_integrity (q2);
912 for (i = 0; i < 200; ++i)
914 GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
916 g_queue_push_nth_link (q, i, l);
918 check_integrity (q2);
921 check_integrity (q2);
925 q2 = g_queue_copy (q);
927 g_queue_foreach (q2, remove_item, q2);
928 check_integrity (q2);
934 random_test (strtol (args[1], NULL, 0));
936 random_test (time (0));