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