1 #undef G_DISABLE_ASSERT
12 static gboolean verbose = FALSE;
15 check_integrity (GQueue *queue)
23 g_assert (queue->length < 4000000000u);
25 g_assert (g_queue_get_length (queue) == queue->length);
28 g_assert (!queue->tail);
30 g_assert (!queue->head);
34 for (list = queue->head; list != NULL; list = list->next)
40 g_assert (n == queue->length);
41 g_assert (last == queue->tail);
45 for (list = queue->tail; list != NULL; list = list->prev)
51 g_assert (n == queue->length);
52 g_assert (last == queue->head);
55 for (list = queue->head; list != NULL; list = list->next)
56 links = g_list_prepend (links, list);
59 for (list = queue->tail; list != NULL; list = list->prev)
61 g_assert (list == link->data);
67 for (list = queue->tail; list != NULL; list = list->prev)
68 links = g_list_prepend (links, list);
71 for (list = queue->head; list != NULL; list = list->next)
73 g_assert (list == link->data);
82 return g_random_int_range (0, 2);
86 check_max (gpointer elm, gpointer user_data)
88 gint *best = user_data;
89 gint element = GPOINTER_TO_INT (elm);
96 check_min (gpointer elm, gpointer user_data)
98 gint *best = user_data;
99 gint element = GPOINTER_TO_INT (elm);
106 find_min (GQueue *queue)
110 g_queue_foreach (queue, check_min, &min);
116 find_max (GQueue *queue)
120 g_queue_foreach (queue, check_max, &max);
126 delete_elm (gpointer elm, gpointer user_data)
128 g_queue_remove ((GQueue *)user_data, elm);
129 check_integrity ((GQueue *)user_data);
133 delete_all (GQueue *queue)
135 g_queue_foreach (queue, delete_elm, queue);
139 compare_int (gconstpointer a, gconstpointer b, gpointer data)
141 int ai = GPOINTER_TO_INT (a);
142 int bi = GPOINTER_TO_INT (b);
153 get_random_position (GQueue *queue, gboolean allow_offlist)
156 enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
159 where = g_random_int_range (OFF_QUEUE, LAST);
161 where = g_random_int_range (HEAD, LAST);
177 n = queue->length - 1;
181 if (queue->length == 0)
184 n = g_random_int_range (0, queue->length);
188 g_assert_not_reached();
198 random_test (int seed)
201 IS_EMPTY, GET_LENGTH, REVERSE, COPY,
202 FOREACH, FIND, FIND_CUSTOM, SORT,
203 PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
204 POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
205 PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
206 INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
207 PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
208 POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
209 LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
212 #define N_ITERATIONS 500000
215 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
217 typedef struct QueueInfo QueueInfo;
228 QueueInfo queues[N_QUEUES];
231 g_print ("seed: %d\n", seed);
233 g_random_set_seed (seed);
235 for (i = 0; i < N_QUEUES; ++i)
237 queues[i].queue = g_queue_new ();
238 queues[i].head = NULL;
239 queues[i].tail = NULL;
240 queues[i].length = 0;
243 for (i = 0; i < N_ITERATIONS; ++i)
246 QueueInfo *qinf = RANDOM_QUEUE();
247 GQueue *q = qinf->queue;
248 op = g_random_int_range (IS_EMPTY, LAST_OP);
250 g_assert (qinf->head == q->head);
251 g_assert (qinf->tail == q->tail);
252 g_assert (qinf->length == q->length);
258 if (g_queue_is_empty (qinf->queue))
260 g_assert (q->head == NULL);
261 g_assert (q->tail == NULL);
262 g_assert (q->length == 0);
268 g_assert (q->length > 0);
276 l = g_queue_get_length (q);
278 g_assert (qinf->length == q->length);
279 g_assert (qinf->length == l);
284 g_assert (qinf->tail == q->head);
285 g_assert (qinf->head == q->tail);
286 g_assert (qinf->length == q->length);
287 qinf->tail = q->tail;
288 qinf->head = q->head;
292 QueueInfo *random_queue = RANDOM_QUEUE();
293 GQueue *new_queue = g_queue_copy (random_queue->queue);
295 g_queue_free (qinf->queue);
296 q = qinf->queue = new_queue;
297 qinf->head = new_queue->head;
298 qinf->tail = g_list_last (new_queue->head);
299 qinf->length = new_queue->length;
310 gboolean find_existing = rnd_bool ();
311 int first = find_max (q);
312 int second = find_min (q);
315 find_existing = FALSE;
324 g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
325 g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
329 g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
330 g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
338 if (!g_queue_is_empty (q))
340 int max = find_max (q);
341 int min = find_min (q);
342 g_queue_remove_all (q, GINT_TO_POINTER (max));
344 g_queue_remove_all (q, GINT_TO_POINTER (min));
346 g_queue_push_head (q, GINT_TO_POINTER (max));
348 g_queue_push_head (q, GINT_TO_POINTER (min));
349 qinf->length = q->length;
354 g_queue_sort (q, compare_int, NULL);
358 qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
359 qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
361 g_assert (qinf->tail == q->tail);
366 int x = g_random_int_range (0, 435435);
367 g_queue_push_head (q, GINT_TO_POINTER (x));
369 qinf->tail = qinf->head = q->head;
371 qinf->head = qinf->head->prev;
377 int x = g_random_int_range (0, 236546);
378 g_queue_push_tail (q, GINT_TO_POINTER (x));
380 qinf->tail = qinf->head = q->head;
382 qinf->tail = qinf->tail->next;
388 int pos = get_random_position (q, TRUE);
389 int x = g_random_int_range (0, 236546);
390 g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
391 if (qinf->head && qinf->head->prev)
392 qinf->head = qinf->head->prev;
394 qinf->head = q->head;
395 if (qinf->tail && qinf->tail->next)
396 qinf->tail = qinf->tail->next;
398 qinf->tail = g_list_last (qinf->head);
404 qinf->head = qinf->head->next;
407 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
408 g_queue_pop_head (q);
412 qinf->tail = qinf->tail->prev;
415 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
416 g_queue_pop_tail (q);
419 if (!g_queue_is_empty (q))
421 int n = get_random_position (q, TRUE);
422 gpointer elm = g_queue_peek_nth (q, n);
424 if (n == q->length - 1)
425 qinf->tail = qinf->tail->prev;
428 qinf->head = qinf->head->next;
430 if (n >= 0 && n < q->length)
433 g_assert (elm == g_queue_pop_nth (q, n));
438 g_assert (qinf->head->data == g_queue_peek_head (q));
440 g_assert (g_queue_peek_head (q) == NULL);
444 g_assert (qinf->tail->data == g_queue_peek_tail (q));
446 g_assert (g_queue_peek_tail (q) == NULL);
449 if (g_queue_is_empty (q))
451 for (j = -10; j < 10; ++j)
452 g_assert (g_queue_peek_nth (q, j) == NULL);
457 int n = get_random_position (q, TRUE);
458 if (n < 0 || n >= q->length)
460 g_assert (g_queue_peek_nth (q, n) == NULL);
465 for (j = 0; j < n; ++j)
468 g_assert (list->data == g_queue_peek_nth (q, n));
475 int x = g_random_int_range (0, 386538);
479 g_queue_remove_all (q, GINT_TO_POINTER (x));
481 g_queue_push_tail (q, GINT_TO_POINTER (x));
483 g_queue_sort (q, compare_int, NULL);
487 for (list = q->head; list != NULL; list = list->next)
489 if (list->data == GINT_TO_POINTER (x))
494 g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
495 g_queue_link_index (q, list));
496 g_assert (g_queue_link_index (q, list) == n);
498 qinf->head = q->head;
499 qinf->tail = q->tail;
500 qinf->length = q->length;
504 if (!g_queue_is_empty (q))
505 g_queue_remove (q, qinf->tail->data);
506 if (!g_queue_is_empty (q))
507 g_queue_remove (q, qinf->head->data);
508 if (!g_queue_is_empty (q))
509 g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
511 qinf->head = q->head;
512 qinf->tail = q->tail;
513 qinf->length = q->length;
516 if (!g_queue_is_empty (q))
517 g_queue_remove_all (q, qinf->tail->data);
518 if (!g_queue_is_empty (q))
519 g_queue_remove_all (q, qinf->head->data);
520 if (!g_queue_is_empty (q))
521 g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
523 qinf->head = q->head;
524 qinf->tail = q->tail;
525 qinf->length = q->length;
528 if (!g_queue_is_empty (q))
530 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
532 g_queue_insert_before (q, qinf->tail, x);
533 g_queue_insert_before (q, qinf->head, x);
534 g_queue_insert_before (q, g_queue_find (q, x), x);
536 qinf->head = q->head;
537 qinf->tail = q->tail;
538 qinf->length = q->length;
541 if (!g_queue_is_empty (q))
543 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
545 g_queue_insert_after (q, qinf->tail, x);
546 g_queue_insert_after (q, qinf->head, x);
547 g_queue_insert_after (q, g_queue_find (q, x), x);
549 qinf->head = q->head;
550 qinf->tail = q->tail;
551 qinf->length = q->length;
555 int max = find_max (q);
556 int min = find_min (q);
558 if (g_queue_is_empty (q))
564 g_queue_sort (q, compare_int, NULL);
566 g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
568 g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
569 g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
571 g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
572 qinf->head = q->head;
573 qinf->tail = q->tail;
574 qinf->length = q->length;
579 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
580 g_queue_push_head_link (q, link);
589 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
590 g_queue_push_tail_link (q, link);
599 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
600 gint n = get_random_position (q, TRUE);
601 g_queue_push_nth_link (q, n, link);
603 if (qinf->head && qinf->head->prev)
604 qinf->head = qinf->head->prev;
606 qinf->head = q->head;
607 if (qinf->tail && qinf->tail->next)
608 qinf->tail = qinf->tail->next;
610 qinf->tail = g_list_last (qinf->head);
615 if (!g_queue_is_empty (q))
617 qinf->head = qinf->head->next;
621 g_list_free (g_queue_pop_head_link (q));
625 if (!g_queue_is_empty (q))
627 qinf->tail = qinf->tail->prev;
631 g_list_free (g_queue_pop_tail_link (q));
635 if (g_queue_is_empty (q))
636 g_assert (g_queue_pop_nth_link (q, 200) == NULL);
639 int n = get_random_position (q, FALSE);
641 if (n == g_queue_get_length (q) - 1)
642 qinf->tail = qinf->tail->prev;
645 qinf->head = qinf->head->next;
649 g_list_free (g_queue_pop_nth_link (q, n));
653 if (g_queue_is_empty (q))
654 g_assert (g_queue_peek_head_link (q) == NULL);
656 g_assert (g_queue_peek_head_link (q) == qinf->head);
659 if (g_queue_is_empty (q))
660 g_assert (g_queue_peek_tail_link (q) == NULL);
662 g_assert (g_queue_peek_tail_link (q) == qinf->tail);
665 if (g_queue_is_empty(q))
666 g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
669 gint n = get_random_position (q, FALSE);
673 for (j = 0; j < n; ++j)
676 g_assert (g_queue_peek_nth_link (q, n) == link);
680 if (!g_queue_is_empty (q))
682 gint n = g_random_int_range (0, g_queue_get_length (q));
686 for (j = 0; j < n; ++j)
689 g_queue_unlink (q, link);
694 qinf->head = q->head;
695 qinf->tail = q->tail;
700 if (!g_queue_is_empty (q))
702 gint n = g_random_int_range (0, g_queue_get_length (q));
706 for (j = 0; j < n; ++j)
709 g_queue_delete_link (q, link);
712 qinf->head = q->head;
713 qinf->tail = q->tail;
719 g_assert_not_reached();
723 if (qinf->head != q->head ||
724 qinf->tail != q->tail ||
725 qinf->length != q->length)
726 g_print ("op: %d\n", op);
728 g_assert (qinf->head == q->head);
729 g_assert (qinf->tail == q->tail);
730 g_assert (qinf->length == q->length);
732 for (j = 0; j < N_QUEUES; ++j)
733 check_integrity (queues[j].queue);
736 for (i = 0; i < N_QUEUES; ++i)
737 g_queue_free (queues[i].queue);
741 remove_item (gpointer data, gpointer q)
745 g_queue_remove (queue, data);
748 int main(int argc, gchar *args[])
755 if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v')
760 g_assert (g_queue_is_empty (q) == TRUE);
762 g_queue_push_head (q, GINT_TO_POINTER (2));
764 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
766 g_assert (g_queue_is_empty (q) == FALSE);
768 g_assert (g_list_length (q->head) == 1);
769 g_assert (q->head == q->tail);
770 g_queue_push_head (q, GINT_TO_POINTER (1));
772 g_assert (q->head->next == q->tail);
773 g_assert (q->tail->prev == q->head);
774 g_assert (g_list_length (q->head) == 2);
776 g_assert (q->tail->data == GINT_TO_POINTER (2));
777 g_assert (q->head->data == GINT_TO_POINTER (1));
779 g_queue_push_tail (q, GINT_TO_POINTER (3));
780 g_assert (g_list_length (q->head) == 3);
781 g_assert (q->head->data == GINT_TO_POINTER (1));
782 g_assert (q->head->next->data == GINT_TO_POINTER (2));
783 g_assert (q->head->next->next == q->tail);
784 g_assert (q->head->next == q->tail->prev);
785 g_assert (q->tail->data == GINT_TO_POINTER (3));
786 g_queue_push_tail (q, GINT_TO_POINTER (4));
788 g_assert (g_list_length (q->head) == 4);
789 g_assert (q->head->data == GINT_TO_POINTER (1));
790 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
791 g_queue_push_tail (q, GINT_TO_POINTER (5));
793 g_assert (g_list_length (q->head) == 5);
795 g_assert (g_queue_is_empty (q) == FALSE);
798 g_assert (q->length == 5);
799 g_assert (q->head->prev == NULL);
800 g_assert (q->head->data == GINT_TO_POINTER (1));
801 g_assert (q->head->next->data == GINT_TO_POINTER (2));
802 g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
803 g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
804 g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
805 g_assert (q->head->next->next->next->next->next == NULL);
806 g_assert (q->head->next->next->next->next == q->tail);
807 g_assert (q->tail->data == GINT_TO_POINTER (5));
808 g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
809 g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
810 g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
811 g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
812 g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
813 g_assert (q->tail->prev->prev->prev->prev == q->head);
814 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
815 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
817 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
819 g_assert (g_list_length (q->head) == 4 && q->length == 4);
820 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
822 g_assert (g_list_length (q->head) == 3);
823 g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
825 g_assert (g_list_length (q->head) == 2);
826 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
828 g_assert (g_list_length (q->head) == 1);
829 g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
831 g_assert (g_list_length (q->head) == 0);
832 g_assert (g_queue_pop_tail (q) == NULL);
834 g_assert (g_list_length (q->head) == 0);
835 g_assert (g_queue_pop_head (q) == NULL);
837 g_assert (g_list_length (q->head) == 0);
839 g_assert (g_queue_is_empty (q) == TRUE);
842 /************************/
844 g_queue_push_head (q, GINT_TO_POINTER (1));
846 g_assert (g_list_length (q->head) == 1 && 1 == q->length);
847 g_queue_push_head (q, GINT_TO_POINTER (2));
849 g_assert (g_list_length (q->head) == 2 && 2 == q->length);
850 g_queue_push_head (q, GINT_TO_POINTER (3));
852 g_assert (g_list_length (q->head) == 3 && 3 == q->length);
853 g_queue_push_head (q, GINT_TO_POINTER (4));
855 g_assert (g_list_length (q->head) == 4 && 4 == q->length);
856 g_queue_push_head (q, GINT_TO_POINTER (5));
858 g_assert (g_list_length (q->head) == 5 && 5 == q->length);
860 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
862 g_assert (g_list_length (q->head) == 4);
864 g_assert (node == g_queue_pop_tail_link (q));
866 g_assert (g_list_length (q->head) == 3);
867 data = q->head->data;
868 g_assert (data == g_queue_pop_head (q));
870 g_assert (g_list_length (q->head) == 2);
871 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
873 g_assert (g_list_length (q->head) == 1);
874 g_assert (q->head == q->tail);
875 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
877 g_assert (g_list_length (q->head) == 0);
878 g_assert (g_queue_pop_head (q) == NULL);
880 g_assert (g_queue_pop_head_link (q) == NULL);
882 g_assert (g_list_length (q->head) == 0);
883 g_assert (g_queue_pop_tail_link (q) == NULL);
885 g_assert (g_list_length (q->head) == 0);
890 g_assert (g_list_length (q->head) == 0);
892 q2 = g_queue_copy (q);
894 check_integrity (q2);
895 g_assert (g_list_length (q->head) == 0);
896 g_assert (g_list_length (q2->head) == 0);
897 g_queue_sort (q, compare_int, NULL);
898 check_integrity (q2);
900 g_queue_sort (q2, compare_int, NULL);
901 check_integrity (q2);
904 for (i = 0; i < 200; ++i)
906 g_queue_push_nth (q, GINT_TO_POINTER (i), i);
907 g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
909 check_integrity (q2);
912 for (i = 0; i < 200; ++i)
914 g_queue_remove (q, GINT_TO_POINTER (i));
916 check_integrity (q2);
919 for (i = 0; i < 200; ++i)
921 GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
923 g_queue_push_nth_link (q, i, l);
925 check_integrity (q2);
928 check_integrity (q2);
932 q2 = g_queue_copy (q);
934 g_queue_foreach (q2, remove_item, q2);
935 check_integrity (q2);
938 /* some checks for off by one errors */
939 g_queue_push_tail (q, GINT_TO_POINTER (1234));
941 node = g_queue_peek_tail_link (q);
942 g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
943 node = g_queue_peek_nth_link (q, g_queue_get_length (q));
944 g_assert (node == NULL);
945 node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
946 g_assert (node->data == GINT_TO_POINTER (1234));
947 node = g_queue_pop_nth_link (q, g_queue_get_length (q));
948 g_assert (node == NULL);
949 node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
950 g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
954 if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v')
955 random_test (strtol (args[2], NULL, 0));
957 random_test (strtol (args[1], NULL, 0));
959 random_test (time (0));