|
1 /* |
|
2 * Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 |
|
18 #undef G_DISABLE_ASSERT |
|
19 #undef G_LOG_DOMAIN |
|
20 |
|
21 #include <time.h> |
|
22 #include <stdlib.h> |
|
23 |
|
24 #include <glib.h> |
|
25 |
|
26 #ifdef __SYMBIAN32__ |
|
27 #include "mrt2_glib2_test.h" |
|
28 #endif /*__SYMBIAN32__*/ |
|
29 |
|
30 static gboolean verbose = FALSE; |
|
31 |
|
32 |
|
33 static void |
|
34 check_integrity (GQueue *queue) |
|
35 { |
|
36 GList *list; |
|
37 GList *last; |
|
38 GList *links; |
|
39 GList *link; |
|
40 gint n; |
|
41 |
|
42 g_assert (queue->length < 4000000000u); |
|
43 |
|
44 g_assert (g_queue_get_length (queue) == queue->length); |
|
45 |
|
46 if (!queue->head) |
|
47 g_assert (!queue->tail); |
|
48 if (!queue->tail) |
|
49 g_assert (!queue->head); |
|
50 |
|
51 n = 0; |
|
52 last = NULL; |
|
53 for (list = queue->head; list != NULL; list = list->next) |
|
54 { |
|
55 if (!list->next) |
|
56 last = list; |
|
57 ++n; |
|
58 } |
|
59 g_assert (n == queue->length); |
|
60 g_assert (last == queue->tail); |
|
61 |
|
62 n = 0; |
|
63 last = NULL; |
|
64 for (list = queue->tail; list != NULL; list = list->prev) |
|
65 { |
|
66 if (!list->prev) |
|
67 last = list; |
|
68 ++n; |
|
69 } |
|
70 g_assert (n == queue->length); |
|
71 g_assert (last == queue->head); |
|
72 |
|
73 links = NULL; |
|
74 for (list = queue->head; list != NULL; list = list->next) |
|
75 links = g_list_prepend (links, list); |
|
76 |
|
77 link = links; |
|
78 for (list = queue->tail; list != NULL; list = list->prev) |
|
79 { |
|
80 g_assert (list == link->data); |
|
81 link = link->next; |
|
82 } |
|
83 g_list_free (links); |
|
84 |
|
85 links = NULL; |
|
86 for (list = queue->tail; list != NULL; list = list->prev) |
|
87 links = g_list_prepend (links, list); |
|
88 |
|
89 link = links; |
|
90 for (list = queue->head; list != NULL; list = list->next) |
|
91 { |
|
92 g_assert (list == link->data); |
|
93 link = link->next; |
|
94 } |
|
95 g_list_free (links); |
|
96 } |
|
97 |
|
98 static gboolean |
|
99 rnd_bool (void) |
|
100 { |
|
101 return g_random_int_range (0, 2); |
|
102 } |
|
103 |
|
104 static void |
|
105 check_max (gpointer elm, gpointer user_data) |
|
106 { |
|
107 gint *best = user_data; |
|
108 gint element = GPOINTER_TO_INT (elm); |
|
109 |
|
110 if (element > *best) |
|
111 *best = element; |
|
112 } |
|
113 |
|
114 static void |
|
115 check_min (gpointer elm, gpointer user_data) |
|
116 { |
|
117 gint *best = user_data; |
|
118 gint element = GPOINTER_TO_INT (elm); |
|
119 |
|
120 if (element < *best) |
|
121 *best = element; |
|
122 } |
|
123 |
|
124 static gint |
|
125 find_min (GQueue *queue) |
|
126 { |
|
127 gint min = G_MAXINT; |
|
128 |
|
129 g_queue_foreach (queue, check_min, &min); |
|
130 |
|
131 return min; |
|
132 } |
|
133 |
|
134 static gint |
|
135 find_max (GQueue *queue) |
|
136 { |
|
137 gint max = G_MININT; |
|
138 |
|
139 g_queue_foreach (queue, check_max, &max); |
|
140 |
|
141 return max; |
|
142 } |
|
143 |
|
144 static void |
|
145 delete_elm (gpointer elm, gpointer user_data) |
|
146 { |
|
147 g_queue_remove ((GQueue *)user_data, elm); |
|
148 check_integrity ((GQueue *)user_data); |
|
149 } |
|
150 |
|
151 static void |
|
152 delete_all (GQueue *queue) |
|
153 { |
|
154 g_queue_foreach (queue, delete_elm, queue); |
|
155 } |
|
156 |
|
157 static int |
|
158 compare_int (gconstpointer a, gconstpointer b, gpointer data) |
|
159 { |
|
160 int ai = GPOINTER_TO_INT (a); |
|
161 int bi = GPOINTER_TO_INT (b); |
|
162 |
|
163 if (ai > bi) |
|
164 return 1; |
|
165 else if (ai == bi) |
|
166 return 0; |
|
167 else |
|
168 return -1; |
|
169 } |
|
170 |
|
171 static gint |
|
172 get_random_position (GQueue *queue, gboolean allow_offlist) |
|
173 { |
|
174 int n; |
|
175 enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where; |
|
176 |
|
177 if (allow_offlist) |
|
178 where = g_random_int_range (OFF_QUEUE, LAST); |
|
179 else |
|
180 where = g_random_int_range (HEAD, LAST); |
|
181 |
|
182 switch (where) |
|
183 { |
|
184 case OFF_QUEUE: |
|
185 n = g_random_int (); |
|
186 break; |
|
187 |
|
188 case HEAD: |
|
189 n = 0; |
|
190 break; |
|
191 |
|
192 case TAIL: |
|
193 if (allow_offlist) |
|
194 n = queue->length; |
|
195 else |
|
196 n = queue->length - 1; |
|
197 break; |
|
198 |
|
199 case MIDDLE: |
|
200 if (queue->length == 0) |
|
201 n = 0; |
|
202 else |
|
203 n = g_random_int_range (0, queue->length); |
|
204 break; |
|
205 |
|
206 default: |
|
207 g_assert_not_reached(); |
|
208 n = 100; |
|
209 break; |
|
210 |
|
211 } |
|
212 |
|
213 return n; |
|
214 } |
|
215 |
|
216 static void |
|
217 random_test (int seed) |
|
218 { |
|
219 typedef enum { |
|
220 IS_EMPTY, GET_LENGTH, REVERSE, COPY, |
|
221 FOREACH, FIND, FIND_CUSTOM, SORT, |
|
222 PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD, |
|
223 POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL, |
|
224 PEEK_NTH, INDEX, REMOVE, REMOVE_ALL, |
|
225 INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK, |
|
226 PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK, |
|
227 POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK, |
|
228 LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP |
|
229 } QueueOp; |
|
230 |
|
231 #ifdef __SYMBIAN32__ |
|
232 #define N_ITERATIONS 50000 |
|
233 #else |
|
234 #define N_ITERATIONS 500000 |
|
235 #endif//__SYMBIAN32__ |
|
236 #define N_QUEUES 3 |
|
237 |
|
238 #define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)]) |
|
239 |
|
240 typedef struct QueueInfo QueueInfo; |
|
241 struct QueueInfo |
|
242 { |
|
243 GQueue *queue; |
|
244 GList *tail; |
|
245 GList *head; |
|
246 guint length; |
|
247 }; |
|
248 |
|
249 gint i; |
|
250 QueueOp op; |
|
251 QueueInfo queues[N_QUEUES]; |
|
252 |
|
253 if (verbose) |
|
254 g_print ("seed: %d\n", seed); |
|
255 |
|
256 g_random_set_seed (seed); |
|
257 |
|
258 for (i = 0; i < N_QUEUES; ++i) |
|
259 { |
|
260 queues[i].queue = g_queue_new (); |
|
261 queues[i].head = NULL; |
|
262 queues[i].tail = NULL; |
|
263 queues[i].length = 0; |
|
264 } |
|
265 |
|
266 for (i = 0; i < N_ITERATIONS; ++i) |
|
267 { |
|
268 int j; |
|
269 QueueInfo *qinf = RANDOM_QUEUE(); |
|
270 GQueue *q = qinf->queue; |
|
271 op = g_random_int_range (IS_EMPTY, LAST_OP); |
|
272 |
|
273 g_assert (qinf->head == q->head); |
|
274 g_assert (qinf->tail == q->tail); |
|
275 g_assert (qinf->length == q->length); |
|
276 |
|
277 switch (op) |
|
278 { |
|
279 case IS_EMPTY: |
|
280 { |
|
281 if (g_queue_is_empty (qinf->queue)) |
|
282 { |
|
283 g_assert (q->head == NULL); |
|
284 g_assert (q->tail == NULL); |
|
285 g_assert (q->length == 0); |
|
286 } |
|
287 else |
|
288 { |
|
289 g_assert (q->head); |
|
290 g_assert (q->tail); |
|
291 g_assert (q->length > 0); |
|
292 } |
|
293 } |
|
294 break; |
|
295 case GET_LENGTH: |
|
296 { |
|
297 int l; |
|
298 |
|
299 l = g_queue_get_length (q); |
|
300 |
|
301 g_assert (qinf->length == q->length); |
|
302 g_assert (qinf->length == l); |
|
303 } |
|
304 break; |
|
305 case REVERSE: |
|
306 g_queue_reverse (q); |
|
307 g_assert (qinf->tail == q->head); |
|
308 g_assert (qinf->head == q->tail); |
|
309 g_assert (qinf->length == q->length); |
|
310 qinf->tail = q->tail; |
|
311 qinf->head = q->head; |
|
312 break; |
|
313 case COPY: |
|
314 { |
|
315 QueueInfo *random_queue = RANDOM_QUEUE(); |
|
316 GQueue *new_queue = g_queue_copy (random_queue->queue); |
|
317 |
|
318 g_queue_free (qinf->queue); |
|
319 q = qinf->queue = new_queue; |
|
320 qinf->head = new_queue->head; |
|
321 qinf->tail = g_list_last (new_queue->head); |
|
322 qinf->length = new_queue->length; |
|
323 } |
|
324 break; |
|
325 case FOREACH: |
|
326 delete_all (q); |
|
327 qinf->head = NULL; |
|
328 qinf->tail = NULL; |
|
329 qinf->length = 0; |
|
330 break; |
|
331 case FIND: |
|
332 { |
|
333 gboolean find_existing = rnd_bool (); |
|
334 int first = find_max (q); |
|
335 int second = find_min (q); |
|
336 |
|
337 if (q->length == 0) |
|
338 find_existing = FALSE; |
|
339 |
|
340 if (!find_existing) |
|
341 first++; |
|
342 if (!find_existing) |
|
343 second--; |
|
344 |
|
345 if (find_existing) |
|
346 { |
|
347 g_assert (g_queue_find (q, GINT_TO_POINTER (first))); |
|
348 g_assert (g_queue_find (q, GINT_TO_POINTER (second))); |
|
349 } |
|
350 else |
|
351 { |
|
352 g_assert (!g_queue_find (q, GINT_TO_POINTER (first))); |
|
353 g_assert (!g_queue_find (q, GINT_TO_POINTER (second))); |
|
354 } |
|
355 } |
|
356 break; |
|
357 case FIND_CUSTOM: |
|
358 break; |
|
359 case SORT: |
|
360 { |
|
361 if (!g_queue_is_empty (q)) |
|
362 { |
|
363 int max = find_max (q); |
|
364 int min = find_min (q); |
|
365 g_queue_remove_all (q, GINT_TO_POINTER (max)); |
|
366 check_integrity (q); |
|
367 g_queue_remove_all (q, GINT_TO_POINTER (min)); |
|
368 check_integrity (q); |
|
369 g_queue_push_head (q, GINT_TO_POINTER (max)); |
|
370 if (max != min) |
|
371 g_queue_push_head (q, GINT_TO_POINTER (min)); |
|
372 qinf->length = q->length; |
|
373 } |
|
374 |
|
375 check_integrity (q); |
|
376 |
|
377 g_queue_sort (q, compare_int, NULL); |
|
378 |
|
379 check_integrity (q); |
|
380 |
|
381 qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q))); |
|
382 qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q))); |
|
383 |
|
384 g_assert (qinf->tail == q->tail); |
|
385 } |
|
386 break; |
|
387 case PUSH_HEAD: |
|
388 { |
|
389 int x = g_random_int_range (0, 435435); |
|
390 g_queue_push_head (q, GINT_TO_POINTER (x)); |
|
391 if (!qinf->head) |
|
392 qinf->tail = qinf->head = q->head; |
|
393 else |
|
394 qinf->head = qinf->head->prev; |
|
395 qinf->length++; |
|
396 } |
|
397 break; |
|
398 case PUSH_TAIL: |
|
399 { |
|
400 int x = g_random_int_range (0, 236546); |
|
401 g_queue_push_tail (q, GINT_TO_POINTER (x)); |
|
402 if (!qinf->tail) |
|
403 qinf->tail = qinf->head = q->head; |
|
404 else |
|
405 qinf->tail = qinf->tail->next; |
|
406 qinf->length++; |
|
407 } |
|
408 break; |
|
409 case PUSH_NTH: |
|
410 { |
|
411 int pos = get_random_position (q, TRUE); |
|
412 int x = g_random_int_range (0, 236546); |
|
413 g_queue_push_nth (q, GINT_TO_POINTER (x), pos); |
|
414 if (qinf->head && qinf->head->prev) |
|
415 qinf->head = qinf->head->prev; |
|
416 else |
|
417 qinf->head = q->head; |
|
418 if (qinf->tail && qinf->tail->next) |
|
419 qinf->tail = qinf->tail->next; |
|
420 else |
|
421 qinf->tail = g_list_last (qinf->head); |
|
422 qinf->length++; |
|
423 } |
|
424 break; |
|
425 case POP_HEAD: |
|
426 if (qinf->head) |
|
427 qinf->head = qinf->head->next; |
|
428 if (!qinf->head) |
|
429 qinf->tail = NULL; |
|
430 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1; |
|
431 g_queue_pop_head (q); |
|
432 break; |
|
433 case POP_TAIL: |
|
434 if (qinf->tail) |
|
435 qinf->tail = qinf->tail->prev; |
|
436 if (!qinf->tail) |
|
437 qinf->head = NULL; |
|
438 qinf->length = (qinf->length == 0)? 0 : qinf->length - 1; |
|
439 g_queue_pop_tail (q); |
|
440 break; |
|
441 case POP_NTH: |
|
442 if (!g_queue_is_empty (q)) |
|
443 { |
|
444 int n = get_random_position (q, TRUE); |
|
445 gpointer elm = g_queue_peek_nth (q, n); |
|
446 |
|
447 if (n == q->length - 1) |
|
448 qinf->tail = qinf->tail->prev; |
|
449 |
|
450 if (n == 0) |
|
451 qinf->head = qinf->head->next; |
|
452 |
|
453 if (n >= 0 && n < q->length) |
|
454 qinf->length--; |
|
455 |
|
456 g_assert (elm == g_queue_pop_nth (q, n)); |
|
457 } |
|
458 break; |
|
459 case PEEK_HEAD: |
|
460 if (qinf->head) |
|
461 g_assert (qinf->head->data == g_queue_peek_head (q)); |
|
462 else |
|
463 g_assert (g_queue_peek_head (q) == NULL); |
|
464 break; |
|
465 case PEEK_TAIL: |
|
466 if (qinf->head) |
|
467 g_assert (qinf->tail->data == g_queue_peek_tail (q)); |
|
468 else |
|
469 g_assert (g_queue_peek_tail (q) == NULL); |
|
470 break; |
|
471 case PEEK_NTH: |
|
472 if (g_queue_is_empty (q)) |
|
473 { |
|
474 for (j = -10; j < 10; ++j) |
|
475 g_assert (g_queue_peek_nth (q, j) == NULL); |
|
476 } |
|
477 else |
|
478 { |
|
479 GList *list; |
|
480 int n = get_random_position (q, TRUE); |
|
481 if (n < 0 || n >= q->length) |
|
482 { |
|
483 g_assert (g_queue_peek_nth (q, n) == NULL); |
|
484 } |
|
485 else |
|
486 { |
|
487 list = qinf->head; |
|
488 for (j = 0; j < n; ++j) |
|
489 list = list->next; |
|
490 |
|
491 g_assert (list->data == g_queue_peek_nth (q, n)); |
|
492 } |
|
493 } |
|
494 break; |
|
495 case INDEX: |
|
496 case LINK_INDEX: |
|
497 { |
|
498 int x = g_random_int_range (0, 386538); |
|
499 int n; |
|
500 GList *list; |
|
501 |
|
502 g_queue_remove_all (q, GINT_TO_POINTER (x)); |
|
503 check_integrity (q); |
|
504 g_queue_push_tail (q, GINT_TO_POINTER (x)); |
|
505 check_integrity (q); |
|
506 g_queue_sort (q, compare_int, NULL); |
|
507 check_integrity (q); |
|
508 |
|
509 n = 0; |
|
510 for (list = q->head; list != NULL; list = list->next) |
|
511 { |
|
512 if (list->data == GINT_TO_POINTER (x)) |
|
513 break; |
|
514 n++; |
|
515 } |
|
516 g_assert (list); |
|
517 g_assert (g_queue_index (q, GINT_TO_POINTER (x)) == |
|
518 g_queue_link_index (q, list)); |
|
519 g_assert (g_queue_link_index (q, list) == n); |
|
520 |
|
521 qinf->head = q->head; |
|
522 qinf->tail = q->tail; |
|
523 qinf->length = q->length; |
|
524 } |
|
525 break; |
|
526 case REMOVE: |
|
527 if (!g_queue_is_empty (q)) |
|
528 g_queue_remove (q, qinf->tail->data); |
|
529 if (!g_queue_is_empty (q)) |
|
530 g_queue_remove (q, qinf->head->data); |
|
531 if (!g_queue_is_empty (q)) |
|
532 g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE))); |
|
533 |
|
534 qinf->head = q->head; |
|
535 qinf->tail = q->tail; |
|
536 qinf->length = q->length; |
|
537 break; |
|
538 case REMOVE_ALL: |
|
539 if (!g_queue_is_empty (q)) |
|
540 g_queue_remove_all (q, qinf->tail->data); |
|
541 if (!g_queue_is_empty (q)) |
|
542 g_queue_remove_all (q, qinf->head->data); |
|
543 if (!g_queue_is_empty (q)) |
|
544 g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE))); |
|
545 |
|
546 qinf->head = q->head; |
|
547 qinf->tail = q->tail; |
|
548 qinf->length = q->length; |
|
549 break; |
|
550 case INSERT_BEFORE: |
|
551 if (!g_queue_is_empty (q)) |
|
552 { |
|
553 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538)); |
|
554 |
|
555 g_queue_insert_before (q, qinf->tail, x); |
|
556 g_queue_insert_before (q, qinf->head, x); |
|
557 g_queue_insert_before (q, g_queue_find (q, x), x); |
|
558 } |
|
559 qinf->head = q->head; |
|
560 qinf->tail = q->tail; |
|
561 qinf->length = q->length; |
|
562 break; |
|
563 case INSERT_AFTER: |
|
564 if (!g_queue_is_empty (q)) |
|
565 { |
|
566 gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538)); |
|
567 |
|
568 g_queue_insert_after (q, qinf->tail, x); |
|
569 g_queue_insert_after (q, qinf->head, x); |
|
570 g_queue_insert_after (q, g_queue_find (q, x), x); |
|
571 } |
|
572 qinf->head = q->head; |
|
573 qinf->tail = q->tail; |
|
574 qinf->length = q->length; |
|
575 break; |
|
576 case INSERT_SORTED: |
|
577 { |
|
578 int max = find_max (q); |
|
579 int min = find_min (q); |
|
580 |
|
581 if (g_queue_is_empty (q)) |
|
582 { |
|
583 max = 345; |
|
584 min = -12; |
|
585 } |
|
586 |
|
587 g_queue_sort (q, compare_int, NULL); |
|
588 check_integrity (q); |
|
589 g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL); |
|
590 check_integrity (q); |
|
591 g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1); |
|
592 g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL); |
|
593 check_integrity (q); |
|
594 g_assert (GPOINTER_TO_INT (q->head->data) == min - 1); |
|
595 qinf->head = q->head; |
|
596 qinf->tail = q->tail; |
|
597 qinf->length = q->length; |
|
598 } |
|
599 break; |
|
600 case PUSH_HEAD_LINK: |
|
601 { |
|
602 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
|
603 g_queue_push_head_link (q, link); |
|
604 if (!qinf->tail) |
|
605 qinf->tail = link; |
|
606 qinf->head = link; |
|
607 qinf->length++; |
|
608 } |
|
609 break; |
|
610 case PUSH_TAIL_LINK: |
|
611 { |
|
612 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
|
613 g_queue_push_tail_link (q, link); |
|
614 if (!qinf->head) |
|
615 qinf->head = link; |
|
616 qinf->tail = link; |
|
617 qinf->length++; |
|
618 } |
|
619 break; |
|
620 case PUSH_NTH_LINK: |
|
621 { |
|
622 GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
|
623 gint n = get_random_position (q, TRUE); |
|
624 g_queue_push_nth_link (q, n, link); |
|
625 |
|
626 if (qinf->head && qinf->head->prev) |
|
627 qinf->head = qinf->head->prev; |
|
628 else |
|
629 qinf->head = q->head; |
|
630 if (qinf->tail && qinf->tail->next) |
|
631 qinf->tail = qinf->tail->next; |
|
632 else |
|
633 qinf->tail = g_list_last (qinf->head); |
|
634 qinf->length++; |
|
635 } |
|
636 break; |
|
637 case POP_HEAD_LINK: |
|
638 if (!g_queue_is_empty (q)) |
|
639 { |
|
640 qinf->head = qinf->head->next; |
|
641 if (!qinf->head) |
|
642 qinf->tail = NULL; |
|
643 qinf->length--; |
|
644 g_list_free (g_queue_pop_head_link (q)); |
|
645 } |
|
646 break; |
|
647 case POP_TAIL_LINK: |
|
648 if (!g_queue_is_empty (q)) |
|
649 { |
|
650 qinf->tail = qinf->tail->prev; |
|
651 if (!qinf->tail) |
|
652 qinf->head = NULL; |
|
653 qinf->length--; |
|
654 g_list_free (g_queue_pop_tail_link (q)); |
|
655 } |
|
656 break; |
|
657 case POP_NTH_LINK: |
|
658 if (g_queue_is_empty (q)) |
|
659 g_assert (g_queue_pop_nth_link (q, 200) == NULL); |
|
660 else |
|
661 { |
|
662 int n = get_random_position (q, FALSE); |
|
663 |
|
664 if (n == g_queue_get_length (q) - 1) |
|
665 qinf->tail = qinf->tail->prev; |
|
666 |
|
667 if (n == 0) |
|
668 qinf->head = qinf->head->next; |
|
669 |
|
670 qinf->length--; |
|
671 |
|
672 g_list_free (g_queue_pop_nth_link (q, n)); |
|
673 } |
|
674 break; |
|
675 case PEEK_HEAD_LINK: |
|
676 if (g_queue_is_empty (q)) |
|
677 g_assert (g_queue_peek_head_link (q) == NULL); |
|
678 else |
|
679 g_assert (g_queue_peek_head_link (q) == qinf->head); |
|
680 break; |
|
681 case PEEK_TAIL_LINK: |
|
682 if (g_queue_is_empty (q)) |
|
683 g_assert (g_queue_peek_tail_link (q) == NULL); |
|
684 else |
|
685 g_assert (g_queue_peek_tail_link (q) == qinf->tail); |
|
686 break; |
|
687 case PEEK_NTH_LINK: |
|
688 if (g_queue_is_empty(q)) |
|
689 g_assert (g_queue_peek_nth_link (q, 1000) == NULL); |
|
690 else |
|
691 { |
|
692 gint n = get_random_position (q, FALSE); |
|
693 GList *link; |
|
694 |
|
695 link = q->head; |
|
696 for (j = 0; j < n; ++j) |
|
697 link = link->next; |
|
698 |
|
699 g_assert (g_queue_peek_nth_link (q, n) == link); |
|
700 } |
|
701 break; |
|
702 case UNLINK: |
|
703 if (!g_queue_is_empty (q)) |
|
704 { |
|
705 gint n = g_random_int_range (0, g_queue_get_length (q)); |
|
706 GList *link; |
|
707 |
|
708 link = q->head; |
|
709 for (j = 0; j < n; ++j) |
|
710 link = link->next; |
|
711 |
|
712 g_queue_unlink (q, link); |
|
713 check_integrity (q); |
|
714 |
|
715 g_list_free (link); |
|
716 |
|
717 qinf->head = q->head; |
|
718 qinf->tail = q->tail; |
|
719 qinf->length--; |
|
720 } |
|
721 break; |
|
722 case DELETE_LINK: |
|
723 if (!g_queue_is_empty (q)) |
|
724 { |
|
725 gint n = g_random_int_range (0, g_queue_get_length (q)); |
|
726 GList *link; |
|
727 |
|
728 link = q->head; |
|
729 for (j = 0; j < n; ++j) |
|
730 link = link->next; |
|
731 |
|
732 g_queue_delete_link (q, link); |
|
733 check_integrity (q); |
|
734 |
|
735 qinf->head = q->head; |
|
736 qinf->tail = q->tail; |
|
737 qinf->length--; |
|
738 } |
|
739 break; |
|
740 case LAST_OP: |
|
741 default: |
|
742 g_assert_not_reached(); |
|
743 break; |
|
744 } |
|
745 |
|
746 if (qinf->head != q->head || |
|
747 qinf->tail != q->tail || |
|
748 qinf->length != q->length) |
|
749 g_print ("op: %d\n", op); |
|
750 |
|
751 g_assert (qinf->head == q->head); |
|
752 g_assert (qinf->tail == q->tail); |
|
753 g_assert (qinf->length == q->length); |
|
754 |
|
755 for (j = 0; j < N_QUEUES; ++j) |
|
756 check_integrity (queues[j].queue); |
|
757 } |
|
758 |
|
759 for (i = 0; i < N_QUEUES; ++i) |
|
760 g_queue_free (queues[i].queue); |
|
761 } |
|
762 |
|
763 static void |
|
764 remove_item (gpointer data, gpointer q) |
|
765 { |
|
766 GQueue *queue = q; |
|
767 |
|
768 g_queue_remove (queue, data); |
|
769 } |
|
770 |
|
771 int main(int argc, gchar *args[]) |
|
772 { |
|
773 GQueue *q, *q2; |
|
774 GList *node; |
|
775 gpointer data; |
|
776 int i; |
|
777 |
|
778 #ifdef __SYMBIAN32__ |
|
779 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); |
|
780 g_set_print_handler(mrtPrintHandler); |
|
781 #endif /*__SYMBIAN32__*/ |
|
782 |
|
783 if (argc > 1 && args[1][0] == '-' && args[1][1] == 'v') |
|
784 verbose = TRUE; |
|
785 |
|
786 q = g_queue_new (); |
|
787 |
|
788 g_assert (g_queue_is_empty (q) == TRUE); |
|
789 |
|
790 g_queue_push_head (q, GINT_TO_POINTER (2)); |
|
791 check_integrity (q); |
|
792 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2)); |
|
793 check_integrity (q); |
|
794 g_assert (g_queue_is_empty (q) == FALSE); |
|
795 check_integrity (q); |
|
796 g_assert (g_list_length (q->head) == 1); |
|
797 g_assert (q->head == q->tail); |
|
798 g_queue_push_head (q, GINT_TO_POINTER (1)); |
|
799 check_integrity (q); |
|
800 g_assert (q->head->next == q->tail); |
|
801 g_assert (q->tail->prev == q->head); |
|
802 g_assert (g_list_length (q->head) == 2); |
|
803 check_integrity (q); |
|
804 g_assert (q->tail->data == GINT_TO_POINTER (2)); |
|
805 g_assert (q->head->data == GINT_TO_POINTER (1)); |
|
806 check_integrity (q); |
|
807 g_queue_push_tail (q, GINT_TO_POINTER (3)); |
|
808 g_assert (g_list_length (q->head) == 3); |
|
809 g_assert (q->head->data == GINT_TO_POINTER (1)); |
|
810 g_assert (q->head->next->data == GINT_TO_POINTER (2)); |
|
811 g_assert (q->head->next->next == q->tail); |
|
812 g_assert (q->head->next == q->tail->prev); |
|
813 g_assert (q->tail->data == GINT_TO_POINTER (3)); |
|
814 g_queue_push_tail (q, GINT_TO_POINTER (4)); |
|
815 check_integrity (q); |
|
816 g_assert (g_list_length (q->head) == 4); |
|
817 g_assert (q->head->data == GINT_TO_POINTER (1)); |
|
818 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4)); |
|
819 g_queue_push_tail (q, GINT_TO_POINTER (5)); |
|
820 check_integrity (q); |
|
821 g_assert (g_list_length (q->head) == 5); |
|
822 |
|
823 g_assert (g_queue_is_empty (q) == FALSE); |
|
824 check_integrity (q); |
|
825 |
|
826 g_assert (q->length == 5); |
|
827 g_assert (q->head->prev == NULL); |
|
828 g_assert (q->head->data == GINT_TO_POINTER (1)); |
|
829 g_assert (q->head->next->data == GINT_TO_POINTER (2)); |
|
830 g_assert (q->head->next->next->data == GINT_TO_POINTER (3)); |
|
831 g_assert (q->head->next->next->next->data == GINT_TO_POINTER (4)); |
|
832 g_assert (q->head->next->next->next->next->data == GINT_TO_POINTER (5)); |
|
833 g_assert (q->head->next->next->next->next->next == NULL); |
|
834 g_assert (q->head->next->next->next->next == q->tail); |
|
835 g_assert (q->tail->data == GINT_TO_POINTER (5)); |
|
836 g_assert (q->tail->prev->data == GINT_TO_POINTER (4)); |
|
837 g_assert (q->tail->prev->prev->data == GINT_TO_POINTER (3)); |
|
838 g_assert (q->tail->prev->prev->prev->data == GINT_TO_POINTER (2)); |
|
839 g_assert (q->tail->prev->prev->prev->prev->data == GINT_TO_POINTER (1)); |
|
840 g_assert (q->tail->prev->prev->prev->prev->prev == NULL); |
|
841 g_assert (q->tail->prev->prev->prev->prev == q->head); |
|
842 g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5)); |
|
843 g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1)); |
|
844 |
|
845 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1)); |
|
846 check_integrity (q); |
|
847 g_assert (g_list_length (q->head) == 4 && q->length == 4); |
|
848 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5)); |
|
849 check_integrity (q); |
|
850 g_assert (g_list_length (q->head) == 3); |
|
851 g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2)); |
|
852 check_integrity (q); |
|
853 g_assert (g_list_length (q->head) == 2); |
|
854 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4)); |
|
855 check_integrity (q); |
|
856 g_assert (g_list_length (q->head) == 1); |
|
857 g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3)); |
|
858 check_integrity (q); |
|
859 g_assert (g_list_length (q->head) == 0); |
|
860 g_assert (g_queue_pop_tail (q) == NULL); |
|
861 check_integrity (q); |
|
862 g_assert (g_list_length (q->head) == 0); |
|
863 g_assert (g_queue_pop_head (q) == NULL); |
|
864 check_integrity (q); |
|
865 g_assert (g_list_length (q->head) == 0); |
|
866 |
|
867 g_assert (g_queue_is_empty (q) == TRUE); |
|
868 check_integrity (q); |
|
869 |
|
870 /************************/ |
|
871 |
|
872 g_queue_push_head (q, GINT_TO_POINTER (1)); |
|
873 check_integrity (q); |
|
874 g_assert (g_list_length (q->head) == 1 && 1 == q->length); |
|
875 g_queue_push_head (q, GINT_TO_POINTER (2)); |
|
876 check_integrity (q); |
|
877 g_assert (g_list_length (q->head) == 2 && 2 == q->length); |
|
878 g_queue_push_head (q, GINT_TO_POINTER (3)); |
|
879 check_integrity (q); |
|
880 g_assert (g_list_length (q->head) == 3 && 3 == q->length); |
|
881 g_queue_push_head (q, GINT_TO_POINTER (4)); |
|
882 check_integrity (q); |
|
883 g_assert (g_list_length (q->head) == 4 && 4 == q->length); |
|
884 g_queue_push_head (q, GINT_TO_POINTER (5)); |
|
885 check_integrity (q); |
|
886 g_assert (g_list_length (q->head) == 5 && 5 == q->length); |
|
887 |
|
888 g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5)); |
|
889 check_integrity (q); |
|
890 g_assert (g_list_length (q->head) == 4); |
|
891 node = q->tail; |
|
892 g_assert (node == g_queue_pop_tail_link (q)); |
|
893 check_integrity (q); |
|
894 g_assert (g_list_length (q->head) == 3); |
|
895 data = q->head->data; |
|
896 g_assert (data == g_queue_pop_head (q)); |
|
897 check_integrity (q); |
|
898 g_assert (g_list_length (q->head) == 2); |
|
899 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2)); |
|
900 check_integrity (q); |
|
901 g_assert (g_list_length (q->head) == 1); |
|
902 g_assert (q->head == q->tail); |
|
903 g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3)); |
|
904 check_integrity (q); |
|
905 g_assert (g_list_length (q->head) == 0); |
|
906 g_assert (g_queue_pop_head (q) == NULL); |
|
907 check_integrity (q); |
|
908 g_assert (g_queue_pop_head_link (q) == NULL); |
|
909 check_integrity (q); |
|
910 g_assert (g_list_length (q->head) == 0); |
|
911 g_assert (g_queue_pop_tail_link (q) == NULL); |
|
912 check_integrity (q); |
|
913 g_assert (g_list_length (q->head) == 0); |
|
914 |
|
915 /* */ |
|
916 g_queue_reverse (q); |
|
917 check_integrity (q); |
|
918 g_assert (g_list_length (q->head) == 0); |
|
919 |
|
920 q2 = g_queue_copy (q); |
|
921 check_integrity (q); |
|
922 check_integrity (q2); |
|
923 g_assert (g_list_length (q->head) == 0); |
|
924 g_assert (g_list_length (q2->head) == 0); |
|
925 g_queue_sort (q, compare_int, NULL); |
|
926 check_integrity (q2); |
|
927 check_integrity (q); |
|
928 g_queue_sort (q2, compare_int, NULL); |
|
929 check_integrity (q2); |
|
930 check_integrity (q); |
|
931 |
|
932 for (i = 0; i < 200; ++i) |
|
933 { |
|
934 g_queue_push_nth (q, GINT_TO_POINTER (i), i); |
|
935 g_assert (g_queue_find (q, GINT_TO_POINTER (i))); |
|
936 check_integrity (q); |
|
937 check_integrity (q2); |
|
938 } |
|
939 |
|
940 for (i = 0; i < 200; ++i) |
|
941 { |
|
942 g_queue_remove (q, GINT_TO_POINTER (i)); |
|
943 check_integrity (q); |
|
944 check_integrity (q2); |
|
945 } |
|
946 |
|
947 for (i = 0; i < 200; ++i) |
|
948 { |
|
949 GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i)); |
|
950 |
|
951 g_queue_push_nth_link (q, i, l); |
|
952 check_integrity (q); |
|
953 check_integrity (q2); |
|
954 g_queue_reverse (q); |
|
955 check_integrity (q); |
|
956 check_integrity (q2); |
|
957 } |
|
958 |
|
959 g_queue_free (q2); |
|
960 q2 = g_queue_copy (q); |
|
961 |
|
962 g_queue_foreach (q2, remove_item, q2); |
|
963 check_integrity (q2); |
|
964 check_integrity (q); |
|
965 |
|
966 /* some checks for off by one errors */ |
|
967 g_queue_push_tail (q, GINT_TO_POINTER (1234)); |
|
968 check_integrity (q); |
|
969 node = g_queue_peek_tail_link (q); |
|
970 g_assert (node != NULL && node->data == GINT_TO_POINTER (1234)); |
|
971 node = g_queue_peek_nth_link (q, g_queue_get_length (q)); |
|
972 g_assert (node == NULL); |
|
973 node = g_queue_peek_nth_link (q, g_queue_get_length (q) - 1); |
|
974 g_assert (node->data == GINT_TO_POINTER (1234)); |
|
975 node = g_queue_pop_nth_link (q, g_queue_get_length (q)); |
|
976 g_assert (node == NULL); |
|
977 node = g_queue_pop_nth_link (q, g_queue_get_length (q) - 1); |
|
978 g_assert (node != NULL && node->data == GINT_TO_POINTER (1234)); |
|
979 |
|
980 g_queue_free (q); |
|
981 |
|
982 if (argc > 2 && args[1][0] == '-' && args[1][1] == 'v') |
|
983 random_test (strtol (args[2], NULL, 0)); |
|
984 if (argc > 1) |
|
985 random_test (strtol (args[1], NULL, 0)); |
|
986 else |
|
987 random_test (time (0)); |
|
988 #ifdef __SYMBIAN32__ |
|
989 testResultXml("queue-test"); |
|
990 #endif /* EMULATOR */ |
|
991 |
|
992 return 0; |
|
993 } |
|
994 |