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