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 #include <time.h>

     6 #include <stdlib.h>

     7 

     8 #include <glib.h>

     9 

    10 #ifdef __SYMBIAN32__

    11 #include "mrt2_glib2_test.h"

    12 #endif /*__SYMBIAN32__*/

    13 

    14 static gboolean verbose = FALSE;

    15 

    16 

    17 static void

    18 check_integrity (GQueue *queue)

    19 {

    20   GList *list;

    21   GList *last;

    22   GList *links;

    23   GList *link;

    24   gint n;

    25   

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

    27   

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

    29   

    30   if (!queue->head)

    31     g_assert (!queue->tail);

    32   if (!queue->tail)

    33     g_assert (!queue->head);

    34   

    35   n = 0;

    36   last = NULL;

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

    38     {

    39       if (!list->next)

    40 	last = list;

    41       ++n;

    42     }

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

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

    45   

    46   n = 0;

    47   last = NULL;

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

    49     {

    50       if (!list->prev)

    51 	last = list;

    52       ++n;

    53     }

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

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

    56   

    57   links = NULL;

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

    59     links = g_list_prepend (links, list);

    60   

    61   link = links;

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

    63     {

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

    65       link = link->next;

    66     }

    67   g_list_free (links);

    68   

    69   links = NULL;

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

    71     links = g_list_prepend (links, list);

    72   

    73   link = links;

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

    75     {

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

    77       link = link->next;

    78     }

    79   g_list_free (links);

    80 }

    81 

    82 static gboolean

    83 rnd_bool (void)

    84 {

    85   return g_random_int_range (0, 2);

    86 }

    87 

    88 static void

    89 check_max (gpointer elm, gpointer user_data)

    90 {

    91   gint *best = user_data;

    92   gint element = GPOINTER_TO_INT (elm);

    93 

    94   if (element > *best)

    95     *best = element;

    96 }

    97 

    98 static void

    99 check_min (gpointer elm, gpointer user_data)

   100 {

   101   gint *best = user_data;

   102   gint element = GPOINTER_TO_INT (elm);

   103 

   104   if (element < *best)

   105     *best = element;

   106 }

   107 

   108 static gint

   109 find_min (GQueue *queue)

   110 {

   111   gint min = G_MAXINT;

   112 

   113   g_queue_foreach (queue, check_min, &min);

   114 

   115   return min;

   116 }

   117 

   118 static gint

   119 find_max (GQueue *queue)

   120 {

   121   gint max = G_MININT;

   122   

   123   g_queue_foreach (queue, check_max, &max);

   124 

   125   return max;

   126 }

   127 

   128 static void

   129 delete_elm (gpointer elm, gpointer user_data)

   130 {

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

   132   check_integrity ((GQueue *)user_data);

   133 }

   134 

   135 static void

   136 delete_all (GQueue *queue)

   137 {

   138   g_queue_foreach (queue, delete_elm, queue);

   139 }

   140 

   141 static int

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

   143 {

   144   int ai = GPOINTER_TO_INT (a);

   145   int bi = GPOINTER_TO_INT (b);

   146 

   147   if (ai > bi)

   148     return 1;

   149   else if (ai == bi)

   150     return 0;

   151   else

   152     return -1;

   153 }

   154 

   155 static gint

   156 get_random_position (GQueue *queue, gboolean allow_offlist)

   157 {

   158   int n;

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

   160 

   161   if (allow_offlist)

   162     where = g_random_int_range (OFF_QUEUE, LAST);

   163   else

   164     where = g_random_int_range (HEAD, LAST);

   165 

   166   switch (where)

   167     {

   168     case OFF_QUEUE:

   169       n = g_random_int ();

   170       break;

   171 

   172     case HEAD:

   173       n = 0;

   174       break;

   175 

   176     case TAIL:

   177       if (allow_offlist)

   178 	n = queue->length;

   179       else

   180 	n = queue->length - 1;

   181       break;

   182 

   183     case MIDDLE:

   184       if (queue->length == 0)

   185 	n = 0;

   186       else

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

   188       break;

   189 

   190     default:

   191       g_assert_not_reached();

   192       n = 100;

   193       break;

   194 

   195     }

   196 

   197   return n;

   198 }

   199 

   200 static void

   201 random_test (int seed)

   202 {

   203   typedef enum {

   204     IS_EMPTY, GET_LENGTH, REVERSE, COPY,

   205     FOREACH, FIND, FIND_CUSTOM, SORT,

   206     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,

   207     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,

   208     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,

   209     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,

   210     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,

   211     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,

   212     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP

   213   } QueueOp;

   214 

   215 #ifdef __SYMBIAN32__

   216 #define N_ITERATIONS 50000

   217 #else

   218 #define N_ITERATIONS 500000

   219 #endif//__SYMBIAN32__

   220 #define N_QUEUES 3

   221 

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

   223 

   224   typedef struct QueueInfo QueueInfo;

   225   struct QueueInfo

   226   {

   227     GQueue *queue;

   228     GList *tail;

   229     GList *head;

   230     guint length;

   231   };

   232   

   233   gint i;

   234   QueueOp op;

   235   QueueInfo queues[N_QUEUES];

   236 

   237   if (verbose)

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

   239 

   240   g_random_set_seed (seed);

   241   

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

   243     {

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

   245       queues[i].head = NULL;

   246       queues[i].tail = NULL;

   247       queues[i].length = 0;

   248     }

   249   

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

   251     {

   252       int j;

   253       QueueInfo *qinf = RANDOM_QUEUE();

   254       GQueue *q = qinf->queue;

   255       op = g_random_int_range (IS_EMPTY, LAST_OP);

   256 

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

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

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

   260       

   261       switch (op)

   262 	{

   263 	case IS_EMPTY:

   264 	  {

   265 	    if (g_queue_is_empty (qinf->queue))

   266 	      {

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

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

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

   270 	      }

   271 	    else

   272 	      {

   273 		g_assert (q->head);

   274 		g_assert (q->tail);

   275 		g_assert (q->length > 0);

   276 	      }

   277 	  }

   278 	  break;

   279 	case GET_LENGTH:

   280 	  {

   281 	    int l;

   282 	    

   283 	    l = g_queue_get_length (q);

   284 	    

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

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

   287 	  }

   288 	  break;

   289 	case REVERSE:

   290 	  g_queue_reverse (q);

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

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

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

   294 	  qinf->tail = q->tail;

   295 	  qinf->head = q->head;

   296 	  break;

   297 	case COPY:

   298 	  {

   299 	    QueueInfo *random_queue = RANDOM_QUEUE();

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

   301 	    

   302 	    g_queue_free (qinf->queue);

   303 	    q = qinf->queue = new_queue;

   304 	    qinf->head = new_queue->head;

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

   306 	    qinf->length = new_queue->length;

   307 	  }

   308 	  break;

   309 	case FOREACH:

   310 	  delete_all (q);

   311 	  qinf->head = NULL;

   312 	  qinf->tail = NULL;

   313 	  qinf->length = 0;

   314 	  break;

   315 	case FIND:

   316 	  {

   317 	    gboolean find_existing = rnd_bool ();

   318 	    int first = find_max (q);

   319 	    int second = find_min (q);

   320 

   321 	    if (q->length == 0)

   322 	      find_existing = FALSE;

   323 	    

   324 	    if (!find_existing)

   325 	      first++;

   326 	    if (!find_existing)

   327 	      second--;

   328 

   329 	    if (find_existing)

   330 	      {

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

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

   333 	      }

   334 	    else

   335 	      {

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

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

   338 	      }

   339 	  }

   340 	  break;

   341 	case FIND_CUSTOM:

   342 	  break;

   343 	case SORT:

   344 	  {

   345 	    if (!g_queue_is_empty (q))

   346 	      {

   347 		int max = find_max (q);

   348 		int min = find_min (q);

   349 		g_queue_remove_all (q, GINT_TO_POINTER (max));

   350 		check_integrity (q);

   351 		g_queue_remove_all (q, GINT_TO_POINTER (min));

   352 		check_integrity (q);

   353 		g_queue_push_head (q, GINT_TO_POINTER (max));

   354 		if (max != min)

   355 		  g_queue_push_head (q, GINT_TO_POINTER (min));

   356 		qinf->length = q->length;

   357 	      }

   358 

   359 	    check_integrity (q);

   360 	    

   361 	    g_queue_sort (q, compare_int, NULL);

   362 

   363 	    check_integrity (q);

   364 	    

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

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

   367 

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

   369 	  }

   370 	  break;

   371 	case PUSH_HEAD:

   372 	  {

   373 	    int x = g_random_int_range (0, 435435);

   374 	    g_queue_push_head (q, GINT_TO_POINTER (x));

   375 	    if (!qinf->head)

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

   377 	    else

   378 	      qinf->head = qinf->head->prev;

   379 	    qinf->length++;

   380 	  }

   381 	  break;

   382 	case PUSH_TAIL:

   383 	  {

   384 	    int x = g_random_int_range (0, 236546);

   385 	    g_queue_push_tail (q, GINT_TO_POINTER (x));

   386 	    if (!qinf->tail)

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

   388 	    else

   389 	      qinf->tail = qinf->tail->next;

   390 	    qinf->length++;

   391 	  }

   392 	  break;

   393 	case PUSH_NTH:

   394 	  {

   395 	    int pos = get_random_position (q, TRUE);

   396 	    int x = g_random_int_range (0, 236546);

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

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

   399 	      qinf->head = qinf->head->prev;

   400 	    else

   401 	      qinf->head = q->head;

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

   403 	      qinf->tail = qinf->tail->next;

   404 	    else

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

   406 	    qinf->length++;

   407 	  }

   408 	  break;

   409 	case POP_HEAD:

   410 	  if (qinf->head)

   411 	    qinf->head = qinf->head->next;

   412 	  if (!qinf->head)

   413 	    qinf->tail = NULL;

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

   415 	  g_queue_pop_head (q);

   416 	  break;

   417 	case POP_TAIL:

   418 	  if (qinf->tail)

   419 	    qinf->tail = qinf->tail->prev;

   420 	  if (!qinf->tail)

   421 	    qinf->head = NULL;

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

   423 	  g_queue_pop_tail (q);

   424 	  break;

   425 	case POP_NTH:

   426 	  if (!g_queue_is_empty (q))

   427 	    {

   428 	      int n = get_random_position (q, TRUE);

   429 	      gpointer elm = g_queue_peek_nth (q, n);

   430 

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

   432 		qinf->tail = qinf->tail->prev;

   433 	      

   434 	      if (n == 0)

   435 		qinf->head = qinf->head->next;

   436 

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

   438 		qinf->length--;

   439 	      

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

   441 	    }

   442 	  break;

   443 	case PEEK_HEAD:

   444 	  if (qinf->head)

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

   446 	  else

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

   448 	  break;

   449 	case PEEK_TAIL:

   450 	  if (qinf->head)

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

   452 	  else

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

   454 	  break;

   455 	case PEEK_NTH:

   456 	  if (g_queue_is_empty (q))

   457 	    {

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

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

   460 	    }

   461 	  else

   462 	    {

   463 	      GList *list;

   464 	      int n = get_random_position (q, TRUE);

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

   466 		{

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

   468 		}

   469 	      else

   470 		{

   471 		  list = qinf->head;

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

   473 		    list = list->next;

   474 		  

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

   476 		}

   477 	    }

   478 	  break;

   479 	case INDEX:

   480 	case LINK_INDEX:

   481 	  {

   482 	    int x = g_random_int_range (0, 386538);

   483 	    int n;

   484 	    GList *list;

   485 

   486 	    g_queue_remove_all (q, GINT_TO_POINTER (x));

   487  	    check_integrity (q);

   488 	    g_queue_push_tail (q, GINT_TO_POINTER (x));

   489  	    check_integrity (q);

   490 	    g_queue_sort (q, compare_int, NULL);

   491  	    check_integrity (q);

   492 

   493 	    n = 0;

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

   495 	      {

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

   497 		  break;

   498 		n++;

   499 	      }

   500 	    g_assert (list);

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

   502 		      g_queue_link_index (q, list));

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

   504 

   505 	    qinf->head = q->head;

   506 	    qinf->tail = q->tail;

   507 	    qinf->length = q->length;

   508 	  }

   509 	  break;

   510 	case REMOVE:

   511 	  if (!g_queue_is_empty (q))

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

   513 	  if (!g_queue_is_empty (q))

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

   515 	  if (!g_queue_is_empty (q))

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

   517 

   518 	  qinf->head = q->head;

   519 	  qinf->tail = q->tail;

   520 	  qinf->length = q->length;

   521 	  break;

   522 	case REMOVE_ALL:

   523 	  if (!g_queue_is_empty (q))

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

   525 	  if (!g_queue_is_empty (q))

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

   527 	  if (!g_queue_is_empty (q))

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

   529 

   530 	  qinf->head = q->head;

   531 	  qinf->tail = q->tail;

   532 	  qinf->length = q->length;

   533 	  break;

   534 	case INSERT_BEFORE:

   535 	  if (!g_queue_is_empty (q))

   536 	    {

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

   538 	      

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

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

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

   542 	    }

   543 	  qinf->head = q->head;

   544 	  qinf->tail = q->tail;

   545 	  qinf->length = q->length;

   546 	  break;

   547 	case INSERT_AFTER:

   548 	  if (!g_queue_is_empty (q))

   549 	    {

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

   551 	      

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

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

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

   555 	    }

   556 	  qinf->head = q->head;

   557 	  qinf->tail = q->tail;

   558 	  qinf->length = q->length;

   559 	  break;

   560 	case INSERT_SORTED:

   561 	  {

   562 	    int max = find_max (q);

   563 	    int min = find_min (q);

   564 

   565 	    if (g_queue_is_empty (q))

   566 	      {

   567 		max = 345;

   568 		min = -12;

   569 	      }

   570 	    

   571 	    g_queue_sort (q, compare_int, NULL);

   572  	    check_integrity (q);

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

   574  	    check_integrity (q);

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

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

   577  	    check_integrity (q);

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

   579 	    qinf->head = q->head;

   580 	    qinf->tail = q->tail;

   581 	    qinf->length = q->length;

   582 	  }

   583 	  break;

   584 	case PUSH_HEAD_LINK:

   585 	  {

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

   587 	    g_queue_push_head_link (q, link);

   588 	    if (!qinf->tail)

   589 	      qinf->tail = link;

   590 	    qinf->head = link;

   591 	    qinf->length++;

   592 	  }

   593 	  break;

   594 	case PUSH_TAIL_LINK:

   595 	  {

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

   597 	    g_queue_push_tail_link (q, link);

   598 	    if (!qinf->head)

   599 	      qinf->head = link;

   600 	    qinf->tail = link;

   601 	    qinf->length++;

   602 	  }

   603 	  break;

   604 	case PUSH_NTH_LINK:

   605 	  {

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

   607 	    gint n = get_random_position (q, TRUE);

   608 	    g_queue_push_nth_link (q, n, link);

   609 

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

   611 	      qinf->head = qinf->head->prev;

   612 	    else

   613 	      qinf->head = q->head;

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

   615 	      qinf->tail = qinf->tail->next;

   616 	    else

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

   618 	    qinf->length++;

   619 	  }

   620 	  break;

   621 	case POP_HEAD_LINK:

   622 	  if (!g_queue_is_empty (q))

   623 	    {

   624 	      qinf->head = qinf->head->next;

   625 	      if (!qinf->head)

   626 		qinf->tail = NULL;

   627 	      qinf->length--;

   628 	      g_list_free (g_queue_pop_head_link (q));

   629 	    }

   630 	  break;

   631 	case POP_TAIL_LINK:

   632 	  if (!g_queue_is_empty (q))

   633 	    {

   634 	      qinf->tail = qinf->tail->prev;

   635 	      if (!qinf->tail)

   636 		qinf->head = NULL;

   637 	      qinf->length--;

   638 	      g_list_free (g_queue_pop_tail_link (q));

   639 	    }

   640 	  break;

   641 	case POP_NTH_LINK:

   642 	  if (g_queue_is_empty (q))

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

   644 	  else

   645 	    {

   646 	      int n = get_random_position (q, FALSE);

   647 	      

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

   649 		qinf->tail = qinf->tail->prev;

   650 	      

   651 	      if (n == 0)

   652 		qinf->head = qinf->head->next;

   653 	      

   654 	      qinf->length--;

   655 	      

   656 	      g_list_free (g_queue_pop_nth_link (q, n));

   657 	    }

   658 	  break;

   659 	case PEEK_HEAD_LINK:

   660 	  if (g_queue_is_empty (q))

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

   662 	  else

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

   664 	  break;

   665 	case PEEK_TAIL_LINK:

   666 	  if (g_queue_is_empty (q))

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

   668 	  else

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

   670 	  break;

   671 	case PEEK_NTH_LINK:

   672 	  if (g_queue_is_empty(q))

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

   674 	  else

   675 	    {

   676 	      gint n = get_random_position (q, FALSE);

   677 	      GList *link;

   678 

   679 	      link = q->head;

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

   681 		link = link->next;

   682 

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

   684 	    }

   685 	  break;

   686 	case UNLINK:

   687 	  if (!g_queue_is_empty (q))

   688 	    {

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

   690 	      GList *link;

   691 

   692 	      link = q->head;

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

   694 		link = link->next;

   695 

   696 	      g_queue_unlink (q, link);

   697 	      check_integrity (q);

   698 

   699 	      g_list_free (link);

   700 

   701 	      qinf->head = q->head;

   702 	      qinf->tail = q->tail;

   703 	      qinf->length--;

   704 	    }

   705 	  break;

   706 	case DELETE_LINK:

   707 	  if (!g_queue_is_empty (q))

   708 	    {

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

   710 	      GList *link;

   711 

   712 	      link = q->head;

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

   714 		link = link->next;

   715 

   716 	      g_queue_delete_link (q, link);

   717 	      check_integrity (q);

   718 

   719 	      qinf->head = q->head;

   720 	      qinf->tail = q->tail;

   721 	      qinf->length--;

   722 	    }

   723 	  break;

   724 	case LAST_OP:

   725 	default:

   726 	  g_assert_not_reached();

   727 	  break;

   728 	}

   729 

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

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

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

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

   734 

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

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

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

   738       

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

   740 	check_integrity (queues[j].queue);

   741     }

   742   

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

   744     g_queue_free (queues[i].queue);

   745 }

   746 

   747 static void

   748 remove_item (gpointer data, gpointer q)

   749 {

   750   GQueue *queue = q;

   751   

   752   g_queue_remove (queue, data);

   753 }

   754 

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

   756 {

   757   GQueue *q, *q2;

   758   GList *node;

   759   gpointer data;

   760   int i;

   761   

   762   #ifdef __SYMBIAN32__

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

   764   g_set_print_handler(mrtPrintHandler);

   765   #endif /*__SYMBIAN32__*/

   766 	  

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

   768     verbose = TRUE;

   769 

   770   q = g_queue_new ();

   771   

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

   773   

   774   g_queue_push_head (q, GINT_TO_POINTER (2));

   775   check_integrity (q);

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

   777   check_integrity (q);

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

   779   check_integrity (q);

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

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

   782   g_queue_push_head (q, GINT_TO_POINTER (1));

   783   check_integrity (q);

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

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

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

   787   check_integrity (q);

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

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

   790   check_integrity (q);

   791   g_queue_push_tail (q, GINT_TO_POINTER (3));

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

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

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

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

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

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

   798   g_queue_push_tail (q, GINT_TO_POINTER (4));

   799   check_integrity (q);

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

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

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

   803   g_queue_push_tail (q, GINT_TO_POINTER (5));

   804   check_integrity (q);

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

   806   

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

   808   check_integrity (q);

   809   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   828   

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

   830   check_integrity (q);

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

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

   833   check_integrity (q);

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

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

   836   check_integrity (q);

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

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

   839   check_integrity (q);

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

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

   842   check_integrity (q);

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

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

   845   check_integrity (q);

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

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

   848   check_integrity (q);

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

   850   

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

   852   check_integrity (q);

   853   

   854   /************************/

   855   

   856   g_queue_push_head (q, GINT_TO_POINTER (1));

   857   check_integrity (q);

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

   859   g_queue_push_head (q, GINT_TO_POINTER (2));

   860   check_integrity (q);

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

   862   g_queue_push_head (q, GINT_TO_POINTER (3));

   863   check_integrity (q);

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

   865   g_queue_push_head (q, GINT_TO_POINTER (4));

   866   check_integrity (q);

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

   868   g_queue_push_head (q, GINT_TO_POINTER (5));

   869   check_integrity (q);

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

   871   

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

   873   check_integrity (q);

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

   875   node = q->tail;

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

   877   check_integrity (q);

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

   879   data = q->head->data;

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

   881   check_integrity (q);

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

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

   884   check_integrity (q);

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

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

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

   888   check_integrity (q);

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

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

   891   check_integrity (q);

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

   893   check_integrity (q);

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

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

   896   check_integrity (q);

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

   898   

   899   /* */

   900   g_queue_reverse (q);

   901   check_integrity (q);

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

   903   

   904   q2 = g_queue_copy (q);

   905   check_integrity (q);

   906   check_integrity (q2);

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

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

   909   g_queue_sort (q, compare_int, NULL);

   910   check_integrity (q2);

   911   check_integrity (q);

   912   g_queue_sort (q2, compare_int, NULL);

   913   check_integrity (q2);

   914   check_integrity (q);

   915   

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

   917     {

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

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

   920       check_integrity (q);

   921       check_integrity (q2);

   922     }

   923   

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

   925     {

   926       g_queue_remove (q, GINT_TO_POINTER (i));

   927       check_integrity (q);

   928       check_integrity (q2);

   929     }

   930   

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

   932     {

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

   934       

   935       g_queue_push_nth_link (q, i, l);

   936       check_integrity (q);

   937       check_integrity (q2);

   938       g_queue_reverse (q);

   939       check_integrity (q);

   940       check_integrity (q2);

   941     }

   942   

   943   g_queue_free (q2);

   944   q2 = g_queue_copy (q);

   945   

   946   g_queue_foreach (q2, remove_item, q2);

   947   check_integrity (q2);

   948   check_integrity (q);

   949 

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

   951   g_queue_push_tail (q, GINT_TO_POINTER (1234));

   952   check_integrity (q);

   953   node = g_queue_peek_tail_link (q);

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

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

   956   g_assert (node == NULL);

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

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

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

   960   g_assert (node == NULL);

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

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

   963   

   964   g_queue_free (q);

   965 

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

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

   968   if (argc > 1)

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

   970   else

   971     random_test (time (0));  

   972 #ifdef __SYMBIAN32__

   973   testResultXml("queue-test");

   974 #endif /* EMULATOR */

   975 

   976   return 0;

   977 }

   978