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 | guint 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: node->left); |
54 | check_node (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 | guint 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 (data: 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 (sequence: 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 ((guint) g_sequence_get_length (info->sequence) == info->n_items); |
141 | |
142 | iter = g_sequence_get_begin_iter (seq: info->sequence); |
143 | list = info->queue->head; |
144 | i = 0; |
145 | while (iter != g_sequence_get_end_iter (seq: info->sequence)) |
146 | { |
147 | Item *item; |
148 | g_assert (list->data == iter); |
149 | item = get_item (iter: 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 ((guint) 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 (mem: 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 (data: a); |
209 | const Item *item_b = fix_pointer (data: 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: iter_a); |
228 | gpointer item_b = g_sequence_get (iter: 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 (a: item_a, b: 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 (data: a); |
245 | const Item *item_b = fix_pointer (data: 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: iter_a); |
310 | Item *item_b = g_sequence_get (iter: 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 (a: item_a, b: 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 (queue: seq->queue, link_: link); |
329 | else |
330 | return g_queue_get_length (queue: 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 (queue: seq->queue); |
341 | int b = g_random_int_range (begin: 0, end: length + 1); |
342 | int e = g_random_int_range (begin: b, end: 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: seq->sequence, pos: b); |
348 | if (end_iter) |
349 | *end_iter = g_sequence_get_iter_at_pos (seq: seq->sequence, pos: e); |
350 | if (begin_link) |
351 | *begin_link = g_queue_peek_nth_link (queue: seq->queue, n: b); |
352 | if (end_link) |
353 | *end_link = g_queue_peek_nth_link (queue: seq->queue, n: 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 (queue: seq->queue); |
372 | |
373 | g_assert (length == g_sequence_get_length (seq->sequence)); |
374 | |
375 | return g_random_int_range (begin: -2, end: 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 (queue: seq->queue, n: pos); |
386 | iter = g_sequence_get_iter_at_pos (seq: 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 (data_destroy: 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 (begin: 0, end: 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 (queue: seq->queue); |
455 | g_sequence_free (seq: seq->sequence); |
456 | |
457 | g_assert (seq->n_items == 0); |
458 | |
459 | seq->queue = g_queue_new (); |
460 | seq->sequence = g_sequence_new (data_destroy: free_item); |
461 | |
462 | check_integrity (info: seq); |
463 | } |
464 | break; |
465 | case GET_LENGTH: |
466 | { |
467 | int slen = g_sequence_get_length (seq: seq->sequence); |
468 | int qlen = g_queue_get_length (queue: 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: seq->sequence, func: seq_foreach, user_data: &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: &begin_iter, end_iter: &end_iter, begin_link: &begin_link, end_link: &end_link); |
486 | |
487 | check_integrity (info: seq); |
488 | |
489 | g_sequence_foreach_range (begin: begin_iter, end: end_iter, func: seq_foreach, user_data: &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: seq->sequence, cmp_func: compare_items, NULL); |
499 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
500 | |
501 | check_sorted (info: seq); |
502 | |
503 | dump_info (seq); |
504 | } |
505 | break; |
506 | case SORT_ITER: |
507 | { |
508 | check_integrity (info: seq); |
509 | g_sequence_sort_iter (seq: seq->sequence, |
510 | cmp_func: (GSequenceIterCompareFunc)compare_iters, cmp_data: seq->sequence); |
511 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
512 | check_sorted (info: 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: seq->sequence); |
525 | check_integrity (info: seq); |
526 | |
527 | end_iter = g_sequence_get_end_iter (seq: seq->sequence); |
528 | check_integrity (info: seq); |
529 | |
530 | penultimate_iter = g_sequence_iter_prev (iter: end_iter); |
531 | check_integrity (info: seq); |
532 | |
533 | if (g_sequence_get_length (seq: 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) == (guint) 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: seq->sequence, pos); |
560 | GList *link = g_queue_peek_nth_link (queue: seq->queue, n: pos); |
561 | check_integrity (info: seq); |
562 | if (pos >= g_sequence_get_length (seq: 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: seq->sequence, data: new_item (seq)); |
580 | g_queue_push_tail (queue: seq->queue, data: iter); |
581 | } |
582 | } |
583 | break; |
584 | case PREPEND: |
585 | { |
586 | for (i = 0; i < 10; ++i) |
587 | { |
588 | GSequenceIter *iter = g_sequence_prepend (seq: seq->sequence, data: new_item (seq)); |
589 | g_queue_push_head (queue: seq->queue, data: 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: &link); |
599 | GSequenceIter *new_iter; |
600 | check_integrity (info: seq); |
601 | |
602 | new_iter = g_sequence_insert_before (iter, data: new_item (seq)); |
603 | |
604 | g_queue_insert_before (queue: seq->queue, sibling: link, data: 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 (seq: seq1, link: &link1); |
614 | GSequenceIter *iter2 = get_random_iter (seq: seq2, link: &link2); |
615 | |
616 | if (!g_sequence_iter_is_end (iter: iter1)) |
617 | { |
618 | g_sequence_move (src: iter1, dest: iter2); |
619 | |
620 | if (!link2) |
621 | g_assert (g_sequence_iter_is_end (iter2)); |
622 | |
623 | g_queue_insert_before (queue: seq2->queue, sibling: link2, data: link1->data); |
624 | |
625 | g_queue_delete_link (queue: seq1->queue, link_: link1); |
626 | |
627 | get_item (iter: iter1)->seq = seq2; |
628 | |
629 | seq1->n_items--; |
630 | seq2->n_items++; |
631 | } |
632 | |
633 | check_integrity (info: 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 (iter: iter1)) |
639 | g_sequence_move (src: iter1, dest: 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 (seq: seq1, link: &link1); |
648 | GSequenceIter *iter2 = get_random_iter (seq: seq2, link: &link2); |
649 | |
650 | if (!g_sequence_iter_is_end (iter: iter1) && |
651 | !g_sequence_iter_is_end (iter: iter2)) |
652 | { |
653 | gpointer tmp; |
654 | |
655 | g_sequence_swap (a: iter1, b: iter2); |
656 | |
657 | get_item (iter: iter1)->seq = seq2; |
658 | get_item (iter: 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: seq->sequence, cmp_func: compare_items, NULL); |
672 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
673 | |
674 | check_sorted (info: seq); |
675 | |
676 | for (i = 0; i < N_TIMES; ++i) |
677 | { |
678 | GSequenceIter *iter = |
679 | g_sequence_insert_sorted (seq: seq->sequence, data: new_item(seq), cmp_func: compare_items, NULL); |
680 | |
681 | g_queue_insert_sorted (queue: seq->queue, data: iter, func: compare_iters, NULL); |
682 | } |
683 | |
684 | check_sorted (info: 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: seq->sequence, cmp_func: compare_items, NULL); |
695 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
696 | |
697 | check_sorted (info: seq); |
698 | |
699 | for (i = 0; i < N_TIMES; ++i) |
700 | { |
701 | GSequenceIter *iter; |
702 | |
703 | iter = g_sequence_insert_sorted_iter (seq: seq->sequence, |
704 | data: new_item (seq), |
705 | iter_cmp: (GSequenceIterCompareFunc)compare_iters, |
706 | cmp_data: seq->sequence); |
707 | |
708 | g_queue_insert_sorted (queue: seq->queue, data: iter, func: compare_iters, NULL); |
709 | } |
710 | |
711 | check_sorted (info: seq); |
712 | |
713 | dump_info (seq); |
714 | } |
715 | break; |
716 | case SORT_CHANGED: |
717 | { |
718 | int i; |
719 | |
720 | g_sequence_sort (seq: seq->sequence, cmp_func: compare_items, NULL); |
721 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
722 | |
723 | check_sorted (info: seq); |
724 | |
725 | for (i = 0; i < N_TIMES; ++i) |
726 | { |
727 | GList *link; |
728 | GSequenceIter *iter = get_random_iter (seq, link: &link); |
729 | |
730 | if (!g_sequence_iter_is_end (iter)) |
731 | { |
732 | g_sequence_set (iter, data: new_item (seq)); |
733 | g_sequence_sort_changed (iter, cmp_func: compare_items, NULL); |
734 | |
735 | g_queue_delete_link (queue: seq->queue, link_: link); |
736 | g_queue_insert_sorted (queue: seq->queue, data: iter, func: compare_iters, NULL); |
737 | } |
738 | |
739 | check_sorted (info: seq); |
740 | } |
741 | } |
742 | break; |
743 | case SORT_CHANGED_ITER: |
744 | { |
745 | int i; |
746 | |
747 | g_sequence_sort (seq: seq->sequence, cmp_func: compare_items, NULL); |
748 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
749 | |
750 | check_sorted (info: seq); |
751 | |
752 | for (i = 0; i < N_TIMES; ++i) |
753 | { |
754 | GList *link; |
755 | GSequenceIter *iter = get_random_iter (seq, link: &link); |
756 | |
757 | if (!g_sequence_iter_is_end (iter)) |
758 | { |
759 | g_sequence_set (iter, data: new_item (seq)); |
760 | g_sequence_sort_changed_iter (iter, |
761 | iter_cmp: (GSequenceIterCompareFunc)compare_iters, cmp_data: seq->sequence); |
762 | |
763 | g_queue_delete_link (queue: seq->queue, link_: link); |
764 | g_queue_insert_sorted (queue: seq->queue, data: iter, func: compare_iters, NULL); |
765 | } |
766 | |
767 | check_sorted (info: 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: &link); |
779 | |
780 | if (!g_sequence_iter_is_end (iter)) |
781 | { |
782 | g_sequence_remove (iter); |
783 | g_queue_delete_link (queue: seq->queue, link_: 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: &begin_iter, end_iter: &end_iter, begin_link: &begin_link, end_link: &end_link); |
795 | |
796 | g_sequence_remove_range (begin: begin_iter, end: end_iter); |
797 | |
798 | list = begin_link; |
799 | while (list != end_link) |
800 | { |
801 | GList *next = list->next; |
802 | |
803 | g_queue_delete_link (queue: seq->queue, link_: 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 (seq: src, begin_iter: &begin_iter, end_iter: &end_iter, begin_link: &begin_link, end_link: &end_link); |
826 | dst_iter = get_random_iter (seq: dst, link: &dst_link); |
827 | |
828 | g_sequence_move_range (dest: dst_iter, begin: begin_iter, end: end_iter); |
829 | |
830 | if (dst_link == begin_link || (src == dst && dst_link == end_link)) |
831 | { |
832 | check_integrity (info: src); |
833 | check_integrity (info: dst); |
834 | break; |
835 | } |
836 | |
837 | if (queue_link_index (seq: src, link: begin_link) >= |
838 | queue_link_index (seq: src, link: end_link)) |
839 | { |
840 | break; |
841 | } |
842 | |
843 | if (src == dst && |
844 | queue_link_index (seq: src, link: dst_link) >= queue_link_index (seq: src, link: begin_link) && |
845 | queue_link_index (seq: src, link: dst_link) <= queue_link_index (seq: src, link: 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 (iter: list->data); |
855 | |
856 | g_assert (dst->queue); |
857 | g_queue_insert_before (queue: dst->queue, sibling: dst_link, data: list->data); |
858 | g_queue_delete_link (queue: src->queue, link_: 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: seq->sequence, cmp_func: compare_items, NULL); |
877 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
878 | |
879 | check_sorted (info: seq); |
880 | |
881 | item = new_item (seq); |
882 | search_iter = g_sequence_search (seq: seq->sequence, data: item, cmp_func: compare_items, NULL); |
883 | |
884 | insert_iter = g_sequence_insert_sorted (seq: seq->sequence, data: item, cmp_func: compare_items, NULL); |
885 | |
886 | g_assert (search_iter == g_sequence_iter_next (insert_iter)); |
887 | |
888 | g_queue_insert_sorted (queue: seq->queue, data: insert_iter, func: 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: seq->sequence, cmp_func: compare_items, NULL); |
898 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
899 | |
900 | check_sorted (info: seq); |
901 | |
902 | item = new_item (seq); |
903 | search_iter = g_sequence_search_iter (seq: seq->sequence, |
904 | data: item, |
905 | iter_cmp: (GSequenceIterCompareFunc)compare_iters, cmp_data: seq->sequence); |
906 | |
907 | insert_iter = g_sequence_insert_sorted (seq: seq->sequence, data: item, cmp_func: compare_items, NULL); |
908 | |
909 | g_assert (search_iter == g_sequence_iter_next (insert_iter)); |
910 | |
911 | g_queue_insert_sorted (queue: seq->queue, data: insert_iter, func: 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: seq->sequence, cmp_func: compare_items, NULL); |
921 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
922 | |
923 | check_sorted (info: seq); |
924 | |
925 | item = new_item (seq); |
926 | insert_iter = g_sequence_insert_sorted (seq: seq->sequence, data: item, cmp_func: compare_items, NULL); |
927 | g_queue_insert_sorted (queue: seq->queue, data: insert_iter, func: compare_iters, NULL); |
928 | |
929 | lookup_iter = g_sequence_lookup (seq: seq->sequence, data: item, cmp_func: 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: seq->sequence, cmp_func: compare_items, NULL); |
940 | g_queue_sort (queue: seq->queue, compare_func: compare_iters, NULL); |
941 | |
942 | check_sorted (info: seq); |
943 | |
944 | item = new_item (seq); |
945 | insert_iter = g_sequence_insert_sorted (seq: seq->sequence, data: item, cmp_func: compare_items, NULL); |
946 | g_queue_insert_sorted (queue: seq->queue, data: insert_iter, func: compare_iters, NULL); |
947 | |
948 | lookup_iter = g_sequence_lookup_iter (seq: seq->sequence, data: item, |
949 | iter_cmp: (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: &link); |
962 | |
963 | if (!g_sequence_iter_is_end (iter)) |
964 | { |
965 | Item *item; |
966 | int i; |
967 | |
968 | check_integrity (info: seq); |
969 | |
970 | /* Test basic functionality */ |
971 | item = new_item (seq); |
972 | g_sequence_set (iter, data: 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, data: new_item (seq)); |
978 | |
979 | check_integrity (info: seq); |
980 | |
981 | g_sequence_set (iter, data: 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: seq->sequence, pos: 0); |
992 | |
993 | g_assert (g_sequence_iter_is_begin (iter)); |
994 | |
995 | check_integrity (info: seq); |
996 | |
997 | if (g_sequence_get_length (seq: 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: seq->sequence); |
1013 | |
1014 | iter = g_sequence_get_iter_at_pos (seq: seq->sequence, pos: 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: seq->sequence, data: new_item (seq)); |
1035 | iter2 = g_sequence_append (seq: seq->sequence, data: new_item (seq)); |
1036 | iter3 = g_sequence_append (seq: seq->sequence, data: new_item (seq)); |
1037 | |
1038 | end = g_sequence_get_end_iter (seq: 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 (queue: seq->queue, data: iter1); |
1046 | g_queue_push_tail (queue: seq->queue, data: iter2); |
1047 | g_queue_push_tail (queue: seq->queue, data: iter3); |
1048 | } |
1049 | break; |
1050 | case ITER_PREV: |
1051 | { |
1052 | GSequenceIter *iter1, *iter2, *iter3, *begin; |
1053 | |
1054 | iter1 = g_sequence_prepend (seq: seq->sequence, data: new_item (seq)); |
1055 | iter2 = g_sequence_prepend (seq: seq->sequence, data: new_item (seq)); |
1056 | iter3 = g_sequence_prepend (seq: seq->sequence, data: new_item (seq)); |
1057 | |
1058 | begin = g_sequence_get_begin_iter (seq: 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 (queue: seq->queue, data: iter1); |
1067 | g_queue_push_head (queue: seq->queue, data: iter2); |
1068 | g_queue_push_head (queue: seq->queue, data: iter3); |
1069 | } |
1070 | break; |
1071 | case ITER_GET_POSITION: |
1072 | { |
1073 | GList *link; |
1074 | GSequenceIter *iter = get_random_iter (seq, link: &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: 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, delta: 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, delta: 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, link: &link1); |
1116 | GSequenceIter *iter2 = get_random_iter (seq, link: &link2); |
1117 | |
1118 | int cmp = g_sequence_iter_compare (a: iter1, b: iter2); |
1119 | int pos1 = queue_link_index (seq, link: link1); |
1120 | int pos2 = queue_link_index (seq, link: 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 (a: iter1, b: 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 (begin: iter1, end: 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 (info: seq); |
1172 | } |
1173 | |
1174 | for (k = 0; k < N_SEQUENCES; ++k) |
1175 | { |
1176 | g_queue_free (queue: sequences[k].queue); |
1177 | g_sequence_free (seq: 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, delta: 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, delta: 5); |
1226 | g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5); |
1227 | |
1228 | iter = g_sequence_iter_move (iter, delta: -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, delta: -5); |
1233 | g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5); |
1234 | |
1235 | iter = g_sequence_iter_move (iter, delta: 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 (a: g_sequence_get (iter: a), |
1263 | b: g_sequence_get (iter: b), |
1264 | userdata: 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 | cmp_func: compare, NULL); |
1281 | |
1282 | g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()), |
1283 | iter_cmp: compare_iter, NULL); |
1284 | } |
1285 | |
1286 | g_sequence_check (sequence: 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 (sequence: 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 (sequence: 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 (sequence: seq); |
1321 | } |
1322 | |
1323 | g_sequence_sort (seq, cmp_func: 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 (sequence: seq); |
1334 | |
1335 | i++; |
1336 | } |
1337 | |
1338 | for (i = N_ITEMS - 1; i >= 0; --i) |
1339 | { |
1340 | g_sequence_check (sequence: 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 (iter: iters[i], cmp_func: 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 (sequence: 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 (iter: g_sequence_iter_prev (iter: 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 | gsize i; |
1391 | guint32 seed; |
1392 | gchar *path; |
1393 | |
1394 | g_test_init (argc: &argc, argv: &argv, NULL); |
1395 | |
1396 | /* Standalone tests */ |
1397 | g_test_add_func (testpath: "/sequence/out-of-range-jump" , test_func: test_out_of_range_jump); |
1398 | g_test_add_func (testpath: "/sequence/iter-move" , test_func: test_iter_move); |
1399 | g_test_add_func (testpath: "/sequence/insert-sorted-non-pointer" , test_func: test_insert_sorted_non_pointer); |
1400 | g_test_add_func (testpath: "/sequence/stable-sort" , test_func: test_stable_sort); |
1401 | g_test_add_func (testpath: "/sequence/is_empty" , test_func: test_empty); |
1402 | |
1403 | /* Regression tests */ |
1404 | for (i = 0; i < G_N_ELEMENTS (seeds); ++i) |
1405 | { |
1406 | path = g_strdup_printf (format: "/sequence/random/seed:%lu" , seeds[i]); |
1407 | g_test_add_data_func (testpath: path, GUINT_TO_POINTER (seeds[i]), test_func: run_random_tests); |
1408 | g_free (mem: path); |
1409 | } |
1410 | |
1411 | /* New random seed */ |
1412 | seed = g_test_rand_int_range (begin: 0, G_MAXINT); |
1413 | path = g_strdup_printf (format: "/sequence/random/seed:%u" , seed); |
1414 | g_test_add_data_func (testpath: path, GUINT_TO_POINTER (seed), test_func: run_random_tests); |
1415 | g_free (mem: path); |
1416 | |
1417 | return g_test_run (); |
1418 | } |
1419 | |