tests/queue-test.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 gboolean verbose = FALSE;
  11
  12
  13 static void
  14 check_integrity (GQueue *queue)
  15 {
  16   GList *list;
  17   GList *last;
  18   GList *links;
  19   GList *link;
  20   gint n;
  21
  22   g_assert (queue->length < 4000000000u);
  23
  24   g_assert (g_queue_get_length (queue) == queue->length);
  25
  26   if (!queue->head)
  27     g_assert (!queue->tail);
  28   if (!queue->tail)
  29     g_assert (!queue->head);
  30
  31   n = 0;
  32   last = NULL;
  33   for (list = queue->head; list != NULL; list = list->next)
  34     {
  35       if (!list->next)
  36         last = list;
  37       ++n;
  38     }
  39   g_assert (n == queue->length);
  40   g_assert (last == queue->tail);
  41
  42   n = 0;
  43   last = NULL;
  44   for (list = queue->tail; list != NULL; list = list->prev)
  45     {
  46       if (!list->prev)
  47         last = list;
  48       ++n;
  49     }
  50   g_assert (n == queue->length);
  51   g_assert (last == queue->head);
  52
  53   links = NULL;
  54   for (list = queue->head; list != NULL; list = list->next)
  55     links = g_list_prepend (links, list);
  56
  57   link = links;
  58   for (list = queue->tail; list != NULL; list = list->prev)
  59     {
  60       g_assert (list == link->data);
  61       link = link->next;
  62     }
  63   g_list_free (links);
  64
  65   links = NULL;
  66   for (list = queue->tail; list != NULL; list = list->prev)
  67     links = g_list_prepend (links, list);
  68
  69   link = links;
  70   for (list = queue->head; list != NULL; list = list->next)
  71     {
  72       g_assert (list == link->data);
  73       link = link->next;
  74     }
  75   g_list_free (links);
  76 }
  77
  78 static gboolean
  79 rnd_bool (void)
  80 {
  81   return g_random_int_range (0, 2);
  82 }
  83
  84 static void
  85 check_max (gpointer elm, gpointer user_data)
  86 {
  87   gint *best = user_data;
  88   gint element = GPOINTER_TO_INT (elm);
  89
  90   if (element > *best)
  91     *best = element;
  92 }
  93
  94 static void
  95 check_min (gpointer elm, gpointer user_data)
  96 {
  97   gint *best = user_data;
  98   gint element = GPOINTER_TO_INT (elm);
  99
 100   if (element < *best)
 101     *best = element;
 102 }
 103
 104 static gint
 105 find_min (GQueue *queue)
 106 {
 107   gint min = G_MAXINT;
 108
 109   g_queue_foreach (queue, check_min, &min);
 110
 111   return min;
 112 }
 113
 114 static gint
 115 find_max (GQueue *queue)
 116 {
 117   gint max = G_MININT;
 118
 119   g_queue_foreach (queue, check_max, &max);
 120
 121   return max;
 122 }
 123
 124 static void
 125 delete_elm (gpointer elm, gpointer user_data)
 126 {
 127   g_queue_remove ((GQueue *)user_data, elm);
 128   check_integrity ((GQueue *)user_data);
 129 }
 130
 131 static void
 132 delete_all (GQueue *queue)
 133 {
 134   g_queue_foreach (queue, delete_elm, queue);
 135 }
 136
 137 static int
 138 compare_int (gconstpointer a, gconstpointer b, gpointer data)
 139 {
 140   int ai = GPOINTER_TO_INT (a);
 141   int bi = GPOINTER_TO_INT (b);
 142
 143   if (ai > bi)
 144     return 1;
 145   else if (ai == bi)
 146     return 0;
 147   else
 148     return -1;
 149 }
 150
 151 static gint
 152 get_random_position (GQueue *queue, gboolean allow_offlist)
 153 {
 154   int n;
 155   enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
 156
 157   if (allow_offlist)
 158     where = g_random_int_range (OFF_QUEUE, LAST);
 159   else
 160     where = g_random_int_range (HEAD, LAST);
 161
 162   switch (where)
 163     {
 164     case OFF_QUEUE:
 165       n = g_random_int ();
 166       break;
 167
 168     case HEAD:
 169       n = 0;
 170       break;
 171
 172     case TAIL:
 173       if (allow_offlist)
 174         n = queue->length;
 175       else
 176         n = queue->length - 1;
 177       break;
 178
 179     case MIDDLE:
 180       if (queue->length == 0)
 181         n = 0;
 182       else
 183         n = g_random_int_range (0, queue->length);
 184       break;
 185
 186     default:
 187       g_assert_not_reached();
 188       n = 100;
 189       break;
 190
 191     }
 192
 193   return n;
 194 }
 195
 196 static void
 197 random_test (int seed)
 198 {
 199   typedef enum {
 200     IS_EMPTY, GET_LENGTH, REVERSE, COPY,
 201     FOREACH, FIND, FIND_CUSTOM, SORT,
 202     PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
 203     POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
 204     PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
 205     INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
 206     PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
 207     POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
 208     LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
 209   } QueueOp;
 210
 211 #define N_ITERATIONS 500000
 212 #define N_QUEUES 3
 213
 214 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
 215
 216   typedef struct QueueInfo QueueInfo;
 217   struct QueueInfo
 218   {
 219     GQueue *queue;
 220     GList *tail;
 221     GList *head;
 222     guint length;
 223   };
 224
 225   gint i;
 226   QueueOp op;
 227   QueueInfo queues[N_QUEUES];
 228
 229   if (verbose)
 230     g_print ("seed: %d\n", seed);
 231
 232   g_random_set_seed (seed);
 233
 234   for (i = 0; i < N_QUEUES; ++i)
 235     {
 236       queues[i].queue = g_queue_new ();
 237       queues[i].head = NULL;
 238       queues[i].tail = NULL;
 239       queues[i].length = 0;
 240     }
 241
 242   for (i = 0; i < N_ITERATIONS; ++i)
 243     {
 244       int j;
 245       QueueInfo *qinf = RANDOM_QUEUE();
 246       GQueue *q = qinf->queue;
 247       op = g_random_int_range (IS_EMPTY, LAST_OP);
 248
 249       g_assert (qinf->head == q->head);
 250       g_assert (qinf->tail == q->tail);
 251       g_assert (qinf->length == q->length);
 252
 253       switch (op)
 254         {
 255         case IS_EMPTY:
 256           {
 257             if (g_queue_is_empty (qinf->queue))
 258               {
 259                 g_assert (q->head == NULL);
 260                 g_assert (q->tail == NULL);
 261                 g_assert (q->length == 0);
 262               }
 263             else
 264               {
 265                 g_assert (q->head);
 266                 g_assert (q->tail);
 267                 g_assert (q->length > 0);
 268               }
 269           }
 270           break;
 271         case GET_LENGTH:
 272           {
 273             int l;
 274
 275             l = g_queue_get_length (q);
 276
 277             g_assert (qinf->length == q->length);
 278             g_assert (qinf->length == l);
 279           }
 280           break;
 281         case REVERSE:
 282           g_queue_reverse (q);
 283           g_assert (qinf->tail == q->head);
 284           g_assert (qinf->head == q->tail);
 285           g_assert (qinf->length == q->length);
 286           qinf->tail = q->tail;
 287           qinf->head = q->head;
 288           break;
 289         case COPY:
 290           {
 291             QueueInfo *random_queue = RANDOM_QUEUE();
 292             GQueue *new_queue = g_queue_copy (random_queue->queue);
 293
 294             g_queue_free (qinf->queue);
 295             q = qinf->queue = new_queue;
 296             qinf->head = new_queue->head;
 297             qinf->tail = g_list_last (new_queue->head);
 298             qinf->length = new_queue->length;
 299           }
 300           break;
 301         case FOREACH:
 302           delete_all (q);
 303           qinf->head = NULL;
 304           qinf->tail = NULL;
 305           qinf->length = 0;
 306           break;
 307         case FIND:
 308           {
 309             gboolean find_existing = rnd_bool ();
 310             int first = find_max (q);
 311             int second = find_min (q);
 312
 313             if (q->length == 0)
 314               find_existing = FALSE;
 315
 316             if (!find_existing)
 317               first++;
 318             if (!find_existing)
 319               second--;
 320
 321             if (find_existing)
 322               {
 323                 g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
 324                 g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
 325               }
 326             else
 327               {
 328                 g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
 329                 g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
 330               }
 331           }
 332           break;
 333         case FIND_CUSTOM:
 334           break;
 335         case SORT:
 336           {
 337             if (!g_queue_is_empty (q))
 338               {
 339                 int max = find_max (q);
 340                 int min = find_min (q);
 341                 g_queue_remove_all (q, GINT_TO_POINTER (max));
 342                 check_integrity (q);
 343                 g_queue_remove_all (q, GINT_TO_POINTER (min));
 344                 check_integrity (q);
 345                 g_queue_push_head (q, GINT_TO_POINTER (max));
 346                 if (max != min)
 347                   g_queue_push_head (q, GINT_TO_POINTER (min));
 348                 qinf->length = q->length;
 349               }
 350
 351             check_integrity (q);
 352
 353             g_queue_sort (q, compare_int, NULL);
 354
 355             check_integrity (q);
 356
 357             qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
 358             qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
 359
 360             g_assert (qinf->tail == q->tail);
 361           }
 362           break;
 363         case PUSH_HEAD:
 364           {
 365             int x = g_random_int_range (0, 435435);
 366             g_queue_push_head (q, GINT_TO_POINTER (x));
 367             if (!qinf->head)
 368               qinf->tail = qinf->head = q->head;
 369             else
 370               qinf->head = qinf->head->prev;
 371             qinf->length++;
 372           }
 373           break;
 374         case PUSH_TAIL:
 375           {
 376             int x = g_random_int_range (0, 236546);
 377             g_queue_push_tail (q, GINT_TO_POINTER (x));
 378             if (!qinf->tail)
 379               qinf->tail = qinf->head = q->head;
 380             else
 381               qinf->tail = qinf->tail->next;
 382             qinf->length++;
 383           }
 384           break;
 385         case PUSH_NTH:
 386           {
 387             int pos = get_random_position (q, TRUE);
 388             int x = g_random_int_range (0, 236546);
 389             g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
 390             if (qinf->head && qinf->head->prev)
 391               qinf->head = qinf->head->prev;
 392             else
 393               qinf->head = q->head;
 394             if (qinf->tail && qinf->tail->next)
 395               qinf->tail = qinf->tail->next;
 396             else
 397               qinf->tail = g_list_last (qinf->head);
 398             qinf->length++;
 399           }
 400           break;
 401         case POP_HEAD:
 402           if (qinf->head)
 403             qinf->head = qinf->head->next;
 404           if (!qinf->head)
 405             qinf->tail = NULL;
 406           qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
 407           g_queue_pop_head (q);
 408           break;
 409         case POP_TAIL:
 410           if (qinf->tail)
 411             qinf->tail = qinf->tail->prev;
 412           if (!qinf->tail)
 413             qinf->head = NULL;
 414           qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
 415           g_queue_pop_tail (q);
 416           break;
 417         case POP_NTH:
 418           if (!g_queue_is_empty (q))
 419             {
 420               int n = get_random_position (q, TRUE);
 421               gpointer elm = g_queue_peek_nth (q, n);
 422
 423               if (n == q->length - 1)
 424                 qinf->tail = qinf->tail->prev;
 425
 426               if (n == 0)
 427                 qinf->head = qinf->head->next;
 428
 429               if (n >= 0 && n < q->length)
 430                 qinf->length--;
 431
 432               g_assert (elm == g_queue_pop_nth (q, n));
 433             }
 434           break;
 435         case PEEK_HEAD:
 436           if (qinf->head)
 437             g_assert (qinf->head->data == g_queue_peek_head (q));
 438           else
 439             g_assert (g_queue_peek_head (q) == NULL);
 440           break;
 441         case PEEK_TAIL:
 442           if (qinf->head)
 443             g_assert (qinf->tail->data == g_queue_peek_tail (q));
 444           else
 445             g_assert (g_queue_peek_tail (q) == NULL);
 446           break;
 447         case PEEK_NTH:
 448           if (g_queue_is_empty (q))
 449             {
 450               for (j = -10; j < 10; ++j)
 451                 g_assert (g_queue_peek_nth (q, j) == NULL);
 452             }
 453           else
 454             {
 455               GList *list;
 456               int n = get_random_position (q, TRUE);
 457               if (n < 0 || n >= q->length)
 458                 {
 459                   g_assert (g_queue_peek_nth (q, n) == NULL);
 460                 }
 461               else
 462                 {
 463                   list = qinf->head;
 464                   for (j = 0; j < n; ++j)
 465                     list = list->next;
 466
 467                   g_assert (list->data == g_queue_peek_nth (q, n));
 468                 }
 469             }
 470           break;
 471         case INDEX:
 472         case LINK_INDEX:
 473           {
 474             int x = g_random_int_range (0, 386538);
 475             int n;
 476             GList *list;
 477
 478             g_queue_remove_all (q, GINT_TO_POINTER (x));
 479             check_integrity (q);
 480             g_queue_push_tail (q, GINT_TO_POINTER (x));
 481             check_integrity (q);
 482             g_queue_sort (q, compare_int, NULL);
 483             check_integrity (q);
 484
 485             n = 0;
 486             for (list = q->head; list != NULL; list = list->next)
 487               {
 488                 if (list->data == GINT_TO_POINTER (x))
 489                   break;
 490                 n++;
 491               }
 492             g_assert (list);
 493             g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
 494                       g_queue_link_index (q, list));
 495             g_assert (g_queue_link_index (q, list) == n);
 496
 497             qinf->head = q->head;
 498             qinf->tail = q->tail;
 499             qinf->length = q->length;
 500           }
 501           break;
 502         case REMOVE:
 503           if (!g_queue_is_empty (q))
 504             g_queue_remove (q, qinf->tail->data);
 505           if (!g_queue_is_empty (q))
 506             g_queue_remove (q, qinf->head->data);
 507           if (!g_queue_is_empty (q))
 508             g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
 509
 510           qinf->head = q->head;
 511           qinf->tail = q->tail;
 512           qinf->length = q->length;
 513           break;
 514         case REMOVE_ALL:
 515           if (!g_queue_is_empty (q))
 516             g_queue_remove_all (q, qinf->tail->data);
 517           if (!g_queue_is_empty (q))
 518             g_queue_remove_all (q, qinf->head->data);
 519           if (!g_queue_is_empty (q))
 520             g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
 521
 522           qinf->head = q->head;
 523           qinf->tail = q->tail;
 524           qinf->length = q->length;
 525           break;
 526         case INSERT_BEFORE:
 527           if (!g_queue_is_empty (q))
 528             {
 529               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 530
 531               g_queue_insert_before (q, qinf->tail, x);
 532               g_queue_insert_before (q, qinf->head, x);
 533               g_queue_insert_before (q, g_queue_find (q, x), x);
 534             }
 535           qinf->head = q->head;
 536           qinf->tail = q->tail;
 537           qinf->length = q->length;
 538           break;
 539         case INSERT_AFTER:
 540           if (!g_queue_is_empty (q))
 541             {
 542               gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
 543
 544               g_queue_insert_after (q, qinf->tail, x);
 545               g_queue_insert_after (q, qinf->head, x);
 546               g_queue_insert_after (q, g_queue_find (q, x), 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_print ("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 int main(int argc, gchar *args[])
 748 {
 749   GQueue *q, *q2;
 750   GList *node;
 751   gpointer data;
 752   int i;
 753
 754   if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v')
 755     verbose = TRUE;
 756
 757   q = g_queue_new ();
 758
 759   g_assert (g_queue_is_empty (q) == TRUE);
 760
 761   g_queue_push_head (q, GINT_TO_POINTER (2));
 762   check_integrity (q);
 763   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
 764   check_integrity (q);
 765   g_assert (g_queue_is_empty (q) == FALSE);
 766   check_integrity (q);
 767   g_assert (g_list_length (q->head) == 1);
 768   g_assert (q->head == q->tail);
 769   g_queue_push_head (q, GINT_TO_POINTER (1));
 770   check_integrity (q);
 771   g_assert (q->head->next == q->tail);
 772   g_assert (q->tail->prev == q->head);
 773   g_assert (g_list_length (q->head) == 2);
 774   check_integrity (q);
 775   g_assert (q->tail->data == GINT_TO_POINTER (2));
 776   g_assert (q->head->data == GINT_TO_POINTER (1));
 777   check_integrity (q);
 778   g_queue_push_tail (q, GINT_TO_POINTER (3));
 779   g_assert (g_list_length (q->head) == 3);
 780   g_assert (q->head->data == GINT_TO_POINTER (1));
 781   g_assert (q->head->next->data == GINT_TO_POINTER (2));
 782   g_assert (q->head->next->next == q->tail);
 783   g_assert (q->head->next == q->tail->prev);
 784   g_assert (q->tail->data == GINT_TO_POINTER (3));
 785   g_queue_push_tail (q, GINT_TO_POINTER (4));
 786   check_integrity (q);
 787   g_assert (g_list_length (q->head) == 4);
 788   g_assert (q->head->data == GINT_TO_POINTER (1));
 789   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
 790   g_queue_push_tail (q, GINT_TO_POINTER (5));
 791   check_integrity (q);
 792   g_assert (g_list_length (q->head) == 5);
 793
 794   g_assert (g_queue_is_empty (q) == FALSE);
 795   check_integrity (q);
 796
 797   g_assert (q->length == 5);
 798   g_assert (q->head->prev == NULL);
 799   g_assert (q->head->data == GINT_TO_POINTER (1));
 800   g_assert (q->head->next->data == GINT_TO_POINTER (2));
 801   g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
 802   g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
 803   g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
 804   g_assert (q->head->next->next->next->next->next == NULL);
 805   g_assert (q->head->next->next->next->next == q->tail);
 806   g_assert (q->tail->data == GINT_TO_POINTER (5));
 807   g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
 808   g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
 809   g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
 810   g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
 811   g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
 812   g_assert (q->tail->prev->prev->prev->prev == q->head);
 813   g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
 814   g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
 815
 816   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
 817   check_integrity (q);
 818   g_assert (g_list_length (q->head) == 4 && q->length == 4);
 819   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
 820   check_integrity (q);
 821   g_assert (g_list_length (q->head) == 3);
 822   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
 823   check_integrity (q);
 824   g_assert (g_list_length (q->head) == 2);
 825   g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
 826   check_integrity (q);
 827   g_assert (g_list_length (q->head) == 1);
 828   g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
 829   check_integrity (q);
 830   g_assert (g_list_length (q->head) == 0);
 831   g_assert (g_queue_pop_tail (q) == NULL);
 832   check_integrity (q);
 833   g_assert (g_list_length (q->head) == 0);
 834   g_assert (g_queue_pop_head (q) == NULL);
 835   check_integrity (q);
 836   g_assert (g_list_length (q->head) == 0);
 837
 838   g_assert (g_queue_is_empty (q) == TRUE);
 839   check_integrity (q);
 840
 841   /************************/
 842
 843   g_queue_push_head (q, GINT_TO_POINTER (1));
 844   check_integrity (q);
 845   g_assert (g_list_length (q->head) == 1 && 1 == q->length);
 846   g_queue_push_head (q, GINT_TO_POINTER (2));
 847   check_integrity (q);
 848   g_assert (g_list_length (q->head) == 2 && 2 == q->length);
 849   g_queue_push_head (q, GINT_TO_POINTER (3));
 850   check_integrity (q);
 851   g_assert (g_list_length (q->head) == 3 && 3 == q->length);
 852   g_queue_push_head (q, GINT_TO_POINTER (4));
 853   check_integrity (q);
 854   g_assert (g_list_length (q->head) == 4 && 4 == q->length);
 855   g_queue_push_head (q, GINT_TO_POINTER (5));
 856   check_integrity (q);
 857   g_assert (g_list_length (q->head) == 5 && 5 == q->length);
 858
 859   g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
 860   check_integrity (q);
 861   g_assert (g_list_length (q->head) == 4);
 862   node = q->tail;
 863   g_assert (node == g_queue_pop_tail_link (q));
 864   check_integrity (q);
 865   g_assert (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 (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 (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 (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 (g_list_length (q->head) == 0);
 882   g_assert (g_queue_pop_tail_link (q) == NULL);
 883   check_integrity (q);
 884   g_assert (g_list_length (q->head) == 0);
 885
 886   /* */
 887   g_queue_reverse (q);
 888   check_integrity (q);
 889   g_assert (g_list_length (q->head) == 0);
 890
 891   q2 = g_queue_copy (q);
 892   check_integrity (q);
 893   check_integrity (q2);
 894   g_assert (g_list_length (q->head) == 0);
 895   g_assert (g_list_length (q2->head) == 0);
 896   g_queue_sort (q, compare_int, NULL);
 897   check_integrity (q2);
 898   check_integrity (q);
 899   g_queue_sort (q2, compare_int, NULL);
 900   check_integrity (q2);
 901   check_integrity (q);
 902
 903   for (i = 0; i < 200; ++i)
 904     {
 905       g_queue_push_nth (q, GINT_TO_POINTER (i), i);
 906       g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
 907       check_integrity (q);
 908       check_integrity (q2);
 909     }
 910
 911   for (i = 0; i < 200; ++i)
 912     {
 913       g_queue_remove (q, GINT_TO_POINTER (i));
 914       check_integrity (q);
 915       check_integrity (q2);
 916     }
 917
 918   for (i = 0; i < 200; ++i)
 919     {
 920       GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
 921
 922       g_queue_push_nth_link (q, i, l);
 923       check_integrity (q);
 924       check_integrity (q2);
 925       g_queue_reverse (q);
 926       check_integrity (q);
 927       check_integrity (q2);
 928     }
 929
 930   g_queue_free (q2);
 931   q2 = g_queue_copy (q);
 932
 933   g_queue_foreach (q2, remove_item, q2);
 934   check_integrity (q2);
 935   check_integrity (q);
 936
 937   /* some checks for off by one errors */
 938   g_queue_push_tail (q, GINT_TO_POINTER (1234));
 939   check_integrity (q);
 940   node = g_queue_peek_tail_link (q);
 941   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
 942   node = g_queue_peek_nth_link (q, g_queue_get_length (q));
 943   g_assert (node == NULL);
 944   node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
 945   g_assert (node->data == GINT_TO_POINTER (1234));
 946   node = g_queue_pop_nth_link (q, g_queue_get_length (q));
 947   g_assert (node == NULL);
 948   node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
 949   g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
 950
 951   g_queue_free (q);
 952
 953   if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v')
 954     random_test (strtol (args[2], NULL, 0));
 955   if (argc > 1)
 956     random_test (strtol (args[1], NULL, 0));
 957   else
 958     random_test (time (0));
 959
 960   return 0;
 961 }
 962