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