tests/queue-test.c

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