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 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   int           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_print ("%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 (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 (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_print ("%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 /* A version of g_queue_insert_before() that appends if link is NULL */
 414 static void
 415 queue_insert_before (SequenceInfo *seq, GList *link, gpointer data)
 416 {
 417   if (link)
 418     g_queue_insert_before (seq->queue, link, data);
 419   else
 420     g_queue_push_tail (seq->queue, data);
 421 }
 422
 423 static void
 424 run_random_tests (gconstpointer d)
 425 {
 426   guint32 seed = GPOINTER_TO_UINT (d);
 427 #define N_ITERATIONS 60000
 428 #define N_SEQUENCES 8
 429 #define N_TIMES 24
 430
 431   SequenceInfo sequences[N_SEQUENCES];
 432   int k;
 433
 434 #if 0
 435   g_print ("    seed: %u\n", seed);
 436 #endif
 437
 438   g_random_set_seed (seed);
 439
 440   for (k = 0; k < N_SEQUENCES; ++k)
 441     {
 442       sequences[k].queue = g_queue_new ();
 443       sequences[k].sequence = g_sequence_new (free_item);
 444       sequences[k].n_items = 0;
 445     }
 446
 447 #define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])
 448
 449   for (k = 0; k < N_ITERATIONS; ++k)
 450     {
 451       int i;
 452       SequenceInfo *seq = RANDOM_SEQUENCE();
 453       int op = g_random_int_range (0, N_OPS);
 454
 455 #if 0
 456       g_print ("%d on %p\n", op, seq);
 457 #endif
 458
 459       switch (op)
 460         {
 461         case NEW:
 462         case FREE:
 463           {
 464             g_queue_free (seq->queue);
 465             g_sequence_free (seq->sequence);
 466
 467             g_assert (seq->n_items == 0);
 468
 469             seq->queue = g_queue_new ();
 470             seq->sequence = g_sequence_new (free_item);
 471
 472             check_integrity (seq);
 473           }
 474           break;
 475         case GET_LENGTH:
 476           {
 477             int slen = g_sequence_get_length (seq->sequence);
 478             int qlen = g_queue_get_length (seq->queue);
 479
 480             g_assert (slen == qlen);
 481           }
 482           break;
 483         case FOREACH:
 484           {
 485             GList *link = seq->queue->head;
 486             g_sequence_foreach (seq->sequence, seq_foreach, &link);
 487             g_assert (link == NULL);
 488           }
 489           break;
 490         case FOREACH_RANGE:
 491           {
 492             GSequenceIter *begin_iter, *end_iter;
 493             GList *begin_link, *end_link;
 494
 495             get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
 496
 497             check_integrity (seq);
 498
 499             g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);
 500
 501             g_assert (begin_link == end_link);
 502           }
 503           break;
 504         case SORT:
 505           {
 506             dump_info (seq);
 507
 508             g_sequence_sort (seq->sequence, compare_items, NULL);
 509             g_queue_sort (seq->queue, compare_iters, NULL);
 510
 511             check_sorted (seq);
 512
 513             dump_info (seq);
 514           }
 515           break;
 516         case SORT_ITER:
 517           {
 518             check_integrity (seq);
 519             g_sequence_sort_iter (seq->sequence,
 520                                   (GSequenceIterCompareFunc)compare_iters, seq->sequence);
 521             g_queue_sort (seq->queue, compare_iters, NULL);
 522             check_sorted (seq);
 523           }
 524           break;
 525
 526           /* Getting iters */
 527         case GET_END_ITER:
 528         case GET_BEGIN_ITER:
 529           {
 530             GSequenceIter *begin_iter;
 531             GSequenceIter *end_iter;
 532             GSequenceIter *penultimate_iter;
 533
 534             begin_iter = g_sequence_get_begin_iter (seq->sequence);
 535             check_integrity (seq);
 536
 537             end_iter = g_sequence_get_end_iter (seq->sequence);
 538             check_integrity (seq);
 539
 540             penultimate_iter = g_sequence_iter_prev (end_iter);
 541             check_integrity (seq);
 542
 543             if (g_sequence_get_length (seq->sequence) > 0)
 544               {
 545                 g_assert (seq->queue->head);
 546                 g_assert (seq->queue->head->data == begin_iter);
 547                 g_assert (seq->queue->tail);
 548                 g_assert (seq->queue->tail->data == penultimate_iter);
 549               }
 550             else
 551               {
 552                 g_assert (penultimate_iter == end_iter);
 553                 g_assert (begin_iter == end_iter);
 554                 g_assert (penultimate_iter == begin_iter);
 555                 g_assert (seq->queue->head == NULL);
 556                 g_assert (seq->queue->tail == NULL);
 557               }
 558           }
 559           break;
 560         case GET_ITER_AT_POS:
 561           {
 562             int i;
 563
 564             g_assert (g_queue_get_length (seq->queue) == g_sequence_get_length (seq->sequence));
 565
 566             for (i = 0; i < 10; ++i)
 567               {
 568                 int pos = get_random_position (seq);
 569                 GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
 570                 GList *link = g_queue_peek_nth_link (seq->queue, pos);
 571                 check_integrity (seq);
 572                 if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
 573                   {
 574                     g_assert (iter == g_sequence_get_end_iter (seq->sequence));
 575                     g_assert (link == NULL);
 576                   }
 577                 else
 578                   {
 579                     g_assert (link);
 580                     g_assert (link->data == iter);
 581                   }
 582               }
 583           }
 584           break;
 585         case APPEND:
 586           {
 587             for (i = 0; i < 10; ++i)
 588               {
 589                 GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
 590                 g_queue_push_tail (seq->queue, iter);
 591               }
 592           }
 593           break;
 594         case PREPEND:
 595           {
 596             for (i = 0; i < 10; ++i)
 597               {
 598                 GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
 599                 g_queue_push_head (seq->queue, iter);
 600               }
 601           }
 602           break;
 603         case INSERT_BEFORE:
 604           {
 605             for (i = 0; i < 10; ++i)
 606               {
 607                 GList *link;
 608                 GSequenceIter *iter = get_random_iter (seq, &link);
 609                 GSequenceIter *new_iter;
 610                 check_integrity (seq);
 611
 612                 new_iter = g_sequence_insert_before (iter, new_item (seq));
 613
 614                 queue_insert_before (seq, link, new_iter);
 615               }
 616           }
 617           break;
 618         case MOVE:
 619           {
 620             GList *link1, *link2;
 621             SequenceInfo *seq1 = RANDOM_SEQUENCE();
 622             SequenceInfo *seq2 = RANDOM_SEQUENCE();
 623             GSequenceIter *iter1 = get_random_iter (seq1, &link1);
 624             GSequenceIter *iter2 = get_random_iter (seq2, &link2);
 625
 626             if (!g_sequence_iter_is_end (iter1))
 627               {
 628                 g_sequence_move (iter1, iter2);
 629
 630                 if (!link2)
 631                   g_assert (g_sequence_iter_is_end (iter2));
 632
 633                 queue_insert_before (seq2, link2, link1->data);
 634
 635                 g_queue_delete_link (seq1->queue, link1);
 636
 637                 get_item (iter1)->seq = seq2;
 638
 639                 seq1->n_items--;
 640                 seq2->n_items++;
 641               }
 642
 643             check_integrity (seq);
 644
 645             iter1 = get_random_iter (seq, NULL);
 646
 647             /* Moving an iter to itself should have no effect */
 648             if (!g_sequence_iter_is_end (iter1))
 649               g_sequence_move (iter1, iter1);
 650           }
 651           break;
 652         case SWAP:
 653           {
 654             GList *link1, *link2;
 655             SequenceInfo *seq1 = RANDOM_SEQUENCE();
 656             SequenceInfo *seq2 = RANDOM_SEQUENCE();
 657             GSequenceIter *iter1 = get_random_iter (seq1, &link1);
 658             GSequenceIter *iter2 = get_random_iter (seq2, &link2);
 659
 660             if (!g_sequence_iter_is_end (iter1) &&
 661                 !g_sequence_iter_is_end (iter2))
 662               {
 663                 gpointer tmp;
 664
 665                 g_sequence_swap (iter1, iter2);
 666
 667                 get_item (iter1)->seq = seq2;
 668                 get_item (iter2)->seq = seq1;
 669
 670                 tmp = link1->data;
 671                 link1->data = link2->data;
 672                 link2->data = tmp;
 673               }
 674           }
 675           break;
 676         case INSERT_SORTED:
 677           {
 678             int i;
 679             dump_info (seq);
 680
 681             g_sequence_sort (seq->sequence, compare_items, NULL);
 682             g_queue_sort (seq->queue, compare_iters, NULL);
 683
 684             check_sorted (seq);
 685
 686             for (i = 0; i < N_TIMES; ++i)
 687               {
 688                 GSequenceIter *iter =
 689                   g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
 690
 691                 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
 692               }
 693
 694             check_sorted (seq);
 695
 696             dump_info (seq);
 697           }
 698           break;
 699         case INSERT_SORTED_ITER:
 700           {
 701             int i;
 702             dump_info (seq);
 703
 704             g_sequence_sort (seq->sequence, compare_items, NULL);
 705             g_queue_sort (seq->queue, compare_iters, NULL);
 706
 707             check_sorted (seq);
 708
 709             for (i = 0; i < N_TIMES; ++i)
 710               {
 711                 GSequenceIter *iter;
 712
 713                 iter = g_sequence_insert_sorted_iter (seq->sequence,
 714                                                       new_item (seq),
 715                                                       (GSequenceIterCompareFunc)compare_iters,
 716                                                       seq->sequence);
 717
 718                 g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
 719               }
 720
 721             check_sorted (seq);
 722
 723             dump_info (seq);
 724           }
 725           break;
 726         case SORT_CHANGED:
 727           {
 728             int i;
 729
 730             g_sequence_sort (seq->sequence, compare_items, NULL);
 731             g_queue_sort (seq->queue, compare_iters, NULL);
 732
 733             check_sorted (seq);
 734
 735             for (i = 0; i < N_TIMES; ++i)
 736               {
 737                 GList *link;
 738                 GSequenceIter *iter = get_random_iter (seq, &link);
 739
 740                 if (!g_sequence_iter_is_end (iter))
 741                   {
 742                     g_sequence_set (iter, new_item (seq));
 743                     g_sequence_sort_changed (iter, compare_items, NULL);
 744
 745                     g_queue_delete_link (seq->queue, link);
 746                     g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
 747                   }
 748
 749                 check_sorted (seq);
 750               }
 751           }
 752           break;
 753         case SORT_CHANGED_ITER:
 754           {
 755             int i;
 756
 757             g_sequence_sort (seq->sequence, compare_items, NULL);
 758             g_queue_sort (seq->queue, compare_iters, NULL);
 759
 760             check_sorted (seq);
 761
 762             for (i = 0; i < N_TIMES; ++i)
 763               {
 764                 GList *link;
 765                 GSequenceIter *iter = get_random_iter (seq, &link);
 766
 767                 if (!g_sequence_iter_is_end (iter))
 768                   {
 769                     g_sequence_set (iter, new_item (seq));
 770                     g_sequence_sort_changed_iter (iter,
 771                                                   (GSequenceIterCompareFunc)compare_iters, seq->sequence);
 772
 773                     g_queue_delete_link (seq->queue, link);
 774                     g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
 775                   }
 776
 777                 check_sorted (seq);
 778               }
 779           }
 780           break;
 781         case REMOVE:
 782           {
 783             int i;
 784
 785             for (i = 0; i < N_TIMES; ++i)
 786               {
 787                 GList *link;
 788                 GSequenceIter *iter = get_random_iter (seq, &link);
 789
 790                 if (!g_sequence_iter_is_end (iter))
 791                   {
 792                     g_sequence_remove (iter);
 793                     g_queue_delete_link (seq->queue, link);
 794                   }
 795               }
 796           }
 797           break;
 798         case REMOVE_RANGE:
 799           {
 800             GSequenceIter *begin_iter, *end_iter;
 801             GList *begin_link, *end_link;
 802             GList *list;
 803
 804             get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
 805
 806             g_sequence_remove_range (begin_iter, end_iter);
 807
 808             list = begin_link;
 809             while (list != end_link)
 810               {
 811                 GList *next = list->next;
 812
 813                 g_queue_delete_link (seq->queue, list);
 814
 815                 list = next;
 816               }
 817           }
 818           break;
 819         case MOVE_RANGE:
 820           {
 821             SequenceInfo *src = RANDOM_SEQUENCE();
 822             SequenceInfo *dst = RANDOM_SEQUENCE();
 823
 824             GSequenceIter *begin_iter, *end_iter;
 825             GList *begin_link, *end_link;
 826
 827             GSequenceIter *dst_iter;
 828             GList *dst_link;
 829
 830             GList *list;
 831
 832             g_assert (src->queue);
 833             g_assert (dst->queue);
 834
 835             get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
 836             dst_iter = get_random_iter (dst, &dst_link);
 837
 838             g_sequence_move_range (dst_iter, begin_iter, end_iter);
 839
 840             if (dst_link == begin_link || (src == dst && dst_link == end_link))
 841               {
 842                 check_integrity (src);
 843                 check_integrity (dst);
 844                 break;
 845               }
 846
 847             if (queue_link_index (src, begin_link) >=
 848                 queue_link_index (src, end_link))
 849               {
 850                 break;
 851               }
 852
 853             if (src == dst &&
 854                 queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
 855                 queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
 856               {
 857                 break;
 858               }
 859
 860             list = begin_link;
 861             while (list != end_link)
 862               {
 863                 GList *next = list->next;
 864                 Item *item = get_item (list->data);
 865
 866                 g_assert (dst->queue);
 867                 queue_insert_before (dst, dst_link, list->data);
 868                 g_queue_delete_link (src->queue, list);
 869
 870                 g_assert (item->seq == src);
 871
 872                 src->n_items--;
 873                 dst->n_items++;
 874                 item->seq = dst;
 875
 876                 list = next;
 877               }
 878           }
 879           break;
 880         case SEARCH:
 881           {
 882             Item *item;
 883             GSequenceIter *search_iter;
 884             GSequenceIter *insert_iter;
 885
 886             g_sequence_sort (seq->sequence, compare_items, NULL);
 887             g_queue_sort (seq->queue, compare_iters, NULL);
 888
 889             check_sorted (seq);
 890
 891             item = new_item (seq);
 892             search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);
 893
 894             insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
 895
 896             g_assert (search_iter == g_sequence_iter_next (insert_iter));
 897
 898             g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
 899           }
 900           break;
 901         case SEARCH_ITER:
 902           {
 903             Item *item;
 904             GSequenceIter *search_iter;
 905             GSequenceIter *insert_iter;
 906
 907             g_sequence_sort (seq->sequence, compare_items, NULL);
 908             g_queue_sort (seq->queue, compare_iters, NULL);
 909
 910             check_sorted (seq);
 911
 912             item = new_item (seq);
 913             search_iter = g_sequence_search_iter (seq->sequence,
 914                                                   item,
 915                                                   (GSequenceIterCompareFunc)compare_iters, seq->sequence);
 916
 917             insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
 918
 919             g_assert (search_iter == g_sequence_iter_next (insert_iter));
 920
 921             g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
 922           }
 923           break;
 924         case LOOKUP:
 925           {
 926             Item *item;
 927             GSequenceIter *lookup_iter;
 928             GSequenceIter *insert_iter;
 929
 930             g_sequence_sort (seq->sequence, compare_items, NULL);
 931             g_queue_sort (seq->queue, compare_iters, NULL);
 932
 933             check_sorted (seq);
 934
 935             item = new_item (seq);
 936             insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
 937             g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
 938
 939             lookup_iter = g_sequence_lookup (seq->sequence, item, simple_items_cmp, NULL);
 940             g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
 941           }
 942           break;
 943         case LOOKUP_ITER:
 944           {
 945             Item *item;
 946             GSequenceIter *lookup_iter;
 947             GSequenceIter *insert_iter;
 948
 949             g_sequence_sort (seq->sequence, compare_items, NULL);
 950             g_queue_sort (seq->queue, compare_iters, NULL);
 951
 952             check_sorted (seq);
 953
 954             item = new_item (seq);
 955             insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
 956             g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
 957
 958             lookup_iter = g_sequence_lookup_iter (seq->sequence, item,
 959                 (GSequenceIterCompareFunc) simple_iters_cmp, NULL);
 960             g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
 961           }
 962           break;
 963
 964           /* dereferencing */
 965         case GET:
 966         case SET:
 967           {
 968             GSequenceIter *iter;
 969             GList *link;
 970
 971             iter = get_random_iter (seq, &link);
 972
 973             if (!g_sequence_iter_is_end (iter))
 974               {
 975                 Item *item;
 976                 int i;
 977
 978                 check_integrity (seq);
 979
 980                 /* Test basic functionality */
 981                 item = new_item (seq);
 982                 g_sequence_set (iter, item);
 983                 g_assert (g_sequence_get (iter) == item);
 984
 985                 /* Make sure that existing items are freed */
 986                 for (i = 0; i < N_TIMES; ++i)
 987                   g_sequence_set (iter, new_item (seq));
 988
 989                 check_integrity (seq);
 990
 991                 g_sequence_set (iter, new_item (seq));
 992               }
 993           }
 994           break;
 995
 996           /* operations on GSequenceIter * */
 997         case ITER_IS_BEGIN:
 998           {
 999             GSequenceIter *iter;
1000
1001             iter = g_sequence_get_iter_at_pos (seq->sequence, 0);
1002
1003             g_assert (g_sequence_iter_is_begin (iter));
1004
1005             check_integrity (seq);
1006
1007             if (g_sequence_get_length (seq->sequence) > 0)
1008               {
1009                 g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
1010               }
1011             else
1012               {
1013                 g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
1014               }
1015
1016             g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
1017           }
1018           break;
1019         case ITER_IS_END:
1020           {
1021             GSequenceIter *iter;
1022             int len = g_sequence_get_length (seq->sequence);
1023
1024             iter = g_sequence_get_iter_at_pos (seq->sequence, len);
1025
1026             g_assert (g_sequence_iter_is_end (iter));
1027
1028             if (len > 0)
1029               {
1030                 g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1031               }
1032             else
1033               {
1034                 g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
1035               }
1036
1037             g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
1038           }
1039           break;
1040         case ITER_NEXT:
1041           {
1042             GSequenceIter *iter1, *iter2, *iter3, *end;
1043
1044             iter1 = g_sequence_append (seq->sequence, new_item (seq));
1045             iter2 = g_sequence_append (seq->sequence, new_item (seq));
1046             iter3 = g_sequence_append (seq->sequence, new_item (seq));
1047
1048             end = g_sequence_get_end_iter (seq->sequence);
1049
1050             g_assert (g_sequence_iter_next (iter1) == iter2);
1051             g_assert (g_sequence_iter_next (iter2) == iter3);
1052             g_assert (g_sequence_iter_next (iter3) == end);
1053             g_assert (g_sequence_iter_next (end) == end);
1054
1055             g_queue_push_tail (seq->queue, iter1);
1056             g_queue_push_tail (seq->queue, iter2);
1057             g_queue_push_tail (seq->queue, iter3);
1058           }
1059           break;
1060         case ITER_PREV:
1061           {
1062             GSequenceIter *iter1, *iter2, *iter3, *begin;
1063
1064             iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
1065             iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
1066             iter3 = g_sequence_prepend (seq->sequence, new_item (seq));
1067
1068             begin = g_sequence_get_begin_iter (seq->sequence);
1069
1070             g_assert (g_sequence_iter_prev (iter1) == iter2);
1071             g_assert (g_sequence_iter_prev (iter2) == iter3);
1072             g_assert (iter3 == begin);
1073             g_assert (g_sequence_iter_prev (iter3) == begin);
1074             g_assert (g_sequence_iter_prev (begin) == begin);
1075
1076             g_queue_push_head (seq->queue, iter1);
1077             g_queue_push_head (seq->queue, iter2);
1078             g_queue_push_head (seq->queue, iter3);
1079           }
1080           break;
1081         case ITER_GET_POSITION:
1082           {
1083             GList *link;
1084             GSequenceIter *iter = get_random_iter (seq, &link);
1085
1086             g_assert (g_sequence_iter_get_position (iter) ==
1087                       queue_link_index (seq, link));
1088           }
1089           break;
1090         case ITER_MOVE:
1091           {
1092             int len = g_sequence_get_length (seq->sequence);
1093             GSequenceIter *iter;
1094             int pos;
1095
1096             iter = get_random_iter (seq, NULL);
1097             pos = g_sequence_iter_get_position (iter);
1098             iter = g_sequence_iter_move (iter, len - pos);
1099             g_assert (g_sequence_iter_is_end (iter));
1100
1101
1102             iter = get_random_iter (seq, NULL);
1103             pos = g_sequence_iter_get_position (iter);
1104             while (pos < len)
1105               {
1106                 g_assert (!g_sequence_iter_is_end (iter));
1107                 pos++;
1108                 iter = g_sequence_iter_move (iter, 1);
1109               }
1110             g_assert (g_sequence_iter_is_end (iter));
1111           }
1112           break;
1113         case ITER_GET_SEQUENCE:
1114           {
1115             GSequenceIter *iter = get_random_iter (seq, NULL);
1116
1117             g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
1118           }
1119           break;
1120
1121           /* search */
1122         case ITER_COMPARE:
1123           {
1124             GList *link1, *link2;
1125             GSequenceIter *iter1 = get_random_iter (seq, &link1);
1126             GSequenceIter *iter2 = get_random_iter (seq, &link2);
1127
1128             int cmp = g_sequence_iter_compare (iter1, iter2);
1129             int pos1 = queue_link_index (seq, link1);
1130             int pos2 = queue_link_index (seq, link2);
1131
1132             if (cmp == 0)
1133               {
1134                 g_assert (pos1 == pos2);
1135               }
1136             else if (cmp < 0)
1137               {
1138                 g_assert (pos1 < pos2);
1139               }
1140             else
1141               {
1142                 g_assert (pos1 > pos2);
1143               }
1144           }
1145           break;
1146         case RANGE_GET_MIDPOINT:
1147           {
1148             GSequenceIter *iter1 = get_random_iter (seq, NULL);
1149             GSequenceIter *iter2 = get_random_iter (seq, NULL);
1150             GSequenceIter *iter3;
1151             int cmp;
1152
1153             cmp = g_sequence_iter_compare (iter1, iter2);
1154
1155             if (cmp > 0)
1156               {
1157                 GSequenceIter *tmp;
1158
1159                 tmp = iter1;
1160                 iter1 = iter2;
1161                 iter2 = tmp;
1162               }
1163
1164             iter3 = g_sequence_range_get_midpoint (iter1, iter2);
1165
1166             if (cmp == 0)
1167               {
1168                 g_assert (iter3 == iter1);
1169                 g_assert (iter3 == iter2);
1170               }
1171
1172             g_assert (g_sequence_iter_get_position (iter3) >=
1173                       g_sequence_iter_get_position (iter1));
1174             g_assert (g_sequence_iter_get_position (iter2) >=
1175                       g_sequence_iter_get_position (iter3));
1176           }
1177           break;
1178
1179         }
1180
1181       check_integrity (seq);
1182     }
1183
1184   for (k = 0; k < N_SEQUENCES; ++k)
1185     {
1186       g_queue_free (sequences[k].queue);
1187       g_sequence_free (sequences[k].sequence);
1188       sequences[k].n_items = 0;
1189     }
1190 }
1191
1192 /* Random seeds known to have failed at one point
1193  */
1194 static gulong seeds[] =
1195   {
1196     825541564u,
1197     801678400u,
1198     1477639090u,
1199     3369132895u,
1200     1192944867u,
1201     770458294u,
1202     1099575817u,
1203     590523467u,
1204     3583571454u,
1205     579241222u
1206   };
1207
1208 /* Single, stand-alone tests */
1209
1210 static void
1211 test_out_of_range_jump (void)
1212 {
1213   GSequence *seq = g_sequence_new (NULL);
1214   GSequenceIter *iter = g_sequence_get_begin_iter (seq);
1215
1216   g_sequence_iter_move (iter, 5);
1217
1218   g_assert (g_sequence_iter_is_begin (iter));
1219   g_assert (g_sequence_iter_is_end (iter));
1220
1221   g_sequence_free (seq);
1222 }
1223
1224 static void
1225 test_iter_move (void)
1226 {
1227   GSequence *seq = g_sequence_new (NULL);
1228   GSequenceIter *iter;
1229   gint i;
1230
1231   for (i = 0; i < 10; ++i)
1232     g_sequence_append (seq, GINT_TO_POINTER (i));
1233
1234   iter = g_sequence_get_begin_iter (seq);
1235   iter = g_sequence_iter_move (iter, 5);
1236   g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1237
1238   iter = g_sequence_iter_move (iter, -10);
1239   g_assert (g_sequence_iter_is_begin (iter));
1240
1241   iter = g_sequence_get_end_iter (seq);
1242   iter = g_sequence_iter_move (iter, -5);
1243   g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);
1244
1245   iter = g_sequence_iter_move (iter, 10);
1246   g_assert (g_sequence_iter_is_end (iter));
1247
1248   g_sequence_free (seq);
1249 }
1250
1251 static int
1252 compare (gconstpointer a, gconstpointer b, gpointer userdata)
1253 {
1254   int ai, bi;
1255
1256   ai = GPOINTER_TO_INT (a);
1257   bi = GPOINTER_TO_INT (b);
1258
1259   if (ai < bi)
1260     return -1;
1261   else if (ai > bi)
1262     return 1;
1263   else
1264     return 0;
1265 }
1266
1267 static int
1268 compare_iter (GSequenceIter *a,
1269               GSequenceIter *b,
1270               gpointer data)
1271 {
1272   return compare (g_sequence_get (a),
1273                   g_sequence_get (b),
1274                   data);
1275 }
1276
1277 static void
1278 test_insert_sorted_non_pointer (void)
1279 {
1280   int i;
1281
1282   for (i = 0; i < 10; i++)
1283     {
1284       GSequence *seq = g_sequence_new (NULL);
1285       int j;
1286
1287       for (j = 0; j < 10000; j++)
1288         {
1289           g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
1290                                     compare, NULL);
1291
1292           g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
1293                                          compare_iter, NULL);
1294         }
1295
1296       g_sequence_check (seq);
1297
1298       g_sequence_free (seq);
1299     }
1300 }
1301
1302 static void
1303 test_stable_sort (void)
1304 {
1305   int i;
1306   GSequence *seq = g_sequence_new (NULL);
1307
1308 #define N_ITEMS 1000
1309
1310   GSequenceIter *iters[N_ITEMS];
1311   GSequenceIter *iter;
1312
1313   for (i = 0; i < N_ITEMS; ++i)
1314     {
1315       iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
1316       g_sequence_check (seq);
1317       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1318    }
1319
1320   i = 0;
1321   iter = g_sequence_get_begin_iter (seq);
1322   g_assert (g_sequence_iter_get_sequence (iter) == seq);
1323   g_sequence_check (seq);
1324   while (!g_sequence_iter_is_end (iter))
1325     {
1326       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1327       g_assert (iters[i++] == iter);
1328
1329       iter = g_sequence_iter_next (iter);
1330       g_sequence_check (seq);
1331     }
1332
1333   g_sequence_sort (seq, compare, NULL);
1334
1335   i = 0;
1336   iter = g_sequence_get_begin_iter (seq);
1337   while (!g_sequence_iter_is_end (iter))
1338     {
1339       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1340       g_assert (iters[i] == iter);
1341
1342       iter = g_sequence_iter_next (iter);
1343       g_sequence_check (seq);
1344
1345       i++;
1346     }
1347
1348   for (i = N_ITEMS - 1; i >= 0; --i)
1349     {
1350       g_sequence_check (seq);
1351       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
1352       g_assert (g_sequence_get_end_iter (seq) != iters[i]);
1353       g_sequence_sort_changed (iters[i], compare, NULL);
1354     }
1355
1356   i = 0;
1357   iter = g_sequence_get_begin_iter (seq);
1358   while (!g_sequence_iter_is_end (iter))
1359     {
1360       g_assert (iters[i++] == iter);
1361
1362       iter = g_sequence_iter_next (iter);
1363       g_sequence_check (seq);
1364     }
1365
1366   g_sequence_free (seq);
1367 }
1368
1369 int
1370 main (int argc,
1371       char **argv)
1372 {
1373   gint i;
1374   guint32 seed;
1375   gchar *path;
1376
1377   g_test_init (&argc, &argv, NULL);
1378
1379   /* Standalone tests */
1380   g_test_add_func ("/sequence/out-of-range-jump", test_out_of_range_jump);
1381   g_test_add_func ("/sequence/iter-move", test_iter_move);
1382   g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
1383   g_test_add_func ("/sequence/stable-sort", test_stable_sort);
1384
1385   /* Regression tests */
1386   for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
1387     {
1388       path = g_strdup_printf ("/sequence/random/seed:%lu", seeds[i]);
1389       g_test_add_data_func (path, GUINT_TO_POINTER (seeds[i]), run_random_tests);
1390       g_free (path);
1391     }
1392
1393   /* New random seed */
1394   seed = g_test_rand_int_range (0, G_MAXINT);
1395   path = g_strdup_printf ("/sequence/random/seed:%u", seed);
1396   g_test_add_data_func (path, GUINT_TO_POINTER (seed), run_random_tests);
1397   g_free (path);
1398
1399   return g_test_run ();
1400 }
1401