LCOV - code coverage report
Current view: top level - glib/glib/tests - sequence.c (source / functions) Hit Total Coverage
Test: unnamed Lines: 641 648 98.9 %
Date: 2024-03-26 05:16:46 Functions: 28 28 100.0 %
Branches: 185 201 92.0 %

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

Generated by: LCOV version 1.14