tests/sequence-test.c

   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