1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/glib/tsrc/BC/tests/queue-test.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,980 @@
1.4 +/* Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.*/
1.5 +#undef G_DISABLE_ASSERT
1.6 +#undef G_LOG_DOMAIN
1.7 +
1.8 +#ifdef HAVE_CONFIG_H
1.9 +# include <config.h>
1.10 +#endif
1.11 +#include <glib.h>
1.12 +#include <time.h>
1.13 +#include <stdlib.h>
1.14 +#include <stdio.h>
1.15 +
1.16 +#ifdef SYMBIAN
1.17 +#include "mrt2_glib2_test.h"
1.18 +#endif /*SYMBIAN*/
1.19 +
1.20 +#include <glib.h>
1.21 +
1.22 +
1.23 +static gboolean verbose = FALSE;
1.24 +
1.25 +
1.26 +static void
1.27 +check_integrity (GQueue *queue)
1.28 +{
1.29 + GList *list;
1.30 + GList *last;
1.31 + GList *links;
1.32 + GList *link;
1.33 + gint n;
1.34 +
1.35 + g_assert (queue->length < 4000000000u);
1.36 +
1.37 + g_assert (g_queue_get_length (queue) == queue->length);
1.38 +
1.39 + if (!queue->head)
1.40 + g_assert (!queue->tail);
1.41 + if (!queue->tail)
1.42 + g_assert (!queue->head);
1.43 +
1.44 + n = 0;
1.45 + last = NULL;
1.46 + for (list = queue->head; list != NULL; list = list->next)
1.47 + {
1.48 + if (!list->next)
1.49 + last = list;
1.50 + ++n;
1.51 + }
1.52 + g_assert (n == queue->length);
1.53 + g_assert (last == queue->tail);
1.54 +
1.55 + n = 0;
1.56 + last = NULL;
1.57 + for (list = queue->tail; list != NULL; list = list->prev)
1.58 + {
1.59 + if (!list->prev)
1.60 + last = list;
1.61 + ++n;
1.62 + }
1.63 + g_assert (n == queue->length);
1.64 + g_assert (last == queue->head);
1.65 +
1.66 + links = NULL;
1.67 + for (list = queue->head; list != NULL; list = list->next)
1.68 + links = g_list_prepend (links, list);
1.69 +
1.70 + link = links;
1.71 + for (list = queue->tail; list != NULL; list = list->prev)
1.72 + {
1.73 + g_assert (list == link->data);
1.74 + link = link->next;
1.75 + }
1.76 + g_list_free (links);
1.77 +
1.78 + links = NULL;
1.79 + for (list = queue->tail; list != NULL; list = list->prev)
1.80 + links = g_list_prepend (links, list);
1.81 +
1.82 + link = links;
1.83 + for (list = queue->head; list != NULL; list = list->next)
1.84 + {
1.85 + g_assert (list == link->data);
1.86 + link = link->next;
1.87 + }
1.88 + g_list_free (links);
1.89 +}
1.90 +
1.91 +static gboolean
1.92 +rnd_bool (void)
1.93 +{
1.94 + return g_random_int_range (0, 2);
1.95 +}
1.96 +
1.97 +static void
1.98 +check_max (gpointer elm, gpointer user_data)
1.99 +{
1.100 + gint *best = user_data;
1.101 + gint element = GPOINTER_TO_INT (elm);
1.102 +
1.103 + if (element > *best)
1.104 + *best = element;
1.105 +}
1.106 +
1.107 +static void
1.108 +check_min (gpointer elm, gpointer user_data)
1.109 +{
1.110 + gint *best = user_data;
1.111 + gint element = GPOINTER_TO_INT (elm);
1.112 +
1.113 + if (element < *best)
1.114 + *best = element;
1.115 +}
1.116 +
1.117 +static gint
1.118 +find_min (GQueue *queue)
1.119 +{
1.120 + gint min = G_MAXINT;
1.121 +
1.122 + g_queue_foreach (queue, check_min, &min);
1.123 +
1.124 + return min;
1.125 +}
1.126 +
1.127 +static gint
1.128 +find_max (GQueue *queue)
1.129 +{
1.130 + gint max = G_MININT;
1.131 +
1.132 + g_queue_foreach (queue, check_max, &max);
1.133 +
1.134 + return max;
1.135 +}
1.136 +
1.137 +static void
1.138 +delete_elm (gpointer elm, gpointer user_data)
1.139 +{
1.140 + g_queue_remove ((GQueue *)user_data, elm);
1.141 + check_integrity ((GQueue *)user_data);
1.142 +}
1.143 +
1.144 +static void
1.145 +delete_all (GQueue *queue)
1.146 +{
1.147 + g_queue_foreach (queue, delete_elm, queue);
1.148 +}
1.149 +
1.150 +static int
1.151 +compare_int (gconstpointer a, gconstpointer b, gpointer data)
1.152 +{
1.153 + int ai = GPOINTER_TO_INT (a);
1.154 + int bi = GPOINTER_TO_INT (b);
1.155 +
1.156 + if (ai > bi)
1.157 + return 1;
1.158 + else if (ai == bi)
1.159 + return 0;
1.160 + else
1.161 + return -1;
1.162 +}
1.163 +
1.164 +static gint
1.165 +get_random_position (GQueue *queue, gboolean allow_offlist)
1.166 +{
1.167 + int n;
1.168 + enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
1.169 +
1.170 + if (allow_offlist)
1.171 + where = g_random_int_range (OFF_QUEUE, LAST);
1.172 + else
1.173 + where = g_random_int_range (HEAD, LAST);
1.174 +
1.175 + switch (where)
1.176 + {
1.177 + case OFF_QUEUE:
1.178 + n = g_random_int ();
1.179 + break;
1.180 +
1.181 + case HEAD:
1.182 + n = 0;
1.183 + break;
1.184 +
1.185 + case TAIL:
1.186 + if (allow_offlist)
1.187 + n = queue->length;
1.188 + else
1.189 + n = queue->length - 1;
1.190 + break;
1.191 +
1.192 + case MIDDLE:
1.193 + if (queue->length == 0)
1.194 + n = 0;
1.195 + else
1.196 + n = g_random_int_range (0, queue->length);
1.197 + break;
1.198 +
1.199 + default:
1.200 + g_assert_not_reached();
1.201 + n = 100;
1.202 + break;
1.203 +
1.204 + }
1.205 +
1.206 + return n;
1.207 +}
1.208 +
1.209 +static void
1.210 +random_test (int seed)
1.211 +{
1.212 + typedef enum {
1.213 + IS_EMPTY, GET_LENGTH, REVERSE, COPY,
1.214 + FOREACH, FIND, FIND_CUSTOM, SORT,
1.215 + PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
1.216 + POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
1.217 + PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
1.218 + INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
1.219 + PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
1.220 + POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
1.221 + LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
1.222 + } QueueOp;
1.223 +
1.224 +#define N_ITERATIONS 500
1.225 +#define N_QUEUES 3
1.226 +
1.227 +#define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
1.228 +
1.229 + typedef struct QueueInfo QueueInfo;
1.230 + struct QueueInfo
1.231 + {
1.232 + GQueue *queue;
1.233 + GList *tail;
1.234 + GList *head;
1.235 + guint length;
1.236 + };
1.237 +
1.238 + gint i;
1.239 + QueueOp op;
1.240 + QueueInfo queues[N_QUEUES];
1.241 +
1.242 + if (verbose)
1.243 + g_print ("seed: %d\n", seed);
1.244 +
1.245 + g_random_set_seed (seed);
1.246 +
1.247 + for (i = 0; i < N_QUEUES; ++i)
1.248 + {
1.249 + queues[i].queue = g_queue_new ();
1.250 + queues[i].head = NULL;
1.251 + queues[i].tail = NULL;
1.252 + queues[i].length = 0;
1.253 + }
1.254 +
1.255 + for (i = 0; i < N_ITERATIONS; ++i)
1.256 + {
1.257 + int j;
1.258 + QueueInfo *qinf = RANDOM_QUEUE();
1.259 + GQueue *q = qinf->queue;
1.260 + op = g_random_int_range (IS_EMPTY, LAST_OP);
1.261 +
1.262 + g_assert (qinf->head == q->head);
1.263 + g_assert (qinf->tail == q->tail);
1.264 + g_assert (qinf->length == q->length);
1.265 +
1.266 + switch (op)
1.267 + {
1.268 + case IS_EMPTY:
1.269 + {
1.270 + if (g_queue_is_empty (qinf->queue))
1.271 + {
1.272 + g_assert (q->head == NULL);
1.273 + g_assert (q->tail == NULL);
1.274 + g_assert (q->length == 0);
1.275 + }
1.276 + else
1.277 + {
1.278 + g_assert (q->head);
1.279 + g_assert (q->tail);
1.280 + g_assert (q->length > 0);
1.281 + }
1.282 + }
1.283 + break;
1.284 + case GET_LENGTH:
1.285 + {
1.286 + int l;
1.287 +
1.288 + l = g_queue_get_length (q);
1.289 +
1.290 + g_assert (qinf->length == q->length);
1.291 + g_assert (qinf->length == l);
1.292 + }
1.293 + break;
1.294 + case REVERSE:
1.295 + g_queue_reverse (q);
1.296 + g_assert (qinf->tail == q->head);
1.297 + g_assert (qinf->head == q->tail);
1.298 + g_assert (qinf->length == q->length);
1.299 + qinf->tail = q->tail;
1.300 + qinf->head = q->head;
1.301 + break;
1.302 + case COPY:
1.303 + {
1.304 + QueueInfo *random_queue = RANDOM_QUEUE();
1.305 + GQueue *new_queue = g_queue_copy (random_queue->queue);
1.306 +
1.307 + g_queue_free (qinf->queue);
1.308 + q = qinf->queue = new_queue;
1.309 + qinf->head = new_queue->head;
1.310 + qinf->tail = g_list_last (new_queue->head);
1.311 + qinf->length = new_queue->length;
1.312 + }
1.313 + break;
1.314 + case FOREACH:
1.315 + delete_all (q);
1.316 + qinf->head = NULL;
1.317 + qinf->tail = NULL;
1.318 + qinf->length = 0;
1.319 + break;
1.320 + case FIND:
1.321 + {
1.322 + gboolean find_existing = rnd_bool ();
1.323 + int first = find_max (q);
1.324 + int second = find_min (q);
1.325 +
1.326 + if (q->length == 0)
1.327 + find_existing = FALSE;
1.328 +
1.329 + if (!find_existing)
1.330 + first++;
1.331 + if (!find_existing)
1.332 + second--;
1.333 +
1.334 + if (find_existing)
1.335 + {
1.336 + g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
1.337 + g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
1.338 + }
1.339 + else
1.340 + {
1.341 + g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
1.342 + g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
1.343 + }
1.344 + }
1.345 + break;
1.346 + case FIND_CUSTOM:
1.347 + break;
1.348 + case SORT:
1.349 + {
1.350 + if (!g_queue_is_empty (q))
1.351 + {
1.352 + int max = find_max (q);
1.353 + int min = find_min (q);
1.354 + g_queue_remove_all (q, GINT_TO_POINTER (max));
1.355 + check_integrity (q);
1.356 + g_queue_remove_all (q, GINT_TO_POINTER (min));
1.357 + check_integrity (q);
1.358 + g_queue_push_head (q, GINT_TO_POINTER (max));
1.359 + if (max != min)
1.360 + g_queue_push_head (q, GINT_TO_POINTER (min));
1.361 + qinf->length = q->length;
1.362 + }
1.363 +
1.364 + check_integrity (q);
1.365 +
1.366 + g_queue_sort (q, compare_int, NULL);
1.367 +
1.368 + check_integrity (q);
1.369 +
1.370 + qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
1.371 + qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
1.372 +
1.373 + g_assert (qinf->tail == q->tail);
1.374 + }
1.375 + break;
1.376 + case PUSH_HEAD:
1.377 + {
1.378 + int x = g_random_int_range (0, 435435);
1.379 + g_queue_push_head (q, GINT_TO_POINTER (x));
1.380 + if (!qinf->head)
1.381 + qinf->tail = qinf->head = q->head;
1.382 + else
1.383 + qinf->head = qinf->head->prev;
1.384 + qinf->length++;
1.385 + }
1.386 + break;
1.387 + case PUSH_TAIL:
1.388 + {
1.389 + int x = g_random_int_range (0, 236546);
1.390 + g_queue_push_tail (q, GINT_TO_POINTER (x));
1.391 + if (!qinf->tail)
1.392 + qinf->tail = qinf->head = q->head;
1.393 + else
1.394 + qinf->tail = qinf->tail->next;
1.395 + qinf->length++;
1.396 + }
1.397 + break;
1.398 + case PUSH_NTH:
1.399 + {
1.400 + int pos = get_random_position (q, TRUE);
1.401 + int x = g_random_int_range (0, 236546);
1.402 + g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
1.403 + if (qinf->head && qinf->head->prev)
1.404 + qinf->head = qinf->head->prev;
1.405 + else
1.406 + qinf->head = q->head;
1.407 + if (qinf->tail && qinf->tail->next)
1.408 + qinf->tail = qinf->tail->next;
1.409 + else
1.410 + qinf->tail = g_list_last (qinf->head);
1.411 + qinf->length++;
1.412 + }
1.413 + break;
1.414 + case POP_HEAD:
1.415 + if (qinf->head)
1.416 + qinf->head = qinf->head->next;
1.417 + if (!qinf->head)
1.418 + qinf->tail = NULL;
1.419 + qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
1.420 + g_queue_pop_head (q);
1.421 + break;
1.422 + case POP_TAIL:
1.423 + if (qinf->tail)
1.424 + qinf->tail = qinf->tail->prev;
1.425 + if (!qinf->tail)
1.426 + qinf->head = NULL;
1.427 + qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
1.428 + g_queue_pop_tail (q);
1.429 + break;
1.430 + case POP_NTH:
1.431 + if (!g_queue_is_empty (q))
1.432 + {
1.433 + int n = get_random_position (q, TRUE);
1.434 + gpointer elm = g_queue_peek_nth (q, n);
1.435 +
1.436 + if (n == q->length - 1)
1.437 + qinf->tail = qinf->tail->prev;
1.438 +
1.439 + if (n == 0)
1.440 + qinf->head = qinf->head->next;
1.441 +
1.442 + if (n >= 0 && n < q->length)
1.443 + qinf->length--;
1.444 +
1.445 + g_assert (elm == g_queue_pop_nth (q, n));
1.446 + }
1.447 + break;
1.448 + case PEEK_HEAD:
1.449 + if (qinf->head)
1.450 + g_assert (qinf->head->data == g_queue_peek_head (q));
1.451 + else
1.452 + g_assert (g_queue_peek_head (q) == NULL);
1.453 + break;
1.454 + case PEEK_TAIL:
1.455 + if (qinf->head)
1.456 + g_assert (qinf->tail->data == g_queue_peek_tail (q));
1.457 + else
1.458 + g_assert (g_queue_peek_tail (q) == NULL);
1.459 + break;
1.460 + case PEEK_NTH:
1.461 + if (g_queue_is_empty (q))
1.462 + {
1.463 + for (j = -10; j < 10; ++j)
1.464 + g_assert (g_queue_peek_nth (q, j) == NULL);
1.465 + }
1.466 + else
1.467 + {
1.468 + GList *list;
1.469 + int n = get_random_position (q, TRUE);
1.470 + if (n < 0 || n >= q->length)
1.471 + {
1.472 + g_assert (g_queue_peek_nth (q, n) == NULL);
1.473 + }
1.474 + else
1.475 + {
1.476 + list = qinf->head;
1.477 + for (j = 0; j < n; ++j)
1.478 + list = list->next;
1.479 +
1.480 + g_assert (list->data == g_queue_peek_nth (q, n));
1.481 + }
1.482 + }
1.483 + break;
1.484 + case INDEX:
1.485 + case LINK_INDEX:
1.486 + {
1.487 + int x = g_random_int_range (0, 386538);
1.488 + int n;
1.489 + GList *list;
1.490 +
1.491 + g_queue_remove_all (q, GINT_TO_POINTER (x));
1.492 + check_integrity (q);
1.493 + g_queue_push_tail (q, GINT_TO_POINTER (x));
1.494 + check_integrity (q);
1.495 + g_queue_sort (q, compare_int, NULL);
1.496 + check_integrity (q);
1.497 +
1.498 + n = 0;
1.499 + for (list = q->head; list != NULL; list = list->next)
1.500 + {
1.501 + if (list->data == GINT_TO_POINTER (x))
1.502 + break;
1.503 + n++;
1.504 + }
1.505 + g_assert (list);
1.506 + g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
1.507 + g_queue_link_index (q, list));
1.508 + g_assert (g_queue_link_index (q, list) == n);
1.509 +
1.510 + qinf->head = q->head;
1.511 + qinf->tail = q->tail;
1.512 + qinf->length = q->length;
1.513 + }
1.514 + break;
1.515 + case REMOVE:
1.516 + if (!g_queue_is_empty (q))
1.517 + g_queue_remove (q, qinf->tail->data);
1.518 + if (!g_queue_is_empty (q))
1.519 + g_queue_remove (q, qinf->head->data);
1.520 + if (!g_queue_is_empty (q))
1.521 + g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
1.522 +
1.523 + qinf->head = q->head;
1.524 + qinf->tail = q->tail;
1.525 + qinf->length = q->length;
1.526 + break;
1.527 + case REMOVE_ALL:
1.528 + if (!g_queue_is_empty (q))
1.529 + g_queue_remove_all (q, qinf->tail->data);
1.530 + if (!g_queue_is_empty (q))
1.531 + g_queue_remove_all (q, qinf->head->data);
1.532 + if (!g_queue_is_empty (q))
1.533 + g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
1.534 +
1.535 + qinf->head = q->head;
1.536 + qinf->tail = q->tail;
1.537 + qinf->length = q->length;
1.538 + break;
1.539 + case INSERT_BEFORE:
1.540 + if (!g_queue_is_empty (q))
1.541 + {
1.542 + gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
1.543 +
1.544 + g_queue_insert_before (q, qinf->tail, x);
1.545 + g_queue_insert_before (q, qinf->head, x);
1.546 + g_queue_insert_before (q, g_queue_find (q, x), x);
1.547 + }
1.548 + qinf->head = q->head;
1.549 + qinf->tail = q->tail;
1.550 + qinf->length = q->length;
1.551 + break;
1.552 + case INSERT_AFTER:
1.553 + if (!g_queue_is_empty (q))
1.554 + {
1.555 + gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
1.556 +
1.557 + g_queue_insert_after (q, qinf->tail, x);
1.558 + g_queue_insert_after (q, qinf->head, x);
1.559 + g_queue_insert_after (q, g_queue_find (q, x), x);
1.560 + }
1.561 + qinf->head = q->head;
1.562 + qinf->tail = q->tail;
1.563 + qinf->length = q->length;
1.564 + break;
1.565 + case INSERT_SORTED:
1.566 + {
1.567 + int max = find_max (q);
1.568 + int min = find_min (q);
1.569 +
1.570 + if (g_queue_is_empty (q))
1.571 + {
1.572 + max = 345;
1.573 + min = -12;
1.574 + }
1.575 +
1.576 + g_queue_sort (q, compare_int, NULL);
1.577 + check_integrity (q);
1.578 + g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
1.579 + check_integrity (q);
1.580 + g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
1.581 + g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
1.582 + check_integrity (q);
1.583 + g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
1.584 + qinf->head = q->head;
1.585 + qinf->tail = q->tail;
1.586 + qinf->length = q->length;
1.587 + }
1.588 + break;
1.589 + case PUSH_HEAD_LINK:
1.590 + {
1.591 + GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
1.592 + g_queue_push_head_link (q, link);
1.593 + if (!qinf->tail)
1.594 + qinf->tail = link;
1.595 + qinf->head = link;
1.596 + qinf->length++;
1.597 + }
1.598 + break;
1.599 + case PUSH_TAIL_LINK:
1.600 + {
1.601 + GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
1.602 + g_queue_push_tail_link (q, link);
1.603 + if (!qinf->head)
1.604 + qinf->head = link;
1.605 + qinf->tail = link;
1.606 + qinf->length++;
1.607 + }
1.608 + break;
1.609 + case PUSH_NTH_LINK:
1.610 + {
1.611 + GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
1.612 + gint n = get_random_position (q, TRUE);
1.613 + g_queue_push_nth_link (q, n, link);
1.614 +
1.615 + if (qinf->head && qinf->head->prev)
1.616 + qinf->head = qinf->head->prev;
1.617 + else
1.618 + qinf->head = q->head;
1.619 + if (qinf->tail && qinf->tail->next)
1.620 + qinf->tail = qinf->tail->next;
1.621 + else
1.622 + qinf->tail = g_list_last (qinf->head);
1.623 + qinf->length++;
1.624 + }
1.625 + break;
1.626 + case POP_HEAD_LINK:
1.627 + if (!g_queue_is_empty (q))
1.628 + {
1.629 + qinf->head = qinf->head->next;
1.630 + if (!qinf->head)
1.631 + qinf->tail = NULL;
1.632 + qinf->length--;
1.633 + g_list_free (g_queue_pop_head_link (q));
1.634 + }
1.635 + break;
1.636 + case POP_TAIL_LINK:
1.637 + if (!g_queue_is_empty (q))
1.638 + {
1.639 + qinf->tail = qinf->tail->prev;
1.640 + if (!qinf->tail)
1.641 + qinf->head = NULL;
1.642 + qinf->length--;
1.643 + g_list_free (g_queue_pop_tail_link (q));
1.644 + }
1.645 + break;
1.646 + case POP_NTH_LINK:
1.647 + if (g_queue_is_empty (q))
1.648 + g_assert (g_queue_pop_nth_link (q, 200) == NULL);
1.649 + else
1.650 + {
1.651 + int n = get_random_position (q, FALSE);
1.652 +
1.653 + if (n == g_queue_get_length (q) - 1)
1.654 + qinf->tail = qinf->tail->prev;
1.655 +
1.656 + if (n == 0)
1.657 + qinf->head = qinf->head->next;
1.658 +
1.659 + qinf->length--;
1.660 +
1.661 + g_list_free (g_queue_pop_nth_link (q, n));
1.662 + }
1.663 + break;
1.664 + case PEEK_HEAD_LINK:
1.665 + if (g_queue_is_empty (q))
1.666 + g_assert (g_queue_peek_head_link (q) == NULL);
1.667 + else
1.668 + g_assert (g_queue_peek_head_link (q) == qinf->head);
1.669 + break;
1.670 + case PEEK_TAIL_LINK:
1.671 + if (g_queue_is_empty (q))
1.672 + g_assert (g_queue_peek_tail_link (q) == NULL);
1.673 + else
1.674 + g_assert (g_queue_peek_tail_link (q) == qinf->tail);
1.675 + break;
1.676 + case PEEK_NTH_LINK:
1.677 + if (g_queue_is_empty(q))
1.678 + g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
1.679 + else
1.680 + {
1.681 + gint n = get_random_position (q, FALSE);
1.682 + GList *link;
1.683 +
1.684 + link = q->head;
1.685 + for (j = 0; j < n; ++j)
1.686 + link = link->next;
1.687 +
1.688 + g_assert (g_queue_peek_nth_link (q, n) == link);
1.689 + }
1.690 + break;
1.691 + case UNLINK:
1.692 + if (!g_queue_is_empty (q))
1.693 + {
1.694 + gint n = g_random_int_range (0, g_queue_get_length (q));
1.695 + GList *link;
1.696 +
1.697 + link = q->head;
1.698 + for (j = 0; j < n; ++j)
1.699 + link = link->next;
1.700 +
1.701 + g_queue_unlink (q, link);
1.702 + check_integrity (q);
1.703 +
1.704 + g_list_free (link);
1.705 +
1.706 + qinf->head = q->head;
1.707 + qinf->tail = q->tail;
1.708 + qinf->length--;
1.709 + }
1.710 + break;
1.711 + case DELETE_LINK:
1.712 + if (!g_queue_is_empty (q))
1.713 + {
1.714 + gint n = g_random_int_range (0, g_queue_get_length (q));
1.715 + GList *link;
1.716 +
1.717 + link = q->head;
1.718 + for (j = 0; j < n; ++j)
1.719 + link = link->next;
1.720 +
1.721 + g_queue_delete_link (q, link);
1.722 + check_integrity (q);
1.723 +
1.724 + qinf->head = q->head;
1.725 + qinf->tail = q->tail;
1.726 + qinf->length--;
1.727 + }
1.728 + break;
1.729 + case LAST_OP:
1.730 + default:
1.731 + g_assert_not_reached();
1.732 + break;
1.733 + }
1.734 +
1.735 + if (qinf->head != q->head ||
1.736 + qinf->tail != q->tail ||
1.737 + qinf->length != q->length)
1.738 + g_print ("op: %d\n", op);
1.739 +
1.740 + g_assert (qinf->head == q->head);
1.741 + g_assert (qinf->tail == q->tail);
1.742 + g_assert (qinf->length == q->length);
1.743 +
1.744 + for (j = 0; j < N_QUEUES; ++j)
1.745 + check_integrity (queues[j].queue);
1.746 + }
1.747 +
1.748 + for (i = 0; i < N_QUEUES; ++i)
1.749 + g_queue_free (queues[i].queue);
1.750 +}
1.751 +
1.752 +static void
1.753 +remove_item (gpointer data, gpointer q)
1.754 +{
1.755 + GQueue *queue = q;
1.756 +
1.757 + g_queue_remove (queue, data);
1.758 +}
1.759 +
1.760 +int main(int argc, gchar *args[])
1.761 +{
1.762 + GQueue *q, *q2;
1.763 + GList *node;
1.764 + gpointer data;
1.765 + int i;
1.766 +
1.767 + #ifdef SYMBIAN
1.768 + g_log_set_handler (NULL, G_LOG_FLAG_FATAL| G_LOG_FLAG_RECURSION | G_LOG_LEVEL_CRITICAL | G_LOG_LEVEL_WARNING | G_LOG_LEVEL_MESSAGE | G_LOG_LEVEL_INFO | G_LOG_LEVEL_DEBUG, &mrtLogHandler, NULL);
1.769 + g_set_print_handler(mrtPrintHandler);
1.770 + #endif /*SYMBIAN*/
1.771 +
1.772 + if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v')
1.773 + verbose = TRUE;
1.774 +
1.775 + q = g_queue_new ();
1.776 +
1.777 + g_assert (g_queue_is_empty (q) == TRUE);
1.778 +
1.779 + g_queue_push_head (q, GINT_TO_POINTER (2));
1.780 + check_integrity (q);
1.781 + g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
1.782 + check_integrity (q);
1.783 + g_assert (g_queue_is_empty (q) == FALSE);
1.784 + check_integrity (q);
1.785 + g_assert (g_list_length (q->head) == 1);
1.786 + g_assert (q->head == q->tail);
1.787 + g_queue_push_head (q, GINT_TO_POINTER (1));
1.788 + check_integrity (q);
1.789 + g_assert (q->head->next == q->tail);
1.790 + g_assert (q->tail->prev == q->head);
1.791 + g_assert (g_list_length (q->head) == 2);
1.792 + check_integrity (q);
1.793 + g_assert (q->tail->data == GINT_TO_POINTER (2));
1.794 + g_assert (q->head->data == GINT_TO_POINTER (1));
1.795 + check_integrity (q);
1.796 + g_queue_push_tail (q, GINT_TO_POINTER (3));
1.797 + g_assert (g_list_length (q->head) == 3);
1.798 + g_assert (q->head->data == GINT_TO_POINTER (1));
1.799 + g_assert (q->head->next->data == GINT_TO_POINTER (2));
1.800 + g_assert (q->head->next->next == q->tail);
1.801 + g_assert (q->head->next == q->tail->prev);
1.802 + g_assert (q->tail->data == GINT_TO_POINTER (3));
1.803 + g_queue_push_tail (q, GINT_TO_POINTER (4));
1.804 + check_integrity (q);
1.805 + g_assert (g_list_length (q->head) == 4);
1.806 + g_assert (q->head->data == GINT_TO_POINTER (1));
1.807 + g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
1.808 + g_queue_push_tail (q, GINT_TO_POINTER (5));
1.809 + check_integrity (q);
1.810 + g_assert (g_list_length (q->head) == 5);
1.811 +
1.812 + g_assert (g_queue_is_empty (q) == FALSE);
1.813 + check_integrity (q);
1.814 +
1.815 + g_assert (q->length == 5);
1.816 + g_assert (q->head->prev == NULL);
1.817 + g_assert (q->head->data == GINT_TO_POINTER (1));
1.818 + g_assert (q->head->next->data == GINT_TO_POINTER (2));
1.819 + g_assert (q->head->next->next->data == GINT_TO_POINTER (3));
1.820 + g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4));
1.821 + g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5));
1.822 + g_assert (q->head->next->next->next->next->next == NULL);
1.823 + g_assert (q->head->next->next->next->next == q->tail);
1.824 + g_assert (q->tail->data == GINT_TO_POINTER (5));
1.825 + g_assert (q->tail->prev->data == GINT_TO_POINTER (4));
1.826 + g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3));
1.827 + g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2));
1.828 + g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1));
1.829 + g_assert (q->tail->prev->prev->prev->prev->prev == NULL);
1.830 + g_assert (q->tail->prev->prev->prev->prev == q->head);
1.831 + g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
1.832 + g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
1.833 +
1.834 + g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
1.835 + check_integrity (q);
1.836 + g_assert (g_list_length (q->head) == 4 && q->length == 4);
1.837 + g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
1.838 + check_integrity (q);
1.839 + g_assert (g_list_length (q->head) == 3);
1.840 + g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
1.841 + check_integrity (q);
1.842 + g_assert (g_list_length (q->head) == 2);
1.843 + g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
1.844 + check_integrity (q);
1.845 + g_assert (g_list_length (q->head) == 1);
1.846 + g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
1.847 + check_integrity (q);
1.848 + g_assert (g_list_length (q->head) == 0);
1.849 + g_assert (g_queue_pop_tail (q) == NULL);
1.850 + check_integrity (q);
1.851 + g_assert (g_list_length (q->head) == 0);
1.852 + g_assert (g_queue_pop_head (q) == NULL);
1.853 + check_integrity (q);
1.854 + g_assert (g_list_length (q->head) == 0);
1.855 +
1.856 + g_assert (g_queue_is_empty (q) == TRUE);
1.857 + check_integrity (q);
1.858 +
1.859 + /************************/
1.860 +
1.861 + g_queue_push_head (q, GINT_TO_POINTER (1));
1.862 + check_integrity (q);
1.863 + g_assert (g_list_length (q->head) == 1 && 1 == q->length);
1.864 + g_queue_push_head (q, GINT_TO_POINTER (2));
1.865 + check_integrity (q);
1.866 + g_assert (g_list_length (q->head) == 2 && 2 == q->length);
1.867 + g_queue_push_head (q, GINT_TO_POINTER (3));
1.868 + check_integrity (q);
1.869 + g_assert (g_list_length (q->head) == 3 && 3 == q->length);
1.870 + g_queue_push_head (q, GINT_TO_POINTER (4));
1.871 + check_integrity (q);
1.872 + g_assert (g_list_length (q->head) == 4 && 4 == q->length);
1.873 + g_queue_push_head (q, GINT_TO_POINTER (5));
1.874 + check_integrity (q);
1.875 + g_assert (g_list_length (q->head) == 5 && 5 == q->length);
1.876 +
1.877 + g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
1.878 + check_integrity (q);
1.879 + g_assert (g_list_length (q->head) == 4);
1.880 + node = q->tail;
1.881 + g_assert (node == g_queue_pop_tail_link (q));
1.882 + check_integrity (q);
1.883 + g_assert (g_list_length (q->head) == 3);
1.884 + data = q->head->data;
1.885 + g_assert (data == g_queue_pop_head (q));
1.886 + check_integrity (q);
1.887 + g_assert (g_list_length (q->head) == 2);
1.888 + g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
1.889 + check_integrity (q);
1.890 + g_assert (g_list_length (q->head) == 1);
1.891 + g_assert (q->head == q->tail);
1.892 + g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
1.893 + check_integrity (q);
1.894 + g_assert (g_list_length (q->head) == 0);
1.895 + g_assert (g_queue_pop_head (q) == NULL);
1.896 + check_integrity (q);
1.897 + g_assert (g_queue_pop_head_link (q) == NULL);
1.898 + check_integrity (q);
1.899 + g_assert (g_list_length (q->head) == 0);
1.900 + g_assert (g_queue_pop_tail_link (q) == NULL);
1.901 + check_integrity (q);
1.902 + g_assert (g_list_length (q->head) == 0);
1.903 +
1.904 + /* */
1.905 + g_queue_reverse (q);
1.906 + check_integrity (q);
1.907 + g_assert (g_list_length (q->head) == 0);
1.908 +
1.909 + q2 = g_queue_copy (q);
1.910 + check_integrity (q);
1.911 + check_integrity (q2);
1.912 + g_assert (g_list_length (q->head) == 0);
1.913 + g_assert (g_list_length (q2->head) == 0);
1.914 + g_queue_sort (q, compare_int, NULL);
1.915 + check_integrity (q2);
1.916 + check_integrity (q);
1.917 + g_queue_sort (q2, compare_int, NULL);
1.918 + check_integrity (q2);
1.919 + check_integrity (q);
1.920 +
1.921 + for (i = 0; i < 200; ++i)
1.922 + {
1.923 + g_queue_push_nth (q, GINT_TO_POINTER (i), i);
1.924 + g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
1.925 + check_integrity (q);
1.926 + check_integrity (q2);
1.927 + }
1.928 +
1.929 + for (i = 0; i < 200; ++i)
1.930 + {
1.931 + g_queue_remove (q, GINT_TO_POINTER (i));
1.932 + check_integrity (q);
1.933 + check_integrity (q2);
1.934 + }
1.935 +
1.936 + for (i = 0; i < 200; ++i)
1.937 + {
1.938 + GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
1.939 +
1.940 + g_queue_push_nth_link (q, i, l);
1.941 + check_integrity (q);
1.942 + check_integrity (q2);
1.943 + g_queue_reverse (q);
1.944 + check_integrity (q);
1.945 + check_integrity (q2);
1.946 + }
1.947 +
1.948 + g_queue_free (q2);
1.949 + q2 = g_queue_copy (q);
1.950 +
1.951 + g_queue_foreach (q2, remove_item, q2);
1.952 + check_integrity (q2);
1.953 + check_integrity (q);
1.954 +
1.955 + /* some checks for off by one errors */
1.956 + g_queue_push_tail (q, GINT_TO_POINTER (1234));
1.957 + check_integrity (q);
1.958 + node = g_queue_peek_tail_link (q);
1.959 + g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
1.960 + node = g_queue_peek_nth_link (q, g_queue_get_length (q));
1.961 + g_assert (node == NULL);
1.962 + node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
1.963 + g_assert (node->data == GINT_TO_POINTER (1234));
1.964 + node = g_queue_pop_nth_link (q, g_queue_get_length (q));
1.965 + g_assert (node == NULL);
1.966 + node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
1.967 + g_assert (node != NULL && node->data == GINT_TO_POINTER (1234));
1.968 +
1.969 + g_queue_free (q);
1.970 +
1.971 + if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v')
1.972 + random_test (strtol (args[2], NULL, 0));
1.973 + if (argc > 1)
1.974 + random_test (strtol (args[1], NULL, 0));
1.975 + else
1.976 + random_test (time (0));
1.977 +#ifdef SYMBIAN
1.978 + testResultXml("queue-test");
1.979 +#endif /* EMULATOR */
1.980 +
1.981 + return 0;
1.982 +}
1.983 +