Branch data Line data Source code
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 : 168096180 : get_priority (GSequenceNode *node)
28 : : {
29 : 168096180 : guint key = node->priority;
30 : :
31 : : /* We rely on 0 being less than all other priorities */
32 [ + - ]: 168096180 : return key? key : 1;
33 : : }
34 : :
35 : : static void
36 : 175141251 : check_node (GSequenceNode *node)
37 : : {
38 [ + + ]: 175141251 : if (node)
39 : : {
40 : 86396447 : g_assert (node->parent != node);
41 [ + + ]: 86396447 : if (node->parent)
42 : 84048090 : g_assert (node->parent->left == node || node->parent->right == node);
43 : 86396447 : g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));
44 [ + + ]: 86396447 : if (node->left)
45 : 42051495 : g_assert (get_priority (node) >= get_priority (node->left));
46 [ + + ]: 86396447 : if (node->right)
47 : 41996595 : g_assert (get_priority (node) >= get_priority (node->right));
48 : 86396447 : check_node (node->left);
49 : 86396447 : check_node (node->right);
50 : : }
51 : 175141251 : }
52 : :
53 : : static void
54 : 2348357 : g_sequence_check (GSequence *seq)
55 : : {
56 : 2348357 : GSequenceNode *node = seq->end_node;
57 : :
58 [ + + ]: 7989145 : while (node->parent)
59 : 5640788 : node = node->parent;
60 : :
61 : 2348357 : check_node (node);
62 : :
63 [ + + ]: 7989145 : while (node->right)
64 : 5640788 : node = node->right;
65 : :
66 : 2348357 : g_assert (seq->end_node == node);
67 : 2348357 : g_assert (node->data == seq);
68 : :
69 : 2348357 : }
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 : 298450216 : fix_pointer (gconstpointer data)
110 : : {
111 : 298450216 : return (Item *)((char *)data - 1);
112 : : }
113 : :
114 : : static Item *
115 : 116849609 : get_item (GSequenceIter *iter)
116 : : {
117 : 116849609 : return fix_pointer (g_sequence_get (iter));
118 : : }
119 : :
120 : : static void
121 : 2343346 : check_integrity (SequenceInfo *info)
122 : : {
123 : : GList *list;
124 : : GSequenceIter *iter;
125 : : unsigned int i;
126 : :
127 : 2343346 : 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 : 2343346 : g_assert (info->n_items == g_queue_get_length (info->queue));
135 : 2343346 : g_assert ((guint) g_sequence_get_length (info->sequence) == info->n_items);
136 : :
137 : 2343346 : iter = g_sequence_get_begin_iter (info->sequence);
138 : 2343346 : list = info->queue->head;
139 : 2343346 : i = 0;
140 [ + + ]: 81689936 : while (iter != g_sequence_get_end_iter (info->sequence))
141 : : {
142 : : Item *item;
143 : 79346590 : g_assert (list->data == iter);
144 : 79346590 : item = get_item (list->data);
145 : 79346590 : g_assert (item->seq == info);
146 : :
147 : 79346590 : iter = g_sequence_iter_next (iter);
148 : 79346590 : list = list->next;
149 : 79346590 : i++;
150 : : }
151 : :
152 : 2343346 : g_assert_cmpuint (i, ==, info->n_items);
153 : 2343346 : g_assert (info->n_items == g_queue_get_length (info->queue));
154 : 2343346 : g_assert ((guint) g_sequence_get_length (info->sequence) == info->n_items);
155 : 2343346 : }
156 : :
157 : : static gpointer
158 : 2651109 : new_item (SequenceInfo *seq)
159 : : {
160 : 2651109 : Item *item = g_new (Item, 1);
161 : 2651109 : seq->n_items++;
162 : 2651109 : item->seq = seq;
163 : 2651109 : 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 : 2651109 : return ((char *)item + 1);
170 : : }
171 : :
172 : : static void
173 : 2651109 : free_item (gpointer data)
174 : : {
175 : 2651109 : Item *item = fix_pointer (data);
176 : 2651109 : item->seq->n_items--;
177 : 2651109 : g_free (item);
178 : 2651109 : }
179 : :
180 : : static void
181 : 760632 : seq_foreach (gpointer data,
182 : : gpointer user_data)
183 : : {
184 : 760632 : Item *item = fix_pointer (data);
185 : 760632 : GList **link = user_data;
186 : : GSequenceIter *iter;
187 : :
188 : 760632 : g_assert (*link != NULL);
189 : :
190 : 760632 : iter = (*link)->data;
191 : :
192 : 760632 : g_assert (get_item (iter) == item);
193 : :
194 : 760632 : item->number = g_random_int();
195 : :
196 : 760632 : *link = (*link)->next;
197 : 760632 : }
198 : :
199 : : static gint
200 : 192094 : simple_items_cmp (gconstpointer a,
201 : : gconstpointer b,
202 : : gpointer data)
203 : : {
204 : 192094 : const Item *item_a = fix_pointer (a);
205 : 192094 : const Item *item_b = fix_pointer (b);
206 : :
207 [ + + ]: 192094 : if (item_a->number > item_b->number)
208 : 60545 : return +1;
209 [ + + ]: 131549 : else if (item_a->number < item_b->number)
210 : 60583 : return -1;
211 : : else
212 : 70966 : return 0;
213 : : }
214 : :
215 : : static gint
216 : 113854 : simple_iters_cmp (gconstpointer a,
217 : : gconstpointer b,
218 : : gpointer data)
219 : : {
220 : 113854 : GSequence *seq = data;
221 : 113854 : GSequenceIter *iter_a = (GSequenceIter *)a;
222 : 113854 : GSequenceIter *iter_b = (GSequenceIter *)b;
223 : 113854 : gpointer item_a = g_sequence_get (iter_a);
224 : 113854 : gpointer item_b = g_sequence_get (iter_b);
225 : :
226 [ - + ]: 113854 : if (seq)
227 : : {
228 : 0 : g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
229 : 0 : g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
230 : : }
231 : :
232 : 113854 : return simple_items_cmp (item_a, item_b, data);
233 : : }
234 : :
235 : : static gint
236 : 88902339 : compare_items (gconstpointer a,
237 : : gconstpointer b,
238 : : gpointer data)
239 : : {
240 : 88902339 : const Item *item_a = fix_pointer (a);
241 : 88902339 : const Item *item_b = fix_pointer (b);
242 : :
243 [ + + ]: 88902339 : if (item_a->number < item_b->number)
244 : : {
245 : 74923223 : return -1;
246 : : }
247 [ - + ]: 13979116 : 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 [ # # ]: 0 : if (item_a < item_b)
256 : 0 : return -1;
257 [ # # ]: 0 : else if (item_a == item_b)
258 : 0 : return 0;
259 : : else
260 : 0 : return 1;
261 : : }
262 : : else
263 : : {
264 : 13979116 : return 1;
265 : : }
266 : : }
267 : :
268 : : static void
269 : 1071703 : check_sorted (SequenceInfo *info)
270 : : {
271 : : GList *list;
272 : : int last;
273 : : GSequenceIter *last_iter;
274 : :
275 : 1071703 : check_integrity (info);
276 : :
277 : 1071703 : last = G_MININT;
278 : 1071703 : last_iter = NULL;
279 [ + + ]: 37648491 : for (list = info->queue->head; list != NULL; list = list->next)
280 : : {
281 : 36576788 : GSequenceIter *iter = list->data;
282 : 36576788 : Item *item = get_item (iter);
283 : :
284 : 36576788 : 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 [ + + ]: 36576788 : if (last_iter)
289 : 35665598 : g_assert (iter == g_sequence_iter_next (last_iter));
290 : :
291 : 36576788 : last = item->number;
292 : 36576788 : last_iter = iter;
293 : : }
294 : 1071703 : }
295 : :
296 : : static gint
297 : 61174411 : compare_iters (gconstpointer a,
298 : : gconstpointer b,
299 : : gpointer data)
300 : : {
301 : 61174411 : GSequence *seq = data;
302 : 61174411 : GSequenceIter *iter_a = (GSequenceIter *)a;
303 : 61174411 : GSequenceIter *iter_b = (GSequenceIter *)b;
304 : : /* compare_items() will fix up the pointers */
305 : 61174411 : Item *item_a = g_sequence_get (iter_a);
306 : 61174411 : Item *item_b = g_sequence_get (iter_b);
307 : :
308 [ + + ]: 61174411 : if (seq)
309 : : {
310 : 7359345 : g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
311 : 7359345 : g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
312 : : }
313 : :
314 : 61174411 : 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 : 1836443 : queue_link_index (SequenceInfo *seq, GList *link)
322 : : {
323 [ + + ]: 1836443 : if (link)
324 : 1113327 : return g_queue_link_index (seq->queue, link);
325 : : else
326 : 723116 : return g_queue_get_length (seq->queue);
327 : : }
328 : :
329 : : static void
330 : 53482 : get_random_range (SequenceInfo *seq,
331 : : GSequenceIter **begin_iter,
332 : : GSequenceIter **end_iter,
333 : : GList **begin_link,
334 : : GList **end_link)
335 : : {
336 : 53482 : int length = g_queue_get_length (seq->queue);
337 : 53482 : int b = g_random_int_range (0, length + 1);
338 : 53482 : int e = g_random_int_range (b, length + 1);
339 : :
340 : 53482 : g_assert (length == g_sequence_get_length (seq->sequence));
341 : :
342 [ + - ]: 53482 : if (begin_iter)
343 : 53482 : *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);
344 [ + - ]: 53482 : if (end_iter)
345 : 53482 : *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);
346 [ + - ]: 53482 : if (begin_link)
347 : 53482 : *begin_link = g_queue_peek_nth_link (seq->queue, b);
348 [ + - ]: 53482 : if (end_link)
349 : 53482 : *end_link = g_queue_peek_nth_link (seq->queue, e);
350 [ + - + - ]: 53482 : if (begin_iter && begin_link)
351 : : {
352 : 53482 : g_assert (
353 : : queue_link_index (seq, *begin_link) ==
354 : : g_sequence_iter_get_position (*begin_iter));
355 : : }
356 [ + - + - ]: 53482 : if (end_iter && end_link)
357 : : {
358 : 53482 : g_assert (
359 : : queue_link_index (seq, *end_link) ==
360 : : g_sequence_iter_get_position (*end_iter));
361 : : }
362 : 53482 : }
363 : :
364 : : static gint
365 : 1922510 : get_random_position (SequenceInfo *seq)
366 : : {
367 : 1922510 : int length = g_queue_get_length (seq->queue);
368 : :
369 : 1922510 : g_assert (length == g_sequence_get_length (seq->sequence));
370 : :
371 : 1922510 : return g_random_int_range (-2, length + 5);
372 : : }
373 : :
374 : : static GSequenceIter *
375 : 1747600 : get_random_iter (SequenceInfo *seq,
376 : : GList **link)
377 : : {
378 : : GSequenceIter *iter;
379 : 1747600 : int pos = get_random_position (seq);
380 [ + + ]: 1747600 : if (link)
381 : 1640127 : *link = g_queue_peek_nth_link (seq->queue, pos);
382 : 1747600 : iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
383 [ + + ]: 1747600 : if (link)
384 : 1640127 : g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));
385 : 1747600 : return iter;
386 : : }
387 : :
388 : : static void
389 : 107100 : 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 : 107100 : }
408 : :
409 : : static void
410 : 11 : run_random_tests (gconstpointer d)
411 : : {
412 : 11 : 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 : 11 : g_random_set_seed (seed);
425 : :
426 [ + + ]: 99 : for (k = 0; k < N_SEQUENCES; ++k)
427 : : {
428 : 88 : sequences[k].queue = g_queue_new ();
429 : 88 : sequences[k].sequence = g_sequence_new (free_item);
430 : 88 : sequences[k].n_items = 0;
431 : : }
432 : :
433 : : #define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])
434 : :
435 [ + + ]: 660011 : for (k = 0; k < N_ITERATIONS; ++k)
436 : : {
437 : : int i;
438 : 660000 : SequenceInfo *seq = RANDOM_SEQUENCE();
439 : 660000 : 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 [ + + + + : 660000 : switch (op)
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- ]
446 : : {
447 : 35576 : case NEW:
448 : : case FREE:
449 : : {
450 : 35576 : g_queue_free (seq->queue);
451 : 35576 : g_sequence_free (seq->sequence);
452 : :
453 : 35576 : g_assert (seq->n_items == 0);
454 : :
455 : 35576 : seq->queue = g_queue_new ();
456 : 35576 : seq->sequence = g_sequence_new (free_item);
457 : :
458 : 35576 : check_integrity (seq);
459 : : }
460 : 35576 : break;
461 : 17710 : case GET_LENGTH:
462 : : {
463 : 17710 : int slen = g_sequence_get_length (seq->sequence);
464 : 17710 : int qlen = g_queue_get_length (seq->queue);
465 : :
466 : 17710 : g_assert (slen == qlen);
467 : : }
468 : 17710 : break;
469 : 17954 : case FOREACH:
470 : : {
471 : 17954 : GList *link = seq->queue->head;
472 : 17954 : g_sequence_foreach (seq->sequence, seq_foreach, &link);
473 : 17954 : g_assert (link == NULL);
474 : : }
475 : 17954 : break;
476 : 17815 : case FOREACH_RANGE:
477 : : {
478 : : GSequenceIter *begin_iter, *end_iter;
479 : : GList *begin_link, *end_link;
480 : :
481 : 17815 : get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
482 : :
483 : 17815 : check_integrity (seq);
484 : :
485 : 17815 : g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);
486 : :
487 : 17815 : g_assert (begin_link == end_link);
488 : : }
489 : 17815 : break;
490 : 17849 : case SORT:
491 : : {
492 : 17849 : dump_info (seq);
493 : :
494 : 17849 : g_sequence_sort (seq->sequence, compare_items, NULL);
495 : 17849 : g_queue_sort (seq->queue, compare_iters, NULL);
496 : :
497 : 17849 : check_sorted (seq);
498 : :
499 : 17849 : dump_info (seq);
500 : : }
501 : 17849 : break;
502 : 17941 : case SORT_ITER:
503 : : {
504 : 17941 : check_integrity (seq);
505 : 17941 : g_sequence_sort_iter (seq->sequence,
506 : 17941 : (GSequenceIterCompareFunc)compare_iters, seq->sequence);
507 : 17941 : g_queue_sort (seq->queue, compare_iters, NULL);
508 : 17941 : check_sorted (seq);
509 : : }
510 : 17941 : break;
511 : :
512 : : /* Getting iters */
513 : 35644 : case GET_END_ITER:
514 : : case GET_BEGIN_ITER:
515 : : {
516 : : GSequenceIter *begin_iter;
517 : : GSequenceIter *end_iter;
518 : : GSequenceIter *penultimate_iter;
519 : :
520 : 35644 : begin_iter = g_sequence_get_begin_iter (seq->sequence);
521 : 35644 : check_integrity (seq);
522 : :
523 : 35644 : end_iter = g_sequence_get_end_iter (seq->sequence);
524 : 35644 : check_integrity (seq);
525 : :
526 : 35644 : penultimate_iter = g_sequence_iter_prev (end_iter);
527 : 35644 : check_integrity (seq);
528 : :
529 [ + + ]: 35644 : if (g_sequence_get_length (seq->sequence) > 0)
530 : : {
531 : 30040 : g_assert (seq->queue->head);
532 : 30040 : g_assert (seq->queue->head->data == begin_iter);
533 : 30040 : g_assert (seq->queue->tail);
534 : 30040 : g_assert (seq->queue->tail->data == penultimate_iter);
535 : : }
536 : : else
537 : : {
538 : 5604 : g_assert (penultimate_iter == end_iter);
539 : 5604 : g_assert (begin_iter == end_iter);
540 : 5604 : g_assert (penultimate_iter == begin_iter);
541 : 5604 : g_assert (seq->queue->head == NULL);
542 : 5604 : g_assert (seq->queue->tail == NULL);
543 : : }
544 : : }
545 : 35644 : break;
546 : 17491 : case GET_ITER_AT_POS:
547 : : {
548 : 17491 : g_assert (g_queue_get_length (seq->queue) == (guint) g_sequence_get_length (seq->sequence));
549 : :
550 [ + + ]: 192401 : for (i = 0; i < 10; ++i)
551 : : {
552 : 174910 : int pos = get_random_position (seq);
553 : 174910 : GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
554 : 174910 : GList *link = g_queue_peek_nth_link (seq->queue, pos);
555 : 174910 : check_integrity (seq);
556 [ + + + + ]: 174910 : if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
557 : : {
558 : 68989 : g_assert (iter == g_sequence_get_end_iter (seq->sequence));
559 : 68989 : g_assert (link == NULL);
560 : : }
561 : : else
562 : : {
563 : 105921 : g_assert (link);
564 : 105921 : g_assert (link->data == iter);
565 : : }
566 : : }
567 : : }
568 : 17491 : break;
569 : 17918 : case APPEND:
570 : : {
571 [ + + ]: 197098 : for (i = 0; i < 10; ++i)
572 : : {
573 : 179180 : GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
574 : 179180 : g_queue_push_tail (seq->queue, iter);
575 : : }
576 : : }
577 : 17918 : break;
578 : 17930 : case PREPEND:
579 : : {
580 [ + + ]: 197230 : for (i = 0; i < 10; ++i)
581 : : {
582 : 179300 : GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
583 : 179300 : g_queue_push_head (seq->queue, iter);
584 : : }
585 : : }
586 : 17930 : break;
587 : 17590 : case INSERT_BEFORE:
588 : : {
589 [ + + ]: 193490 : for (i = 0; i < 10; ++i)
590 : : {
591 : : GList *link;
592 : 175900 : GSequenceIter *iter = get_random_iter (seq, &link);
593 : : GSequenceIter *new_iter;
594 : 175900 : check_integrity (seq);
595 : :
596 : 175900 : new_iter = g_sequence_insert_before (iter, new_item (seq));
597 : :
598 : 175900 : g_queue_insert_before (seq->queue, link, new_iter);
599 : : }
600 : : }
601 : 17590 : break;
602 : 17688 : case MOVE:
603 : : {
604 : : GList *link1, *link2;
605 : 17688 : SequenceInfo *seq1 = RANDOM_SEQUENCE();
606 : 17688 : SequenceInfo *seq2 = RANDOM_SEQUENCE();
607 : 17688 : GSequenceIter *iter1 = get_random_iter (seq1, &link1);
608 : 17688 : GSequenceIter *iter2 = get_random_iter (seq2, &link2);
609 : :
610 [ + + ]: 17688 : if (!g_sequence_iter_is_end (iter1))
611 : : {
612 : 10696 : g_sequence_move (iter1, iter2);
613 : :
614 [ + + ]: 10696 : if (!link2)
615 : 3969 : g_assert (g_sequence_iter_is_end (iter2));
616 : :
617 : 10696 : g_queue_insert_before (seq2->queue, link2, link1->data);
618 : :
619 : 10696 : g_queue_delete_link (seq1->queue, link1);
620 : :
621 : 10696 : get_item (iter1)->seq = seq2;
622 : :
623 : 10696 : seq1->n_items--;
624 : 10696 : seq2->n_items++;
625 : : }
626 : :
627 : 17688 : check_integrity (seq);
628 : :
629 : 17688 : iter1 = get_random_iter (seq, NULL);
630 : :
631 : : /* Moving an iter to itself should have no effect */
632 [ + + ]: 17688 : if (!g_sequence_iter_is_end (iter1))
633 : 10727 : g_sequence_move (iter1, iter1);
634 : : }
635 : 17688 : break;
636 : 17844 : case SWAP:
637 : : {
638 : : GList *link1, *link2;
639 : 17844 : SequenceInfo *seq1 = RANDOM_SEQUENCE();
640 : 17844 : SequenceInfo *seq2 = RANDOM_SEQUENCE();
641 : 17844 : GSequenceIter *iter1 = get_random_iter (seq1, &link1);
642 : 17844 : GSequenceIter *iter2 = get_random_iter (seq2, &link2);
643 : :
644 [ + + + + ]: 28600 : if (!g_sequence_iter_is_end (iter1) &&
645 : 10756 : !g_sequence_iter_is_end (iter2))
646 : : {
647 : : gpointer tmp;
648 : :
649 : 6769 : g_sequence_swap (iter1, iter2);
650 : :
651 : 6769 : get_item (iter1)->seq = seq2;
652 : 6769 : get_item (iter2)->seq = seq1;
653 : :
654 : 6769 : tmp = link1->data;
655 : 6769 : link1->data = link2->data;
656 : 6769 : link2->data = tmp;
657 : : }
658 : : }
659 : 17844 : break;
660 : 17862 : case INSERT_SORTED:
661 : : {
662 : 17862 : dump_info (seq);
663 : :
664 : 17862 : g_sequence_sort (seq->sequence, compare_items, NULL);
665 : 17862 : g_queue_sort (seq->queue, compare_iters, NULL);
666 : :
667 : 17862 : check_sorted (seq);
668 : :
669 [ + + ]: 446550 : for (i = 0; i < N_TIMES; ++i)
670 : : {
671 : : GSequenceIter *iter =
672 : 428688 : g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
673 : :
674 : 428688 : g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
675 : : }
676 : :
677 : 17862 : check_sorted (seq);
678 : :
679 : 17862 : dump_info (seq);
680 : : }
681 : 17862 : break;
682 : 17839 : case INSERT_SORTED_ITER:
683 : : {
684 : 17839 : dump_info (seq);
685 : :
686 : 17839 : g_sequence_sort (seq->sequence, compare_items, NULL);
687 : 17839 : g_queue_sort (seq->queue, compare_iters, NULL);
688 : :
689 : 17839 : check_sorted (seq);
690 : :
691 [ + + ]: 445975 : for (i = 0; i < N_TIMES; ++i)
692 : : {
693 : : GSequenceIter *iter;
694 : :
695 : 428136 : iter = g_sequence_insert_sorted_iter (seq->sequence,
696 : : new_item (seq),
697 : : (GSequenceIterCompareFunc)compare_iters,
698 : 428136 : seq->sequence);
699 : :
700 : 428136 : g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
701 : : }
702 : :
703 : 17839 : check_sorted (seq);
704 : :
705 : 17839 : dump_info (seq);
706 : : }
707 : 17839 : break;
708 : 17715 : case SORT_CHANGED:
709 : : {
710 : 17715 : g_sequence_sort (seq->sequence, compare_items, NULL);
711 : 17715 : g_queue_sort (seq->queue, compare_iters, NULL);
712 : :
713 : 17715 : check_sorted (seq);
714 : :
715 [ + + ]: 442875 : for (i = 0; i < N_TIMES; ++i)
716 : : {
717 : : GList *link;
718 : 425160 : GSequenceIter *iter = get_random_iter (seq, &link);
719 : :
720 [ + + ]: 425160 : if (!g_sequence_iter_is_end (iter))
721 : : {
722 : 256187 : g_sequence_set (iter, new_item (seq));
723 : 256187 : g_sequence_sort_changed (iter, compare_items, NULL);
724 : :
725 : 256187 : g_queue_delete_link (seq->queue, link);
726 : 256187 : g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
727 : : }
728 : :
729 : 425160 : check_sorted (seq);
730 : : }
731 : : }
732 : 17715 : break;
733 : 18014 : case SORT_CHANGED_ITER:
734 : : {
735 : 18014 : g_sequence_sort (seq->sequence, compare_items, NULL);
736 : 18014 : g_queue_sort (seq->queue, compare_iters, NULL);
737 : :
738 : 18014 : check_sorted (seq);
739 : :
740 [ + + ]: 450350 : for (i = 0; i < N_TIMES; ++i)
741 : : {
742 : : GList *link;
743 : 432336 : GSequenceIter *iter = get_random_iter (seq, &link);
744 : :
745 [ + + ]: 432336 : if (!g_sequence_iter_is_end (iter))
746 : : {
747 : 262180 : g_sequence_set (iter, new_item (seq));
748 : 262180 : g_sequence_sort_changed_iter (iter,
749 : 262180 : (GSequenceIterCompareFunc)compare_iters, seq->sequence);
750 : :
751 : 262180 : g_queue_delete_link (seq->queue, link);
752 : 262180 : g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
753 : : }
754 : :
755 : 432336 : check_sorted (seq);
756 : : }
757 : : }
758 : 18014 : break;
759 : 17852 : case REMOVE:
760 : : {
761 [ + + ]: 446300 : for (i = 0; i < N_TIMES; ++i)
762 : : {
763 : : GList *link;
764 : 428448 : GSequenceIter *iter = get_random_iter (seq, &link);
765 : :
766 [ + + ]: 428448 : if (!g_sequence_iter_is_end (iter))
767 : : {
768 : 224480 : g_sequence_remove (iter);
769 : 224480 : g_queue_delete_link (seq->queue, link);
770 : : }
771 : : }
772 : : }
773 : 17852 : break;
774 : 17886 : case REMOVE_RANGE:
775 : : {
776 : : GSequenceIter *begin_iter, *end_iter;
777 : : GList *begin_link, *end_link;
778 : : GList *list;
779 : :
780 : 17886 : get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
781 : :
782 : 17886 : g_sequence_remove_range (begin_iter, end_iter);
783 : :
784 : 17886 : list = begin_link;
785 [ + + ]: 161830 : while (list != end_link)
786 : : {
787 : 143944 : GList *next = list->next;
788 : :
789 : 143944 : g_queue_delete_link (seq->queue, list);
790 : :
791 : 143944 : list = next;
792 : : }
793 : : }
794 : 17886 : break;
795 : 17781 : case MOVE_RANGE:
796 : : {
797 : 17781 : SequenceInfo *src = RANDOM_SEQUENCE();
798 : 17781 : 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 : 17781 : g_assert (src->queue);
809 : 17781 : g_assert (dst->queue);
810 : :
811 : 17781 : get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
812 : 17781 : dst_iter = get_random_iter (dst, &dst_link);
813 : :
814 : 17781 : g_sequence_move_range (dst_iter, begin_iter, end_iter);
815 : :
816 [ + + + + : 17781 : if (dst_link == begin_link || (src == dst && dst_link == end_link))
+ + ]
817 : : {
818 : 2002 : check_integrity (src);
819 : 2002 : check_integrity (dst);
820 : 6261 : break;
821 : : }
822 : :
823 [ + + ]: 31558 : if (queue_link_index (src, begin_link) >=
824 : 15779 : queue_link_index (src, end_link))
825 : : {
826 : 4000 : break;
827 : : }
828 : :
829 [ + + + + ]: 13058 : if (src == dst &&
830 [ + + ]: 2030 : queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
831 : 751 : queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
832 : : {
833 : 259 : break;
834 : : }
835 : :
836 : 11520 : list = begin_link;
837 [ + + ]: 152885 : while (list != end_link)
838 : : {
839 : 141365 : GList *next = list->next;
840 : 141365 : Item *item = get_item (list->data);
841 : :
842 : 141365 : g_assert (dst->queue);
843 : 141365 : g_queue_insert_before (dst->queue, dst_link, list->data);
844 : 141365 : g_queue_delete_link (src->queue, list);
845 : :
846 : 141365 : g_assert (item->seq == src);
847 : :
848 : 141365 : src->n_items--;
849 : 141365 : dst->n_items++;
850 : 141365 : item->seq = dst;
851 : :
852 : 141365 : list = next;
853 : : }
854 : : }
855 : 11520 : break;
856 : 18021 : case SEARCH:
857 : : {
858 : : Item *item;
859 : : GSequenceIter *search_iter;
860 : : GSequenceIter *insert_iter;
861 : :
862 : 18021 : g_sequence_sort (seq->sequence, compare_items, NULL);
863 : 18021 : g_queue_sort (seq->queue, compare_iters, NULL);
864 : :
865 : 18021 : check_sorted (seq);
866 : :
867 : 18021 : item = new_item (seq);
868 : 18021 : search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);
869 : :
870 : 18021 : insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
871 : :
872 : 18021 : g_assert (search_iter == g_sequence_iter_next (insert_iter));
873 : :
874 : 18021 : g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
875 : : }
876 : 18021 : break;
877 : 17782 : case SEARCH_ITER:
878 : : {
879 : : Item *item;
880 : : GSequenceIter *search_iter;
881 : : GSequenceIter *insert_iter;
882 : :
883 : 17782 : g_sequence_sort (seq->sequence, compare_items, NULL);
884 : 17782 : g_queue_sort (seq->queue, compare_iters, NULL);
885 : :
886 : 17782 : check_sorted (seq);
887 : :
888 : 17782 : item = new_item (seq);
889 : 17782 : search_iter = g_sequence_search_iter (seq->sequence,
890 : : item,
891 : 17782 : (GSequenceIterCompareFunc)compare_iters, seq->sequence);
892 : :
893 : 17782 : insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
894 : :
895 : 17782 : g_assert (search_iter == g_sequence_iter_next (insert_iter));
896 : :
897 : 17782 : g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
898 : : }
899 : 17782 : break;
900 : 17693 : case LOOKUP:
901 : : {
902 : : Item *item;
903 : : GSequenceIter *lookup_iter;
904 : : GSequenceIter *insert_iter;
905 : :
906 : 17693 : g_sequence_sort (seq->sequence, compare_items, NULL);
907 : 17693 : g_queue_sort (seq->queue, compare_iters, NULL);
908 : :
909 : 17693 : check_sorted (seq);
910 : :
911 : 17693 : item = new_item (seq);
912 : 17693 : insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
913 : 17693 : g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
914 : :
915 : 17693 : lookup_iter = g_sequence_lookup (seq->sequence, item, simple_items_cmp, NULL);
916 : 17693 : g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
917 : : }
918 : 17693 : break;
919 : 17790 : case LOOKUP_ITER:
920 : : {
921 : : Item *item;
922 : : GSequenceIter *lookup_iter;
923 : : GSequenceIter *insert_iter;
924 : :
925 : 17790 : g_sequence_sort (seq->sequence, compare_items, NULL);
926 : 17790 : g_queue_sort (seq->queue, compare_iters, NULL);
927 : :
928 : 17790 : check_sorted (seq);
929 : :
930 : 17790 : item = new_item (seq);
931 : 17790 : insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
932 : 17790 : g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
933 : :
934 : 17790 : lookup_iter = g_sequence_lookup_iter (seq->sequence, item,
935 : : (GSequenceIterCompareFunc) simple_iters_cmp, NULL);
936 : 17790 : g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
937 : : }
938 : 17790 : break;
939 : :
940 : : /* dereferencing */
941 : 35704 : case GET:
942 : : case SET:
943 : : {
944 : : GSequenceIter *iter;
945 : : GList *link;
946 : :
947 : 35704 : iter = get_random_iter (seq, &link);
948 : :
949 [ + + ]: 35704 : if (!g_sequence_iter_is_end (iter))
950 : : {
951 : : Item *item;
952 : :
953 : 21632 : check_integrity (seq);
954 : :
955 : : /* Test basic functionality */
956 : 21632 : item = new_item (seq);
957 : 21632 : g_sequence_set (iter, item);
958 : 21632 : g_assert (g_sequence_get (iter) == item);
959 : :
960 : : /* Make sure that existing items are freed */
961 [ + + ]: 540800 : for (i = 0; i < N_TIMES; ++i)
962 : 519168 : g_sequence_set (iter, new_item (seq));
963 : :
964 : 21632 : check_integrity (seq);
965 : :
966 : 21632 : g_sequence_set (iter, new_item (seq));
967 : : }
968 : : }
969 : 35704 : break;
970 : :
971 : : /* operations on GSequenceIter * */
972 : 17613 : case ITER_IS_BEGIN:
973 : : {
974 : : GSequenceIter *iter;
975 : :
976 : 17613 : iter = g_sequence_get_iter_at_pos (seq->sequence, 0);
977 : :
978 : 17613 : g_assert (g_sequence_iter_is_begin (iter));
979 : :
980 : 17613 : check_integrity (seq);
981 : :
982 [ + + ]: 17613 : if (g_sequence_get_length (seq->sequence) > 0)
983 : : {
984 : 14845 : g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
985 : : }
986 : : else
987 : : {
988 : 2768 : g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
989 : : }
990 : :
991 : 17613 : g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
992 : : }
993 : 17613 : break;
994 : 17857 : case ITER_IS_END:
995 : : {
996 : : GSequenceIter *iter;
997 : 17857 : int len = g_sequence_get_length (seq->sequence);
998 : :
999 : 17857 : iter = g_sequence_get_iter_at_pos (seq->sequence, len);
1000 : :
1001 : 17857 : g_assert (g_sequence_iter_is_end (iter));
1002 : :
1003 [ + + ]: 17857 : if (len > 0)
1004 : : {
1005 : 15062 : g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1006 : : }
1007 : : else
1008 : : {
1009 : 2795 : g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1010 : : }
1011 : :
1012 : 17857 : g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
1013 : : }
1014 : 17857 : break;
1015 : 17891 : case ITER_NEXT:
1016 : : {
1017 : : GSequenceIter *iter1, *iter2, *iter3, *end;
1018 : :
1019 : 17891 : iter1 = g_sequence_append (seq->sequence, new_item (seq));
1020 : 17891 : iter2 = g_sequence_append (seq->sequence, new_item (seq));
1021 : 17891 : iter3 = g_sequence_append (seq->sequence, new_item (seq));
1022 : :
1023 : 17891 : end = g_sequence_get_end_iter (seq->sequence);
1024 : :
1025 : 17891 : g_assert (g_sequence_iter_next (iter1) == iter2);
1026 : 17891 : g_assert (g_sequence_iter_next (iter2) == iter3);
1027 : 17891 : g_assert (g_sequence_iter_next (iter3) == end);
1028 : 17891 : g_assert (g_sequence_iter_next (end) == end);
1029 : :
1030 : 17891 : g_queue_push_tail (seq->queue, iter1);
1031 : 17891 : g_queue_push_tail (seq->queue, iter2);
1032 : 17891 : g_queue_push_tail (seq->queue, iter3);
1033 : : }
1034 : 17891 : break;
1035 : 18049 : case ITER_PREV:
1036 : : {
1037 : : GSequenceIter *iter1, *iter2, *iter3, *begin;
1038 : :
1039 : 18049 : iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
1040 : 18049 : iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
1041 : 18049 : iter3 = g_sequence_prepend (seq->sequence, new_item (seq));
1042 : :
1043 : 18049 : begin = g_sequence_get_begin_iter (seq->sequence);
1044 : :
1045 : 18049 : g_assert (g_sequence_iter_prev (iter1) == iter2);
1046 : 18049 : g_assert (g_sequence_iter_prev (iter2) == iter3);
1047 : 18049 : g_assert (iter3 == begin);
1048 : 18049 : g_assert (g_sequence_iter_prev (iter3) == begin);
1049 : 18049 : g_assert (g_sequence_iter_prev (begin) == begin);
1050 : :
1051 : 18049 : g_queue_push_head (seq->queue, iter1);
1052 : 18049 : g_queue_push_head (seq->queue, iter2);
1053 : 18049 : g_queue_push_head (seq->queue, iter3);
1054 : : }
1055 : 18049 : break;
1056 : 17922 : case ITER_GET_POSITION:
1057 : : {
1058 : : GList *link;
1059 : 17922 : GSequenceIter *iter = get_random_iter (seq, &link);
1060 : :
1061 : 17922 : g_assert (g_sequence_iter_get_position (iter) ==
1062 : : queue_link_index (seq, link));
1063 : : }
1064 : 17922 : break;
1065 : 17921 : case ITER_MOVE:
1066 : : {
1067 : 17921 : int len = g_sequence_get_length (seq->sequence);
1068 : : GSequenceIter *iter;
1069 : : int pos;
1070 : :
1071 : 17921 : iter = get_random_iter (seq, NULL);
1072 : 17921 : pos = g_sequence_iter_get_position (iter);
1073 : 17921 : iter = g_sequence_iter_move (iter, len - pos);
1074 : 17921 : g_assert (g_sequence_iter_is_end (iter));
1075 : :
1076 : :
1077 : 17921 : iter = get_random_iter (seq, NULL);
1078 : 17921 : pos = g_sequence_iter_get_position (iter);
1079 [ + + ]: 289876 : while (pos < len)
1080 : : {
1081 : 271955 : g_assert (!g_sequence_iter_is_end (iter));
1082 : 271955 : pos++;
1083 : 271955 : iter = g_sequence_iter_move (iter, 1);
1084 : : }
1085 : 17921 : g_assert (g_sequence_iter_is_end (iter));
1086 : : }
1087 : 17921 : break;
1088 : 17961 : case ITER_GET_SEQUENCE:
1089 : : {
1090 : 17961 : GSequenceIter *iter = get_random_iter (seq, NULL);
1091 : :
1092 : 17961 : g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
1093 : : }
1094 : 17961 : break;
1095 : :
1096 : : /* search */
1097 : 17906 : case ITER_COMPARE:
1098 : : {
1099 : : GList *link1, *link2;
1100 : 17906 : GSequenceIter *iter1 = get_random_iter (seq, &link1);
1101 : 17906 : GSequenceIter *iter2 = get_random_iter (seq, &link2);
1102 : :
1103 : 17906 : int cmp = g_sequence_iter_compare (iter1, iter2);
1104 : 17906 : int pos1 = queue_link_index (seq, link1);
1105 : 17906 : int pos2 = queue_link_index (seq, link2);
1106 : :
1107 [ + + ]: 17906 : if (cmp == 0)
1108 : : {
1109 : 5271 : g_assert (pos1 == pos2);
1110 : : }
1111 [ + + ]: 12635 : else if (cmp < 0)
1112 : : {
1113 : 6254 : g_assert (pos1 < pos2);
1114 : : }
1115 : : else
1116 : : {
1117 : 6381 : g_assert (pos1 > pos2);
1118 : : }
1119 : : }
1120 : 17906 : break;
1121 : 17991 : case RANGE_GET_MIDPOINT:
1122 : : {
1123 : 17991 : GSequenceIter *iter1 = get_random_iter (seq, NULL);
1124 : 17991 : GSequenceIter *iter2 = get_random_iter (seq, NULL);
1125 : : GSequenceIter *iter3;
1126 : : int cmp;
1127 : :
1128 : 17991 : cmp = g_sequence_iter_compare (iter1, iter2);
1129 : :
1130 [ + + ]: 17991 : if (cmp > 0)
1131 : : {
1132 : : GSequenceIter *tmp;
1133 : :
1134 : 6349 : tmp = iter1;
1135 : 6349 : iter1 = iter2;
1136 : 6349 : iter2 = tmp;
1137 : : }
1138 : :
1139 : 17991 : iter3 = g_sequence_range_get_midpoint (iter1, iter2);
1140 : :
1141 [ + + ]: 17991 : if (cmp == 0)
1142 : : {
1143 : 5205 : g_assert (iter3 == iter1);
1144 : 5205 : g_assert (iter3 == iter2);
1145 : : }
1146 : :
1147 : 17991 : g_assert (g_sequence_iter_get_position (iter3) >=
1148 : : g_sequence_iter_get_position (iter1));
1149 : 17991 : g_assert (g_sequence_iter_get_position (iter2) >=
1150 : : g_sequence_iter_get_position (iter3));
1151 : : }
1152 : 17991 : break;
1153 : :
1154 : : }
1155 : :
1156 : 660000 : check_integrity (seq);
1157 : : }
1158 : :
1159 [ + + ]: 99 : for (k = 0; k < N_SEQUENCES; ++k)
1160 : : {
1161 : 88 : g_queue_free (sequences[k].queue);
1162 : 88 : g_sequence_free (sequences[k].sequence);
1163 : 88 : sequences[k].n_items = 0;
1164 : : }
1165 : 11 : }
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 : 1 : test_out_of_range_jump (void)
1187 : : {
1188 : 1 : GSequence *seq = g_sequence_new (NULL);
1189 : 1 : GSequenceIter *iter = g_sequence_get_begin_iter (seq);
1190 : :
1191 : 1 : g_sequence_iter_move (iter, 5);
1192 : :
1193 : 1 : g_assert (g_sequence_iter_is_begin (iter));
1194 : 1 : g_assert (g_sequence_iter_is_end (iter));
1195 : :
1196 : 1 : g_sequence_free (seq);
1197 : 1 : }
1198 : :
1199 : : static void
1200 : 1 : test_iter_move (void)
1201 : : {
1202 : 1 : GSequence *seq = g_sequence_new (NULL);
1203 : : GSequenceIter *iter;
1204 : : gint i;
1205 : :
1206 [ + + ]: 11 : for (i = 0; i < 10; ++i)
1207 : 10 : g_sequence_append (seq, GINT_TO_POINTER (i));
1208 : :
1209 : 1 : iter = g_sequence_get_begin_iter (seq);
1210 : 1 : iter = g_sequence_iter_move (iter, 5);
1211 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1212 : :
1213 : 1 : iter = g_sequence_iter_move (iter, -10);
1214 : 1 : g_assert (g_sequence_iter_is_begin (iter));
1215 : :
1216 : 1 : iter = g_sequence_get_end_iter (seq);
1217 : 1 : iter = g_sequence_iter_move (iter, -5);
1218 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1219 : :
1220 : 1 : iter = g_sequence_iter_move (iter, 10);
1221 : 1 : g_assert (g_sequence_iter_is_end (iter));
1222 : :
1223 : 1 : g_sequence_free (seq);
1224 : 1 : }
1225 : :
1226 : : static int
1227 : 3361163 : compare (gconstpointer a, gconstpointer b, gpointer userdata)
1228 : : {
1229 : : int ai, bi;
1230 : :
1231 : 3361163 : ai = GPOINTER_TO_INT (a);
1232 : 3361163 : bi = GPOINTER_TO_INT (b);
1233 : :
1234 [ + + ]: 3361163 : if (ai < bi)
1235 : 1665067 : return -1;
1236 [ + + ]: 1696096 : else if (ai > bi)
1237 : 1689066 : return 1;
1238 : : else
1239 : 7030 : return 0;
1240 : : }
1241 : :
1242 : : static int
1243 : 1676670 : compare_iter (GSequenceIter *a,
1244 : : GSequenceIter *b,
1245 : : gpointer data)
1246 : : {
1247 : 1676670 : return compare (g_sequence_get (a),
1248 : 1676670 : g_sequence_get (b),
1249 : : data);
1250 : : }
1251 : :
1252 : : static void
1253 : 1 : test_insert_sorted_non_pointer (void)
1254 : : {
1255 : : int i;
1256 : :
1257 [ + + ]: 11 : for (i = 0; i < 10; i++)
1258 : : {
1259 : 10 : GSequence *seq = g_sequence_new (NULL);
1260 : : int j;
1261 : :
1262 [ + + ]: 100010 : for (j = 0; j < 10000; j++)
1263 : : {
1264 : 100000 : g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
1265 : : compare, NULL);
1266 : :
1267 : 100000 : g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
1268 : : compare_iter, NULL);
1269 : : }
1270 : :
1271 : 10 : g_sequence_check (seq);
1272 : :
1273 : 10 : g_sequence_free (seq);
1274 : : }
1275 : 1 : }
1276 : :
1277 : : static void
1278 : 1 : test_stable_sort (void)
1279 : : {
1280 : : int i;
1281 : 1 : GSequence *seq = g_sequence_new (NULL);
1282 : :
1283 : : #define N_ITEMS 1000
1284 : :
1285 : : GSequenceIter *iters[N_ITEMS];
1286 : : GSequenceIter *iter;
1287 : :
1288 [ + + ]: 1001 : for (i = 0; i < N_ITEMS; ++i)
1289 : : {
1290 : 1000 : iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
1291 : 1000 : g_sequence_check (seq);
1292 : 1000 : g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1293 : : }
1294 : :
1295 : 1 : i = 0;
1296 : 1 : iter = g_sequence_get_begin_iter (seq);
1297 : 1 : g_assert (g_sequence_iter_get_sequence (iter) == seq);
1298 : 1 : g_sequence_check (seq);
1299 [ + + ]: 1001 : while (!g_sequence_iter_is_end (iter))
1300 : : {
1301 : 1000 : g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1302 : 1000 : g_assert (iters[i++] == iter);
1303 : :
1304 : 1000 : iter = g_sequence_iter_next (iter);
1305 : 1000 : g_sequence_check (seq);
1306 : : }
1307 : :
1308 : 1 : g_sequence_sort (seq, compare, NULL);
1309 : :
1310 : 1 : i = 0;
1311 : 1 : iter = g_sequence_get_begin_iter (seq);
1312 [ + + ]: 1001 : while (!g_sequence_iter_is_end (iter))
1313 : : {
1314 : 1000 : g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1315 : 1000 : g_assert (iters[i] == iter);
1316 : :
1317 : 1000 : iter = g_sequence_iter_next (iter);
1318 : 1000 : g_sequence_check (seq);
1319 : :
1320 : 1000 : i++;
1321 : : }
1322 : :
1323 [ + + ]: 1001 : for (i = N_ITEMS - 1; i >= 0; --i)
1324 : : {
1325 : 1000 : g_sequence_check (seq);
1326 : 1000 : g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1327 : 1000 : g_assert (g_sequence_get_end_iter (seq) != iters[i]);
1328 : 1000 : g_sequence_sort_changed (iters[i], compare, NULL);
1329 : : }
1330 : :
1331 : 1 : i = 0;
1332 : 1 : iter = g_sequence_get_begin_iter (seq);
1333 [ + + ]: 1001 : while (!g_sequence_iter_is_end (iter))
1334 : : {
1335 : 1000 : g_assert (iters[i++] == iter);
1336 : :
1337 : 1000 : iter = g_sequence_iter_next (iter);
1338 : 1000 : g_sequence_check (seq);
1339 : : }
1340 : :
1341 : 1 : g_sequence_free (seq);
1342 : 1 : }
1343 : :
1344 : : static void
1345 : 1 : test_empty (void)
1346 : : {
1347 : : GSequence *seq;
1348 : : int i;
1349 : :
1350 : 1 : seq = g_sequence_new (NULL);
1351 : 1 : g_assert_true (g_sequence_is_empty (seq));
1352 : :
1353 [ + + ]: 1001 : for (i = 0; i < 1000; i++)
1354 : : {
1355 : 1000 : g_sequence_append (seq, GINT_TO_POINTER (i));
1356 : 1000 : g_assert_false (g_sequence_is_empty (seq));
1357 : : }
1358 : :
1359 [ + + ]: 1001 : for (i = 0; i < 1000; i++)
1360 : : {
1361 : 1000 : GSequenceIter *end = g_sequence_get_end_iter (seq);
1362 : 1000 : g_assert_false (g_sequence_is_empty (seq));
1363 : 1000 : g_sequence_remove (g_sequence_iter_prev (end));
1364 : : }
1365 : :
1366 : 1 : g_assert_true (g_sequence_is_empty (seq));
1367 : :
1368 : 1 : g_sequence_free (seq);
1369 : 1 : }
1370 : :
1371 : : int
1372 : 1 : main (int argc,
1373 : : char **argv)
1374 : : {
1375 : : gsize i;
1376 : : guint32 seed;
1377 : : gchar *path;
1378 : :
1379 : 1 : g_test_init (&argc, &argv, NULL);
1380 : :
1381 : : /* Standalone tests */
1382 : 1 : g_test_add_func ("/sequence/out-of-range-jump", test_out_of_range_jump);
1383 : 1 : g_test_add_func ("/sequence/iter-move", test_iter_move);
1384 : 1 : g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
1385 : 1 : g_test_add_func ("/sequence/stable-sort", test_stable_sort);
1386 : 1 : g_test_add_func ("/sequence/is_empty", test_empty);
1387 : :
1388 : : /* Regression tests */
1389 [ + + ]: 11 : for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
1390 : : {
1391 : 10 : path = g_strdup_printf ("/sequence/random/seed:%lu", seeds[i]);
1392 : 10 : g_test_add_data_func (path, GUINT_TO_POINTER (seeds[i]), run_random_tests);
1393 : 10 : g_free (path);
1394 : : }
1395 : :
1396 : : /* New random seed */
1397 : 1 : seed = g_test_rand_int_range (0, G_MAXINT);
1398 : 1 : path = g_strdup_printf ("/sequence/random/seed:%u", seed);
1399 : 1 : g_test_add_data_func (path, GUINT_TO_POINTER (seed), run_random_tests);
1400 : 1 : g_free (path);
1401 : :
1402 : 1 : return g_test_run ();
1403 : : }
|