glib/tests/queue.c

   1 #undef G_DISABLE_ASSERT
   2 #undef G_LOG_DOMAIN
   3
   4 #include <time.h>
   5 #include <stdlib.h>
   6
   7 #include <glib.h>
   8
   9
  10 static void
  11 check_integrity (GQueue *queue)
  12 {
  13   GList *list;
  14   GList *last;
  15   GList *links;
  16   GList *link;
  17   gint n;
  18
  19   g_assert (queue->length < 4000000000u);
  20
  21   g_assert (g_queue_get_length (queue) == queue->length);
  22
  23   if (!queue->head)
  24     g_assert (!queue->tail);
  25   if (!queue->tail)
  26     g_assert (!queue->head);
  27
  28   n = 0;
  29   last = NULL;
  30   for (list = queue->head; list != NULL; list = list->next)
  31     {
  32       if (!list->next)
  33         last = list;
  34       ++n;
  35     }
  36   g_assert (n == queue->length);
  37   g_assert (last == queue->tail);
  38
  39   n = 0;
  40   last = NULL;
  41   for (list = queue->tail; list != NULL; list = list->prev)
  42     {
  43       if (!list->prev)
  44         last = list;
  45       ++n;
  46     }
  47   g_assert (n == queue->length);
  48   g_assert (last == queue->head);
  49
  50   links = NULL;
  51   for (list = queue->head; list != NULL; list = list->next)
  52     links = g_list_prepend (links, list);
  53
  54   link = links;
  55   for (list = queue->tail; list != NULL; list = list->prev)
  56     {
  57       g_assert (list == link->data);
  58       link = link->next;
  59     }
  60   g_list_free (links);
  61
  62   links = NULL;
  63   for (list = queue->tail; list != NULL; list = list->prev)
  64     links = g_list_prepend (links, list);
  65
  66   link = links;
  67   for (list = queue->head; list != NULL; list = list->next)
  68     {
  69       g_assert (list == link->data);
  70       link = link->next;
  71     }
  72   g_list_free (links);
  73 }
  74
  75 static gboolean
  76 rnd_bool (void)
  77 {
  78   return g_random_int_range (0, 2);
  79 }
  80
  81 static void
  82 check_max (gpointer elm, gpointer user_data)
  83 {
  84   gint *best = user_data;
  85   gint element = GPOINTER_TO_INT (elm);
  86
  87   if (element > *best)
  88     *best = element;
  89 }
  90
  91 static void
  92 check_min (gpointer elm, gpointer user_data)
  93 {
  94   gint *best = user_data;
  95   gint element = GPOINTER_TO_INT (elm);
  96
  97   if (element < *best)
  98     *best = element;
  99 }
 100
 101 static gint
 102 find_min (GQueue *queue)
 103 {
 104   gint min = G_MAXINT;
 105
 106   g_queue_foreach (queue, check_min, &min);
 107
 108   return min;
 109 }
 110
 111 static gint
 112 find_max (GQueue *queue)
 113 {
 114   gint max = G_MININT;
 115
 116   g_queue_foreach (queue, check_max, &max);
 117
 118   return max;
 119 }
 120
 121 static void
 122 delete_elm (gpointer elm, gpointer user_data)
 123 {
 124   g_queue_remove ((GQueue *)user_data, elm);
 125   check_integrity ((GQueue *)user_data);
 126 }
 127
 128 static void
 129 delete_all (GQueue *queue)
 130 {
 131   g_queue_foreach (queue, delete_elm, queue);
 132 }
 133
 134 static int
 135 compare_int (gconstpointer a, gconstpointer b, gpointer data)
 136 {
 137   int ai = GPOINTER_TO_INT (a);
 138   int bi = GPOINTER_TO_INT (b);
 139
 140   if (ai > bi)
 141     return 1;
 142   else if (ai == bi)
 143     return 0;
 144   else
 145     return -1;
 146 }
 147
 148 static gint
 149 get_random_position (GQueue *queue, gboolean allow_offlist)
 150 {
 151   int n;
 152   enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
 153
 154   if (allow_offlist)
 155     where = g_random_int_range (OFF_QUEUE, LAST);
 156   else
 157     where = g_random_int_range (HEAD, LAST);
 158
 159   switch (where)
 160     {
 161     case OFF_QUEUE:
 162       n = g_random_int ();
 163       break;
 164
 165     case HEAD:
 166       n = 0;
 167       break;
 168
 169     case TAIL:
 170       if (allow_offlist)
 171         n = queue->length;
 172       else
 173         n = queue->length - 1;
 174       break;
 175
 176     case MIDDLE:
 177       if (queue->length == 0)
 178         n = 0;
 179       else
 180         n = g_random_int_range (0, queue->length);
 181       break;
 182
 183     default:
 184       g_assert_not_reached();
 185       n = 100;
 186       break;
 187
 188     }
 189
 190   return n;
 191 }
 192
 193 static void
 194 random_test (gconstpointer d)
 195 {
 196   guint32 seed = GPOINTER_TO_UINT (d);
 197
 198   typedef enum {
 199     IS_EMPTY, GET_LENGTH, REVERSE, COPY,
 200     FOREACH, FIND, FIND_CUSTOM, SORT,
 201     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
 202     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
 203     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
 204     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
 205     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
 206     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
 207     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
 208   } QueueOp;
 209
 210 #define N_ITERATIONS 500000
 211 #define N_QUEUES 3
 212
 213 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
 214
 215   typedef struct QueueInfo QueueInfo;
 216   struct QueueInfo
 217   {
 218     GQueue *queue;
 219     GList *tail;
 220     GList *head;
 221     guint length;
 222   };
 223
 224   gint i;
 225   QueueOp op;
 226   QueueInfo queues[N_QUEUES];
 227
 228   g_random_set_seed (seed);
 229
 230   for (i = 0; i < N_QUEUES; ++i)
 231     {
 232       queues[i].queue = g_queue_new ();
 233       queues[i].head = NULL;
 234       queues[i].tail = NULL;
 235       queues[i].length = 0;
 236     }
 237
 238   for (i = 0; i < N_ITERATIONS; ++i)
 239     {
 240       int j;
 241       QueueInfo *qinf = RANDOM_QUEUE();
 242       GQueue *q = qinf->queue;
 243       op = g_random_int_range (IS_EMPTY, LAST_OP);
 244
 245       g_assert (qinf->head == q->head);
 246       g_assert (qinf->tail == q->tail);
 247       g_assert (qinf->length == q->length);
 248
 249       switch (op)
 250         {
 251         case IS_EMPTY:
 252           {
 253             if (g_queue_is_empty (qinf->queue))
 254               {
 255                 g_assert (q->head == NULL);
 256                 g_assert (q->tail == NULL);
 257                 g_assert (q->length == 0);
 258               }
 259             else
 260               {
 261                 g_assert (q->head);
 262                 g_assert (q->tail);
 263                 g_assert (q->length > 0);
 264               }
 265           }
 266           break;
 267         case GET_LENGTH:
 268           {
 269             int l;
 270
 271             l = g_queue_get_length (q);
 272
 273             g_assert (qinf->length == q->length);
 274             g_assert (qinf->length == l);
 275           }
 276           break;
 277         case REVERSE:
 278           g_queue_reverse (q);
 279           g_assert (qinf->tail == q->head);
 280           g_assert (qinf->head == q->tail);
 281           g_assert (qinf->length == q->length);
 282           qinf->tail = q->tail;
 283           qinf->head = q->head;
 284           break;
 285         case COPY:
 286           {
 287             QueueInfo *random_queue = RANDOM_QUEUE();
 288             GQueue *new_queue = g_queue_copy (random_queue->queue);
 289
 290             g_queue_free (qinf->queue);
 291             q = qinf->queue = new_queue;
 292             qinf->head = new_queue->head;
 293             qinf->tail = g_list_last (new_queue->head);
 294             qinf->length = new_queue->length;
 295           }
 296           break;
 297         case FOREACH:
 298           delete_all (q);
 299           qinf->head = NULL;
 300           qinf->tail = NULL;
 301           qinf->length = 0;
 302           break;
 303         case FIND:
 304           {
 305             gboolean find_existing = rnd_bool ();
 306             int first = find_max (q);
 307             int second = find_min (q);
 308
 309             if (q->length == 0)
 310               find_existing = FALSE;
 311
 312             if (!find_existing)
 313               first++;
 314             if (!find_existing)
 315               second--;
 316
 317             if (find_existing)
 318               {
 319                 g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
 320                 g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
 321               }
 322             else
 323               {
 324                 g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
 325                 g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
 326               }
 327           }
 328           break;
 329         case FIND_CUSTOM:
 330           break;
 331         case SORT:
 332           {
 333             if (!g_queue_is_empty (q))
 334               {
 335                 int max = find_max (q);
 336                 int min = find_min (q);
 337                 g_queue_remove_all (q, GINT_TO_POINTER (max));
 338                 check_integrity (q);
 339                 g_queue_remove_all (q, GINT_TO_POINTER (min));
 340                 check_integrity (q);
 341                 g_queue_push_head (q, GINT_TO_POINTER (max));
 342                 if (max != min)
 343                   g_queue_push_head (q, GINT_TO_POINTER (min));
 344                 qinf->length = q->length;
 345               }
 346
 347             check_integrity (q);
 348
 349             g_queue_sort (q, compare_int, NULL);
 350
 351             check_integrity (q);
 352
 353             qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
 354             qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
 355
 356             g_assert (qinf->tail == q->tail);
 357           }
 358           break;
 359         case PUSH_HEAD:
 360           {
 361             int x = g_random_int_range (0, 435435);
 362             g_queue_push_head (q, GINT_TO_POINTER (x));
 363             if (!qinf->head)
 364               qinf->tail = qinf->head = q->head;
 365             else
 366               qinf->head = qinf->head->prev;
 367             qinf->length++;
 368           }
 369           break;
 370         case PUSH_TAIL:
 371           {
 372             int x = g_random_int_range (0, 236546);
 373             g_queue_push_tail (q, GINT_TO_POINTER (x));
 374             if (!qinf->tail)
 375               qinf->tail = qinf->head = q->head;
 376             else
 377               qinf->tail = qinf->tail->next;
 378             qinf->length++;
 379           }
 380           break;
 381         case PUSH_NTH:
 382           {
 383             int pos = get_random_position (q, TRUE);
 384             int x = g_random_int_range (0, 236546);
 385             g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
 386             if (qinf->head && qinf->head->prev)
 387               qinf->head = qinf->head->prev;
 388             else
 389               qinf->head = q->head;
 390             if (qinf->tail && qinf->tail->next)
 391               qinf->tail = qinf->tail->next;
 392             else
 393               qinf->tail = g_list_last (qinf->head);
 394             qinf->length++;
 395           }
 396           break;
 397         case POP_HEAD:
 398           if (qinf->head)
 399             qinf->head = qinf->head->next;
 400           if (!qinf->head)
 401             qinf->tail = NULL;
 402           qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
 403           g_queue_pop_head (q);
 404           break;
 405         case POP_TAIL:
 406           if (qinf->tail)
 407             qinf->tail = qinf->tail->prev;
 408           if (!qinf->tail)
 409             qinf->head = NULL;
 410           qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
 411           g_queue_pop_tail (q);
 412           break;
 413         case POP_NTH:
 414           if (!g_queue_is_empty (q))
 415             {
 416               int n = get_random_position (q, TRUE);
 417               gpointer elm = g_queue_peek_nth (q, n);
 418
 419               if (n == q->length - 1)
 420                 qinf->tail = qinf->tail->prev;
 421
 422               if (n == 0)
 423                 qinf->head = qinf->head->next;
 424
 425               if (n >= 0 && n < q->length)
 426                 qinf->length--;
 427
 428               g_assert (elm == g_queue_pop_nth (q, n));
 429             }
 430           break;
 431         case PEEK_HEAD:
 432           if (qinf->head)
 433             g_assert (qinf->head->data == g_queue_peek_head (q));
 434           else
 435             g_assert (g_queue_peek_head (q) == NULL);
 436           break;
 437         case PEEK_TAIL:
 438           if (qinf->head)
 439             g_assert (qinf->tail->data == g_queue_peek_tail (q));
 440           else
 441             g_assert (g_queue_peek_tail (q) == NULL);
 442           break;
 443         case PEEK_NTH:
 444           if (g_queue_is_empty (q))
 445             {
 446               for (j = -10; j < 10; ++j)
 447                 g_assert (g_queue_peek_nth (q, j) == NULL);
 448             }
 449           else
 450             {
 451               GList *list;
 452               int n = get_random_position (q, TRUE);
 453               if (n < 0 || n >= q->length)
 454                 {
 455                   g_assert (g_queue_peek_nth (q, n) == NULL);
 456                 }
 457               else
 458                 {
 459                   list = qinf->head;
 460                   for (j = 0; j < n; ++j)
 461                     list = list->next;
 462
 463                   g_assert (list->data == g_queue_peek_nth (q, n));
 464                 }
 465             }
 466           break;
 467         case INDEX:
 468         case LINK_INDEX:
 469           {
 470             int x = g_random_int_range (0, 386538);
 471             int n;
 472             GList *list;
 473
 474             g_queue_remove_all (q, GINT_TO_POINTER (x));
 475             check_integrity (q);
 476             g_queue_push_tail (q, GINT_TO_POINTER (x));
 477             check_integrity (q);
 478             g_queue_sort (q, compare_int, NULL);
 479             check_integrity (q);
 480
 481             n = 0;
 482             for (list = q->head; list != NULL; list = list->next)
 483               {
 484                 if (list->data == GINT_TO_POINTER (x))
 485                   break;
 486                 n++;
 487               }
 488             g_assert (list);
 489             g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
 490                       g_queue_link_index (q, list));
 491             g_assert (g_queue_link_index (q, list) == n);
 492
 493             qinf->head = q->head;
 494             qinf->tail = q->tail;
 495             qinf->length = q->length;
 496           }
 497           break;
 498         case REMOVE:
 499           if (!g_queue_is_empty (q))
 500             g_queue_remove (q, qinf->tail->data);
 501           /* qinf->head/qinf->tail may be invalid at this point */
 502           if (!g_queue_is_empty (q))
 503             g_queue_remove (q, q->head->data);
 504           if (!g_queue_is_empty (q))
 505             g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
 506
 507           qinf->head = q->head;
 508           qinf->tail = q->tail;
 509           qinf->length = q->length;
 510           break;
 511         case REMOVE_ALL:
 512           if (!g_queue_is_empty (q))
 513             g_queue_remove_all (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_all (q, q->head->data);
 517           if (!g_queue_is_empty (q))
 518             g_queue_remove_all (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 INSERT_BEFORE:
 525           if (!g_queue_is_empty (q))
 526             {
 527               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 528
 529               g_queue_insert_before (q, qinf->tail, x);
 530               g_queue_insert_before (q, qinf->head, x);
 531               g_queue_insert_before (q, g_queue_find (q, x), x);
 532               g_queue_insert_before (q, NULL, x);
 533             }
 534           qinf->head = q->head;
 535           qinf->tail = q->tail;
 536           qinf->length = q->length;
 537           break;
 538         case INSERT_AFTER:
 539           if (!g_queue_is_empty (q))
 540             {
 541               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 542
 543               g_queue_insert_after (q, qinf->tail, x);
 544               g_queue_insert_after (q, qinf->head, x);
 545               g_queue_insert_after (q, g_queue_find (q, x), x);
 546               g_queue_insert_after (q, NULL, x);
 547             }
 548           qinf->head = q->head;
 549           qinf->tail = q->tail;
 550           qinf->length = q->length;
 551           break;
 552         case INSERT_SORTED:
 553           {
 554             int max = find_max (q);
 555             int min = find_min (q);
 556
 557             if (g_queue_is_empty (q))
 558               {
 559                 max = 345;
 560                 min = -12;
 561               }
 562
 563             g_queue_sort (q, compare_int, NULL);
 564             check_integrity (q);
 565             g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
 566             check_integrity (q);
 567             g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
 568             g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
 569             check_integrity (q);
 570             g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
 571             qinf->head = q->head;
 572             qinf->tail = q->tail;
 573             qinf->length = q->length;
 574           }
 575           break;
 576         case PUSH_HEAD_LINK:
 577           {
 578             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 579             g_queue_push_head_link (q, link);
 580             if (!qinf->tail)
 581               qinf->tail = link;
 582             qinf->head = link;
 583             qinf->length++;
 584           }
 585           break;
 586         case PUSH_TAIL_LINK:
 587           {
 588             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 589             g_queue_push_tail_link (q, link);
 590             if (!qinf->head)
 591               qinf->head = link;
 592             qinf->tail = link;
 593             qinf->length++;
 594           }
 595           break;
 596         case PUSH_NTH_LINK:
 597           {
 598             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 599             gint n = get_random_position (q, TRUE);
 600             g_queue_push_nth_link (q, n, link);
 601
 602             if (qinf->head && qinf->head->prev)
 603               qinf->head = qinf->head->prev;
 604             else
 605               qinf->head = q->head;
 606             if (qinf->tail && qinf->tail->next)
 607               qinf->tail = qinf->tail->next;
 608             else
 609               qinf->tail = g_list_last (qinf->head);
 610             qinf->length++;
 611           }
 612           break;
 613         case POP_HEAD_LINK:
 614           if (!g_queue_is_empty (q))
 615             {
 616               qinf->head = qinf->head->next;
 617               if (!qinf->head)
 618                 qinf->tail = NULL;
 619               qinf->length--;
 620               g_list_free (g_queue_pop_head_link (q));
 621             }
 622           break;
 623         case POP_TAIL_LINK:
 624           if (!g_queue_is_empty (q))
 625             {
 626               qinf->tail = qinf->tail->prev;
 627               if (!qinf->tail)
 628                 qinf->head = NULL;
 629               qinf->length--;
 630               g_list_free (g_queue_pop_tail_link (q));
 631             }
 632           break;
 633         case POP_NTH_LINK:
 634           if (g_queue_is_empty (q))
 635             g_assert (g_queue_pop_nth_link (q, 200) == NULL);
 636           else
 637             {
 638               int n = get_random_position (q, FALSE);
 639
 640               if (n == g_queue_get_length (q) - 1)
 641                 qinf->tail = qinf->tail->prev;
 642
 643               if (n == 0)
 644                 qinf->head = qinf->head->next;
 645
 646               qinf->length--;
 647
 648               g_list_free (g_queue_pop_nth_link (q, n));
 649             }
 650           break;
 651         case PEEK_HEAD_LINK:
 652           if (g_queue_is_empty (q))
 653             g_assert (g_queue_peek_head_link (q) == NULL);
 654           else
 655             g_assert (g_queue_peek_head_link (q) == qinf->head);
 656           break;
 657         case PEEK_TAIL_LINK:
 658           if (g_queue_is_empty (q))
 659             g_assert (g_queue_peek_tail_link (q) == NULL);
 660           else
 661             g_assert (g_queue_peek_tail_link (q) == qinf->tail);
 662           break;
 663         case PEEK_NTH_LINK:
 664           if (g_queue_is_empty(q))
 665             g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
 666           else
 667             {
 668               gint n = get_random_position (q, FALSE);
 669               GList *link;
 670
 671               link = q->head;
 672               for (j = 0; j < n; ++j)
 673                 link = link->next;
 674
 675               g_assert (g_queue_peek_nth_link (q, n) == link);
 676             }
 677           break;
 678         case UNLINK:
 679           if (!g_queue_is_empty (q))
 680             {
 681               gint n = g_random_int_range (0, g_queue_get_length (q));
 682               GList *link;
 683
 684               link = q->head;
 685               for (j = 0; j < n; ++j)
 686                 link = link->next;
 687
 688               g_queue_unlink (q, link);
 689               check_integrity (q);
 690
 691               g_list_free (link);
 692
 693               qinf->head = q->head;
 694               qinf->tail = q->tail;
 695               qinf->length--;
 696             }
 697           break;
 698         case DELETE_LINK:
 699           if (!g_queue_is_empty (q))
 700             {
 701               gint n = g_random_int_range (0, g_queue_get_length (q));
 702               GList *link;
 703
 704               link = q->head;
 705               for (j = 0; j < n; ++j)
 706                 link = link->next;
 707
 708               g_queue_delete_link (q, link);
 709               check_integrity (q);
 710
 711               qinf->head = q->head;
 712               qinf->tail = q->tail;
 713               qinf->length--;
 714             }
 715           break;
 716         case LAST_OP:
 717         default:
 718           g_assert_not_reached();
 719           break;
 720         }
 721
 722       if (qinf->head != q->head ||
 723           qinf->tail != q->tail ||
 724           qinf->length != q->length)
 725         g_printerr ("op: %d\n", op);
 726
 727       g_assert (qinf->head == q->head);
 728       g_assert (qinf->tail == q->tail);
 729       g_assert (qinf->length == q->length);
 730
 731       for (j = 0; j < N_QUEUES; ++j)
 732         check_integrity (queues[j].queue);
 733     }
 734
 735   for (i = 0; i < N_QUEUES; ++i)
 736     g_queue_free (queues[i].queue);
 737 }
 738
 739 static void
 740 remove_item (gpointer data, gpointer q)
 741 {
 742   GQueue *queue = q;
 743
 744   g_queue_remove (queue, data);
 745 }
 746
 747 static void
 748 test_basic (void)
 749 {
 750   GQueue *q;
 751   GList *node;
 752   gpointer data;
 753
 754   q = g_queue_new ();
 755
 756   g_assert (g_queue_is_empty (q));
 757   g_queue_push_head (q, GINT_TO_POINTER (2));
 758   check_integrity (q);
 759   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
 760   check_integrity (q);
 761   g_assert (!g_queue_is_empty (q));
 762   check_integrity (q);
 763   g_assert_cmpint (g_list_length (q->head), ==, 1);
 764   g_assert (q->head == q->tail);
 765   g_queue_push_head (q, GINT_TO_POINTER (1));
 766   check_integrity (q);
 767   g_assert (q->head->next == q->tail);
 768   g_assert (q->tail->prev == q->head);
 769   g_assert_cmpint (g_list_length (q->head), ==, 2);
 770   check_integrity (q);
 771   g_assert (q->tail->data == GINT_TO_POINTER (2));
 772   g_assert (q->head->data == GINT_TO_POINTER (1));
 773   check_integrity (q);
 774   g_queue_push_tail (q, GINT_TO_POINTER (3));
 775   g_assert_cmpint (g_list_length (q->head), ==, 3);
 776   g_assert (q->head->data == GINT_TO_POINTER (1));
 777   g_assert (q->head->next->data == GINT_TO_POINTER (2));
 778   g_assert (q->head->next->next == q->tail);
 779   g_assert (q->head->next == q->tail->prev);
 780   g_assert (q->tail->data == GINT_TO_POINTER (3));
 781   g_queue_push_tail (q, GINT_TO_POINTER (4));
 782   check_integrity (q);
 783   g_assert_cmpint (g_list_length (q->head), ==, 4);
 784   g_assert (q->head->data == GINT_TO_POINTER (1));
 785   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
 786   g_queue_push_tail (q, GINT_TO_POINTER (5));
 787   check_integrity (q);
 788   g_assert_cmpint (g_list_length (q->head), ==, 5);
 789   g_assert (g_queue_is_empty (q) == FALSE);
 790   check_integrity (q);
 791   g_assert_cmpint (q->length, ==, 5);
 792   g_assert (q->head->prev == NULL);
 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->data == GINT_TO_POINTER (3));
 796   g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
 797   g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
 798   g_assert (q->head->next->next->next->next->next == NULL);
 799   g_assert (q->head->next->next->next->next == q->tail);
 800   g_assert (q->tail->data == GINT_TO_POINTER (5));
 801   g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
 802   g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
 803   g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
 804   g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
 805   g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
 806   g_assert (q->tail->prev->prev->prev->prev == q->head);
 807   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
 808   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
 809   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
 810   check_integrity (q);
 811   g_assert_cmpint (g_list_length (q->head), ==, 4);
 812   g_assert_cmpint (q->length, ==, 4);
 813   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
 814   check_integrity (q);
 815   g_assert_cmpint (g_list_length (q->head), ==, 3);
 816
 817   node = g_queue_pop_head_link (q);
 818   g_assert (node->data == GINT_TO_POINTER (2));
 819   g_list_free_1 (node);
 820
 821   check_integrity (q);
 822   g_assert_cmpint (g_list_length (q->head), ==, 2);
 823   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
 824   check_integrity (q);
 825   g_assert_cmpint (g_list_length (q->head), ==, 1);
 826   node = g_queue_pop_head_link (q);
 827   g_assert (node->data == GINT_TO_POINTER (3));
 828   g_list_free_1 (node);
 829   check_integrity (q);
 830   g_assert_cmpint (g_list_length (q->head), ==, 0);
 831   g_assert (g_queue_pop_tail (q) == NULL);
 832   check_integrity (q);
 833   g_assert_cmpint (g_list_length (q->head), ==, 0);
 834   g_assert (g_queue_pop_head (q) == NULL);
 835   check_integrity (q);
 836   g_assert_cmpint (g_list_length (q->head), ==, 0);
 837   g_assert (g_queue_is_empty (q));
 838   check_integrity (q);
 839
 840   g_queue_push_head (q, GINT_TO_POINTER (1));
 841   check_integrity (q);
 842   g_assert_cmpint (g_list_length (q->head), ==, 1);
 843   g_assert_cmpint (q->length, ==, 1);
 844   g_queue_push_head (q, GINT_TO_POINTER (2));
 845   check_integrity (q);
 846   g_assert_cmpint (g_list_length (q->head), ==, 2);
 847   g_assert_cmpint (q->length, ==, 2);
 848   g_queue_push_head (q, GINT_TO_POINTER (3));
 849   check_integrity (q);
 850   g_assert_cmpint (g_list_length (q->head), ==, 3);
 851   g_assert_cmpint (q->length, ==, 3);
 852   g_queue_push_head (q, GINT_TO_POINTER (4));
 853   check_integrity (q);
 854   g_assert_cmpint (g_list_length (q->head), ==, 4);
 855   g_assert_cmpint (q->length, ==, 4);
 856   g_queue_push_head (q, GINT_TO_POINTER (5));
 857   check_integrity (q);
 858   g_assert_cmpint (g_list_length (q->head), ==, 5);
 859   g_assert_cmpint (q->length, ==, 5);
 860   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
 861   check_integrity (q);
 862   g_assert_cmpint (g_list_length (q->head), ==, 4);
 863   node = q->tail;
 864   g_assert (node == g_queue_pop_tail_link (q));
 865   check_integrity (q);
 866   g_list_free_1 (node);
 867   g_assert_cmpint (g_list_length (q->head), ==, 3);
 868   data = q->head->data;
 869   g_assert (data == g_queue_pop_head (q));
 870   check_integrity (q);
 871   g_assert_cmpint (g_list_length (q->head), ==, 2);
 872   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
 873   check_integrity (q);
 874   g_assert_cmpint (g_list_length (q->head), ==, 1);
 875   g_assert (q->head == q->tail);
 876   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
 877   check_integrity (q);
 878   g_assert_cmpint (g_list_length (q->head), ==, 0);
 879   g_assert (g_queue_pop_head (q) == NULL);
 880   check_integrity (q);
 881   g_assert (g_queue_pop_head_link (q) == NULL);
 882   check_integrity (q);
 883   g_assert_cmpint (g_list_length (q->head), ==, 0);
 884   g_assert (g_queue_pop_tail_link (q) == NULL);
 885   check_integrity (q);
 886   g_assert_cmpint (g_list_length (q->head), ==, 0);
 887
 888   g_queue_reverse (q);
 889   check_integrity (q);
 890   g_assert_cmpint (g_list_length (q->head), ==, 0);
 891   g_queue_free (q);
 892 }
 893
 894 static void
 895 test_copy (void)
 896 {
 897   GQueue *q, *q2;
 898   gint i;
 899
 900   q = g_queue_new ();
 901   q2 = g_queue_copy (q);
 902   check_integrity (q);
 903   check_integrity (q2);
 904   g_assert_cmpint (g_list_length (q->head), ==, 0);
 905   g_assert_cmpint (g_list_length (q2->head), ==, 0);
 906   g_queue_sort (q, compare_int, NULL);
 907   check_integrity (q2);
 908   check_integrity (q);
 909   g_queue_sort (q2, compare_int, NULL);
 910   check_integrity (q2);
 911   check_integrity (q);
 912
 913   for (i = 0; i < 200; ++i)
 914     {
 915       g_queue_push_nth (q, GINT_TO_POINTER (i), i);
 916       g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
 917       check_integrity (q);
 918       check_integrity (q2);
 919     }
 920
 921   for (i = 0; i < 200; ++i)
 922     {
 923       g_queue_remove (q, GINT_TO_POINTER (i));
 924       check_integrity (q);
 925       check_integrity (q2);
 926     }
 927
 928   for (i = 0; i < 200; ++i)
 929     {
 930       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
 931
 932       g_queue_push_nth_link (q, i, l);
 933       check_integrity (q);
 934       check_integrity (q2);
 935       g_queue_reverse (q);
 936       check_integrity (q);
 937       check_integrity (q2);
 938     }
 939
 940   g_queue_free (q2);
 941   q2 = g_queue_copy (q);
 942
 943   g_queue_foreach (q2, remove_item, q2);
 944   check_integrity (q2);
 945   check_integrity (q);
 946
 947   g_queue_free (q);
 948   g_queue_free (q2);
 949 }
 950
 951 static void
 952 test_off_by_one (void)
 953 {
 954   GQueue *q;
 955   GList *node;
 956
 957   q = g_queue_new ();
 958
 959   g_queue_push_tail (q, GINT_TO_POINTER (1234));
 960   check_integrity (q);
 961   node = g_queue_peek_tail_link (q);
 962   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
 963   node = g_queue_peek_nth_link (q, g_queue_get_length (q));
 964   g_assert (node == NULL);
 965   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
 966   g_assert (node->data == GINT_TO_POINTER (1234));
 967   node = g_queue_pop_nth_link (q, g_queue_get_length (q));
 968   g_assert (node == NULL);
 969   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
 970   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
 971   g_list_free_1 (node);
 972
 973   g_queue_free (q);
 974 }
 975
 976 static gint
 977 find_custom (gconstpointer a, gconstpointer b)
 978 {
 979   return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
 980 }
 981
 982 static void
 983 test_find_custom (void)
 984 {
 985   GQueue *q;
 986   GList *node;
 987   q = g_queue_new ();
 988
 989   g_queue_push_tail (q, GINT_TO_POINTER (1234));
 990   g_queue_push_tail (q, GINT_TO_POINTER (1));
 991   g_queue_push_tail (q, GINT_TO_POINTER (2));
 992   node = g_queue_find_custom  (q, GINT_TO_POINTER (1), find_custom);
 993   g_assert (node != NULL);
 994   node = g_queue_find_custom  (q, GINT_TO_POINTER (2), find_custom);
 995   g_assert (node != NULL);
 996   node = g_queue_find_custom  (q, GINT_TO_POINTER (3), find_custom);
 997   g_assert (node == NULL);
 998
 999   g_queue_free (q);
1000 }
1001
1002 static void
1003 test_static (void)
1004 {
1005   GQueue q;
1006   GQueue q2 = G_QUEUE_INIT;
1007
1008   g_queue_init (&q);
1009
1010   check_integrity (&q);
1011   g_assert (g_queue_is_empty (&q));
1012
1013   check_integrity (&q2);
1014   g_assert (g_queue_is_empty (&q2));
1015 }
1016
1017 static void
1018 test_clear (void)
1019 {
1020   GQueue *q;
1021   q = g_queue_new ();
1022
1023   g_queue_push_tail (q, GINT_TO_POINTER (1234));
1024   g_queue_push_tail (q, GINT_TO_POINTER (1));
1025   g_queue_push_tail (q, GINT_TO_POINTER (2));
1026   g_assert_cmpint (g_queue_get_length (q), ==, 3);
1027
1028   g_queue_clear (q);
1029   check_integrity (q);
1030   g_assert (g_queue_is_empty (q));
1031
1032   g_queue_free (q);
1033 }
1034
1035 typedef struct
1036 {
1037   gboolean freed;
1038   int x;
1039 } QueueItem;
1040
1041 static void
1042 free_func (gpointer data)
1043 {
1044   QueueItem *item = data;
1045
1046   item->freed = TRUE;
1047 }
1048
1049 static QueueItem *
1050 new_item (int x)
1051 {
1052   QueueItem *item;
1053
1054   item = g_slice_new (QueueItem);
1055   item->freed = FALSE;
1056   item->x = x;
1057
1058   return item;
1059 }
1060
1061 static void
1062 test_free_full (void)
1063 {
1064   QueueItem *one, *two, *three;
1065   GQueue *queue = NULL;
1066
1067   queue = g_queue_new();
1068   g_queue_push_tail (queue, one = new_item (1));
1069   g_queue_push_tail (queue, two = new_item (2));
1070   g_queue_push_tail (queue, three = new_item (3));
1071   g_assert (!one->freed);
1072   g_assert (!two->freed);
1073   g_assert (!three->freed);
1074   g_queue_free_full (queue, free_func);
1075   g_assert (one->freed);
1076   g_assert (two->freed);
1077   g_assert (three->freed);
1078   g_slice_free (QueueItem, one);
1079   g_slice_free (QueueItem, two);
1080   g_slice_free (QueueItem, three);
1081 }
1082
1083
1084 int main (int argc, char *argv[])
1085 {
1086   guint32 seed;
1087   gchar *path;
1088
1089   g_test_init (&argc, &argv, NULL);
1090
1091   g_test_add_func ("/queue/basic", test_basic);
1092   g_test_add_func ("/queue/copy", test_copy);
1093   g_test_add_func ("/queue/off-by-one", test_off_by_one);
1094   g_test_add_func ("/queue/find-custom", test_find_custom);
1095   g_test_add_func ("/queue/static", test_static);
1096   g_test_add_func ("/queue/clear", test_clear);
1097   g_test_add_func ("/queue/free-full", test_free_full);
1098
1099   seed = g_test_rand_int_range (0, G_MAXINT);
1100   path = g_strdup_printf ("/queue/random/seed:%u", seed);
1101   g_test_add_data_func (path, GUINT_TO_POINTER (seed), random_test);
1102   g_free (path);
1103
1104   return g_test_run ();
1105 }