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