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