[glib] Move sequence tests to the test framework
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [glib] Move sequence tests to the test framework
- Date: Sun, 20 Jun 2010 16:24:36 +0000 (UTC)
commit 09aa2e79ab9b39b92c1cc911b95b49872a417382
Author: Matthias Clasen <mclasen redhat com>
Date: Sun Jun 20 12:23:13 2010 -0400
Move sequence tests to the test framework
glib/tests/Makefile.am | 3 +
glib/tests/sequence.c | 1286 +++++++++++++++++++++++++++++++++++++++++++++++
tests/sequence-test.c | 1301 ------------------------------------------------
3 files changed, 1289 insertions(+), 1301 deletions(-)
---
diff --git a/glib/tests/Makefile.am b/glib/tests/Makefile.am
index 72ff471..f39b3ce 100644
--- a/glib/tests/Makefile.am
+++ b/glib/tests/Makefile.am
@@ -62,6 +62,9 @@ regex_LDADD = $(progs_ldadd)
TEST_PROGS += base64
base64_LDADD = $(progs_ldadd)
+TEST_PROGS += sequence
+sequence_LDADD = $(progs_ldadd)
+
if OS_UNIX
# some testing of gtester funcitonality
diff --git a/glib/tests/sequence.c b/glib/tests/sequence.c
new file mode 100644
index 0000000..f46761a
--- /dev/null
+++ b/glib/tests/sequence.c
@@ -0,0 +1,1286 @@
+#include <stdio.h>
+#include <glib.h>
+#include <stdlib.h>
+
+/* Keep this in sync with gsequence.c !!! */
+typedef struct _GSequenceNode GSequenceNode;
+
+struct _GSequence
+{
+ GSequenceNode * end_node;
+ GDestroyNotify data_destroy_notify;
+ gboolean access_prohibited;
+ GSequence * real_sequence;
+};
+
+struct _GSequenceNode
+{
+ gint n_nodes;
+ GSequenceNode * parent;
+ GSequenceNode * left;
+ GSequenceNode * right;
+ gpointer data;
+};
+
+static guint
+get_priority (GSequenceNode *node)
+{
+ guint key = GPOINTER_TO_UINT (node);
+
+ key = (key << 15) - key - 1;
+ key = key ^ (key >> 12);
+ key = key + (key << 2);
+ key = key ^ (key >> 4);
+ key = key + (key << 3) + (key << 11);
+ key = key ^ (key >> 16);
+
+ return key? key : 1;
+}
+
+static void
+check_node (GSequenceNode *node)
+{
+ if (node)
+ {
+ g_assert (node->parent != node);
+ if (node->parent)
+ g_assert (node->parent->left == node || node->parent->right == node);
+ g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));
+ if (node->left)
+ g_assert (get_priority (node) >= get_priority (node->left));
+ if (node->right)
+ g_assert (get_priority (node) >= get_priority (node->right));
+ check_node (node->left);
+ check_node (node->right);
+ }
+}
+
+void
+g_sequence_check (GSequence *seq)
+{
+ GSequenceNode *node = seq->end_node;
+
+ while (node->parent)
+ node = node->parent;
+
+ check_node (node);
+
+ while (node->right)
+ node = node->right;
+
+ g_assert (seq->end_node == node);
+ g_assert (node->data == seq);
+
+}
+
+
+enum {
+ NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,
+
+ /* Getting iters */
+ GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
+ INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
+ SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
+
+ /* dereferencing */
+ GET, SET,
+
+ /* operations on GSequenceIter * */
+ ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
+ ITER_MOVE, ITER_GET_SEQUENCE,
+
+ /* search */
+ ITER_COMPARE, RANGE_GET_MIDPOINT,
+ N_OPS
+};
+
+typedef struct SequenceInfo
+{
+ GQueue * queue;
+ GSequence * sequence;
+ int n_items;
+} SequenceInfo;
+
+typedef struct
+{
+ SequenceInfo *seq;
+ int number;
+} Item;
+
+void g_sequence_check (GSequence *sequence);
+
+static Item *
+fix_pointer (gconstpointer data)
+{
+ return (Item *)((char *)data - 1);
+}
+
+static Item *
+get_item (GSequenceIter *iter)
+{
+ return fix_pointer (g_sequence_get (iter));
+}
+
+static void
+check_integrity (SequenceInfo *info)
+{
+ GList *list;
+ GSequenceIter *iter;
+ int i;
+
+ g_sequence_check (info->sequence);
+
+#if 0
+ if (g_sequence_get_length (info->sequence) != info->n_items)
+ g_print ("%d %d\n",
+ g_sequence_get_length (info->sequence), info->n_items);
+#endif
+ g_assert (info->n_items == g_queue_get_length (info->queue));
+ g_assert (g_sequence_get_length (info->sequence) == info->n_items);
+
+ iter = g_sequence_get_begin_iter (info->sequence);
+ list = info->queue->head;
+ i = 0;
+ while (iter != g_sequence_get_end_iter (info->sequence))
+ {
+ Item *item;
+ g_assert (list->data == iter);
+ item = get_item (list->data);
+ g_assert (item->seq == info);
+
+ iter = g_sequence_iter_next (iter);
+ list = list->next;
+ i++;
+ }
+
+ g_assert (info->n_items == g_queue_get_length (info->queue));
+ g_assert (g_sequence_get_length (info->sequence) == info->n_items);
+}
+
+static gpointer
+new_item (SequenceInfo *seq)
+{
+ Item *item = g_new (Item, 1);
+ seq->n_items++;
+ item->seq = seq;
+ item->number = g_random_int ();
+
+ /* There have been bugs in the past where the GSequence would
+ * dereference the user pointers. This will make sure such
+ * behavior causes crashes
+ */
+ return ((char *)item + 1);
+}
+
+static void
+free_item (gpointer data)
+{
+ Item *item = fix_pointer (data);
+ item->seq->n_items--;
+ g_free (item);
+}
+
+static void
+seq_foreach (gpointer data,
+ gpointer user_data)
+{
+ Item *item = fix_pointer (data);
+ GList **link = user_data;
+ GSequenceIter *iter;
+
+ g_assert (*link != NULL);
+
+ iter = (*link)->data;
+
+ g_assert (get_item (iter) == item);
+
+ item->number = g_random_int();
+
+ *link = (*link)->next;
+}
+
+static gint
+compare_items (gconstpointer a,
+ gconstpointer b,
+ gpointer data)
+{
+ const Item *item_a = fix_pointer (a);
+ const Item *item_b = fix_pointer (b);
+
+ if (item_a->number < item_b->number)
+ {
+ return -1;
+ }
+ else if (item_a->number == item_b->number)
+ {
+ /* Force an arbitrary order on the items
+ * We have to do this, since g_queue_insert_sorted() and
+ * g_sequence_insert_sorted() do not agree on the exact
+ * position the item is inserted if the new item is
+ * equal to an existing one.
+ */
+ if (item_a < item_b)
+ return -1;
+ else if (item_a == item_b)
+ return 0;
+ else
+ return 1;
+ }
+ else
+ {
+ return 1;
+ }
+}
+
+static void
+check_sorted (SequenceInfo *info)
+{
+ GList *list;
+ int last;
+ GSequenceIter *last_iter;
+
+ check_integrity (info);
+
+ last = G_MININT;
+ last_iter = NULL;
+ for (list = info->queue->head; list != NULL; list = list->next)
+ {
+ GSequenceIter *iter = list->data;
+ Item *item = get_item (iter);
+
+ g_assert (item->number >= last);
+ /* Check that the ordering is the same as that of the queue,
+ * ie. that the sort is stable
+ */
+ if (last_iter)
+ g_assert (iter == g_sequence_iter_next (last_iter));
+
+ last = item->number;
+ last_iter = iter;
+ }
+}
+
+static gint
+compare_iters (gconstpointer a,
+ gconstpointer b,
+ gpointer data)
+{
+ GSequence *seq = data;
+ GSequenceIter *iter_a = (GSequenceIter *)a;
+ GSequenceIter *iter_b = (GSequenceIter *)b;
+ /* compare_items() will fix up the pointers */
+ Item *item_a = g_sequence_get (iter_a);
+ Item *item_b = g_sequence_get (iter_b);
+
+ if (seq)
+ {
+ g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
+ g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
+ }
+
+ return compare_items (item_a, item_b, data);
+}
+
+/* A version of g_queue_link_index() that treats NULL as just
+ * beyond the queue
+ */
+static int
+queue_link_index (SequenceInfo *seq, GList *link)
+{
+ if (link)
+ return g_queue_link_index (seq->queue, link);
+ else
+ return g_queue_get_length (seq->queue);
+}
+
+static void
+get_random_range (SequenceInfo *seq,
+ GSequenceIter **begin_iter,
+ GSequenceIter **end_iter,
+ GList **begin_link,
+ GList **end_link)
+{
+ int length = g_queue_get_length (seq->queue);
+ int b = g_random_int_range (0, length + 1);
+ int e = g_random_int_range (b, length + 1);
+
+ g_assert (length == g_sequence_get_length (seq->sequence));
+
+ if (begin_iter)
+ *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);
+ if (end_iter)
+ *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);
+ if (begin_link)
+ *begin_link = g_queue_peek_nth_link (seq->queue, b);
+ if (end_link)
+ *end_link = g_queue_peek_nth_link (seq->queue, e);
+ if (begin_iter && begin_link)
+ {
+ g_assert (
+ queue_link_index (seq, *begin_link) ==
+ g_sequence_iter_get_position (*begin_iter));
+ }
+ if (end_iter && end_link)
+ {
+ g_assert (
+ queue_link_index (seq, *end_link) ==
+ g_sequence_iter_get_position (*end_iter));
+ }
+}
+
+static gint
+get_random_position (SequenceInfo *seq)
+{
+ int length = g_queue_get_length (seq->queue);
+
+ g_assert (length == g_sequence_get_length (seq->sequence));
+
+ return g_random_int_range (-2, length + 5);
+}
+
+static GSequenceIter *
+get_random_iter (SequenceInfo *seq,
+ GList **link)
+{
+ GSequenceIter *iter;
+ int pos = get_random_position (seq);
+ if (link)
+ *link = g_queue_peek_nth_link (seq->queue, pos);
+ iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
+ if (link)
+ g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));
+ return iter;
+}
+
+static void
+dump_info (SequenceInfo *seq)
+{
+#if 0
+ GSequenceIter *iter;
+ GList *list;
+
+ iter = g_sequence_get_begin_iter (seq->sequence);
+ list = seq->queue->head;
+
+ while (iter != g_sequence_get_end_iter (seq->sequence))
+ {
+ Item *item = get_item (iter);
+ g_print ("%p %p %d\n", list->data, iter, item->number);
+
+ iter = g_sequence_iter_next (iter);
+ list = list->next;
+ }
+#endif
+}
+
+/* A version of g_queue_insert_before() that appends if link is NULL */
+static void
+queue_insert_before (SequenceInfo *seq, GList *link, gpointer data)
+{
+ if (link)
+ g_queue_insert_before (seq->queue, link, data);
+ else
+ g_queue_push_tail (seq->queue, data);
+}
+
+static void
+run_random_tests (gconstpointer d)
+{
+ guint32 seed = GPOINTER_TO_UINT (d);
+#define N_ITERATIONS 60000
+#define N_SEQUENCES 8
+#define N_TIMES 24
+
+ SequenceInfo sequences[N_SEQUENCES];
+ int k;
+
+#if 0
+ g_print (" seed: %u\n", seed);
+#endif
+
+ g_random_set_seed (seed);
+
+ for (k = 0; k < N_SEQUENCES; ++k)
+ {
+ sequences[k].queue = g_queue_new ();
+ sequences[k].sequence = g_sequence_new (free_item);
+ sequences[k].n_items = 0;
+ }
+
+#define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])
+
+ for (k = 0; k < N_ITERATIONS; ++k)
+ {
+ int i;
+ SequenceInfo *seq = RANDOM_SEQUENCE();
+ int op = g_random_int_range (0, N_OPS);
+
+#if 0
+ g_print ("%d on %p\n", op, seq);
+#endif
+
+ switch (op)
+ {
+ case NEW:
+ case FREE:
+ {
+ g_queue_free (seq->queue);
+ g_sequence_free (seq->sequence);
+
+ g_assert (seq->n_items == 0);
+
+ seq->queue = g_queue_new ();
+ seq->sequence = g_sequence_new (free_item);
+
+ check_integrity (seq);
+ }
+ break;
+ case GET_LENGTH:
+ {
+ int slen = g_sequence_get_length (seq->sequence);
+ int qlen = g_queue_get_length (seq->queue);
+
+ g_assert (slen == qlen);
+ }
+ break;
+ case FOREACH:
+ {
+ GList *link = seq->queue->head;
+ g_sequence_foreach (seq->sequence, seq_foreach, &link);
+ g_assert (link == NULL);
+ }
+ break;
+ case FOREACH_RANGE:
+ {
+ GSequenceIter *begin_iter, *end_iter;
+ GList *begin_link, *end_link;
+
+ get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
+
+ check_integrity (seq);
+
+ g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);
+
+ g_assert (begin_link == end_link);
+ }
+ break;
+ case SORT:
+ {
+ dump_info (seq);
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ dump_info (seq);
+ }
+ break;
+ case SORT_ITER:
+ {
+ check_integrity (seq);
+ g_sequence_sort_iter (seq->sequence,
+ (GSequenceIterCompareFunc)compare_iters, seq->sequence);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+ check_sorted (seq);
+ }
+ break;
+
+ /* Getting iters */
+ case GET_END_ITER:
+ case GET_BEGIN_ITER:
+ {
+ GSequenceIter *begin_iter;
+ GSequenceIter *end_iter;
+ GSequenceIter *penultimate_iter;
+
+ begin_iter = g_sequence_get_begin_iter (seq->sequence);
+ check_integrity (seq);
+
+ end_iter = g_sequence_get_end_iter (seq->sequence);
+ check_integrity (seq);
+
+ penultimate_iter = g_sequence_iter_prev (end_iter);
+ check_integrity (seq);
+
+ if (g_sequence_get_length (seq->sequence) > 0)
+ {
+ g_assert (seq->queue->head);
+ g_assert (seq->queue->head->data == begin_iter);
+ g_assert (seq->queue->tail);
+ g_assert (seq->queue->tail->data == penultimate_iter);
+ }
+ else
+ {
+ g_assert (penultimate_iter == end_iter);
+ g_assert (begin_iter == end_iter);
+ g_assert (penultimate_iter == begin_iter);
+ g_assert (seq->queue->head == NULL);
+ g_assert (seq->queue->tail == NULL);
+ }
+ }
+ break;
+ case GET_ITER_AT_POS:
+ {
+ int i;
+
+ g_assert (g_queue_get_length (seq->queue) == g_sequence_get_length (seq->sequence));
+
+ for (i = 0; i < 10; ++i)
+ {
+ int pos = get_random_position (seq);
+ GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
+ GList *link = g_queue_peek_nth_link (seq->queue, pos);
+ check_integrity (seq);
+ if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
+ {
+ g_assert (iter == g_sequence_get_end_iter (seq->sequence));
+ g_assert (link == NULL);
+ }
+ else
+ {
+ g_assert (link);
+ g_assert (link->data == iter);
+ }
+ }
+ }
+ break;
+ case APPEND:
+ {
+ for (i = 0; i < 10; ++i)
+ {
+ GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
+ g_queue_push_tail (seq->queue, iter);
+ }
+ }
+ break;
+ case PREPEND:
+ {
+ for (i = 0; i < 10; ++i)
+ {
+ GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
+ g_queue_push_head (seq->queue, iter);
+ }
+ }
+ break;
+ case INSERT_BEFORE:
+ {
+ for (i = 0; i < 10; ++i)
+ {
+ GList *link;
+ GSequenceIter *iter = get_random_iter (seq, &link);
+ GSequenceIter *new_iter;
+ check_integrity (seq);
+
+ new_iter = g_sequence_insert_before (iter, new_item (seq));
+
+ queue_insert_before (seq, link, new_iter);
+ }
+ }
+ break;
+ case MOVE:
+ {
+ GList *link1, *link2;
+ SequenceInfo *seq1 = RANDOM_SEQUENCE();
+ SequenceInfo *seq2 = RANDOM_SEQUENCE();
+ GSequenceIter *iter1 = get_random_iter (seq1, &link1);
+ GSequenceIter *iter2 = get_random_iter (seq2, &link2);
+
+ if (!g_sequence_iter_is_end (iter1))
+ {
+ g_sequence_move (iter1, iter2);
+
+ if (!link2)
+ g_assert (g_sequence_iter_is_end (iter2));
+
+ queue_insert_before (seq2, link2, link1->data);
+
+ g_queue_delete_link (seq1->queue, link1);
+
+ get_item (iter1)->seq = seq2;
+
+ seq1->n_items--;
+ seq2->n_items++;
+ }
+
+ check_integrity (seq);
+
+ iter1 = get_random_iter (seq, NULL);
+
+ /* Moving an iter to itself should have no effect */
+ if (!g_sequence_iter_is_end (iter1))
+ g_sequence_move (iter1, iter1);
+ }
+ break;
+ case SWAP:
+ {
+ GList *link1, *link2;
+ SequenceInfo *seq1 = RANDOM_SEQUENCE();
+ SequenceInfo *seq2 = RANDOM_SEQUENCE();
+ GSequenceIter *iter1 = get_random_iter (seq1, &link1);
+ GSequenceIter *iter2 = get_random_iter (seq2, &link2);
+
+ if (!g_sequence_iter_is_end (iter1) &&
+ !g_sequence_iter_is_end (iter2))
+ {
+ gpointer tmp;
+
+ g_sequence_swap (iter1, iter2);
+
+ get_item (iter1)->seq = seq2;
+ get_item (iter2)->seq = seq1;
+
+ tmp = link1->data;
+ link1->data = link2->data;
+ link2->data = tmp;
+ }
+ }
+ break;
+ case INSERT_SORTED:
+ {
+ int i;
+ dump_info (seq);
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ for (i = 0; i < N_TIMES; ++i)
+ {
+ GSequenceIter *iter =
+ g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
+
+ g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
+ }
+
+ check_sorted (seq);
+
+ dump_info (seq);
+ }
+ break;
+ case INSERT_SORTED_ITER:
+ {
+ int i;
+ dump_info (seq);
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ for (i = 0; i < N_TIMES; ++i)
+ {
+ GSequenceIter *iter;
+
+ iter = g_sequence_insert_sorted_iter (seq->sequence,
+ new_item (seq),
+ (GSequenceIterCompareFunc)compare_iters,
+ seq->sequence);
+
+ g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
+ }
+
+ check_sorted (seq);
+
+ dump_info (seq);
+ }
+ break;
+ case SORT_CHANGED:
+ {
+ int i;
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ for (i = 0; i < N_TIMES; ++i)
+ {
+ GList *link;
+ GSequenceIter *iter = get_random_iter (seq, &link);
+
+ if (!g_sequence_iter_is_end (iter))
+ {
+ g_sequence_set (iter, new_item (seq));
+ g_sequence_sort_changed (iter, compare_items, NULL);
+
+ g_queue_delete_link (seq->queue, link);
+ g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
+ }
+
+ check_sorted (seq);
+ }
+ }
+ break;
+ case SORT_CHANGED_ITER:
+ {
+ int i;
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ for (i = 0; i < N_TIMES; ++i)
+ {
+ GList *link;
+ GSequenceIter *iter = get_random_iter (seq, &link);
+
+ if (!g_sequence_iter_is_end (iter))
+ {
+ g_sequence_set (iter, new_item (seq));
+ g_sequence_sort_changed_iter (iter,
+ (GSequenceIterCompareFunc)compare_iters, seq->sequence);
+
+ g_queue_delete_link (seq->queue, link);
+ g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
+ }
+
+ check_sorted (seq);
+ }
+ }
+ break;
+ case REMOVE:
+ {
+ int i;
+
+ for (i = 0; i < N_TIMES; ++i)
+ {
+ GList *link;
+ GSequenceIter *iter = get_random_iter (seq, &link);
+
+ if (!g_sequence_iter_is_end (iter))
+ {
+ g_sequence_remove (iter);
+ g_queue_delete_link (seq->queue, link);
+ }
+ }
+ }
+ break;
+ case REMOVE_RANGE:
+ {
+ GSequenceIter *begin_iter, *end_iter;
+ GList *begin_link, *end_link;
+ GList *list;
+
+ get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);
+
+ g_sequence_remove_range (begin_iter, end_iter);
+
+ list = begin_link;
+ while (list != end_link)
+ {
+ GList *next = list->next;
+
+ g_queue_delete_link (seq->queue, list);
+
+ list = next;
+ }
+ }
+ break;
+ case MOVE_RANGE:
+ {
+ SequenceInfo *src = RANDOM_SEQUENCE();
+ SequenceInfo *dst = RANDOM_SEQUENCE();
+
+ GSequenceIter *begin_iter, *end_iter;
+ GList *begin_link, *end_link;
+
+ GSequenceIter *dst_iter;
+ GList *dst_link;
+
+ GList *list;
+
+ g_assert (src->queue);
+ g_assert (dst->queue);
+
+ get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
+ dst_iter = get_random_iter (dst, &dst_link);
+
+ g_sequence_move_range (dst_iter, begin_iter, end_iter);
+
+ if (dst_link == begin_link || (src == dst && dst_link == end_link))
+ {
+ check_integrity (src);
+ check_integrity (dst);
+ break;
+ }
+
+ if (queue_link_index (src, begin_link) >=
+ queue_link_index (src, end_link))
+ {
+ break;
+ }
+
+ if (src == dst &&
+ queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
+ queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
+ {
+ break;
+ }
+
+ list = begin_link;
+ while (list != end_link)
+ {
+ GList *next = list->next;
+ Item *item = get_item (list->data);
+
+ g_assert (dst->queue);
+ queue_insert_before (dst, dst_link, list->data);
+ g_queue_delete_link (src->queue, list);
+
+ g_assert (item->seq == src);
+
+ src->n_items--;
+ dst->n_items++;
+ item->seq = dst;
+
+ list = next;
+ }
+ }
+ break;
+ case SEARCH:
+ {
+ Item *item;
+ GSequenceIter *search_iter;
+ GSequenceIter *insert_iter;
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ item = new_item (seq);
+ search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);
+
+ insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
+
+ g_assert (search_iter == g_sequence_iter_next (insert_iter));
+
+ g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
+ }
+ break;
+ case SEARCH_ITER:
+ {
+ Item *item;
+ GSequenceIter *search_iter;
+ GSequenceIter *insert_iter;
+
+ g_sequence_sort (seq->sequence, compare_items, NULL);
+ g_queue_sort (seq->queue, compare_iters, NULL);
+
+ check_sorted (seq);
+
+ item = new_item (seq);
+ search_iter = g_sequence_search_iter (seq->sequence,
+ item,
+ (GSequenceIterCompareFunc)compare_iters, seq->sequence);
+
+ insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
+
+ g_assert (search_iter == g_sequence_iter_next (insert_iter));
+
+ g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
+ }
+ break;
+
+ /* dereferencing */
+ case GET:
+ case SET:
+ {
+ GSequenceIter *iter;
+ GList *link;
+
+ iter = get_random_iter (seq, &link);
+
+ if (!g_sequence_iter_is_end (iter))
+ {
+ Item *item;
+ int i;
+
+ check_integrity (seq);
+
+ /* Test basic functionality */
+ item = new_item (seq);
+ g_sequence_set (iter, item);
+ g_assert (g_sequence_get (iter) == item);
+
+ /* Make sure that existing items are freed */
+ for (i = 0; i < N_TIMES; ++i)
+ g_sequence_set (iter, new_item (seq));
+
+ check_integrity (seq);
+
+ g_sequence_set (iter, new_item (seq));
+ }
+ }
+ break;
+
+ /* operations on GSequenceIter * */
+ case ITER_IS_BEGIN:
+ {
+ GSequenceIter *iter;
+
+ iter = g_sequence_get_iter_at_pos (seq->sequence, 0);
+
+ g_assert (g_sequence_iter_is_begin (iter));
+
+ check_integrity (seq);
+
+ if (g_sequence_get_length (seq->sequence) > 0)
+ {
+ g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
+ }
+ else
+ {
+ g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
+ }
+
+ g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
+ }
+ break;
+ case ITER_IS_END:
+ {
+ GSequenceIter *iter;
+ int len = g_sequence_get_length (seq->sequence);
+
+ iter = g_sequence_get_iter_at_pos (seq->sequence, len);
+
+ g_assert (g_sequence_iter_is_end (iter));
+
+ if (len > 0)
+ {
+ g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
+ }
+ else
+ {
+ g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
+ }
+
+ g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
+ }
+ break;
+ case ITER_NEXT:
+ {
+ GSequenceIter *iter1, *iter2, *iter3, *end;
+
+ iter1 = g_sequence_append (seq->sequence, new_item (seq));
+ iter2 = g_sequence_append (seq->sequence, new_item (seq));
+ iter3 = g_sequence_append (seq->sequence, new_item (seq));
+
+ end = g_sequence_get_end_iter (seq->sequence);
+
+ g_assert (g_sequence_iter_next (iter1) == iter2);
+ g_assert (g_sequence_iter_next (iter2) == iter3);
+ g_assert (g_sequence_iter_next (iter3) == end);
+ g_assert (g_sequence_iter_next (end) == end);
+
+ g_queue_push_tail (seq->queue, iter1);
+ g_queue_push_tail (seq->queue, iter2);
+ g_queue_push_tail (seq->queue, iter3);
+ }
+ break;
+ case ITER_PREV:
+ {
+ GSequenceIter *iter1, *iter2, *iter3, *begin;
+
+ iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
+ iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
+ iter3 = g_sequence_prepend (seq->sequence, new_item (seq));
+
+ begin = g_sequence_get_begin_iter (seq->sequence);
+
+ g_assert (g_sequence_iter_prev (iter1) == iter2);
+ g_assert (g_sequence_iter_prev (iter2) == iter3);
+ g_assert (iter3 == begin);
+ g_assert (g_sequence_iter_prev (iter3) == begin);
+ g_assert (g_sequence_iter_prev (begin) == begin);
+
+ g_queue_push_head (seq->queue, iter1);
+ g_queue_push_head (seq->queue, iter2);
+ g_queue_push_head (seq->queue, iter3);
+ }
+ break;
+ case ITER_GET_POSITION:
+ {
+ GList *link;
+ GSequenceIter *iter = get_random_iter (seq, &link);
+
+ g_assert (g_sequence_iter_get_position (iter) ==
+ queue_link_index (seq, link));
+ }
+ break;
+ case ITER_MOVE:
+ {
+ int len = g_sequence_get_length (seq->sequence);
+ GSequenceIter *iter;
+ int pos;
+
+ iter = get_random_iter (seq, NULL);
+ pos = g_sequence_iter_get_position (iter);
+ iter = g_sequence_iter_move (iter, len - pos);
+ g_assert (g_sequence_iter_is_end (iter));
+
+
+ iter = get_random_iter (seq, NULL);
+ pos = g_sequence_iter_get_position (iter);
+ while (pos < len)
+ {
+ g_assert (!g_sequence_iter_is_end (iter));
+ pos++;
+ iter = g_sequence_iter_move (iter, 1);
+ }
+ g_assert (g_sequence_iter_is_end (iter));
+ }
+ break;
+ case ITER_GET_SEQUENCE:
+ {
+ GSequenceIter *iter = get_random_iter (seq, NULL);
+
+ g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
+ }
+ break;
+
+ /* search */
+ case ITER_COMPARE:
+ {
+ GList *link1, *link2;
+ GSequenceIter *iter1 = get_random_iter (seq, &link1);
+ GSequenceIter *iter2 = get_random_iter (seq, &link2);
+
+ int cmp = g_sequence_iter_compare (iter1, iter2);
+ int pos1 = queue_link_index (seq, link1);
+ int pos2 = queue_link_index (seq, link2);
+
+ if (cmp == 0)
+ {
+ g_assert (pos1 == pos2);
+ }
+ else if (cmp < 0)
+ {
+ g_assert (pos1 < pos2);
+ }
+ else
+ {
+ g_assert (pos1 > pos2);
+ }
+ }
+ break;
+ case RANGE_GET_MIDPOINT:
+ {
+ GSequenceIter *iter1 = get_random_iter (seq, NULL);
+ GSequenceIter *iter2 = get_random_iter (seq, NULL);
+ GSequenceIter *iter3;
+ int cmp;
+
+ cmp = g_sequence_iter_compare (iter1, iter2);
+
+ if (cmp > 0)
+ {
+ GSequenceIter *tmp;
+
+ tmp = iter1;
+ iter1 = iter2;
+ iter2 = tmp;
+ }
+
+ iter3 = g_sequence_range_get_midpoint (iter1, iter2);
+
+ if (cmp == 0)
+ {
+ g_assert (iter3 == iter1);
+ g_assert (iter3 == iter2);
+ }
+
+ g_assert (g_sequence_iter_get_position (iter3) >=
+ g_sequence_iter_get_position (iter1));
+ g_assert (g_sequence_iter_get_position (iter2) >=
+ g_sequence_iter_get_position (iter3));
+ }
+ break;
+
+ }
+
+ check_integrity (seq);
+ }
+}
+
+/* Random seeds known to have failed at one point
+ */
+static gulong seeds[] =
+ {
+ 825541564u,
+ 801678400u,
+ 1477639090u,
+ 3369132895u,
+ 1192944867u,
+ 770458294u,
+ 1099575817u,
+ 590523467u,
+ 3583571454u,
+ 579241222u
+ };
+
+/* Single, stand-alone tests */
+
+static void
+test_out_of_range_jump (void)
+{
+ GSequence *seq = g_sequence_new (NULL);
+ GSequenceIter *iter = g_sequence_get_begin_iter (seq);
+
+ g_sequence_iter_move (iter, 5);
+
+ g_assert (g_sequence_iter_is_begin (iter));
+ g_assert (g_sequence_iter_is_end (iter));
+}
+
+static int
+compare (gconstpointer a, gconstpointer b, gpointer userdata)
+{
+ int ai, bi;
+
+ ai = GPOINTER_TO_INT (a);
+ bi = GPOINTER_TO_INT (b);
+
+ if (ai < bi)
+ return -1;
+ else if (ai > bi)
+ return 1;
+ else
+ return 0;
+}
+
+static int
+compare_iter (GSequenceIter *a,
+ GSequenceIter *b,
+ gpointer data)
+{
+ return compare (g_sequence_get (a),
+ g_sequence_get (b),
+ data);
+}
+
+static void
+test_insert_sorted_non_pointer (void)
+{
+ int i;
+
+ for (i = 0; i < 10; i++)
+ {
+ GSequence *seq = g_sequence_new (NULL);
+ int j;
+
+ for (j = 0; j < 10000; j++)
+ {
+ g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
+ compare, NULL);
+
+ g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
+ compare_iter, NULL);
+ }
+
+ g_sequence_check (seq);
+
+ g_sequence_free (seq);
+ }
+}
+
+static void
+test_stable_sort (void)
+{
+ int i;
+ GSequence *seq = g_sequence_new (NULL);
+
+#define N_ITEMS 1000
+
+ GSequenceIter *iters[N_ITEMS];
+ GSequenceIter *iter;
+
+ for (i = 0; i < N_ITEMS; ++i)
+ {
+ iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
+ g_sequence_check (seq);
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ }
+
+ i = 0;
+ iter = g_sequence_get_begin_iter (seq);
+ g_assert (g_sequence_iter_get_sequence (iter) == seq);
+ g_sequence_check (seq);
+ while (!g_sequence_iter_is_end (iter))
+ {
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ g_assert (iters[i++] == iter);
+
+ iter = g_sequence_iter_next (iter);
+ g_sequence_check (seq);
+ }
+
+ g_sequence_sort (seq, compare, NULL);
+
+ i = 0;
+ iter = g_sequence_get_begin_iter (seq);
+ while (!g_sequence_iter_is_end (iter))
+ {
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ g_assert (iters[i] == iter);
+
+ iter = g_sequence_iter_next (iter);
+ g_sequence_check (seq);
+
+ i++;
+ }
+
+ for (i = N_ITEMS - 1; i >= 0; --i)
+ {
+ g_sequence_check (seq);
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ g_assert (g_sequence_get_end_iter (seq) != iters[i]);
+ g_sequence_sort_changed (iters[i], compare, NULL);
+ }
+
+ i = 0;
+ iter = g_sequence_get_begin_iter (seq);
+ while (!g_sequence_iter_is_end (iter))
+ {
+ g_assert (iters[i++] == iter);
+
+ iter = g_sequence_iter_next (iter);
+ g_sequence_check (seq);
+ }
+}
+
+int
+main (int argc,
+ char **argv)
+{
+ gint i;
+ guint32 seed;
+ gchar *path;
+
+ g_test_init (&argc, &argv, NULL);
+
+ /* Standalone tests */
+ g_test_add_func ("/sequence/out-of-range-jump", test_out_of_range_jump);
+ g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
+ g_test_add_func ("/sequence/stable-sort", test_stable_sort);
+
+ /* Regression tests */
+ for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
+ {
+ path = g_strdup_printf ("/sequence/random/seed:%lu", seeds[i]);
+ g_test_add_data_func (path, GUINT_TO_POINTER (seeds[i]), run_random_tests);
+ g_free (path);
+ }
+
+ /* New random seed */
+ seed = g_test_rand_int_range (0, G_MAXINT);
+ path = g_strdup_printf ("/sequence/random/seed:%u", seed);
+ g_test_add_data_func (path, GUINT_TO_POINTER (seed), run_random_tests);
+ g_free (path);
+
+ return g_test_run ();
+}
+
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
