1 #include <stdio.h>
2 #include <glib.h>
3 #include <stdlib.h>
4
5 /* Keep this in sync with gsequence.c !!! */
6 typedef struct _GSequenceNode GSequenceNode;
7
8 struct _GSequence
9 {
10 GSequenceNode * end_node;
11 GDestroyNotify data_destroy_notify;
12 gboolean access_prohibited;
13 GSequence * real_sequence;
14 };
15
16 struct _GSequenceNode
17 {
18 gint n_nodes;
19 guint32 priority;
20 GSequenceNode * parent;
21 GSequenceNode * left;
22 GSequenceNode * right;
23 gpointer data;
24 };
25
26 static guint
27 get_priority (GSequenceNode *node)
28 {
29 guint key = node->priority;
30
31 /* We rely on 0 being less than all other priorities */
32 return key? key : 1;
33 }
34
35 static void
36 check_node (GSequenceNode *node)
37 {
38 if (node)
39 {
40 g_assert (node->parent != node);
41 if (node->parent)
42 g_assert (node->parent->left == node || node->parent->right == node);
43 g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));
44 if (node->left)
45 g_assert (get_priority (node) >= get_priority (node->left));
46 if (node->right)
47 g_assert (get_priority (node) >= get_priority (node->right));
48 check_node (node->left);
49 check_node (node->right);
50 }
51 }
52
53 static void
54 g_sequence_check (GSequence *seq)
55 {
56 GSequenceNode *node = seq->end_node;
57
58 while (node->parent)
59 node = node->parent;
60
61 check_node (node);
62
63 while (node->right)
64 node = node->right;
65
66 g_assert (seq->end_node == node);
67 g_assert (node->data == seq);
68
69 }
70
71
72 enum {
73 NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,
74
75 /* Getting iters */
76 GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
77 INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
78 SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
79 LOOKUP, LOOKUP_ITER,
80
81 /* dereferencing */
82 GET, SET,
83
84 /* operations on GSequenceIter * */
85 ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
86 ITER_MOVE, ITER_GET_SEQUENCE,
87
88 /* search */
89 ITER_COMPARE, RANGE_GET_MIDPOINT,
90 N_OPS
91 };
92
93 typedef struct SequenceInfo
94 {
95 GQueue * queue;
96 GSequence * sequence;
97 guint n_items;
98 } SequenceInfo;
99
100 typedef struct
101 {
102 SequenceInfo *seq;
103 int number;
104 } Item;
105
106 void g_sequence_check (GSequence *sequence);
107
108 static Item *
109 fix_pointer (gconstpointer data)
110 {
111 return (Item *)((char *)data - 1);
112 }
113
114 static Item *
115 get_item (GSequenceIter *iter)
116 {
117 return fix_pointer (g_sequence_get (iter));
118 }
119
120 static void
121 check_integrity (SequenceInfo *info)
122 {
123 GList *list;
124 GSequenceIter *iter;
125 unsigned int i;
126
127 g_sequence_check (info->sequence);
128
129 #if 0
130 if (g_sequence_get_length (info->sequence) != info->n_items)
131 g_printerr ("%d %d\n",
132 g_sequence_get_length (info->sequence), info->n_items);
133 #endif
134 g_assert (info->n_items == g_queue_get_length (info->queue));
135 g_assert ((guint) g_sequence_get_length (info->sequence) == info->n_items);
136
137 iter = g_sequence_get_begin_iter (info->sequence);
138 list = info->queue->head;
139 i = 0;
140 while (iter != g_sequence_get_end_iter (info->sequence))
141 {
142 Item *item;
143 g_assert (list->data == iter);
144 item = get_item (list->data);
145 g_assert (item->seq == info);
146
147 iter = g_sequence_iter_next (iter);
148 list = list->next;
149 i++;
150 }
151
152 g_assert_cmpuint (i, ==, info->n_items);
153 g_assert (info->n_items == g_queue_get_length (info->queue));
154 g_assert ((guint) g_sequence_get_length (info->sequence) == info->n_items);
155 }
156
157 static gpointer
158 new_item (SequenceInfo *seq)
159 {
160 Item *item = g_new (Item, 1);
161 seq->n_items++;
162 item->seq = seq;
163 item->number = g_random_int ();
164
165 /* There have been bugs in the past where the GSequence would
166 * dereference the user pointers. This will make sure such
167 * behavior causes crashes
168 */
169 return ((char *)item + 1);
170 }
171
172 static void
173 free_item (gpointer data)
174 {
175 Item *item = fix_pointer (data);
176 item->seq->n_items--;
177 g_free (item);
178 }
179
180 static void
181 seq_foreach (gpointer data,
182 gpointer user_data)
183 {
184 Item *item = fix_pointer (data);
185 GList **link = user_data;
186 GSequenceIter *iter;
187
188 g_assert (*link != NULL);
189
190 iter = (*link)->data;
191
192 g_assert (get_item (iter) == item);
193
194 item->number = g_random_int();
195
196 *link = (*link)->next;
197 }
198
199 static gint
200 simple_items_cmp (gconstpointer a,
201 gconstpointer b,
202 gpointer data)
203 {
204 const Item *item_a = fix_pointer (a);
205 const Item *item_b = fix_pointer (b);
206
207 if (item_a->number > item_b->number)
208 return +1;
209 else if (item_a->number < item_b->number)
210 return -1;
211 else
212 return 0;
213 }
214
215 static gint
216 simple_iters_cmp (gconstpointer a,
217 gconstpointer b,
218 gpointer data)
219 {
220 GSequence *seq = data;
221 GSequenceIter *iter_a = (GSequenceIter *)a;
222 GSequenceIter *iter_b = (GSequenceIter *)b;
223 gpointer item_a = g_sequence_get (iter_a);
224 gpointer item_b = g_sequence_get (iter_b);
225
226 if (seq)
227 {
228 g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
229 g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
230 }
231
232 return simple_items_cmp (item_a, item_b, data);
233 }
234
235 static gint
236 compare_items (gconstpointer a,
237 gconstpointer b,
238 gpointer data)
239 {
240 const Item *item_a = fix_pointer (a);
241 const Item *item_b = fix_pointer (b);
242
243 if (item_a->number < item_b->number)
244 {
245 return -1;
246 }
247 else if (item_a->number == item_b->number)
248 {
249 /* Force an arbitrary order on the items
250 * We have to do this, since g_queue_insert_sorted() and
251 * g_sequence_insert_sorted() do not agree on the exact
252 * position the item is inserted if the new item is
253 * equal to an existing one.
254 */
255 if (item_a < item_b)
256 return -1;
257 else if (item_a == item_b)
258 return 0;
259 else
260 return 1;
261 }
262 else
263 {
264 return 1;
265 }
266 }
267
268 static void
269 check_sorted (SequenceInfo *info)
270 {
271 GList *list;
272 int last;
273 GSequenceIter *last_iter;
274
275 check_integrity (info);
276
277 last = G_MININT;
278 last_iter = NULL;
279 for (list = info->queue->head; list != NULL; list = list->next)
280 {
281 GSequenceIter *iter = list->data;
282 Item *item = get_item (iter);
283
284 g_assert (item->number >= last);
285 /* Check that the ordering is the same as that of the queue,
286 * ie. that the sort is stable
287 */
288 if (last_iter)
289 g_assert (iter == g_sequence_iter_next (last_iter));
290
291 last = item->number;
292 last_iter = iter;
293 }
294 }
295
296 static gint
297 compare_iters (gconstpointer a,
298 gconstpointer b,
299 gpointer data)
300 {
301 GSequence *seq = data;
302 GSequenceIter *iter_a = (GSequenceIter *)a;
303 GSequenceIter *iter_b = (GSequenceIter *)b;
304 /* compare_items() will fix up the pointers */
305 Item *item_a = g_sequence_get (iter_a);
306 Item *item_b = g_sequence_get (iter_b);
307
308 if (seq)
309 {
310 g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
311 g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
312 }
313
314 return compare_items (item_a, item_b, data);
315 }
316
317 /* A version of g_queue_link_index() that treats NULL as just
318 * beyond the queue
319 */
320 static int
321 queue_link_index (SequenceInfo *seq, GList *link)
322 {
323 if (link)
324 return g_queue_link_index (seq->queue, link);
325 else
326 return g_queue_get_length (seq->queue);
327 }
328
329 static void
330 get_random_range (SequenceInfo *seq,
331 GSequenceIter **begin_iter,
332 GSequenceIter **end_iter,
333 GList **begin_link,
334 GList **end_link)
335 {
336 int length = g_queue_get_length (seq->queue);
337 int b = g_random_int_range (0, length + 1);
338 int e = g_random_int_range (b, length + 1);
339
340 g_assert (length == g_sequence_get_length (seq->sequence));
341
342 if (begin_iter)
343 *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);
344 if (end_iter)
345 *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);
346 if (begin_link)
347 *begin_link = g_queue_peek_nth_link (seq->queue, b);
348 if (end_link)
349 *end_link = g_queue_peek_nth_link (seq->queue, e);
350 if (begin_iter && begin_link)
351 {
352 g_assert (
353 queue_link_index (seq, *begin_link) ==
354 g_sequence_iter_get_position (*begin_iter));
355 }
356 if (end_iter && end_link)
357 {
358 g_assert (
359 queue_link_index (seq, *end_link) ==
360 g_sequence_iter_get_position (*end_iter));
361 }
362 }
363
364 static gint
365 get_random_position (SequenceInfo *seq)
366 {
367 int length = g_queue_get_length (seq->queue);
368
369 g_assert (length == g_sequence_get_length (seq->sequence));
370
371 return g_random_int_range (-2, length + 5);
372 }
373
374 static GSequenceIter *
375 get_random_iter (SequenceInfo *seq,
376 GList **link)
377 {
378 GSequenceIter *iter;
379 int pos = get_random_position (seq);
380 if (link)
381 *link = g_queue_peek_nth_link (seq->queue, pos);
382 iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
383 if (link)
384 g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));
385 return iter;
386 }
387
388 static void
389 dump_info (SequenceInfo *seq)
390 {
391 #if 0
392 GSequenceIter *iter;
393 GList *list;
394
395 iter = g_sequence_get_begin_iter (seq->sequence);
396 list = seq->queue->head;
397
398 while (iter != g_sequence_get_end_iter (seq->sequence))
399 {
400 Item *item = get_item (iter);
401 g_printerr ("%p %p %d\n", list->data, iter, item->number);
402
403 iter = g_sequence_iter_next (iter);
404 list = list->next;
405 }
406 #endif
407 }
408
409 static void
410 run_random_tests (gconstpointer d)
411 {
412 guint32 seed = GPOINTER_TO_UINT (d);
413 #define N_ITERATIONS 60000
414 #define N_SEQUENCES 8
415 #define N_TIMES 24
416
417 SequenceInfo sequences[N_SEQUENCES];
418 int k;
419
420 #if 0
421 g_printerr (" seed: %u\n", seed);
422 #endif
423
424 g_random_set_seed (seed);
425
426 for (k = 0; k < N_SEQUENCES; ++k)
427 {
428 sequences[k].queue = g_queue_new ();
429 sequences[k].sequence = g_sequence_new (free_item);
430 sequences[k].n_items = 0;
431 }
432
433 #define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])
434
435 for (k = 0; k < N_ITERATIONS; ++k)
436 {
437 int i;
438 SequenceInfo *seq = RANDOM_SEQUENCE();
439 int op = g_random_int_range (0, N_OPS);
440
441 #if 0
442 g_printerr ("%d on %p\n", op, seq);
443 #endif
444
445 switch (op)
446 {
447 case NEW:
448 case FREE:
449 {
450 g_queue_free (seq->queue);
451 g_sequence_free (seq->sequence);
452
453 g_assert (seq->n_items == 0);
454
455 seq->queue = g_queue_new ();
456 seq->sequence = g_sequence_new (free_item);
457
458 check_integrity (seq);
459 }
460 break;
461 case GET_LENGTH:
462 {
463 int slen = g_sequence_get_length (seq->sequence);
464 int qlen = g_queue_get_length (seq->queue);
465
466 g_assert (slen == qlen);
467 }
468 break;
469 case FOREACH:
470 {
471 GList *link = seq->queue->head;
472 g_sequence_foreach (seq->sequence, seq_foreach, &link);
473 g_assert (link == NULL);
474 }
475 break;
476 case FOREACH_RANGE:
477 {
478 GSequenceIter *begin_iter, *end_iter;
479 GList *begin_link, *end_link;
480
481 get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
482
483 check_integrity (seq);
484
485 g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);
486
487 g_assert (begin_link == end_link);
488 }
489 break;
490 case SORT:
491 {
492 dump_info (seq);
493
494 g_sequence_sort (seq->sequence, compare_items, NULL);
495 g_queue_sort (seq->queue, compare_iters, NULL);
496
497 check_sorted (seq);
498
499 dump_info (seq);
500 }
501 break;
502 case SORT_ITER:
503 {
504 check_integrity (seq);
505 g_sequence_sort_iter (seq->sequence,
506 (GSequenceIterCompareFunc)compare_iters, seq->sequence);
507 g_queue_sort (seq->queue, compare_iters, NULL);
508 check_sorted (seq);
509 }
510 break;
511
512 /* Getting iters */
513 case GET_END_ITER:
514 case GET_BEGIN_ITER:
515 {
516 GSequenceIter *begin_iter;
517 GSequenceIter *end_iter;
518 GSequenceIter *penultimate_iter;
519
520 begin_iter = g_sequence_get_begin_iter (seq->sequence);
521 check_integrity (seq);
522
523 end_iter = g_sequence_get_end_iter (seq->sequence);
524 check_integrity (seq);
525
526 penultimate_iter = g_sequence_iter_prev (end_iter);
527 check_integrity (seq);
528
529 if (g_sequence_get_length (seq->sequence) > 0)
530 {
531 g_assert (seq->queue->head);
532 g_assert (seq->queue->head->data == begin_iter);
533 g_assert (seq->queue->tail);
534 g_assert (seq->queue->tail->data == penultimate_iter);
535 }
536 else
537 {
538 g_assert (penultimate_iter == end_iter);
539 g_assert (begin_iter == end_iter);
540 g_assert (penultimate_iter == begin_iter);
541 g_assert (seq->queue->head == NULL);
542 g_assert (seq->queue->tail == NULL);
543 }
544 }
545 break;
546 case GET_ITER_AT_POS:
547 {
548 g_assert (g_queue_get_length (seq->queue) == (guint) g_sequence_get_length (seq->sequence));
549
550 for (i = 0; i < 10; ++i)
551 {
552 int pos = get_random_position (seq);
553 GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
554 GList *link = g_queue_peek_nth_link (seq->queue, pos);
555 check_integrity (seq);
556 if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
557 {
558 g_assert (iter == g_sequence_get_end_iter (seq->sequence));
559 g_assert (link == NULL);
560 }
561 else
562 {
563 g_assert (link);
564 g_assert (link->data == iter);
565 }
566 }
567 }
568 break;
569 case APPEND:
570 {
571 for (i = 0; i < 10; ++i)
572 {
573 GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
574 g_queue_push_tail (seq->queue, iter);
575 }
576 }
577 break;
578 case PREPEND:
579 {
580 for (i = 0; i < 10; ++i)
581 {
582 GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
583 g_queue_push_head (seq->queue, iter);
584 }
585 }
586 break;
587 case INSERT_BEFORE:
588 {
589 for (i = 0; i < 10; ++i)
590 {
591 GList *link;
592 GSequenceIter *iter = get_random_iter (seq, &link);
593 GSequenceIter *new_iter;
594 check_integrity (seq);
595
596 new_iter = g_sequence_insert_before (iter, new_item (seq));
597
598 g_queue_insert_before (seq->queue, link, new_iter);
599 }
600 }
601 break;
602 case MOVE:
603 {
604 GList *link1, *link2;
605 SequenceInfo *seq1 = RANDOM_SEQUENCE();
606 SequenceInfo *seq2 = RANDOM_SEQUENCE();
607 GSequenceIter *iter1 = get_random_iter (seq1, &link1);
608 GSequenceIter *iter2 = get_random_iter (seq2, &link2);
609
610 if (!g_sequence_iter_is_end (iter1))
611 {
612 g_sequence_move (iter1, iter2);
613
614 if (!link2)
615 g_assert (g_sequence_iter_is_end (iter2));
616
617 g_queue_insert_before (seq2->queue, link2, link1->data);
618
619 g_queue_delete_link (seq1->queue, link1);
620
621 get_item (iter1)->seq = seq2;
622
623 seq1->n_items--;
624 seq2->n_items++;
625 }
626
627 check_integrity (seq);
628
629 iter1 = get_random_iter (seq, NULL);
630
631 /* Moving an iter to itself should have no effect */
632 if (!g_sequence_iter_is_end (iter1))
633 g_sequence_move (iter1, iter1);
634 }
635 break;
636 case SWAP:
637 {
638 GList *link1, *link2;
639 SequenceInfo *seq1 = RANDOM_SEQUENCE();
640 SequenceInfo *seq2 = RANDOM_SEQUENCE();
641 GSequenceIter *iter1 = get_random_iter (seq1, &link1);
642 GSequenceIter *iter2 = get_random_iter (seq2, &link2);
643
644 if (!g_sequence_iter_is_end (iter1) &&
645 !g_sequence_iter_is_end (iter2))
646 {
647 gpointer tmp;
648
649 g_sequence_swap (iter1, iter2);
650
651 get_item (iter1)->seq = seq2;
652 get_item (iter2)->seq = seq1;
653
654 tmp = link1->data;
655 link1->data = link2->data;
656 link2->data = tmp;
657 }
658 }
659 break;
660 case INSERT_SORTED:
661 {
662 dump_info (seq);
663
664 g_sequence_sort (seq->sequence, compare_items, NULL);
665 g_queue_sort (seq->queue, compare_iters, NULL);
666
667 check_sorted (seq);
668
669 for (i = 0; i < N_TIMES; ++i)
670 {
671 GSequenceIter *iter =
672 g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
673
674 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
675 }
676
677 check_sorted (seq);
678
679 dump_info (seq);
680 }
681 break;
682 case INSERT_SORTED_ITER:
683 {
684 dump_info (seq);
685
686 g_sequence_sort (seq->sequence, compare_items, NULL);
687 g_queue_sort (seq->queue, compare_iters, NULL);
688
689 check_sorted (seq);
690
691 for (i = 0; i < N_TIMES; ++i)
692 {
693 GSequenceIter *iter;
694
695 iter = g_sequence_insert_sorted_iter (seq->sequence,
696 new_item (seq),
697 (GSequenceIterCompareFunc)compare_iters,
698 seq->sequence);
699
700 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
701 }
702
703 check_sorted (seq);
704
705 dump_info (seq);
706 }
707 break;
708 case SORT_CHANGED:
709 {
710 g_sequence_sort (seq->sequence, compare_items, NULL);
711 g_queue_sort (seq->queue, compare_iters, NULL);
712
713 check_sorted (seq);
714
715 for (i = 0; i < N_TIMES; ++i)
716 {
717 GList *link;
718 GSequenceIter *iter = get_random_iter (seq, &link);
719
720 if (!g_sequence_iter_is_end (iter))
721 {
722 g_sequence_set (iter, new_item (seq));
723 g_sequence_sort_changed (iter, compare_items, NULL);
724
725 g_queue_delete_link (seq->queue, link);
726 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
727 }
728
729 check_sorted (seq);
730 }
731 }
732 break;
733 case SORT_CHANGED_ITER:
734 {
735 g_sequence_sort (seq->sequence, compare_items, NULL);
736 g_queue_sort (seq->queue, compare_iters, NULL);
737
738 check_sorted (seq);
739
740 for (i = 0; i < N_TIMES; ++i)
741 {
742 GList *link;
743 GSequenceIter *iter = get_random_iter (seq, &link);
744
745 if (!g_sequence_iter_is_end (iter))
746 {
747 g_sequence_set (iter, new_item (seq));
748 g_sequence_sort_changed_iter (iter,
749 (GSequenceIterCompareFunc)compare_iters, seq->sequence);
750
751 g_queue_delete_link (seq->queue, link);
752 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
753 }
754
755 check_sorted (seq);
756 }
757 }
758 break;
759 case REMOVE:
760 {
761 for (i = 0; i < N_TIMES; ++i)
762 {
763 GList *link;
764 GSequenceIter *iter = get_random_iter (seq, &link);
765
766 if (!g_sequence_iter_is_end (iter))
767 {
768 g_sequence_remove (iter);
769 g_queue_delete_link (seq->queue, link);
770 }
771 }
772 }
773 break;
774 case REMOVE_RANGE:
775 {
776 GSequenceIter *begin_iter, *end_iter;
777 GList *begin_link, *end_link;
778 GList *list;
779
780 get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
781
782 g_sequence_remove_range (begin_iter, end_iter);
783
784 list = begin_link;
785 while (list != end_link)
786 {
787 GList *next = list->next;
788
789 g_queue_delete_link (seq->queue, list);
790
791 list = next;
792 }
793 }
794 break;
795 case MOVE_RANGE:
796 {
797 SequenceInfo *src = RANDOM_SEQUENCE();
798 SequenceInfo *dst = RANDOM_SEQUENCE();
799
800 GSequenceIter *begin_iter, *end_iter;
801 GList *begin_link, *end_link;
802
803 GSequenceIter *dst_iter;
804 GList *dst_link;
805
806 GList *list;
807
808 g_assert (src->queue);
809 g_assert (dst->queue);
810
811 get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
812 dst_iter = get_random_iter (dst, &dst_link);
813
814 g_sequence_move_range (dst_iter, begin_iter, end_iter);
815
816 if (dst_link == begin_link || (src == dst && dst_link == end_link))
817 {
818 check_integrity (src);
819 check_integrity (dst);
820 break;
821 }
822
823 if (queue_link_index (src, begin_link) >=
824 queue_link_index (src, end_link))
825 {
826 break;
827 }
828
829 if (src == dst &&
830 queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
831 queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
832 {
833 break;
834 }
835
836 list = begin_link;
837 while (list != end_link)
838 {
839 GList *next = list->next;
840 Item *item = get_item (list->data);
841
842 g_assert (dst->queue);
843 g_queue_insert_before (dst->queue, dst_link, list->data);
844 g_queue_delete_link (src->queue, list);
845
846 g_assert (item->seq == src);
847
848 src->n_items--;
849 dst->n_items++;
850 item->seq = dst;
851
852 list = next;
853 }
854 }
855 break;
856 case SEARCH:
857 {
858 Item *item;
859 GSequenceIter *search_iter;
860 GSequenceIter *insert_iter;
861
862 g_sequence_sort (seq->sequence, compare_items, NULL);
863 g_queue_sort (seq->queue, compare_iters, NULL);
864
865 check_sorted (seq);
866
867 item = new_item (seq);
868 search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);
869
870 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
871
872 g_assert (search_iter == g_sequence_iter_next (insert_iter));
873
874 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
875 }
876 break;
877 case SEARCH_ITER:
878 {
879 Item *item;
880 GSequenceIter *search_iter;
881 GSequenceIter *insert_iter;
882
883 g_sequence_sort (seq->sequence, compare_items, NULL);
884 g_queue_sort (seq->queue, compare_iters, NULL);
885
886 check_sorted (seq);
887
888 item = new_item (seq);
889 search_iter = g_sequence_search_iter (seq->sequence,
890 item,
891 (GSequenceIterCompareFunc)compare_iters, seq->sequence);
892
893 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
894
895 g_assert (search_iter == g_sequence_iter_next (insert_iter));
896
897 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
898 }
899 break;
900 case LOOKUP:
901 {
902 Item *item;
903 GSequenceIter *lookup_iter;
904 GSequenceIter *insert_iter;
905
906 g_sequence_sort (seq->sequence, compare_items, NULL);
907 g_queue_sort (seq->queue, compare_iters, NULL);
908
909 check_sorted (seq);
910
911 item = new_item (seq);
912 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
913 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
914
915 lookup_iter = g_sequence_lookup (seq->sequence, item, simple_items_cmp, NULL);
916 g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
917 }
918 break;
919 case LOOKUP_ITER:
920 {
921 Item *item;
922 GSequenceIter *lookup_iter;
923 GSequenceIter *insert_iter;
924
925 g_sequence_sort (seq->sequence, compare_items, NULL);
926 g_queue_sort (seq->queue, compare_iters, NULL);
927
928 check_sorted (seq);
929
930 item = new_item (seq);
931 insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
932 g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
933
934 lookup_iter = g_sequence_lookup_iter (seq->sequence, item,
935 (GSequenceIterCompareFunc) simple_iters_cmp, NULL);
936 g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
937 }
938 break;
939
940 /* dereferencing */
941 case GET:
942 case SET:
943 {
944 GSequenceIter *iter;
945 GList *link;
946
947 iter = get_random_iter (seq, &link);
948
949 if (!g_sequence_iter_is_end (iter))
950 {
951 Item *item;
952
953 check_integrity (seq);
954
955 /* Test basic functionality */
956 item = new_item (seq);
957 g_sequence_set (iter, item);
958 g_assert (g_sequence_get (iter) == item);
959
960 /* Make sure that existing items are freed */
961 for (i = 0; i < N_TIMES; ++i)
962 g_sequence_set (iter, new_item (seq));
963
964 check_integrity (seq);
965
966 g_sequence_set (iter, new_item (seq));
967 }
968 }
969 break;
970
971 /* operations on GSequenceIter * */
972 case ITER_IS_BEGIN:
973 {
974 GSequenceIter *iter;
975
976 iter = g_sequence_get_iter_at_pos (seq->sequence, 0);
977
978 g_assert (g_sequence_iter_is_begin (iter));
979
980 check_integrity (seq);
981
982 if (g_sequence_get_length (seq->sequence) > 0)
983 {
984 g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
985 }
986 else
987 {
988 g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
989 }
990
991 g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
992 }
993 break;
994 case ITER_IS_END:
995 {
996 GSequenceIter *iter;
997 int len = g_sequence_get_length (seq->sequence);
998
999 iter = g_sequence_get_iter_at_pos (seq->sequence, len);
1000
1001 g_assert (g_sequence_iter_is_end (iter));
1002
1003 if (len > 0)
1004 {
1005 g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1006 }
1007 else
1008 {
1009 g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1010 }
1011
1012 g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
1013 }
1014 break;
1015 case ITER_NEXT:
1016 {
1017 GSequenceIter *iter1, *iter2, *iter3, *end;
1018
1019 iter1 = g_sequence_append (seq->sequence, new_item (seq));
1020 iter2 = g_sequence_append (seq->sequence, new_item (seq));
1021 iter3 = g_sequence_append (seq->sequence, new_item (seq));
1022
1023 end = g_sequence_get_end_iter (seq->sequence);
1024
1025 g_assert (g_sequence_iter_next (iter1) == iter2);
1026 g_assert (g_sequence_iter_next (iter2) == iter3);
1027 g_assert (g_sequence_iter_next (iter3) == end);
1028 g_assert (g_sequence_iter_next (end) == end);
1029
1030 g_queue_push_tail (seq->queue, iter1);
1031 g_queue_push_tail (seq->queue, iter2);
1032 g_queue_push_tail (seq->queue, iter3);
1033 }
1034 break;
1035 case ITER_PREV:
1036 {
1037 GSequenceIter *iter1, *iter2, *iter3, *begin;
1038
1039 iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
1040 iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
1041 iter3 = g_sequence_prepend (seq->sequence, new_item (seq));
1042
1043 begin = g_sequence_get_begin_iter (seq->sequence);
1044
1045 g_assert (g_sequence_iter_prev (iter1) == iter2);
1046 g_assert (g_sequence_iter_prev (iter2) == iter3);
1047 g_assert (iter3 == begin);
1048 g_assert (g_sequence_iter_prev (iter3) == begin);
1049 g_assert (g_sequence_iter_prev (begin) == begin);
1050
1051 g_queue_push_head (seq->queue, iter1);
1052 g_queue_push_head (seq->queue, iter2);
1053 g_queue_push_head (seq->queue, iter3);
1054 }
1055 break;
1056 case ITER_GET_POSITION:
1057 {
1058 GList *link;
1059 GSequenceIter *iter = get_random_iter (seq, &link);
1060
1061 g_assert (g_sequence_iter_get_position (iter) ==
1062 queue_link_index (seq, link));
1063 }
1064 break;
1065 case ITER_MOVE:
1066 {
1067 int len = g_sequence_get_length (seq->sequence);
1068 GSequenceIter *iter;
1069 int pos;
1070
1071 iter = get_random_iter (seq, NULL);
1072 pos = g_sequence_iter_get_position (iter);
1073 iter = g_sequence_iter_move (iter, len - pos);
1074 g_assert (g_sequence_iter_is_end (iter));
1075
1076
1077 iter = get_random_iter (seq, NULL);
1078 pos = g_sequence_iter_get_position (iter);
1079 while (pos < len)
1080 {
1081 g_assert (!g_sequence_iter_is_end (iter));
1082 pos++;
1083 iter = g_sequence_iter_move (iter, 1);
1084 }
1085 g_assert (g_sequence_iter_is_end (iter));
1086 }
1087 break;
1088 case ITER_GET_SEQUENCE:
1089 {
1090 GSequenceIter *iter = get_random_iter (seq, NULL);
1091
1092 g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
1093 }
1094 break;
1095
1096 /* search */
1097 case ITER_COMPARE:
1098 {
1099 GList *link1, *link2;
1100 GSequenceIter *iter1 = get_random_iter (seq, &link1);
1101 GSequenceIter *iter2 = get_random_iter (seq, &link2);
1102
1103 int cmp = g_sequence_iter_compare (iter1, iter2);
1104 int pos1 = queue_link_index (seq, link1);
1105 int pos2 = queue_link_index (seq, link2);
1106
1107 if (cmp == 0)
1108 {
1109 g_assert (pos1 == pos2);
1110 }
1111 else if (cmp < 0)
1112 {
1113 g_assert (pos1 < pos2);
1114 }
1115 else
1116 {
1117 g_assert (pos1 > pos2);
1118 }
1119 }
1120 break;
1121 case RANGE_GET_MIDPOINT:
1122 {
1123 GSequenceIter *iter1 = get_random_iter (seq, NULL);
1124 GSequenceIter *iter2 = get_random_iter (seq, NULL);
1125 GSequenceIter *iter3;
1126 int cmp;
1127
1128 cmp = g_sequence_iter_compare (iter1, iter2);
1129
1130 if (cmp > 0)
1131 {
1132 GSequenceIter *tmp;
1133
1134 tmp = iter1;
1135 iter1 = iter2;
1136 iter2 = tmp;
1137 }
1138
1139 iter3 = g_sequence_range_get_midpoint (iter1, iter2);
1140
1141 if (cmp == 0)
1142 {
1143 g_assert (iter3 == iter1);
1144 g_assert (iter3 == iter2);
1145 }
1146
1147 g_assert (g_sequence_iter_get_position (iter3) >=
1148 g_sequence_iter_get_position (iter1));
1149 g_assert (g_sequence_iter_get_position (iter2) >=
1150 g_sequence_iter_get_position (iter3));
1151 }
1152 break;
1153
1154 }
1155
1156 check_integrity (seq);
1157 }
1158
1159 for (k = 0; k < N_SEQUENCES; ++k)
1160 {
1161 g_queue_free (sequences[k].queue);
1162 g_sequence_free (sequences[k].sequence);
1163 sequences[k].n_items = 0;
1164 }
1165 }
1166
1167 /* Random seeds known to have failed at one point
1168 */
1169 static gulong seeds[] =
1170 {
1171 825541564u,
1172 801678400u,
1173 1477639090u,
1174 3369132895u,
1175 1192944867u,
1176 770458294u,
1177 1099575817u,
1178 590523467u,
1179 3583571454u,
1180 579241222u
1181 };
1182
1183 /* Single, stand-alone tests */
1184
1185 static void
1186 test_out_of_range_jump (void)
1187 {
1188 GSequence *seq = g_sequence_new (NULL);
1189 GSequenceIter *iter = g_sequence_get_begin_iter (seq);
1190
1191 g_sequence_iter_move (iter, 5);
1192
1193 g_assert (g_sequence_iter_is_begin (iter));
1194 g_assert (g_sequence_iter_is_end (iter));
1195
1196 g_sequence_free (seq);
1197 }
1198
1199 static void
1200 test_iter_move (void)
1201 {
1202 GSequence *seq = g_sequence_new (NULL);
1203 GSequenceIter *iter;
1204 gint i;
1205
1206 for (i = 0; i < 10; ++i)
1207 g_sequence_append (seq, GINT_TO_POINTER (i));
1208
1209 iter = g_sequence_get_begin_iter (seq);
1210 iter = g_sequence_iter_move (iter, 5);
1211 g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1212
1213 iter = g_sequence_iter_move (iter, -10);
1214 g_assert (g_sequence_iter_is_begin (iter));
1215
1216 iter = g_sequence_get_end_iter (seq);
1217 iter = g_sequence_iter_move (iter, -5);
1218 g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1219
1220 iter = g_sequence_iter_move (iter, 10);
1221 g_assert (g_sequence_iter_is_end (iter));
1222
1223 g_sequence_free (seq);
1224 }
1225
1226 static int
1227 compare (gconstpointer a, gconstpointer b, gpointer userdata)
1228 {
1229 int ai, bi;
1230
1231 ai = GPOINTER_TO_INT (a);
1232 bi = GPOINTER_TO_INT (b);
1233
1234 if (ai < bi)
1235 return -1;
1236 else if (ai > bi)
1237 return 1;
1238 else
1239 return 0;
1240 }
1241
1242 static int
1243 compare_iter (GSequenceIter *a,
1244 GSequenceIter *b,
1245 gpointer data)
1246 {
1247 return compare (g_sequence_get (a),
1248 g_sequence_get (b),
1249 data);
1250 }
1251
1252 static void
1253 test_insert_sorted_non_pointer (void)
1254 {
1255 int i;
1256
1257 for (i = 0; i < 10; i++)
1258 {
1259 GSequence *seq = g_sequence_new (NULL);
1260 int j;
1261
1262 for (j = 0; j < 10000; j++)
1263 {
1264 g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
1265 compare, NULL);
1266
1267 g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
1268 compare_iter, NULL);
1269 }
1270
1271 g_sequence_check (seq);
1272
1273 g_sequence_free (seq);
1274 }
1275 }
1276
1277 static void
1278 test_stable_sort (void)
1279 {
1280 int i;
1281 GSequence *seq = g_sequence_new (NULL);
1282
1283 #define N_ITEMS 1000
1284
1285 GSequenceIter *iters[N_ITEMS];
1286 GSequenceIter *iter;
1287
1288 for (i = 0; i < N_ITEMS; ++i)
1289 {
1290 iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
1291 g_sequence_check (seq);
1292 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1293 }
1294
1295 i = 0;
1296 iter = g_sequence_get_begin_iter (seq);
1297 g_assert (g_sequence_iter_get_sequence (iter) == seq);
1298 g_sequence_check (seq);
1299 while (!g_sequence_iter_is_end (iter))
1300 {
1301 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1302 g_assert (iters[i++] == iter);
1303
1304 iter = g_sequence_iter_next (iter);
1305 g_sequence_check (seq);
1306 }
1307
1308 g_sequence_sort (seq, compare, NULL);
1309
1310 i = 0;
1311 iter = g_sequence_get_begin_iter (seq);
1312 while (!g_sequence_iter_is_end (iter))
1313 {
1314 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1315 g_assert (iters[i] == iter);
1316
1317 iter = g_sequence_iter_next (iter);
1318 g_sequence_check (seq);
1319
1320 i++;
1321 }
1322
1323 for (i = N_ITEMS - 1; i >= 0; --i)
1324 {
1325 g_sequence_check (seq);
1326 g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1327 g_assert (g_sequence_get_end_iter (seq) != iters[i]);
1328 g_sequence_sort_changed (iters[i], compare, NULL);
1329 }
1330
1331 i = 0;
1332 iter = g_sequence_get_begin_iter (seq);
1333 while (!g_sequence_iter_is_end (iter))
1334 {
1335 g_assert (iters[i++] == iter);
1336
1337 iter = g_sequence_iter_next (iter);
1338 g_sequence_check (seq);
1339 }
1340
1341 g_sequence_free (seq);
1342 }
1343
1344 static void
1345 test_empty (void)
1346 {
1347 GSequence *seq;
1348 int i;
1349
1350 seq = g_sequence_new (NULL);
1351 g_assert_true (g_sequence_is_empty (seq));
1352
1353 for (i = 0; i < 1000; i++)
1354 {
1355 g_sequence_append (seq, GINT_TO_POINTER (i));
1356 g_assert_false (g_sequence_is_empty (seq));
1357 }
1358
1359 for (i = 0; i < 1000; i++)
1360 {
1361 GSequenceIter *end = g_sequence_get_end_iter (seq);
1362 g_assert_false (g_sequence_is_empty (seq));
1363 g_sequence_remove (g_sequence_iter_prev (end));
1364 }
1365
1366 g_assert_true (g_sequence_is_empty (seq));
1367
1368 g_sequence_free (seq);
1369 }
1370
1371 int
1372 main (int argc,
1373 char **argv)
1374 {
1375 gsize i;
1376 guint32 seed;
1377 gchar *path;
1378
1379 g_test_init (&argc, &argv, NULL);
1380
1381 /* Standalone tests */
1382 g_test_add_func ("/sequence/out-of-range-jump", test_out_of_range_jump);
1383 g_test_add_func ("/sequence/iter-move", test_iter_move);
1384 g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
1385 g_test_add_func ("/sequence/stable-sort", test_stable_sort);
1386 g_test_add_func ("/sequence/is_empty", test_empty);
1387
1388 /* Regression tests */
1389 for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
1390 {
1391 path = g_strdup_printf ("/sequence/random/seed:%lu", seeds[i]);
1392 g_test_add_data_func (path, GUINT_TO_POINTER (seeds[i]), run_random_tests);
1393 g_free (path);
1394 }
1395
1396 /* New random seed */
1397 seed = g_test_rand_int_range (0, G_MAXINT);
1398 path = g_strdup_printf ("/sequence/random/seed:%u", seed);
1399 g_test_add_data_func (path, GUINT_TO_POINTER (seed), run_random_tests);
1400 g_free (path);
1401
1402 return g_test_run ();
1403 }