sl@0: /* Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.*/
sl@0: #undef G_DISABLE_ASSERT
sl@0: #undef G_LOG_DOMAIN
sl@0: 
sl@0: #ifdef HAVE_CONFIG_H
sl@0: #  include <config.h>
sl@0: #endif
sl@0: #include <glib.h>
sl@0: #include <time.h>
sl@0: #include <stdlib.h>
sl@0: #include <stdio.h>
sl@0: 
sl@0: #ifdef SYMBIAN
sl@0: #include "mrt2_glib2_test.h"
sl@0: #endif /*SYMBIAN*/
sl@0: 
sl@0: #include <glib.h>
sl@0: 
sl@0: 
sl@0: static gboolean verbose = FALSE;
sl@0: 
sl@0: 
sl@0: static void
sl@0: check_integrity (GQueue *queue)
sl@0: {
sl@0:   GList *list;
sl@0:   GList *last;
sl@0:   GList *links;
sl@0:   GList *link;
sl@0:   gint n;
sl@0:   
sl@0:   g_assert (queue->length < 4000000000u);
sl@0:   
sl@0:   g_assert (g_queue_get_length (queue) == queue->length);
sl@0:   
sl@0:   if (!queue->head)
sl@0:     g_assert (!queue->tail);
sl@0:   if (!queue->tail)
sl@0:     g_assert (!queue->head);
sl@0:   
sl@0:   n = 0;
sl@0:   last = NULL;
sl@0:   for (list = queue->head; list != NULL; list = list->next)
sl@0:     {
sl@0:       if (!list->next)
sl@0: 	last = list;
sl@0:       ++n;
sl@0:     }
sl@0:   g_assert (n == queue->length); 
sl@0:   g_assert (last == queue->tail);
sl@0:   
sl@0:   n = 0;
sl@0:   last = NULL;
sl@0:   for (list = queue->tail; list != NULL; list = list->prev)
sl@0:     {
sl@0:       if (!list->prev)
sl@0: 	last = list;
sl@0:       ++n;
sl@0:     }
sl@0:   g_assert (n == queue->length);
sl@0:   g_assert (last == queue->head);
sl@0:   
sl@0:   links = NULL;
sl@0:   for (list = queue->head; list != NULL; list = list->next)
sl@0:     links = g_list_prepend (links, list);
sl@0:   
sl@0:   link = links;
sl@0:   for (list = queue->tail; list != NULL; list = list->prev)
sl@0:     {
sl@0:       g_assert (list == link->data);
sl@0:       link = link->next;
sl@0:     }
sl@0:   g_list_free (links);
sl@0:   
sl@0:   links = NULL;
sl@0:   for (list = queue->tail; list != NULL; list = list->prev)
sl@0:     links = g_list_prepend (links, list);
sl@0:   
sl@0:   link = links;
sl@0:   for (list = queue->head; list != NULL; list = list->next)
sl@0:     {
sl@0:       g_assert (list == link->data);
sl@0:       link = link->next;
sl@0:     }
sl@0:   g_list_free (links);
sl@0: }
sl@0: 
sl@0: static gboolean
sl@0: rnd_bool (void)
sl@0: {
sl@0:   return g_random_int_range (0, 2);
sl@0: }
sl@0: 
sl@0: static void
sl@0: check_max (gpointer elm, gpointer user_data)
sl@0: {
sl@0:   gint *best = user_data;
sl@0:   gint element = GPOINTER_TO_INT (elm);
sl@0: 
sl@0:   if (element > *best)
sl@0:     *best = element;
sl@0: }
sl@0: 
sl@0: static void
sl@0: check_min (gpointer elm, gpointer user_data)
sl@0: {
sl@0:   gint *best = user_data;
sl@0:   gint element = GPOINTER_TO_INT (elm);
sl@0: 
sl@0:   if (element < *best)
sl@0:     *best = element;
sl@0: }
sl@0: 
sl@0: static gint
sl@0: find_min (GQueue *queue)
sl@0: {
sl@0:   gint min = G_MAXINT;
sl@0: 
sl@0:   g_queue_foreach (queue, check_min, &min);
sl@0: 
sl@0:   return min;
sl@0: }
sl@0: 
sl@0: static gint
sl@0: find_max (GQueue *queue)
sl@0: {
sl@0:   gint max = G_MININT;
sl@0:   
sl@0:   g_queue_foreach (queue, check_max, &max);
sl@0: 
sl@0:   return max;
sl@0: }
sl@0: 
sl@0: static void
sl@0: delete_elm (gpointer elm, gpointer user_data)
sl@0: {
sl@0:   g_queue_remove ((GQueue *)user_data, elm);
sl@0:   check_integrity ((GQueue *)user_data);
sl@0: }
sl@0: 
sl@0: static void
sl@0: delete_all (GQueue *queue)
sl@0: {
sl@0:   g_queue_foreach (queue, delete_elm, queue);
sl@0: }
sl@0: 
sl@0: static int
sl@0: compare_int (gconstpointer a, gconstpointer b, gpointer data)
sl@0: {
sl@0:   int ai = GPOINTER_TO_INT (a);
sl@0:   int 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 0;
sl@0:   else
sl@0:     return -1;
sl@0: }
sl@0: 
sl@0: static gint
sl@0: get_random_position (GQueue *queue, gboolean allow_offlist)
sl@0: {
sl@0:   int n;
sl@0:   enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
sl@0: 
sl@0:   if (allow_offlist)
sl@0:     where = g_random_int_range (OFF_QUEUE, LAST);
sl@0:   else
sl@0:     where = g_random_int_range (HEAD, LAST);
sl@0: 
sl@0:   switch (where)
sl@0:     {
sl@0:     case OFF_QUEUE:
sl@0:       n = g_random_int ();
sl@0:       break;
sl@0: 
sl@0:     case HEAD:
sl@0:       n = 0;
sl@0:       break;
sl@0: 
sl@0:     case TAIL:
sl@0:       if (allow_offlist)
sl@0: 	n = queue->length;
sl@0:       else
sl@0: 	n = queue->length - 1;
sl@0:       break;
sl@0: 
sl@0:     case MIDDLE:
sl@0:       if (queue->length == 0)
sl@0: 	n = 0;
sl@0:       else
sl@0: 	n = g_random_int_range (0, queue->length);
sl@0:       break;
sl@0: 
sl@0:     default:
sl@0:       g_assert_not_reached();
sl@0:       n = 100;
sl@0:       break;
sl@0: 
sl@0:     }
sl@0: 
sl@0:   return n;
sl@0: }
sl@0: 
sl@0: static void
sl@0: random_test (int seed)
sl@0: {
sl@0:   typedef enum {
sl@0:     IS_EMPTY, GET_LENGTH, REVERSE, COPY,
sl@0:     FOREACH, FIND, FIND_CUSTOM, SORT,
sl@0:     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
sl@0:     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
sl@0:     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
sl@0:     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
sl@0:     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
sl@0:     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
sl@0:     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
sl@0:   } QueueOp;
sl@0: 
sl@0: #define N_ITERATIONS 500
sl@0: #define N_QUEUES 3
sl@0: 
sl@0: #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
sl@0: 
sl@0:   typedef struct QueueInfo QueueInfo;
sl@0:   struct QueueInfo
sl@0:   {
sl@0:     GQueue *queue;
sl@0:     GList *tail;
sl@0:     GList *head;
sl@0:     guint length;
sl@0:   };
sl@0:   
sl@0:   gint i;
sl@0:   QueueOp op;
sl@0:   QueueInfo queues[N_QUEUES];
sl@0: 
sl@0:   if (verbose)
sl@0:     g_print ("seed: %d\n", seed);
sl@0: 
sl@0:   g_random_set_seed (seed);
sl@0:   
sl@0:   for (i = 0; i < N_QUEUES; ++i)
sl@0:     {
sl@0:       queues[i].queue = g_queue_new ();
sl@0:       queues[i].head = NULL;
sl@0:       queues[i].tail = NULL;
sl@0:       queues[i].length = 0;
sl@0:     }
sl@0:   
sl@0:   for (i = 0; i < N_ITERATIONS; ++i)
sl@0:     {
sl@0:       int j;
sl@0:       QueueInfo *qinf = RANDOM_QUEUE();
sl@0:       GQueue *q = qinf->queue;
sl@0:       op = g_random_int_range (IS_EMPTY, LAST_OP);
sl@0: 
sl@0:       g_assert (qinf->head == q->head);
sl@0:       g_assert (qinf->tail == q->tail);
sl@0:       g_assert (qinf->length == q->length);
sl@0:       
sl@0:       switch (op)
sl@0: 	{
sl@0: 	case IS_EMPTY:
sl@0: 	  {
sl@0: 	    if (g_queue_is_empty (qinf->queue))
sl@0: 	      {
sl@0: 		g_assert (q->head == NULL);
sl@0: 		g_assert (q->tail == NULL);
sl@0: 		g_assert (q->length == 0);
sl@0: 	      }
sl@0: 	    else
sl@0: 	      {
sl@0: 		g_assert (q->head);
sl@0: 		g_assert (q->tail);
sl@0: 		g_assert (q->length > 0);
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case GET_LENGTH:
sl@0: 	  {
sl@0: 	    int l;
sl@0: 	    
sl@0: 	    l = g_queue_get_length (q);
sl@0: 	    
sl@0: 	    g_assert (qinf->length == q->length);
sl@0: 	    g_assert (qinf->length == l);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case REVERSE:
sl@0: 	  g_queue_reverse (q);
sl@0: 	  g_assert (qinf->tail == q->head);
sl@0: 	  g_assert (qinf->head == q->tail);
sl@0: 	  g_assert (qinf->length == q->length);
sl@0: 	  qinf->tail = q->tail;
sl@0: 	  qinf->head = q->head;
sl@0: 	  break;
sl@0: 	case COPY:
sl@0: 	  {
sl@0: 	    QueueInfo *random_queue = RANDOM_QUEUE();
sl@0: 	    GQueue *new_queue = g_queue_copy (random_queue->queue);
sl@0: 	    
sl@0: 	    g_queue_free (qinf->queue);
sl@0: 	    q = qinf->queue = new_queue;
sl@0: 	    qinf->head = new_queue->head;
sl@0: 	    qinf->tail = g_list_last (new_queue->head);
sl@0: 	    qinf->length = new_queue->length;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case FOREACH:
sl@0: 	  delete_all (q);
sl@0: 	  qinf->head = NULL;
sl@0: 	  qinf->tail = NULL;
sl@0: 	  qinf->length = 0;
sl@0: 	  break;
sl@0: 	case FIND:
sl@0: 	  {
sl@0: 	    gboolean find_existing = rnd_bool ();
sl@0: 	    int first = find_max (q);
sl@0: 	    int second = find_min (q);
sl@0: 
sl@0: 	    if (q->length == 0)
sl@0: 	      find_existing = FALSE;
sl@0: 	    
sl@0: 	    if (!find_existing)
sl@0: 	      first++;
sl@0: 	    if (!find_existing)
sl@0: 	      second--;
sl@0: 
sl@0: 	    if (find_existing)
sl@0: 	      {
sl@0: 		g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
sl@0: 		g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
sl@0: 	      }
sl@0: 	    else
sl@0: 	      {
sl@0: 		g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
sl@0: 		g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
sl@0: 	      }
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case FIND_CUSTOM:
sl@0: 	  break;
sl@0: 	case SORT:
sl@0: 	  {
sl@0: 	    if (!g_queue_is_empty (q))
sl@0: 	      {
sl@0: 		int max = find_max (q);
sl@0: 		int min = find_min (q);
sl@0: 		g_queue_remove_all (q, GINT_TO_POINTER (max));
sl@0: 		check_integrity (q);
sl@0: 		g_queue_remove_all (q, GINT_TO_POINTER (min));
sl@0: 		check_integrity (q);
sl@0: 		g_queue_push_head (q, GINT_TO_POINTER (max));
sl@0: 		if (max != min)
sl@0: 		  g_queue_push_head (q, GINT_TO_POINTER (min));
sl@0: 		qinf->length = q->length;
sl@0: 	      }
sl@0: 
sl@0: 	    check_integrity (q);
sl@0: 	    
sl@0: 	    g_queue_sort (q, compare_int, NULL);
sl@0: 
sl@0: 	    check_integrity (q);
sl@0: 	    
sl@0: 	    qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
sl@0: 	    qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
sl@0: 
sl@0: 	    g_assert (qinf->tail == q->tail);
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PUSH_HEAD:
sl@0: 	  {
sl@0: 	    int x = g_random_int_range (0, 435435);
sl@0: 	    g_queue_push_head (q, GINT_TO_POINTER (x));
sl@0: 	    if (!qinf->head)
sl@0: 	      qinf->tail = qinf->head = q->head;
sl@0: 	    else
sl@0: 	      qinf->head = qinf->head->prev;
sl@0: 	    qinf->length++;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PUSH_TAIL:
sl@0: 	  {
sl@0: 	    int x = g_random_int_range (0, 236546);
sl@0: 	    g_queue_push_tail (q, GINT_TO_POINTER (x));
sl@0: 	    if (!qinf->tail)
sl@0: 	      qinf->tail = qinf->head = q->head;
sl@0: 	    else
sl@0: 	      qinf->tail = qinf->tail->next;
sl@0: 	    qinf->length++;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PUSH_NTH:
sl@0: 	  {
sl@0: 	    int pos = get_random_position (q, TRUE);
sl@0: 	    int x = g_random_int_range (0, 236546);
sl@0: 	    g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
sl@0: 	    if (qinf->head && qinf->head->prev)
sl@0: 	      qinf->head = qinf->head->prev;
sl@0: 	    else
sl@0: 	      qinf->head = q->head;
sl@0: 	    if (qinf->tail && qinf->tail->next)
sl@0: 	      qinf->tail = qinf->tail->next;
sl@0: 	    else
sl@0: 	      qinf->tail = g_list_last (qinf->head);
sl@0: 	    qinf->length++;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case POP_HEAD:
sl@0: 	  if (qinf->head)
sl@0: 	    qinf->head = qinf->head->next;
sl@0: 	  if (!qinf->head)
sl@0: 	    qinf->tail = NULL;
sl@0: 	  qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
sl@0: 	  g_queue_pop_head (q);
sl@0: 	  break;
sl@0: 	case POP_TAIL:
sl@0: 	  if (qinf->tail)
sl@0: 	    qinf->tail = qinf->tail->prev;
sl@0: 	  if (!qinf->tail)
sl@0: 	    qinf->head = NULL;
sl@0: 	  qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
sl@0: 	  g_queue_pop_tail (q);
sl@0: 	  break;
sl@0: 	case POP_NTH:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      int n = get_random_position (q, TRUE);
sl@0: 	      gpointer elm = g_queue_peek_nth (q, n);
sl@0: 
sl@0: 	      if (n == q->length - 1)
sl@0: 		qinf->tail = qinf->tail->prev;
sl@0: 	      
sl@0: 	      if (n == 0)
sl@0: 		qinf->head = qinf->head->next;
sl@0: 
sl@0: 	      if (n >= 0 && n < q->length)
sl@0: 		qinf->length--;
sl@0: 	      
sl@0: 	      g_assert (elm == g_queue_pop_nth (q, n));
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case PEEK_HEAD:
sl@0: 	  if (qinf->head)
sl@0: 	    g_assert (qinf->head->data == g_queue_peek_head (q));
sl@0: 	  else
sl@0: 	    g_assert (g_queue_peek_head (q) == NULL);
sl@0: 	  break;
sl@0: 	case PEEK_TAIL:
sl@0: 	  if (qinf->head)
sl@0: 	    g_assert (qinf->tail->data == g_queue_peek_tail (q));
sl@0: 	  else
sl@0: 	    g_assert (g_queue_peek_tail (q) == NULL);
sl@0: 	  break;
sl@0: 	case PEEK_NTH:
sl@0: 	  if (g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      for (j = -10; j < 10; ++j)
sl@0: 		g_assert (g_queue_peek_nth (q, j) == NULL);
sl@0: 	    }
sl@0: 	  else
sl@0: 	    {
sl@0: 	      GList *list;
sl@0: 	      int n = get_random_position (q, TRUE);
sl@0: 	      if (n < 0 || n >= q->length)
sl@0: 		{
sl@0: 		  g_assert (g_queue_peek_nth (q, n) == NULL);
sl@0: 		}
sl@0: 	      else
sl@0: 		{
sl@0: 		  list = qinf->head;
sl@0: 		  for (j = 0; j < n; ++j)
sl@0: 		    list = list->next;
sl@0: 		  
sl@0: 		  g_assert (list->data == g_queue_peek_nth (q, n));
sl@0: 		}
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case INDEX:
sl@0: 	case LINK_INDEX:
sl@0: 	  {
sl@0: 	    int x = g_random_int_range (0, 386538);
sl@0: 	    int n;
sl@0: 	    GList *list;
sl@0: 
sl@0: 	    g_queue_remove_all (q, GINT_TO_POINTER (x));
sl@0:  	    check_integrity (q);
sl@0: 	    g_queue_push_tail (q, GINT_TO_POINTER (x));
sl@0:  	    check_integrity (q);
sl@0: 	    g_queue_sort (q, compare_int, NULL);
sl@0:  	    check_integrity (q);
sl@0: 
sl@0: 	    n = 0;
sl@0: 	    for (list = q->head; list != NULL; list = list->next)
sl@0: 	      {
sl@0: 		if (list->data == GINT_TO_POINTER (x))
sl@0: 		  break;
sl@0: 		n++;
sl@0: 	      }
sl@0: 	    g_assert (list);
sl@0: 	    g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
sl@0: 		      g_queue_link_index (q, list));
sl@0: 	    g_assert (g_queue_link_index (q, list) == n);
sl@0: 
sl@0: 	    qinf->head = q->head;
sl@0: 	    qinf->tail = q->tail;
sl@0: 	    qinf->length = q->length;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case REMOVE:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    g_queue_remove (q, qinf->tail->data);
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    g_queue_remove (q, qinf->head->data);
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
sl@0: 
sl@0: 	  qinf->head = q->head;
sl@0: 	  qinf->tail = q->tail;
sl@0: 	  qinf->length = q->length;
sl@0: 	  break;
sl@0: 	case REMOVE_ALL:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    g_queue_remove_all (q, qinf->tail->data);
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    g_queue_remove_all (q, qinf->head->data);
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
sl@0: 
sl@0: 	  qinf->head = q->head;
sl@0: 	  qinf->tail = q->tail;
sl@0: 	  qinf->length = q->length;
sl@0: 	  break;
sl@0: 	case INSERT_BEFORE:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
sl@0: 	      
sl@0: 	      g_queue_insert_before (q, qinf->tail, x);
sl@0: 	      g_queue_insert_before (q, qinf->head, x);
sl@0: 	      g_queue_insert_before (q, g_queue_find (q, x), x);
sl@0: 	    }
sl@0: 	  qinf->head = q->head;
sl@0: 	  qinf->tail = q->tail;
sl@0: 	  qinf->length = q->length;
sl@0: 	  break;
sl@0: 	case INSERT_AFTER:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
sl@0: 	      
sl@0: 	      g_queue_insert_after (q, qinf->tail, x);
sl@0: 	      g_queue_insert_after (q, qinf->head, x);
sl@0: 	      g_queue_insert_after (q, g_queue_find (q, x), x);
sl@0: 	    }
sl@0: 	  qinf->head = q->head;
sl@0: 	  qinf->tail = q->tail;
sl@0: 	  qinf->length = q->length;
sl@0: 	  break;
sl@0: 	case INSERT_SORTED:
sl@0: 	  {
sl@0: 	    int max = find_max (q);
sl@0: 	    int min = find_min (q);
sl@0: 
sl@0: 	    if (g_queue_is_empty (q))
sl@0: 	      {
sl@0: 		max = 345;
sl@0: 		min = -12;
sl@0: 	      }
sl@0: 	    
sl@0: 	    g_queue_sort (q, compare_int, NULL);
sl@0:  	    check_integrity (q);
sl@0: 	    g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
sl@0:  	    check_integrity (q);
sl@0: 	    g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
sl@0: 	    g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
sl@0:  	    check_integrity (q);
sl@0: 	    g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
sl@0: 	    qinf->head = q->head;
sl@0: 	    qinf->tail = q->tail;
sl@0: 	    qinf->length = q->length;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PUSH_HEAD_LINK:
sl@0: 	  {
sl@0: 	    GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
sl@0: 	    g_queue_push_head_link (q, link);
sl@0: 	    if (!qinf->tail)
sl@0: 	      qinf->tail = link;
sl@0: 	    qinf->head = link;
sl@0: 	    qinf->length++;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PUSH_TAIL_LINK:
sl@0: 	  {
sl@0: 	    GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
sl@0: 	    g_queue_push_tail_link (q, link);
sl@0: 	    if (!qinf->head)
sl@0: 	      qinf->head = link;
sl@0: 	    qinf->tail = link;
sl@0: 	    qinf->length++;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case PUSH_NTH_LINK:
sl@0: 	  {
sl@0: 	    GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
sl@0: 	    gint n = get_random_position (q, TRUE);
sl@0: 	    g_queue_push_nth_link (q, n, link);
sl@0: 
sl@0: 	    if (qinf->head && qinf->head->prev)
sl@0: 	      qinf->head = qinf->head->prev;
sl@0: 	    else
sl@0: 	      qinf->head = q->head;
sl@0: 	    if (qinf->tail && qinf->tail->next)
sl@0: 	      qinf->tail = qinf->tail->next;
sl@0: 	    else
sl@0: 	      qinf->tail = g_list_last (qinf->head);
sl@0: 	    qinf->length++;
sl@0: 	  }
sl@0: 	  break;
sl@0: 	case POP_HEAD_LINK:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      qinf->head = qinf->head->next;
sl@0: 	      if (!qinf->head)
sl@0: 		qinf->tail = NULL;
sl@0: 	      qinf->length--;
sl@0: 	      g_list_free (g_queue_pop_head_link (q));
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case POP_TAIL_LINK:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      qinf->tail = qinf->tail->prev;
sl@0: 	      if (!qinf->tail)
sl@0: 		qinf->head = NULL;
sl@0: 	      qinf->length--;
sl@0: 	      g_list_free (g_queue_pop_tail_link (q));
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case POP_NTH_LINK:
sl@0: 	  if (g_queue_is_empty (q))
sl@0: 	    g_assert (g_queue_pop_nth_link (q, 200) == NULL);
sl@0: 	  else
sl@0: 	    {
sl@0: 	      int n = get_random_position (q, FALSE);
sl@0: 	      
sl@0: 	      if (n == g_queue_get_length (q) - 1)
sl@0: 		qinf->tail = qinf->tail->prev;
sl@0: 	      
sl@0: 	      if (n == 0)
sl@0: 		qinf->head = qinf->head->next;
sl@0: 	      
sl@0: 	      qinf->length--;
sl@0: 	      
sl@0: 	      g_list_free (g_queue_pop_nth_link (q, n));
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case PEEK_HEAD_LINK:
sl@0: 	  if (g_queue_is_empty (q))
sl@0: 	    g_assert (g_queue_peek_head_link (q) == NULL);
sl@0: 	  else
sl@0: 	    g_assert (g_queue_peek_head_link (q) == qinf->head);
sl@0: 	  break;
sl@0: 	case PEEK_TAIL_LINK:
sl@0: 	  if (g_queue_is_empty (q))
sl@0: 	    g_assert (g_queue_peek_tail_link (q) == NULL);
sl@0: 	  else
sl@0: 	    g_assert (g_queue_peek_tail_link (q) == qinf->tail);
sl@0: 	  break;
sl@0: 	case PEEK_NTH_LINK:
sl@0: 	  if (g_queue_is_empty(q))
sl@0: 	    g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
sl@0: 	  else
sl@0: 	    {
sl@0: 	      gint n = get_random_position (q, FALSE);
sl@0: 	      GList *link;
sl@0: 
sl@0: 	      link = q->head;
sl@0: 	      for (j = 0; j < n; ++j)
sl@0: 		link = link->next;
sl@0: 
sl@0: 	      g_assert (g_queue_peek_nth_link (q, n) == link);
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case UNLINK:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      gint n = g_random_int_range (0, g_queue_get_length (q));
sl@0: 	      GList *link;
sl@0: 
sl@0: 	      link = q->head;
sl@0: 	      for (j = 0; j < n; ++j)
sl@0: 		link = link->next;
sl@0: 
sl@0: 	      g_queue_unlink (q, link);
sl@0: 	      check_integrity (q);
sl@0: 
sl@0: 	      g_list_free (link);
sl@0: 
sl@0: 	      qinf->head = q->head;
sl@0: 	      qinf->tail = q->tail;
sl@0: 	      qinf->length--;
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case DELETE_LINK:
sl@0: 	  if (!g_queue_is_empty (q))
sl@0: 	    {
sl@0: 	      gint n = g_random_int_range (0, g_queue_get_length (q));
sl@0: 	      GList *link;
sl@0: 
sl@0: 	      link = q->head;
sl@0: 	      for (j = 0; j < n; ++j)
sl@0: 		link = link->next;
sl@0: 
sl@0: 	      g_queue_delete_link (q, link);
sl@0: 	      check_integrity (q);
sl@0: 
sl@0: 	      qinf->head = q->head;
sl@0: 	      qinf->tail = q->tail;
sl@0: 	      qinf->length--;
sl@0: 	    }
sl@0: 	  break;
sl@0: 	case LAST_OP:
sl@0: 	default:
sl@0: 	  g_assert_not_reached();
sl@0: 	  break;
sl@0: 	}
sl@0: 
sl@0:       if (qinf->head != q->head ||
sl@0: 	  qinf->tail != q->tail ||
sl@0: 	  qinf->length != q->length)
sl@0: 	g_print ("op: %d\n", op);
sl@0: 
sl@0:       g_assert (qinf->head == q->head);
sl@0:       g_assert (qinf->tail == q->tail);
sl@0:       g_assert (qinf->length == q->length);
sl@0:       
sl@0:       for (j = 0; j < N_QUEUES; ++j)
sl@0: 	check_integrity (queues[j].queue);
sl@0:     }
sl@0:   
sl@0:   for (i = 0; i < N_QUEUES; ++i)
sl@0:     g_queue_free (queues[i].queue);
sl@0: }
sl@0: 
sl@0: static void
sl@0: remove_item (gpointer data, gpointer q)
sl@0: {
sl@0:   GQueue *queue = q;
sl@0:   
sl@0:   g_queue_remove (queue, data);
sl@0: }
sl@0: 
sl@0: int main(int argc, gchar *args[])
sl@0: {
sl@0:   GQueue *q, *q2;
sl@0:   GList *node;
sl@0:   gpointer data;
sl@0:   int i;
sl@0:   
sl@0:   #ifdef SYMBIAN
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 /*SYMBIAN*/
sl@0: 	  
sl@0:   if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v')
sl@0:     verbose = TRUE;
sl@0: 
sl@0:   q = g_queue_new ();
sl@0:   
sl@0:   g_assert (g_queue_is_empty (q) == TRUE);
sl@0:   
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (2));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_queue_is_empty (q) == FALSE);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 1);
sl@0:   g_assert (q->head == q->tail);
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (1));
sl@0:   check_integrity (q);
sl@0:   g_assert (q->head->next == q->tail);
sl@0:   g_assert (q->tail->prev == q->head);
sl@0:   g_assert (g_list_length (q->head) == 2);
sl@0:   check_integrity (q);
sl@0:   g_assert (q->tail->data == GINT_TO_POINTER (2));
sl@0:   g_assert (q->head->data == GINT_TO_POINTER (1));
sl@0:   check_integrity (q);
sl@0:   g_queue_push_tail (q, GINT_TO_POINTER (3));
sl@0:   g_assert (g_list_length (q->head) == 3);
sl@0:   g_assert (q->head->data == GINT_TO_POINTER (1));
sl@0:   g_assert (q->head->next->data == GINT_TO_POINTER (2));
sl@0:   g_assert (q->head->next->next == q->tail);
sl@0:   g_assert (q->head->next == q->tail->prev);
sl@0:   g_assert (q->tail->data == GINT_TO_POINTER (3));
sl@0:   g_queue_push_tail (q, GINT_TO_POINTER (4));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 4);
sl@0:   g_assert (q->head->data == GINT_TO_POINTER (1));
sl@0:   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
sl@0:   g_queue_push_tail (q, GINT_TO_POINTER (5));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 5);
sl@0:   
sl@0:   g_assert (g_queue_is_empty (q) == FALSE);
sl@0:   check_integrity (q);
sl@0:   
sl@0:   g_assert (q->length == 5);
sl@0:   g_assert (q->head->prev == NULL);
sl@0:   g_assert (q->head->data == GINT_TO_POINTER (1));
sl@0:   g_assert (q->head->next->data == GINT_TO_POINTER (2));
sl@0:   g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
sl@0:   g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
sl@0:   g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
sl@0:   g_assert (q->head->next->next->next->next->next == NULL);
sl@0:   g_assert (q->head->next->next->next->next == q->tail);
sl@0:   g_assert (q->tail->data == GINT_TO_POINTER (5));
sl@0:   g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
sl@0:   g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
sl@0:   g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
sl@0:   g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
sl@0:   g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
sl@0:   g_assert (q->tail->prev->prev->prev->prev == q->head);
sl@0:   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
sl@0:   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
sl@0:   
sl@0:   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 4 && q->length == 4);
sl@0:   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 3);
sl@0:   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 2);
sl@0:   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 1);
sl@0:   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   g_assert (g_queue_pop_tail (q) == NULL);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   g_assert (g_queue_pop_head (q) == NULL);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   
sl@0:   g_assert (g_queue_is_empty (q) == TRUE);
sl@0:   check_integrity (q);
sl@0:   
sl@0:   /************************/
sl@0:   
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (1));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 1 && 1 == q->length);
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (2));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 2 && 2 == q->length);
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (3));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 3 && 3 == q->length);
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (4));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 4 && 4 == q->length);
sl@0:   g_queue_push_head (q, GINT_TO_POINTER (5));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 5 && 5 == q->length);
sl@0:   
sl@0:   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 4);
sl@0:   node = q->tail;
sl@0:   g_assert (node == g_queue_pop_tail_link (q));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 3);
sl@0:   data = q->head->data;
sl@0:   g_assert (data == g_queue_pop_head (q));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 2);
sl@0:   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 1);
sl@0:   g_assert (q->head == q->tail);
sl@0:   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   g_assert (g_queue_pop_head (q) == NULL);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_queue_pop_head_link (q) == NULL);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   g_assert (g_queue_pop_tail_link (q) == NULL);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   
sl@0:   /* */
sl@0:   g_queue_reverse (q);
sl@0:   check_integrity (q);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   
sl@0:   q2 = g_queue_copy (q);
sl@0:   check_integrity (q);
sl@0:   check_integrity (q2);
sl@0:   g_assert (g_list_length (q->head) == 0);
sl@0:   g_assert (g_list_length (q2->head) == 0);
sl@0:   g_queue_sort (q, compare_int, NULL);
sl@0:   check_integrity (q2);
sl@0:   check_integrity (q);
sl@0:   g_queue_sort (q2, compare_int, NULL);
sl@0:   check_integrity (q2);
sl@0:   check_integrity (q);
sl@0:   
sl@0:   for (i = 0; i < 200; ++i)
sl@0:     {
sl@0:       g_queue_push_nth (q, GINT_TO_POINTER (i), i);
sl@0:       g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
sl@0:       check_integrity (q);
sl@0:       check_integrity (q2);
sl@0:     }
sl@0:   
sl@0:   for (i = 0; i < 200; ++i)
sl@0:     {
sl@0:       g_queue_remove (q, GINT_TO_POINTER (i));
sl@0:       check_integrity (q);
sl@0:       check_integrity (q2);
sl@0:     }
sl@0:   
sl@0:   for (i = 0; i < 200; ++i)
sl@0:     {
sl@0:       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
sl@0:       
sl@0:       g_queue_push_nth_link (q, i, l);
sl@0:       check_integrity (q);
sl@0:       check_integrity (q2);
sl@0:       g_queue_reverse (q);
sl@0:       check_integrity (q);
sl@0:       check_integrity (q2);
sl@0:     }
sl@0:   
sl@0:   g_queue_free (q2);
sl@0:   q2 = g_queue_copy (q);
sl@0:   
sl@0:   g_queue_foreach (q2, remove_item, q2);
sl@0:   check_integrity (q2);
sl@0:   check_integrity (q);
sl@0: 
sl@0:   /* some checks for off by one errors */  
sl@0:   g_queue_push_tail (q, GINT_TO_POINTER (1234));
sl@0:   check_integrity (q);
sl@0:   node = g_queue_peek_tail_link (q);
sl@0:   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
sl@0:   node = g_queue_peek_nth_link (q, g_queue_get_length (q));
sl@0:   g_assert (node == NULL);
sl@0:   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
sl@0:   g_assert (node->data == GINT_TO_POINTER (1234));
sl@0:   node = g_queue_pop_nth_link (q, g_queue_get_length (q));
sl@0:   g_assert (node == NULL);
sl@0:   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
sl@0:   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
sl@0:   
sl@0:   g_queue_free (q);
sl@0: 
sl@0:   if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v')
sl@0:     random_test (strtol (args[2], NULL, 0));    
sl@0:   if (argc > 1)
sl@0:     random_test (strtol (args[1], NULL, 0));
sl@0:   else
sl@0:     random_test (time (0));  
sl@0: #ifdef SYMBIAN
sl@0:   testResultXml("queue-test");
sl@0: #endif /* EMULATOR */
sl@0: 
sl@0:   return 0;
sl@0: }
sl@0: