[glib] Move queue tests to the test framework

[Matthias Clasen <matthiasc src gnome org>]

commit e5a72ae3c415ae6e8437a0714f48311b534684c9
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Jul 25 19:12:51 2010 -0400

    Move queue tests to the test framework

 glib/tests/Makefile.am |    3 +
 glib/tests/queue.c     | 1043 ++++++++++++++++++++++++++++++++++++++++++++++++
 tests/Makefile.am      |    2 -
 tests/queue-test.c     |  962 --------------------------------------------
 4 files changed, 1046 insertions(+), 964 deletions(-)
---
diff --git a/glib/tests/Makefile.am b/glib/tests/Makefile.am
index 4095574..0205194 100644
--- a/glib/tests/Makefile.am
+++ b/glib/tests/Makefile.am
@@ -110,6 +110,9 @@ list_LDADD          = $(progs_ldadd)
 TEST_PROGS         += slist
 slist_LDADD         = $(progs_ldadd)
 
+TEST_PROGS         += queue
+queue_LDADD         = $(progs_ldadd)
+
 TEST_PROGS         += tree
 tree_LDADD          = $(progs_ldadd)
 
diff --git a/glib/tests/queue.c b/glib/tests/queue.c
new file mode 100644
index 0000000..1c33d72
--- /dev/null
+++ b/glib/tests/queue.c
@@ -0,0 +1,1043 @@
+#undef G_DISABLE_ASSERT
+#undef G_LOG_DOMAIN
+
+#include <time.h>
+#include <stdlib.h>
+
+#include <glib.h>
+
+
+static void
+check_integrity (GQueue *queue)
+{
+  GList *list;
+  GList *last;
+  GList *links;
+  GList *link;
+  gint n;
+
+  g_assert (queue->length < 4000000000u);
+
+  g_assert (g_queue_get_length (queue) == queue->length);
+
+  if (!queue->head)
+    g_assert (!queue->tail);
+  if (!queue->tail)
+    g_assert (!queue->head);
+
+  n = 0;
+  last = NULL;
+  for (list = queue->head; list != NULL; list = list->next)
+    {
+      if (!list->next)
+        last = list;
+      ++n;
+    }
+  g_assert (n == queue->length);
+  g_assert (last == queue->tail);
+
+  n = 0;
+  last = NULL;
+  for (list = queue->tail; list != NULL; list = list->prev)
+    {
+      if (!list->prev)
+        last = list;
+      ++n;
+    }
+  g_assert (n == queue->length);
+  g_assert (last == queue->head);
+
+  links = NULL;
+  for (list = queue->head; list != NULL; list = list->next)
+    links = g_list_prepend (links, list);
+
+  link = links;
+  for (list = queue->tail; list != NULL; list = list->prev)
+    {
+      g_assert (list == link->data);
+      link = link->next;
+    }
+  g_list_free (links);
+
+  links = NULL;
+  for (list = queue->tail; list != NULL; list = list->prev)
+    links = g_list_prepend (links, list);
+
+  link = links;
+  for (list = queue->head; list != NULL; list = list->next)
+    {
+      g_assert (list == link->data);
+      link = link->next;
+    }
+  g_list_free (links);
+}
+
+static gboolean
+rnd_bool (void)
+{
+  return g_random_int_range (0, 2);
+}
+
+static void
+check_max (gpointer elm, gpointer user_data)
+{
+  gint *best = user_data;
+  gint element = GPOINTER_TO_INT (elm);
+
+  if (element > *best)
+    *best = element;
+}
+
+static void
+check_min (gpointer elm, gpointer user_data)
+{
+  gint *best = user_data;
+  gint element = GPOINTER_TO_INT (elm);
+
+  if (element < *best)
+    *best = element;
+}
+
+static gint
+find_min (GQueue *queue)
+{
+  gint min = G_MAXINT;
+
+  g_queue_foreach (queue, check_min, &min);
+
+  return min;
+}
+
+static gint
+find_max (GQueue *queue)
+{
+  gint max = G_MININT;
+
+  g_queue_foreach (queue, check_max, &max);
+
+  return max;
+}
+
+static void
+delete_elm (gpointer elm, gpointer user_data)
+{
+  g_queue_remove ((GQueue *)user_data, elm);
+  check_integrity ((GQueue *)user_data);
+}
+
+static void
+delete_all (GQueue *queue)
+{
+  g_queue_foreach (queue, delete_elm, queue);
+}
+
+static int
+compare_int (gconstpointer a, gconstpointer b, gpointer data)
+{
+  int ai = GPOINTER_TO_INT (a);
+  int bi = GPOINTER_TO_INT (b);
+
+  if (ai > bi)
+    return 1;
+  else if (ai == bi)
+    return 0;
+  else
+    return -1;
+}
+
+static gint
+get_random_position (GQueue *queue, gboolean allow_offlist)
+{
+  int n;
+  enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
+
+  if (allow_offlist)
+    where = g_random_int_range (OFF_QUEUE, LAST);
+  else
+    where = g_random_int_range (HEAD, LAST);
+
+  switch (where)
+    {
+    case OFF_QUEUE:
+      n = g_random_int ();
+      break;
+
+    case HEAD:
+      n = 0;
+      break;
+
+    case TAIL:
+      if (allow_offlist)
+        n = queue->length;
+      else
+        n = queue->length - 1;
+      break;
+
+    case MIDDLE:
+      if (queue->length == 0)
+        n = 0;
+      else
+        n = g_random_int_range (0, queue->length);
+      break;
+
+    default:
+      g_assert_not_reached();
+      n = 100;
+      break;
+
+    }
+
+  return n;
+}
+
+static void
+random_test (gconstpointer d)
+{
+  guint32 seed = GPOINTER_TO_UINT (d);
+
+  typedef enum {
+    IS_EMPTY, GET_LENGTH, REVERSE, COPY,
+    FOREACH, FIND, FIND_CUSTOM, SORT,
+    PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
+    POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
+    PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
+    INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
+    PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
+    POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
+    LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
+  } QueueOp;
+
+#define N_ITERATIONS 500000
+#define N_QUEUES 3
+
+#define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
+
+  typedef struct QueueInfo QueueInfo;
+  struct QueueInfo
+  {
+    GQueue *queue;
+    GList *tail;
+    GList *head;
+    guint length;
+  };
+
+  gint i;
+  QueueOp op;
+  QueueInfo queues[N_QUEUES];
+
+  g_random_set_seed (seed);
+
+  for (i = 0; i < N_QUEUES; ++i)
+    {
+      queues[i].queue = g_queue_new ();
+      queues[i].head = NULL;
+      queues[i].tail = NULL;
+      queues[i].length = 0;
+    }
+
+  for (i = 0; i < N_ITERATIONS; ++i)
+    {
+      int j;
+      QueueInfo *qinf = RANDOM_QUEUE();
+      GQueue *q = qinf->queue;
+      op = g_random_int_range (IS_EMPTY, LAST_OP);
+
+      g_assert (qinf->head == q->head);
+      g_assert (qinf->tail == q->tail);
+      g_assert (qinf->length == q->length);
+
+      switch (op)
+        {
+        case IS_EMPTY:
+          {
+            if (g_queue_is_empty (qinf->queue))
+              {
+                g_assert (q->head == NULL);
+                g_assert (q->tail == NULL);
+                g_assert (q->length == 0);
+              }
+            else
+              {
+                g_assert (q->head);
+                g_assert (q->tail);
+                g_assert (q->length > 0);
+              }
+          }
+          break;
+        case GET_LENGTH:
+          {
+            int l;
+
+            l = g_queue_get_length (q);
+
+            g_assert (qinf->length == q->length);
+            g_assert (qinf->length == l);
+          }
+          break;
+        case REVERSE:
+          g_queue_reverse (q);
+          g_assert (qinf->tail == q->head);
+          g_assert (qinf->head == q->tail);
+          g_assert (qinf->length == q->length);
+          qinf->tail = q->tail;
+          qinf->head = q->head;
+          break;
+        case COPY:
+          {
+            QueueInfo *random_queue = RANDOM_QUEUE();
+            GQueue *new_queue = g_queue_copy (random_queue->queue);
+
+            g_queue_free (qinf->queue);
+            q = qinf->queue = new_queue;
+            qinf->head = new_queue->head;
+            qinf->tail = g_list_last (new_queue->head);
+            qinf->length = new_queue->length;
+          }
+          break;
+        case FOREACH:
+          delete_all (q);
+          qinf->head = NULL;
+          qinf->tail = NULL;
+          qinf->length = 0;
+          break;
+        case FIND:
+          {
+            gboolean find_existing = rnd_bool ();
+            int first = find_max (q);
+            int second = find_min (q);
+
+            if (q->length == 0)
+              find_existing = FALSE;
+
+            if (!find_existing)
+              first++;
+            if (!find_existing)
+              second--;
+
+            if (find_existing)
+              {
+                g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
+                g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
+              }
+            else
+              {
+                g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
+                g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
+              }
+          }
+          break;
+        case FIND_CUSTOM:
+          break;
+        case SORT:
+          {
+            if (!g_queue_is_empty (q))
+              {
+                int max = find_max (q);
+                int min = find_min (q);
+                g_queue_remove_all (q, GINT_TO_POINTER (max));
+                check_integrity (q);
+                g_queue_remove_all (q, GINT_TO_POINTER (min));
+                check_integrity (q);
+                g_queue_push_head (q, GINT_TO_POINTER (max));
+                if (max != min)
+                  g_queue_push_head (q, GINT_TO_POINTER (min));
+                qinf->length = q->length;
+              }
+
+            check_integrity (q);
+
+            g_queue_sort (q, compare_int, NULL);
+
+            check_integrity (q);
+
+            qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
+            qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
+
+            g_assert (qinf->tail == q->tail);
+          }
+          break;
+        case PUSH_HEAD:
+          {
+            int x = g_random_int_range (0, 435435);
+            g_queue_push_head (q, GINT_TO_POINTER (x));
+            if (!qinf->head)
+              qinf->tail = qinf->head = q->head;
+            else
+              qinf->head = qinf->head->prev;
+            qinf->length++;
+          }
+          break;
+        case PUSH_TAIL:
+          {
+            int x = g_random_int_range (0, 236546);
+            g_queue_push_tail (q, GINT_TO_POINTER (x));
+            if (!qinf->tail)
+              qinf->tail = qinf->head = q->head;
+            else
+              qinf->tail = qinf->tail->next;
+            qinf->length++;
+          }
+          break;
+        case PUSH_NTH:
+          {
+            int pos = get_random_position (q, TRUE);
+            int x = g_random_int_range (0, 236546);
+            g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
+            if (qinf->head && qinf->head->prev)
+              qinf->head = qinf->head->prev;
+            else
+              qinf->head = q->head;
+            if (qinf->tail && qinf->tail->next)
+              qinf->tail = qinf->tail->next;
+            else
+              qinf->tail = g_list_last (qinf->head);
+            qinf->length++;
+          }
+          break;
+        case POP_HEAD:
+          if (qinf->head)
+            qinf->head = qinf->head->next;
+          if (!qinf->head)
+            qinf->tail = NULL;
+          qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
+          g_queue_pop_head (q);
+          break;
+        case POP_TAIL:
+          if (qinf->tail)
+            qinf->tail = qinf->tail->prev;
+          if (!qinf->tail)
+            qinf->head = NULL;
+          qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
+          g_queue_pop_tail (q);
+          break;
+        case POP_NTH:
+          if (!g_queue_is_empty (q))
+            {
+              int n = get_random_position (q, TRUE);
+              gpointer elm = g_queue_peek_nth (q, n);
+
+              if (n == q->length - 1)
+                qinf->tail = qinf->tail->prev;
+
+              if (n == 0)
+                qinf->head = qinf->head->next;
+
+              if (n >= 0 && n < q->length)
+                qinf->length--;
+
+              g_assert (elm == g_queue_pop_nth (q, n));
+            }
+          break;
+        case PEEK_HEAD:
+          if (qinf->head)
+            g_assert (qinf->head->data == g_queue_peek_head (q));
+          else
+            g_assert (g_queue_peek_head (q) == NULL);
+          break;
+        case PEEK_TAIL:
+          if (qinf->head)
+            g_assert (qinf->tail->data == g_queue_peek_tail (q));
+          else
+            g_assert (g_queue_peek_tail (q) == NULL);
+          break;
+        case PEEK_NTH:
+          if (g_queue_is_empty (q))
+            {
+              for (j = -10; j < 10; ++j)
+                g_assert (g_queue_peek_nth (q, j) == NULL);
+            }
+          else
+            {
+              GList *list;
+              int n = get_random_position (q, TRUE);
+              if (n < 0 || n >= q->length)
+                {
+                  g_assert (g_queue_peek_nth (q, n) == NULL);
+                }
+              else
+                {
+                  list = qinf->head;
+                  for (j = 0; j < n; ++j)
+                    list = list->next;
+
+                  g_assert (list->data == g_queue_peek_nth (q, n));
+                }
+            }
+          break;
+        case INDEX:
+        case LINK_INDEX:
+          {
+            int x = g_random_int_range (0, 386538);
+            int n;
+            GList *list;
+
+            g_queue_remove_all (q, GINT_TO_POINTER (x));
+            check_integrity (q);
+            g_queue_push_tail (q, GINT_TO_POINTER (x));
+            check_integrity (q);
+            g_queue_sort (q, compare_int, NULL);
+            check_integrity (q);
+
+            n = 0;
+            for (list = q->head; list != NULL; list = list->next)
+              {
+                if (list->data == GINT_TO_POINTER (x))
+                  break;
+                n++;
+              }
+            g_assert (list);
+            g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
+                      g_queue_link_index (q, list));
+            g_assert (g_queue_link_index (q, list) == n);
+
+            qinf->head = q->head;
+            qinf->tail = q->tail;
+            qinf->length = q->length;
+          }
+          break;
+        case REMOVE:
+          if (!g_queue_is_empty (q))
+            g_queue_remove (q, qinf->tail->data);
+          if (!g_queue_is_empty (q))
+            g_queue_remove (q, qinf->head->data);
+          if (!g_queue_is_empty (q))
+            g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
+
+          qinf->head = q->head;
+          qinf->tail = q->tail;
+          qinf->length = q->length;
+          break;
+        case REMOVE_ALL:
+          if (!g_queue_is_empty (q))
+            g_queue_remove_all (q, qinf->tail->data);
+          if (!g_queue_is_empty (q))
+            g_queue_remove_all (q, qinf->head->data);
+          if (!g_queue_is_empty (q))
+            g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
+
+          qinf->head = q->head;
+          qinf->tail = q->tail;
+          qinf->length = q->length;
+          break;
+        case INSERT_BEFORE:
+          if (!g_queue_is_empty (q))
+            {
+              gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
+
+              g_queue_insert_before (q, qinf->tail, x);
+              g_queue_insert_before (q, qinf->head, x);
+              g_queue_insert_before (q, g_queue_find (q, x), x);
+            }
+          qinf->head = q->head;
+          qinf->tail = q->tail;
+          qinf->length = q->length;
+          break;
+        case INSERT_AFTER:
+          if (!g_queue_is_empty (q))
+            {
+              gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
+
+              g_queue_insert_after (q, qinf->tail, x);
+              g_queue_insert_after (q, qinf->head, x);
+              g_queue_insert_after (q, g_queue_find (q, x), x);
+            }
+          qinf->head = q->head;
+          qinf->tail = q->tail;
+          qinf->length = q->length;
+          break;
+        case INSERT_SORTED:
+          {
+            int max = find_max (q);
+            int min = find_min (q);
+
+            if (g_queue_is_empty (q))
+              {
+                max = 345;
+                min = -12;
+              }
+
+            g_queue_sort (q, compare_int, NULL);
+            check_integrity (q);
+            g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
+            check_integrity (q);
+            g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
+            g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
+            check_integrity (q);
+            g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
+            qinf->head = q->head;
+            qinf->tail = q->tail;
+            qinf->length = q->length;
+          }
+          break;
+        case PUSH_HEAD_LINK:
+          {
+            GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
+            g_queue_push_head_link (q, link);
+            if (!qinf->tail)
+              qinf->tail = link;
+            qinf->head = link;
+            qinf->length++;
+          }
+          break;
+        case PUSH_TAIL_LINK:
+          {
+            GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
+            g_queue_push_tail_link (q, link);
+            if (!qinf->head)
+              qinf->head = link;
+            qinf->tail = link;
+            qinf->length++;
+          }
+          break;
+        case PUSH_NTH_LINK:
+          {
+            GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
+            gint n = get_random_position (q, TRUE);
+            g_queue_push_nth_link (q, n, link);
+
+            if (qinf->head && qinf->head->prev)
+              qinf->head = qinf->head->prev;
+            else
+              qinf->head = q->head;
+            if (qinf->tail && qinf->tail->next)
+              qinf->tail = qinf->tail->next;
+            else
+              qinf->tail = g_list_last (qinf->head);
+            qinf->length++;
+          }
+          break;
+        case POP_HEAD_LINK:
+          if (!g_queue_is_empty (q))
+            {
+              qinf->head = qinf->head->next;
+              if (!qinf->head)
+                qinf->tail = NULL;
+              qinf->length--;
+              g_list_free (g_queue_pop_head_link (q));
+            }
+          break;
+        case POP_TAIL_LINK:
+          if (!g_queue_is_empty (q))
+            {
+              qinf->tail = qinf->tail->prev;
+              if (!qinf->tail)
+                qinf->head = NULL;
+              qinf->length--;
+              g_list_free (g_queue_pop_tail_link (q));
+            }
+          break;
+        case POP_NTH_LINK:
+          if (g_queue_is_empty (q))
+            g_assert (g_queue_pop_nth_link (q, 200) == NULL);
+          else
+            {
+              int n = get_random_position (q, FALSE);
+
+              if (n == g_queue_get_length (q) - 1)
+                qinf->tail = qinf->tail->prev;
+
+              if (n == 0)
+                qinf->head = qinf->head->next;
+
+              qinf->length--;
+
+              g_list_free (g_queue_pop_nth_link (q, n));
+            }
+          break;
+        case PEEK_HEAD_LINK:
+          if (g_queue_is_empty (q))
+            g_assert (g_queue_peek_head_link (q) == NULL);
+          else
+            g_assert (g_queue_peek_head_link (q) == qinf->head);
+          break;
+        case PEEK_TAIL_LINK:
+          if (g_queue_is_empty (q))
+            g_assert (g_queue_peek_tail_link (q) == NULL);
+          else
+            g_assert (g_queue_peek_tail_link (q) == qinf->tail);
+          break;
+        case PEEK_NTH_LINK:
+          if (g_queue_is_empty(q))
+            g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
+          else
+            {
+              gint n = get_random_position (q, FALSE);
+              GList *link;
+
+              link = q->head;
+              for (j = 0; j < n; ++j)
+                link = link->next;
+
+              g_assert (g_queue_peek_nth_link (q, n) == link);
+            }
+          break;
+        case UNLINK:
+          if (!g_queue_is_empty (q))
+            {
+              gint n = g_random_int_range (0, g_queue_get_length (q));
+              GList *link;
+
+              link = q->head;
+              for (j = 0; j < n; ++j)
+                link = link->next;
+
+              g_queue_unlink (q, link);
+              check_integrity (q);
+
+              g_list_free (link);
+
+              qinf->head = q->head;
+              qinf->tail = q->tail;
+              qinf->length--;
+            }
+          break;
+        case DELETE_LINK:
+          if (!g_queue_is_empty (q))
+            {
+              gint n = g_random_int_range (0, g_queue_get_length (q));
+              GList *link;
+
+              link = q->head;
+              for (j = 0; j < n; ++j)
+                link = link->next;
+
+              g_queue_delete_link (q, link);
+              check_integrity (q);
+
+              qinf->head = q->head;
+              qinf->tail = q->tail;
+              qinf->length--;
+            }
+          break;
+        case LAST_OP:
+        default:
+          g_assert_not_reached();
+          break;
+        }
+
+      if (qinf->head != q->head ||
+          qinf->tail != q->tail ||
+          qinf->length != q->length)
+        g_print ("op: %d\n", op);
+
+      g_assert (qinf->head == q->head);
+      g_assert (qinf->tail == q->tail);
+      g_assert (qinf->length == q->length);
+
+      for (j = 0; j < N_QUEUES; ++j)
+        check_integrity (queues[j].queue);
+    }
+
+  for (i = 0; i < N_QUEUES; ++i)
+    g_queue_free (queues[i].queue);
+}
+
+static void
+remove_item (gpointer data, gpointer q)
+{
+  GQueue *queue = q;
+
+  g_queue_remove (queue, data);
+}
+
+static void
+test_basic (void)
+{
+  GQueue *q;
+  GList *node;
+  gpointer data;
+
+  q = g_queue_new ();
+
+  g_assert (g_queue_is_empty (q));
+  g_queue_push_head (q, GINT_TO_POINTER (2));
+  check_integrity (q);
+  g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
+  check_integrity (q);
+  g_assert (!g_queue_is_empty (q));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 1);
+  g_assert (q->head == q->tail);
+  g_queue_push_head (q, GINT_TO_POINTER (1));
+  check_integrity (q);
+  g_assert (q->head->next == q->tail);
+  g_assert (q->tail->prev == q->head);
+  g_assert_cmpint (g_list_length (q->head), ==, 2);
+  check_integrity (q);
+  g_assert (q->tail->data == GINT_TO_POINTER (2));
+  g_assert (q->head->data == GINT_TO_POINTER (1));
+  check_integrity (q);
+  g_queue_push_tail (q, GINT_TO_POINTER (3));
+  g_assert_cmpint (g_list_length (q->head), ==, 3);
+  g_assert (q->head->data == GINT_TO_POINTER (1));
+  g_assert (q->head->next->data == GINT_TO_POINTER (2));
+  g_assert (q->head->next->next == q->tail);
+  g_assert (q->head->next == q->tail->prev);
+  g_assert (q->tail->data == GINT_TO_POINTER (3));
+  g_queue_push_tail (q, GINT_TO_POINTER (4));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 4);
+  g_assert (q->head->data == GINT_TO_POINTER (1));
+  g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
+  g_queue_push_tail (q, GINT_TO_POINTER (5));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 5);
+  g_assert (g_queue_is_empty (q) == FALSE);
+  check_integrity (q);
+  g_assert_cmpint (q->length, ==, 5);
+  g_assert (q->head->prev == NULL);
+  g_assert (q->head->data == GINT_TO_POINTER (1));
+  g_assert (q->head->next->data == GINT_TO_POINTER (2));
+  g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
+  g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
+  g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
+  g_assert (q->head->next->next->next->next->next == NULL);
+  g_assert (q->head->next->next->next->next == q->tail);
+  g_assert (q->tail->data == GINT_TO_POINTER (5));
+  g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
+  g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
+  g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
+  g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
+  g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
+  g_assert (q->tail->prev->prev->prev->prev == q->head);
+  g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
+  g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
+  g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 4);
+  g_assert_cmpint (q->length, ==, 4);
+  g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 3);
+  g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 2);
+  g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 1);
+  g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_assert (g_queue_pop_tail (q) == NULL);
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_assert (g_queue_pop_head (q) == NULL);
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_assert (g_queue_is_empty (q));
+  check_integrity (q);
+
+  g_queue_push_head (q, GINT_TO_POINTER (1));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 1);
+  g_assert_cmpint (q->length, ==, 1);
+  g_queue_push_head (q, GINT_TO_POINTER (2));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 2);
+  g_assert_cmpint (q->length, ==, 2);
+  g_queue_push_head (q, GINT_TO_POINTER (3));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 3);
+  g_assert_cmpint (q->length, ==, 3);
+  g_queue_push_head (q, GINT_TO_POINTER (4));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 4);
+  g_assert_cmpint (q->length, ==, 4);
+  g_queue_push_head (q, GINT_TO_POINTER (5));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 5);
+  g_assert_cmpint (q->length, ==, 5);
+  g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 4);
+  node = q->tail;
+  g_assert (node == g_queue_pop_tail_link (q));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 3);
+  data = q->head->data;
+  g_assert (data == g_queue_pop_head (q));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 2);
+  g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 1);
+  g_assert (q->head == q->tail);
+  g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_assert (g_queue_pop_head (q) == NULL);
+  check_integrity (q);
+  g_assert (g_queue_pop_head_link (q) == NULL);
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_assert (g_queue_pop_tail_link (q) == NULL);
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+
+  g_queue_reverse (q);
+  check_integrity (q);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_queue_free (q);
+}
+
+static void
+test_copy (void)
+{
+  GQueue *q, *q2;
+  gint i;
+
+  q = g_queue_new ();
+  q2 = g_queue_copy (q);
+  check_integrity (q);
+  check_integrity (q2);
+  g_assert_cmpint (g_list_length (q->head), ==, 0);
+  g_assert_cmpint (g_list_length (q2->head), ==, 0);
+  g_queue_sort (q, compare_int, NULL);
+  check_integrity (q2);
+  check_integrity (q);
+  g_queue_sort (q2, compare_int, NULL);
+  check_integrity (q2);
+  check_integrity (q);
+
+  for (i = 0; i < 200; ++i)
+    {
+      g_queue_push_nth (q, GINT_TO_POINTER (i), i);
+      g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
+      check_integrity (q);
+      check_integrity (q2);
+    }
+
+  for (i = 0; i < 200; ++i)
+    {
+      g_queue_remove (q, GINT_TO_POINTER (i));
+      check_integrity (q);
+      check_integrity (q2);
+    }
+
+  for (i = 0; i < 200; ++i)
+    {
+      GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
+
+      g_queue_push_nth_link (q, i, l);
+      check_integrity (q);
+      check_integrity (q2);
+      g_queue_reverse (q);
+      check_integrity (q);
+      check_integrity (q2);
+    }
+
+  g_queue_free (q2);
+  q2 = g_queue_copy (q);
+
+  g_queue_foreach (q2, remove_item, q2);
+  check_integrity (q2);
+  check_integrity (q);
+
+  g_queue_free (q);
+  g_queue_free (q2);
+}
+
+static void
+test_off_by_one (void)
+{
+  GQueue *q;
+  GList *node;
+
+  q = g_queue_new ();
+
+  g_queue_push_tail (q, GINT_TO_POINTER (1234));
+  check_integrity (q);
+  node = g_queue_peek_tail_link (q);
+  g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
+  node = g_queue_peek_nth_link (q, g_queue_get_length (q));
+  g_assert (node == NULL);
+  node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
+  g_assert (node->data == GINT_TO_POINTER (1234));
+  node = g_queue_pop_nth_link (q, g_queue_get_length (q));
+  g_assert (node == NULL);
+  node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
+  g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
+
+  g_queue_free (q);
+}
+
+static gint
+find_custom (gconstpointer a, gconstpointer b)
+{
+  return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
+}
+
+static void
+test_find_custom (void)
+{
+  GQueue *q;
+  GList *node;
+  q = g_queue_new ();
+
+  g_queue_push_tail (q, GINT_TO_POINTER (1234));
+  g_queue_push_tail (q, GINT_TO_POINTER (1));
+  g_queue_push_tail (q, GINT_TO_POINTER (2));
+  node = g_queue_find_custom  (q, GINT_TO_POINTER (1), find_custom);
+  g_assert (node != NULL);
+  node = g_queue_find_custom  (q, GINT_TO_POINTER (2), find_custom);
+  g_assert (node != NULL);
+  node = g_queue_find_custom  (q, GINT_TO_POINTER (3), find_custom);
+  g_assert (node == NULL);
+
+  g_queue_free (q);
+}
+
+static void
+test_static (void)
+{
+  GQueue q;
+  GQueue q2 = G_QUEUE_INIT;
+
+  g_queue_init (&q);
+
+  check_integrity (&q);
+  g_assert (g_queue_is_empty (&q));
+
+  check_integrity (&q2);
+  g_assert (g_queue_is_empty (&q2));
+}
+
+static void
+test_clear (void)
+{
+  GQueue *q;
+  q = g_queue_new ();
+
+  g_queue_push_tail (q, GINT_TO_POINTER (1234));
+  g_queue_push_tail (q, GINT_TO_POINTER (1));
+  g_queue_push_tail (q, GINT_TO_POINTER (2));
+  g_assert_cmpint (g_queue_get_length (q), ==, 3);
+
+  g_queue_clear (q);
+  check_integrity (q);
+  g_assert (g_queue_is_empty (q));
+
+  g_queue_free (q);
+}
+
+int main (int argc, char *argv[])
+{
+  guint32 seed;
+  gchar *path;
+
+  g_test_init (&argc, &argv, NULL);
+
+  g_test_add_func ("/queue/basic", test_basic);
+  g_test_add_func ("/queue/copy", test_copy);
+  g_test_add_func ("/queue/off-by-one", test_off_by_one);
+  g_test_add_func ("/queue/find-custom", test_find_custom);
+  g_test_add_func ("/queue/static", test_static);
+  g_test_add_func ("/queue/clear", test_clear);
+
+  seed = g_test_rand_int_range (0, G_MAXINT);
+  path = g_strdup_printf ("/queue/random/seed:%u", seed);
+  g_test_add_data_func (path, GUINT_TO_POINTER (seed), random_test);
+  g_free (path);
+
+  return g_test_run ();
+}
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 8437186..e07f982 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -101,7 +101,6 @@ test_programs =					\
 	module-test				\
 	onceinit				\
 	patterntest				\
-	queue-test				\
 	asyncqueue-test				\
 	qsort-test				\
 	relation-test				\
@@ -153,7 +152,6 @@ markup_escape_test_LDADD = $(progs_ldadd)
 module_test_LDADD = $(module_ldadd) $(module_test_exp)
 module_test_LDFLAGS = $(G_MODULE_LDFLAGS)
 onceinit_LDADD = $(thread_ldadd)
-queue_test_LDADD = $(progs_ldadd)
 asyncqueue_test_LDADD = $(thread_ldadd)
 qsort_test_LDADD = $(progs_ldadd)
 relation_test_LDADD = $(progs_ldadd)