1674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#include <stdio.h> 2674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#include <glib.h> 3674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#include <stdlib.h> 4674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 545b2988d051ea396a941883a124880329516c7fbMatthias Clasen/* Keep this in sync with gsequence.c !!! */ 645b2988d051ea396a941883a124880329516c7fbMatthias Clasentypedef struct _GSequenceNode GSequenceNode; 745b2988d051ea396a941883a124880329516c7fbMatthias Clasen 845b2988d051ea396a941883a124880329516c7fbMatthias Clasenstruct _GSequence 945b2988d051ea396a941883a124880329516c7fbMatthias Clasen{ 1045b2988d051ea396a941883a124880329516c7fbMatthias Clasen GSequenceNode * end_node; 1145b2988d051ea396a941883a124880329516c7fbMatthias Clasen GDestroyNotify data_destroy_notify; 1245b2988d051ea396a941883a124880329516c7fbMatthias Clasen gboolean access_prohibited; 1345b2988d051ea396a941883a124880329516c7fbMatthias Clasen GSequence * real_sequence; 1445b2988d051ea396a941883a124880329516c7fbMatthias Clasen}; 1545b2988d051ea396a941883a124880329516c7fbMatthias Clasen 1645b2988d051ea396a941883a124880329516c7fbMatthias Clasenstruct _GSequenceNode 1745b2988d051ea396a941883a124880329516c7fbMatthias Clasen{ 1845b2988d051ea396a941883a124880329516c7fbMatthias Clasen gint n_nodes; 1945b2988d051ea396a941883a124880329516c7fbMatthias Clasen GSequenceNode * parent; 2045b2988d051ea396a941883a124880329516c7fbMatthias Clasen GSequenceNode * left; 2145b2988d051ea396a941883a124880329516c7fbMatthias Clasen GSequenceNode * right; 2245b2988d051ea396a941883a124880329516c7fbMatthias Clasen gpointer data; 2345b2988d051ea396a941883a124880329516c7fbMatthias Clasen}; 2445b2988d051ea396a941883a124880329516c7fbMatthias Clasen 2545b2988d051ea396a941883a124880329516c7fbMatthias Clasenstatic guint 2645b2988d051ea396a941883a124880329516c7fbMatthias Clasenget_priority (GSequenceNode *node) 2745b2988d051ea396a941883a124880329516c7fbMatthias Clasen{ 2845b2988d051ea396a941883a124880329516c7fbMatthias Clasen guint key = GPOINTER_TO_UINT (node); 2945b2988d051ea396a941883a124880329516c7fbMatthias Clasen 3045b2988d051ea396a941883a124880329516c7fbMatthias Clasen key = (key << 15) - key - 1; 3145b2988d051ea396a941883a124880329516c7fbMatthias Clasen key = key ^ (key >> 12); 3245b2988d051ea396a941883a124880329516c7fbMatthias Clasen key = key + (key << 2); 3345b2988d051ea396a941883a124880329516c7fbMatthias Clasen key = key ^ (key >> 4); 3445b2988d051ea396a941883a124880329516c7fbMatthias Clasen key = key + (key << 3) + (key << 11); 3545b2988d051ea396a941883a124880329516c7fbMatthias Clasen key = key ^ (key >> 16); 3645b2988d051ea396a941883a124880329516c7fbMatthias Clasen 3745b2988d051ea396a941883a124880329516c7fbMatthias Clasen return key? key : 1; 3845b2988d051ea396a941883a124880329516c7fbMatthias Clasen} 3945b2988d051ea396a941883a124880329516c7fbMatthias Clasen 4045b2988d051ea396a941883a124880329516c7fbMatthias Clasenstatic void 4145b2988d051ea396a941883a124880329516c7fbMatthias Clasencheck_node (GSequenceNode *node) 4245b2988d051ea396a941883a124880329516c7fbMatthias Clasen{ 4345b2988d051ea396a941883a124880329516c7fbMatthias Clasen if (node) 4445b2988d051ea396a941883a124880329516c7fbMatthias Clasen { 4545b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (node->parent != node); 4645b2988d051ea396a941883a124880329516c7fbMatthias Clasen if (node->parent) 4745b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (node->parent->left == node || node->parent->right == node); 4845b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0)); 4945b2988d051ea396a941883a124880329516c7fbMatthias Clasen if (node->left) 5045b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (get_priority (node) >= get_priority (node->left)); 5145b2988d051ea396a941883a124880329516c7fbMatthias Clasen if (node->right) 5245b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (get_priority (node) >= get_priority (node->right)); 5345b2988d051ea396a941883a124880329516c7fbMatthias Clasen check_node (node->left); 5445b2988d051ea396a941883a124880329516c7fbMatthias Clasen check_node (node->right); 5545b2988d051ea396a941883a124880329516c7fbMatthias Clasen } 5645b2988d051ea396a941883a124880329516c7fbMatthias Clasen} 5745b2988d051ea396a941883a124880329516c7fbMatthias Clasen 5845b2988d051ea396a941883a124880329516c7fbMatthias Clasenvoid 5945b2988d051ea396a941883a124880329516c7fbMatthias Claseng_sequence_check (GSequence *seq) 6045b2988d051ea396a941883a124880329516c7fbMatthias Clasen{ 6145b2988d051ea396a941883a124880329516c7fbMatthias Clasen GSequenceNode *node = seq->end_node; 6245b2988d051ea396a941883a124880329516c7fbMatthias Clasen 6345b2988d051ea396a941883a124880329516c7fbMatthias Clasen while (node->parent) 6445b2988d051ea396a941883a124880329516c7fbMatthias Clasen node = node->parent; 6545b2988d051ea396a941883a124880329516c7fbMatthias Clasen 6645b2988d051ea396a941883a124880329516c7fbMatthias Clasen check_node (node); 6745b2988d051ea396a941883a124880329516c7fbMatthias Clasen 6845b2988d051ea396a941883a124880329516c7fbMatthias Clasen while (node->right) 6945b2988d051ea396a941883a124880329516c7fbMatthias Clasen node = node->right; 7045b2988d051ea396a941883a124880329516c7fbMatthias Clasen 7145b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (seq->end_node == node); 7245b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_assert (node->data == seq); 7345b2988d051ea396a941883a124880329516c7fbMatthias Clasen 7445b2988d051ea396a941883a124880329516c7fbMatthias Clasen} 7545b2988d051ea396a941883a124880329516c7fbMatthias Clasen 7645b2988d051ea396a941883a124880329516c7fbMatthias Clasen 77f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmannenum { 78f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER, 79f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 80f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann /* Getting iters */ 81f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND, 82f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED, 83f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER, 84f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 85f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann /* dereferencing */ 86f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GET, SET, 87f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 88f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann /* operations on GSequenceIter * */ 89f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION, 90f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann ITER_MOVE, ITER_GET_SEQUENCE, 91f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 92f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann /* search */ 93f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann ITER_COMPARE, RANGE_GET_MIDPOINT, 94f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann N_OPS 95f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann}; 96674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 97674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanntypedef struct SequenceInfo 98674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 99674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GQueue * queue; 100674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequence * sequence; 101674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int n_items; 102674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} SequenceInfo; 103674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1045fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmanntypedef struct 1055fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann{ 1065fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann SequenceInfo *seq; 1075fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann int number; 1085fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann} Item; 1095fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann 11045b2988d051ea396a941883a124880329516c7fbMatthias Clasenvoid g_sequence_check (GSequence *sequence); 111674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1125fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmannstatic Item * 1135fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmannfix_pointer (gconstpointer data) 1145fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann{ 1155fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return (Item *)((char *)data - 1); 1165fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann} 1175fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann 1185fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmannstatic Item * 1195fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmannget_item (GSequenceIter *iter) 1205fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann{ 1215fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return fix_pointer (g_sequence_get (iter)); 1225fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann} 1235fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann 124674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 125674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanncheck_integrity (SequenceInfo *info) 126674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 127674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *list; 128674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 1295fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann int i; 130674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 13145b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (info->sequence); 132674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 133674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (g_sequence_get_length (info->sequence) != info->n_items) 134674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_print ("%d %d\n", 135674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_get_length (info->sequence), info->n_items); 136674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (info->n_items == g_queue_get_length (info->queue)); 137674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_get_length (info->sequence) == info->n_items); 1385fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann 139674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_begin_iter (info->sequence); 140674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = info->queue->head; 1415fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann i = 0; 142674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (iter != g_sequence_get_end_iter (info->sequence)) 143674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 144f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann Item *item; 145674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (list->data == iter); 146f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann item = get_item (list->data); 147f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (item->seq == info); 148674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 149674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_next (iter); 150674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = list->next; 1515fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann i++; 152674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 153674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 154674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (info->n_items == g_queue_get_length (info->queue)); 155674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_get_length (info->sequence) == info->n_items); 156674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 157674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 158674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic gpointer 159674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannnew_item (SequenceInfo *seq) 160674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 161674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item = g_new (Item, 1); 162674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann seq->n_items++; 163674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item->seq = seq; 164674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item->number = g_random_int (); 165674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 166674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* There have been bugs in the past where the GSequence would 167674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann * dereference the user pointers. This will make sure such 168674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann * behavior causes crashes 169674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann */ 170674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return ((char *)item + 1); 171674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 172674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 173674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 174674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannfree_item (gpointer data) 175674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 176674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item = fix_pointer (data); 177674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item->seq->n_items--; 178674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_free (item); 179674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 180674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 181674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 182674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannseq_foreach (gpointer data, 183674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann gpointer user_data) 184674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 185674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item = fix_pointer (data); 186674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList **link = user_data; 187674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 188674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 189674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (*link != NULL); 190674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 191674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = (*link)->data; 192674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 193674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (get_item (iter) == item); 194674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 195674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item->number = g_random_int(); 196674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 197674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann *link = (*link)->next; 198674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 199674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 200674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic gint 201674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanncompare_items (gconstpointer a, 202674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann gconstpointer b, 203674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann gpointer data) 204674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 205674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann const Item *item_a = fix_pointer (a); 206674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann const Item *item_b = fix_pointer (b); 207576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann 208674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (item_a->number < item_b->number) 2095fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann { 2105fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return -1; 2115fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann } 212674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else if (item_a->number == item_b->number) 2135fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann { 2145fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann /* Force an arbitrary order on the items 2155fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann * We have to do this, since g_queue_insert_sorted() and 2165fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann * g_sequence_insert_sorted() do not agree on the exact 2175fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann * position the item is inserted if the new item is 2185fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann * equal to an existing one. 2195fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann */ 2205fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann if (item_a < item_b) 2215fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return -1; 2225fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann else if (item_a == item_b) 2235fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return 0; 2245fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann else 2255fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return 1; 2265fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann } 227674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 2285fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann { 2295fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann return 1; 2305fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann } 231674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 232674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 233674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 234674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanncheck_sorted (SequenceInfo *info) 235674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 236674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *list; 237674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int last; 238674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *last_iter; 239674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 240674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (info); 241674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 242674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann last = G_MININT; 243674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann last_iter = NULL; 244674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (list = info->queue->head; list != NULL; list = list->next) 245674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 246674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = list->data; 247674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item = get_item (iter); 248674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 249674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (item->number >= last); 250674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Check that the ordering is the same as that of the queue, 251674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann * ie. that the sort is stable 252674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann */ 253674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (last_iter) 254674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iter == g_sequence_iter_next (last_iter)); 255674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 256674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann last = item->number; 257674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann last_iter = iter; 258674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 259674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 260674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 261674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic gint 262674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanncompare_iters (gconstpointer a, 263674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann gconstpointer b, 264674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann gpointer data) 265674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 266576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann GSequence *seq = data; 267674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter_a = (GSequenceIter *)a; 268674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter_b = (GSequenceIter *)b; 269674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* compare_items() will fix up the pointers */ 270674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item_a = g_sequence_get (iter_a); 271674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item_b = g_sequence_get (iter_b); 272674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 273576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann if (seq) 274576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann { 275576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_assert (g_sequence_iter_get_sequence (iter_a) == seq); 276576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_assert (g_sequence_iter_get_sequence (iter_b) == seq); 277576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann } 278576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann 279674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return compare_items (item_a, item_b, data); 280674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 281674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 282674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann/* A version of g_queue_link_index() that treats NULL as just 283674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann * beyond the queue 284674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann */ 285674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic int 286674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannqueue_link_index (SequenceInfo *seq, GList *link) 287674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 288674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (link) 289674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return g_queue_link_index (seq->queue, link); 290674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 291674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return g_queue_get_length (seq->queue); 292674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 293674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 294674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 295674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannget_random_range (SequenceInfo *seq, 296674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter **begin_iter, 297674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter **end_iter, 298674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList **begin_link, 299674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList **end_link) 300674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 301674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int length = g_queue_get_length (seq->queue); 302674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int b = g_random_int_range (0, length + 1); 303674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int e = g_random_int_range (b, length + 1); 304674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 305674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (length == g_sequence_get_length (seq->sequence)); 306674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 307674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (begin_iter) 308674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b); 309674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (end_iter) 310674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e); 311674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (begin_link) 312674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann *begin_link = g_queue_peek_nth_link (seq->queue, b); 313674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (end_link) 314674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann *end_link = g_queue_peek_nth_link (seq->queue, e); 315674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (begin_iter && begin_link) 316674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 317674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert ( 318674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_link_index (seq, *begin_link) == 319674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_iter_get_position (*begin_iter)); 320674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 321674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (end_iter && end_link) 322674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 323674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert ( 324674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_link_index (seq, *end_link) == 325674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_iter_get_position (*end_iter)); 326674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 327674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 328674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 329674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic gint 330674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannget_random_position (SequenceInfo *seq) 331674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 332674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int length = g_queue_get_length (seq->queue); 333674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 334674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (length == g_sequence_get_length (seq->sequence)); 335674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 336674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return g_random_int_range (-2, length + 5); 337674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 338674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 339674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic GSequenceIter * 340674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannget_random_iter (SequenceInfo *seq, 341674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList **link) 342674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 343674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 344674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int pos = get_random_position (seq); 345674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (link) 346674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann *link = g_queue_peek_nth_link (seq->queue, pos); 347674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_iter_at_pos (seq->sequence, pos); 348674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (link) 349674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter)); 350674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return iter; 351674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 352674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 353674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 354674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanndump_info (SequenceInfo *seq) 355674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 356674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#if 0 357674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 358674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *list; 359674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 360674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_begin_iter (seq->sequence); 361674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = seq->queue->head; 362674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 363674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (iter != g_sequence_get_end_iter (seq->sequence)) 364674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 365674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item = get_item (iter); 366674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_print ("%p %p %d\n", list->data, iter, item->number); 367674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 368674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_next (iter); 369674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = list->next; 370674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 371674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#endif 372674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 373674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 374674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann/* A version of g_queue_insert_before() that appends if link is NULL */ 375674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 376674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannqueue_insert_before (SequenceInfo *seq, GList *link, gpointer data) 377674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 378674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (link) 379674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_before (seq->queue, link, data); 380674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 381674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_tail (seq->queue, data); 382674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 383674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 384674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 385674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannrun_random_tests (guint32 seed) 386674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 387674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#define N_ITERATIONS 60000 388674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#define N_SEQUENCES 8 389f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann#define N_TIMES 24 390f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 391674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann SequenceInfo sequences[N_SEQUENCES]; 392674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int k; 393674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 394674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_print (" seed: %u\n", seed); 395674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 396674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_random_set_seed (seed); 397674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 398674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (k = 0; k < N_SEQUENCES; ++k) 399674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 400674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann sequences[k].queue = g_queue_new (); 401674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann sequences[k].sequence = g_sequence_new (free_item); 402674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann sequences[k].n_items = 0; 403674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 404674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 405674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)]) 406674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 407674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (k = 0; k < N_ITERATIONS; ++k) 408674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 409674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 410674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann SequenceInfo *seq = RANDOM_SEQUENCE(); 411674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int op = g_random_int_range (0, N_OPS); 4125fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann 413674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#if 0 4145fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann g_print ("%d on %p\n", op, seq); 415674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#endif 416674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 417674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann switch (op) 418674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 419674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case NEW: 420674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case FREE: 421674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 422674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_free (seq->queue); 423674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_free (seq->sequence); 424674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 425674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->n_items == 0); 426674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 427674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann seq->queue = g_queue_new (); 428674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann seq->sequence = g_sequence_new (free_item); 429674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 430674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 431674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 432674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 433674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case GET_LENGTH: 434674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 435674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int slen = g_sequence_get_length (seq->sequence); 436674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int qlen = g_queue_get_length (seq->queue); 437674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 438674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (slen == qlen); 439674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 440674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 441674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case FOREACH: 442674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 443674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link = seq->queue->head; 444674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_foreach (seq->sequence, seq_foreach, &link); 445674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (link == NULL); 446674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 447674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 448674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case FOREACH_RANGE: 449674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 450674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *begin_iter, *end_iter; 451674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *begin_link, *end_link; 452674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 453674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link); 454674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 455674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 456674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 457674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link); 458674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 459674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (begin_link == end_link); 460674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 461674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 462674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SORT: 463674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 464674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dump_info (seq); 465674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 466674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 467674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 468674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 469674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 470674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 471674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dump_info (seq); 472674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 473674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 474674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SORT_ITER: 475674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 4765fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann check_integrity (seq); 477674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort_iter (seq->sequence, 478576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann (GSequenceIterCompareFunc)compare_iters, seq->sequence); 479674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 480674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 481674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 482674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 483674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 484674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Getting iters */ 485674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case GET_END_ITER: 486674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case GET_BEGIN_ITER: 487674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 488674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *begin_iter; 489674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *end_iter; 490674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *penultimate_iter; 491674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 492674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann begin_iter = g_sequence_get_begin_iter (seq->sequence); 493674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 494674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 495674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann end_iter = g_sequence_get_end_iter (seq->sequence); 496674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 497674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 498674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann penultimate_iter = g_sequence_iter_prev (end_iter); 499674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 500674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 501674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (g_sequence_get_length (seq->sequence) > 0) 502674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 503674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->queue->head); 504674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->queue->head->data == begin_iter); 505674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->queue->tail); 506674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->queue->tail->data == penultimate_iter); 507674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 508674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 509674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 510674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (penultimate_iter == end_iter); 511674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (begin_iter == end_iter); 512674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (penultimate_iter == begin_iter); 513674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->queue->head == NULL); 514674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (seq->queue->tail == NULL); 515674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 516674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 517674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 518674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case GET_ITER_AT_POS: 519674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 520674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 521674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 522674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_queue_get_length (seq->queue) == g_sequence_get_length (seq->sequence)); 523674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 524674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < 10; ++i) 525674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 526674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int pos = get_random_position (seq); 527674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos); 528674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link = g_queue_peek_nth_link (seq->queue, pos); 529674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 530674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (pos >= g_sequence_get_length (seq->sequence) || pos < 0) 531674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 532674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iter == g_sequence_get_end_iter (seq->sequence)); 533674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (link == NULL); 534674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 535674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 536674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 537674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (link); 538674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (link->data == iter); 539674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 540674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 541674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 542674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 543674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case APPEND: 544674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 545674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < 10; ++i) 546674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 547674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq)); 548674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_tail (seq->queue, iter); 549674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 550674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 551674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 552674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case PREPEND: 553674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 554674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < 10; ++i) 555674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 556674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq)); 557674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_head (seq->queue, iter); 558674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 559674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 560674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 561674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case INSERT_BEFORE: 562674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 563674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < 10; ++i) 564674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 565674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link; 566674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = get_random_iter (seq, &link); 567674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *new_iter; 568674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 569674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 570674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann new_iter = g_sequence_insert_before (iter, new_item (seq)); 571674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 572674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_insert_before (seq, link, new_iter); 573674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 574674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 575674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 576674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case MOVE: 577674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 578674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link1, *link2; 579f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann SequenceInfo *seq1 = RANDOM_SEQUENCE(); 580f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann SequenceInfo *seq2 = RANDOM_SEQUENCE(); 581f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GSequenceIter *iter1 = get_random_iter (seq1, &link1); 582f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GSequenceIter *iter2 = get_random_iter (seq2, &link2); 583674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 584674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!g_sequence_iter_is_end (iter1)) 585674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 586674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_move (iter1, iter2); 587674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 588674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!link2) 589674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_end (iter2)); 590674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 591f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann queue_insert_before (seq2, link2, link1->data); 592674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 593f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_queue_delete_link (seq1->queue, link1); 594f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 595f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann get_item (iter1)->seq = seq2; 596f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 597f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann seq1->n_items--; 598f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann seq2->n_items++; 599674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 600674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 601674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 602674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 603674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter1 = get_random_iter (seq, NULL); 604674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 605674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Moving an iter to itself should have no effect */ 606674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!g_sequence_iter_is_end (iter1)) 607674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_move (iter1, iter1); 608674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 609674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 610f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann case SWAP: 611f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann { 612f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GList *link1, *link2; 613f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann SequenceInfo *seq1 = RANDOM_SEQUENCE(); 614f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann SequenceInfo *seq2 = RANDOM_SEQUENCE(); 615f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GSequenceIter *iter1 = get_random_iter (seq1, &link1); 616f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann GSequenceIter *iter2 = get_random_iter (seq2, &link2); 617f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 618f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann if (!g_sequence_iter_is_end (iter1) && 619f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann !g_sequence_iter_is_end (iter2)) 620f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann { 621f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann gpointer tmp; 622f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 623f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_sequence_swap (iter1, iter2); 624f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 625f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann get_item (iter1)->seq = seq2; 626f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann get_item (iter2)->seq = seq1; 627f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 628f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann tmp = link1->data; 629f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann link1->data = link2->data; 630f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann link2->data = tmp; 631f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann } 632f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann } 633f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann break; 634674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case INSERT_SORTED: 635674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 636674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 637674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dump_info (seq); 638674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 639674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 640674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 641674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 642674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 643674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 644f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann for (i = 0; i < N_TIMES; ++i) 645674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 646674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = 647840d9bab2624105e8f18c08b41e8f4b86fc1345eSoren Sandmann g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL); 648674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 649674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL); 650674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 651674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 652674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 653674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 654674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dump_info (seq); 655674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 656674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 657674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case INSERT_SORTED_ITER: 658674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 659674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 660674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dump_info (seq); 661674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 662674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 663674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 664674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 665674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 666674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 667f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann for (i = 0; i < N_TIMES; ++i) 668674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 669674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 670674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 671674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_insert_sorted_iter (seq->sequence, 672674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann new_item (seq), 673674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann (GSequenceIterCompareFunc)compare_iters, 674576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann seq->sequence); 675674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 676674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL); 677674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 678674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 679674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 680674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 681674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dump_info (seq); 682674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 683674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 684674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SORT_CHANGED: 685674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 686674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 687674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 688674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 689674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 690674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 691674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 692674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 693f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann for (i = 0; i < N_TIMES; ++i) 694674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 695674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link; 696674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = get_random_iter (seq, &link); 697674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 698674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!g_sequence_iter_is_end (iter)) 699674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 700674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_set (iter, new_item (seq)); 701674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort_changed (iter, compare_items, NULL); 702674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 703674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_delete_link (seq->queue, link); 704674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL); 705674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 706674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 707674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 708674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 709674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 710674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 711674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SORT_CHANGED_ITER: 712674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 713674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 714674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 715674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 716674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 717674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 718674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 719674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 720f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann for (i = 0; i < N_TIMES; ++i) 721674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 722674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link; 723674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = get_random_iter (seq, &link); 724674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 725674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!g_sequence_iter_is_end (iter)) 726674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 727674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_set (iter, new_item (seq)); 728674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort_changed_iter (iter, 729576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann (GSequenceIterCompareFunc)compare_iters, seq->sequence); 730674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 731674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_delete_link (seq->queue, link); 732674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL); 733674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 734674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 735674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 736674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 737674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 738674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 739674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case REMOVE: 740674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 741674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 742674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 743f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann for (i = 0; i < N_TIMES; ++i) 744674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 745674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link; 746674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = get_random_iter (seq, &link); 747674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 748674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!g_sequence_iter_is_end (iter)) 749674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 750674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_remove (iter); 751674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_delete_link (seq->queue, link); 752674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 753674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 754674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 755674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 756674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case REMOVE_RANGE: 757674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 758674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *begin_iter, *end_iter; 759674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *begin_link, *end_link; 760674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *list; 761674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 762674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link); 763674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 764674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_remove_range (begin_iter, end_iter); 765674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 766674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = begin_link; 767674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (list != end_link) 768674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 769674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *next = list->next; 770674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 771674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_delete_link (seq->queue, list); 772674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 773674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = next; 774674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 775674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 776674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 777674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case MOVE_RANGE: 778674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 779674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann SequenceInfo *src = RANDOM_SEQUENCE(); 780674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann SequenceInfo *dst = RANDOM_SEQUENCE(); 781674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 782674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *begin_iter, *end_iter; 783674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *begin_link, *end_link; 784674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 785674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *dst_iter; 786674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *dst_link; 787674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 788674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *list; 789674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 790674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (src->queue); 791674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (dst->queue); 792674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 793674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link); 794674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dst_iter = get_random_iter (dst, &dst_link); 795674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 796674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_move_range (dst_iter, begin_iter, end_iter); 797674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 798674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (dst_link == begin_link || (src == dst && dst_link == end_link)) 799674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 800674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (src); 801674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (dst); 802674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 803674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 804674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 805674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (queue_link_index (src, begin_link) >= 806674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_link_index (src, end_link)) 807674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 808674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 809674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 810674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 811674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (src == dst && 812674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) && 813674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_link_index (src, dst_link) <= queue_link_index (src, end_link)) 814674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 815674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 816674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 817674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 818674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = begin_link; 819674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (list != end_link) 820674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 821674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *next = list->next; 822674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item = get_item (list->data); 823674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 824674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (dst->queue); 825674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_insert_before (dst, dst_link, list->data); 826674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_delete_link (src->queue, list); 827674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 828674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (item->seq == src); 829674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 830674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann src->n_items--; 831674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann dst->n_items++; 832674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item->seq = dst; 833674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 834674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann list = next; 835674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 836674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 837674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 838674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SEARCH: 839674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 840674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item; 841674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *search_iter; 842674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *insert_iter; 843674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 844674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 845674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 846674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 847674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 848674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 849674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item = new_item (seq); 850674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL); 851674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 852674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL); 853674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 854674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (search_iter == g_sequence_iter_next (insert_iter)); 855674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 856674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL); 857674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 858674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 859674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SEARCH_ITER: 860674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 861674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item; 862674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *search_iter; 863674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *insert_iter; 864674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 865674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq->sequence, compare_items, NULL); 866674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_sort (seq->queue, compare_iters, NULL); 867674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 868674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_sorted (seq); 869674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 870674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item = new_item (seq); 871674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann search_iter = g_sequence_search_iter (seq->sequence, 872674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item, 873576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann (GSequenceIterCompareFunc)compare_iters, seq->sequence); 874674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 875674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL); 876674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 877674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (search_iter == g_sequence_iter_next (insert_iter)); 878674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 879674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL); 880674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 881674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 882674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 883674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* dereferencing */ 884674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case GET: 885674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case SET: 886674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 887674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 888674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link; 889674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 890674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = get_random_iter (seq, &link); 891674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 892674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (!g_sequence_iter_is_end (iter)) 893674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 894674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann Item *item; 895674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 896674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 897674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 898674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 899674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Test basic functionality */ 900674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann item = new_item (seq); 901674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_set (iter, item); 902674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_get (iter) == item); 903674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 904674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Make sure that existing items are freed */ 905f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann for (i = 0; i < N_TIMES; ++i) 906674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_set (iter, new_item (seq)); 907674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 908674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 909674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 910674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_set (iter, new_item (seq)); 911674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 912674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 913674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 914674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 915674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* operations on GSequenceIter * */ 916674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_IS_BEGIN: 917674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 918674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 919674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 920674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_iter_at_pos (seq->sequence, 0); 921674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 922674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_begin (iter)); 923674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 924674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 925674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 926674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (g_sequence_get_length (seq->sequence) > 0) 927674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 928576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence))); 929674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 930674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 931674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 932576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence))); 933674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 934674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 935674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence))); 936674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 937674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 938674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_IS_END: 939674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 940674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 941674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int len = g_sequence_get_length (seq->sequence); 942674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 943674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_iter_at_pos (seq->sequence, len); 944674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 945674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_end (iter)); 946674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 947674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (len > 0) 948674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 949576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence))); 950674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 951674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 952674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 953576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence))); 954674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 955674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 956674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence))); 957674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 958674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 959674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_NEXT: 960674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 961674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter1, *iter2, *iter3, *end; 962674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 963674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter1 = g_sequence_append (seq->sequence, new_item (seq)); 964674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter2 = g_sequence_append (seq->sequence, new_item (seq)); 965674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter3 = g_sequence_append (seq->sequence, new_item (seq)); 966674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 967674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann end = g_sequence_get_end_iter (seq->sequence); 968674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 969674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_next (iter1) == iter2); 970674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_next (iter2) == iter3); 971674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_next (iter3) == end); 972674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_next (end) == end); 973674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 974674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_tail (seq->queue, iter1); 975674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_tail (seq->queue, iter2); 976674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_tail (seq->queue, iter3); 977674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 978674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 979674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_PREV: 980674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 981674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter1, *iter2, *iter3, *begin; 982674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 983674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter1 = g_sequence_prepend (seq->sequence, new_item (seq)); 984674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter2 = g_sequence_prepend (seq->sequence, new_item (seq)); 985674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter3 = g_sequence_prepend (seq->sequence, new_item (seq)); 986674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 987674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann begin = g_sequence_get_begin_iter (seq->sequence); 988674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 989674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_prev (iter1) == iter2); 990674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_prev (iter2) == iter3); 991674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iter3 == begin); 992674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_prev (iter3) == begin); 993674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_prev (begin) == begin); 994674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 995674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_head (seq->queue, iter1); 996674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_head (seq->queue, iter2); 997674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_queue_push_head (seq->queue, iter3); 998674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 999674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 1000674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_GET_POSITION: 1001674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1002674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link; 1003674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = get_random_iter (seq, &link); 1004674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1005674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_get_position (iter) == 1006674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann queue_link_index (seq, link)); 1007674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1008674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 1009674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_MOVE: 1010674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1011674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int len = g_sequence_get_length (seq->sequence); 1012674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 1013674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int pos; 1014674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1015674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = get_random_iter (seq, NULL); 1016674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann pos = g_sequence_iter_get_position (iter); 1017674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_move (iter, len - pos); 1018674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_end (iter)); 1019674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1020674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1021674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = get_random_iter (seq, NULL); 1022674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann pos = g_sequence_iter_get_position (iter); 1023674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (pos < len) 1024674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1025674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (!g_sequence_iter_is_end (iter)); 1026674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann pos++; 1027674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_move (iter, 1); 1028674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1029674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_end (iter)); 1030674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1031674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 1032674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_GET_SEQUENCE: 1033674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1034674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = get_random_iter (seq, NULL); 1035674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1036674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence); 1037674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1038674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 1039674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1040674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* search */ 1041674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case ITER_COMPARE: 1042674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1043674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GList *link1, *link2; 1044674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter1 = get_random_iter (seq, &link1); 1045674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter2 = get_random_iter (seq, &link2); 1046674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1047674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int cmp = g_sequence_iter_compare (iter1, iter2); 1048674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int pos1 = queue_link_index (seq, link1); 1049674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int pos2 = queue_link_index (seq, link2); 1050674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1051674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (cmp == 0) 1052674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1053674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (pos1 == pos2); 1054674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1055674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else if (cmp < 0) 1056674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1057674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (pos1 < pos2); 1058674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1059674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 1060674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1061674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (pos1 > pos2); 1062674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1063674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1064674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 1065674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann case RANGE_GET_MIDPOINT: 1066674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1067674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter1 = get_random_iter (seq, NULL); 1068674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter2 = get_random_iter (seq, NULL); 1069674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter3; 1070674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int cmp; 1071674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1072674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann cmp = g_sequence_iter_compare (iter1, iter2); 1073674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1074674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (cmp > 0) 1075674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1076674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *tmp; 1077674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1078674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann tmp = iter1; 1079674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter1 = iter2; 1080674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter2 = tmp; 1081674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1082674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1083674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter3 = g_sequence_range_get_midpoint (iter1, iter2); 1084674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1085674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (cmp == 0) 1086674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1087674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iter3 == iter1); 1088674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iter3 == iter2); 1089674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1090674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1091674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_get_position (iter3) >= 1092674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_iter_get_position (iter1)); 1093674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_get_position (iter2) >= 1094674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_iter_get_position (iter3)); 1095674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1096674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann break; 1097674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1098674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1099674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1100674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann check_integrity (seq); 1101674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1102674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1103674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1104674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann/* Random seeds known to have failed at one point 1105674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann */ 1106674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic gulong seeds[] = 1107674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 11085fa8f600f5321d4a381e08119b39e3ae9b19838aSoren Sandmann 825541564u, 1109674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 801678400u, 1110674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1477639090u, 1111674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 3369132895u, 1112674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1192944867u, 1113674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 770458294u, 1114674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1099575817u, 1115674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 590523467u, 1116674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 3583571454u, 1117674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 579241222u 1118674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann }; 1119674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1120674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void standalone_tests (void); 1121674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1122674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic guint32 1123674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannget_seed (int argc, char **argv) 1124674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1125674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (argc > 1) 1126674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1127674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann char *endptr; 1128674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1129674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return strtol (argv[1], &endptr, 0); 1130674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1131674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 1132674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1133674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return g_random_int(); 1134674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1135674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1136674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1137674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannint 1138674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannmain (int argc, 1139674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann char **argv) 1140674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1141674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann guint32 seed = get_seed (argc, argv); 1142674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 1143674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1144674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Run stand alone tests */ 1145674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_print ("running standalone tests\n"); 1146674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann standalone_tests(); 1147674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1148674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_print ("running regression tests:\n"); 1149674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Run regression tests */ 1150674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < G_N_ELEMENTS (seeds); ++i) 1151674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1152674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann run_random_tests (seeds[i]); 1153674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1154674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1155674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann /* Run with a new random seed */ 1156674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_print ("random seed:\n"); 1157674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann run_random_tests (seed); 1158674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1159674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1160674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return 0; 1161674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1162674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1163674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1164674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann/* Single, stand-alone tests */ 1165674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1166674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 1167674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanntest_out_of_range_jump (void) 1168674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1169674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequence *seq = g_sequence_new (NULL); 1170674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter = g_sequence_get_begin_iter (seq); 1171674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1172674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_iter_move (iter, 5); 1173674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1174674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_begin (iter)); 1175674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (g_sequence_iter_is_end (iter)); 1176674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1177674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1178674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic int 1179674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanncompare (gconstpointer a, gconstpointer b, gpointer userdata) 1180674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1181674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int ai, bi; 1182674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1183674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann ai = GPOINTER_TO_INT (a); 1184674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann bi = GPOINTER_TO_INT (b); 1185674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1186674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann if (ai < bi) 1187674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return -1; 1188674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else if (ai > bi) 1189674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return 1; 1190674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann else 1191674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return 0; 1192674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1193674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1194674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic int 1195674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanncompare_iter (GSequenceIter *a, 1196674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *b, 1197674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann gpointer data) 1198674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1199674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann return compare (g_sequence_get (a), 1200674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_get (b), 1201674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann data); 1202674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1203674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1204674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 1205674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanntest_insert_sorted_non_pointer (void) 1206674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1207674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 1208674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1209674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < 10; i++) 1210674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1211674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequence *seq = g_sequence_new (NULL); 1212674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int j; 1213674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1214674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (j = 0; j < 10000; j++) 1215674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1216576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()), 1217674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann compare, NULL); 1218674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1219576a5d41270c6a1ee2fd7a423998b92d808183beSoren Sandmann g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()), 1220674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann compare_iter, NULL); 1221674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1222f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 122345b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1224674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1225674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_free (seq); 1226674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1227674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1228674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1229674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 1230674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmanntest_stable_sort (void) 1231674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1232674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann int i; 1233674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequence *seq = g_sequence_new (NULL); 1234674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1235674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann#define N_ITEMS 1000 1236674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1237674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iters[N_ITEMS]; 1238674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann GSequenceIter *iter; 1239674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1240674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = 0; i < N_ITEMS; ++i) 1241f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann { 1242f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000)); 124345b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1244f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (g_sequence_iter_get_sequence (iters[i]) == seq); 1245f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann } 1246f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 1247674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann i = 0; 1248674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_begin_iter (seq); 1249f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (g_sequence_iter_get_sequence (iter) == seq); 125045b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1251674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (!g_sequence_iter_is_end (iter)) 1252674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1253f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (g_sequence_iter_get_sequence (iters[i]) == seq); 1254674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iters[i++] == iter); 1255674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1256674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_next (iter); 125745b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1258674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1259674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1260674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_sequence_sort (seq, compare, NULL); 1261674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1262674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann i = 0; 1263674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_begin_iter (seq); 1264674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (!g_sequence_iter_is_end (iter)) 1265674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1266f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (g_sequence_iter_get_sequence (iters[i]) == seq); 1267f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (iters[i] == iter); 1268674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1269674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_next (iter); 127045b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1271f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann 1272f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann i++; 1273674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1274674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1275674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann for (i = N_ITEMS - 1; i >= 0; --i) 1276f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann { 127745b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1278f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (g_sequence_iter_get_sequence (iters[i]) == seq); 1279f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_assert (g_sequence_get_end_iter (seq) != iters[i]); 1280f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann g_sequence_sort_changed (iters[i], compare, NULL); 1281f13d070e20cfd7014783a81db20b78fad11df6b5Soren Sandmann } 1282674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1283674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann i = 0; 1284674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_get_begin_iter (seq); 1285674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann while (!g_sequence_iter_is_end (iter)) 1286674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann { 1287674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann g_assert (iters[i++] == iter); 1288674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1289674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann iter = g_sequence_iter_next (iter); 129045b2988d051ea396a941883a124880329516c7fbMatthias Clasen g_sequence_check (seq); 1291674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann } 1292674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1293674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1294674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstatic void 1295674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmannstandalone_tests (void) 1296674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann{ 1297674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann test_out_of_range_jump (); 1298674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann test_insert_sorted_non_pointer (); 1299674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann test_stable_sort (); 1300674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann} 1301674c4df418d2be7aeb55462b3534f985560098c3Soren Sandmann 1302