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