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