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