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