1 /*

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

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

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

     6 * which accompanies this distribution, and is available

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

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 *

    16 */

    17 

    18 #undef G_DISABLE_ASSERT

    19 #undef G_LOG_DOMAIN

    20 

    21 #include <time.h>

    22 #include <stdlib.h>

    23 

    24 #include <glib.h>

    25 

    26 #ifdef __SYMBIAN32__

    27 #include "mrt2_glib2_test.h"

    28 #endif /*__SYMBIAN32__*/

    29 

    30 static gboolean verbose = FALSE;

    31 

    32 

    33 static void

    34 check_integrity (GQueue *queue)

    35 {

    36   GList *list;

    37   GList *last;

    38   GList *links;

    39   GList *link;

    40   gint n;

    41   

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

    43   

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

    45   

    46   if (!queue->head)

    47     g_assert (!queue->tail);

    48   if (!queue->tail)

    49     g_assert (!queue->head);

    50   

    51   n = 0;

    52   last = NULL;

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

    54     {

    55       if (!list->next)

    56 	last = list;

    57       ++n;

    58     }

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

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

    61   

    62   n = 0;

    63   last = NULL;

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

    65     {

    66       if (!list->prev)

    67 	last = list;

    68       ++n;

    69     }

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

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

    72   

    73   links = NULL;

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

    75     links = g_list_prepend (links, list);

    76   

    77   link = links;

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

    79     {

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

    81       link = link->next;

    82     }

    83   g_list_free (links);

    84   

    85   links = NULL;

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

    87     links = g_list_prepend (links, list);

    88   

    89   link = links;

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

    91     {

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

    93       link = link->next;

    94     }

    95   g_list_free (links);

    96 }

    97 

    98 static gboolean

    99 rnd_bool (void)

   100 {

   101   return g_random_int_range (0, 2);

   102 }

   103 

   104 static void

   105 check_max (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 void

   115 check_min (gpointer elm, gpointer user_data)

   116 {

   117   gint *best = user_data;

   118   gint element = GPOINTER_TO_INT (elm);

   119 

   120   if (element < *best)

   121     *best = element;

   122 }

   123 

   124 static gint

   125 find_min (GQueue *queue)

   126 {

   127   gint min = G_MAXINT;

   128 

   129   g_queue_foreach (queue, check_min, &min);

   130 

   131   return min;

   132 }

   133 

   134 static gint

   135 find_max (GQueue *queue)

   136 {

   137   gint max = G_MININT;

   138   

   139   g_queue_foreach (queue, check_max, &max);

   140 

   141   return max;

   142 }

   143 

   144 static void

   145 delete_elm (gpointer elm, gpointer user_data)

   146 {

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

   148   check_integrity ((GQueue *)user_data);

   149 }

   150 

   151 static void

   152 delete_all (GQueue *queue)

   153 {

   154   g_queue_foreach (queue, delete_elm, queue);

   155 }

   156 

   157 static int

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

   159 {

   160   int ai = GPOINTER_TO_INT (a);

   161   int bi = GPOINTER_TO_INT (b);

   162 

   163   if (ai > bi)

   164     return 1;

   165   else if (ai == bi)

   166     return 0;

   167   else

   168     return -1;

   169 }

   170 

   171 static gint

   172 get_random_position (GQueue *queue, gboolean allow_offlist)

   173 {

   174   int n;

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

   176 

   177   if (allow_offlist)

   178     where = g_random_int_range (OFF_QUEUE, LAST);

   179   else

   180     where = g_random_int_range (HEAD, LAST);

   181 

   182   switch (where)

   183     {

   184     case OFF_QUEUE:

   185       n = g_random_int ();

   186       break;

   187 

   188     case HEAD:

   189       n = 0;

   190       break;

   191 

   192     case TAIL:

   193       if (allow_offlist)

   194 	n = queue->length;

   195       else

   196 	n = queue->length - 1;

   197       break;

   198 

   199     case MIDDLE:

   200       if (queue->length == 0)

   201 	n = 0;

   202       else

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

   204       break;

   205 

   206     default:

   207       g_assert_not_reached();

   208       n = 100;

   209       break;

   210 

   211     }

   212 

   213   return n;

   214 }

   215 

   216 static void

   217 random_test (int seed)

   218 {

   219   typedef enum {

   220     IS_EMPTY, GET_LENGTH, REVERSE, COPY,

   221     FOREACH, FIND, FIND_CUSTOM, SORT,

   222     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,

   223     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,

   224     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,

   225     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,

   226     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,

   227     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,

   228     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP

   229   } QueueOp;

   230 

   231 #ifdef __SYMBIAN32__

   232 #define N_ITERATIONS 50000

   233 #else

   234 #define N_ITERATIONS 500000

   235 #endif//__SYMBIAN32__

   236 #define N_QUEUES 3

   237 

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

   239 

   240   typedef struct QueueInfo QueueInfo;

   241   struct QueueInfo

   242   {

   243     GQueue *queue;

   244     GList *tail;

   245     GList *head;

   246     guint length;

   247   };

   248   

   249   gint i;

   250   QueueOp op;

   251   QueueInfo queues[N_QUEUES];

   252 

   253   if (verbose)

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

   255 

   256   g_random_set_seed (seed);

   257   

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

   259     {

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

   261       queues[i].head = NULL;

   262       queues[i].tail = NULL;

   263       queues[i].length = 0;

   264     }

   265   

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

   267     {

   268       int j;

   269       QueueInfo *qinf = RANDOM_QUEUE();

   270       GQueue *q = qinf->queue;

   271       op = g_random_int_range (IS_EMPTY, LAST_OP);

   272 

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

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

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

   276       

   277       switch (op)

   278 	{

   279 	case IS_EMPTY:

   280 	  {

   281 	    if (g_queue_is_empty (qinf->queue))

   282 	      {

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

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

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

   286 	      }

   287 	    else

   288 	      {

   289 		g_assert (q->head);

   290 		g_assert (q->tail);

   291 		g_assert (q->length > 0);

   292 	      }

   293 	  }

   294 	  break;

   295 	case GET_LENGTH:

   296 	  {

   297 	    int l;

   298 	    

   299 	    l = g_queue_get_length (q);

   300 	    

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

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

   303 	  }

   304 	  break;

   305 	case REVERSE:

   306 	  g_queue_reverse (q);

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

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

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

   310 	  qinf->tail = q->tail;

   311 	  qinf->head = q->head;

   312 	  break;

   313 	case COPY:

   314 	  {

   315 	    QueueInfo *random_queue = RANDOM_QUEUE();

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

   317 	    

   318 	    g_queue_free (qinf->queue);

   319 	    q = qinf->queue = new_queue;

   320 	    qinf->head = new_queue->head;

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

   322 	    qinf->length = new_queue->length;

   323 	  }

   324 	  break;

   325 	case FOREACH:

   326 	  delete_all (q);

   327 	  qinf->head = NULL;

   328 	  qinf->tail = NULL;

   329 	  qinf->length = 0;

   330 	  break;

   331 	case FIND:

   332 	  {

   333 	    gboolean find_existing = rnd_bool ();

   334 	    int first = find_max (q);

   335 	    int second = find_min (q);

   336 

   337 	    if (q->length == 0)

   338 	      find_existing = FALSE;

   339 	    

   340 	    if (!find_existing)

   341 	      first++;

   342 	    if (!find_existing)

   343 	      second--;

   344 

   345 	    if (find_existing)

   346 	      {

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

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

   349 	      }

   350 	    else

   351 	      {

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

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

   354 	      }

   355 	  }

   356 	  break;

   357 	case FIND_CUSTOM:

   358 	  break;

   359 	case SORT:

   360 	  {

   361 	    if (!g_queue_is_empty (q))

   362 	      {

   363 		int max = find_max (q);

   364 		int min = find_min (q);

   365 		g_queue_remove_all (q, GINT_TO_POINTER (max));

   366 		check_integrity (q);

   367 		g_queue_remove_all (q, GINT_TO_POINTER (min));

   368 		check_integrity (q);

   369 		g_queue_push_head (q, GINT_TO_POINTER (max));

   370 		if (max != min)

   371 		  g_queue_push_head (q, GINT_TO_POINTER (min));

   372 		qinf->length = q->length;

   373 	      }

   374 

   375 	    check_integrity (q);

   376 	    

   377 	    g_queue_sort (q, compare_int, NULL);

   378 

   379 	    check_integrity (q);

   380 	    

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

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

   383 

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

   385 	  }

   386 	  break;

   387 	case PUSH_HEAD:

   388 	  {

   389 	    int x = g_random_int_range (0, 435435);

   390 	    g_queue_push_head (q, GINT_TO_POINTER (x));

   391 	    if (!qinf->head)

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

   393 	    else

   394 	      qinf->head = qinf->head->prev;

   395 	    qinf->length++;

   396 	  }

   397 	  break;

   398 	case PUSH_TAIL:

   399 	  {

   400 	    int x = g_random_int_range (0, 236546);

   401 	    g_queue_push_tail (q, GINT_TO_POINTER (x));

   402 	    if (!qinf->tail)

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

   404 	    else

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

   406 	    qinf->length++;

   407 	  }

   408 	  break;

   409 	case PUSH_NTH:

   410 	  {

   411 	    int pos = get_random_position (q, TRUE);

   412 	    int x = g_random_int_range (0, 236546);

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

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

   415 	      qinf->head = qinf->head->prev;

   416 	    else

   417 	      qinf->head = q->head;

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

   419 	      qinf->tail = qinf->tail->next;

   420 	    else

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

   422 	    qinf->length++;

   423 	  }

   424 	  break;

   425 	case POP_HEAD:

   426 	  if (qinf->head)

   427 	    qinf->head = qinf->head->next;

   428 	  if (!qinf->head)

   429 	    qinf->tail = NULL;

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

   431 	  g_queue_pop_head (q);

   432 	  break;

   433 	case POP_TAIL:

   434 	  if (qinf->tail)

   435 	    qinf->tail = qinf->tail->prev;

   436 	  if (!qinf->tail)

   437 	    qinf->head = NULL;

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

   439 	  g_queue_pop_tail (q);

   440 	  break;

   441 	case POP_NTH:

   442 	  if (!g_queue_is_empty (q))

   443 	    {

   444 	      int n = get_random_position (q, TRUE);

   445 	      gpointer elm = g_queue_peek_nth (q, n);

   446 

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

   448 		qinf->tail = qinf->tail->prev;

   449 	      

   450 	      if (n == 0)

   451 		qinf->head = qinf->head->next;

   452 

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

   454 		qinf->length--;

   455 	      

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

   457 	    }

   458 	  break;

   459 	case PEEK_HEAD:

   460 	  if (qinf->head)

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

   462 	  else

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

   464 	  break;

   465 	case PEEK_TAIL:

   466 	  if (qinf->head)

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

   468 	  else

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

   470 	  break;

   471 	case PEEK_NTH:

   472 	  if (g_queue_is_empty (q))

   473 	    {

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

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

   476 	    }

   477 	  else

   478 	    {

   479 	      GList *list;

   480 	      int n = get_random_position (q, TRUE);

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

   482 		{

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

   484 		}

   485 	      else

   486 		{

   487 		  list = qinf->head;

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

   489 		    list = list->next;

   490 		  

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

   492 		}

   493 	    }

   494 	  break;

   495 	case INDEX:

   496 	case LINK_INDEX:

   497 	  {

   498 	    int x = g_random_int_range (0, 386538);

   499 	    int n;

   500 	    GList *list;

   501 

   502 	    g_queue_remove_all (q, GINT_TO_POINTER (x));

   503  	    check_integrity (q);

   504 	    g_queue_push_tail (q, GINT_TO_POINTER (x));

   505  	    check_integrity (q);

   506 	    g_queue_sort (q, compare_int, NULL);

   507  	    check_integrity (q);

   508 

   509 	    n = 0;

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

   511 	      {

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

   513 		  break;

   514 		n++;

   515 	      }

   516 	    g_assert (list);

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

   518 		      g_queue_link_index (q, list));

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

   520 

   521 	    qinf->head = q->head;

   522 	    qinf->tail = q->tail;

   523 	    qinf->length = q->length;

   524 	  }

   525 	  break;

   526 	case REMOVE:

   527 	  if (!g_queue_is_empty (q))

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

   529 	  if (!g_queue_is_empty (q))

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

   531 	  if (!g_queue_is_empty (q))

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

   533 

   534 	  qinf->head = q->head;

   535 	  qinf->tail = q->tail;

   536 	  qinf->length = q->length;

   537 	  break;

   538 	case REMOVE_ALL:

   539 	  if (!g_queue_is_empty (q))

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

   541 	  if (!g_queue_is_empty (q))

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

   543 	  if (!g_queue_is_empty (q))

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

   545 

   546 	  qinf->head = q->head;

   547 	  qinf->tail = q->tail;

   548 	  qinf->length = q->length;

   549 	  break;

   550 	case INSERT_BEFORE:

   551 	  if (!g_queue_is_empty (q))

   552 	    {

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

   554 	      

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

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

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

   558 	    }

   559 	  qinf->head = q->head;

   560 	  qinf->tail = q->tail;

   561 	  qinf->length = q->length;

   562 	  break;

   563 	case INSERT_AFTER:

   564 	  if (!g_queue_is_empty (q))

   565 	    {

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

   567 	      

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

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

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

   571 	    }

   572 	  qinf->head = q->head;

   573 	  qinf->tail = q->tail;

   574 	  qinf->length = q->length;

   575 	  break;

   576 	case INSERT_SORTED:

   577 	  {

   578 	    int max = find_max (q);

   579 	    int min = find_min (q);

   580 

   581 	    if (g_queue_is_empty (q))

   582 	      {

   583 		max = 345;

   584 		min = -12;

   585 	      }

   586 	    

   587 	    g_queue_sort (q, compare_int, NULL);

   588  	    check_integrity (q);

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

   590  	    check_integrity (q);

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

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

   593  	    check_integrity (q);

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

   595 	    qinf->head = q->head;

   596 	    qinf->tail = q->tail;

   597 	    qinf->length = q->length;

   598 	  }

   599 	  break;

   600 	case PUSH_HEAD_LINK:

   601 	  {

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

   603 	    g_queue_push_head_link (q, link);

   604 	    if (!qinf->tail)

   605 	      qinf->tail = link;

   606 	    qinf->head = link;

   607 	    qinf->length++;

   608 	  }

   609 	  break;

   610 	case PUSH_TAIL_LINK:

   611 	  {

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

   613 	    g_queue_push_tail_link (q, link);

   614 	    if (!qinf->head)

   615 	      qinf->head = link;

   616 	    qinf->tail = link;

   617 	    qinf->length++;

   618 	  }

   619 	  break;

   620 	case PUSH_NTH_LINK:

   621 	  {

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

   623 	    gint n = get_random_position (q, TRUE);

   624 	    g_queue_push_nth_link (q, n, link);

   625 

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

   627 	      qinf->head = qinf->head->prev;

   628 	    else

   629 	      qinf->head = q->head;

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

   631 	      qinf->tail = qinf->tail->next;

   632 	    else

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

   634 	    qinf->length++;

   635 	  }

   636 	  break;

   637 	case POP_HEAD_LINK:

   638 	  if (!g_queue_is_empty (q))

   639 	    {

   640 	      qinf->head = qinf->head->next;

   641 	      if (!qinf->head)

   642 		qinf->tail = NULL;

   643 	      qinf->length--;

   644 	      g_list_free (g_queue_pop_head_link (q));

   645 	    }

   646 	  break;

   647 	case POP_TAIL_LINK:

   648 	  if (!g_queue_is_empty (q))

   649 	    {

   650 	      qinf->tail = qinf->tail->prev;

   651 	      if (!qinf->tail)

   652 		qinf->head = NULL;

   653 	      qinf->length--;

   654 	      g_list_free (g_queue_pop_tail_link (q));

   655 	    }

   656 	  break;

   657 	case POP_NTH_LINK:

   658 	  if (g_queue_is_empty (q))

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

   660 	  else

   661 	    {

   662 	      int n = get_random_position (q, FALSE);

   663 	      

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

   665 		qinf->tail = qinf->tail->prev;

   666 	      

   667 	      if (n == 0)

   668 		qinf->head = qinf->head->next;

   669 	      

   670 	      qinf->length--;

   671 	      

   672 	      g_list_free (g_queue_pop_nth_link (q, n));

   673 	    }

   674 	  break;

   675 	case PEEK_HEAD_LINK:

   676 	  if (g_queue_is_empty (q))

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

   678 	  else

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

   680 	  break;

   681 	case PEEK_TAIL_LINK:

   682 	  if (g_queue_is_empty (q))

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

   684 	  else

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

   686 	  break;

   687 	case PEEK_NTH_LINK:

   688 	  if (g_queue_is_empty(q))

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

   690 	  else

   691 	    {

   692 	      gint n = get_random_position (q, FALSE);

   693 	      GList *link;

   694 

   695 	      link = q->head;

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

   697 		link = link->next;

   698 

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

   700 	    }

   701 	  break;

   702 	case UNLINK:

   703 	  if (!g_queue_is_empty (q))

   704 	    {

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

   706 	      GList *link;

   707 

   708 	      link = q->head;

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

   710 		link = link->next;

   711 

   712 	      g_queue_unlink (q, link);

   713 	      check_integrity (q);

   714 

   715 	      g_list_free (link);

   716 

   717 	      qinf->head = q->head;

   718 	      qinf->tail = q->tail;

   719 	      qinf->length--;

   720 	    }

   721 	  break;

   722 	case DELETE_LINK:

   723 	  if (!g_queue_is_empty (q))

   724 	    {

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

   726 	      GList *link;

   727 

   728 	      link = q->head;

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

   730 		link = link->next;

   731 

   732 	      g_queue_delete_link (q, link);

   733 	      check_integrity (q);

   734 

   735 	      qinf->head = q->head;

   736 	      qinf->tail = q->tail;

   737 	      qinf->length--;

   738 	    }

   739 	  break;

   740 	case LAST_OP:

   741 	default:

   742 	  g_assert_not_reached();

   743 	  break;

   744 	}

   745 

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

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

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

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

   750 

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

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

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

   754       

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

   756 	check_integrity (queues[j].queue);

   757     }

   758   

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

   760     g_queue_free (queues[i].queue);

   761 }

   762 

   763 static void

   764 remove_item (gpointer data, gpointer q)

   765 {

   766   GQueue *queue = q;

   767   

   768   g_queue_remove (queue, data);

   769 }

   770 

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

   772 {

   773   GQueue *q, *q2;

   774   GList *node;

   775   gpointer data;

   776   int i;

   777   

   778   #ifdef __SYMBIAN32__

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

   780   g_set_print_handler(mrtPrintHandler);

   781   #endif /*__SYMBIAN32__*/

   782 	  

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

   784     verbose = TRUE;

   785 

   786   q = g_queue_new ();

   787   

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

   789   

   790   g_queue_push_head (q, GINT_TO_POINTER (2));

   791   check_integrity (q);

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

   793   check_integrity (q);

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

   795   check_integrity (q);

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

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

   798   g_queue_push_head (q, GINT_TO_POINTER (1));

   799   check_integrity (q);

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

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

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

   803   check_integrity (q);

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

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

   806   check_integrity (q);

   807   g_queue_push_tail (q, GINT_TO_POINTER (3));

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

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

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

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

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

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

   814   g_queue_push_tail (q, GINT_TO_POINTER (4));

   815   check_integrity (q);

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

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

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

   819   g_queue_push_tail (q, GINT_TO_POINTER (5));

   820   check_integrity (q);

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

   822   

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

   824   check_integrity (q);

   825   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   844   

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

   846   check_integrity (q);

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

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

   849   check_integrity (q);

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

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

   852   check_integrity (q);

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

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

   855   check_integrity (q);

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

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

   858   check_integrity (q);

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

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

   861   check_integrity (q);

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

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

   864   check_integrity (q);

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

   866   

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

   868   check_integrity (q);

   869   

   870   /************************/

   871   

   872   g_queue_push_head (q, GINT_TO_POINTER (1));

   873   check_integrity (q);

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

   875   g_queue_push_head (q, GINT_TO_POINTER (2));

   876   check_integrity (q);

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

   878   g_queue_push_head (q, GINT_TO_POINTER (3));

   879   check_integrity (q);

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

   881   g_queue_push_head (q, GINT_TO_POINTER (4));

   882   check_integrity (q);

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

   884   g_queue_push_head (q, GINT_TO_POINTER (5));

   885   check_integrity (q);

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

   887   

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

   889   check_integrity (q);

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

   891   node = q->tail;

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

   893   check_integrity (q);

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

   895   data = q->head->data;

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

   897   check_integrity (q);

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

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

   900   check_integrity (q);

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

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

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

   904   check_integrity (q);

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

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

   907   check_integrity (q);

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

   909   check_integrity (q);

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

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

   912   check_integrity (q);

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

   914   

   915   /* */

   916   g_queue_reverse (q);

   917   check_integrity (q);

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

   919   

   920   q2 = g_queue_copy (q);

   921   check_integrity (q);

   922   check_integrity (q2);

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

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

   925   g_queue_sort (q, compare_int, NULL);

   926   check_integrity (q2);

   927   check_integrity (q);

   928   g_queue_sort (q2, compare_int, NULL);

   929   check_integrity (q2);

   930   check_integrity (q);

   931   

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

   933     {

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

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

   936       check_integrity (q);

   937       check_integrity (q2);

   938     }

   939   

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

   941     {

   942       g_queue_remove (q, GINT_TO_POINTER (i));

   943       check_integrity (q);

   944       check_integrity (q2);

   945     }

   946   

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

   948     {

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

   950       

   951       g_queue_push_nth_link (q, i, l);

   952       check_integrity (q);

   953       check_integrity (q2);

   954       g_queue_reverse (q);

   955       check_integrity (q);

   956       check_integrity (q2);

   957     }

   958   

   959   g_queue_free (q2);

   960   q2 = g_queue_copy (q);

   961   

   962   g_queue_foreach (q2, remove_item, q2);

   963   check_integrity (q2);

   964   check_integrity (q);

   965 

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

   967   g_queue_push_tail (q, GINT_TO_POINTER (1234));

   968   check_integrity (q);

   969   node = g_queue_peek_tail_link (q);

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

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

   972   g_assert (node == NULL);

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

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

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

   976   g_assert (node == NULL);

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

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

   979   

   980   g_queue_free (q);

   981 

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

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

   984   if (argc > 1)

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

   986   else

   987     random_test (time (0));  

   988 #ifdef __SYMBIAN32__

   989   testResultXml("queue-test");

   990 #endif /* EMULATOR */

   991 

   992   return 0;

   993 }

   994