glib/tests/queue.c

   1 /*
   2  * Copyright 1999 Jeff Garzik
   3  * Copyright 1999 Tim Janik
   4  * Copyright 2004 Soeren Sandmann
   5  * Copyright 2006 Martyn James Russell
   6  * Copyright 2004, 2005, 2010, 2019 Red Hat, Inc.
   7  * Copyright 2011 Samsung
   8  * Copyright 2018 Tapasweni Pathak
   9  * Copyright 2019 Endless Mobile, Inc.
  10  * Copyright 2020 Emmanuel Fleury
  11  *
  12  * SPDX-License-Identifier: LGPL-2.1-or-later
  13  *
  14  * This program is free software; you can redistribute it and/or
  15  * modify it under the terms of the GNU Lesser General Public
  16  * License as published by the Free Software Foundation; either
  17  * version 2.1 of the License, or (at your option) any later version.
  18  *
  19  * See the included COPYING file for more information.
  20  */
  21
  22 #undef G_DISABLE_ASSERT
  23 #undef G_LOG_DOMAIN
  24
  25 #include <time.h>
  26 #include <stdlib.h>
  27
  28 #include <glib.h>
  29
  30
  31 static void
  32 check_integrity (GQueue *queue)
  33 {
  34   GList *list;
  35   GList *last;
  36   GList *links;
  37   GList *link;
  38   guint n;
  39
  40   g_assert_cmpuint (queue->length, <, 4000000000u);
  41
  42   g_assert_cmpuint (g_queue_get_length (queue), ==, queue->length);
  43
  44   if (!queue->head)
  45     g_assert_null (queue->tail);
  46   if (!queue->tail)
  47     g_assert_null (queue->head);
  48
  49   n = 0;
  50   last = NULL;
  51   for (list = queue->head; list != NULL; list = list->next)
  52     {
  53       if (!list->next)
  54         last = list;
  55       ++n;
  56     }
  57   g_assert_cmpuint (n, ==, queue->length);
  58   g_assert_true (last == queue->tail);
  59
  60   n = 0;
  61   last = NULL;
  62   for (list = queue->tail; list != NULL; list = list->prev)
  63     {
  64       if (!list->prev)
  65         last = list;
  66       ++n;
  67     }
  68   g_assert_cmpuint (n, ==, queue->length);
  69   g_assert_true (last == queue->head);
  70
  71   links = NULL;
  72   for (list = queue->head; list != NULL; list = list->next)
  73     links = g_list_prepend (links, list);
  74
  75   link = links;
  76   for (list = queue->tail; list != NULL; list = list->prev)
  77     {
  78       g_assert_true (list == link->data);
  79       link = link->next;
  80     }
  81   g_list_free (links);
  82
  83   links = NULL;
  84   for (list = queue->tail; list != NULL; list = list->prev)
  85     links = g_list_prepend (links, list);
  86
  87   link = links;
  88   for (list = queue->head; list != NULL; list = list->next)
  89     {
  90       g_assert_true (list == link->data);
  91       link = link->next;
  92     }
  93   g_list_free (links);
  94 }
  95
  96 static gboolean
  97 rnd_bool (void)
  98 {
  99   return g_random_int_range (0, 2);
 100 }
 101
 102 static void
 103 check_max (gpointer elm, gpointer user_data)
 104 {
 105   gint *best = user_data;
 106   gint element = GPOINTER_TO_INT (elm);
 107
 108   if (element > *best)
 109     *best = element;
 110 }
 111
 112 static void
 113 check_min (gpointer elm, gpointer user_data)
 114 {
 115   gint *best = user_data;
 116   gint element = GPOINTER_TO_INT (elm);
 117
 118   if (element < *best)
 119     *best = element;
 120 }
 121
 122 static gint
 123 find_min (GQueue *queue)
 124 {
 125   gint min = G_MAXINT;
 126
 127   g_queue_foreach (queue, check_min, &min);
 128
 129   return min;
 130 }
 131
 132 static gint
 133 find_max (GQueue *queue)
 134 {
 135   gint max = G_MININT;
 136
 137   g_queue_foreach (queue, check_max, &max);
 138
 139   return max;
 140 }
 141
 142 static void
 143 delete_elm (gpointer elm, gpointer user_data)
 144 {
 145   g_queue_remove ((GQueue *)user_data, elm);
 146   check_integrity ((GQueue *)user_data);
 147 }
 148
 149 static void
 150 delete_all (GQueue *queue)
 151 {
 152   g_queue_foreach (queue, delete_elm, queue);
 153 }
 154
 155 static int
 156 compare_int (gconstpointer a, gconstpointer b, gpointer data)
 157 {
 158   int ai = GPOINTER_TO_INT (a);
 159   int bi = GPOINTER_TO_INT (b);
 160
 161   if (ai > bi)
 162     return 1;
 163   else if (ai == bi)
 164     return 0;
 165   else
 166     return -1;
 167 }
 168
 169 static guint
 170 get_random_position (GQueue *queue, gboolean allow_offlist)
 171 {
 172   enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
 173
 174   if (allow_offlist)
 175     where = g_random_int_range (OFF_QUEUE, LAST);
 176   else
 177     where = g_random_int_range (HEAD, LAST);
 178
 179   switch (where)
 180     {
 181     case OFF_QUEUE:
 182       return g_random_int ();
 183
 184     case HEAD:
 185       return 0;
 186
 187     case TAIL:
 188       if (allow_offlist)
 189         return queue->length;
 190       else if (queue->length > 0)
 191         return queue->length - 1;
 192       else
 193         return 0;
 194
 195     case MIDDLE:
 196       if (queue->length == 0)
 197         return 0;
 198       else
 199         return g_random_int_range (0, queue->length);
 200
 201     default:
 202       g_assert_not_reached ();
 203     }
 204 }
 205
 206 static void
 207 random_test (gconstpointer d)
 208 {
 209   guint32 seed = GPOINTER_TO_UINT (d);
 210
 211   typedef enum {
 212     IS_EMPTY, GET_LENGTH, REVERSE, COPY,
 213     FOREACH, FIND, FIND_CUSTOM, SORT,
 214     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
 215     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
 216     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
 217     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
 218     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
 219     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
 220     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
 221   } QueueOp;
 222
 223   const guint n_iterations = g_test_thorough () ? 500000 : 100000;
 224
 225 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, G_N_ELEMENTS (queues))])
 226
 227   typedef struct QueueInfo QueueInfo;
 228   struct QueueInfo
 229   {
 230     GQueue *queue;
 231     GList *tail;
 232     GList *head;
 233     guint length;
 234   };
 235
 236   guint i;
 237   QueueOp op;
 238   QueueInfo queues[3];
 239
 240   g_random_set_seed (seed);
 241
 242   for (i = 0; i < G_N_ELEMENTS (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       guint 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_true (qinf->head == q->head);
 258       g_assert_true (qinf->tail == q->tail);
 259       g_assert_cmpuint (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_null (q->head);
 268                 g_assert_null (q->tail);
 269                 g_assert_cmpuint (q->length, ==, 0);
 270               }
 271             else
 272               {
 273                 g_assert_nonnull (q->head);
 274                 g_assert_nonnull (q->tail);
 275                 g_assert_cmpuint (q->length, >, 0);
 276               }
 277           }
 278           break;
 279         case GET_LENGTH:
 280           {
 281             guint l;
 282
 283             l = g_queue_get_length (q);
 284
 285             g_assert_cmpuint (qinf->length, ==, q->length);
 286             g_assert_cmpuint (qinf->length, ==, l);
 287           }
 288           break;
 289         case REVERSE:
 290           g_queue_reverse (q);
 291           g_assert_true (qinf->tail == q->head);
 292           g_assert_true (qinf->head == q->tail);
 293           g_assert_cmpuint (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_nonnull (g_queue_find (q, GINT_TO_POINTER (first)));
 332                 g_assert_nonnull (g_queue_find (q, GINT_TO_POINTER (second)));
 333               }
 334             else
 335               {
 336                 g_assert_null (g_queue_find (q, GINT_TO_POINTER (first)));
 337                 g_assert_null (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_true (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             guint 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               guint 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 < q->length)
 438                 qinf->length--;
 439
 440               g_assert_true (elm == g_queue_pop_nth (q, n));
 441             }
 442           break;
 443         case PEEK_HEAD:
 444           if (qinf->head)
 445             g_assert_true (qinf->head->data == g_queue_peek_head (q));
 446           else
 447             g_assert_null (g_queue_peek_head (q));
 448           break;
 449         case PEEK_TAIL:
 450           if (qinf->tail)
 451             g_assert_true (qinf->tail->data == g_queue_peek_tail (q));
 452           else
 453             g_assert_null (g_queue_peek_tail (q));
 454           break;
 455         case PEEK_NTH:
 456           if (g_queue_is_empty (q))
 457             {
 458               int k;
 459               for (k = -10; k < 10; ++k)
 460                 g_assert_null (g_queue_peek_nth (q, (guint) k));
 461             }
 462           else
 463             {
 464               GList *list;
 465               guint n = get_random_position (q, TRUE);
 466               if (n >= q->length)
 467                 {
 468                   g_assert_null (g_queue_peek_nth (q, n));
 469                 }
 470               else
 471                 {
 472                   list = qinf->head;
 473                   for (j = 0; j < n; ++j)
 474                     list = list->next;
 475
 476                   g_assert_true (list->data == g_queue_peek_nth (q, n));
 477                 }
 478             }
 479           break;
 480         case INDEX:
 481         case LINK_INDEX:
 482           {
 483             int x = g_random_int_range (0, 386538);
 484             int n;
 485             GList *list;
 486
 487             g_queue_remove_all (q, GINT_TO_POINTER (x));
 488             check_integrity (q);
 489             g_queue_push_tail (q, GINT_TO_POINTER (x));
 490             check_integrity (q);
 491             g_queue_sort (q, compare_int, NULL);
 492             check_integrity (q);
 493
 494             n = 0;
 495             for (list = q->head; list != NULL; list = list->next)
 496               {
 497                 if (list->data == GINT_TO_POINTER (x))
 498                   break;
 499                 n++;
 500               }
 501             g_assert_nonnull (list);
 502             g_assert_cmpint (g_queue_index (q, GINT_TO_POINTER (x)), ==,
 503                              g_queue_link_index (q, list));
 504             g_assert_cmpint (g_queue_link_index (q, list), ==, n);
 505
 506             qinf->head = q->head;
 507             qinf->tail = q->tail;
 508             qinf->length = q->length;
 509           }
 510           break;
 511         case REMOVE:
 512           if (!g_queue_is_empty (q))
 513             g_queue_remove (q, qinf->tail->data);
 514           /* qinf->head/qinf->tail may be invalid at this point */
 515           if (!g_queue_is_empty (q))
 516             g_queue_remove (q, q->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           /* qinf->head/qinf->tail may be invalid at this point */
 528           if (!g_queue_is_empty (q))
 529             g_queue_remove_all (q, q->head->data);
 530           if (!g_queue_is_empty (q))
 531             g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
 532
 533           qinf->head = q->head;
 534           qinf->tail = q->tail;
 535           qinf->length = q->length;
 536           break;
 537         case INSERT_BEFORE:
 538           if (!g_queue_is_empty (q))
 539             {
 540               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 541
 542               g_queue_insert_before (q, qinf->tail, x);
 543               g_queue_insert_before (q, qinf->head, x);
 544               g_queue_insert_before (q, g_queue_find (q, x), x);
 545               g_queue_insert_before (q, NULL, x);
 546             }
 547           qinf->head = q->head;
 548           qinf->tail = q->tail;
 549           qinf->length = q->length;
 550           break;
 551         case INSERT_AFTER:
 552           if (!g_queue_is_empty (q))
 553             {
 554               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 555
 556               g_queue_insert_after (q, qinf->tail, x);
 557               g_queue_insert_after (q, qinf->head, x);
 558               g_queue_insert_after (q, g_queue_find (q, x), x);
 559               g_queue_insert_after (q, NULL, x);
 560             }
 561           qinf->head = q->head;
 562           qinf->tail = q->tail;
 563           qinf->length = q->length;
 564           break;
 565         case INSERT_SORTED:
 566           {
 567             int max = find_max (q);
 568             int min = find_min (q);
 569
 570             if (g_queue_is_empty (q))
 571               {
 572                 max = 345;
 573                 min = -12;
 574               }
 575
 576             g_queue_sort (q, compare_int, NULL);
 577             check_integrity (q);
 578             g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
 579             check_integrity (q);
 580             g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, max + 1);
 581             g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
 582             check_integrity (q);
 583             g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, min - 1);
 584             qinf->head = q->head;
 585             qinf->tail = q->tail;
 586             qinf->length = q->length;
 587           }
 588           break;
 589         case PUSH_HEAD_LINK:
 590           {
 591             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 592             g_queue_push_head_link (q, link);
 593             if (!qinf->tail)
 594               qinf->tail = link;
 595             qinf->head = link;
 596             qinf->length++;
 597           }
 598           break;
 599         case PUSH_TAIL_LINK:
 600           {
 601             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 602             g_queue_push_tail_link (q, link);
 603             if (!qinf->head)
 604               qinf->head = link;
 605             qinf->tail = link;
 606             qinf->length++;
 607           }
 608           break;
 609         case PUSH_NTH_LINK:
 610           {
 611             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 612             guint n = get_random_position (q, TRUE);
 613             g_queue_push_nth_link (q, n, link);
 614
 615             if (qinf->head && qinf->head->prev)
 616               qinf->head = qinf->head->prev;
 617             else
 618               qinf->head = q->head;
 619             if (qinf->tail && qinf->tail->next)
 620               qinf->tail = qinf->tail->next;
 621             else
 622               qinf->tail = g_list_last (qinf->head);
 623             qinf->length++;
 624           }
 625           break;
 626         case POP_HEAD_LINK:
 627           if (!g_queue_is_empty (q))
 628             {
 629               qinf->head = qinf->head->next;
 630               if (!qinf->head)
 631                 qinf->tail = NULL;
 632               qinf->length--;
 633               g_list_free (g_queue_pop_head_link (q));
 634             }
 635           break;
 636         case POP_TAIL_LINK:
 637           if (!g_queue_is_empty (q))
 638             {
 639               qinf->tail = qinf->tail->prev;
 640               if (!qinf->tail)
 641                 qinf->head = NULL;
 642               qinf->length--;
 643               g_list_free (g_queue_pop_tail_link (q));
 644             }
 645           break;
 646         case POP_NTH_LINK:
 647           if (g_queue_is_empty (q))
 648             g_assert_null (g_queue_pop_nth_link (q, 200));
 649           else
 650             {
 651               guint n = get_random_position (q, FALSE);
 652
 653               if (n == g_queue_get_length (q) - 1)
 654                 qinf->tail = qinf->tail->prev;
 655
 656               if (n == 0)
 657                 qinf->head = qinf->head->next;
 658
 659               qinf->length--;
 660
 661               g_list_free (g_queue_pop_nth_link (q, n));
 662             }
 663           break;
 664         case PEEK_HEAD_LINK:
 665           if (g_queue_is_empty (q))
 666             g_assert_null (g_queue_peek_head_link (q));
 667           else
 668             g_assert_true (g_queue_peek_head_link (q) == qinf->head);
 669           break;
 670         case PEEK_TAIL_LINK:
 671           if (g_queue_is_empty (q))
 672             g_assert_null (g_queue_peek_tail_link (q));
 673           else
 674             g_assert_true (g_queue_peek_tail_link (q) == qinf->tail);
 675           break;
 676         case PEEK_NTH_LINK:
 677           if (g_queue_is_empty(q))
 678             g_assert_null (g_queue_peek_nth_link (q, 1000));
 679           else
 680             {
 681               guint n = get_random_position (q, FALSE);
 682               GList *link;
 683
 684               link = q->head;
 685               for (j = 0; j < n; ++j)
 686                 link = link->next;
 687
 688               g_assert_true (g_queue_peek_nth_link (q, n) == link);
 689             }
 690           break;
 691         case UNLINK:
 692           if (!g_queue_is_empty (q))
 693             {
 694               guint n = g_random_int_range (0, g_queue_get_length (q));
 695               GList *link;
 696
 697               link = q->head;
 698               for (j = 0; j < n; ++j)
 699                 link = link->next;
 700
 701               g_queue_unlink (q, link);
 702               check_integrity (q);
 703
 704               g_list_free (link);
 705
 706               qinf->head = q->head;
 707               qinf->tail = q->tail;
 708               qinf->length--;
 709             }
 710           break;
 711         case DELETE_LINK:
 712           if (!g_queue_is_empty (q))
 713             {
 714               guint n = g_random_int_range (0, g_queue_get_length (q));
 715               GList *link;
 716
 717               link = q->head;
 718               for (j = 0; j < n; ++j)
 719                 link = link->next;
 720
 721               g_queue_delete_link (q, link);
 722               check_integrity (q);
 723
 724               qinf->head = q->head;
 725               qinf->tail = q->tail;
 726               qinf->length--;
 727             }
 728           break;
 729         case LAST_OP:
 730         default:
 731           g_assert_not_reached();
 732           break;
 733         }
 734
 735       if (qinf->head != q->head ||
 736           qinf->tail != q->tail ||
 737           qinf->length != q->length)
 738         g_printerr ("op: %d\n", op);
 739
 740       g_assert_true (qinf->head == q->head);
 741       g_assert_true (qinf->tail == q->tail);
 742       g_assert_cmpuint (qinf->length, ==, q->length);
 743
 744       for (j = 0; j < G_N_ELEMENTS (queues); ++j)
 745         check_integrity (queues[j].queue);
 746     }
 747
 748   for (i = 0; i < G_N_ELEMENTS (queues); ++i)
 749     g_queue_free (queues[i].queue);
 750 }
 751
 752 static void
 753 remove_item (gpointer data, gpointer q)
 754 {
 755   GQueue *queue = q;
 756
 757   g_queue_remove (queue, data);
 758 }
 759
 760 static void
 761 test_basic (void)
 762 {
 763   GQueue *q;
 764   GList *node;
 765   gpointer data;
 766
 767   q = g_queue_new ();
 768
 769   g_assert_true (g_queue_is_empty (q));
 770   g_queue_push_head (q, GINT_TO_POINTER (2));
 771   check_integrity (q);
 772   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_head (q)), ==, 2);
 773   check_integrity (q);
 774   g_assert_false (g_queue_is_empty (q));
 775   check_integrity (q);
 776   g_assert_cmpint (g_list_length (q->head), ==, 1);
 777   g_assert_true (q->head == q->tail);
 778   g_queue_push_head (q, GINT_TO_POINTER (1));
 779   check_integrity (q);
 780   g_assert_true (q->head->next == q->tail);
 781   g_assert_true (q->tail->prev == q->head);
 782   g_assert_cmpint (g_list_length (q->head), ==, 2);
 783   check_integrity (q);
 784   g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, 2);
 785   g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
 786   check_integrity (q);
 787   g_queue_push_tail (q, GINT_TO_POINTER (3));
 788   g_assert_cmpint (g_list_length (q->head), ==, 3);
 789   g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
 790   g_assert_cmpint (GPOINTER_TO_INT (q->head->next->data), ==, 2);
 791   g_assert_true (q->head->next->next == q->tail);
 792   g_assert_true (q->head->next == q->tail->prev);
 793   g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, 3);
 794   g_queue_push_tail (q, GINT_TO_POINTER (4));
 795   check_integrity (q);
 796   g_assert_cmpint (g_list_length (q->head), ==, 4);
 797   g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
 798   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_tail (q)), ==, 4);
 799   g_queue_push_tail (q, GINT_TO_POINTER (5));
 800   check_integrity (q);
 801   g_assert_cmpint (g_list_length (q->head), ==, 5);
 802   g_assert_false (g_queue_is_empty (q));
 803   check_integrity (q);
 804   g_assert_cmpint (q->length, ==, 5);
 805   g_assert_null (q->head->prev);
 806   g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
 807   g_assert_cmpint (GPOINTER_TO_INT (q->head->next->data), ==, 2);
 808   g_assert_cmpint (GPOINTER_TO_INT (q->head->next->next->data), ==, 3);
 809   g_assert_cmpint (GPOINTER_TO_INT (q->head->next->next->next->data), ==, 4);
 810   g_assert_cmpint (GPOINTER_TO_INT (q->head->next->next->next->next->data), ==, 5);
 811   g_assert_null (q->head->next->next->next->next->next);
 812   g_assert_true (q->head->next->next->next->next == q->tail);
 813   g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, 5);
 814   g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->data), ==, 4);
 815   g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->prev->data), ==, 3);
 816   g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->prev->prev->data), ==, 2);
 817   g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->prev->prev->prev->data), ==, 1);
 818   g_assert_null (q->tail->prev->prev->prev->prev->prev);
 819   g_assert_true (q->tail->prev->prev->prev->prev == q->head);
 820   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_tail (q)), ==, 5);
 821   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_head (q)), ==, 1);
 822   g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_head (q)), ==, 1);
 823   check_integrity (q);
 824   g_assert_cmpint (g_list_length (q->head), ==, 4);
 825   g_assert_cmpint (q->length, ==, 4);
 826   g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 5);
 827   check_integrity (q);
 828   g_assert_cmpint (g_list_length (q->head), ==, 3);
 829
 830   node = g_queue_pop_head_link (q);
 831   g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 2);
 832   g_list_free_1 (node);
 833
 834   check_integrity (q);
 835   g_assert_cmpint (g_list_length (q->head), ==, 2);
 836   g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 4);
 837   check_integrity (q);
 838   g_assert_cmpint (g_list_length (q->head), ==, 1);
 839   node = g_queue_pop_head_link (q);
 840   g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 3);
 841   g_list_free_1 (node);
 842   check_integrity (q);
 843   g_assert_cmpint (g_list_length (q->head), ==, 0);
 844   g_assert_null (g_queue_pop_tail (q));
 845   check_integrity (q);
 846   g_assert_cmpint (g_list_length (q->head), ==, 0);
 847   g_assert_null (g_queue_pop_head (q));
 848   check_integrity (q);
 849   g_assert_cmpint (g_list_length (q->head), ==, 0);
 850   g_assert_true (g_queue_is_empty (q));
 851   check_integrity (q);
 852
 853   g_queue_push_head (q, GINT_TO_POINTER (1));
 854   check_integrity (q);
 855   g_assert_cmpint (g_list_length (q->head), ==, 1);
 856   g_assert_cmpint (q->length, ==, 1);
 857   g_queue_push_head (q, GINT_TO_POINTER (2));
 858   check_integrity (q);
 859   g_assert_cmpint (g_list_length (q->head), ==, 2);
 860   g_assert_cmpint (q->length, ==, 2);
 861   g_queue_push_head (q, GINT_TO_POINTER (3));
 862   check_integrity (q);
 863   g_assert_cmpint (g_list_length (q->head), ==, 3);
 864   g_assert_cmpint (q->length, ==, 3);
 865   g_queue_push_head (q, GINT_TO_POINTER (4));
 866   check_integrity (q);
 867   g_assert_cmpint (g_list_length (q->head), ==, 4);
 868   g_assert_cmpint (q->length, ==, 4);
 869   g_queue_push_head (q, GINT_TO_POINTER (5));
 870   check_integrity (q);
 871   g_assert_cmpint (g_list_length (q->head), ==, 5);
 872   g_assert_cmpint (q->length, ==, 5);
 873   g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_head (q)), ==, 5);
 874   check_integrity (q);
 875   g_assert_cmpint (g_list_length (q->head), ==, 4);
 876   node = q->tail;
 877   g_assert_true (node == g_queue_pop_tail_link (q));
 878   check_integrity (q);
 879   g_list_free_1 (node);
 880   g_assert_cmpint (g_list_length (q->head), ==, 3);
 881   data = q->head->data;
 882   g_assert_true (data == g_queue_pop_head (q));
 883   check_integrity (q);
 884   g_assert_cmpint (g_list_length (q->head), ==, 2);
 885   g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 2);
 886   check_integrity (q);
 887   g_assert_cmpint (g_list_length (q->head), ==, 1);
 888   g_assert_true (q->head == q->tail);
 889   g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 3);
 890   check_integrity (q);
 891   g_assert_cmpint (g_list_length (q->head), ==, 0);
 892   g_assert_null (g_queue_pop_head (q));
 893   check_integrity (q);
 894   g_assert_null (g_queue_pop_head_link (q));
 895   check_integrity (q);
 896   g_assert_cmpint (g_list_length (q->head), ==, 0);
 897   g_assert_null (g_queue_pop_tail_link (q));
 898   check_integrity (q);
 899   g_assert_cmpint (g_list_length (q->head), ==, 0);
 900
 901   g_queue_reverse (q);
 902   check_integrity (q);
 903   g_assert_cmpint (g_list_length (q->head), ==, 0);
 904   g_queue_free (q);
 905 }
 906
 907 static void
 908 test_copy (void)
 909 {
 910   GQueue *q, *q2;
 911   gint i;
 912
 913   q = g_queue_new ();
 914   q2 = g_queue_copy (q);
 915   check_integrity (q);
 916   check_integrity (q2);
 917   g_assert_cmpint (g_list_length (q->head), ==, 0);
 918   g_assert_cmpint (g_list_length (q2->head), ==, 0);
 919   g_queue_sort (q, compare_int, NULL);
 920   check_integrity (q2);
 921   check_integrity (q);
 922   g_queue_sort (q2, compare_int, NULL);
 923   check_integrity (q2);
 924   check_integrity (q);
 925
 926   for (i = 0; i < 200; ++i)
 927     {
 928       g_queue_push_nth (q, GINT_TO_POINTER (i), i);
 929       g_assert_nonnull (g_queue_find (q, GINT_TO_POINTER (i)));
 930       check_integrity (q);
 931       check_integrity (q2);
 932     }
 933
 934   for (i = 0; i < 200; ++i)
 935     {
 936       g_queue_remove (q, GINT_TO_POINTER (i));
 937       check_integrity (q);
 938       check_integrity (q2);
 939     }
 940
 941   for (i = 0; i < 200; ++i)
 942     {
 943       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
 944
 945       g_queue_push_nth_link (q, i, l);
 946       check_integrity (q);
 947       check_integrity (q2);
 948       g_queue_reverse (q);
 949       check_integrity (q);
 950       check_integrity (q2);
 951     }
 952
 953   g_queue_free (q2);
 954   q2 = g_queue_copy (q);
 955
 956   g_queue_foreach (q2, remove_item, q2);
 957   check_integrity (q2);
 958   check_integrity (q);
 959
 960   g_queue_free (q);
 961   g_queue_free (q2);
 962 }
 963
 964 static void
 965 test_off_by_one (void)
 966 {
 967   GQueue *q;
 968   GList *node;
 969
 970   q = g_queue_new ();
 971
 972   g_queue_push_tail (q, GINT_TO_POINTER (1234));
 973   check_integrity (q);
 974   node = g_queue_peek_tail_link (q);
 975   g_assert_nonnull (node);
 976   g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 1234);
 977
 978   node = g_queue_peek_nth_link (q, g_queue_get_length (q));
 979   g_assert_null (node);
 980
 981   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
 982   g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 1234);
 983
 984   node = g_queue_pop_nth_link (q, g_queue_get_length (q));
 985   g_assert_null (node);
 986
 987   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
 988   g_assert_nonnull (node);
 989   g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 1234);
 990
 991   g_list_free_1 (node);
 992
 993   g_queue_free (q);
 994 }
 995
 996 static gint
 997 find_custom (gconstpointer a, gconstpointer b)
 998 {
 999   return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
1000 }
1001
1002 static void
1003 test_find_custom (void)
1004 {
1005   GQueue *q;
1006   GList *node;
1007   q = g_queue_new ();
1008
1009   g_queue_push_tail (q, GINT_TO_POINTER (1234));
1010   g_queue_push_tail (q, GINT_TO_POINTER (1));
1011   g_queue_push_tail (q, GINT_TO_POINTER (2));
1012   node = g_queue_find_custom  (q, GINT_TO_POINTER (1), find_custom);
1013   g_assert_nonnull (node);
1014   node = g_queue_find_custom  (q, GINT_TO_POINTER (2), find_custom);
1015   g_assert_nonnull (node);
1016   node = g_queue_find_custom  (q, GINT_TO_POINTER (3), find_custom);
1017   g_assert_null (node);
1018
1019   g_queue_free (q);
1020 }
1021
1022 static void
1023 test_static (void)
1024 {
1025   GQueue q;
1026   GQueue q2 = G_QUEUE_INIT;
1027
1028   g_queue_init (&q);
1029
1030   check_integrity (&q);
1031   g_assert_true (g_queue_is_empty (&q));
1032
1033   check_integrity (&q2);
1034   g_assert_true (g_queue_is_empty (&q2));
1035 }
1036
1037 static void
1038 test_clear (void)
1039 {
1040   GQueue *q;
1041   q = g_queue_new ();
1042
1043   g_queue_push_tail (q, GINT_TO_POINTER (1234));
1044   g_queue_push_tail (q, GINT_TO_POINTER (1));
1045   g_queue_push_tail (q, GINT_TO_POINTER (2));
1046   g_assert_cmpint (g_queue_get_length (q), ==, 3);
1047
1048   g_queue_clear (q);
1049   check_integrity (q);
1050   g_assert_true (g_queue_is_empty (q));
1051
1052   g_queue_free (q);
1053 }
1054
1055 typedef struct
1056 {
1057   gboolean freed;
1058   int x;
1059 } QueueItem;
1060
1061 static void
1062 free_func (gpointer data)
1063 {
1064   QueueItem *item = data;
1065
1066   item->freed = TRUE;
1067 }
1068
1069 static QueueItem *
1070 new_item (int x)
1071 {
1072   QueueItem *item;
1073
1074   item = g_slice_new (QueueItem);
1075   item->freed = FALSE;
1076   item->x = x;
1077
1078   return item;
1079 }
1080
1081 static void
1082 test_clear_full (void)
1083 {
1084   QueueItem *one, *two, *three, *four;
1085   GQueue *queue;
1086
1087   queue = g_queue_new ();
1088   g_queue_push_tail (queue, one = new_item (1));
1089   g_queue_push_tail (queue, two = new_item (2));
1090   g_queue_push_tail (queue, three = new_item (3));
1091   g_queue_push_tail (queue, four = new_item (4));
1092
1093   g_assert_cmpint (g_queue_get_length (queue), ==, 4);
1094   g_assert_false (one->freed);
1095   g_assert_false (two->freed);
1096   g_assert_false (three->freed);
1097   g_assert_false (four->freed);
1098
1099   g_queue_clear_full (queue, free_func);
1100
1101   g_assert_true (one->freed);
1102   g_assert_true (two->freed);
1103   g_assert_true (three->freed);
1104   g_assert_true (four->freed);
1105
1106   g_assert_true (g_queue_is_empty (queue));
1107   check_integrity (queue);
1108
1109   g_slice_free (QueueItem, one);
1110   g_slice_free (QueueItem, two);
1111   g_slice_free (QueueItem, three);
1112   g_slice_free (QueueItem, four);
1113   g_queue_free (queue);
1114 }
1115
1116 /* Check that g_queue_clear_full() called with a NULL free_func is equivalent
1117  * to g_queue_clear(). */
1118 static void
1119 test_clear_full_noop (void)
1120 {
1121   QueueItem *one, *two, *three, *four;
1122   GQueue *queue;
1123
1124   queue = g_queue_new ();
1125   g_queue_push_tail (queue, one = new_item (1));
1126   g_queue_push_tail (queue, two = new_item (2));
1127   g_queue_push_tail (queue, three = new_item (3));
1128   g_queue_push_tail (queue, four = new_item (4));
1129
1130   g_assert_cmpint (g_queue_get_length (queue), ==, 4);
1131   g_assert_false (one->freed);
1132   g_assert_false (two->freed);
1133   g_assert_false (three->freed);
1134   g_assert_false (four->freed);
1135
1136   g_queue_clear_full (queue, NULL);
1137
1138   g_assert_true (g_queue_is_empty (queue));
1139   check_integrity (queue);
1140
1141   g_slice_free (QueueItem, one);
1142   g_slice_free (QueueItem, two);
1143   g_slice_free (QueueItem, three);
1144   g_slice_free (QueueItem, four);
1145   g_queue_free (queue);
1146 }
1147
1148 /* Test g_queue_push_nth_link() with various combinations of position (before,
1149  * in the middle of, or at the end of the queue) and various existing queues
1150  * (empty, single element, multiple elements). */
1151 static void
1152 test_push_nth_link (void)
1153 {
1154   GQueue *q;
1155   q = g_queue_new ();
1156
1157   /* Push onto before the front of an empty queue (which results in it being
1158    * added to the end of the queue). */
1159   g_queue_push_nth_link (q, -1, g_list_prepend (NULL, GINT_TO_POINTER (1)));
1160   check_integrity (q);
1161   g_assert_cmpint (g_queue_get_length (q), ==, 1);
1162   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 1);
1163
1164   g_queue_clear (q);
1165
1166   /* Push onto after the rear of an empty queue. */
1167   g_queue_push_nth_link (q, 100, g_list_prepend (NULL, GINT_TO_POINTER (2)));
1168   check_integrity (q);
1169   g_assert_cmpint (g_queue_get_length (q), ==, 1);
1170   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 2);
1171
1172   g_queue_clear (q);
1173
1174   /* Push onto the front of an empty queue. */
1175   g_queue_push_nth_link (q, 0, g_list_prepend (NULL, GINT_TO_POINTER (3)));
1176   check_integrity (q);
1177   g_assert_cmpint (g_queue_get_length (q), ==, 1);
1178   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 3);
1179
1180   g_queue_clear (q);
1181
1182   /* Push onto before the front of a non-empty queue (which results in it being
1183    * added to the end of the queue). */
1184   g_queue_push_head (q, GINT_TO_POINTER (4));
1185   g_queue_push_nth_link (q, -1, g_list_prepend (NULL, GINT_TO_POINTER (5)));
1186   check_integrity (q);
1187   g_assert_cmpint (g_queue_get_length (q), ==, 2);
1188   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 4);
1189   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 5);
1190
1191   g_queue_clear (q);
1192
1193   /* Push onto after the rear of a non-empty queue. */
1194   g_queue_push_head (q, GINT_TO_POINTER (6));
1195   g_queue_push_nth_link (q, 100, g_list_prepend (NULL, GINT_TO_POINTER (7)));
1196   check_integrity (q);
1197   g_assert_cmpint (g_queue_get_length (q), ==, 2);
1198   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 6);
1199   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 7);
1200
1201   g_queue_clear (q);
1202
1203   /* Push onto the rear of a non-empty queue. */
1204   g_queue_push_head (q, GINT_TO_POINTER (8));
1205   g_queue_push_nth_link (q, 1, g_list_prepend (NULL, GINT_TO_POINTER (9)));
1206   check_integrity (q);
1207   g_assert_cmpint (g_queue_get_length (q), ==, 2);
1208   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 8);
1209   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 9);
1210
1211   g_queue_clear (q);
1212
1213   /* Push onto the front of a non-empty queue. */
1214   g_queue_push_head (q, GINT_TO_POINTER (10));
1215   g_queue_push_nth_link (q, 0, g_list_prepend (NULL, GINT_TO_POINTER (11)));
1216   check_integrity (q);
1217   g_assert_cmpint (g_queue_get_length (q), ==, 2);
1218   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 11);
1219   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 10);
1220
1221   g_queue_clear (q);
1222
1223   /* Push into the middle of a non-empty queue. */
1224   g_queue_push_head (q, GINT_TO_POINTER (12));
1225   g_queue_push_head (q, GINT_TO_POINTER (13));
1226   g_queue_push_nth_link (q, 1, g_list_prepend (NULL, GINT_TO_POINTER (14)));
1227   check_integrity (q);
1228   g_assert_cmpint (g_queue_get_length (q), ==, 3);
1229   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 13);
1230   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 14);
1231   g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 2)), ==, 12);
1232
1233   g_queue_free (q);
1234 }
1235
1236 static void
1237 test_free_full (void)
1238 {
1239   QueueItem *one, *two, *three;
1240   GQueue *queue = NULL;
1241
1242   queue = g_queue_new();
1243   g_queue_push_tail (queue, one = new_item (1));
1244   g_queue_push_tail (queue, two = new_item (2));
1245   g_queue_push_tail (queue, three = new_item (3));
1246   g_assert_false (one->freed);
1247   g_assert_false (two->freed);
1248   g_assert_false (three->freed);
1249   g_queue_free_full (queue, free_func);
1250   g_assert_true (one->freed);
1251   g_assert_true (two->freed);
1252   g_assert_true (three->freed);
1253   g_slice_free (QueueItem, one);
1254   g_slice_free (QueueItem, two);
1255   g_slice_free (QueueItem, three);
1256 }
1257
1258 static void
1259 test_insert_sibling_link (void)
1260 {
1261   GQueue q = G_QUEUE_INIT;
1262   GList a = {0};
1263   GList b = {0};
1264   GList c = {0};
1265   GList d = {0};
1266   GList e = {0};
1267
1268   g_queue_push_head_link (&q, &a);
1269   g_queue_insert_after_link (&q, &a, &d);
1270   g_queue_insert_before_link (&q, &d, &b);
1271   g_queue_insert_after_link (&q, &b, &c);
1272   g_queue_insert_after_link (&q, NULL, &e);
1273
1274   g_assert_true (q.head == &e);
1275   g_assert_true (q.tail == &d);
1276
1277   g_assert_null (e.prev);
1278   g_assert_true (e.next == &a);
1279
1280   g_assert_true (a.prev == &e);
1281   g_assert_true (a.next == &b);
1282
1283   g_assert_true (b.prev == &a);
1284   g_assert_true (b.next == &c);
1285
1286   g_assert_true (c.prev == &b);
1287   g_assert_true (c.next == &d);
1288
1289   g_assert_true (d.prev == &c);
1290   g_assert_null (d.next);
1291 }
1292
1293 int main (int argc, char *argv[])
1294 {
1295   guint32 seed;
1296   gchar *path;
1297
1298   g_test_init (&argc, &argv, NULL);
1299
1300   g_test_add_func ("/queue/basic", test_basic);
1301   g_test_add_func ("/queue/copy", test_copy);
1302   g_test_add_func ("/queue/off-by-one", test_off_by_one);
1303   g_test_add_func ("/queue/find-custom", test_find_custom);
1304   g_test_add_func ("/queue/static", test_static);
1305   g_test_add_func ("/queue/clear", test_clear);
1306   g_test_add_func ("/queue/free-full", test_free_full);
1307   g_test_add_func ("/queue/clear-full", test_clear_full);
1308   g_test_add_func ("/queue/clear-full/noop", test_clear_full_noop);
1309   g_test_add_func ("/queue/insert-sibling-link", test_insert_sibling_link);
1310   g_test_add_func ("/queue/push-nth-link", test_push_nth_link);
1311
1312   seed = g_test_rand_int_range (0, G_MAXINT);
1313   path = g_strdup_printf ("/queue/random/seed:%u", seed);
1314   g_test_add_data_func (path, GUINT_TO_POINTER (seed), random_test);
1315   g_free (path);
1316
1317   return g_test_run ();
1318 }