Branch data Line data Source code
1 : : /*
2 : : * Copyright 1999 Jeff Garzik
3 : : * Copyright 1999 Tim Janik
4 : : * Copyright 2004 Soeren Sandmann
5 : : * Copyright 2006 Martyn James Russell
6 : : * Copyright 2004, 2005, 2010, 2019 Red Hat, Inc.
7 : : * Copyright 2011 Samsung
8 : : * Copyright 2018 Tapasweni Pathak
9 : : * Copyright 2019 Endless Mobile, Inc.
10 : : * Copyright 2020 Emmanuel Fleury
11 : : *
12 : : * SPDX-License-Identifier: LGPL-2.1-or-later
13 : : *
14 : : * This program is free software; you can redistribute it and/or
15 : : * modify it under the terms of the GNU Lesser General Public
16 : : * License as published by the Free Software Foundation; either
17 : : * version 2.1 of the License, or (at your option) any later version.
18 : : *
19 : : * See the included COPYING file for more information.
20 : : */
21 : :
22 : : #undef G_DISABLE_ASSERT
23 : : #undef G_LOG_DOMAIN
24 : :
25 : : #include <time.h>
26 : : #include <stdlib.h>
27 : :
28 : : #include <glib.h>
29 : :
30 : :
31 : : static void
32 : 358784 : check_integrity (GQueue *queue)
33 : : {
34 : : GList *list;
35 : : GList *last;
36 : : GList *links;
37 : : GList *link;
38 : : guint n;
39 : :
40 : 358784 : g_assert_cmpuint (queue->length, <, 4000000000u);
41 : :
42 : 358784 : g_assert_cmpuint (g_queue_get_length (queue), ==, queue->length);
43 : :
44 [ + + ]: 358784 : if (!queue->head)
45 : 85224 : g_assert_null (queue->tail);
46 [ + + ]: 358784 : if (!queue->tail)
47 : 85224 : g_assert_null (queue->head);
48 : :
49 : 358784 : n = 0;
50 : 358784 : last = NULL;
51 [ + + ]: 2586352 : for (list = queue->head; list != NULL; list = list->next)
52 : : {
53 [ + + ]: 2227568 : if (!list->next)
54 : 273560 : last = list;
55 : 2227568 : ++n;
56 : : }
57 : 358784 : g_assert_cmpuint (n, ==, queue->length);
58 : 358784 : g_assert_true (last == queue->tail);
59 : :
60 : 358784 : n = 0;
61 : 358784 : last = NULL;
62 [ + + ]: 2586352 : for (list = queue->tail; list != NULL; list = list->prev)
63 : : {
64 [ + + ]: 2227568 : if (!list->prev)
65 : 273560 : last = list;
66 : 2227568 : ++n;
67 : : }
68 : 358784 : g_assert_cmpuint (n, ==, queue->length);
69 : 358784 : g_assert_true (last == queue->head);
70 : :
71 : 358784 : links = NULL;
72 [ + + ]: 2586352 : for (list = queue->head; list != NULL; list = list->next)
73 : 2227568 : links = g_list_prepend (links, list);
74 : :
75 : 358784 : link = links;
76 [ + + ]: 2586352 : for (list = queue->tail; list != NULL; list = list->prev)
77 : : {
78 : 2227568 : g_assert_true (list == link->data);
79 : 2227568 : link = link->next;
80 : : }
81 : 358784 : g_list_free (links);
82 : :
83 : 358784 : links = NULL;
84 [ + + ]: 2586352 : for (list = queue->tail; list != NULL; list = list->prev)
85 : 2227568 : links = g_list_prepend (links, list);
86 : :
87 : 358784 : link = links;
88 [ + + ]: 2586352 : for (list = queue->head; list != NULL; list = list->next)
89 : : {
90 : 2227568 : g_assert_true (list == link->data);
91 : 2227568 : link = link->next;
92 : : }
93 : 358784 : g_list_free (links);
94 : 358784 : }
95 : :
96 : : static gboolean
97 : 2854 : rnd_bool (void)
98 : : {
99 : 2854 : return g_random_int_range (0, 2);
100 : : }
101 : :
102 : : static void
103 : 64700 : check_max (gpointer elm, gpointer user_data)
104 : : {
105 : 64700 : gint *best = user_data;
106 : 64700 : gint element = GPOINTER_TO_INT (elm);
107 : :
108 [ + + ]: 64700 : if (element > *best)
109 : 35588 : *best = element;
110 : 64700 : }
111 : :
112 : : static void
113 : 64700 : check_min (gpointer elm, gpointer user_data)
114 : : {
115 : 64700 : gint *best = user_data;
116 : 64700 : gint element = GPOINTER_TO_INT (elm);
117 : :
118 [ + + ]: 64700 : if (element < *best)
119 : 13084 : *best = element;
120 : 64700 : }
121 : :
122 : : static gint
123 : 10573 : find_min (GQueue *queue)
124 : : {
125 : 10573 : gint min = G_MAXINT;
126 : :
127 : 10573 : g_queue_foreach (queue, check_min, &min);
128 : :
129 : 10573 : return min;
130 : : }
131 : :
132 : : static gint
133 : 10573 : find_max (GQueue *queue)
134 : : {
135 : 10573 : gint max = G_MININT;
136 : :
137 : 10573 : g_queue_foreach (queue, check_max, &max);
138 : :
139 : 10573 : return max;
140 : : }
141 : :
142 : : static void
143 : 17297 : delete_elm (gpointer elm, gpointer user_data)
144 : : {
145 : 17297 : g_queue_remove ((GQueue *)user_data, elm);
146 : 17297 : check_integrity ((GQueue *)user_data);
147 : 17297 : }
148 : :
149 : : static void
150 : 2788 : delete_all (GQueue *queue)
151 : : {
152 : 2788 : g_queue_foreach (queue, delete_elm, queue);
153 : 2788 : }
154 : :
155 : : static int
156 : 164714 : compare_int (gconstpointer a, gconstpointer b, gpointer data)
157 : : {
158 : 164714 : int ai = GPOINTER_TO_INT (a);
159 : 164714 : int bi = GPOINTER_TO_INT (b);
160 : :
161 [ + + ]: 164714 : if (ai > bi)
162 : 50917 : return 1;
163 [ + + ]: 113797 : else if (ai == bi)
164 : 22968 : return 0;
165 : : else
166 : 90829 : return -1;
167 : : }
168 : :
169 : : static guint
170 : 17352 : get_random_position (GQueue *queue, gboolean allow_offlist)
171 : : {
172 : : enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
173 : :
174 [ + + ]: 17352 : if (allow_offlist)
175 : 12993 : where = g_random_int_range (OFF_QUEUE, LAST);
176 : : else
177 : 4359 : where = g_random_int_range (HEAD, LAST);
178 : :
179 [ + + + + : 17352 : switch (where)
- ]
180 : : {
181 : 3265 : case OFF_QUEUE:
182 : 3265 : return g_random_int ();
183 : :
184 : 4684 : case HEAD:
185 : 4684 : return 0;
186 : :
187 : 4776 : case TAIL:
188 [ + + ]: 4776 : if (allow_offlist)
189 : 3338 : return queue->length;
190 [ + - ]: 1438 : else if (queue->length > 0)
191 : 1438 : return queue->length - 1;
192 : : else
193 : 0 : return 0;
194 : :
195 : 4627 : case MIDDLE:
196 [ + + ]: 4627 : if (queue->length == 0)
197 : 369 : return 0;
198 : : else
199 : 4258 : return g_random_int_range (0, queue->length);
200 : :
201 : 0 : default:
202 : : g_assert_not_reached ();
203 : : }
204 : : }
205 : :
206 : : static void
207 : 1 : random_test (gconstpointer d)
208 : : {
209 : 1 : guint32 seed = GPOINTER_TO_UINT (d);
210 : :
211 : : typedef enum {
212 : : IS_EMPTY, GET_LENGTH, REVERSE, COPY,
213 : : FOREACH, FIND, FIND_CUSTOM, SORT,
214 : : PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
215 : : POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
216 : : PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
217 : : INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
218 : : PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
219 : : POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
220 : : LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
221 : : } QueueOp;
222 : :
223 [ - + ]: 1 : const guint n_iterations = g_test_thorough () ? 500000 : 100000;
224 : :
225 : : #define RANDOM_QUEUE() &(queues[g_random_int_range(0, G_N_ELEMENTS (queues))])
226 : :
227 : : typedef struct QueueInfo QueueInfo;
228 : : struct QueueInfo
229 : : {
230 : : GQueue *queue;
231 : : GList *tail;
232 : : GList *head;
233 : : guint length;
234 : : };
235 : :
236 : : guint i;
237 : : QueueOp op;
238 : : QueueInfo queues[3];
239 : :
240 : 1 : g_random_set_seed (seed);
241 : :
242 [ + + ]: 4 : for (i = 0; i < G_N_ELEMENTS (queues); ++i)
243 : : {
244 : 3 : queues[i].queue = g_queue_new ();
245 : 3 : queues[i].head = NULL;
246 : 3 : queues[i].tail = NULL;
247 : 3 : queues[i].length = 0;
248 : : }
249 : :
250 [ + + ]: 100001 : for (i = 0; i < n_iterations; ++i)
251 : : {
252 : : guint j;
253 : 100000 : QueueInfo *qinf = RANDOM_QUEUE();
254 : 100000 : GQueue *q = qinf->queue;
255 : 100000 : op = g_random_int_range (IS_EMPTY, LAST_OP);
256 : :
257 : 100000 : g_assert_true (qinf->head == q->head);
258 : 100000 : g_assert_true (qinf->tail == q->tail);
259 : 100000 : g_assert_cmpuint (qinf->length, ==, q->length);
260 : :
261 [ + + + + : 100000 : switch (op)
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- ]
262 : : {
263 : 2866 : case IS_EMPTY:
264 : : {
265 [ + + ]: 2866 : if (g_queue_is_empty (qinf->queue))
266 : : {
267 : 719 : g_assert_null (q->head);
268 : 719 : g_assert_null (q->tail);
269 : 719 : g_assert_cmpuint (q->length, ==, 0);
270 : : }
271 : : else
272 : : {
273 : 2147 : g_assert_nonnull (q->head);
274 : 2147 : g_assert_nonnull (q->tail);
275 : 2147 : g_assert_cmpuint (q->length, >, 0);
276 : : }
277 : : }
278 : 2866 : break;
279 : 2903 : case GET_LENGTH:
280 : : {
281 : : guint l;
282 : :
283 : 2903 : l = g_queue_get_length (q);
284 : :
285 : 2903 : g_assert_cmpuint (qinf->length, ==, q->length);
286 : 2903 : g_assert_cmpuint (qinf->length, ==, l);
287 : : }
288 : 2903 : break;
289 : 2788 : case REVERSE:
290 : 2788 : g_queue_reverse (q);
291 : 2788 : g_assert_true (qinf->tail == q->head);
292 : 2788 : g_assert_true (qinf->head == q->tail);
293 : 2788 : g_assert_cmpuint (qinf->length, ==, q->length);
294 : 2788 : qinf->tail = q->tail;
295 : 2788 : qinf->head = q->head;
296 : 2788 : break;
297 : 2935 : case COPY:
298 : : {
299 : 2935 : QueueInfo *random_queue = RANDOM_QUEUE();
300 : 2935 : GQueue *new_queue = g_queue_copy (random_queue->queue);
301 : :
302 : 2935 : g_queue_free (qinf->queue);
303 : 2935 : q = qinf->queue = new_queue;
304 : 2935 : qinf->head = new_queue->head;
305 : 2935 : qinf->tail = g_list_last (new_queue->head);
306 : 2935 : qinf->length = new_queue->length;
307 : : }
308 : 2935 : break;
309 : 2788 : case FOREACH:
310 : 2788 : delete_all (q);
311 : 2788 : qinf->head = NULL;
312 : 2788 : qinf->tail = NULL;
313 : 2788 : qinf->length = 0;
314 : 2788 : break;
315 : 2854 : case FIND:
316 : : {
317 : 2854 : gboolean find_existing = rnd_bool ();
318 : 2854 : int first = find_max (q);
319 : 2854 : int second = find_min (q);
320 : :
321 [ + + ]: 2854 : if (q->length == 0)
322 : 761 : find_existing = FALSE;
323 : :
324 [ + + ]: 2854 : if (!find_existing)
325 : 1832 : first++;
326 [ + + ]: 2854 : if (!find_existing)
327 : 1832 : second--;
328 : :
329 [ + + ]: 2854 : if (find_existing)
330 : : {
331 : 1022 : g_assert_nonnull (g_queue_find (q, GINT_TO_POINTER (first)));
332 : 1022 : g_assert_nonnull (g_queue_find (q, GINT_TO_POINTER (second)));
333 : : }
334 : : else
335 : : {
336 : 1832 : g_assert_null (g_queue_find (q, GINT_TO_POINTER (first)));
337 : 1832 : g_assert_null (g_queue_find (q, GINT_TO_POINTER (second)));
338 : : }
339 : : }
340 : 2854 : break;
341 : 2862 : case FIND_CUSTOM:
342 : 2862 : break;
343 : 2844 : case SORT:
344 : : {
345 [ + + ]: 2844 : if (!g_queue_is_empty (q))
346 : : {
347 : 2100 : int max = find_max (q);
348 : 2100 : int min = find_min (q);
349 : 2100 : g_queue_remove_all (q, GINT_TO_POINTER (max));
350 : 2100 : check_integrity (q);
351 : 2100 : g_queue_remove_all (q, GINT_TO_POINTER (min));
352 : 2100 : check_integrity (q);
353 : 2100 : g_queue_push_head (q, GINT_TO_POINTER (max));
354 [ + + ]: 2100 : if (max != min)
355 : 1712 : g_queue_push_head (q, GINT_TO_POINTER (min));
356 : 2100 : qinf->length = q->length;
357 : : }
358 : :
359 : 2844 : check_integrity (q);
360 : :
361 : 2844 : g_queue_sort (q, compare_int, NULL);
362 : :
363 : 2844 : check_integrity (q);
364 : :
365 : 2844 : qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
366 : 2844 : qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
367 : :
368 : 2844 : g_assert_true (qinf->tail == q->tail);
369 : : }
370 : 2844 : break;
371 : 2781 : case PUSH_HEAD:
372 : : {
373 : 2781 : int x = g_random_int_range (0, 435435);
374 : 2781 : g_queue_push_head (q, GINT_TO_POINTER (x));
375 [ + + ]: 2781 : if (!qinf->head)
376 : 685 : qinf->tail = qinf->head = q->head;
377 : : else
378 : 2096 : qinf->head = qinf->head->prev;
379 : 2781 : qinf->length++;
380 : : }
381 : 2781 : break;
382 : 2823 : case PUSH_TAIL:
383 : : {
384 : 2823 : int x = g_random_int_range (0, 236546);
385 : 2823 : g_queue_push_tail (q, GINT_TO_POINTER (x));
386 [ + + ]: 2823 : if (!qinf->tail)
387 : 751 : qinf->tail = qinf->head = q->head;
388 : : else
389 : 2072 : qinf->tail = qinf->tail->next;
390 : 2823 : qinf->length++;
391 : : }
392 : 2823 : break;
393 : 2914 : case PUSH_NTH:
394 : : {
395 : 2914 : guint pos = get_random_position (q, TRUE);
396 : 2914 : int x = g_random_int_range (0, 236546);
397 : 2914 : g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
398 [ + + + + ]: 2914 : if (qinf->head && qinf->head->prev)
399 : 705 : qinf->head = qinf->head->prev;
400 : : else
401 : 2209 : qinf->head = q->head;
402 [ + + + + ]: 2914 : if (qinf->tail && qinf->tail->next)
403 : 1142 : qinf->tail = qinf->tail->next;
404 : : else
405 : 1772 : qinf->tail = g_list_last (qinf->head);
406 : 2914 : qinf->length++;
407 : : }
408 : 2914 : break;
409 : 2781 : case POP_HEAD:
410 [ + + ]: 2781 : if (qinf->head)
411 : 2077 : qinf->head = qinf->head->next;
412 [ + + ]: 2781 : if (!qinf->head)
413 : 1085 : qinf->tail = NULL;
414 [ + + ]: 2781 : qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
415 : 2781 : g_queue_pop_head (q);
416 : 2781 : break;
417 : 2916 : case POP_TAIL:
418 [ + + ]: 2916 : if (qinf->tail)
419 : 2190 : qinf->tail = qinf->tail->prev;
420 [ + + ]: 2916 : if (!qinf->tail)
421 : 1094 : qinf->head = NULL;
422 [ + + ]: 2916 : qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
423 : 2916 : g_queue_pop_tail (q);
424 : 2916 : break;
425 : 2948 : case POP_NTH:
426 [ + + ]: 2948 : if (!g_queue_is_empty (q))
427 : : {
428 : 2194 : guint n = get_random_position (q, TRUE);
429 : 2194 : gpointer elm = g_queue_peek_nth (q, n);
430 : :
431 [ + + ]: 2194 : if (n == q->length - 1)
432 : 274 : qinf->tail = qinf->tail->prev;
433 : :
434 [ + + ]: 2194 : if (n == 0)
435 : 731 : qinf->head = qinf->head->next;
436 : :
437 [ + + ]: 2194 : if (n < q->length)
438 : 1114 : qinf->length--;
439 : :
440 : 2194 : g_assert_true (elm == g_queue_pop_nth (q, n));
441 : : }
442 : 2948 : break;
443 : 2923 : case PEEK_HEAD:
444 [ + + ]: 2923 : if (qinf->head)
445 : 2141 : g_assert_true (qinf->head->data == g_queue_peek_head (q));
446 : : else
447 : 782 : g_assert_null (g_queue_peek_head (q));
448 : 2923 : break;
449 : 2885 : case PEEK_TAIL:
450 [ + + ]: 2885 : if (qinf->tail)
451 : 2181 : g_assert_true (qinf->tail->data == g_queue_peek_tail (q));
452 : : else
453 : 704 : g_assert_null (g_queue_peek_tail (q));
454 : 2885 : break;
455 : 2824 : case PEEK_NTH:
456 [ + + ]: 2824 : if (g_queue_is_empty (q))
457 : : {
458 : : int k;
459 [ + + ]: 14574 : for (k = -10; k < 10; ++k)
460 : 13880 : g_assert_null (g_queue_peek_nth (q, (guint) k));
461 : : }
462 : : else
463 : : {
464 : : GList *list;
465 : 2130 : guint n = get_random_position (q, TRUE);
466 [ + + ]: 2130 : if (n >= q->length)
467 : : {
468 : 1072 : g_assert_null (g_queue_peek_nth (q, n));
469 : : }
470 : : else
471 : : {
472 : 1058 : list = qinf->head;
473 [ + + ]: 2899 : for (j = 0; j < n; ++j)
474 : 1841 : list = list->next;
475 : :
476 : 1058 : g_assert_true (list->data == g_queue_peek_nth (q, n));
477 : : }
478 : : }
479 : 2824 : break;
480 : 5799 : case INDEX:
481 : : case LINK_INDEX:
482 : : {
483 : 5799 : int x = g_random_int_range (0, 386538);
484 : : int n;
485 : : GList *list;
486 : :
487 : 5799 : g_queue_remove_all (q, GINT_TO_POINTER (x));
488 : 5799 : check_integrity (q);
489 : 5799 : g_queue_push_tail (q, GINT_TO_POINTER (x));
490 : 5799 : check_integrity (q);
491 : 5799 : g_queue_sort (q, compare_int, NULL);
492 : 5799 : check_integrity (q);
493 : :
494 : 5799 : n = 0;
495 [ + - ]: 25892 : for (list = q->head; list != NULL; list = list->next)
496 : : {
497 [ + + ]: 25892 : if (list->data == GINT_TO_POINTER (x))
498 : 5799 : break;
499 : 20093 : n++;
500 : : }
501 : 5799 : g_assert_nonnull (list);
502 : 5799 : g_assert_cmpint (g_queue_index (q, GINT_TO_POINTER (x)), ==,
503 : : g_queue_link_index (q, list));
504 : 5799 : g_assert_cmpint (g_queue_link_index (q, list), ==, n);
505 : :
506 : 5799 : qinf->head = q->head;
507 : 5799 : qinf->tail = q->tail;
508 : 5799 : qinf->length = q->length;
509 : : }
510 : 5799 : break;
511 : 2905 : case REMOVE:
512 [ + + ]: 2905 : if (!g_queue_is_empty (q))
513 : 2147 : g_queue_remove (q, qinf->tail->data);
514 : : /* qinf->head/qinf->tail may be invalid at this point */
515 [ + + ]: 2905 : if (!g_queue_is_empty (q))
516 : 1758 : g_queue_remove (q, q->head->data);
517 [ + + ]: 2905 : if (!g_queue_is_empty (q))
518 : 1505 : g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
519 : :
520 : 2905 : qinf->head = q->head;
521 : 2905 : qinf->tail = q->tail;
522 : 2905 : qinf->length = q->length;
523 : 2905 : break;
524 : 2870 : case REMOVE_ALL:
525 [ + + ]: 2870 : if (!g_queue_is_empty (q))
526 : 2117 : g_queue_remove_all (q, qinf->tail->data);
527 : : /* qinf->head/qinf->tail may be invalid at this point */
528 [ + + ]: 2870 : if (!g_queue_is_empty (q))
529 : 1684 : g_queue_remove_all (q, q->head->data);
530 [ + + ]: 2870 : if (!g_queue_is_empty (q))
531 : 1359 : g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
532 : :
533 : 2870 : qinf->head = q->head;
534 : 2870 : qinf->tail = q->tail;
535 : 2870 : qinf->length = q->length;
536 : 2870 : break;
537 : 2829 : case INSERT_BEFORE:
538 [ + + ]: 2829 : if (!g_queue_is_empty (q))
539 : : {
540 : 2141 : gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
541 : :
542 : 2141 : g_queue_insert_before (q, qinf->tail, x);
543 : 2141 : g_queue_insert_before (q, qinf->head, x);
544 : 2141 : g_queue_insert_before (q, g_queue_find (q, x), x);
545 : 2141 : g_queue_insert_before (q, NULL, x);
546 : : }
547 : 2829 : qinf->head = q->head;
548 : 2829 : qinf->tail = q->tail;
549 : 2829 : qinf->length = q->length;
550 : 2829 : break;
551 : 2825 : case INSERT_AFTER:
552 [ + + ]: 2825 : if (!g_queue_is_empty (q))
553 : : {
554 : 2077 : gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
555 : :
556 : 2077 : g_queue_insert_after (q, qinf->tail, x);
557 : 2077 : g_queue_insert_after (q, qinf->head, x);
558 : 2077 : g_queue_insert_after (q, g_queue_find (q, x), x);
559 : 2077 : g_queue_insert_after (q, NULL, x);
560 : : }
561 : 2825 : qinf->head = q->head;
562 : 2825 : qinf->tail = q->tail;
563 : 2825 : qinf->length = q->length;
564 : 2825 : break;
565 : 2775 : case INSERT_SORTED:
566 : : {
567 : 2775 : int max = find_max (q);
568 : 2775 : int min = find_min (q);
569 : :
570 [ + + ]: 2775 : if (g_queue_is_empty (q))
571 : : {
572 : 716 : max = 345;
573 : 716 : min = -12;
574 : : }
575 : :
576 : 2775 : g_queue_sort (q, compare_int, NULL);
577 : 2775 : check_integrity (q);
578 : 2775 : g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
579 : 2775 : check_integrity (q);
580 : 2775 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, max + 1);
581 : 2775 : g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
582 : 2775 : check_integrity (q);
583 : 2775 : g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, min - 1);
584 : 2775 : qinf->head = q->head;
585 : 2775 : qinf->tail = q->tail;
586 : 2775 : qinf->length = q->length;
587 : : }
588 : 2775 : break;
589 : 2875 : case PUSH_HEAD_LINK:
590 : : {
591 : 2875 : GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
592 : 2875 : g_queue_push_head_link (q, link);
593 [ + + ]: 2875 : if (!qinf->tail)
594 : 716 : qinf->tail = link;
595 : 2875 : qinf->head = link;
596 : 2875 : qinf->length++;
597 : : }
598 : 2875 : break;
599 : 2844 : case PUSH_TAIL_LINK:
600 : : {
601 : 2844 : GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
602 : 2844 : g_queue_push_tail_link (q, link);
603 [ + + ]: 2844 : if (!qinf->head)
604 : 734 : qinf->head = link;
605 : 2844 : qinf->tail = link;
606 : 2844 : qinf->length++;
607 : : }
608 : 2844 : break;
609 : 2891 : case PUSH_NTH_LINK:
610 : : {
611 : 2891 : GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
612 : 2891 : guint n = get_random_position (q, TRUE);
613 : 2891 : g_queue_push_nth_link (q, n, link);
614 : :
615 [ + + + + ]: 2891 : if (qinf->head && qinf->head->prev)
616 : 725 : qinf->head = qinf->head->prev;
617 : : else
618 : 2166 : qinf->head = q->head;
619 [ + + + + ]: 2891 : if (qinf->tail && qinf->tail->next)
620 : 1119 : qinf->tail = qinf->tail->next;
621 : : else
622 : 1772 : qinf->tail = g_list_last (qinf->head);
623 : 2891 : qinf->length++;
624 : : }
625 : 2891 : break;
626 : 2835 : case POP_HEAD_LINK:
627 [ + + ]: 2835 : if (!g_queue_is_empty (q))
628 : : {
629 : 2165 : qinf->head = qinf->head->next;
630 [ + + ]: 2165 : if (!qinf->head)
631 : 386 : qinf->tail = NULL;
632 : 2165 : qinf->length--;
633 : 2165 : g_list_free (g_queue_pop_head_link (q));
634 : : }
635 : 2835 : break;
636 : 2836 : case POP_TAIL_LINK:
637 [ + + ]: 2836 : if (!g_queue_is_empty (q))
638 : : {
639 : 2128 : qinf->tail = qinf->tail->prev;
640 [ + + ]: 2128 : if (!qinf->tail)
641 : 391 : qinf->head = NULL;
642 : 2128 : qinf->length--;
643 : 2128 : g_list_free (g_queue_pop_tail_link (q));
644 : : }
645 : 2836 : break;
646 : 2833 : case POP_NTH_LINK:
647 [ + + ]: 2833 : if (g_queue_is_empty (q))
648 : 666 : g_assert_null (g_queue_pop_nth_link (q, 200));
649 : : else
650 : : {
651 : 2167 : guint n = get_random_position (q, FALSE);
652 : :
653 [ + + ]: 2167 : if (n == g_queue_get_length (q) - 1)
654 : 1096 : qinf->tail = qinf->tail->prev;
655 : :
656 [ + + ]: 2167 : if (n == 0)
657 : 1120 : qinf->head = qinf->head->next;
658 : :
659 : 2167 : qinf->length--;
660 : :
661 : 2167 : g_list_free (g_queue_pop_nth_link (q, n));
662 : : }
663 : 2833 : break;
664 : 2840 : case PEEK_HEAD_LINK:
665 [ + + ]: 2840 : if (g_queue_is_empty (q))
666 : 725 : g_assert_null (g_queue_peek_head_link (q));
667 : : else
668 : 2115 : g_assert_true (g_queue_peek_head_link (q) == qinf->head);
669 : 2840 : break;
670 : 2790 : case PEEK_TAIL_LINK:
671 [ + + ]: 2790 : if (g_queue_is_empty (q))
672 : 721 : g_assert_null (g_queue_peek_tail_link (q));
673 : : else
674 : 2069 : g_assert_true (g_queue_peek_tail_link (q) == qinf->tail);
675 : 2790 : break;
676 : 2941 : case PEEK_NTH_LINK:
677 [ + + ]: 2941 : if (g_queue_is_empty(q))
678 : 749 : g_assert_null (g_queue_peek_nth_link (q, 1000));
679 : : else
680 : : {
681 : 2192 : guint n = get_random_position (q, FALSE);
682 : : GList *link;
683 : :
684 : 2192 : link = q->head;
685 [ + + ]: 9037 : for (j = 0; j < n; ++j)
686 : 6845 : link = link->next;
687 : :
688 : 2192 : g_assert_true (g_queue_peek_nth_link (q, n) == link);
689 : : }
690 : 2941 : break;
691 : 2840 : case UNLINK:
692 [ + + ]: 2840 : if (!g_queue_is_empty (q))
693 : : {
694 : 2090 : guint n = g_random_int_range (0, g_queue_get_length (q));
695 : : GList *link;
696 : :
697 : 2090 : link = q->head;
698 [ + + ]: 9566 : for (j = 0; j < n; ++j)
699 : 7476 : link = link->next;
700 : :
701 : 2090 : g_queue_unlink (q, link);
702 : 2090 : check_integrity (q);
703 : :
704 : 2090 : g_list_free (link);
705 : :
706 : 2090 : qinf->head = q->head;
707 : 2090 : qinf->tail = q->tail;
708 : 2090 : qinf->length--;
709 : : }
710 : 2840 : break;
711 : 2837 : case DELETE_LINK:
712 [ + + ]: 2837 : if (!g_queue_is_empty (q))
713 : : {
714 : 2134 : guint n = g_random_int_range (0, g_queue_get_length (q));
715 : : GList *link;
716 : :
717 : 2134 : link = q->head;
718 [ + + ]: 9441 : for (j = 0; j < n; ++j)
719 : 7307 : link = link->next;
720 : :
721 : 2134 : g_queue_delete_link (q, link);
722 : 2134 : check_integrity (q);
723 : :
724 : 2134 : qinf->head = q->head;
725 : 2134 : qinf->tail = q->tail;
726 : 2134 : qinf->length--;
727 : : }
728 : 2837 : break;
729 : 0 : case LAST_OP:
730 : : default:
731 : : g_assert_not_reached();
732 : : break;
733 : : }
734 : :
735 [ + - ]: 100000 : if (qinf->head != q->head ||
736 [ + - ]: 100000 : qinf->tail != q->tail ||
737 [ - + ]: 100000 : qinf->length != q->length)
738 : 0 : g_printerr ("op: %d\n", op);
739 : :
740 : 100000 : g_assert_true (qinf->head == q->head);
741 : 100000 : g_assert_true (qinf->tail == q->tail);
742 : 100000 : g_assert_cmpuint (qinf->length, ==, q->length);
743 : :
744 [ + + ]: 400000 : for (j = 0; j < G_N_ELEMENTS (queues); ++j)
745 : 300000 : check_integrity (queues[j].queue);
746 : : }
747 : :
748 [ + + ]: 4 : for (i = 0; i < G_N_ELEMENTS (queues); ++i)
749 : 3 : g_queue_free (queues[i].queue);
750 : 1 : }
751 : :
752 : : static void
753 : 200 : remove_item (gpointer data, gpointer q)
754 : : {
755 : 200 : GQueue *queue = q;
756 : :
757 : 200 : g_queue_remove (queue, data);
758 : 200 : }
759 : :
760 : : static void
761 : 1 : test_basic (void)
762 : : {
763 : : GQueue *q;
764 : : GList *node;
765 : : gpointer data;
766 : :
767 : 1 : q = g_queue_new ();
768 : :
769 : 1 : g_assert_true (g_queue_is_empty (q));
770 : 1 : g_queue_push_head (q, GINT_TO_POINTER (2));
771 : 1 : check_integrity (q);
772 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_head (q)), ==, 2);
773 : 1 : check_integrity (q);
774 : 1 : g_assert_false (g_queue_is_empty (q));
775 : 1 : check_integrity (q);
776 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 1);
777 : 1 : g_assert_true (q->head == q->tail);
778 : 1 : g_queue_push_head (q, GINT_TO_POINTER (1));
779 : 1 : check_integrity (q);
780 : 1 : g_assert_true (q->head->next == q->tail);
781 : 1 : g_assert_true (q->tail->prev == q->head);
782 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 2);
783 : 1 : check_integrity (q);
784 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, 2);
785 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
786 : 1 : check_integrity (q);
787 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (3));
788 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 3);
789 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
790 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->next->data), ==, 2);
791 : 1 : g_assert_true (q->head->next->next == q->tail);
792 : 1 : g_assert_true (q->head->next == q->tail->prev);
793 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, 3);
794 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (4));
795 : 1 : check_integrity (q);
796 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 4);
797 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
798 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_tail (q)), ==, 4);
799 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (5));
800 : 1 : check_integrity (q);
801 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 5);
802 : 1 : g_assert_false (g_queue_is_empty (q));
803 : 1 : check_integrity (q);
804 : 1 : g_assert_cmpint (q->length, ==, 5);
805 : 1 : g_assert_null (q->head->prev);
806 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->data), ==, 1);
807 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->next->data), ==, 2);
808 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->next->next->data), ==, 3);
809 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->next->next->next->data), ==, 4);
810 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->head->next->next->next->next->data), ==, 5);
811 : 1 : g_assert_null (q->head->next->next->next->next->next);
812 : 1 : g_assert_true (q->head->next->next->next->next == q->tail);
813 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->data), ==, 5);
814 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->data), ==, 4);
815 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->prev->data), ==, 3);
816 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->prev->prev->data), ==, 2);
817 : 1 : g_assert_cmpint (GPOINTER_TO_INT (q->tail->prev->prev->prev->prev->data), ==, 1);
818 : 1 : g_assert_null (q->tail->prev->prev->prev->prev->prev);
819 : 1 : g_assert_true (q->tail->prev->prev->prev->prev == q->head);
820 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_tail (q)), ==, 5);
821 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_head (q)), ==, 1);
822 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_head (q)), ==, 1);
823 : 1 : check_integrity (q);
824 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 4);
825 : 1 : g_assert_cmpint (q->length, ==, 4);
826 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 5);
827 : 1 : check_integrity (q);
828 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 3);
829 : :
830 : 1 : node = g_queue_pop_head_link (q);
831 : 1 : g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 2);
832 : 1 : g_list_free_1 (node);
833 : :
834 : 1 : check_integrity (q);
835 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 2);
836 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 4);
837 : 1 : check_integrity (q);
838 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 1);
839 : 1 : node = g_queue_pop_head_link (q);
840 : 1 : g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 3);
841 : 1 : g_list_free_1 (node);
842 : 1 : check_integrity (q);
843 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
844 : 1 : g_assert_null (g_queue_pop_tail (q));
845 : 1 : check_integrity (q);
846 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
847 : 1 : g_assert_null (g_queue_pop_head (q));
848 : 1 : check_integrity (q);
849 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
850 : 1 : g_assert_true (g_queue_is_empty (q));
851 : 1 : check_integrity (q);
852 : :
853 : 1 : g_queue_push_head (q, GINT_TO_POINTER (1));
854 : 1 : check_integrity (q);
855 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 1);
856 : 1 : g_assert_cmpint (q->length, ==, 1);
857 : 1 : g_queue_push_head (q, GINT_TO_POINTER (2));
858 : 1 : check_integrity (q);
859 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 2);
860 : 1 : g_assert_cmpint (q->length, ==, 2);
861 : 1 : g_queue_push_head (q, GINT_TO_POINTER (3));
862 : 1 : check_integrity (q);
863 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 3);
864 : 1 : g_assert_cmpint (q->length, ==, 3);
865 : 1 : g_queue_push_head (q, GINT_TO_POINTER (4));
866 : 1 : check_integrity (q);
867 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 4);
868 : 1 : g_assert_cmpint (q->length, ==, 4);
869 : 1 : g_queue_push_head (q, GINT_TO_POINTER (5));
870 : 1 : check_integrity (q);
871 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 5);
872 : 1 : g_assert_cmpint (q->length, ==, 5);
873 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_head (q)), ==, 5);
874 : 1 : check_integrity (q);
875 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 4);
876 : 1 : node = q->tail;
877 : 1 : g_assert_true (node == g_queue_pop_tail_link (q));
878 : 1 : check_integrity (q);
879 : 1 : g_list_free_1 (node);
880 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 3);
881 : 1 : data = q->head->data;
882 : 1 : g_assert_true (data == g_queue_pop_head (q));
883 : 1 : check_integrity (q);
884 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 2);
885 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 2);
886 : 1 : check_integrity (q);
887 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 1);
888 : 1 : g_assert_true (q->head == q->tail);
889 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_pop_tail (q)), ==, 3);
890 : 1 : check_integrity (q);
891 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
892 : 1 : g_assert_null (g_queue_pop_head (q));
893 : 1 : check_integrity (q);
894 : 1 : g_assert_null (g_queue_pop_head_link (q));
895 : 1 : check_integrity (q);
896 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
897 : 1 : g_assert_null (g_queue_pop_tail_link (q));
898 : 1 : check_integrity (q);
899 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
900 : :
901 : 1 : g_queue_reverse (q);
902 : 1 : check_integrity (q);
903 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
904 : 1 : g_queue_free (q);
905 : 1 : }
906 : :
907 : : static void
908 : 1 : test_copy (void)
909 : : {
910 : : GQueue *q, *q2;
911 : : gint i;
912 : :
913 : 1 : q = g_queue_new ();
914 : 1 : q2 = g_queue_copy (q);
915 : 1 : check_integrity (q);
916 : 1 : check_integrity (q2);
917 : 1 : g_assert_cmpint (g_list_length (q->head), ==, 0);
918 : 1 : g_assert_cmpint (g_list_length (q2->head), ==, 0);
919 : 1 : g_queue_sort (q, compare_int, NULL);
920 : 1 : check_integrity (q2);
921 : 1 : check_integrity (q);
922 : 1 : g_queue_sort (q2, compare_int, NULL);
923 : 1 : check_integrity (q2);
924 : 1 : check_integrity (q);
925 : :
926 [ + + ]: 201 : for (i = 0; i < 200; ++i)
927 : : {
928 : 200 : g_queue_push_nth (q, GINT_TO_POINTER (i), i);
929 : 200 : g_assert_nonnull (g_queue_find (q, GINT_TO_POINTER (i)));
930 : 200 : check_integrity (q);
931 : 200 : check_integrity (q2);
932 : : }
933 : :
934 [ + + ]: 201 : for (i = 0; i < 200; ++i)
935 : : {
936 : 200 : g_queue_remove (q, GINT_TO_POINTER (i));
937 : 200 : check_integrity (q);
938 : 200 : check_integrity (q2);
939 : : }
940 : :
941 [ + + ]: 201 : for (i = 0; i < 200; ++i)
942 : : {
943 : 200 : GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
944 : :
945 : 200 : g_queue_push_nth_link (q, i, l);
946 : 200 : check_integrity (q);
947 : 200 : check_integrity (q2);
948 : 200 : g_queue_reverse (q);
949 : 200 : check_integrity (q);
950 : 200 : check_integrity (q2);
951 : : }
952 : :
953 : 1 : g_queue_free (q2);
954 : 1 : q2 = g_queue_copy (q);
955 : :
956 : 1 : g_queue_foreach (q2, remove_item, q2);
957 : 1 : check_integrity (q2);
958 : 1 : check_integrity (q);
959 : :
960 : 1 : g_queue_free (q);
961 : 1 : g_queue_free (q2);
962 : 1 : }
963 : :
964 : : static void
965 : 1 : test_off_by_one (void)
966 : : {
967 : : GQueue *q;
968 : : GList *node;
969 : :
970 : 1 : q = g_queue_new ();
971 : :
972 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (1234));
973 : 1 : check_integrity (q);
974 : 1 : node = g_queue_peek_tail_link (q);
975 : 1 : g_assert_nonnull (node);
976 : 1 : g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 1234);
977 : :
978 : 1 : node = g_queue_peek_nth_link (q, g_queue_get_length (q));
979 : 1 : g_assert_null (node);
980 : :
981 : 1 : node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1);
982 : 1 : g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 1234);
983 : :
984 : 1 : node = g_queue_pop_nth_link (q, g_queue_get_length (q));
985 : 1 : g_assert_null (node);
986 : :
987 : 1 : node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1);
988 : 1 : g_assert_nonnull (node);
989 : 1 : g_assert_cmpint (GPOINTER_TO_INT (node->data), ==, 1234);
990 : :
991 : 1 : g_list_free_1 (node);
992 : :
993 : 1 : g_queue_free (q);
994 : 1 : }
995 : :
996 : : static gint
997 : 8 : find_custom (gconstpointer a, gconstpointer b)
998 : : {
999 : 8 : return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
1000 : : }
1001 : :
1002 : : static void
1003 : 1 : test_find_custom (void)
1004 : : {
1005 : : GQueue *q;
1006 : : GList *node;
1007 : 1 : q = g_queue_new ();
1008 : :
1009 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (1234));
1010 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (1));
1011 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (2));
1012 : 1 : node = g_queue_find_custom (q, GINT_TO_POINTER (1), find_custom);
1013 : 1 : g_assert_nonnull (node);
1014 : 1 : node = g_queue_find_custom (q, GINT_TO_POINTER (2), find_custom);
1015 : 1 : g_assert_nonnull (node);
1016 : 1 : node = g_queue_find_custom (q, GINT_TO_POINTER (3), find_custom);
1017 : 1 : g_assert_null (node);
1018 : :
1019 : 1 : g_queue_free (q);
1020 : 1 : }
1021 : :
1022 : : static void
1023 : 1 : test_static (void)
1024 : : {
1025 : : GQueue q;
1026 : 1 : GQueue q2 = G_QUEUE_INIT;
1027 : :
1028 : 1 : g_queue_init (&q);
1029 : :
1030 : 1 : check_integrity (&q);
1031 : 1 : g_assert_true (g_queue_is_empty (&q));
1032 : :
1033 : 1 : check_integrity (&q2);
1034 : 1 : g_assert_true (g_queue_is_empty (&q2));
1035 : 1 : }
1036 : :
1037 : : static void
1038 : 1 : test_clear (void)
1039 : : {
1040 : : GQueue *q;
1041 : 1 : q = g_queue_new ();
1042 : :
1043 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (1234));
1044 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (1));
1045 : 1 : g_queue_push_tail (q, GINT_TO_POINTER (2));
1046 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 3);
1047 : :
1048 : 1 : g_queue_clear (q);
1049 : 1 : check_integrity (q);
1050 : 1 : g_assert_true (g_queue_is_empty (q));
1051 : :
1052 : 1 : g_queue_free (q);
1053 : 1 : }
1054 : :
1055 : : typedef struct
1056 : : {
1057 : : gboolean freed;
1058 : : int x;
1059 : : } QueueItem;
1060 : :
1061 : : static void
1062 : 7 : free_func (gpointer data)
1063 : : {
1064 : 7 : QueueItem *item = data;
1065 : :
1066 : 7 : item->freed = TRUE;
1067 : 7 : }
1068 : :
1069 : : static QueueItem *
1070 : 11 : new_item (int x)
1071 : : {
1072 : : QueueItem *item;
1073 : :
1074 : 11 : item = g_slice_new (QueueItem);
1075 : 11 : item->freed = FALSE;
1076 : 11 : item->x = x;
1077 : :
1078 : 11 : return item;
1079 : : }
1080 : :
1081 : : static void
1082 : 1 : test_clear_full (void)
1083 : : {
1084 : : QueueItem *one, *two, *three, *four;
1085 : : GQueue *queue;
1086 : :
1087 : 1 : queue = g_queue_new ();
1088 : 1 : g_queue_push_tail (queue, one = new_item (1));
1089 : 1 : g_queue_push_tail (queue, two = new_item (2));
1090 : 1 : g_queue_push_tail (queue, three = new_item (3));
1091 : 1 : g_queue_push_tail (queue, four = new_item (4));
1092 : :
1093 : 1 : g_assert_cmpint (g_queue_get_length (queue), ==, 4);
1094 : 1 : g_assert_false (one->freed);
1095 : 1 : g_assert_false (two->freed);
1096 : 1 : g_assert_false (three->freed);
1097 : 1 : g_assert_false (four->freed);
1098 : :
1099 : 1 : g_queue_clear_full (queue, free_func);
1100 : :
1101 : 1 : g_assert_true (one->freed);
1102 : 1 : g_assert_true (two->freed);
1103 : 1 : g_assert_true (three->freed);
1104 : 1 : g_assert_true (four->freed);
1105 : :
1106 : 1 : g_assert_true (g_queue_is_empty (queue));
1107 : 1 : check_integrity (queue);
1108 : :
1109 : 1 : g_slice_free (QueueItem, one);
1110 : 1 : g_slice_free (QueueItem, two);
1111 : 1 : g_slice_free (QueueItem, three);
1112 : 1 : g_slice_free (QueueItem, four);
1113 : 1 : g_queue_free (queue);
1114 : 1 : }
1115 : :
1116 : : /* Check that g_queue_clear_full() called with a NULL free_func is equivalent
1117 : : * to g_queue_clear(). */
1118 : : static void
1119 : 1 : test_clear_full_noop (void)
1120 : : {
1121 : : QueueItem *one, *two, *three, *four;
1122 : : GQueue *queue;
1123 : :
1124 : 1 : queue = g_queue_new ();
1125 : 1 : g_queue_push_tail (queue, one = new_item (1));
1126 : 1 : g_queue_push_tail (queue, two = new_item (2));
1127 : 1 : g_queue_push_tail (queue, three = new_item (3));
1128 : 1 : g_queue_push_tail (queue, four = new_item (4));
1129 : :
1130 : 1 : g_assert_cmpint (g_queue_get_length (queue), ==, 4);
1131 : 1 : g_assert_false (one->freed);
1132 : 1 : g_assert_false (two->freed);
1133 : 1 : g_assert_false (three->freed);
1134 : 1 : g_assert_false (four->freed);
1135 : :
1136 : 1 : g_queue_clear_full (queue, NULL);
1137 : :
1138 : 1 : g_assert_true (g_queue_is_empty (queue));
1139 : 1 : check_integrity (queue);
1140 : :
1141 : 1 : g_slice_free (QueueItem, one);
1142 : 1 : g_slice_free (QueueItem, two);
1143 : 1 : g_slice_free (QueueItem, three);
1144 : 1 : g_slice_free (QueueItem, four);
1145 : 1 : g_queue_free (queue);
1146 : 1 : }
1147 : :
1148 : : /* Test g_queue_push_nth_link() with various combinations of position (before,
1149 : : * in the middle of, or at the end of the queue) and various existing queues
1150 : : * (empty, single element, multiple elements). */
1151 : : static void
1152 : 1 : test_push_nth_link (void)
1153 : : {
1154 : : GQueue *q;
1155 : 1 : q = g_queue_new ();
1156 : :
1157 : : /* Push onto before the front of an empty queue (which results in it being
1158 : : * added to the end of the queue). */
1159 : 1 : g_queue_push_nth_link (q, -1, g_list_prepend (NULL, GINT_TO_POINTER (1)));
1160 : 1 : check_integrity (q);
1161 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 1);
1162 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 1);
1163 : :
1164 : 1 : g_queue_clear (q);
1165 : :
1166 : : /* Push onto after the rear of an empty queue. */
1167 : 1 : g_queue_push_nth_link (q, 100, g_list_prepend (NULL, GINT_TO_POINTER (2)));
1168 : 1 : check_integrity (q);
1169 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 1);
1170 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 2);
1171 : :
1172 : 1 : g_queue_clear (q);
1173 : :
1174 : : /* Push onto the front of an empty queue. */
1175 : 1 : g_queue_push_nth_link (q, 0, g_list_prepend (NULL, GINT_TO_POINTER (3)));
1176 : 1 : check_integrity (q);
1177 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 1);
1178 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 3);
1179 : :
1180 : 1 : g_queue_clear (q);
1181 : :
1182 : : /* Push onto before the front of a non-empty queue (which results in it being
1183 : : * added to the end of the queue). */
1184 : 1 : g_queue_push_head (q, GINT_TO_POINTER (4));
1185 : 1 : g_queue_push_nth_link (q, -1, g_list_prepend (NULL, GINT_TO_POINTER (5)));
1186 : 1 : check_integrity (q);
1187 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 2);
1188 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 4);
1189 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 5);
1190 : :
1191 : 1 : g_queue_clear (q);
1192 : :
1193 : : /* Push onto after the rear of a non-empty queue. */
1194 : 1 : g_queue_push_head (q, GINT_TO_POINTER (6));
1195 : 1 : g_queue_push_nth_link (q, 100, g_list_prepend (NULL, GINT_TO_POINTER (7)));
1196 : 1 : check_integrity (q);
1197 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 2);
1198 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 6);
1199 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 7);
1200 : :
1201 : 1 : g_queue_clear (q);
1202 : :
1203 : : /* Push onto the rear of a non-empty queue. */
1204 : 1 : g_queue_push_head (q, GINT_TO_POINTER (8));
1205 : 1 : g_queue_push_nth_link (q, 1, g_list_prepend (NULL, GINT_TO_POINTER (9)));
1206 : 1 : check_integrity (q);
1207 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 2);
1208 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 8);
1209 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 9);
1210 : :
1211 : 1 : g_queue_clear (q);
1212 : :
1213 : : /* Push onto the front of a non-empty queue. */
1214 : 1 : g_queue_push_head (q, GINT_TO_POINTER (10));
1215 : 1 : g_queue_push_nth_link (q, 0, g_list_prepend (NULL, GINT_TO_POINTER (11)));
1216 : 1 : check_integrity (q);
1217 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 2);
1218 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 11);
1219 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 10);
1220 : :
1221 : 1 : g_queue_clear (q);
1222 : :
1223 : : /* Push into the middle of a non-empty queue. */
1224 : 1 : g_queue_push_head (q, GINT_TO_POINTER (12));
1225 : 1 : g_queue_push_head (q, GINT_TO_POINTER (13));
1226 : 1 : g_queue_push_nth_link (q, 1, g_list_prepend (NULL, GINT_TO_POINTER (14)));
1227 : 1 : check_integrity (q);
1228 : 1 : g_assert_cmpint (g_queue_get_length (q), ==, 3);
1229 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 0)), ==, 13);
1230 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 1)), ==, 14);
1231 : 1 : g_assert_cmpint (GPOINTER_TO_INT (g_queue_peek_nth (q, 2)), ==, 12);
1232 : :
1233 : 1 : g_queue_free (q);
1234 : 1 : }
1235 : :
1236 : : static void
1237 : 1 : test_free_full (void)
1238 : : {
1239 : : QueueItem *one, *two, *three;
1240 : 1 : GQueue *queue = NULL;
1241 : :
1242 : 1 : queue = g_queue_new();
1243 : 1 : g_queue_push_tail (queue, one = new_item (1));
1244 : 1 : g_queue_push_tail (queue, two = new_item (2));
1245 : 1 : g_queue_push_tail (queue, three = new_item (3));
1246 : 1 : g_assert_false (one->freed);
1247 : 1 : g_assert_false (two->freed);
1248 : 1 : g_assert_false (three->freed);
1249 : 1 : g_queue_free_full (queue, free_func);
1250 : 1 : g_assert_true (one->freed);
1251 : 1 : g_assert_true (two->freed);
1252 : 1 : g_assert_true (three->freed);
1253 : 1 : g_slice_free (QueueItem, one);
1254 : 1 : g_slice_free (QueueItem, two);
1255 : 1 : g_slice_free (QueueItem, three);
1256 : 1 : }
1257 : :
1258 : : static void
1259 : 1 : test_insert_sibling_link (void)
1260 : : {
1261 : 1 : GQueue q = G_QUEUE_INIT;
1262 : 1 : GList a = {0};
1263 : 1 : GList b = {0};
1264 : 1 : GList c = {0};
1265 : 1 : GList d = {0};
1266 : 1 : GList e = {0};
1267 : :
1268 : 1 : g_queue_push_head_link (&q, &a);
1269 : 1 : g_queue_insert_after_link (&q, &a, &d);
1270 : 1 : g_queue_insert_before_link (&q, &d, &b);
1271 : 1 : g_queue_insert_after_link (&q, &b, &c);
1272 : 1 : g_queue_insert_after_link (&q, NULL, &e);
1273 : :
1274 : 1 : g_assert_true (q.head == &e);
1275 : 1 : g_assert_true (q.tail == &d);
1276 : :
1277 : 1 : g_assert_null (e.prev);
1278 : 1 : g_assert_true (e.next == &a);
1279 : :
1280 : 1 : g_assert_true (a.prev == &e);
1281 : 1 : g_assert_true (a.next == &b);
1282 : :
1283 : 1 : g_assert_true (b.prev == &a);
1284 : 1 : g_assert_true (b.next == &c);
1285 : :
1286 : 1 : g_assert_true (c.prev == &b);
1287 : 1 : g_assert_true (c.next == &d);
1288 : :
1289 : 1 : g_assert_true (d.prev == &c);
1290 : 1 : g_assert_null (d.next);
1291 : 1 : }
1292 : :
1293 : 1 : int main (int argc, char *argv[])
1294 : : {
1295 : : guint32 seed;
1296 : : gchar *path;
1297 : :
1298 : 1 : g_test_init (&argc, &argv, NULL);
1299 : :
1300 : 1 : g_test_add_func ("/queue/basic", test_basic);
1301 : 1 : g_test_add_func ("/queue/copy", test_copy);
1302 : 1 : g_test_add_func ("/queue/off-by-one", test_off_by_one);
1303 : 1 : g_test_add_func ("/queue/find-custom", test_find_custom);
1304 : 1 : g_test_add_func ("/queue/static", test_static);
1305 : 1 : g_test_add_func ("/queue/clear", test_clear);
1306 : 1 : g_test_add_func ("/queue/free-full", test_free_full);
1307 : 1 : g_test_add_func ("/queue/clear-full", test_clear_full);
1308 : 1 : g_test_add_func ("/queue/clear-full/noop", test_clear_full_noop);
1309 : 1 : g_test_add_func ("/queue/insert-sibling-link", test_insert_sibling_link);
1310 : 1 : g_test_add_func ("/queue/push-nth-link", test_push_nth_link);
1311 : :
1312 : 1 : seed = g_test_rand_int_range (0, G_MAXINT);
1313 : 1 : path = g_strdup_printf ("/queue/random/seed:%u", seed);
1314 : 1 : g_test_add_data_func (path, GUINT_TO_POINTER (seed), random_test);
1315 : 1 : g_free (path);
1316 : :
1317 : 1 : return g_test_run ();
1318 : : }
|
