5 /* Keep this in sync with gsequence.c !!! */
6 typedef struct _GSequenceNode GSequenceNode;
10 GSequenceNode * end_node;
11 GDestroyNotify data_destroy_notify;
12 gboolean access_prohibited;
13 GSequence * real_sequence;
19 GSequenceNode * parent;
21 GSequenceNode * right;
26 get_priority (GSequenceNode *node)
28 guint key = GPOINTER_TO_UINT (node);
30 key = (key << 15) - key - 1;
31 key = key ^ (key >> 12);
32 key = key + (key << 2);
33 key = key ^ (key >> 4);
34 key = key + (key << 3) + (key << 11);
35 key = key ^ (key >> 16);
41 check_node (GSequenceNode *node)
45 g_assert (node->parent != node);
47 g_assert (node->parent->left == node || node->parent->right == node);
48 g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));
50 g_assert (get_priority (node) >= get_priority (node->left));
52 g_assert (get_priority (node) >= get_priority (node->right));
53 check_node (node->left);
54 check_node (node->right);
59 g_sequence_check (GSequence *seq)
61 GSequenceNode *node = seq->end_node;
71 g_assert (seq->end_node == node);
72 g_assert (node->data == seq);
78 NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,
81 GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
82 INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
83 SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
89 /* operations on GSequenceIter * */
90 ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
91 ITER_MOVE, ITER_GET_SEQUENCE,
94 ITER_COMPARE, RANGE_GET_MIDPOINT,
98 typedef struct SequenceInfo
101 GSequence * sequence;
111 void g_sequence_check (GSequence *sequence);
114 fix_pointer (gconstpointer data)
116 return (Item *)((char *)data - 1);
120 get_item (GSequenceIter *iter)
122 return fix_pointer (g_sequence_get (iter));
126 check_integrity (SequenceInfo *info)
132 g_sequence_check (info->sequence);
135 if (g_sequence_get_length (info->sequence) != info->n_items)
137 g_sequence_get_length (info->sequence), info->n_items);
139 g_assert (info->n_items == g_queue_get_length (info->queue));
140 g_assert (g_sequence_get_length (info->sequence) == info->n_items);
142 iter = g_sequence_get_begin_iter (info->sequence);
143 list = info->queue->head;
145 while (iter != g_sequence_get_end_iter (info->sequence))
148 g_assert (list->data == iter);
149 item = get_item (list->data);
150 g_assert (item->seq == info);
152 iter = g_sequence_iter_next (iter);
157 g_assert (info->n_items == g_queue_get_length (info->queue));
158 g_assert (g_sequence_get_length (info->sequence) == info->n_items);
162 new_item (SequenceInfo *seq)
164 Item *item = g_new (Item, 1);
167 item->number = g_random_int ();
169 /* There have been bugs in the past where the GSequence would
170 * dereference the user pointers. This will make sure such
171 * behavior causes crashes
173 return ((char *)item + 1);
177 free_item (gpointer data)
179 Item *item = fix_pointer (data);
180 item->seq->n_items--;
185 seq_foreach (gpointer data,
188 Item *item = fix_pointer (data);
189 GList **link = user_data;
192 g_assert (*link != NULL);
194 iter = (*link)->data;
196 g_assert (get_item (iter) == item);
198 item->number = g_random_int();
200 *link = (*link)->next;
204 simple_items_cmp (gconstpointer a,
208 const Item *item_a = fix_pointer (a);
209 const Item *item_b = fix_pointer (b);
211 if (item_a->number > item_b->number)
213 else if (item_a->number < item_b->number)
220 simple_iters_cmp (gconstpointer a,
224 GSequence *seq = data;
225 GSequenceIter *iter_a = (GSequenceIter *)a;
226 GSequenceIter *iter_b = (GSequenceIter *)b;
227 gpointer item_a = g_sequence_get (iter_a);
228 gpointer item_b = g_sequence_get (iter_b);
232 g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
233 g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
236 return simple_items_cmp (item_a, item_b, data);
240 compare_items (gconstpointer a,
244 const Item *item_a = fix_pointer (a);
245 const Item *item_b = fix_pointer (b);
247 if (item_a->number < item_b->number)
251 else if (item_a->number == item_b->number)
253 /* Force an arbitrary order on the items
254 * We have to do this, since g_queue_insert_sorted() and
255 * g_sequence_insert_sorted() do not agree on the exact
256 * position the item is inserted if the new item is
257 * equal to an existing one.
261 else if (item_a == item_b)
273 check_sorted (SequenceInfo *info)
277 GSequenceIter *last_iter;
279 check_integrity (info);
283 for (list = info->queue->head; list != NULL; list = list->next)
285 GSequenceIter *iter = list->data;
286 Item *item = get_item (iter);
288 g_assert (item->number >= last);
289 /* Check that the ordering is the same as that of the queue,
290 * ie. that the sort is stable
293 g_assert (iter == g_sequence_iter_next (last_iter));
301 compare_iters (gconstpointer a,
305 GSequence *seq = data;
306 GSequenceIter *iter_a = (GSequenceIter *)a;
307 GSequenceIter *iter_b = (GSequenceIter *)b;
308 /* compare_items() will fix up the pointers */
309 Item *item_a = g_sequence_get (iter_a);
310 Item *item_b = g_sequence_get (iter_b);
314 g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
315 g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
318 return compare_items (item_a, item_b, data);
321 /* A version of g_queue_link_index() that treats NULL as just
325 queue_link_index (SequenceInfo *seq, GList *link)
328 return g_queue_link_index (seq->queue, link);
330 return g_queue_get_length (seq->queue);
334 get_random_range (SequenceInfo *seq,
335 GSequenceIter **begin_iter,
336 GSequenceIter **end_iter,
340 int length = g_queue_get_length (seq->queue);
341 int b = g_random_int_range (0, length + 1);
342 int e = g_random_int_range (b, length + 1);
344 g_assert (length == g_sequence_get_length (seq->sequence));
347 *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);
349 *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);
351 *begin_link = g_queue_peek_nth_link (seq->queue, b);
353 *end_link = g_queue_peek_nth_link (seq->queue, e);
354 if (begin_iter && begin_link)
357 queue_link_index (seq, *begin_link) ==
358 g_sequence_iter_get_position (*begin_iter));
360 if (end_iter && end_link)
363 queue_link_index (seq, *end_link) ==
364 g_sequence_iter_get_position (*end_iter));
369 get_random_position (SequenceInfo *seq)
371 int length = g_queue_get_length (seq->queue);
373 g_assert (length == g_sequence_get_length (seq->sequence));
375 return g_random_int_range (-2, length + 5);
378 static GSequenceIter *
379 get_random_iter (SequenceInfo *seq,
383 int pos = get_random_position (seq);
385 *link = g_queue_peek_nth_link (seq->queue, pos);
386 iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
388 g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));
393 dump_info (SequenceInfo *seq)
399 iter = g_sequence_get_begin_iter (seq->sequence);
400 list = seq->queue->head;
402 while (iter != g_sequence_get_end_iter (seq->sequence))
404 Item *item = get_item (iter);
405 g_print ("%p %p %d\n", list->data, iter, item->number);
407 iter = g_sequence_iter_next (iter);
413 /* A version of g_queue_insert_before() that appends if link is NULL */
415 queue_insert_before (SequenceInfo *seq, GList *link, gpointer data)
418 g_queue_insert_before (seq->queue, link, data);
420 g_queue_push_tail (seq->queue, data);
424 run_random_tests (gconstpointer d)
426 guint32 seed = GPOINTER_TO_UINT (d);
427 #define N_ITERATIONS 60000
428 #define N_SEQUENCES 8
431 SequenceInfo sequences[N_SEQUENCES];
435 g_print (" seed: %u\n", seed);
438 g_random_set_seed (seed);
440 for (k = 0; k < N_SEQUENCES; ++k)
442 sequences[k].queue = g_queue_new ();
443 sequences[k].sequence = g_sequence_new (free_item);
444 sequences[k].n_items = 0;
447 #define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])
449 for (k = 0; k < N_ITERATIONS; ++k)
452 SequenceInfo *seq = RANDOM_SEQUENCE();
453 int op = g_random_int_range (0, N_OPS);
456 g_print ("%d on %p\n", op, seq);
464 g_queue_free (seq->queue);
465 g_sequence_free (seq->sequence);
467 g_assert (seq->n_items == 0);
469 seq->queue = g_queue_new ();
470 seq->sequence = g_sequence_new (free_item);
472 check_integrity (seq);
477 int slen = g_sequence_get_length (seq->sequence);
478 int qlen = g_queue_get_length (seq->queue);
480 g_assert (slen == qlen);
485 GList *link = seq->queue->head;
486 g_sequence_foreach (seq->sequence, seq_foreach, &link);
487 g_assert (link == NULL);
492 GSequenceIter *begin_iter, *end_iter;
493 GList *begin_link, *end_link;
495 get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
497 check_integrity (seq);
499 g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);
501 g_assert (begin_link == end_link);
508 g_sequence_sort (seq->sequence, compare_items, NULL);
509 g_queue_sort (seq->queue, compare_iters, NULL);
518 check_integrity (seq);
519 g_sequence_sort_iter (seq->sequence,
520 (GSequenceIterCompareFunc)compare_iters, seq->sequence);
521 g_queue_sort (seq->queue, compare_iters, NULL);
530 GSequenceIter *begin_iter;
531 GSequenceIter *end_iter;
532 GSequenceIter *penultimate_iter;
534 begin_iter = g_sequence_get_begin_iter (seq->sequence);
535 check_integrity (seq);
537 end_iter = g_sequence_get_end_iter (seq->sequence);
538 check_integrity (seq);
540 penultimate_iter = g_sequence_iter_prev (end_iter);
541 check_integrity (seq);
543 if (g_sequence_get_length (seq->sequence) > 0)
545 g_assert (seq->queue->head);
546 g_assert (seq->queue->head->data == begin_iter);
547 g_assert (seq->queue->tail);
548 g_assert (seq->queue->tail->data == penultimate_iter);
552 g_assert (penultimate_iter == end_iter);
553 g_assert (begin_iter == end_iter);
554 g_assert (penultimate_iter == begin_iter);
555 g_assert (seq->queue->head == NULL);
556 g_assert (seq->queue->tail == NULL);
560 case GET_ITER_AT_POS:
564 g_assert (g_queue_get_length (seq->queue) == g_sequence_get_length (seq->sequence));
566 for (i = 0; i < 10; ++i)
568 int pos = get_random_position (seq);
569 GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
570 GList *link = g_queue_peek_nth_link (seq->queue, pos);
571 check_integrity (seq);
572 if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
574 g_assert (iter == g_sequence_get_end_iter (seq->sequence));
575 g_assert (link == NULL);
580 g_assert (link->data == iter);
587 for (i = 0; i < 10; ++i)
589 GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
590 g_queue_push_tail (seq->queue, iter);
596 for (i = 0; i < 10; ++i)
598 GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
599 g_queue_push_head (seq->queue, iter);
605 for (i = 0; i < 10; ++i)
608 GSequenceIter *iter = get_random_iter (seq, &link);
609 GSequenceIter *new_iter;
610 check_integrity (seq);
612 new_iter = g_sequence_insert_before (iter, new_item (seq));
614 queue_insert_before (seq, link, new_iter);
620 GList *link1, *link2;
621 SequenceInfo *seq1 = RANDOM_SEQUENCE();
622 SequenceInfo *seq2 = RANDOM_SEQUENCE();
623 GSequenceIter *iter1 = get_random_iter (seq1, &link1);
624 GSequenceIter *iter2 = get_random_iter (seq2, &link2);
626 if (!g_sequence_iter_is_end (iter1))
628 g_sequence_move (iter1, iter2);
631 g_assert (g_sequence_iter_is_end (iter2));
633 queue_insert_before (seq2, link2, link1->data);
635 g_queue_delete_link (seq1->queue, link1);
637 get_item (iter1)->seq = seq2;
643 check_integrity (seq);
645 iter1 = get_random_iter (seq, NULL);
647 /* Moving an iter to itself should have no effect */
648 if (!g_sequence_iter_is_end (iter1))
649 g_sequence_move (iter1, iter1);
654 GList *link1, *link2;
655 SequenceInfo *seq1 = RANDOM_SEQUENCE();
656 SequenceInfo *seq2 = RANDOM_SEQUENCE();
657 GSequenceIter *iter1 = get_random_iter (seq1, &link1);
658 GSequenceIter *iter2 = get_random_iter (seq2, &link2);
660 if (!g_sequence_iter_is_end (iter1) &&
661 !g_sequence_iter_is_end (iter2))
665 g_sequence_swap (iter1, iter2);
667 get_item (iter1)->seq = seq2;
668 get_item (iter2)->seq = seq1;
671 link1->data = link2->data;
681 g_sequence_sort (seq->sequence, compare_items, NULL);
682 g_queue_sort (seq->queue, compare_iters, NULL);
686 for (i = 0; i < N_TIMES; ++i)
688 GSequenceIter *iter =
689 g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
691 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
699 case INSERT_SORTED_ITER:
704 g_sequence_sort (seq->sequence, compare_items, NULL);
705 g_queue_sort (seq->queue, compare_iters, NULL);
709 for (i = 0; i < N_TIMES; ++i)
713 iter = g_sequence_insert_sorted_iter (seq->sequence,
715 (GSequenceIterCompareFunc)compare_iters,
718 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
730 g_sequence_sort (seq->sequence, compare_items, NULL);
731 g_queue_sort (seq->queue, compare_iters, NULL);
735 for (i = 0; i < N_TIMES; ++i)
738 GSequenceIter *iter = get_random_iter (seq, &link);
740 if (!g_sequence_iter_is_end (iter))
742 g_sequence_set (iter, new_item (seq));
743 g_sequence_sort_changed (iter, compare_items, NULL);
745 g_queue_delete_link (seq->queue, link);
746 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
753 case SORT_CHANGED_ITER:
757 g_sequence_sort (seq->sequence, compare_items, NULL);
758 g_queue_sort (seq->queue, compare_iters, NULL);
762 for (i = 0; i < N_TIMES; ++i)
765 GSequenceIter *iter = get_random_iter (seq, &link);
767 if (!g_sequence_iter_is_end (iter))
769 g_sequence_set (iter, new_item (seq));
770 g_sequence_sort_changed_iter (iter,
771 (GSequenceIterCompareFunc)compare_iters, seq->sequence);
773 g_queue_delete_link (seq->queue, link);
774 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
785 for (i = 0; i < N_TIMES; ++i)
788 GSequenceIter *iter = get_random_iter (seq, &link);
790 if (!g_sequence_iter_is_end (iter))
792 g_sequence_remove (iter);
793 g_queue_delete_link (seq->queue, link);
800 GSequenceIter *begin_iter, *end_iter;
801 GList *begin_link, *end_link;
804 get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
806 g_sequence_remove_range (begin_iter, end_iter);
809 while (list != end_link)
811 GList *next = list->next;
813 g_queue_delete_link (seq->queue, list);
821 SequenceInfo *src = RANDOM_SEQUENCE();
822 SequenceInfo *dst = RANDOM_SEQUENCE();
824 GSequenceIter *begin_iter, *end_iter;
825 GList *begin_link, *end_link;
827 GSequenceIter *dst_iter;
832 g_assert (src->queue);
833 g_assert (dst->queue);
835 get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
836 dst_iter = get_random_iter (dst, &dst_link);
838 g_sequence_move_range (dst_iter, begin_iter, end_iter);
840 if (dst_link == begin_link || (src == dst && dst_link == end_link))
842 check_integrity (src);
843 check_integrity (dst);
847 if (queue_link_index (src, begin_link) >=
848 queue_link_index (src, end_link))
854 queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
855 queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
861 while (list != end_link)
863 GList *next = list->next;
864 Item *item = get_item (list->data);
866 g_assert (dst->queue);
867 queue_insert_before (dst, dst_link, list->data);
868 g_queue_delete_link (src->queue, list);
870 g_assert (item->seq == src);
883 GSequenceIter *search_iter;
884 GSequenceIter *insert_iter;
886 g_sequence_sort (seq->sequence, compare_items, NULL);
887 g_queue_sort (seq->queue, compare_iters, NULL);
891 item = new_item (seq);
892 search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);
894 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
896 g_assert (search_iter == g_sequence_iter_next (insert_iter));
898 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
904 GSequenceIter *search_iter;
905 GSequenceIter *insert_iter;
907 g_sequence_sort (seq->sequence, compare_items, NULL);
908 g_queue_sort (seq->queue, compare_iters, NULL);
912 item = new_item (seq);
913 search_iter = g_sequence_search_iter (seq->sequence,
915 (GSequenceIterCompareFunc)compare_iters, seq->sequence);
917 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
919 g_assert (search_iter == g_sequence_iter_next (insert_iter));
921 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
927 GSequenceIter *lookup_iter;
928 GSequenceIter *insert_iter;
930 g_sequence_sort (seq->sequence, compare_items, NULL);
931 g_queue_sort (seq->queue, compare_iters, NULL);
935 item = new_item (seq);
936 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
937 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
939 lookup_iter = g_sequence_lookup (seq->sequence, item, simple_items_cmp, NULL);
940 g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
946 GSequenceIter *lookup_iter;
947 GSequenceIter *insert_iter;
949 g_sequence_sort (seq->sequence, compare_items, NULL);
950 g_queue_sort (seq->queue, compare_iters, NULL);
954 item = new_item (seq);
955 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
956 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
958 lookup_iter = g_sequence_lookup_iter (seq->sequence, item,
959 (GSequenceIterCompareFunc) simple_iters_cmp, NULL);
960 g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
971 iter = get_random_iter (seq, &link);
973 if (!g_sequence_iter_is_end (iter))
978 check_integrity (seq);
980 /* Test basic functionality */
981 item = new_item (seq);
982 g_sequence_set (iter, item);
983 g_assert (g_sequence_get (iter) == item);
985 /* Make sure that existing items are freed */
986 for (i = 0; i < N_TIMES; ++i)
987 g_sequence_set (iter, new_item (seq));
989 check_integrity (seq);
991 g_sequence_set (iter, new_item (seq));
996 /* operations on GSequenceIter * */
1001 iter = g_sequence_get_iter_at_pos (seq->sequence, 0);
1003 g_assert (g_sequence_iter_is_begin (iter));
1005 check_integrity (seq);
1007 if (g_sequence_get_length (seq->sequence) > 0)
1009 g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
1013 g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
1016 g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
1021 GSequenceIter *iter;
1022 int len = g_sequence_get_length (seq->sequence);
1024 iter = g_sequence_get_iter_at_pos (seq->sequence, len);
1026 g_assert (g_sequence_iter_is_end (iter));
1030 g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1034 g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1037 g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
1042 GSequenceIter *iter1, *iter2, *iter3, *end;
1044 iter1 = g_sequence_append (seq->sequence, new_item (seq));
1045 iter2 = g_sequence_append (seq->sequence, new_item (seq));
1046 iter3 = g_sequence_append (seq->sequence, new_item (seq));
1048 end = g_sequence_get_end_iter (seq->sequence);
1050 g_assert (g_sequence_iter_next (iter1) == iter2);
1051 g_assert (g_sequence_iter_next (iter2) == iter3);
1052 g_assert (g_sequence_iter_next (iter3) == end);
1053 g_assert (g_sequence_iter_next (end) == end);
1055 g_queue_push_tail (seq->queue, iter1);
1056 g_queue_push_tail (seq->queue, iter2);
1057 g_queue_push_tail (seq->queue, iter3);
1062 GSequenceIter *iter1, *iter2, *iter3, *begin;
1064 iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
1065 iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
1066 iter3 = g_sequence_prepend (seq->sequence, new_item (seq));
1068 begin = g_sequence_get_begin_iter (seq->sequence);
1070 g_assert (g_sequence_iter_prev (iter1) == iter2);
1071 g_assert (g_sequence_iter_prev (iter2) == iter3);
1072 g_assert (iter3 == begin);
1073 g_assert (g_sequence_iter_prev (iter3) == begin);
1074 g_assert (g_sequence_iter_prev (begin) == begin);
1076 g_queue_push_head (seq->queue, iter1);
1077 g_queue_push_head (seq->queue, iter2);
1078 g_queue_push_head (seq->queue, iter3);
1081 case ITER_GET_POSITION:
1084 GSequenceIter *iter = get_random_iter (seq, &link);
1086 g_assert (g_sequence_iter_get_position (iter) ==
1087 queue_link_index (seq, link));
1092 int len = g_sequence_get_length (seq->sequence);
1093 GSequenceIter *iter;
1096 iter = get_random_iter (seq, NULL);
1097 pos = g_sequence_iter_get_position (iter);
1098 iter = g_sequence_iter_move (iter, len - pos);
1099 g_assert (g_sequence_iter_is_end (iter));
1102 iter = get_random_iter (seq, NULL);
1103 pos = g_sequence_iter_get_position (iter);
1106 g_assert (!g_sequence_iter_is_end (iter));
1108 iter = g_sequence_iter_move (iter, 1);
1110 g_assert (g_sequence_iter_is_end (iter));
1113 case ITER_GET_SEQUENCE:
1115 GSequenceIter *iter = get_random_iter (seq, NULL);
1117 g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
1124 GList *link1, *link2;
1125 GSequenceIter *iter1 = get_random_iter (seq, &link1);
1126 GSequenceIter *iter2 = get_random_iter (seq, &link2);
1128 int cmp = g_sequence_iter_compare (iter1, iter2);
1129 int pos1 = queue_link_index (seq, link1);
1130 int pos2 = queue_link_index (seq, link2);
1134 g_assert (pos1 == pos2);
1138 g_assert (pos1 < pos2);
1142 g_assert (pos1 > pos2);
1146 case RANGE_GET_MIDPOINT:
1148 GSequenceIter *iter1 = get_random_iter (seq, NULL);
1149 GSequenceIter *iter2 = get_random_iter (seq, NULL);
1150 GSequenceIter *iter3;
1153 cmp = g_sequence_iter_compare (iter1, iter2);
1164 iter3 = g_sequence_range_get_midpoint (iter1, iter2);
1168 g_assert (iter3 == iter1);
1169 g_assert (iter3 == iter2);
1172 g_assert (g_sequence_iter_get_position (iter3) >=
1173 g_sequence_iter_get_position (iter1));
1174 g_assert (g_sequence_iter_get_position (iter2) >=
1175 g_sequence_iter_get_position (iter3));
1181 check_integrity (seq);
1184 for (k = 0; k < N_SEQUENCES; ++k)
1186 g_queue_free (sequences[k].queue);
1187 g_sequence_free (sequences[k].sequence);
1188 sequences[k].n_items = 0;
1192 /* Random seeds known to have failed at one point
1194 static gulong seeds[] =
1208 /* Single, stand-alone tests */
1211 test_out_of_range_jump (void)
1213 GSequence *seq = g_sequence_new (NULL);
1214 GSequenceIter *iter = g_sequence_get_begin_iter (seq);
1216 g_sequence_iter_move (iter, 5);
1218 g_assert (g_sequence_iter_is_begin (iter));
1219 g_assert (g_sequence_iter_is_end (iter));
1221 g_sequence_free (seq);
1225 test_iter_move (void)
1227 GSequence *seq = g_sequence_new (NULL);
1228 GSequenceIter *iter;
1231 for (i = 0; i < 10; ++i)
1232 g_sequence_append (seq, GINT_TO_POINTER (i));
1234 iter = g_sequence_get_begin_iter (seq);
1235 iter = g_sequence_iter_move (iter, 5);
1236 g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1238 iter = g_sequence_iter_move (iter, -10);
1239 g_assert (g_sequence_iter_is_begin (iter));
1241 iter = g_sequence_get_end_iter (seq);
1242 iter = g_sequence_iter_move (iter, -5);
1243 g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1245 iter = g_sequence_iter_move (iter, 10);
1246 g_assert (g_sequence_iter_is_end (iter));
1248 g_sequence_free (seq);
1252 compare (gconstpointer a, gconstpointer b, gpointer userdata)
1256 ai = GPOINTER_TO_INT (a);
1257 bi = GPOINTER_TO_INT (b);
1268 compare_iter (GSequenceIter *a,
1272 return compare (g_sequence_get (a),
1278 test_insert_sorted_non_pointer (void)
1282 for (i = 0; i < 10; i++)
1284 GSequence *seq = g_sequence_new (NULL);
1287 for (j = 0; j < 10000; j++)
1289 g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
1292 g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
1293 compare_iter, NULL);
1296 g_sequence_check (seq);
1298 g_sequence_free (seq);
1303 test_stable_sort (void)
1306 GSequence *seq = g_sequence_new (NULL);
1308 #define N_ITEMS 1000
1310 GSequenceIter *iters[N_ITEMS];
1311 GSequenceIter *iter;
1313 for (i = 0; i < N_ITEMS; ++i)
1315 iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
1316 g_sequence_check (seq);
1317 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1321 iter = g_sequence_get_begin_iter (seq);
1322 g_assert (g_sequence_iter_get_sequence (iter) == seq);
1323 g_sequence_check (seq);
1324 while (!g_sequence_iter_is_end (iter))
1326 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1327 g_assert (iters[i++] == iter);
1329 iter = g_sequence_iter_next (iter);
1330 g_sequence_check (seq);
1333 g_sequence_sort (seq, compare, NULL);
1336 iter = g_sequence_get_begin_iter (seq);
1337 while (!g_sequence_iter_is_end (iter))
1339 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1340 g_assert (iters[i] == iter);
1342 iter = g_sequence_iter_next (iter);
1343 g_sequence_check (seq);
1348 for (i = N_ITEMS - 1; i >= 0; --i)
1350 g_sequence_check (seq);
1351 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1352 g_assert (g_sequence_get_end_iter (seq) != iters[i]);
1353 g_sequence_sort_changed (iters[i], compare, NULL);
1357 iter = g_sequence_get_begin_iter (seq);
1358 while (!g_sequence_iter_is_end (iter))
1360 g_assert (iters[i++] == iter);
1362 iter = g_sequence_iter_next (iter);
1363 g_sequence_check (seq);
1366 g_sequence_free (seq);
1377 g_test_init (&argc, &argv, NULL);
1379 /* Standalone tests */
1380 g_test_add_func ("/sequence/out-of-range-jump", test_out_of_range_jump);
1381 g_test_add_func ("/sequence/iter-move", test_iter_move);
1382 g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
1383 g_test_add_func ("/sequence/stable-sort", test_stable_sort);
1385 /* Regression tests */
1386 for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
1388 path = g_strdup_printf ("/sequence/random/seed:%lu", seeds[i]);
1389 g_test_add_data_func (path, GUINT_TO_POINTER (seeds[i]), run_random_tests);
1393 /* New random seed */
1394 seed = g_test_rand_int_range (0, G_MAXINT);
1395 path = g_strdup_printf ("/sequence/random/seed:%u", seed);
1396 g_test_add_data_func (path, GUINT_TO_POINTER (seed), run_random_tests);
1399 return g_test_run ();