1 /* Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.*/

     2 #undef G_DISABLE_ASSERT

     3 #undef G_LOG_DOMAIN

     4 

     5 #ifdef HAVE_CONFIG_H

     6 #  include <config.h>

     7 #endif

     8 #include <glib.h>

     9 #include <time.h>

    10 #include <stdlib.h>

    11 #include <stdio.h>

    12 

    13 #ifdef __SYMBIAN32__

    14 #include "mrt2_glib2_test.h"

    15 #endif /*__SYMBIAN32__*/

    16 

    17 #include <glib.h>

    18 

    19 

    20 static gboolean verbose = FALSE;

    21 

    22 

    23 static void

    24 check_integrity (GQueue *queue)

    25 {

    26   GList *list;

    27   GList *last;

    28   GList *links;

    29   GList *link;

    30   gint n;

    31   

    32   g_assert (queue->length < 4000000000u);

    33   

    34   g_assert (g_queue_get_length (queue) == queue->length);

    35   

    36   if (!queue->head)

    37     g_assert (!queue->tail);

    38   if (!queue->tail)

    39     g_assert (!queue->head);

    40   

    41   n = 0;

    42   last = NULL;

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

    44     {

    45       if (!list->next)

    46 	last = list;

    47       ++n;

    48     }

    49   g_assert (n == queue->length); 

    50   g_assert (last == queue->tail);

    51   

    52   n = 0;

    53   last = NULL;

    54   for (list = queue->tail; list != NULL; list = list->prev)

    55     {

    56       if (!list->prev)

    57 	last = list;

    58       ++n;

    59     }

    60   g_assert (n == queue->length);

    61   g_assert (last == queue->head);

    62   

    63   links = NULL;

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

    65     links = g_list_prepend (links, list);

    66   

    67   link = links;

    68   for (list = queue->tail; list != NULL; list = list->prev)

    69     {

    70       g_assert (list == link->data);

    71       link = link->next;

    72     }

    73   g_list_free (links);

    74   

    75   links = NULL;

    76   for (list = queue->tail; list != NULL; list = list->prev)

    77     links = g_list_prepend (links, list);

    78   

    79   link = links;

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

    81     {

    82       g_assert (list == link->data);

    83       link = link->next;

    84     }

    85   g_list_free (links);

    86 }

    87 

    88 static gboolean

    89 rnd_bool (void)

    90 {

    91   return g_random_int_range (0, 2);

    92 }

    93 

    94 static void

    95 check_max (gpointer elm, gpointer user_data)

    96 {

    97   gint *best = user_data;

    98   gint element = GPOINTER_TO_INT (elm);

    99 

   100   if (element > *best)

   101     *best = element;

   102 }

   103 

   104 static void

   105 check_min (gpointer elm, gpointer user_data)

   106 {

   107   gint *best = user_data;

   108   gint element = GPOINTER_TO_INT (elm);

   109 

   110   if (element < *best)

   111     *best = element;

   112 }

   113 

   114 static gint

   115 find_min (GQueue *queue)

   116 {

   117   gint min = G_MAXINT;

   118 

   119   g_queue_foreach (queue, check_min, &min);

   120 

   121   return min;

   122 }

   123 

   124 static gint

   125 find_max (GQueue *queue)

   126 {

   127   gint max = G_MININT;

   128   

   129   g_queue_foreach (queue, check_max, &max);

   130 

   131   return max;

   132 }

   133 

   134 static void

   135 delete_elm (gpointer elm, gpointer user_data)

   136 {

   137   g_queue_remove ((GQueue *)user_data, elm);

   138   check_integrity ((GQueue *)user_data);

   139 }

   140 

   141 static void

   142 delete_all (GQueue *queue)

   143 {

   144   g_queue_foreach (queue, delete_elm, queue);

   145 }

   146 

   147 static int

   148 compare_int (gconstpointer a, gconstpointer b, gpointer data)

   149 {

   150   int ai = GPOINTER_TO_INT (a);

   151   int bi = GPOINTER_TO_INT (b);

   152 

   153   if (ai > bi)

   154     return 1;

   155   else if (ai == bi)

   156     return 0;

   157   else

   158     return -1;

   159 }

   160 

   161 static gint

   162 get_random_position (GQueue *queue, gboolean allow_offlist)

   163 {

   164   int n;

   165   enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;

   166 

   167   if (allow_offlist)

   168     where = g_random_int_range (OFF_QUEUE, LAST);

   169   else

   170     where = g_random_int_range (HEAD, LAST);

   171 

   172   switch (where)

   173     {

   174     case OFF_QUEUE:

   175       n = g_random_int ();

   176       break;

   177 

   178     case HEAD:

   179       n = 0;

   180       break;

   181 

   182     case TAIL:

   183       if (allow_offlist)

   184 	n = queue->length;

   185       else

   186 	n = queue->length - 1;

   187       break;

   188 

   189     case MIDDLE:

   190       if (queue->length == 0)

   191 	n = 0;

   192       else

   193 	n = g_random_int_range (0, queue->length);

   194       break;

   195 

   196     default:

   197       g_assert_not_reached();

   198       n = 100;

   199       break;

   200 

   201     }

   202 

   203   return n;

   204 }

   205 

   206 static void

   207 random_test (int seed)

   208 {

   209   typedef enum {

   210     IS_EMPTY, GET_LENGTH, REVERSE, COPY,

   211     FOREACH, FIND, FIND_CUSTOM, SORT,

   212     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,

   213     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,

   214     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,

   215     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,

   216     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,

   217     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,

   218     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP

   219   } QueueOp;

   220 

   221 #define N_ITERATIONS 500

   222 #define N_QUEUES 3

   223 

   224 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])

   225 

   226   typedef struct QueueInfo QueueInfo;

   227   struct QueueInfo

   228   {

   229     GQueue *queue;

   230     GList *tail;

   231     GList *head;

   232     guint length;

   233   };

   234   

   235   gint i;

   236   QueueOp op;

   237   QueueInfo queues[N_QUEUES];

   238 

   239   if (verbose)

   240     g_print ("seed: %d\n", seed);

   241 

   242   g_random_set_seed (seed);

   243   

   244   for (i = 0; i < N_QUEUES; ++i)

   245     {

   246       queues[i].queue = g_queue_new ();

   247       queues[i].head = NULL;

   248       queues[i].tail = NULL;

   249       queues[i].length = 0;

   250     }

   251   

   252   for (i = 0; i < N_ITERATIONS; ++i)

   253     {

   254       int j;

   255       QueueInfo *qinf = RANDOM_QUEUE();

   256       GQueue *q = qinf->queue;

   257       op = g_random_int_range (IS_EMPTY, LAST_OP);

   258 

   259       g_assert (qinf->head == q->head);

   260       g_assert (qinf->tail == q->tail);

   261       g_assert (qinf->length == q->length);

   262       

   263       switch (op)

   264 	{

   265 	case IS_EMPTY:

   266 	  {

   267 	    if (g_queue_is_empty (qinf->queue))

   268 	      {

   269 		g_assert (q->head == NULL);

   270 		g_assert (q->tail == NULL);

   271 		g_assert (q->length == 0);

   272 	      }

   273 	    else

   274 	      {

   275 		g_assert (q->head);

   276 		g_assert (q->tail);

   277 		g_assert (q->length > 0);

   278 	      }

   279 	  }

   280 	  break;

   281 	case GET_LENGTH:

   282 	  {

   283 	    int l;

   284 	    

   285 	    l = g_queue_get_length (q);

   286 	    

   287 	    g_assert (qinf->length == q->length);

   288 	    g_assert (qinf->length == l);

   289 	  }

   290 	  break;

   291 	case REVERSE:

   292 	  g_queue_reverse (q);

   293 	  g_assert (qinf->tail == q->head);

   294 	  g_assert (qinf->head == q->tail);

   295 	  g_assert (qinf->length == q->length);

   296 	  qinf->tail = q->tail;

   297 	  qinf->head = q->head;

   298 	  break;

   299 	case COPY:

   300 	  {

   301 	    QueueInfo *random_queue = RANDOM_QUEUE();

   302 	    GQueue *new_queue = g_queue_copy (random_queue->queue);

   303 	    

   304 	    g_queue_free (qinf->queue);

   305 	    q = qinf->queue = new_queue;

   306 	    qinf->head = new_queue->head;

   307 	    qinf->tail = g_list_last (new_queue->head);

   308 	    qinf->length = new_queue->length;

   309 	  }

   310 	  break;

   311 	case FOREACH:

   312 	  delete_all (q);

   313 	  qinf->head = NULL;

   314 	  qinf->tail = NULL;

   315 	  qinf->length = 0;

   316 	  break;

   317 	case FIND:

   318 	  {

   319 	    gboolean find_existing = rnd_bool ();

   320 	    int first = find_max (q);

   321 	    int second = find_min (q);

   322 

   323 	    if (q->length == 0)

   324 	      find_existing = FALSE;

   325 	    

   326 	    if (!find_existing)

   327 	      first++;

   328 	    if (!find_existing)

   329 	      second--;

   330 

   331 	    if (find_existing)

   332 	      {

   333 		g_assert (g_queue_find (q, GINT_TO_POINTER (first)));

   334 		g_assert (g_queue_find (q, GINT_TO_POINTER (second)));

   335 	      }

   336 	    else

   337 	      {

   338 		g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));

   339 		g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));

   340 	      }

   341 	  }

   342 	  break;

   343 	case FIND_CUSTOM:

   344 	  break;

   345 	case SORT:

   346 	  {

   347 	    if (!g_queue_is_empty (q))

   348 	      {

   349 		int max = find_max (q);

   350 		int min = find_min (q);

   351 		g_queue_remove_all (q, GINT_TO_POINTER (max));

   352 		check_integrity (q);

   353 		g_queue_remove_all (q, GINT_TO_POINTER (min));

   354 		check_integrity (q);

   355 		g_queue_push_head (q, GINT_TO_POINTER (max));

   356 		if (max != min)

   357 		  g_queue_push_head (q, GINT_TO_POINTER (min));

   358 		qinf->length = q->length;

   359 	      }

   360 

   361 	    check_integrity (q);

   362 	    

   363 	    g_queue_sort (q, compare_int, NULL);

   364 

   365 	    check_integrity (q);

   366 	    

   367 	    qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));

   368 	    qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));

   369 

   370 	    g_assert (qinf->tail == q->tail);

   371 	  }

   372 	  break;

   373 	case PUSH_HEAD:

   374 	  {

   375 	    int x = g_random_int_range (0, 435435);

   376 	    g_queue_push_head (q, GINT_TO_POINTER (x));

   377 	    if (!qinf->head)

   378 	      qinf->tail = qinf->head = q->head;

   379 	    else

   380 	      qinf->head = qinf->head->prev;

   381 	    qinf->length++;

   382 	  }

   383 	  break;

   384 	case PUSH_TAIL:

   385 	  {

   386 	    int x = g_random_int_range (0, 236546);

   387 	    g_queue_push_tail (q, GINT_TO_POINTER (x));

   388 	    if (!qinf->tail)

   389 	      qinf->tail = qinf->head = q->head;

   390 	    else

   391 	      qinf->tail = qinf->tail->next;

   392 	    qinf->length++;

   393 	  }

   394 	  break;

   395 	case PUSH_NTH:

   396 	  {

   397 	    int pos = get_random_position (q, TRUE);

   398 	    int x = g_random_int_range (0, 236546);

   399 	    g_queue_push_nth (q, GINT_TO_POINTER (x), pos);

   400 	    if (qinf->head && qinf->head->prev)

   401 	      qinf->head = qinf->head->prev;

   402 	    else

   403 	      qinf->head = q->head;

   404 	    if (qinf->tail && qinf->tail->next)

   405 	      qinf->tail = qinf->tail->next;

   406 	    else

   407 	      qinf->tail = g_list_last (qinf->head);

   408 	    qinf->length++;

   409 	  }

   410 	  break;

   411 	case POP_HEAD:

   412 	  if (qinf->head)

   413 	    qinf->head = qinf->head->next;

   414 	  if (!qinf->head)

   415 	    qinf->tail = NULL;

   416 	  qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;

   417 	  g_queue_pop_head (q);

   418 	  break;

   419 	case POP_TAIL:

   420 	  if (qinf->tail)

   421 	    qinf->tail = qinf->tail->prev;

   422 	  if (!qinf->tail)

   423 	    qinf->head = NULL;

   424 	  qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;

   425 	  g_queue_pop_tail (q);

   426 	  break;

   427 	case POP_NTH:

   428 	  if (!g_queue_is_empty (q))

   429 	    {

   430 	      int n = get_random_position (q, TRUE);

   431 	      gpointer elm = g_queue_peek_nth (q, n);

   432 

   433 	      if (n == q->length - 1)

   434 		qinf->tail = qinf->tail->prev;

   435 	      

   436 	      if (n == 0)

   437 		qinf->head = qinf->head->next;

   438 

   439 	      if (n >= 0 && n < q->length)

   440 		qinf->length--;

   441 	      

   442 	      g_assert (elm == g_queue_pop_nth (q, n));

   443 	    }

   444 	  break;

   445 	case PEEK_HEAD:

   446 	  if (qinf->head)

   447 	    g_assert (qinf->head->data == g_queue_peek_head (q));

   448 	  else

   449 	    g_assert (g_queue_peek_head (q) == NULL);

   450 	  break;

   451 	case PEEK_TAIL:

   452 	  if (qinf->head)

   453 	    g_assert (qinf->tail->data == g_queue_peek_tail (q));

   454 	  else

   455 	    g_assert (g_queue_peek_tail (q) == NULL);

   456 	  break;

   457 	case PEEK_NTH:

   458 	  if (g_queue_is_empty (q))

   459 	    {

   460 	      for (j = -10; j < 10; ++j)

   461 		g_assert (g_queue_peek_nth (q, j) == NULL);

   462 	    }

   463 	  else

   464 	    {

   465 	      GList *list;

   466 	      int n = get_random_position (q, TRUE);

   467 	      if (n < 0 || n >= q->length)

   468 		{

   469 		  g_assert (g_queue_peek_nth (q, n) == NULL);

   470 		}

   471 	      else

   472 		{

   473 		  list = qinf->head;

   474 		  for (j = 0; j < n; ++j)

   475 		    list = list->next;

   476 		  

   477 		  g_assert (list->data == g_queue_peek_nth (q, n));

   478 		}

   479 	    }

   480 	  break;

   481 	case INDEX:

   482 	case LINK_INDEX:

   483 	  {

   484 	    int x = g_random_int_range (0, 386538);

   485 	    int n;

   486 	    GList *list;

   487 

   488 	    g_queue_remove_all (q, GINT_TO_POINTER (x));

   489  	    check_integrity (q);

   490 	    g_queue_push_tail (q, GINT_TO_POINTER (x));

   491  	    check_integrity (q);

   492 	    g_queue_sort (q, compare_int, NULL);

   493  	    check_integrity (q);

   494 

   495 	    n = 0;

   496 	    for (list = q->head; list != NULL; list = list->next)

   497 	      {

   498 		if (list->data == GINT_TO_POINTER (x))

   499 		  break;

   500 		n++;

   501 	      }

   502 	    g_assert (list);

   503 	    g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==

   504 		      g_queue_link_index (q, list));

   505 	    g_assert (g_queue_link_index (q, list) == n);

   506 

   507 	    qinf->head = q->head;

   508 	    qinf->tail = q->tail;

   509 	    qinf->length = q->length;

   510 	  }

   511 	  break;

   512 	case REMOVE:

   513 	  if (!g_queue_is_empty (q))

   514 	    g_queue_remove (q, qinf->tail->data);

   515 	  if (!g_queue_is_empty (q))

   516 	    g_queue_remove (q, qinf->head->data);

   517 	  if (!g_queue_is_empty (q))

   518 	    g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));

   519 

   520 	  qinf->head = q->head;

   521 	  qinf->tail = q->tail;

   522 	  qinf->length = q->length;

   523 	  break;

   524 	case REMOVE_ALL:

   525 	  if (!g_queue_is_empty (q))

   526 	    g_queue_remove_all (q, qinf->tail->data);

   527 	  if (!g_queue_is_empty (q))

   528 	    g_queue_remove_all (q, qinf->head->data);

   529 	  if (!g_queue_is_empty (q))

   530 	    g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));

   531 

   532 	  qinf->head = q->head;

   533 	  qinf->tail = q->tail;

   534 	  qinf->length = q->length;

   535 	  break;

   536 	case INSERT_BEFORE:

   537 	  if (!g_queue_is_empty (q))

   538 	    {

   539 	      gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));

   540 	      

   541 	      g_queue_insert_before (q, qinf->tail, x);

   542 	      g_queue_insert_before (q, qinf->head, x);

   543 	      g_queue_insert_before (q, g_queue_find (q, x), x);

   544 	    }

   545 	  qinf->head = q->head;

   546 	  qinf->tail = q->tail;

   547 	  qinf->length = q->length;

   548 	  break;

   549 	case INSERT_AFTER:

   550 	  if (!g_queue_is_empty (q))

   551 	    {

   552 	      gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));

   553 	      

   554 	      g_queue_insert_after (q, qinf->tail, x);

   555 	      g_queue_insert_after (q, qinf->head, x);

   556 	      g_queue_insert_after (q, g_queue_find (q, x), x);

   557 	    }

   558 	  qinf->head = q->head;

   559 	  qinf->tail = q->tail;

   560 	  qinf->length = q->length;

   561 	  break;

   562 	case INSERT_SORTED:

   563 	  {

   564 	    int max = find_max (q);

   565 	    int min = find_min (q);

   566 

   567 	    if (g_queue_is_empty (q))

   568 	      {

   569 		max = 345;

   570 		min = -12;

   571 	      }

   572 	    

   573 	    g_queue_sort (q, compare_int, NULL);

   574  	    check_integrity (q);

   575 	    g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);

   576  	    check_integrity (q);

   577 	    g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);

   578 	    g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);

   579  	    check_integrity (q);

   580 	    g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);

   581 	    qinf->head = q->head;

   582 	    qinf->tail = q->tail;

   583 	    qinf->length = q->length;

   584 	  }

   585 	  break;

   586 	case PUSH_HEAD_LINK:

   587 	  {

   588 	    GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));

   589 	    g_queue_push_head_link (q, link);

   590 	    if (!qinf->tail)

   591 	      qinf->tail = link;

   592 	    qinf->head = link;

   593 	    qinf->length++;

   594 	  }

   595 	  break;

   596 	case PUSH_TAIL_LINK:

   597 	  {

   598 	    GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));

   599 	    g_queue_push_tail_link (q, link);

   600 	    if (!qinf->head)

   601 	      qinf->head = link;

   602 	    qinf->tail = link;

   603 	    qinf->length++;

   604 	  }

   605 	  break;

   606 	case PUSH_NTH_LINK:

   607 	  {

   608 	    GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));

   609 	    gint n = get_random_position (q, TRUE);

   610 	    g_queue_push_nth_link (q, n, link);

   611 

   612 	    if (qinf->head && qinf->head->prev)

   613 	      qinf->head = qinf->head->prev;

   614 	    else

   615 	      qinf->head = q->head;

   616 	    if (qinf->tail && qinf->tail->next)

   617 	      qinf->tail = qinf->tail->next;

   618 	    else

   619 	      qinf->tail = g_list_last (qinf->head);

   620 	    qinf->length++;

   621 	  }

   622 	  break;

   623 	case POP_HEAD_LINK:

   624 	  if (!g_queue_is_empty (q))

   625 	    {

   626 	      qinf->head = qinf->head->next;

   627 	      if (!qinf->head)

   628 		qinf->tail = NULL;

   629 	      qinf->length--;

   630 	      g_list_free (g_queue_pop_head_link (q));

   631 	    }

   632 	  break;

   633 	case POP_TAIL_LINK:

   634 	  if (!g_queue_is_empty (q))

   635 	    {

   636 	      qinf->tail = qinf->tail->prev;

   637 	      if (!qinf->tail)

   638 		qinf->head = NULL;

   639 	      qinf->length--;

   640 	      g_list_free (g_queue_pop_tail_link (q));

   641 	    }

   642 	  break;

   643 	case POP_NTH_LINK:

   644 	  if (g_queue_is_empty (q))

   645 	    g_assert (g_queue_pop_nth_link (q, 200) == NULL);

   646 	  else

   647 	    {

   648 	      int n = get_random_position (q, FALSE);

   649 	      

   650 	      if (n == g_queue_get_length (q) - 1)

   651 		qinf->tail = qinf->tail->prev;

   652 	      

   653 	      if (n == 0)

   654 		qinf->head = qinf->head->next;

   655 	      

   656 	      qinf->length--;

   657 	      

   658 	      g_list_free (g_queue_pop_nth_link (q, n));

   659 	    }

   660 	  break;

   661 	case PEEK_HEAD_LINK:

   662 	  if (g_queue_is_empty (q))

   663 	    g_assert (g_queue_peek_head_link (q) == NULL);

   664 	  else

   665 	    g_assert (g_queue_peek_head_link (q) == qinf->head);

   666 	  break;

   667 	case PEEK_TAIL_LINK:

   668 	  if (g_queue_is_empty (q))

   669 	    g_assert (g_queue_peek_tail_link (q) == NULL);

   670 	  else

   671 	    g_assert (g_queue_peek_tail_link (q) == qinf->tail);

   672 	  break;

   673 	case PEEK_NTH_LINK:

   674 	  if (g_queue_is_empty(q))

   675 	    g_assert (g_queue_peek_nth_link (q, 1000) == NULL);

   676 	  else

   677 	    {

   678 	      gint n = get_random_position (q, FALSE);

   679 	      GList *link;

   680 

   681 	      link = q->head;

   682 	      for (j = 0; j < n; ++j)

   683 		link = link->next;

   684 

   685 	      g_assert (g_queue_peek_nth_link (q, n) == link);

   686 	    }

   687 	  break;

   688 	case UNLINK:

   689 	  if (!g_queue_is_empty (q))

   690 	    {

   691 	      gint n = g_random_int_range (0, g_queue_get_length (q));

   692 	      GList *link;

   693 

   694 	      link = q->head;

   695 	      for (j = 0; j < n; ++j)

   696 		link = link->next;

   697 

   698 	      g_queue_unlink (q, link);

   699 	      check_integrity (q);

   700 

   701 	      g_list_free (link);

   702 

   703 	      qinf->head = q->head;

   704 	      qinf->tail = q->tail;

   705 	      qinf->length--;

   706 	    }

   707 	  break;

   708 	case DELETE_LINK:

   709 	  if (!g_queue_is_empty (q))

   710 	    {

   711 	      gint n = g_random_int_range (0, g_queue_get_length (q));

   712 	      GList *link;

   713 

   714 	      link = q->head;

   715 	      for (j = 0; j < n; ++j)

   716 		link = link->next;

   717 

   718 	      g_queue_delete_link (q, link);

   719 	      check_integrity (q);

   720 

   721 	      qinf->head = q->head;

   722 	      qinf->tail = q->tail;

   723 	      qinf->length--;

   724 	    }

   725 	  break;

   726 	case LAST_OP:

   727 	default:

   728 	  g_assert_not_reached();

   729 	  break;

   730 	}

   731 

   732       if (qinf->head != q->head ||

   733 	  qinf->tail != q->tail ||

   734 	  qinf->length != q->length)

   735 	g_print ("op: %d\n", op);

   736 

   737       g_assert (qinf->head == q->head);

   738       g_assert (qinf->tail == q->tail);

   739       g_assert (qinf->length == q->length);

   740       

   741       for (j = 0; j < N_QUEUES; ++j)

   742 	check_integrity (queues[j].queue);

   743     }

   744   

   745   for (i = 0; i < N_QUEUES; ++i)

   746     g_queue_free (queues[i].queue);

   747 }

   748 

   749 static void

   750 remove_item (gpointer data, gpointer q)

   751 {

   752   GQueue *queue = q;

   753   

   754   g_queue_remove (queue, data);

   755 }

   756 

   757 int main(int argc, gchar *args[])

   758 {

   759   GQueue *q, *q2;

   760   GList *node;

   761   gpointer data;

   762   int i;

   763   

   764   #ifdef __SYMBIAN32__

   765   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);

   766   g_set_print_handler(mrtPrintHandler);

   767   #endif /*__SYMBIAN32__*/

   768 	  

   769   if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v')

   770     verbose = TRUE;

   771 

   772   q = g_queue_new ();

   773   

   774   g_assert (g_queue_is_empty (q) == TRUE);

   775   

   776   g_queue_push_head (q, GINT_TO_POINTER (2));

   777   check_integrity (q);

   778   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));

   779   check_integrity (q);

   780   g_assert (g_queue_is_empty (q) == FALSE);

   781   check_integrity (q);

   782   g_assert (g_list_length (q->head) == 1);

   783   g_assert (q->head == q->tail);

   784   g_queue_push_head (q, GINT_TO_POINTER (1));

   785   check_integrity (q);

   786   g_assert (q->head->next == q->tail);

   787   g_assert (q->tail->prev == q->head);

   788   g_assert (g_list_length (q->head) == 2);

   789   check_integrity (q);

   790   g_assert (q->tail->data == GINT_TO_POINTER (2));

   791   g_assert (q->head->data == GINT_TO_POINTER (1));

   792   check_integrity (q);

   793   g_queue_push_tail (q, GINT_TO_POINTER (3));

   794   g_assert (g_list_length (q->head) == 3);

   795   g_assert (q->head->data == GINT_TO_POINTER (1));

   796   g_assert (q->head->next->data == GINT_TO_POINTER (2));

   797   g_assert (q->head->next->next == q->tail);

   798   g_assert (q->head->next == q->tail->prev);

   799   g_assert (q->tail->data == GINT_TO_POINTER (3));

   800   g_queue_push_tail (q, GINT_TO_POINTER (4));

   801   check_integrity (q);

   802   g_assert (g_list_length (q->head) == 4);

   803   g_assert (q->head->data == GINT_TO_POINTER (1));

   804   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));

   805   g_queue_push_tail (q, GINT_TO_POINTER (5));

   806   check_integrity (q);

   807   g_assert (g_list_length (q->head) == 5);

   808   

   809   g_assert (g_queue_is_empty (q) == FALSE);

   810   check_integrity (q);

   811   

   812   g_assert (q->length == 5);

   813   g_assert (q->head->prev == NULL);

   814   g_assert (q->head->data == GINT_TO_POINTER (1));

   815   g_assert (q->head->next->data == GINT_TO_POINTER (2));

   816   g_assert (q->head->next->next->data == GINT_TO_POINTER (3));

   817   g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));

   818   g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));

   819   g_assert (q->head->next->next->next->next->next == NULL);

   820   g_assert (q->head->next->next->next->next == q->tail);

   821   g_assert (q->tail->data == GINT_TO_POINTER (5));

   822   g_assert (q->tail->prev->data == GINT_TO_POINTER (4));

   823   g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));

   824   g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));

   825   g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));

   826   g_assert (q->tail->prev->prev->prev->prev->prev == NULL);

   827   g_assert (q->tail->prev->prev->prev->prev == q->head);

   828   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));

   829   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));

   830   

   831   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));

   832   check_integrity (q);

   833   g_assert (g_list_length (q->head) == 4 && q->length == 4);

   834   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));

   835   check_integrity (q);

   836   g_assert (g_list_length (q->head) == 3);

   837   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));

   838   check_integrity (q);

   839   g_assert (g_list_length (q->head) == 2);

   840   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));

   841   check_integrity (q);

   842   g_assert (g_list_length (q->head) == 1);

   843   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));

   844   check_integrity (q);

   845   g_assert (g_list_length (q->head) == 0);

   846   g_assert (g_queue_pop_tail (q) == NULL);

   847   check_integrity (q);

   848   g_assert (g_list_length (q->head) == 0);

   849   g_assert (g_queue_pop_head (q) == NULL);

   850   check_integrity (q);

   851   g_assert (g_list_length (q->head) == 0);

   852   

   853   g_assert (g_queue_is_empty (q) == TRUE);

   854   check_integrity (q);

   855   

   856   /************************/

   857   

   858   g_queue_push_head (q, GINT_TO_POINTER (1));

   859   check_integrity (q);

   860   g_assert (g_list_length (q->head) == 1 && 1 == q->length);

   861   g_queue_push_head (q, GINT_TO_POINTER (2));

   862   check_integrity (q);

   863   g_assert (g_list_length (q->head) == 2 && 2 == q->length);

   864   g_queue_push_head (q, GINT_TO_POINTER (3));

   865   check_integrity (q);

   866   g_assert (g_list_length (q->head) == 3 && 3 == q->length);

   867   g_queue_push_head (q, GINT_TO_POINTER (4));

   868   check_integrity (q);

   869   g_assert (g_list_length (q->head) == 4 && 4 == q->length);

   870   g_queue_push_head (q, GINT_TO_POINTER (5));

   871   check_integrity (q);

   872   g_assert (g_list_length (q->head) == 5 && 5 == q->length);

   873   

   874   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));

   875   check_integrity (q);

   876   g_assert (g_list_length (q->head) == 4);

   877   node = q->tail;

   878   g_assert (node == g_queue_pop_tail_link (q));

   879   check_integrity (q);

   880   g_assert (g_list_length (q->head) == 3);

   881   data = q->head->data;

   882   g_assert (data == g_queue_pop_head (q));

   883   check_integrity (q);

   884   g_assert (g_list_length (q->head) == 2);

   885   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));

   886   check_integrity (q);

   887   g_assert (g_list_length (q->head) == 1);

   888   g_assert (q->head == q->tail);

   889   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));

   890   check_integrity (q);

   891   g_assert (g_list_length (q->head) == 0);

   892   g_assert (g_queue_pop_head (q) == NULL);

   893   check_integrity (q);

   894   g_assert (g_queue_pop_head_link (q) == NULL);

   895   check_integrity (q);

   896   g_assert (g_list_length (q->head) == 0);

   897   g_assert (g_queue_pop_tail_link (q) == NULL);

   898   check_integrity (q);

   899   g_assert (g_list_length (q->head) == 0);

   900   

   901   /* */

   902   g_queue_reverse (q);

   903   check_integrity (q);

   904   g_assert (g_list_length (q->head) == 0);

   905   

   906   q2 = g_queue_copy (q);

   907   check_integrity (q);

   908   check_integrity (q2);

   909   g_assert (g_list_length (q->head) == 0);

   910   g_assert (g_list_length (q2->head) == 0);

   911   g_queue_sort (q, compare_int, NULL);

   912   check_integrity (q2);

   913   check_integrity (q);

   914   g_queue_sort (q2, compare_int, NULL);

   915   check_integrity (q2);

   916   check_integrity (q);

   917   

   918   for (i = 0; i < 200; ++i)

   919     {

   920       g_queue_push_nth (q, GINT_TO_POINTER (i), i);

   921       g_assert (g_queue_find (q, GINT_TO_POINTER (i)));

   922       check_integrity (q);

   923       check_integrity (q2);

   924     }

   925   

   926   for (i = 0; i < 200; ++i)

   927     {

   928       g_queue_remove (q, GINT_TO_POINTER (i));

   929       check_integrity (q);

   930       check_integrity (q2);

   931     }

   932   

   933   for (i = 0; i < 200; ++i)

   934     {

   935       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));

   936       

   937       g_queue_push_nth_link (q, i, l);

   938       check_integrity (q);

   939       check_integrity (q2);

   940       g_queue_reverse (q);

   941       check_integrity (q);

   942       check_integrity (q2);

   943     }

   944   

   945   g_queue_free (q2);

   946   q2 = g_queue_copy (q);

   947   

   948   g_queue_foreach (q2, remove_item, q2);

   949   check_integrity (q2);

   950   check_integrity (q);

   951 

   952   /* some checks for off by one errors */  

   953   g_queue_push_tail (q, GINT_TO_POINTER (1234));

   954   check_integrity (q);

   955   node = g_queue_peek_tail_link (q);

   956   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));

   957   node = g_queue_peek_nth_link (q, g_queue_get_length (q));

   958   g_assert (node == NULL);

   959   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);

   960   g_assert (node->data == GINT_TO_POINTER (1234));

   961   node = g_queue_pop_nth_link (q, g_queue_get_length (q));

   962   g_assert (node == NULL);

   963   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);

   964   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));

   965   

   966   g_queue_free (q);

   967 

   968   if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v')

   969     random_test (strtol (args[2], NULL, 0));    

   970   if (argc > 1)

   971     random_test (strtol (args[1], NULL, 0));

   972   else

   973     random_test (time (0));  

   974 #ifdef __SYMBIAN32__

   975   testResultXml("queue-test");

   976 #endif /* EMULATOR */

   977 

   978   return 0;

   979 }

   980