tests/sequence-test.c

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