sl@0: /* Portions copyright (c) 2009 Nokia Corporation.  All rights reserved.*/
sl@0: #include <stdio.h>
sl@0: #include <glib.h>
sl@0: #include <stdlib.h>
sl@0: #ifdef __SYMBIAN32__
sl@0: #include "mrt2_glib2_test.h"
sl@0: #endif /*__SYMBIAN32__*/
sl@0: /* Keep this in sync with gsequence.c !!! */
sl@0: typedef struct _GSequenceNode GSequenceNode;
sl@0: 
sl@0: struct _GSequence
sl@0: {
sl@0:   GSequenceNode *       end_node;
sl@0:   GDestroyNotify        data_destroy_notify;
sl@0:   gboolean              access_prohibited;
sl@0:   GSequence *           real_sequence;
sl@0: };
sl@0: 
sl@0: struct _GSequenceNode
sl@0: {
sl@0:   gint                  n_nodes;
sl@0:   GSequenceNode *       parent;
sl@0:   GSequenceNode *       left;
sl@0:   GSequenceNode *       right;
sl@0:   gpointer              data;
sl@0: };
sl@0: 
sl@0: static guint
sl@0: get_priority (GSequenceNode *node)
sl@0: {
sl@0:   guint key = GPOINTER_TO_UINT (node);
sl@0: 
sl@0:   key = (key << 15) - key - 1;
sl@0:   key = key ^ (key >> 12);
sl@0:   key = key + (key << 2);
sl@0:   key = key ^ (key >> 4);
sl@0:   key = key + (key << 3) + (key << 11);
sl@0:   key = key ^ (key >> 16);
sl@0: 
sl@0:   return key? key : 1;
sl@0: }
sl@0:       
sl@0: static void
sl@0: check_node (GSequenceNode *node)
sl@0: {
sl@0:   if (node)
sl@0:     {
sl@0:       g_assert (node->parent != node);
sl@0:       if (node->parent)
sl@0:         g_assert (node->parent->left == node || node->parent->right == node);
sl@0:       g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));
sl@0:       if (node->left)
sl@0:           g_assert (get_priority (node) >= get_priority (node->left));
sl@0:       if (node->right)
sl@0:           g_assert (get_priority (node) >= get_priority (node->right));
sl@0:       check_node (node->left);
sl@0:       check_node (node->right);
sl@0:     }
sl@0: }
sl@0: 
sl@0: void
sl@0: g_sequence_check (GSequence *seq)
sl@0: {
sl@0:   GSequenceNode *node = seq->end_node;
sl@0: 
sl@0:   while (node->parent)
sl@0:     node = node->parent;
sl@0: 
sl@0:   check_node (node);
sl@0: 
sl@0:   while (node->right)
sl@0:     node = node->right;
sl@0: 
sl@0:   g_assert (seq->end_node == node);
sl@0:   g_assert (node->data == seq);
sl@0: 
sl@0: }
sl@0: 
sl@0: //undefs done here as some of these enums are already defined in s60 environ
sl@0: #ifdef __SYMBIAN32__
sl@0: #undef NEW 
sl@0: #undef FREE
sl@0: #undef GET_LENGTH
sl@0: #undef FOREACH
sl@0: #undef FOREACH_RANGE
sl@0: #undef SORT
sl@0: #undef SORT_ITER
sl@0: #endif//__SYMBIAN32__
sl@0:          
sl@0: enum {
sl@0:   NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,
sl@0:   
sl@0:   /* Getting iters */
sl@0:   GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
sl@0:   INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
sl@0:   SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
sl@0:   
sl@0:   /* dereferencing */
sl@0:   GET, SET,
sl@0:   
sl@0:   /* operations on GSequenceIter * */
sl@0:   ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
sl@0:   ITER_MOVE, ITER_GET_SEQUENCE,
sl@0:   
sl@0:   /* search */
sl@0:   ITER_COMPARE, RANGE_GET_MIDPOINT,
sl@0:   N_OPS
sl@0: };
sl@0: 
sl@0: typedef struct SequenceInfo
sl@0: {
sl@0:   GQueue *	queue;
sl@0:   GSequence *	sequence;
sl@0:   int		n_items;
sl@0: } SequenceInfo;
sl@0: 
sl@0: typedef struct
sl@0: {
sl@0:   SequenceInfo *seq;
sl@0:   int		  number;
sl@0: } Item;
sl@0: 
sl@0: void g_sequence_check (GSequence *sequence);
sl@0: 
sl@0: static Item *
sl@0: fix_pointer (gconstpointer data)
sl@0: {
sl@0:   return (Item *)((char *)data - 1);
sl@0: }
sl@0: 
sl@0: static Item *
sl@0: get_item (GSequenceIter *iter)
sl@0: {
sl@0:   return fix_pointer (g_sequence_get (iter));
sl@0: }
sl@0: 
sl@0: static void
sl@0: check_integrity (SequenceInfo *info)
sl@0: {
sl@0:   GList *list;
sl@0:   GSequenceIter *iter;
sl@0:   int i;
sl@0:   
sl@0:   g_sequence_check (info->sequence);
sl@0:   
sl@0:   if (g_sequence_get_length (info->sequence) != info->n_items)
sl@0:     g_print ("%d %d\n",
sl@0: 	     g_sequence_get_length (info->sequence), info->n_items);
sl@0:   g_assert (info->n_items == g_queue_get_length (info->queue));
sl@0:   g_assert (g_sequence_get_length (info->sequence) == info->n_items);
sl@0: 
sl@0:   iter = g_sequence_get_begin_iter (info->sequence);
sl@0:   list = info->queue->head;
sl@0:   i = 0;
sl@0:   while (iter != g_sequence_get_end_iter (info->sequence))
sl@0:     {
sl@0:       Item *item;
sl@0:       g_assert (list->data == iter);
sl@0:       item = get_item (list->data);
sl@0:       g_assert (item->seq == info);
sl@0:       
sl@0:       iter = g_sequence_iter_next (iter);
sl@0:       list = list->next;
sl@0:       i++;
sl@0:     }
sl@0:   
sl@0:   g_assert (info->n_items == g_queue_get_length (info->queue));
sl@0:   g_assert (g_sequence_get_length (info->sequence) == info->n_items);
sl@0: }
sl@0: 
sl@0: static gpointer
sl@0: new_item (SequenceInfo *seq)
sl@0: {
sl@0:   Item *item = g_new (Item, 1);
sl@0:   seq->n_items++;
sl@0:   item->seq = seq;
sl@0:   item->number = g_random_int ();
sl@0:   
sl@0:   /* There have been bugs in the past where the GSequence would
sl@0:    * dereference the user pointers. This will make sure such
sl@0:    * behavior causes crashes
sl@0:    */
sl@0:   return ((char *)item + 1);
sl@0: }
sl@0: 
sl@0: static void
sl@0: free_item (gpointer data)
sl@0: {
sl@0:   Item *item = fix_pointer (data);
sl@0:   item->seq->n_items--;
sl@0:   g_free (item);
sl@0: }
sl@0: 
sl@0: static void
sl@0: seq_foreach (gpointer data,
sl@0: 	     gpointer user_data)
sl@0: {
sl@0:   Item *item = fix_pointer (data);
sl@0:   GList **link = user_data;
sl@0:   GSequenceIter *iter;
sl@0:   
sl@0:   g_assert (*link != NULL);
sl@0:   
sl@0:   iter = (*link)->data;
sl@0:   
sl@0:   g_assert (get_item (iter) == item);
sl@0:   
sl@0:   item->number = g_random_int();
sl@0:   
sl@0:   *link = (*link)->next;
sl@0: }
sl@0: 
sl@0: static gint
sl@0: compare_items (gconstpointer a,
sl@0: 	       gconstpointer b,
sl@0: 	       gpointer	     data)
sl@0: {
sl@0:   const Item *item_a = fix_pointer (a);
sl@0:   const Item *item_b = fix_pointer (b);
sl@0: 
sl@0:   if (item_a->number < item_b->number)
sl@0:     {
sl@0:       return -1;
sl@0:     }
sl@0:   else if (item_a->number == item_b->number)
sl@0:     {
sl@0:       /* Force an arbitrary order on the items
sl@0:        * We have to do this, since g_queue_insert_sorted() and
sl@0:        * g_sequence_insert_sorted() do not agree on the exact
sl@0:        * position the item is inserted if the new item is
sl@0:        * equal to an existing one.
sl@0:        */
sl@0:       if (item_a < item_b)
sl@0: 	return -1;
sl@0:       else if (item_a == item_b)
sl@0: 	return 0;
sl@0:       else
sl@0: 	return 1;
sl@0:     }
sl@0:   else
sl@0:     {
sl@0:       return 1;
sl@0:     }
sl@0: }
sl@0: 
sl@0: static void
sl@0: check_sorted (SequenceInfo *info)
sl@0: {
sl@0:   GList *list;
sl@0:   int last;
sl@0:   GSequenceIter *last_iter;
sl@0:   
sl@0:   check_integrity (info);
sl@0:   
sl@0:   last = G_MININT;
sl@0:   last_iter = NULL;
sl@0:   for (list = info->queue->head; list != NULL; list = list->next)
sl@0:     {
sl@0:       GSequenceIter *iter = list->data;
sl@0:       Item *item = get_item (iter);
sl@0:       
sl@0:       g_assert (item->number >= last);
sl@0:       /* Check that the ordering is the same as that of the queue,
sl@0:        * ie. that the sort is stable
sl@0:        */
sl@0:       if (last_iter)
sl@0: 	g_assert (iter == g_sequence_iter_next (last_iter));
sl@0:       
sl@0:       last = item->number;
sl@0:       last_iter = iter;
sl@0:     }
sl@0: }
sl@0: 
sl@0: static gint
sl@0: compare_iters (gconstpointer a,
sl@0: 	       gconstpointer b,
sl@0: 	       gpointer      data)
sl@0: {
sl@0:   GSequence *seq = data;
sl@0:   GSequenceIter *iter_a = (GSequenceIter *)a;
sl@0:   GSequenceIter *iter_b = (GSequenceIter *)b;
sl@0:   /* compare_items() will fix up the pointers */
sl@0:   Item *item_a = g_sequence_get (iter_a);
sl@0:   Item *item_b = g_sequence_get (iter_b);
sl@0:   
sl@0:   if (seq)
sl@0:     {
sl@0:       g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
sl@0:       g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
sl@0:     }
sl@0:   
sl@0:   return compare_items (item_a, item_b, data);
sl@0: }
sl@0: 
sl@0: /* A version of g_queue_link_index() that treats NULL as just
sl@0:  * beyond the queue
sl@0:  */
sl@0: static int
sl@0: queue_link_index (SequenceInfo *seq, GList *link)
sl@0: {
sl@0:   if (link)
sl@0:     return g_queue_link_index (seq->queue, link);
sl@0:   else
sl@0:     return g_queue_get_length (seq->queue);
sl@0: }
sl@0: 
sl@0: static void
sl@0: get_random_range (SequenceInfo *seq,
sl@0: 		  GSequenceIter **begin_iter,
sl@0: 		  GSequenceIter **end_iter,
sl@0: 		  GList **begin_link,
sl@0: 		  GList **end_link)
sl@0: {
sl@0:   int length = g_queue_get_length (seq->queue);
sl@0:   int b = g_random_int_range (0, length + 1);
sl@0:   int e = g_random_int_range (b, length + 1);
sl@0:   
sl@0:   g_assert (length == g_sequence_get_length (seq->sequence));
sl@0:   
sl@0:   if (begin_iter)
sl@0:     *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);
sl@0:   if (end_iter)
sl@0:     *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);
sl@0:   if (begin_link)
sl@0:     *begin_link = g_queue_peek_nth_link (seq->queue, b);
sl@0:   if (end_link)
sl@0:     *end_link = g_queue_peek_nth_link (seq->queue, e);
sl@0:   if (begin_iter && begin_link)
sl@0:     {
sl@0:       g_assert (
sl@0: 		queue_link_index (seq, *begin_link) ==
sl@0: 		g_sequence_iter_get_position (*begin_iter));
sl@0:     }
sl@0:   if (end_iter && end_link)
sl@0:     {
sl@0:       g_assert (
sl@0: 		queue_link_index (seq, *end_link) ==
sl@0: 		g_sequence_iter_get_position (*end_iter));
sl@0:     }
sl@0: }
sl@0: 
sl@0: static gint
sl@0: get_random_position (SequenceInfo *seq)
sl@0: {
sl@0:   int length = g_queue_get_length (seq->queue);
sl@0:   
sl@0:   g_assert (length == g_sequence_get_length (seq->sequence));
sl@0:   
sl@0:   return g_random_int_range (-2, length + 5);
sl@0: }
sl@0: 
sl@0: static GSequenceIter *
sl@0: get_random_iter (SequenceInfo  *seq,
sl@0: 		 GList        **link)
sl@0: {
sl@0:   GSequenceIter *iter;
sl@0:   int pos = get_random_position (seq);
sl@0:   if (link)
sl@0:     *link = g_queue_peek_nth_link (seq->queue, pos);
sl@0:   iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
sl@0:   if (link)
sl@0:     g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));
sl@0:   return iter;
sl@0: }
sl@0: 
sl@0: static void
sl@0: dump_info (SequenceInfo *seq)
sl@0: {
sl@0: #if 0
sl@0:   GSequenceIter *iter;
sl@0:   GList *list;
sl@0:   
sl@0:   iter = g_sequence_get_begin_iter (seq->sequence);
sl@0:   list = seq->queue->head;
sl@0:   
sl@0:   while (iter != g_sequence_get_end_iter (seq->sequence))
sl@0:     {
sl@0:       Item *item = get_item (iter);
sl@0:       g_print ("%p  %p    %d\n", list->data, iter, item->number);
sl@0:       
sl@0:       iter = g_sequence_iter_next (iter);
sl@0:       list = list->next;
sl@0:     }
sl@0: #endif
sl@0: }
sl@0: 
sl@0: /* A version of g_queue_insert_before() that appends if link is NULL */
sl@0: static void
sl@0: queue_insert_before (SequenceInfo *seq, GList *link, gpointer data)
sl@0: {
sl@0:   if (link)
sl@0:     g_queue_insert_before (seq->queue, link, data);
sl@0:   else
sl@0:     g_queue_push_tail (seq->queue, data);
sl@0: }
sl@0: 
sl@0: static void
sl@0: run_random_tests (guint32 seed)
sl@0: {
sl@0: #ifndef __SYMBIAN32__
sl@0: #define N_ITERATIONS 60000
sl@0: #else
sl@0: #define N_ITERATIONS 600
sl@0: #endif//__SYMBIAN32__    
sl@0: #define N_SEQUENCES 8
sl@0: #define N_TIMES 24
sl@0:     
sl@0:   SequenceInfo sequences[N_SEQUENCES];
sl@0:   int k;
sl@0:   
sl@0:   g_print ("    seed: %u\n", seed);
sl@0:   
sl@0:   g_random_set_seed (seed);
sl@0:   
sl@0:   for (k = 0; k < N_SEQUENCES; ++k)
sl@0:     {
sl@0:       sequences[k].queue = g_queue_new ();
sl@0:       sequences[k].sequence = g_sequence_new (free_item);
sl@0:       sequences[k].n_items = 0;
sl@0:     }
sl@0:   
sl@0: #define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])
sl@0:   
sl@0:   for (k = 0; k < N_ITERATIONS; ++k)
sl@0:     {
sl@0:       int i;
sl@0:       SequenceInfo *seq = RANDOM_SEQUENCE();
sl@0:       int op = g_random_int_range (0, N_OPS);
sl@0: 
sl@0: #if 0
sl@0:       g_print ("%d on %p\n", op, seq);
sl@0: #endif
sl@0:       
sl@0:       switch (op)
sl@0: 	{
sl@0: 	case NEW:
sl@0: 	case FREE:
sl@0: 	  {
sl@0: 	    g_queue_free (seq->queue);
sl@0: 	    g_sequence_free (seq->sequence);
sl@0: 	    
sl@0: 	    g_assert (seq->n_items == 0);
sl@0: 	    
sl@0: 	    seq->queue = g_queue_new ();
sl@0: 	    seq->sequence = g_sequence_new (free_item);
sl@0: 	    
sl@0: 	    check_integrity (seq);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case GET_LENGTH:
sl@0: 	  {
sl@0: 	    int slen = g_sequence_get_length (seq->sequence);
sl@0: 	    int qlen = g_queue_get_length (seq->queue);
sl@0: 	    
sl@0: 	    g_assert (slen == qlen);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case FOREACH:
sl@0: 	  {
sl@0: 	    GList *link = seq->queue->head;
sl@0: 	    g_sequence_foreach (seq->sequence, seq_foreach, &link);
sl@0: 	    g_assert (link == NULL);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case FOREACH_RANGE:
sl@0: 	  {
sl@0: 	    GSequenceIter *begin_iter, *end_iter;
sl@0: 	    GList *begin_link, *end_link;
sl@0: 	    
sl@0: 	    get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
sl@0: 	    
sl@0: 	    check_integrity (seq);
sl@0: 	    
sl@0: 	    g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);
sl@0: 	    
sl@0: 	    g_assert (begin_link == end_link);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SORT:
sl@0: 	  {
sl@0: 	    dump_info (seq);
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    dump_info (seq);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SORT_ITER:
sl@0: 	  {
sl@0: 	    check_integrity (seq);
sl@0: 	    g_sequence_sort_iter (seq->sequence,
sl@0: 				  (GSequenceIterCompareFunc)compare_iters, seq->sequence);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    check_sorted (seq);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	  
sl@0: 	  /* Getting iters */
sl@0: 	case GET_END_ITER:
sl@0: 	case GET_BEGIN_ITER:
sl@0: 	  {
sl@0: 	    GSequenceIter *begin_iter;
sl@0: 	    GSequenceIter *end_iter;
sl@0: 	    GSequenceIter *penultimate_iter;
sl@0: 	    
sl@0: 	    begin_iter = g_sequence_get_begin_iter (seq->sequence);
sl@0: 	    check_integrity (seq);
sl@0: 	    
sl@0: 	    end_iter = g_sequence_get_end_iter (seq->sequence);
sl@0: 	    check_integrity (seq);
sl@0: 	    
sl@0: 	    penultimate_iter = g_sequence_iter_prev (end_iter);
sl@0: 	    check_integrity (seq);
sl@0: 	    
sl@0: 	    if (g_sequence_get_length (seq->sequence) > 0)
sl@0: 	      {
sl@0: 		g_assert (seq->queue->head);
sl@0: 		g_assert (seq->queue->head->data == begin_iter);
sl@0: 		g_assert (seq->queue->tail);
sl@0: 		g_assert (seq->queue->tail->data == penultimate_iter);
sl@0: 	      }
sl@0: 	    else
sl@0: 	      {
sl@0: 		g_assert (penultimate_iter == end_iter);
sl@0: 		g_assert (begin_iter == end_iter);
sl@0: 		g_assert (penultimate_iter == begin_iter);
sl@0: 		g_assert (seq->queue->head == NULL);
sl@0: 		g_assert (seq->queue->tail == NULL);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case GET_ITER_AT_POS:
sl@0: 	  {
sl@0: 	    int i;
sl@0: 	    
sl@0: 	    g_assert (g_queue_get_length (seq->queue) == g_sequence_get_length (seq->sequence));
sl@0: 	    
sl@0: 	    for (i = 0; i < 10; ++i)
sl@0: 	      {
sl@0: 		int pos = get_random_position (seq);
sl@0: 		GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
sl@0: 		GList *link = g_queue_peek_nth_link (seq->queue, pos);
sl@0: 		check_integrity (seq);
sl@0: 		if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
sl@0: 		  {
sl@0: 		    g_assert (iter == g_sequence_get_end_iter (seq->sequence));
sl@0: 		    g_assert (link == NULL);
sl@0: 		  }
sl@0: 		else
sl@0: 		  {
sl@0: 		    g_assert (link);
sl@0: 		    g_assert (link->data == iter);
sl@0: 		  }
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case APPEND:
sl@0: 	  {
sl@0: 	    for (i = 0; i < 10; ++i)
sl@0: 	      {
sl@0: 		GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
sl@0: 		g_queue_push_tail (seq->queue, iter);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PREPEND:
sl@0: 	  {
sl@0: 	    for (i = 0; i < 10; ++i)
sl@0: 	      {
sl@0: 		GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
sl@0: 		g_queue_push_head (seq->queue, iter);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case INSERT_BEFORE:
sl@0: 	  {
sl@0: 	    for (i = 0; i < 10; ++i)
sl@0: 	      {
sl@0: 		GList *link;
sl@0: 		GSequenceIter *iter = get_random_iter (seq, &link);
sl@0: 		GSequenceIter *new_iter;
sl@0: 		check_integrity (seq);
sl@0: 		
sl@0: 		new_iter = g_sequence_insert_before (iter, new_item (seq));
sl@0: 		
sl@0: 		queue_insert_before (seq, link, new_iter);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0:  	case MOVE:
sl@0: 	  {
sl@0: 	    GList *link1, *link2;
sl@0: 	    SequenceInfo *seq1 = RANDOM_SEQUENCE();
sl@0: 	    SequenceInfo *seq2 = RANDOM_SEQUENCE();
sl@0: 	    GSequenceIter *iter1 = get_random_iter (seq1, &link1);
sl@0: 	    GSequenceIter *iter2 = get_random_iter (seq2, &link2);
sl@0: 	    
sl@0: 	    if (!g_sequence_iter_is_end (iter1))
sl@0: 	      {
sl@0: 		g_sequence_move (iter1, iter2);
sl@0: 		
sl@0: 		if (!link2)
sl@0: 		  g_assert (g_sequence_iter_is_end (iter2));
sl@0: 		
sl@0: 		queue_insert_before (seq2, link2, link1->data);
sl@0: 		
sl@0: 		g_queue_delete_link (seq1->queue, link1);
sl@0: 
sl@0: 		get_item (iter1)->seq = seq2;
sl@0: 		
sl@0: 		seq1->n_items--;
sl@0: 		seq2->n_items++;
sl@0: 	      }
sl@0: 	    
sl@0: 	    check_integrity (seq);
sl@0: 	    
sl@0: 	    iter1 = get_random_iter (seq, NULL);
sl@0: 	    
sl@0: 	    /* Moving an iter to itself should have no effect */
sl@0: 	    if (!g_sequence_iter_is_end (iter1))
sl@0: 	      g_sequence_move (iter1, iter1);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SWAP:
sl@0: 	  {
sl@0: 	    GList *link1, *link2;
sl@0: 	    SequenceInfo *seq1 = RANDOM_SEQUENCE();
sl@0: 	    SequenceInfo *seq2 = RANDOM_SEQUENCE();
sl@0: 	    GSequenceIter *iter1 = get_random_iter (seq1, &link1);
sl@0: 	    GSequenceIter *iter2 = get_random_iter (seq2, &link2);
sl@0: 	    
sl@0: 	    if (!g_sequence_iter_is_end (iter1) &&
sl@0: 		!g_sequence_iter_is_end (iter2))
sl@0: 	      {
sl@0: 		gpointer tmp;
sl@0: 
sl@0: 		g_sequence_swap (iter1, iter2);
sl@0: 
sl@0: 		get_item (iter1)->seq = seq2;
sl@0: 		get_item (iter2)->seq = seq1;
sl@0: 		
sl@0: 		tmp = link1->data;
sl@0: 		link1->data = link2->data;
sl@0: 		link2->data = tmp;
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case INSERT_SORTED:
sl@0: 	  {
sl@0: 	    int i;
sl@0: 	    dump_info (seq);
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    for (i = 0; i < N_TIMES; ++i)
sl@0: 	      {
sl@0: 		GSequenceIter *iter =
sl@0: 		  g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
sl@0: 		
sl@0: 		g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
sl@0: 	      }
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    dump_info (seq);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case INSERT_SORTED_ITER:
sl@0: 	  {
sl@0: 	    int i;
sl@0: 	    dump_info (seq);
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    for (i = 0; i < N_TIMES; ++i)
sl@0: 	      {
sl@0: 		GSequenceIter *iter;
sl@0: 
sl@0: 		iter = g_sequence_insert_sorted_iter (seq->sequence,
sl@0: 						      new_item (seq),
sl@0: 						      (GSequenceIterCompareFunc)compare_iters,
sl@0: 						      seq->sequence);
sl@0: 		
sl@0: 		g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
sl@0: 	      }
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    dump_info (seq);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SORT_CHANGED:
sl@0: 	  {
sl@0: 	    int i;
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    for (i = 0; i < N_TIMES; ++i)
sl@0: 	      {
sl@0: 		GList *link;
sl@0: 		GSequenceIter *iter = get_random_iter (seq, &link);
sl@0: 		
sl@0: 		if (!g_sequence_iter_is_end (iter))
sl@0: 		  {
sl@0: 		    g_sequence_set (iter, new_item (seq));
sl@0: 		    g_sequence_sort_changed (iter, compare_items, NULL);
sl@0: 		    
sl@0: 		    g_queue_delete_link (seq->queue, link);
sl@0: 		    g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
sl@0: 		  }
sl@0: 		
sl@0: 		check_sorted (seq);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SORT_CHANGED_ITER:
sl@0: 	  {
sl@0: 	    int i;
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    for (i = 0; i < N_TIMES; ++i)
sl@0: 	      {
sl@0: 		GList *link;
sl@0: 		GSequenceIter *iter = get_random_iter (seq, &link);
sl@0: 		
sl@0: 		if (!g_sequence_iter_is_end (iter))
sl@0: 		  {
sl@0: 		    g_sequence_set (iter, new_item (seq));
sl@0: 		    g_sequence_sort_changed_iter (iter,
sl@0: 						  (GSequenceIterCompareFunc)compare_iters, seq->sequence);
sl@0: 		    
sl@0: 		    g_queue_delete_link (seq->queue, link);
sl@0: 		    g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
sl@0: 		  }
sl@0: 		
sl@0: 		check_sorted (seq);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case REMOVE:
sl@0: 	  {
sl@0: 	    int i;
sl@0: 	    
sl@0: 	    for (i = 0; i < N_TIMES; ++i)
sl@0: 	      {
sl@0: 		GList *link;
sl@0: 		GSequenceIter *iter = get_random_iter (seq, &link);
sl@0: 		
sl@0: 		if (!g_sequence_iter_is_end (iter))
sl@0: 		  {
sl@0: 		    g_sequence_remove (iter);
sl@0: 		    g_queue_delete_link (seq->queue, link);
sl@0: 		  }
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case REMOVE_RANGE:
sl@0: 	  {
sl@0: 	    GSequenceIter *begin_iter, *end_iter;
sl@0: 	    GList *begin_link, *end_link;
sl@0: 	    GList *list;
sl@0: 	    
sl@0: 	    get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
sl@0: 	    
sl@0: 	    g_sequence_remove_range (begin_iter, end_iter);
sl@0: 	    
sl@0: 	    list = begin_link;
sl@0: 	    while (list != end_link)
sl@0: 	      {
sl@0: 		GList *next = list->next;
sl@0: 		
sl@0: 		g_queue_delete_link (seq->queue, list);
sl@0: 		
sl@0: 		list = next;
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case MOVE_RANGE:
sl@0: 	  {
sl@0: 	    SequenceInfo *src = RANDOM_SEQUENCE();
sl@0: 	    SequenceInfo *dst = RANDOM_SEQUENCE();
sl@0: 	    
sl@0: 	    GSequenceIter *begin_iter, *end_iter;
sl@0: 	    GList *begin_link, *end_link;
sl@0: 	    
sl@0: 	    GSequenceIter *dst_iter;
sl@0: 	    GList *dst_link;
sl@0: 	    
sl@0: 	    GList *list;
sl@0: 	    
sl@0: 	    g_assert (src->queue);
sl@0: 	    g_assert (dst->queue);
sl@0: 	    
sl@0: 	    get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
sl@0: 	    dst_iter = get_random_iter (dst, &dst_link);
sl@0: 	    
sl@0: 	    g_sequence_move_range (dst_iter, begin_iter, end_iter);
sl@0: 	    
sl@0: 	    if (dst_link == begin_link || (src == dst && dst_link == end_link))
sl@0: 	      {
sl@0: 		check_integrity (src);
sl@0: 		check_integrity (dst);
sl@0: 		break;
sl@0: 	      }
sl@0: 	    
sl@0: 	    if (queue_link_index (src, begin_link) >=
sl@0: 		queue_link_index (src, end_link))
sl@0: 	      {
sl@0: 		break;
sl@0: 	      }
sl@0: 	    
sl@0: 	    if (src == dst &&
sl@0: 		queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
sl@0: 		queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
sl@0: 	      {
sl@0: 		break;
sl@0: 	      }
sl@0: 	    
sl@0: 	    list = begin_link;
sl@0: 	    while (list != end_link)
sl@0: 	      {
sl@0: 		GList *next = list->next;
sl@0: 		Item *item = get_item (list->data);
sl@0: 		
sl@0: 		g_assert (dst->queue);
sl@0: 		queue_insert_before (dst, dst_link, list->data);
sl@0: 		g_queue_delete_link (src->queue, list);
sl@0: 		
sl@0: 		g_assert (item->seq == src);
sl@0: 		
sl@0: 		src->n_items--;
sl@0: 		dst->n_items++;
sl@0: 		item->seq = dst;
sl@0: 		
sl@0: 		list = next;
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SEARCH:
sl@0: 	  {
sl@0: 	    Item *item;
sl@0: 	    GSequenceIter *search_iter;
sl@0: 	    GSequenceIter *insert_iter;
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    item = new_item (seq);
sl@0: 	    search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);
sl@0: 	    
sl@0: 	    insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
sl@0: 	    
sl@0: 	    g_assert (search_iter == g_sequence_iter_next (insert_iter));
sl@0: 	    
sl@0: 	    g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case SEARCH_ITER:
sl@0: 	  {
sl@0: 	    Item *item;
sl@0: 	    GSequenceIter *search_iter;
sl@0: 	    GSequenceIter *insert_iter;
sl@0: 	    
sl@0: 	    g_sequence_sort (seq->sequence, compare_items, NULL);
sl@0: 	    g_queue_sort (seq->queue, compare_iters, NULL);
sl@0: 	    
sl@0: 	    check_sorted (seq);
sl@0: 	    
sl@0: 	    item = new_item (seq);
sl@0: 	    search_iter = g_sequence_search_iter (seq->sequence,
sl@0: 						  item,
sl@0: 						  (GSequenceIterCompareFunc)compare_iters, seq->sequence);
sl@0: 	    
sl@0: 	    insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
sl@0: 	    
sl@0: 	    g_assert (search_iter == g_sequence_iter_next (insert_iter));
sl@0: 	    
sl@0: 	    g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	  
sl@0: 	  /* dereferencing */
sl@0: 	case GET:
sl@0: 	case SET:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter;
sl@0: 	    GList *link;
sl@0: 	    
sl@0: 	    iter = get_random_iter (seq, &link);
sl@0: 	    
sl@0: 	    if (!g_sequence_iter_is_end (iter))
sl@0: 	      {
sl@0: 		Item *item;
sl@0: 		int i;
sl@0: 		
sl@0: 		check_integrity (seq);
sl@0: 		
sl@0: 		/* Test basic functionality */
sl@0: 		item = new_item (seq);
sl@0: 		g_sequence_set (iter, item);
sl@0: 		g_assert (g_sequence_get (iter) == item);
sl@0: 		
sl@0: 		/* Make sure that existing items are freed */
sl@0: 		for (i = 0; i < N_TIMES; ++i)
sl@0: 		  g_sequence_set (iter, new_item (seq));
sl@0: 		
sl@0: 		check_integrity (seq);
sl@0: 		
sl@0: 		g_sequence_set (iter, new_item (seq));
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	  
sl@0: 	  /* operations on GSequenceIter * */
sl@0: 	case ITER_IS_BEGIN:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter;
sl@0: 	    
sl@0: 	    iter = g_sequence_get_iter_at_pos (seq->sequence, 0);
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_is_begin (iter));
sl@0: 	    
sl@0: 	    check_integrity (seq);
sl@0: 	    
sl@0: 	    if (g_sequence_get_length (seq->sequence) > 0)
sl@0: 	      {
sl@0: 		g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
sl@0: 	      }
sl@0: 	    else
sl@0: 	      {
sl@0: 		g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
sl@0: 	      }
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case ITER_IS_END:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter;
sl@0: 	    int len = g_sequence_get_length (seq->sequence);
sl@0: 	    
sl@0: 	    iter = g_sequence_get_iter_at_pos (seq->sequence, len);
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_is_end (iter));
sl@0: 	    
sl@0: 	    if (len > 0)
sl@0: 	      {
sl@0: 		g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
sl@0: 	      }
sl@0: 	    else
sl@0: 	      {
sl@0: 		g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
sl@0: 	      }
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case ITER_NEXT:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter1, *iter2, *iter3, *end;
sl@0: 	    
sl@0: 	    iter1 = g_sequence_append (seq->sequence, new_item (seq));
sl@0: 	    iter2 = g_sequence_append (seq->sequence, new_item (seq));
sl@0: 	    iter3 = g_sequence_append (seq->sequence, new_item (seq));
sl@0: 	    
sl@0: 	    end = g_sequence_get_end_iter (seq->sequence);
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_next (iter1) == iter2);
sl@0: 	    g_assert (g_sequence_iter_next (iter2) == iter3);
sl@0: 	    g_assert (g_sequence_iter_next (iter3) == end);
sl@0: 	    g_assert (g_sequence_iter_next (end) == end);
sl@0: 	    
sl@0: 	    g_queue_push_tail (seq->queue, iter1);
sl@0: 	    g_queue_push_tail (seq->queue, iter2);
sl@0: 	    g_queue_push_tail (seq->queue, iter3);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case ITER_PREV:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter1, *iter2, *iter3, *begin;
sl@0: 	    
sl@0: 	    iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
sl@0: 	    iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
sl@0: 	    iter3 = g_sequence_prepend (seq->sequence, new_item (seq));
sl@0: 	    
sl@0: 	    begin = g_sequence_get_begin_iter (seq->sequence);
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_prev (iter1) == iter2);
sl@0: 	    g_assert (g_sequence_iter_prev (iter2) == iter3);
sl@0: 	    g_assert (iter3 == begin);
sl@0: 	    g_assert (g_sequence_iter_prev (iter3) == begin);
sl@0: 	    g_assert (g_sequence_iter_prev (begin) == begin);
sl@0: 	    
sl@0: 	    g_queue_push_head (seq->queue, iter1);
sl@0: 	    g_queue_push_head (seq->queue, iter2);
sl@0: 	    g_queue_push_head (seq->queue, iter3);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case ITER_GET_POSITION:
sl@0: 	  {
sl@0: 	    GList *link;
sl@0: 	    GSequenceIter *iter = get_random_iter (seq, &link);
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_get_position (iter) ==
sl@0: 		      queue_link_index (seq, link));
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case ITER_MOVE:
sl@0: 	  {
sl@0: 	    int len = g_sequence_get_length (seq->sequence);
sl@0: 	    GSequenceIter *iter;
sl@0: 	    int pos;
sl@0: 	    
sl@0: 	    iter = get_random_iter (seq, NULL);
sl@0: 	    pos = g_sequence_iter_get_position (iter);
sl@0: 	    iter = g_sequence_iter_move (iter, len - pos);
sl@0: 	    g_assert (g_sequence_iter_is_end (iter));
sl@0: 	    
sl@0: 	    
sl@0: 	    iter = get_random_iter (seq, NULL);
sl@0: 	    pos = g_sequence_iter_get_position (iter);
sl@0: 	    while (pos < len)
sl@0: 	      {
sl@0: 		g_assert (!g_sequence_iter_is_end (iter));
sl@0: 		pos++;
sl@0: 		iter = g_sequence_iter_move (iter, 1);
sl@0: 	      }
sl@0: 	    g_assert (g_sequence_iter_is_end (iter));
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case ITER_GET_SEQUENCE:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter = get_random_iter (seq, NULL);
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	  
sl@0: 	  /* search */
sl@0: 	case ITER_COMPARE:
sl@0: 	  {
sl@0: 	    GList *link1, *link2;
sl@0: 	    GSequenceIter *iter1 = get_random_iter (seq, &link1);
sl@0: 	    GSequenceIter *iter2 = get_random_iter (seq, &link2);
sl@0: 	    
sl@0: 	    int cmp = g_sequence_iter_compare (iter1, iter2);
sl@0: 	    int pos1 = queue_link_index (seq, link1);
sl@0: 	    int pos2 = queue_link_index (seq, link2);
sl@0: 	    
sl@0: 	    if (cmp == 0)
sl@0: 	      {
sl@0: 		g_assert (pos1 == pos2);
sl@0: 	      }
sl@0: 	    else if (cmp < 0)
sl@0: 	      {
sl@0: 		g_assert (pos1 < pos2);
sl@0: 	      }
sl@0: 	    else
sl@0: 	      {
sl@0: 		g_assert (pos1 > pos2);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case RANGE_GET_MIDPOINT:
sl@0: 	  {
sl@0: 	    GSequenceIter *iter1 = get_random_iter (seq, NULL);
sl@0: 	    GSequenceIter *iter2 = get_random_iter (seq, NULL);
sl@0: 	    GSequenceIter *iter3;
sl@0: 	    int cmp;
sl@0: 	    
sl@0: 	    cmp = g_sequence_iter_compare (iter1, iter2);
sl@0: 	    
sl@0: 	    if (cmp > 0)
sl@0: 	      {
sl@0: 		GSequenceIter *tmp;
sl@0: 		
sl@0: 		tmp = iter1;
sl@0: 		iter1 = iter2;
sl@0: 		iter2 = tmp;
sl@0: 	      }
sl@0: 	    
sl@0: 	    iter3 = g_sequence_range_get_midpoint (iter1, iter2);
sl@0: 	    
sl@0: 	    if (cmp == 0)
sl@0: 	      {
sl@0: 		g_assert (iter3 == iter1);
sl@0: 		g_assert (iter3 == iter2);
sl@0: 	      }
sl@0: 	    
sl@0: 	    g_assert (g_sequence_iter_get_position (iter3) >= 
sl@0: 		      g_sequence_iter_get_position (iter1));
sl@0: 	    g_assert (g_sequence_iter_get_position (iter2) >= 
sl@0: 		      g_sequence_iter_get_position (iter3));
sl@0: 	  }
sl@0: 	  break;
sl@0: 	  
sl@0: 	}
sl@0:       
sl@0:       check_integrity (seq);
sl@0:     }
sl@0: }
sl@0: 
sl@0: /* Random seeds known to have failed at one point
sl@0:  */
sl@0: static gulong seeds[] =
sl@0:   {
sl@0:     825541564u,
sl@0:     801678400u,
sl@0:     1477639090u,
sl@0:     3369132895u,
sl@0:     1192944867u,
sl@0:     770458294u,
sl@0:     1099575817u,
sl@0:     590523467u,
sl@0:     3583571454u,
sl@0:     579241222u
sl@0:   };
sl@0: 
sl@0: static void standalone_tests (void);
sl@0: 
sl@0: static guint32
sl@0: get_seed (int argc, char **argv)
sl@0: {
sl@0:   if (argc > 1)
sl@0:     {
sl@0:       char *endptr;
sl@0:       
sl@0:       return strtol (argv[1], &endptr, 0);
sl@0:     }
sl@0:   else
sl@0:     {
sl@0:       return g_random_int();
sl@0:     }
sl@0: }
sl@0: 
sl@0: int
sl@0: main (int argc,
sl@0:       char **argv)
sl@0: {
sl@0:   guint32 seed = get_seed (argc, argv);
sl@0:   int i;
sl@0:  #ifdef __SYMBIAN32__
sl@0:   g_log_set_handler (NULL,  G_LOG_FLAG_FATAL| G_LOG_FLAG_RECURSION | G_LOG_LEVEL_CRITICAL | G_LOG_LEVEL_WARNING | G_LOG_LEVEL_MESSAGE | G_LOG_LEVEL_INFO | G_LOG_LEVEL_DEBUG, &mrtLogHandler, NULL);
sl@0:   g_set_print_handler(mrtPrintHandler);
sl@0:   #endif /*__SYMBIAN32__*/ 
sl@0:   /* Run stand alone tests */
sl@0:   g_print ("running standalone tests\n");
sl@0:   standalone_tests();
sl@0:   
sl@0:   g_print ("running regression tests:\n");
sl@0:   /* Run regression tests */
sl@0:   for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
sl@0:     {
sl@0:       run_random_tests (seeds[i]);
sl@0:     }
sl@0:   
sl@0:   /* Run with a new random seed */
sl@0:   g_print ("random seed:\n");
sl@0:   run_random_tests (seed);
sl@0:   
sl@0:  #if __SYMBIAN32__
sl@0:   testResultXml("sequence-test");
sl@0:   #endif /* EMULATOR */ 
sl@0:   return 0;
sl@0: }
sl@0: 
sl@0: 
sl@0: /* Single, stand-alone tests */
sl@0: 
sl@0: static void
sl@0: test_out_of_range_jump (void)
sl@0: {
sl@0:   GSequence *seq = g_sequence_new (NULL);
sl@0:   GSequenceIter *iter = g_sequence_get_begin_iter (seq);
sl@0:   
sl@0:   g_sequence_iter_move (iter, 5);
sl@0:   
sl@0:   g_assert (g_sequence_iter_is_begin (iter));
sl@0:   g_assert (g_sequence_iter_is_end (iter));
sl@0: }
sl@0: 
sl@0: static int
sl@0: compare (gconstpointer a, gconstpointer b, gpointer userdata)
sl@0: {
sl@0:   int ai, bi;
sl@0:   
sl@0:   ai = GPOINTER_TO_INT (a);
sl@0:   bi = GPOINTER_TO_INT (b);
sl@0:   
sl@0:   if (ai < bi)
sl@0:     return -1;
sl@0:   else if (ai > bi)
sl@0:     return 1;
sl@0:   else
sl@0:     return 0;
sl@0: }
sl@0: 
sl@0: static int
sl@0: compare_iter (GSequenceIter *a,
sl@0: 	      GSequenceIter *b,
sl@0: 	      gpointer data)
sl@0: {
sl@0:   return compare (g_sequence_get (a),
sl@0: 		  g_sequence_get (b),
sl@0: 		  data);
sl@0: }
sl@0: 
sl@0: static void
sl@0: test_insert_sorted_non_pointer (void)
sl@0: {
sl@0:   int i;
sl@0:   
sl@0:   for (i = 0; i < 10; i++)
sl@0:     {
sl@0:       GSequence *seq = g_sequence_new (NULL);
sl@0:       int j;
sl@0:       
sl@0:       for (j = 0; j < 10000; j++)
sl@0: 	{
sl@0: 	  g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
sl@0: 				    compare, NULL);
sl@0: 	  
sl@0: 	  g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
sl@0: 					 compare_iter, NULL);
sl@0: 	}
sl@0: 
sl@0:       g_sequence_check (seq);
sl@0:       
sl@0:       g_sequence_free (seq);
sl@0:     }
sl@0: }
sl@0: 
sl@0: static void
sl@0: test_stable_sort (void)
sl@0: {
sl@0:   int i;
sl@0:   GSequence *seq = g_sequence_new (NULL);
sl@0:   
sl@0: #define N_ITEMS 1000
sl@0:   
sl@0:   GSequenceIter *iters[N_ITEMS];
sl@0:   GSequenceIter *iter;
sl@0:   
sl@0:   for (i = 0; i < N_ITEMS; ++i)
sl@0:     {
sl@0:       iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000)); 
sl@0:       g_sequence_check (seq);
sl@0:       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
sl@0:    }
sl@0: 
sl@0:   i = 0;
sl@0:   iter = g_sequence_get_begin_iter (seq);
sl@0:   g_assert (g_sequence_iter_get_sequence (iter) == seq);
sl@0:   g_sequence_check (seq);
sl@0:   while (!g_sequence_iter_is_end (iter))
sl@0:     {
sl@0:       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
sl@0:       g_assert (iters[i++] == iter);
sl@0:       
sl@0:       iter = g_sequence_iter_next (iter);
sl@0:       g_sequence_check (seq);
sl@0:     }
sl@0:   
sl@0:   g_sequence_sort (seq, compare, NULL);
sl@0:   
sl@0:   i = 0;
sl@0:   iter = g_sequence_get_begin_iter (seq);
sl@0:   while (!g_sequence_iter_is_end (iter))
sl@0:     {
sl@0:       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
sl@0:       g_assert (iters[i] == iter);
sl@0:       
sl@0:       iter = g_sequence_iter_next (iter);
sl@0:       g_sequence_check (seq);
sl@0: 
sl@0:       i++;
sl@0:     }
sl@0:   
sl@0:   for (i = N_ITEMS - 1; i >= 0; --i)
sl@0:     {
sl@0:       g_sequence_check (seq);
sl@0:       g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
sl@0:       g_assert (g_sequence_get_end_iter (seq) != iters[i]);
sl@0:       g_sequence_sort_changed (iters[i], compare, NULL);
sl@0:     }
sl@0:   
sl@0:   i = 0;
sl@0:   iter = g_sequence_get_begin_iter (seq);
sl@0:   while (!g_sequence_iter_is_end (iter))
sl@0:     {
sl@0:       g_assert (iters[i++] == iter);
sl@0:       
sl@0:       iter = g_sequence_iter_next (iter);
sl@0:       g_sequence_check (seq);
sl@0:     }
sl@0: }
sl@0: 
sl@0: static void
sl@0: standalone_tests (void)
sl@0: {
sl@0:   test_out_of_range_jump ();
sl@0:   test_insert_sorted_non_pointer ();
sl@0:   test_stable_sort ();
sl@0: }
sl@0: