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