1 /*

     2 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 *

    16 */

    17 

    18 #include <stdio.h>

    19 #include <glib.h>

    20 #include <stdlib.h>

    21 #ifdef __SYMBIAN32__

    22 #include "mrt2_glib2_test.h"

    23 #endif /*__SYMBIAN32__*/

    24 /* Keep this in sync with gsequence.c !!! */

    25 typedef struct _GSequenceNode GSequenceNode;

    26 

    27 struct _GSequence

    28 {

    29   GSequenceNode *       end_node;

    30   GDestroyNotify        data_destroy_notify;

    31   gboolean              access_prohibited;

    32   GSequence *           real_sequence;

    33 };

    34 

    35 struct _GSequenceNode

    36 {

    37   gint                  n_nodes;

    38   GSequenceNode *       parent;

    39   GSequenceNode *       left;

    40   GSequenceNode *       right;

    41   gpointer              data;

    42 };

    43 

    44 static guint

    45 get_priority (GSequenceNode *node)

    46 {

    47   guint key = GPOINTER_TO_UINT (node);

    48 

    49   key = (key << 15) - key - 1;

    50   key = key ^ (key >> 12);

    51   key = key + (key << 2);

    52   key = key ^ (key >> 4);

    53   key = key + (key << 3) + (key << 11);

    54   key = key ^ (key >> 16);

    55 

    56   return key? key : 1;

    57 }

    58       

    59 static void

    60 check_node (GSequenceNode *node)

    61 {

    62   if (node)

    63     {

    64       g_assert (node->parent != node);

    65       if (node->parent)

    66         g_assert (node->parent->left == node || node->parent->right == node);

    67       g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));

    68       if (node->left)

    69           g_assert (get_priority (node) >= get_priority (node->left));

    70       if (node->right)

    71           g_assert (get_priority (node) >= get_priority (node->right));

    72       check_node (node->left);

    73       check_node (node->right);

    74     }

    75 }

    76 

    77 void

    78 g_sequence_check (GSequence *seq)

    79 {

    80   GSequenceNode *node = seq->end_node;

    81 

    82   while (node->parent)

    83     node = node->parent;

    84 

    85   check_node (node);

    86 

    87   while (node->right)

    88     node = node->right;

    89 

    90   g_assert (seq->end_node == node);

    91   g_assert (node->data == seq);

    92 

    93 }

    94 

    95 //undefs done here as some of these enums are already defined in s60 environ

    96 #ifdef __SYMBIAN32__

    97 #undef NEW 

    98 #undef FREE

    99 #undef GET_LENGTH

   100 #undef FOREACH

   101 #undef FOREACH_RANGE

   102 #undef SORT

   103 #undef SORT_ITER

   104 #endif//__SYMBIAN32__

   105          

   106 enum {

   107   NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,

   108   

   109   /* Getting iters */

   110   GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,

   111   INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,

   112   SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,

   113   

   114   /* dereferencing */

   115   GET, SET,

   116   

   117   /* operations on GSequenceIter * */

   118   ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,

   119   ITER_MOVE, ITER_GET_SEQUENCE,

   120   

   121   /* search */

   122   ITER_COMPARE, RANGE_GET_MIDPOINT,

   123   N_OPS

   124 };

   125 

   126 typedef struct SequenceInfo

   127 {

   128   GQueue *	queue;

   129   GSequence *	sequence;

   130   int		n_items;

   131 } SequenceInfo;

   132 

   133 typedef struct

   134 {

   135   SequenceInfo *seq;

   136   int		  number;

   137 } Item;

   138 

   139 void g_sequence_check (GSequence *sequence);

   140 

   141 static Item *

   142 fix_pointer (gconstpointer data)

   143 {

   144   return (Item *)((char *)data - 1);

   145 }

   146 

   147 static Item *

   148 get_item (GSequenceIter *iter)

   149 {

   150   return fix_pointer (g_sequence_get (iter));

   151 }

   152 

   153 static void

   154 check_integrity (SequenceInfo *info)

   155 {

   156   GList *list;

   157   GSequenceIter *iter;

   158   int i;

   159   

   160   g_sequence_check (info->sequence);

   161   

   162   if (g_sequence_get_length (info->sequence) != info->n_items)

   163     g_print ("%d %d\n",

   164 	     g_sequence_get_length (info->sequence), info->n_items);

   165   g_assert (info->n_items == g_queue_get_length (info->queue));

   166   g_assert (g_sequence_get_length (info->sequence) == info->n_items);

   167 

   168   iter = g_sequence_get_begin_iter (info->sequence);

   169   list = info->queue->head;

   170   i = 0;

   171   while (iter != g_sequence_get_end_iter (info->sequence))

   172     {

   173       Item *item;

   174       g_assert (list->data == iter);

   175       item = get_item (list->data);

   176       g_assert (item->seq == info);

   177       

   178       iter = g_sequence_iter_next (iter);

   179       list = list->next;

   180       i++;

   181     }

   182   

   183   g_assert (info->n_items == g_queue_get_length (info->queue));

   184   g_assert (g_sequence_get_length (info->sequence) == info->n_items);

   185 }

   186 

   187 static gpointer

   188 new_item (SequenceInfo *seq)

   189 {

   190   Item *item = g_new (Item, 1);

   191   seq->n_items++;

   192   item->seq = seq;

   193   item->number = g_random_int ();

   194   

   195   /* There have been bugs in the past where the GSequence would

   196    * dereference the user pointers. This will make sure such

   197    * behavior causes crashes

   198    */

   199   return ((char *)item + 1);

   200 }

   201 

   202 static void

   203 free_item (gpointer data)

   204 {

   205   Item *item = fix_pointer (data);

   206   item->seq->n_items--;

   207   g_free (item);

   208 }

   209 

   210 static void

   211 seq_foreach (gpointer data,

   212 	     gpointer user_data)

   213 {

   214   Item *item = fix_pointer (data);

   215   GList **link = user_data;

   216   GSequenceIter *iter;

   217   

   218   g_assert (*link != NULL);

   219   

   220   iter = (*link)->data;

   221   

   222   g_assert (get_item (iter) == item);

   223   

   224   item->number = g_random_int();

   225   

   226   *link = (*link)->next;

   227 }

   228 

   229 static gint

   230 compare_items (gconstpointer a,

   231 	       gconstpointer b,

   232 	       gpointer	     data)

   233 {

   234   const Item *item_a = fix_pointer (a);

   235   const Item *item_b = fix_pointer (b);

   236 

   237   if (item_a->number < item_b->number)

   238     {

   239       return -1;

   240     }

   241   else if (item_a->number == item_b->number)

   242     {

   243       /* Force an arbitrary order on the items

   244        * We have to do this, since g_queue_insert_sorted() and

   245        * g_sequence_insert_sorted() do not agree on the exact

   246        * position the item is inserted if the new item is

   247        * equal to an existing one.

   248        */

   249       if (item_a < item_b)

   250 	return -1;

   251       else if (item_a == item_b)

   252 	return 0;

   253       else

   254 	return 1;

   255     }

   256   else

   257     {

   258       return 1;

   259     }

   260 }

   261 

   262 static void

   263 check_sorted (SequenceInfo *info)

   264 {

   265   GList *list;

   266   int last;

   267   GSequenceIter *last_iter;

   268   

   269   check_integrity (info);

   270   

   271   last = G_MININT;

   272   last_iter = NULL;

   273   for (list = info->queue->head; list != NULL; list = list->next)

   274     {

   275       GSequenceIter *iter = list->data;

   276       Item *item = get_item (iter);

   277       

   278       g_assert (item->number >= last);

   279       /* Check that the ordering is the same as that of the queue,

   280        * ie. that the sort is stable

   281        */

   282       if (last_iter)

   283 	g_assert (iter == g_sequence_iter_next (last_iter));

   284       

   285       last = item->number;

   286       last_iter = iter;

   287     }

   288 }

   289 

   290 static gint

   291 compare_iters (gconstpointer a,

   292 	       gconstpointer b,

   293 	       gpointer      data)

   294 {

   295   GSequence *seq = data;

   296   GSequenceIter *iter_a = (GSequenceIter *)a;

   297   GSequenceIter *iter_b = (GSequenceIter *)b;

   298   /* compare_items() will fix up the pointers */

   299   Item *item_a = g_sequence_get (iter_a);

   300   Item *item_b = g_sequence_get (iter_b);

   301   

   302   if (seq)

   303     {

   304       g_assert (g_sequence_iter_get_sequence (iter_a) == seq);

   305       g_assert (g_sequence_iter_get_sequence (iter_b) == seq);

   306     }

   307   

   308   return compare_items (item_a, item_b, data);

   309 }

   310 

   311 /* A version of g_queue_link_index() that treats NULL as just

   312  * beyond the queue

   313  */

   314 static int

   315 queue_link_index (SequenceInfo *seq, GList *link)

   316 {

   317   if (link)

   318     return g_queue_link_index (seq->queue, link);

   319   else

   320     return g_queue_get_length (seq->queue);

   321 }

   322 

   323 static void

   324 get_random_range (SequenceInfo *seq,

   325 		  GSequenceIter **begin_iter,

   326 		  GSequenceIter **end_iter,

   327 		  GList **begin_link,

   328 		  GList **end_link)

   329 {

   330   int length = g_queue_get_length (seq->queue);

   331   int b = g_random_int_range (0, length + 1);

   332   int e = g_random_int_range (b, length + 1);

   333   

   334   g_assert (length == g_sequence_get_length (seq->sequence));

   335   

   336   if (begin_iter)

   337     *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);

   338   if (end_iter)

   339     *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);

   340   if (begin_link)

   341     *begin_link = g_queue_peek_nth_link (seq->queue, b);

   342   if (end_link)

   343     *end_link = g_queue_peek_nth_link (seq->queue, e);

   344   if (begin_iter && begin_link)

   345     {

   346       g_assert (

   347 		queue_link_index (seq, *begin_link) ==

   348 		g_sequence_iter_get_position (*begin_iter));

   349     }

   350   if (end_iter && end_link)

   351     {

   352       g_assert (

   353 		queue_link_index (seq, *end_link) ==

   354 		g_sequence_iter_get_position (*end_iter));

   355     }

   356 }

   357 

   358 static gint

   359 get_random_position (SequenceInfo *seq)

   360 {

   361   int length = g_queue_get_length (seq->queue);

   362   

   363   g_assert (length == g_sequence_get_length (seq->sequence));

   364   

   365   return g_random_int_range (-2, length + 5);

   366 }

   367 

   368 static GSequenceIter *

   369 get_random_iter (SequenceInfo  *seq,

   370 		 GList        **link)

   371 {

   372   GSequenceIter *iter;

   373   int pos = get_random_position (seq);

   374   if (link)

   375     *link = g_queue_peek_nth_link (seq->queue, pos);

   376   iter = g_sequence_get_iter_at_pos (seq->sequence, pos);

   377   if (link)

   378     g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));

   379   return iter;

   380 }

   381 

   382 static void

   383 dump_info (SequenceInfo *seq)

   384 {

   385 #if 0

   386   GSequenceIter *iter;

   387   GList *list;

   388   

   389   iter = g_sequence_get_begin_iter (seq->sequence);

   390   list = seq->queue->head;

   391   

   392   while (iter != g_sequence_get_end_iter (seq->sequence))

   393     {

   394       Item *item = get_item (iter);

   395       g_print ("%p  %p    %d\n", list->data, iter, item->number);

   396       

   397       iter = g_sequence_iter_next (iter);

   398       list = list->next;

   399     }

   400 #endif

   401 }

   402 

   403 /* A version of g_queue_insert_before() that appends if link is NULL */

   404 static void

   405 queue_insert_before (SequenceInfo *seq, GList *link, gpointer data)

   406 {

   407   if (link)

   408     g_queue_insert_before (seq->queue, link, data);

   409   else

   410     g_queue_push_tail (seq->queue, data);

   411 }

   412 

   413 static void

   414 run_random_tests (guint32 seed)

   415 {

   416 #ifndef __SYMBIAN32__

   417 #define N_ITERATIONS 60000

   418 #else

   419 #define N_ITERATIONS 600

   420 #endif//__SYMBIAN32__    

   421 #define N_SEQUENCES 8

   422 #define N_TIMES 24

   423     

   424   SequenceInfo sequences[N_SEQUENCES];

   425   int k;

   426   

   427   g_print ("    seed: %u\n", seed);

   428   

   429   g_random_set_seed (seed);

   430   

   431   for (k = 0; k < N_SEQUENCES; ++k)

   432     {

   433       sequences[k].queue = g_queue_new ();

   434       sequences[k].sequence = g_sequence_new (free_item);

   435       sequences[k].n_items = 0;

   436     }

   437   

   438 #define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])

   439   

   440   for (k = 0; k < N_ITERATIONS; ++k)

   441     {

   442       int i;

   443       SequenceInfo *seq = RANDOM_SEQUENCE();

   444       int op = g_random_int_range (0, N_OPS);

   445 

   446 #if 0

   447       g_print ("%d on %p\n", op, seq);

   448 #endif

   449       

   450       switch (op)

   451 	{

   452 	case NEW:

   453 	case FREE:

   454 	  {

   455 	    g_queue_free (seq->queue);

   456 	    g_sequence_free (seq->sequence);

   457 	    

   458 	    g_assert (seq->n_items == 0);

   459 	    

   460 	    seq->queue = g_queue_new ();

   461 	    seq->sequence = g_sequence_new (free_item);

   462 	    

   463 	    check_integrity (seq);

   464 	  }

   465 	  break;

   466 	case GET_LENGTH:

   467 	  {

   468 	    int slen = g_sequence_get_length (seq->sequence);

   469 	    int qlen = g_queue_get_length (seq->queue);

   470 	    

   471 	    g_assert (slen == qlen);

   472 	  }

   473 	  break;

   474 	case FOREACH:

   475 	  {

   476 	    GList *link = seq->queue->head;

   477 	    g_sequence_foreach (seq->sequence, seq_foreach, &link);

   478 	    g_assert (link == NULL);

   479 	  }

   480 	  break;

   481 	case FOREACH_RANGE:

   482 	  {

   483 	    GSequenceIter *begin_iter, *end_iter;

   484 	    GList *begin_link, *end_link;

   485 	    

   486 	    get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);

   487 	    

   488 	    check_integrity (seq);

   489 	    

   490 	    g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);

   491 	    

   492 	    g_assert (begin_link == end_link);

   493 	  }

   494 	  break;

   495 	case SORT:

   496 	  {

   497 	    dump_info (seq);

   498 	    

   499 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   500 	    g_queue_sort (seq->queue, compare_iters, NULL);

   501 	    

   502 	    check_sorted (seq);

   503 	    

   504 	    dump_info (seq);

   505 	  }

   506 	  break;

   507 	case SORT_ITER:

   508 	  {

   509 	    check_integrity (seq);

   510 	    g_sequence_sort_iter (seq->sequence,

   511 				  (GSequenceIterCompareFunc)compare_iters, seq->sequence);

   512 	    g_queue_sort (seq->queue, compare_iters, NULL);

   513 	    check_sorted (seq);

   514 	  }

   515 	  break;

   516 	  

   517 	  /* Getting iters */

   518 	case GET_END_ITER:

   519 	case GET_BEGIN_ITER:

   520 	  {

   521 	    GSequenceIter *begin_iter;

   522 	    GSequenceIter *end_iter;

   523 	    GSequenceIter *penultimate_iter;

   524 	    

   525 	    begin_iter = g_sequence_get_begin_iter (seq->sequence);

   526 	    check_integrity (seq);

   527 	    

   528 	    end_iter = g_sequence_get_end_iter (seq->sequence);

   529 	    check_integrity (seq);

   530 	    

   531 	    penultimate_iter = g_sequence_iter_prev (end_iter);

   532 	    check_integrity (seq);

   533 	    

   534 	    if (g_sequence_get_length (seq->sequence) > 0)

   535 	      {

   536 		g_assert (seq->queue->head);

   537 		g_assert (seq->queue->head->data == begin_iter);

   538 		g_assert (seq->queue->tail);

   539 		g_assert (seq->queue->tail->data == penultimate_iter);

   540 	      }

   541 	    else

   542 	      {

   543 		g_assert (penultimate_iter == end_iter);

   544 		g_assert (begin_iter == end_iter);

   545 		g_assert (penultimate_iter == begin_iter);

   546 		g_assert (seq->queue->head == NULL);

   547 		g_assert (seq->queue->tail == NULL);

   548 	      }

   549 	  }

   550 	  break;

   551 	case GET_ITER_AT_POS:

   552 	  {

   553 	    int i;

   554 	    

   555 	    g_assert (g_queue_get_length (seq->queue) == g_sequence_get_length (seq->sequence));

   556 	    

   557 	    for (i = 0; i < 10; ++i)

   558 	      {

   559 		int pos = get_random_position (seq);

   560 		GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);

   561 		GList *link = g_queue_peek_nth_link (seq->queue, pos);

   562 		check_integrity (seq);

   563 		if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)

   564 		  {

   565 		    g_assert (iter == g_sequence_get_end_iter (seq->sequence));

   566 		    g_assert (link == NULL);

   567 		  }

   568 		else

   569 		  {

   570 		    g_assert (link);

   571 		    g_assert (link->data == iter);

   572 		  }

   573 	      }

   574 	  }

   575 	  break;

   576 	case APPEND:

   577 	  {

   578 	    for (i = 0; i < 10; ++i)

   579 	      {

   580 		GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));

   581 		g_queue_push_tail (seq->queue, iter);

   582 	      }

   583 	  }

   584 	  break;

   585 	case PREPEND:

   586 	  {

   587 	    for (i = 0; i < 10; ++i)

   588 	      {

   589 		GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));

   590 		g_queue_push_head (seq->queue, iter);

   591 	      }

   592 	  }

   593 	  break;

   594 	case INSERT_BEFORE:

   595 	  {

   596 	    for (i = 0; i < 10; ++i)

   597 	      {

   598 		GList *link;

   599 		GSequenceIter *iter = get_random_iter (seq, &link);

   600 		GSequenceIter *new_iter;

   601 		check_integrity (seq);

   602 		

   603 		new_iter = g_sequence_insert_before (iter, new_item (seq));

   604 		

   605 		queue_insert_before (seq, link, new_iter);

   606 	      }

   607 	  }

   608 	  break;

   609  	case MOVE:

   610 	  {

   611 	    GList *link1, *link2;

   612 	    SequenceInfo *seq1 = RANDOM_SEQUENCE();

   613 	    SequenceInfo *seq2 = RANDOM_SEQUENCE();

   614 	    GSequenceIter *iter1 = get_random_iter (seq1, &link1);

   615 	    GSequenceIter *iter2 = get_random_iter (seq2, &link2);

   616 	    

   617 	    if (!g_sequence_iter_is_end (iter1))

   618 	      {

   619 		g_sequence_move (iter1, iter2);

   620 		

   621 		if (!link2)

   622 		  g_assert (g_sequence_iter_is_end (iter2));

   623 		

   624 		queue_insert_before (seq2, link2, link1->data);

   625 		

   626 		g_queue_delete_link (seq1->queue, link1);

   627 

   628 		get_item (iter1)->seq = seq2;

   629 		

   630 		seq1->n_items--;

   631 		seq2->n_items++;

   632 	      }

   633 	    

   634 	    check_integrity (seq);

   635 	    

   636 	    iter1 = get_random_iter (seq, NULL);

   637 	    

   638 	    /* Moving an iter to itself should have no effect */

   639 	    if (!g_sequence_iter_is_end (iter1))

   640 	      g_sequence_move (iter1, iter1);

   641 	  }

   642 	  break;

   643 	case SWAP:

   644 	  {

   645 	    GList *link1, *link2;

   646 	    SequenceInfo *seq1 = RANDOM_SEQUENCE();

   647 	    SequenceInfo *seq2 = RANDOM_SEQUENCE();

   648 	    GSequenceIter *iter1 = get_random_iter (seq1, &link1);

   649 	    GSequenceIter *iter2 = get_random_iter (seq2, &link2);

   650 	    

   651 	    if (!g_sequence_iter_is_end (iter1) &&

   652 		!g_sequence_iter_is_end (iter2))

   653 	      {

   654 		gpointer tmp;

   655 

   656 		g_sequence_swap (iter1, iter2);

   657 

   658 		get_item (iter1)->seq = seq2;

   659 		get_item (iter2)->seq = seq1;

   660 		

   661 		tmp = link1->data;

   662 		link1->data = link2->data;

   663 		link2->data = tmp;

   664 	      }

   665 	  }

   666 	  break;

   667 	case INSERT_SORTED:

   668 	  {

   669 	    int i;

   670 	    dump_info (seq);

   671 	    

   672 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   673 	    g_queue_sort (seq->queue, compare_iters, NULL);

   674 	    

   675 	    check_sorted (seq);

   676 	    

   677 	    for (i = 0; i < N_TIMES; ++i)

   678 	      {

   679 		GSequenceIter *iter =

   680 		  g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);

   681 		

   682 		g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);

   683 	      }

   684 	    

   685 	    check_sorted (seq);

   686 	    

   687 	    dump_info (seq);

   688 	  }

   689 	  break;

   690 	case INSERT_SORTED_ITER:

   691 	  {

   692 	    int i;

   693 	    dump_info (seq);

   694 	    

   695 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   696 	    g_queue_sort (seq->queue, compare_iters, NULL);

   697 	    

   698 	    check_sorted (seq);

   699 	    

   700 	    for (i = 0; i < N_TIMES; ++i)

   701 	      {

   702 		GSequenceIter *iter;

   703 

   704 		iter = g_sequence_insert_sorted_iter (seq->sequence,

   705 						      new_item (seq),

   706 						      (GSequenceIterCompareFunc)compare_iters,

   707 						      seq->sequence);

   708 		

   709 		g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);

   710 	      }

   711 	    

   712 	    check_sorted (seq);

   713 	    

   714 	    dump_info (seq);

   715 	  }

   716 	  break;

   717 	case SORT_CHANGED:

   718 	  {

   719 	    int i;

   720 	    

   721 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   722 	    g_queue_sort (seq->queue, compare_iters, NULL);

   723 	    

   724 	    check_sorted (seq);

   725 	    

   726 	    for (i = 0; i < N_TIMES; ++i)

   727 	      {

   728 		GList *link;

   729 		GSequenceIter *iter = get_random_iter (seq, &link);

   730 		

   731 		if (!g_sequence_iter_is_end (iter))

   732 		  {

   733 		    g_sequence_set (iter, new_item (seq));

   734 		    g_sequence_sort_changed (iter, compare_items, NULL);

   735 		    

   736 		    g_queue_delete_link (seq->queue, link);

   737 		    g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);

   738 		  }

   739 		

   740 		check_sorted (seq);

   741 	      }

   742 	  }

   743 	  break;

   744 	case SORT_CHANGED_ITER:

   745 	  {

   746 	    int i;

   747 	    

   748 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   749 	    g_queue_sort (seq->queue, compare_iters, NULL);

   750 	    

   751 	    check_sorted (seq);

   752 	    

   753 	    for (i = 0; i < N_TIMES; ++i)

   754 	      {

   755 		GList *link;

   756 		GSequenceIter *iter = get_random_iter (seq, &link);

   757 		

   758 		if (!g_sequence_iter_is_end (iter))

   759 		  {

   760 		    g_sequence_set (iter, new_item (seq));

   761 		    g_sequence_sort_changed_iter (iter,

   762 						  (GSequenceIterCompareFunc)compare_iters, seq->sequence);

   763 		    

   764 		    g_queue_delete_link (seq->queue, link);

   765 		    g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);

   766 		  }

   767 		

   768 		check_sorted (seq);

   769 	      }

   770 	  }

   771 	  break;

   772 	case REMOVE:

   773 	  {

   774 	    int i;

   775 	    

   776 	    for (i = 0; i < N_TIMES; ++i)

   777 	      {

   778 		GList *link;

   779 		GSequenceIter *iter = get_random_iter (seq, &link);

   780 		

   781 		if (!g_sequence_iter_is_end (iter))

   782 		  {

   783 		    g_sequence_remove (iter);

   784 		    g_queue_delete_link (seq->queue, link);

   785 		  }

   786 	      }

   787 	  }

   788 	  break;

   789 	case REMOVE_RANGE:

   790 	  {

   791 	    GSequenceIter *begin_iter, *end_iter;

   792 	    GList *begin_link, *end_link;

   793 	    GList *list;

   794 	    

   795 	    get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);

   796 	    

   797 	    g_sequence_remove_range (begin_iter, end_iter);

   798 	    

   799 	    list = begin_link;

   800 	    while (list != end_link)

   801 	      {

   802 		GList *next = list->next;

   803 		

   804 		g_queue_delete_link (seq->queue, list);

   805 		

   806 		list = next;

   807 	      }

   808 	  }

   809 	  break;

   810 	case MOVE_RANGE:

   811 	  {

   812 	    SequenceInfo *src = RANDOM_SEQUENCE();

   813 	    SequenceInfo *dst = RANDOM_SEQUENCE();

   814 	    

   815 	    GSequenceIter *begin_iter, *end_iter;

   816 	    GList *begin_link, *end_link;

   817 	    

   818 	    GSequenceIter *dst_iter;

   819 	    GList *dst_link;

   820 	    

   821 	    GList *list;

   822 	    

   823 	    g_assert (src->queue);

   824 	    g_assert (dst->queue);

   825 	    

   826 	    get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);

   827 	    dst_iter = get_random_iter (dst, &dst_link);

   828 	    

   829 	    g_sequence_move_range (dst_iter, begin_iter, end_iter);

   830 	    

   831 	    if (dst_link == begin_link || (src == dst && dst_link == end_link))

   832 	      {

   833 		check_integrity (src);

   834 		check_integrity (dst);

   835 		break;

   836 	      }

   837 	    

   838 	    if (queue_link_index (src, begin_link) >=

   839 		queue_link_index (src, end_link))

   840 	      {

   841 		break;

   842 	      }

   843 	    

   844 	    if (src == dst &&

   845 		queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&

   846 		queue_link_index (src, dst_link) <= queue_link_index (src, end_link))

   847 	      {

   848 		break;

   849 	      }

   850 	    

   851 	    list = begin_link;

   852 	    while (list != end_link)

   853 	      {

   854 		GList *next = list->next;

   855 		Item *item = get_item (list->data);

   856 		

   857 		g_assert (dst->queue);

   858 		queue_insert_before (dst, dst_link, list->data);

   859 		g_queue_delete_link (src->queue, list);

   860 		

   861 		g_assert (item->seq == src);

   862 		

   863 		src->n_items--;

   864 		dst->n_items++;

   865 		item->seq = dst;

   866 		

   867 		list = next;

   868 	      }

   869 	  }

   870 	  break;

   871 	case SEARCH:

   872 	  {

   873 	    Item *item;

   874 	    GSequenceIter *search_iter;

   875 	    GSequenceIter *insert_iter;

   876 	    

   877 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   878 	    g_queue_sort (seq->queue, compare_iters, NULL);

   879 	    

   880 	    check_sorted (seq);

   881 	    

   882 	    item = new_item (seq);

   883 	    search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);

   884 	    

   885 	    insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);

   886 	    

   887 	    g_assert (search_iter == g_sequence_iter_next (insert_iter));

   888 	    

   889 	    g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);

   890 	  }

   891 	  break;

   892 	case SEARCH_ITER:

   893 	  {

   894 	    Item *item;

   895 	    GSequenceIter *search_iter;

   896 	    GSequenceIter *insert_iter;

   897 	    

   898 	    g_sequence_sort (seq->sequence, compare_items, NULL);

   899 	    g_queue_sort (seq->queue, compare_iters, NULL);

   900 	    

   901 	    check_sorted (seq);

   902 	    

   903 	    item = new_item (seq);

   904 	    search_iter = g_sequence_search_iter (seq->sequence,

   905 						  item,

   906 						  (GSequenceIterCompareFunc)compare_iters, seq->sequence);

   907 	    

   908 	    insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);

   909 	    

   910 	    g_assert (search_iter == g_sequence_iter_next (insert_iter));

   911 	    

   912 	    g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);

   913 	  }

   914 	  break;

   915 	  

   916 	  /* dereferencing */

   917 	case GET:

   918 	case SET:

   919 	  {

   920 	    GSequenceIter *iter;

   921 	    GList *link;

   922 	    

   923 	    iter = get_random_iter (seq, &link);

   924 	    

   925 	    if (!g_sequence_iter_is_end (iter))

   926 	      {

   927 		Item *item;

   928 		int i;

   929 		

   930 		check_integrity (seq);

   931 		

   932 		/* Test basic functionality */

   933 		item = new_item (seq);

   934 		g_sequence_set (iter, item);

   935 		g_assert (g_sequence_get (iter) == item);

   936 		

   937 		/* Make sure that existing items are freed */

   938 		for (i = 0; i < N_TIMES; ++i)

   939 		  g_sequence_set (iter, new_item (seq));

   940 		

   941 		check_integrity (seq);

   942 		

   943 		g_sequence_set (iter, new_item (seq));

   944 	      }

   945 	  }

   946 	  break;

   947 	  

   948 	  /* operations on GSequenceIter * */

   949 	case ITER_IS_BEGIN:

   950 	  {

   951 	    GSequenceIter *iter;

   952 	    

   953 	    iter = g_sequence_get_iter_at_pos (seq->sequence, 0);

   954 	    

   955 	    g_assert (g_sequence_iter_is_begin (iter));

   956 	    

   957 	    check_integrity (seq);

   958 	    

   959 	    if (g_sequence_get_length (seq->sequence) > 0)

   960 	      {

   961 		g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));

   962 	      }

   963 	    else

   964 	      {

   965 		g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));

   966 	      }

   967 	    

   968 	    g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));

   969 	  }

   970 	  break;

   971 	case ITER_IS_END:

   972 	  {

   973 	    GSequenceIter *iter;

   974 	    int len = g_sequence_get_length (seq->sequence);

   975 	    

   976 	    iter = g_sequence_get_iter_at_pos (seq->sequence, len);

   977 	    

   978 	    g_assert (g_sequence_iter_is_end (iter));

   979 	    

   980 	    if (len > 0)

   981 	      {

   982 		g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));

   983 	      }

   984 	    else

   985 	      {

   986 		g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));

   987 	      }

   988 	    

   989 	    g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));

   990 	  }

   991 	  break;

   992 	case ITER_NEXT:

   993 	  {

   994 	    GSequenceIter *iter1, *iter2, *iter3, *end;

   995 	    

   996 	    iter1 = g_sequence_append (seq->sequence, new_item (seq));

   997 	    iter2 = g_sequence_append (seq->sequence, new_item (seq));

   998 	    iter3 = g_sequence_append (seq->sequence, new_item (seq));

   999 	    

  1000 	    end = g_sequence_get_end_iter (seq->sequence);

  1001 	    

  1002 	    g_assert (g_sequence_iter_next (iter1) == iter2);

  1003 	    g_assert (g_sequence_iter_next (iter2) == iter3);

  1004 	    g_assert (g_sequence_iter_next (iter3) == end);

  1005 	    g_assert (g_sequence_iter_next (end) == end);

  1006 	    

  1007 	    g_queue_push_tail (seq->queue, iter1);

  1008 	    g_queue_push_tail (seq->queue, iter2);

  1009 	    g_queue_push_tail (seq->queue, iter3);

  1010 	  }

  1011 	  break;

  1012 	case ITER_PREV:

  1013 	  {

  1014 	    GSequenceIter *iter1, *iter2, *iter3, *begin;

  1015 	    

  1016 	    iter1 = g_sequence_prepend (seq->sequence, new_item (seq));

  1017 	    iter2 = g_sequence_prepend (seq->sequence, new_item (seq));

  1018 	    iter3 = g_sequence_prepend (seq->sequence, new_item (seq));

  1019 	    

  1020 	    begin = g_sequence_get_begin_iter (seq->sequence);

  1021 	    

  1022 	    g_assert (g_sequence_iter_prev (iter1) == iter2);

  1023 	    g_assert (g_sequence_iter_prev (iter2) == iter3);

  1024 	    g_assert (iter3 == begin);

  1025 	    g_assert (g_sequence_iter_prev (iter3) == begin);

  1026 	    g_assert (g_sequence_iter_prev (begin) == begin);

  1027 	    

  1028 	    g_queue_push_head (seq->queue, iter1);

  1029 	    g_queue_push_head (seq->queue, iter2);

  1030 	    g_queue_push_head (seq->queue, iter3);

  1031 	  }

  1032 	  break;

  1033 	case ITER_GET_POSITION:

  1034 	  {

  1035 	    GList *link;

  1036 	    GSequenceIter *iter = get_random_iter (seq, &link);

  1037 	    

  1038 	    g_assert (g_sequence_iter_get_position (iter) ==

  1039 		      queue_link_index (seq, link));

  1040 	  }

  1041 	  break;

  1042 	case ITER_MOVE:

  1043 	  {

  1044 	    int len = g_sequence_get_length (seq->sequence);

  1045 	    GSequenceIter *iter;

  1046 	    int pos;

  1047 	    

  1048 	    iter = get_random_iter (seq, NULL);

  1049 	    pos = g_sequence_iter_get_position (iter);

  1050 	    iter = g_sequence_iter_move (iter, len - pos);

  1051 	    g_assert (g_sequence_iter_is_end (iter));

  1052 	    

  1053 	    

  1054 	    iter = get_random_iter (seq, NULL);

  1055 	    pos = g_sequence_iter_get_position (iter);

  1056 	    while (pos < len)

  1057 	      {

  1058 		g_assert (!g_sequence_iter_is_end (iter));

  1059 		pos++;

  1060 		iter = g_sequence_iter_move (iter, 1);

  1061 	      }

  1062 	    g_assert (g_sequence_iter_is_end (iter));

  1063 	  }

  1064 	  break;

  1065 	case ITER_GET_SEQUENCE:

  1066 	  {

  1067 	    GSequenceIter *iter = get_random_iter (seq, NULL);

  1068 	    

  1069 	    g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);

  1070 	  }

  1071 	  break;

  1072 	  

  1073 	  /* search */

  1074 	case ITER_COMPARE:

  1075 	  {

  1076 	    GList *link1, *link2;

  1077 	    GSequenceIter *iter1 = get_random_iter (seq, &link1);

  1078 	    GSequenceIter *iter2 = get_random_iter (seq, &link2);

  1079 	    

  1080 	    int cmp = g_sequence_iter_compare (iter1, iter2);

  1081 	    int pos1 = queue_link_index (seq, link1);

  1082 	    int pos2 = queue_link_index (seq, link2);

  1083 	    

  1084 	    if (cmp == 0)

  1085 	      {

  1086 		g_assert (pos1 == pos2);

  1087 	      }

  1088 	    else if (cmp < 0)

  1089 	      {

  1090 		g_assert (pos1 < pos2);

  1091 	      }

  1092 	    else

  1093 	      {

  1094 		g_assert (pos1 > pos2);

  1095 	      }

  1096 	  }

  1097 	  break;

  1098 	case RANGE_GET_MIDPOINT:

  1099 	  {

  1100 	    GSequenceIter *iter1 = get_random_iter (seq, NULL);

  1101 	    GSequenceIter *iter2 = get_random_iter (seq, NULL);

  1102 	    GSequenceIter *iter3;

  1103 	    int cmp;

  1104 	    

  1105 	    cmp = g_sequence_iter_compare (iter1, iter2);

  1106 	    

  1107 	    if (cmp > 0)

  1108 	      {

  1109 		GSequenceIter *tmp;

  1110 		

  1111 		tmp = iter1;

  1112 		iter1 = iter2;

  1113 		iter2 = tmp;

  1114 	      }

  1115 	    

  1116 	    iter3 = g_sequence_range_get_midpoint (iter1, iter2);

  1117 	    

  1118 	    if (cmp == 0)

  1119 	      {

  1120 		g_assert (iter3 == iter1);

  1121 		g_assert (iter3 == iter2);

  1122 	      }

  1123 	    

  1124 	    g_assert (g_sequence_iter_get_position (iter3) >= 

  1125 		      g_sequence_iter_get_position (iter1));

  1126 	    g_assert (g_sequence_iter_get_position (iter2) >= 

  1127 		      g_sequence_iter_get_position (iter3));

  1128 	  }

  1129 	  break;

  1130 	  

  1131 	}

  1132       

  1133       check_integrity (seq);

  1134     }