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           if (!g_queue_is_empty (q))
 502             g_queue_remove (q, qinf->head->data);
 503           if (!g_queue_is_empty (q))
 504             g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
 505
 506           qinf->head = q->head;
 507           qinf->tail = q->tail;
 508           qinf->length = q->length;
 509           break;
 510         case REMOVE_ALL:
 511           if (!g_queue_is_empty (q))
 512             g_queue_remove_all (q, qinf->tail->data);
 513           if (!g_queue_is_empty (q))
 514             g_queue_remove_all (q, qinf->head->data);
 515           if (!g_queue_is_empty (q))
 516             g_queue_remove_all (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 INSERT_BEFORE:
 523           if (!g_queue_is_empty (q))
 524             {
 525               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 526
 527               g_queue_insert_before (q, qinf->tail, x);
 528               g_queue_insert_before (q, qinf->head, x);
 529               g_queue_insert_before (q, g_queue_find (q, x), x);
 530             }
 531           qinf->head = q->head;
 532           qinf->tail = q->tail;
 533           qinf->length = q->length;
 534           break;
 535         case INSERT_AFTER:
 536           if (!g_queue_is_empty (q))
 537             {
 538               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 539
 540               g_queue_insert_after (q, qinf->tail, x);
 541               g_queue_insert_after (q, qinf->head, x);
 542               g_queue_insert_after (q, g_queue_find (q, x), x);
 543             }
 544           qinf->head = q->head;
 545           qinf->tail = q->tail;
 546           qinf->length = q->length;
 547           break;
 548         case INSERT_SORTED:
 549           {
 550             int max = find_max (q);
 551             int min = find_min (q);
 552
 553             if (g_queue_is_empty (q))
 554               {
 555                 max = 345;
 556                 min = -12;
 557               }
 558
 559             g_queue_sort (q, compare_int, NULL);
 560             check_integrity (q);
 561             g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
 562             check_integrity (q);
 563             g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
 564             g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
 565             check_integrity (q);
 566             g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
 567             qinf->head = q->head;
 568             qinf->tail = q->tail;
 569             qinf->length = q->length;
 570           }
 571           break;
 572         case PUSH_HEAD_LINK:
 573           {
 574             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 575             g_queue_push_head_link (q, link);
 576             if (!qinf->tail)
 577               qinf->tail = link;
 578             qinf->head = link;
 579             qinf->length++;
 580           }
 581           break;
 582         case PUSH_TAIL_LINK:
 583           {
 584             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 585             g_queue_push_tail_link (q, link);
 586             if (!qinf->head)
 587               qinf->head = link;
 588             qinf->tail = link;
 589             qinf->length++;
 590           }
 591           break;
 592         case PUSH_NTH_LINK:
 593           {
 594             GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
 595             gint n = get_random_position (q, TRUE);
 596             g_queue_push_nth_link (q, n, link);
 597
 598             if (qinf->head && qinf->head->prev)
 599               qinf->head = qinf->head->prev;
 600             else
 601               qinf->head = q->head;
 602             if (qinf->tail && qinf->tail->next)
 603               qinf->tail = qinf->tail->next;
 604             else
 605               qinf->tail = g_list_last (qinf->head);
 606             qinf->length++;
 607           }
 608           break;
 609         case POP_HEAD_LINK:
 610           if (!g_queue_is_empty (q))
 611             {
 612               qinf->head = qinf->head->next;
 613               if (!qinf->head)
 614                 qinf->tail = NULL;
 615               qinf->length--;
 616               g_list_free (g_queue_pop_head_link (q));
 617             }
 618           break;
 619         case POP_TAIL_LINK:
 620           if (!g_queue_is_empty (q))
 621             {
 622               qinf->tail = qinf->tail->prev;
 623               if (!qinf->tail)
 624                 qinf->head = NULL;
 625               qinf->length--;
 626               g_list_free (g_queue_pop_tail_link (q));
 627             }
 628           break;
 629         case POP_NTH_LINK:
 630           if (g_queue_is_empty (q))
 631             g_assert (g_queue_pop_nth_link (q, 200) == NULL);
 632           else
 633             {
 634               int n = get_random_position (q, FALSE);
 635
 636               if (n == g_queue_get_length (q) - 1)
 637                 qinf->tail = qinf->tail->prev;
 638
 639               if (n == 0)
 640                 qinf->head = qinf->head->next;
 641
 642               qinf->length--;
 643
 644               g_list_free (g_queue_pop_nth_link (q, n));
 645             }
 646           break;
 647         case PEEK_HEAD_LINK:
 648           if (g_queue_is_empty (q))
 649             g_assert (g_queue_peek_head_link (q) == NULL);
 650           else
 651             g_assert (g_queue_peek_head_link (q) == qinf->head);
 652           break;
 653         case PEEK_TAIL_LINK:
 654           if (g_queue_is_empty (q))
 655             g_assert (g_queue_peek_tail_link (q) == NULL);
 656           else
 657             g_assert (g_queue_peek_tail_link (q) == qinf->tail);
 658           break;
 659         case PEEK_NTH_LINK:
 660           if (g_queue_is_empty(q))
 661             g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
 662           else
 663             {
 664               gint n = get_random_position (q, FALSE);
 665               GList *link;
 666
 667               link = q->head;
 668               for (j = 0; j < n; ++j)
 669                 link = link->next;
 670
 671               g_assert (g_queue_peek_nth_link (q, n) == link);
 672             }
 673           break;
 674         case UNLINK:
 675           if (!g_queue_is_empty (q))
 676             {
 677               gint n = g_random_int_range (0, g_queue_get_length (q));
 678               GList *link;
 679
 680               link = q->head;
 681               for (j = 0; j < n; ++j)
 682                 link = link->next;
 683
 684               g_queue_unlink (q, link);
 685               check_integrity (q);
 686
 687               g_list_free (link);
 688
 689               qinf->head = q->head;
 690               qinf->tail = q->tail;
 691               qinf->length--;
 692             }
 693           break;
 694         case DELETE_LINK:
 695           if (!g_queue_is_empty (q))
 696             {
 697               gint n = g_random_int_range (0, g_queue_get_length (q));
 698               GList *link;
 699
 700               link = q->head;
 701               for (j = 0; j < n; ++j)
 702                 link = link->next;
 703
 704               g_queue_delete_link (q, link);
 705               check_integrity (q);
 706
 707               qinf->head = q->head;
 708               qinf->tail = q->tail;
 709               qinf->length--;
 710             }
 711           break;
 712         case LAST_OP:
 713         default:
 714           g_assert_not_reached();
 715           break;
 716         }
 717
 718       if (qinf->head != q->head ||
 719           qinf->tail != q->tail ||
 720           qinf->length != q->length)
 721         g_print ("op: %d\n", op);
 722
 723       g_assert (qinf->head == q->head);
 724       g_assert (qinf->tail == q->tail);
 725       g_assert (qinf->length == q->length);
 726
 727       for (j = 0; j < N_QUEUES; ++j)
 728         check_integrity (queues[j].queue);
 729     }
 730
 731   for (i = 0; i < N_QUEUES; ++i)
 732     g_queue_free (queues[i].queue);
 733 }
 734
 735 static void
 736 remove_item (gpointer data, gpointer q)
 737 {
 738   GQueue *queue = q;
 739
 740   g_queue_remove (queue, data);
 741 }
 742
 743 static void
 744 test_basic (void)
 745 {
 746   GQueue *q;
 747   GList *node;
 748   gpointer data;
 749
 750   q = g_queue_new ();
 751
 752   g_assert (g_queue_is_empty (q));
 753   g_queue_push_head (q, GINT_TO_POINTER (2));
 754   check_integrity (q);
 755   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
 756   check_integrity (q);
 757   g_assert (!g_queue_is_empty (q));
 758   check_integrity (q);
 759   g_assert_cmpint (g_list_length (q->head), ==, 1);
 760   g_assert (q->head == q->tail);
 761   g_queue_push_head (q, GINT_TO_POINTER (1));
 762   check_integrity (q);
 763   g_assert (q->head->next == q->tail);
 764   g_assert (q->tail->prev == q->head);
 765   g_assert_cmpint (g_list_length (q->head), ==, 2);
 766   check_integrity (q);
 767   g_assert (q->tail->data == GINT_TO_POINTER (2));
 768   g_assert (q->head->data == GINT_TO_POINTER (1));
 769   check_integrity (q);
 770   g_queue_push_tail (q, GINT_TO_POINTER (3));
 771   g_assert_cmpint (g_list_length (q->head), ==, 3);
 772   g_assert (q->head->data == GINT_TO_POINTER (1));
 773   g_assert (q->head->next->data == GINT_TO_POINTER (2));
 774   g_assert (q->head->next->next == q->tail);
 775   g_assert (q->head->next == q->tail->prev);
 776   g_assert (q->tail->data == GINT_TO_POINTER (3));
 777   g_queue_push_tail (q, GINT_TO_POINTER (4));
 778   check_integrity (q);
 779   g_assert_cmpint (g_list_length (q->head), ==, 4);
 780   g_assert (q->head->data == GINT_TO_POINTER (1));
 781   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
 782   g_queue_push_tail (q, GINT_TO_POINTER (5));
 783   check_integrity (q);
 784   g_assert_cmpint (g_list_length (q->head), ==, 5);
 785   g_assert (g_queue_is_empty (q) == FALSE);
 786   check_integrity (q);
 787   g_assert_cmpint (q->length, ==, 5);
 788   g_assert (q->head->prev == NULL);
 789   g_assert (q->head->data == GINT_TO_POINTER (1));
 790   g_assert (q->head->next->data == GINT_TO_POINTER (2));
 791   g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
 792   g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
 793   g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
 794   g_assert (q->head->next->next->next->next->next == NULL);
 795   g_assert (q->head->next->next->next->next == q->tail);
 796   g_assert (q->tail->data == GINT_TO_POINTER (5));
 797   g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
 798   g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
 799   g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
 800   g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
 801   g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
 802   g_assert (q->tail->prev->prev->prev->prev == q->head);
 803   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
 804   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
 805   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
 806   check_integrity (q);
 807   g_assert_cmpint (g_list_length (q->head), ==, 4);
 808   g_assert_cmpint (q->length, ==, 4);
 809   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
 810   check_integrity (q);
 811   g_assert_cmpint (g_list_length (q->head), ==, 3);
 812   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
 813   check_integrity (q);
 814   g_assert_cmpint (g_list_length (q->head), ==, 2);
 815   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
 816   check_integrity (q);
 817   g_assert_cmpint (g_list_length (q->head), ==, 1);
 818   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
 819   check_integrity (q);
 820   g_assert_cmpint (g_list_length (q->head), ==, 0);
 821   g_assert (g_queue_pop_tail (q) == NULL);
 822   check_integrity (q);
 823   g_assert_cmpint (g_list_length (q->head), ==, 0);
 824   g_assert (g_queue_pop_head (q) == NULL);
 825   check_integrity (q);
 826   g_assert_cmpint (g_list_length (q->head), ==, 0);
 827   g_assert (g_queue_is_empty (q));
 828   check_integrity (q);
 829
 830   g_queue_push_head (q, GINT_TO_POINTER (1));
 831   check_integrity (q);
 832   g_assert_cmpint (g_list_length (q->head), ==, 1);
 833   g_assert_cmpint (q->length, ==, 1);
 834   g_queue_push_head (q, GINT_TO_POINTER (2));
 835   check_integrity (q);
 836   g_assert_cmpint (g_list_length (q->head), ==, 2);
 837   g_assert_cmpint (q->length, ==, 2);
 838   g_queue_push_head (q, GINT_TO_POINTER (3));
 839   check_integrity (q);
 840   g_assert_cmpint (g_list_length (q->head), ==, 3);
 841   g_assert_cmpint (q->length, ==, 3);
 842   g_queue_push_head (q, GINT_TO_POINTER (4));
 843   check_integrity (q);
 844   g_assert_cmpint (g_list_length (q->head), ==, 4);
 845   g_assert_cmpint (q->length, ==, 4);
 846   g_queue_push_head (q, GINT_TO_POINTER (5));
 847   check_integrity (q);
 848   g_assert_cmpint (g_list_length (q->head), ==, 5);
 849   g_assert_cmpint (q->length, ==, 5);
 850   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
 851   check_integrity (q);
 852   g_assert_cmpint (g_list_length (q->head), ==, 4);
 853   node = q->tail;
 854   g_assert (node == g_queue_pop_tail_link (q));
 855   check_integrity (q);
 856   g_assert_cmpint (g_list_length (q->head), ==, 3);
 857   data = q->head->data;
 858   g_assert (data == g_queue_pop_head (q));
 859   check_integrity (q);
 860   g_assert_cmpint (g_list_length (q->head), ==, 2);
 861   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
 862   check_integrity (q);
 863   g_assert_cmpint (g_list_length (q->head), ==, 1);
 864   g_assert (q->head == q->tail);
 865   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
 866   check_integrity (q);
 867   g_assert_cmpint (g_list_length (q->head), ==, 0);
 868   g_assert (g_queue_pop_head (q) == NULL);
 869   check_integrity (q);
 870   g_assert (g_queue_pop_head_link (q) == NULL);
 871   check_integrity (q);
 872   g_assert_cmpint (g_list_length (q->head), ==, 0);
 873   g_assert (g_queue_pop_tail_link (q) == NULL);
 874   check_integrity (q);
 875   g_assert_cmpint (g_list_length (q->head), ==, 0);
 876
 877   g_queue_reverse (q);
 878   check_integrity (q);
 879   g_assert_cmpint (g_list_length (q->head), ==, 0);
 880   g_queue_free (q);
 881 }
 882
 883 static void
 884 test_copy (void)
 885 {
 886   GQueue *q, *q2;
 887   gint i;
 888
 889   q = g_queue_new ();
 890   q2 = g_queue_copy (q);
 891   check_integrity (q);
 892   check_integrity (q2);
 893   g_assert_cmpint (g_list_length (q->head), ==, 0);
 894   g_assert_cmpint (g_list_length (q2->head), ==, 0);
 895   g_queue_sort (q, compare_int, NULL);
 896   check_integrity (q2);
 897   check_integrity (q);
 898   g_queue_sort (q2, compare_int, NULL);
 899   check_integrity (q2);
 900   check_integrity (q);
 901
 902   for (i = 0; i < 200; ++i)
 903     {
 904       g_queue_push_nth (q, GINT_TO_POINTER (i), i);
 905       g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
 906       check_integrity (q);
 907       check_integrity (q2);
 908     }
 909
 910   for (i = 0; i < 200; ++i)
 911     {
 912       g_queue_remove (q, GINT_TO_POINTER (i));
 913       check_integrity (q);
 914       check_integrity (q2);
 915     }
 916
 917   for (i = 0; i < 200; ++i)
 918     {
 919       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
 920
 921       g_queue_push_nth_link (q, i, l);
 922       check_integrity (q);
 923       check_integrity (q2);
 924       g_queue_reverse (q);
 925       check_integrity (q);
 926       check_integrity (q2);
 927     }
 928
 929   g_queue_free (q2);
 930   q2 = g_queue_copy (q);
 931
 932   g_queue_foreach (q2, remove_item, q2);
 933   check_integrity (q2);
 934   check_integrity (q);
 935
 936   g_queue_free (q);
 937   g_queue_free (q2);
 938 }
 939
 940 static void
 941 test_off_by_one (void)
 942 {
 943   GQueue *q;
 944   GList *node;
 945
 946   q = g_queue_new ();
 947
 948   g_queue_push_tail (q, GINT_TO_POINTER (1234));
 949   check_integrity (q);
 950   node = g_queue_peek_tail_link (q);
 951   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
 952   node = g_queue_peek_nth_link (q, g_queue_get_length (q));
 953   g_assert (node == NULL);
 954   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
 955   g_assert (node->data == GINT_TO_POINTER (1234));
 956   node = g_queue_pop_nth_link (q, g_queue_get_length (q));
 957   g_assert (node == NULL);
 958   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
 959   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
 960
 961   g_queue_free (q);
 962 }
 963
 964 static gint
 965 find_custom (gconstpointer a, gconstpointer b)
 966 {
 967   return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
 968 }
 969
 970 static void
 971 test_find_custom (void)
 972 {
 973   GQueue *q;
 974   GList *node;
 975   q = g_queue_new ();
 976
 977   g_queue_push_tail (q, GINT_TO_POINTER (1234));
 978   g_queue_push_tail (q, GINT_TO_POINTER (1));
 979   g_queue_push_tail (q, GINT_TO_POINTER (2));
 980   node = g_queue_find_custom  (q, GINT_TO_POINTER (1), find_custom);
 981   g_assert (node != NULL);
 982   node = g_queue_find_custom  (q, GINT_TO_POINTER (2), find_custom);
 983   g_assert (node != NULL);
 984   node = g_queue_find_custom  (q, GINT_TO_POINTER (3), find_custom);
 985   g_assert (node == NULL);
 986
 987   g_queue_free (q);
 988 }
 989
 990 static void
 991 test_static (void)
 992 {
 993   GQueue q;
 994   GQueue q2 = G_QUEUE_INIT;
 995
 996   g_queue_init (&q);
 997
 998   check_integrity (&q);
 999   g_assert (g_queue_is_empty (&q));
1000
1001   check_integrity (&q2);
1002   g_assert (g_queue_is_empty (&q2));
1003 }
1004
1005 static void
1006 test_clear (void)
1007 {
1008   GQueue *q;
1009   q = g_queue_new ();
1010
1011   g_queue_push_tail (q, GINT_TO_POINTER (1234));
1012   g_queue_push_tail (q, GINT_TO_POINTER (1));
1013   g_queue_push_tail (q, GINT_TO_POINTER (2));
1014   g_assert_cmpint (g_queue_get_length (q), ==, 3);
1015
1016   g_queue_clear (q);
1017   check_integrity (q);
1018   g_assert (g_queue_is_empty (q));
1019
1020   g_queue_free (q);
1021 }
1022
1023 int main (int argc, char *argv[])
1024 {
1025   guint32 seed;
1026   gchar *path;
1027
1028   g_test_init (&argc, &argv, NULL);
1029
1030   g_test_add_func ("/queue/basic", test_basic);
1031   g_test_add_func ("/queue/copy", test_copy);
1032   g_test_add_func ("/queue/off-by-one", test_off_by_one);
1033   g_test_add_func ("/queue/find-custom", test_find_custom);
1034   g_test_add_func ("/queue/static", test_static);
1035   g_test_add_func ("/queue/clear", test_clear);
1036
1037   seed = g_test_rand_int_range (0, G_MAXINT);
1038   path = g_strdup_printf ("/queue/random/seed:%u", seed);
1039   g_test_add_data_func (path, GUINT_TO_POINTER (seed), random_test);
1040   g_free (path);
1041
1042   return g_test_run ();
1043 }