| #undef G_DISABLE_ASSERT |
| #undef G_LOG_DOMAIN |
| |
| #include <time.h> |
| #include <stdlib.h> |
| |
| #include <glib.h> |
| |
| |
| static void |
| check_integrity (GQueue *queue) |
| { |
| GList *list; |
| GList *last; |
| GList *links; |
| GList *link; |
| guint n; |
| |
| g_assert (queue->length < 4000000000u); |
| |
| g_assert (g_queue_get_length (queue) == queue->length); |
| |
| if (!queue->head) |
| g_assert (!queue->tail); |
| if (!queue->tail) |
| g_assert (!queue->head); |
| |
| n = 0; |
| last = NULL; |
| for (list = queue->head; list != NULL; list = list->next) |
| { |
| if (!list->next) |
| last = list; |
| ++n; |
| } |
| g_assert (n == queue->length); |
| g_assert (last == queue->tail); |
| |
| n = 0; |
| last = NULL; |
| for (list = queue->tail; list != NULL; list = list->prev) |
| { |
| if (!list->prev) |
| last = list; |
| ++n; |
| } |
| g_assert (n == queue->length); |
| g_assert (last == queue->head); |
| |
| links = NULL; |
| for (list = queue->head; list != NULL; list = list->next) |
| links = g_list_prepend (links, list); |
| |
| link = links; |
| for (list = queue->tail; list != NULL; list = list->prev) |
| { |
| g_assert (list == link->data); |
| link = link->next; |
| } |
| g_list_free (links); |
| |
| links = NULL; |
| for (list = queue->tail; list != NULL; list = list->prev) |
| links = g_list_prepend (links, list); |
| |
| link = links; |
| for (list = queue->head; list != NULL; list = list->next) |
| { |
| g_assert (list == link->data); |
| link = link->next; |
| } |
| g_list_free (links); |
| } |
| |
| static gboolean |
| rnd_bool (void) |
| { |
| return g_random_int_range (0, 2); |
| } |
| |
| static void |
| check_max (gpointer elm, gpointer user_data) |
| { |
| gint *best = user_data; |
| gint element = GPOINTER_TO_INT (elm); |
| |
| if (element > *best) |
| *best = element; |
| } |
| |
| static void |
| check_min (gpointer elm, gpointer user_data) |
| { |
| gint *best = user_data; |
| gint element = GPOINTER_TO_INT (elm); |
| |
| if (element < *best) |
| *best = element; |
| } |
| |
| static gint |
| find_min (GQueue *queue) |
| { |
| gint min = G_MAXINT; |
| |
| g_queue_foreach (queue, check_min, &min); |
| |
| return min; |
| } |
| |
| static gint |
| find_max (GQueue *queue) |
| { |
| gint max = G_MININT; |
| |
| g_queue_foreach (queue, check_max, &max); |
| |
| return max; |
| } |
| |
| static void |
| delete_elm (gpointer elm, gpointer user_data) |
| { |
| g_queue_remove ((GQueue *)user_data, elm); |
| check_integrity ((GQueue *)user_data); |
| } |
| |
| static void |
| delete_all (GQueue *queue) |
| { |
| g_queue_foreach (queue, delete_elm, queue); |
| } |
| |
| static int |
| compare_int (gconstpointer a, gconstpointer b, gpointer data) |
| { |
| int ai = GPOINTER_TO_INT (a); |
| int bi = GPOINTER_TO_INT (b); |
| |
| if (ai > bi) |
| return 1; |
| else if (ai == bi) |
| return 0; |
| else |
| return -1; |
| } |
| |
| static gint |
| get_random_position (GQueue *queue, gboolean allow_offlist) |
| { |
| int n; |
| enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where; |
| |
| if (allow_offlist) |
| where = g_random_int_range (OFF_QUEUE, LAST); |
| else |
| where = g_random_int_range (HEAD, LAST); |
| |
| switch (where) |
| { |
| case OFF_QUEUE: |
| n = g_random_int (); |
| break; |
| |
| case HEAD: |
| n = 0; |
| break; |
| |
| case TAIL: |
| if (allow_offlist) |
| n = queue->length; |
| else |
| n = queue->length - 1; |
| break; |
| |
| case MIDDLE: |
| if (queue->length == 0) |
| n = 0; |
| else |
| n = g_random_int_range (0, queue->length); |
| break; |
| |
| default: |
| g_assert_not_reached(); |
| n = 100; |
| break; |
| |
| } |
| |
| return n; |
| } |
| |
| static void |
| random_test (gconstpointer d) |
| { |
| guint32 seed = GPOINTER_TO_UINT (d); |
| |
| typedef enum { |
| IS_EMPTY, GET_LENGTH, REVERSE, COPY, |
| FOREACH, FIND, FIND_CUSTOM, SORT, |
| PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD, |
| POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL, |
| PEEK_NTH, INDEX, REMOVE, REMOVE_ALL, |
| INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK, |
| PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK, |
| POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK, |
| LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP |
| } QueueOp; |
| |
| #define N_ITERATIONS 500000 |
| #define N_QUEUES 3 |
| |
| #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)]) |
| |
| typedef struct QueueInfo QueueInfo; |
| struct QueueInfo |
| { |
| GQueue *queue; |
| GList *tail; |
| GList *head; |
| guint length; |
| }; |
| |
| gint i; |
| QueueOp op; |
| QueueInfo queues[N_QUEUES]; |
| |
| g_random_set_seed (seed); |
| |
| for (i = 0; i < N_QUEUES; ++i) |
| { |
| queues[i].queue = g_queue_new (); |
| queues[i].head = NULL; |
| queues[i].tail = NULL; |
| queues[i].length = 0; |
| } |
| |
| for (i = 0; i < N_ITERATIONS; ++i) |
| { |
| int j; |
| QueueInfo *qinf = RANDOM_QUEUE(); |
| GQueue *q = qinf->queue; |
| op = g_random_int_range (IS_EMPTY, LAST_OP); |
| |
| g_assert (qinf->head == q->head); |
| g_assert (qinf->tail == q->tail); |
| g_assert (qinf->length == q->length); |
| |
| switch (op) |
| { |
| case IS_EMPTY: |
| { |
| if (g_queue_is_empty (qinf->queue)) |
| { |
| g_assert (q->head == NULL); |
| g_assert (q->tail == NULL); |
| g_assert (q->length == 0); |
| } |
| else |
| { |
| g_assert (q->head); |
| g_assert (q->tail); |
| g_assert (q->length > 0); |
| } |
| } |
| break; |
| case GET_LENGTH: |
| { |
| guint l; |
| |
| l = g_queue_get_length (q); |
| |
| g_assert (qinf->length == q->length); |
| g_assert (qinf->length == l); |
| } |
| break; |
| case REVERSE: |
| g_queue_reverse (q); |
| g_assert (qinf->tail == q->head); |
| g_assert (qinf->head == q->tail); |
| g_assert (qinf->length == q->length); |
| qinf->tail = q->tail; |
| qinf->head = q->head; |
| break; |
| case COPY: |
| { |
| QueueInfo *random_queue = RANDOM_QUEUE(); |
| GQueue *new_queue = g_queue_copy (random_queue->queue); |
| |
| g_queue_free (qinf->queue); |
| q = qinf->queue = new_queue; |
| qinf->head = new_queue->head; |
| qinf->tail = g_list_last (new_queue->head); |
| qinf->length = new_queue->length; |
| } |
| break; |
| case FOREACH: |
| delete_all (q); |
| qinf->head = NULL; |
| qinf->tail = NULL; |
| qinf->length = 0; |
| break; |
| case FIND: |
| { |
| gboolean find_existing = rnd_bool (); |
| int first = find_max (q); |
| int second = find_min (q); |
| |
| if (q->length == 0) |
| find_existing = FALSE; |
| |
| if (!find_existing) |
| first++; |
| if (!find_existing) |
| second--; |
| |
| if (find_existing) |
| { |
| g_assert (g_queue_find (q, GINT_TO_POINTER (first))); |
| g_assert (g_queue_find (q, GINT_TO_POINTER (second))); |
| } |
| else |
| { |
| g_assert (!g_queue_find (q, GINT_TO_POINTER (first))); |
| g_assert (!g_queue_find (q, GINT_TO_POINTER (second))); |
| } |
| } |
| break; |
| case FIND_CUSTOM: |
| break; |
| case SORT: |
| { |
| if (!g_queue_is_empty (q)) |
| { |
| int max = find_max (q); |
| int min = find_min (q); |
| g_queue_remove_all (q, GINT_TO_POINTER (max)); |
| check_integrity (q); |
| g_queue_remove_all (q, GINT_TO_POINTER (min)); |
| check_integrity (q); |
| g_queue_push_head (q, GINT_TO_POINTER (max)); |
| if (max != min) |
| g_queue_push_head (q, GINT_TO_POINTER (min)); |
| qinf->length = q->length; |
| } |
| |
| check_integrity (q); |
| |
| g_queue_sort (q, compare_int, NULL); |
| |
| check_integrity (q); |
| |
| qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q))); |
| qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q))); |
| |
| g_assert (qinf->tail == q->tail); |
| } |
| break; |
| case PUSH_HEAD: |
| { |
| int x = g_random_int_range (0, 435435); |
| g_queue_push_head (q, GINT_TO_POINTER (x)); |
| if (!qinf->head) |
| qinf->tail = qinf->head = q->head; |
| else |
| qinf->head = qinf->head->prev; |
| qinf->length++; |
| } |
| break; |
| case PUSH_TAIL: |
| { |
| int x = g_random_int_range (0, 236546); |
| g_queue_push_tail (q, GINT_TO_POINTER (x)); |
| if (!qinf->tail) |
| qinf->tail = qinf->head = q->head; |
| else |
| qinf->tail = qinf->tail->next; |
| qinf->length++; |
| } |
| break; |
| case PUSH_NTH: |
| { |
| int pos = get_random_position (q, TRUE); |
| int x = g_random_int_range (0, 236546); |
| g_queue_push_nth (q, GINT_TO_POINTER (x), pos); |
| if (qinf->head && qinf->head->prev) |
| qinf->head = qinf->head->prev; |
| else |
| qinf->head = q->head; |
| if (qinf->tail && qinf->tail->next) |
| qinf->tail = qinf->tail->next; |
| else |
| qinf->tail = g_list_last (qinf->head); |
| qinf->length++; |
| } |
| break; |
| case POP_HEAD: |
| if (qinf->head) |
| qinf->head = qinf->head->next; |
| if (!qinf->head) |
| qinf->tail = NULL; |
| qinf->length = (qinf->length == 0)? 0 : qinf->length - 1; |
| g_queue_pop_head (q); |
| break; |
| case POP_TAIL: |
| if (qinf->tail) |
| qinf->tail = qinf->tail->prev; |
| if (!qinf->tail) |
| qinf->head = NULL; |
| qinf->length = (qinf->length == 0)? 0 : qinf->length - 1; |
| g_queue_pop_tail (q); |
| break; |
| case POP_NTH: |
| if (!g_queue_is_empty (q)) |
| { |
| int n = get_random_position (q, TRUE); |
| gpointer elm = g_queue_peek_nth (q, n); |
| |
| if (n == (int) (q->length - 1)) |
| qinf->tail = qinf->tail->prev; |
| |
| if (n == 0) |
| qinf->head = qinf->head->next; |
| |
| if (n >= 0 && (guint) n < q->length) |
| qinf->length--; |
| |
| g_assert (elm == g_queue_pop_nth (q, n)); |
| } |
| break; |
| case PEEK_HEAD: |
| if (qinf->head) |
| g_assert (qinf->head->data == g_queue_peek_head (q)); |
| else |
| g_assert (g_queue_peek_head (q) == NULL); |
| break; |
| case PEEK_TAIL: |
| if (qinf->tail) |
| g_assert (qinf->tail->data == g_queue_peek_tail (q)); |
| else |
| g_assert (g_queue_peek_tail (q) == NULL); |
| break; |
| case PEEK_NTH: |
| if (g_queue_is_empty (q)) |
| { |
| for (j = -10; j < 10; ++j) |
| g_assert (g_queue_peek_nth (q, j) == NULL); |
| } |
| else |
| { |
| GList *list; |
| int n = get_random_position (q, TRUE); |
| if (n < 0 || (guint) n >= q->length) |
| { |
| g_assert (g_queue_peek_nth (q, n) == NULL); |
| } |
| else |
| { |
| list = qinf->head; |
| for (j = 0; j < n; ++j) |
| list = list->next; |
| |
| g_assert (list->data == g_queue_peek_nth (q, n)); |
| } |
| } |
| break; |
| case INDEX: |
| case LINK_INDEX: |
| { |
| int x = g_random_int_range (0, 386538); |
| int n; |
| GList *list; |
| |
| g_queue_remove_all (q, GINT_TO_POINTER (x)); |
| check_integrity (q); |
| g_queue_push_tail (q, GINT_TO_POINTER (x)); |
| check_integrity (q); |
| g_queue_sort (q, compare_int, NULL); |
| check_integrity (q); |
| |
| n = 0; |
| for (list = q->head; list != NULL; list = list->next) |
| { |
| if (list->data == GINT_TO_POINTER (x)) |
| break; |
| n++; |
| } |
| g_assert (list); |
| g_assert (g_queue_index (q, GINT_TO_POINTER (x)) == |
| g_queue_link_index (q, list)); |
| g_assert (g_queue_link_index (q, list) == n); |
| |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length = q->length; |
| } |
| break; |
| case REMOVE: |
| if (!g_queue_is_empty (q)) |
| g_queue_remove (q, qinf->tail->data); |
| /* qinf->head/qinf->tail may be invalid at this point */ |
| if (!g_queue_is_empty (q)) |
| g_queue_remove (q, q->head->data); |
| if (!g_queue_is_empty (q)) |
| g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE))); |
| |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length = q->length; |
| break; |
| case REMOVE_ALL: |
| if (!g_queue_is_empty (q)) |
| g_queue_remove_all (q, qinf->tail->data); |
| /* qinf->head/qinf->tail may be invalid at this point */ |
| if (!g_queue_is_empty (q)) |
| g_queue_remove_all (q, q->head->data); |
| if (!g_queue_is_empty (q)) |
| g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE))); |
| |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length = q->length; |
| break; |
| case INSERT_BEFORE: |
| if (!g_queue_is_empty (q)) |
| { |
| gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538)); |
| |
| g_queue_insert_before (q, qinf->tail, x); |
| g_queue_insert_before (q, qinf->head, x); |
| g_queue_insert_before (q, g_queue_find (q, x), x); |
| g_queue_insert_before (q, NULL, x); |
| } |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length = q->length; |
| break; |
| case INSERT_AFTER: |
| if (!g_queue_is_empty (q)) |
| { |
| gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538)); |
| |
| g_queue_insert_after (q, qinf->tail, x); |
| g_queue_insert_after (q, qinf->head, x); |
| g_queue_insert_after (q, g_queue_find (q, x), x); |
| g_queue_insert_after (q, NULL, x); |
| } |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length = q->length; |
| break; |
| case INSERT_SORTED: |
| { |
| int max = find_max (q); |
| int min = find_min (q); |
| |
| if (g_queue_is_empty (q)) |
| { |
| max = 345; |
| min = -12; |
| } |
| |
| g_queue_sort (q, compare_int, NULL); |
| check_integrity (q); |
| g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL); |
| check_integrity (q); |
| g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1); |
| g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL); |
| check_integrity (q); |
| g_assert (GPOINTER_TO_INT (q->head->data) == min - 1); |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length = q->length; |
| } |
| break; |
| case PUSH_HEAD_LINK: |
| { |
| GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
| g_queue_push_head_link (q, link); |
| if (!qinf->tail) |
| qinf->tail = link; |
| qinf->head = link; |
| qinf->length++; |
| } |
| break; |
| case PUSH_TAIL_LINK: |
| { |
| GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
| g_queue_push_tail_link (q, link); |
| if (!qinf->head) |
| qinf->head = link; |
| qinf->tail = link; |
| qinf->length++; |
| } |
| break; |
| case PUSH_NTH_LINK: |
| { |
| GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
| gint n = get_random_position (q, TRUE); |
| g_queue_push_nth_link (q, n, link); |
| |
| if (qinf->head && qinf->head->prev) |
| qinf->head = qinf->head->prev; |
| else |
| qinf->head = q->head; |
| if (qinf->tail && qinf->tail->next) |
| qinf->tail = qinf->tail->next; |
| else |
| qinf->tail = g_list_last (qinf->head); |
| qinf->length++; |
| } |
| break; |
| case POP_HEAD_LINK: |
| if (!g_queue_is_empty (q)) |
| { |
| qinf->head = qinf->head->next; |
| if (!qinf->head) |
| qinf->tail = NULL; |
| qinf->length--; |
| g_list_free (g_queue_pop_head_link (q)); |
| } |
| break; |
| case POP_TAIL_LINK: |
| if (!g_queue_is_empty (q)) |
| { |
| qinf->tail = qinf->tail->prev; |
| if (!qinf->tail) |
| qinf->head = NULL; |
| qinf->length--; |
| g_list_free (g_queue_pop_tail_link (q)); |
| } |
| break; |
| case POP_NTH_LINK: |
| if (g_queue_is_empty (q)) |
| g_assert (g_queue_pop_nth_link (q, 200) == NULL); |
| else |
| { |
| int n = get_random_position (q, FALSE); |
| |
| if (n == (int) (g_queue_get_length (q) - 1)) |
| qinf->tail = qinf->tail->prev; |
| |
| if (n == 0) |
| qinf->head = qinf->head->next; |
| |
| qinf->length--; |
| |
| g_list_free (g_queue_pop_nth_link (q, n)); |
| } |
| break; |
| case PEEK_HEAD_LINK: |
| if (g_queue_is_empty (q)) |
| g_assert (g_queue_peek_head_link (q) == NULL); |
| else |
| g_assert (g_queue_peek_head_link (q) == qinf->head); |
| break; |
| case PEEK_TAIL_LINK: |
| if (g_queue_is_empty (q)) |
| g_assert (g_queue_peek_tail_link (q) == NULL); |
| else |
| g_assert (g_queue_peek_tail_link (q) == qinf->tail); |
| break; |
| case PEEK_NTH_LINK: |
| if (g_queue_is_empty(q)) |
| g_assert (g_queue_peek_nth_link (q, 1000) == NULL); |
| else |
| { |
| gint n = get_random_position (q, FALSE); |
| GList *link; |
| |
| link = q->head; |
| for (j = 0; j < n; ++j) |
| link = link->next; |
| |
| g_assert (g_queue_peek_nth_link (q, n) == link); |
| } |
| break; |
| case UNLINK: |
| if (!g_queue_is_empty (q)) |
| { |
| gint n = g_random_int_range (0, g_queue_get_length (q)); |
| GList *link; |
| |
| link = q->head; |
| for (j = 0; j < n; ++j) |
| link = link->next; |
| |
| g_queue_unlink (q, link); |
| check_integrity (q); |
| |
| g_list_free (link); |
| |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length--; |
| } |
| break; |
| case DELETE_LINK: |
| if (!g_queue_is_empty (q)) |
| { |
| gint n = g_random_int_range (0, g_queue_get_length (q)); |
| GList *link; |
| |
| link = q->head; |
| for (j = 0; j < n; ++j) |
| link = link->next; |
| |
| g_queue_delete_link (q, link); |
| check_integrity (q); |
| |
| qinf->head = q->head; |
| qinf->tail = q->tail; |
| qinf->length--; |
| } |
| break; |
| case LAST_OP: |
| default: |
| g_assert_not_reached(); |
| break; |
| } |
| |
| if (qinf->head != q->head || |
| qinf->tail != q->tail || |
| qinf->length != q->length) |
| g_printerr ("op: %d\n", op); |
| |
| g_assert (qinf->head == q->head); |
| g_assert (qinf->tail == q->tail); |
| g_assert (qinf->length == q->length); |
| |
| for (j = 0; j < N_QUEUES; ++j) |
| check_integrity (queues[j].queue); |
| } |
| |
| for (i = 0; i < N_QUEUES; ++i) |
| g_queue_free (queues[i].queue); |
| } |
| |
| static void |
| remove_item (gpointer data, gpointer q) |
| { |
| GQueue *queue = q; |
| |
| g_queue_remove (queue, data); |
| } |
| |
| static void |
| test_basic (void) |
| { |
| GQueue *q; |
| GList *node; |
| gpointer data; |
| |
| q = g_queue_new (); |
| |
| g_assert (g_queue_is_empty (q)); |
| g_queue_push_head (q, GINT_TO_POINTER (2)); |
| check_integrity (q); |
| g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2)); |
| check_integrity (q); |
| g_assert (!g_queue_is_empty (q)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 1); |
| g_assert (q->head == q->tail); |
| g_queue_push_head (q, GINT_TO_POINTER (1)); |
| check_integrity (q); |
| g_assert (q->head->next == q->tail); |
| g_assert (q->tail->prev == q->head); |
| g_assert_cmpint (g_list_length (q->head), ==, 2); |
| check_integrity (q); |
| g_assert (q->tail->data == GINT_TO_POINTER (2)); |
| g_assert (q->head->data == GINT_TO_POINTER (1)); |
| check_integrity (q); |
| g_queue_push_tail (q, GINT_TO_POINTER (3)); |
| g_assert_cmpint (g_list_length (q->head), ==, 3); |
| g_assert (q->head->data == GINT_TO_POINTER (1)); |
| g_assert (q->head->next->data == GINT_TO_POINTER (2)); |
| g_assert (q->head->next->next == q->tail); |
| g_assert (q->head->next == q->tail->prev); |
| g_assert (q->tail->data == GINT_TO_POINTER (3)); |
| g_queue_push_tail (q, GINT_TO_POINTER (4)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 4); |
| g_assert (q->head->data == GINT_TO_POINTER (1)); |
| g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4)); |
| g_queue_push_tail (q, GINT_TO_POINTER (5)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 5); |
| g_assert (g_queue_is_empty (q) == FALSE); |
| check_integrity (q); |
| g_assert_cmpint (q->length, ==, 5); |
| g_assert (q->head->prev == NULL); |
| g_assert (q->head->data == GINT_TO_POINTER (1)); |
| g_assert (q->head->next->data == GINT_TO_POINTER (2)); |
| g_assert (q->head->next->next->data == GINT_TO_POINTER (3)); |
| g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4)); |
| g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5)); |
| g_assert (q->head->next->next->next->next->next == NULL); |
| g_assert (q->head->next->next->next->next == q->tail); |
| g_assert (q->tail->data == GINT_TO_POINTER (5)); |
| g_assert (q->tail->prev->data == GINT_TO_POINTER (4)); |
| g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3)); |
| g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2)); |
| g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1)); |
| g_assert (q->tail->prev->prev->prev->prev->prev == NULL); |
| g_assert (q->tail->prev->prev->prev->prev == q->head); |
| g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5)); |
| g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1)); |
| g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 4); |
| g_assert_cmpint (q->length, ==, 4); |
| g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 3); |
| |
| node = g_queue_pop_head_link (q); |
| g_assert (node->data == GINT_TO_POINTER (2)); |
| g_list_free_1 (node); |
| |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 2); |
| g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 1); |
| node = g_queue_pop_head_link (q); |
| g_assert (node->data == GINT_TO_POINTER (3)); |
| g_list_free_1 (node); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_assert (g_queue_pop_tail (q) == NULL); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_assert (g_queue_pop_head (q) == NULL); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_assert (g_queue_is_empty (q)); |
| check_integrity (q); |
| |
| g_queue_push_head (q, GINT_TO_POINTER (1)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 1); |
| g_assert_cmpint (q->length, ==, 1); |
| g_queue_push_head (q, GINT_TO_POINTER (2)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 2); |
| g_assert_cmpint (q->length, ==, 2); |
| g_queue_push_head (q, GINT_TO_POINTER (3)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 3); |
| g_assert_cmpint (q->length, ==, 3); |
| g_queue_push_head (q, GINT_TO_POINTER (4)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 4); |
| g_assert_cmpint (q->length, ==, 4); |
| g_queue_push_head (q, GINT_TO_POINTER (5)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 5); |
| g_assert_cmpint (q->length, ==, 5); |
| g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 4); |
| node = q->tail; |
| g_assert (node == g_queue_pop_tail_link (q)); |
| check_integrity (q); |
| g_list_free_1 (node); |
| g_assert_cmpint (g_list_length (q->head), ==, 3); |
| data = q->head->data; |
| g_assert (data == g_queue_pop_head (q)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 2); |
| g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 1); |
| g_assert (q->head == q->tail); |
| g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3)); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_assert (g_queue_pop_head (q) == NULL); |
| check_integrity (q); |
| g_assert (g_queue_pop_head_link (q) == NULL); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_assert (g_queue_pop_tail_link (q) == NULL); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| |
| g_queue_reverse (q); |
| check_integrity (q); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_queue_free (q); |
| } |
| |
| static void |
| test_copy (void) |
| { |
| GQueue *q, *q2; |
| gint i; |
| |
| q = g_queue_new (); |
| q2 = g_queue_copy (q); |
| check_integrity (q); |
| check_integrity (q2); |
| g_assert_cmpint (g_list_length (q->head), ==, 0); |
| g_assert_cmpint (g_list_length (q2->head), ==, 0); |
| g_queue_sort (q, compare_int, NULL); |
| check_integrity (q2); |
| check_integrity (q); |
| g_queue_sort (q2, compare_int, NULL); |
| check_integrity (q2); |
| check_integrity (q); |
| |
| for (i = 0; i < 200; ++i) |
| { |
| g_queue_push_nth (q, GINT_TO_POINTER (i), i); |
| g_assert (g_queue_find (q, GINT_TO_POINTER (i))); |
| check_integrity (q); |
| check_integrity (q2); |
| } |
| |
| for (i = 0; i < 200; ++i) |
| { |
| g_queue_remove (q, GINT_TO_POINTER (i)); |
| check_integrity (q); |
| check_integrity (q2); |
| } |
| |
| for (i = 0; i < 200; ++i) |
| { |
| GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
| |
| g_queue_push_nth_link (q, i, l); |
| check_integrity (q); |
| check_integrity (q2); |
| g_queue_reverse (q); |
| check_integrity (q); |
| check_integrity (q2); |
| } |
| |
| g_queue_free (q2); |
| q2 = g_queue_copy (q); |
| |
| g_queue_foreach (q2, remove_item, q2); |
| check_integrity (q2); |
| check_integrity (q); |
| |
| g_queue_free (q); |
| g_queue_free (q2); |
| } |
| |
| static void |
| test_off_by_one (void) |
| { |
| GQueue *q; |
| GList *node; |
| |
| q = g_queue_new (); |
| |
| g_queue_push_tail (q, GINT_TO_POINTER (1234)); |
| check_integrity (q); |
| node = g_queue_peek_tail_link (q); |
| g_assert (node != NULL && node->data == GINT_TO_POINTER (1234)); |
| node = g_queue_peek_nth_link (q, g_queue_get_length (q)); |
| g_assert (node == NULL); |
| node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1); |
| g_assert (node->data == GINT_TO_POINTER (1234)); |
| node = g_queue_pop_nth_link (q, g_queue_get_length (q)); |
| g_assert (node == NULL); |
| node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1); |
| g_assert (node != NULL && node->data == GINT_TO_POINTER (1234)); |
| g_list_free_1 (node); |
| |
| g_queue_free (q); |
| } |
| |
| static gint |
| find_custom (gconstpointer a, gconstpointer b) |
| { |
| return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b); |
| } |
| |
| static void |
| test_find_custom (void) |
| { |
| GQueue *q; |
| GList *node; |
| q = g_queue_new (); |
| |
| g_queue_push_tail (q, GINT_TO_POINTER (1234)); |
| g_queue_push_tail (q, GINT_TO_POINTER (1)); |
| g_queue_push_tail (q, GINT_TO_POINTER (2)); |
| node = g_queue_find_custom (q, GINT_TO_POINTER (1), find_custom); |
| g_assert (node != NULL); |
| node = g_queue_find_custom (q, GINT_TO_POINTER (2), find_custom); |
| g_assert (node != NULL); |
| node = g_queue_find_custom (q, GINT_TO_POINTER (3), find_custom); |
| g_assert (node == NULL); |
| |
| g_queue_free (q); |
| } |
| |
| static void |
| test_static (void) |
| { |
| GQueue q; |
| GQueue q2 = G_QUEUE_INIT; |
| |
| g_queue_init (&q); |
| |
| check_integrity (&q); |
| g_assert (g_queue_is_empty (&q)); |
| |
| check_integrity (&q2); |
| g_assert (g_queue_is_empty (&q2)); |
| } |
| |
| static void |
| test_clear (void) |
| { |
| GQueue *q; |
| q = g_queue_new (); |
| |
| g_queue_push_tail (q, GINT_TO_POINTER (1234)); |
| g_queue_push_tail (q, GINT_TO_POINTER (1)); |
| g_queue_push_tail (q, GINT_TO_POINTER (2)); |
| g_assert_cmpint (g_queue_get_length (q), ==, 3); |
| |
| g_queue_clear (q); |
| check_integrity (q); |
| g_assert (g_queue_is_empty (q)); |
| |
| g_queue_free (q); |
| } |
| |
| typedef struct |
| { |
| gboolean freed; |
| int x; |
| } QueueItem; |
| |
| static void |
| free_func (gpointer data) |
| { |
| QueueItem *item = data; |
| |
| item->freed = TRUE; |
| } |
| |
| static QueueItem * |
| new_item (int x) |
| { |
| QueueItem *item; |
| |
| item = g_slice_new (QueueItem); |
| item->freed = FALSE; |
| item->x = x; |
| |
| return item; |
| } |
| |
| static void |
| test_clear_full (void) |
| { |
| QueueItem *one, *two, *three, *four; |
| GQueue *queue; |
| |
| queue = g_queue_new (); |
| g_queue_push_tail (queue, one = new_item (1)); |
| g_queue_push_tail (queue, two = new_item (2)); |
| g_queue_push_tail (queue, three = new_item (3)); |
| g_queue_push_tail (queue, four = new_item (4)); |
| |
| g_assert_cmpint (g_queue_get_length (queue), ==, 4); |
| g_assert_false (one->freed); |
| g_assert_false (two->freed); |
| g_assert_false (three->freed); |
| g_assert_false (four->freed); |
| |
| g_queue_clear_full (queue, free_func); |
| |
| g_assert_true (one->freed); |
| g_assert_true (two->freed); |
| g_assert_true (three->freed); |
| g_assert_true (four->freed); |
| |
| g_assert_true (g_queue_is_empty (queue)); |
| check_integrity (queue); |
| |
| g_slice_free (QueueItem, one); |
| g_slice_free (QueueItem, two); |
| g_slice_free (QueueItem, three); |
| g_slice_free (QueueItem, four); |
| g_queue_free (queue); |
| } |
| |
| /* Check that g_queue_clear_full() called with a NULL free_func is equivalent |
| * to g_queue_clear(). */ |
| static void |
| test_clear_full_noop (void) |
| { |
| QueueItem *one, *two, *three, *four; |
| GQueue *queue; |
| |
| queue = g_queue_new (); |
| g_queue_push_tail (queue, one = new_item (1)); |
| g_queue_push_tail (queue, two = new_item (2)); |
| g_queue_push_tail (queue, three = new_item (3)); |
| g_queue_push_tail (queue, four = new_item (4)); |
| |
| g_assert_cmpint (g_queue_get_length (queue), ==, 4); |
| g_assert_false (one->freed); |
| g_assert_false (two->freed); |
| g_assert_false (three->freed); |
| g_assert_false (four->freed); |
| |
| g_queue_clear_full (queue, NULL); |
| |
| g_assert_true (g_queue_is_empty (queue)); |
| check_integrity (queue); |
| |
| g_slice_free (QueueItem, one); |
| g_slice_free (QueueItem, two); |
| g_slice_free (QueueItem, three); |
| g_slice_free (QueueItem, four); |
| g_queue_free (queue); |
| } |
| |
| /* Test g_queue_push_nth_link() with various combinations of position (before, |
| * in the middle of, or at the end of the queue) and various existing queues |
| * (empty, single element, multiple elements). */ |
| static void |
| test_push_nth_link (void) |
| { |
| GQueue *q; |
| q = g_queue_new (); |
| |
| /* Push onto before the front of an empty queue (which results in it being |
| * added to the end of the queue). */ |
| g_queue_push_nth_link (q, -1, g_list_prepend (NULL, GINT_TO_POINTER (1))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 1); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 1); |
| |
| g_queue_clear (q); |
| |
| /* Push onto after the rear of an empty queue. */ |
| g_queue_push_nth_link (q, 100, g_list_prepend (NULL, GINT_TO_POINTER (2))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 1); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 2); |
| |
| g_queue_clear (q); |
| |
| /* Push onto the front of an empty queue. */ |
| g_queue_push_nth_link (q, 0, g_list_prepend (NULL, GINT_TO_POINTER (3))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 1); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 3); |
| |
| g_queue_clear (q); |
| |
| /* Push onto before the front of a non-empty queue (which results in it being |
| * added to the end of the queue). */ |
| g_queue_push_head (q, GINT_TO_POINTER (4)); |
| g_queue_push_nth_link (q, -1, g_list_prepend (NULL, GINT_TO_POINTER (5))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 2); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 4); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 5); |
| |
| g_queue_clear (q); |
| |
| /* Push onto after the rear of a non-empty queue. */ |
| g_queue_push_head (q, GINT_TO_POINTER (6)); |
| g_queue_push_nth_link (q, 100, g_list_prepend (NULL, GINT_TO_POINTER (7))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 2); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 6); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 7); |
| |
| g_queue_clear (q); |
| |
| /* Push onto the rear of a non-empty queue. */ |
| g_queue_push_head (q, GINT_TO_POINTER (8)); |
| g_queue_push_nth_link (q, 1, g_list_prepend (NULL, GINT_TO_POINTER (9))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 2); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 8); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 9); |
| |
| g_queue_clear (q); |
| |
| /* Push onto the front of a non-empty queue. */ |
| g_queue_push_head (q, GINT_TO_POINTER (10)); |
| g_queue_push_nth_link (q, 0, g_list_prepend (NULL, GINT_TO_POINTER (11))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 2); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 11); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 10); |
| |
| g_queue_clear (q); |
| |
| /* Push into the middle of a non-empty queue. */ |
| g_queue_push_head (q, GINT_TO_POINTER (12)); |
| g_queue_push_head (q, GINT_TO_POINTER (13)); |
| g_queue_push_nth_link (q, 1, g_list_prepend (NULL, GINT_TO_POINTER (14))); |
| check_integrity (q); |
| g_assert_cmpint (g_queue_get_length (q), ==, 3); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 13); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 14); |
| g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 2)), ==, 12); |
| |
| g_queue_free (q); |
| } |
| |
| static void |
| test_free_full (void) |
| { |
| QueueItem *one, *two, *three; |
| GQueue *queue = NULL; |
| |
| queue = g_queue_new(); |
| g_queue_push_tail (queue, one = new_item (1)); |
| g_queue_push_tail (queue, two = new_item (2)); |
| g_queue_push_tail (queue, three = new_item (3)); |
| g_assert (!one->freed); |
| g_assert (!two->freed); |
| g_assert (!three->freed); |
| g_queue_free_full (queue, free_func); |
| g_assert (one->freed); |
| g_assert (two->freed); |
| g_assert (three->freed); |
| g_slice_free (QueueItem, one); |
| g_slice_free (QueueItem, two); |
| g_slice_free (QueueItem, three); |
| } |
| |
| static void |
| test_insert_sibling_link (void) |
| { |
| GQueue q = G_QUEUE_INIT; |
| GList a = {0}; |
| GList b = {0}; |
| GList c = {0}; |
| GList d = {0}; |
| GList e = {0}; |
| |
| g_queue_push_head_link (&q, &a); |
| g_queue_insert_after_link (&q, &a, &d); |
| g_queue_insert_before_link (&q, &d, &b); |
| g_queue_insert_after_link (&q, &b, &c); |
| g_queue_insert_after_link (&q, NULL, &e); |
| |
| g_assert_true (q.head == &e); |
| g_assert_true (q.tail == &d); |
| |
| g_assert_null (e.prev); |
| g_assert_true (e.next == &a); |
| |
| g_assert_true (a.prev == &e); |
| g_assert_true (a.next == &b); |
| |
| g_assert_true (b.prev == &a); |
| g_assert_true (b.next == &c); |
| |
| g_assert_true (c.prev == &b); |
| g_assert_true (c.next == &d); |
| |
| g_assert_true (d.prev == &c); |
| g_assert_null (d.next); |
| } |
| |
| int main (int argc, char *argv[]) |
| { |
| guint32 seed; |
| gchar *path; |
| |
| g_test_init (&argc, &argv, NULL); |
| |
| g_test_add_func ("/queue/basic", test_basic); |
| g_test_add_func ("/queue/copy", test_copy); |
| g_test_add_func ("/queue/off-by-one", test_off_by_one); |
| g_test_add_func ("/queue/find-custom", test_find_custom); |
| g_test_add_func ("/queue/static", test_static); |
| g_test_add_func ("/queue/clear", test_clear); |
| g_test_add_func ("/queue/free-full", test_free_full); |
| g_test_add_func ("/queue/clear-full", test_clear_full); |
| g_test_add_func ("/queue/clear-full/noop", test_clear_full_noop); |
| g_test_add_func ("/queue/insert-sibling-link", test_insert_sibling_link); |
| g_test_add_func ("/queue/push-nth-link", test_push_nth_link); |
| |
| seed = g_test_rand_int_range (0, G_MAXINT); |
| path = g_strdup_printf ("/queue/random/seed:%u", seed); |
| g_test_add_data_func (path, GUINT_TO_POINTER (seed), random_test); |
| g_free (path); |
| |
| return g_test_run (); |
| } |
