1 /* -*- mode: C; c-file-style: "gnu" -*- */ 2 /* dbus-list.c Generic linked list utility (internal to D-Bus implementation) 3 * 4 * Copyright (C) 2002 Red Hat, Inc. 5 * 6 * Licensed under the Academic Free License version 2.1 7 * 8 * This program is free software; you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License as published by 10 * the Free Software Foundation; either version 2 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 21 * 22 */ 23 24 #include "dbus-internals.h" 25 #include "dbus-list.h" 26 #include "dbus-mempool.h" 27 #include "dbus-threads-internal.h" 28 29 /** 30 * @defgroup DBusList Linked list 31 * @ingroup DBusInternals 32 * @brief DBusList data structure 33 * 34 * Types and functions related to DBusList. 35 */ 36 37 static DBusMemPool *list_pool; 38 _DBUS_DEFINE_GLOBAL_LOCK (list); 39 40 /** 41 * @defgroup DBusListInternals Linked list implementation details 42 * @ingroup DBusInternals 43 * @brief DBusList implementation details 44 * 45 * The guts of DBusList. 46 * 47 * @{ 48 */ 49 50 /* the mem pool is probably a speed hit, with the thread 51 * lock, though it does still save memory - unknown. 52 */ 53 static DBusList* 54 alloc_link (void *data) 55 { 56 DBusList *link; 57 58 _DBUS_LOCK (list); 59 60 if (list_pool == NULL) 61 { 62 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE); 63 64 if (list_pool == NULL) 65 { 66 _DBUS_UNLOCK (list); 67 return NULL; 68 } 69 70 link = _dbus_mem_pool_alloc (list_pool); 71 if (link == NULL) 72 { 73 _dbus_mem_pool_free (list_pool); 74 list_pool = NULL; 75 _DBUS_UNLOCK (list); 76 return NULL; 77 } 78 } 79 else 80 { 81 link = _dbus_mem_pool_alloc (list_pool); 82 } 83 84 if (link) 85 link->data = data; 86 87 _DBUS_UNLOCK (list); 88 89 return link; 90 } 91 92 static void 93 free_link (DBusList *link) 94 { 95 _DBUS_LOCK (list); 96 if (_dbus_mem_pool_dealloc (list_pool, link)) 97 { 98 _dbus_mem_pool_free (list_pool); 99 list_pool = NULL; 100 } 101 102 _DBUS_UNLOCK (list); 103 } 104 105 static void 106 link_before (DBusList **list, 107 DBusList *before_this_link, 108 DBusList *link) 109 { 110 if (*list == NULL) 111 { 112 link->prev = link; 113 link->next = link; 114 *list = link; 115 } 116 else 117 { 118 link->next = before_this_link; 119 link->prev = before_this_link->prev; 120 before_this_link->prev = link; 121 link->prev->next = link; 122 123 if (before_this_link == *list) 124 *list = link; 125 } 126 } 127 128 static void 129 link_after (DBusList **list, 130 DBusList *after_this_link, 131 DBusList *link) 132 { 133 if (*list == NULL) 134 { 135 link->prev = link; 136 link->next = link; 137 *list = link; 138 } 139 else 140 { 141 link->prev = after_this_link; 142 link->next = after_this_link->next; 143 after_this_link->next = link; 144 link->next->prev = link; 145 } 146 } 147 148 /** @} */ 149 150 /** 151 * @addtogroup DBusList 152 * @{ 153 */ 154 155 /** 156 * @struct DBusList 157 * 158 * A node in a linked list. 159 * 160 * DBusList is a circular list; that is, the tail of the list 161 * points back to the head of the list. The empty list is 162 * represented by a #NULL pointer. 163 */ 164 165 /** 166 * @def _dbus_list_get_next_link 167 * 168 * Gets the next link in the list, or #NULL if 169 * there are no more links. Used for iteration. 170 * 171 * @code 172 * DBusList *link; 173 * link = _dbus_list_get_first_link (&list); 174 * while (link != NULL) 175 * { 176 * printf ("value is %p\n", link->data); 177 * link = _dbus_list_get_next_link (&link); 178 * } 179 * @endcode 180 * 181 * @param list address of the list head. 182 * @param link current link. 183 * @returns the next link, or %NULL if none. 184 * 185 */ 186 187 /** 188 * @def _dbus_list_get_prev_link 189 * 190 * Gets the previous link in the list, or #NULL if 191 * there are no more links. Used for iteration. 192 * 193 * @code 194 * DBusList *link; 195 * link = _dbus_list_get_last_link (&list); 196 * while (link != NULL) 197 * { 198 * printf ("value is %p\n", link->data); 199 * link = _dbus_list_get_prev_link (&link); 200 * } 201 * @endcode 202 * 203 * @param list address of the list head. 204 * @param link current link. 205 * @returns the previous link, or %NULL if none. 206 * 207 */ 208 209 /** 210 * Allocates a linked list node. Useful for preallocating 211 * nodes and using _dbus_list_append_link() to avoid 212 * allocations. 213 * 214 * @param data the value to store in the link. 215 * @returns a newly allocated link. 216 */ 217 DBusList* 218 _dbus_list_alloc_link (void *data) 219 { 220 return alloc_link (data); 221 } 222 223 /** 224 * Frees a linked list node allocated with _dbus_list_alloc_link. 225 * Does not free the data in the node. 226 * 227 * @param link the list node 228 */ 229 void 230 _dbus_list_free_link (DBusList *link) 231 { 232 free_link (link); 233 } 234 235 236 /** 237 * Appends a value to the list. May return #FALSE 238 * if insufficient memory exists to add a list link. 239 * This is a constant-time operation. 240 * 241 * @param list address of the list head. 242 * @param data the value to append. 243 * @returns #TRUE on success. 244 */ 245 dbus_bool_t 246 _dbus_list_append (DBusList **list, 247 void *data) 248 { 249 if (!_dbus_list_prepend (list, data)) 250 return FALSE; 251 252 /* Now cycle the list forward one so the prepended node is the tail */ 253 *list = (*list)->next; 254 255 return TRUE; 256 } 257 258 /** 259 * Prepends a value to the list. May return #FALSE 260 * if insufficient memory exists to add a list link. 261 * This is a constant-time operation. 262 * 263 * @param list address of the list head. 264 * @param data the value to prepend. 265 * @returns #TRUE on success. 266 */ 267 dbus_bool_t 268 _dbus_list_prepend (DBusList **list, 269 void *data) 270 { 271 DBusList *link; 272 273 link = alloc_link (data); 274 if (link == NULL) 275 return FALSE; 276 277 link_before (list, *list, link); 278 279 return TRUE; 280 } 281 282 /** 283 * Appends a link to the list. 284 * Cannot fail due to out of memory. 285 * This is a constant-time operation. 286 * 287 * @param list address of the list head. 288 * @param link the link to append. 289 */ 290 void 291 _dbus_list_append_link (DBusList **list, 292 DBusList *link) 293 { 294 _dbus_list_prepend_link (list, link); 295 296 /* Now cycle the list forward one so the prepended node is the tail */ 297 *list = (*list)->next; 298 } 299 300 /** 301 * Prepends a link to the list. 302 * Cannot fail due to out of memory. 303 * This is a constant-time operation. 304 * 305 * @param list address of the list head. 306 * @param link the link to prepend. 307 */ 308 void 309 _dbus_list_prepend_link (DBusList **list, 310 DBusList *link) 311 { 312 link_before (list, *list, link); 313 } 314 315 #ifdef DBUS_BUILD_TESTS 316 /** 317 * Inserts data into the list before the given existing link. 318 * 319 * @param list the list to modify 320 * @param before_this_link existing link to insert before, or #NULL to append 321 * @param data the value to insert 322 * @returns #TRUE on success, #FALSE if memory allocation fails 323 */ 324 dbus_bool_t 325 _dbus_list_insert_before (DBusList **list, 326 DBusList *before_this_link, 327 void *data) 328 { 329 DBusList *link; 330 331 if (before_this_link == NULL) 332 return _dbus_list_append (list, data); 333 else 334 { 335 link = alloc_link (data); 336 if (link == NULL) 337 return FALSE; 338 339 link_before (list, before_this_link, link); 340 } 341 342 return TRUE; 343 } 344 #endif /* DBUS_BUILD_TESTS */ 345 346 /** 347 * Inserts data into the list after the given existing link. 348 * 349 * @param list the list to modify 350 * @param after_this_link existing link to insert after, or #NULL to prepend 351 * @param data the value to insert 352 * @returns #TRUE on success, #FALSE if memory allocation fails 353 */ 354 dbus_bool_t 355 _dbus_list_insert_after (DBusList **list, 356 DBusList *after_this_link, 357 void *data) 358 { 359 DBusList *link; 360 361 if (after_this_link == NULL) 362 return _dbus_list_prepend (list, data); 363 else 364 { 365 link = alloc_link (data); 366 if (link == NULL) 367 return FALSE; 368 369 link_after (list, after_this_link, link); 370 } 371 372 return TRUE; 373 } 374 375 /** 376 * Inserts a link into the list before the given existing link. 377 * 378 * @param list the list to modify 379 * @param before_this_link existing link to insert before, or #NULL to append 380 * @param link the link to insert 381 */ 382 void 383 _dbus_list_insert_before_link (DBusList **list, 384 DBusList *before_this_link, 385 DBusList *link) 386 { 387 if (before_this_link == NULL) 388 _dbus_list_append_link (list, link); 389 else 390 link_before (list, before_this_link, link); 391 } 392 393 /** 394 * Inserts a link into the list after the given existing link. 395 * 396 * @param list the list to modify 397 * @param after_this_link existing link to insert after, or #NULL to prepend 398 * @param link the link to insert 399 */ 400 void 401 _dbus_list_insert_after_link (DBusList **list, 402 DBusList *after_this_link, 403 DBusList *link) 404 { 405 if (after_this_link == NULL) 406 _dbus_list_prepend_link (list, link); 407 else 408 link_after (list, after_this_link, link); 409 } 410 411 /** 412 * Removes a value from the list. Only removes the 413 * first value equal to the given data pointer, 414 * even if multiple values exist which match. 415 * This is a linear-time operation. 416 * 417 * @param list address of the list head. 418 * @param data the value to remove. 419 * @returns #TRUE if a value was found to remove. 420 */ 421 dbus_bool_t 422 _dbus_list_remove (DBusList **list, 423 void *data) 424 { 425 DBusList *link; 426 427 link = *list; 428 while (link != NULL) 429 { 430 if (link->data == data) 431 { 432 _dbus_list_remove_link (list, link); 433 return TRUE; 434 } 435 436 link = _dbus_list_get_next_link (list, link); 437 } 438 439 return FALSE; 440 } 441 442 /** 443 * Removes a value from the list. Only removes the 444 * last value equal to the given data pointer, 445 * even if multiple values exist which match. 446 * This is a linear-time operation. 447 * 448 * @param list address of the list head. 449 * @param data the value to remove. 450 * @returns #TRUE if a value was found to remove. 451 */ 452 dbus_bool_t 453 _dbus_list_remove_last (DBusList **list, 454 void *data) 455 { 456 DBusList *link; 457 458 link = _dbus_list_find_last (list, data); 459 if (link) 460 { 461 _dbus_list_remove_link (list, link); 462 return TRUE; 463 } 464 else 465 return FALSE; 466 } 467 468 /** 469 * Finds a value in the list. Returns the last link 470 * with value equal to the given data pointer. 471 * This is a linear-time operation. 472 * Returns #NULL if no value found that matches. 473 * 474 * @param list address of the list head. 475 * @param data the value to find. 476 * @returns the link if found 477 */ 478 DBusList* 479 _dbus_list_find_last (DBusList **list, 480 void *data) 481 { 482 DBusList *link; 483 484 link = _dbus_list_get_last_link (list); 485 486 while (link != NULL) 487 { 488 if (link->data == data) 489 return link; 490 491 link = _dbus_list_get_prev_link (list, link); 492 } 493 494 return NULL; 495 } 496 497 /** 498 * Removes the given link from the list, but doesn't 499 * free it. _dbus_list_remove_link() both removes the 500 * link and also frees it. 501 * 502 * @param list the list 503 * @param link the link in the list 504 */ 505 void 506 _dbus_list_unlink (DBusList **list, 507 DBusList *link) 508 { 509 if (link->next == link) 510 { 511 /* one-element list */ 512 *list = NULL; 513 } 514 else 515 { 516 link->prev->next = link->next; 517 link->next->prev = link->prev; 518 519 if (*list == link) 520 *list = link->next; 521 } 522 523 link->next = NULL; 524 link->prev = NULL; 525 } 526 527 /** 528 * Removes a link from the list. This is a constant-time operation. 529 * 530 * @param list address of the list head. 531 * @param link the list link to remove. 532 */ 533 void 534 _dbus_list_remove_link (DBusList **list, 535 DBusList *link) 536 { 537 _dbus_list_unlink (list, link); 538 free_link (link); 539 } 540 541 /** 542 * Frees all links in the list and sets the list head to #NULL. Does 543 * not free the data in each link, for obvious reasons. This is a 544 * linear-time operation. 545 * 546 * @param list address of the list head. 547 */ 548 void 549 _dbus_list_clear (DBusList **list) 550 { 551 DBusList *link; 552 553 link = *list; 554 while (link != NULL) 555 { 556 DBusList *next = _dbus_list_get_next_link (list, link); 557 558 free_link (link); 559 560 link = next; 561 } 562 563 *list = NULL; 564 } 565 566 /** 567 * Gets the first link in the list. 568 * This is a constant-time operation. 569 * 570 * @param list address of the list head. 571 * @returns the first link, or #NULL for an empty list. 572 */ 573 DBusList* 574 _dbus_list_get_first_link (DBusList **list) 575 { 576 return *list; 577 } 578 579 /** 580 * Gets the last link in the list. 581 * This is a constant-time operation. 582 * 583 * @param list address of the list head. 584 * @returns the last link, or #NULL for an empty list. 585 */ 586 DBusList* 587 _dbus_list_get_last_link (DBusList **list) 588 { 589 if (*list == NULL) 590 return NULL; 591 else 592 return (*list)->prev; 593 } 594 595 /** 596 * Gets the last data in the list. 597 * This is a constant-time operation. 598 * 599 * @param list address of the list head. 600 * @returns the last data in the list, or #NULL for an empty list. 601 */ 602 void* 603 _dbus_list_get_last (DBusList **list) 604 { 605 if (*list == NULL) 606 return NULL; 607 else 608 return (*list)->prev->data; 609 } 610 611 /** 612 * Gets the first data in the list. 613 * This is a constant-time operation. 614 * 615 * @param list address of the list head. 616 * @returns the first data in the list, or #NULL for an empty list. 617 */ 618 void* 619 _dbus_list_get_first (DBusList **list) 620 { 621 if (*list == NULL) 622 return NULL; 623 else 624 return (*list)->data; 625 } 626 627 /** 628 * Removes the first link in the list and returns it. This is a 629 * constant-time operation. 630 * 631 * @param list address of the list head. 632 * @returns the first link in the list, or #NULL for an empty list. 633 */ 634 DBusList* 635 _dbus_list_pop_first_link (DBusList **list) 636 { 637 DBusList *link; 638 639 link = _dbus_list_get_first_link (list); 640 if (link == NULL) 641 return NULL; 642 643 _dbus_list_unlink (list, link); 644 645 return link; 646 } 647 648 /** 649 * Removes the first value in the list and returns it. This is a 650 * constant-time operation. 651 * 652 * @param list address of the list head. 653 * @returns the first data in the list, or #NULL for an empty list. 654 */ 655 void* 656 _dbus_list_pop_first (DBusList **list) 657 { 658 DBusList *link; 659 void *data; 660 661 link = _dbus_list_get_first_link (list); 662 if (link == NULL) 663 return NULL; 664 665 data = link->data; 666 _dbus_list_remove_link (list, link); 667 668 return data; 669 } 670 671 /** 672 * Removes the last value in the list and returns it. This is a 673 * constant-time operation. 674 * 675 * @param list address of the list head. 676 * @returns the last data in the list, or #NULL for an empty list. 677 */ 678 void* 679 _dbus_list_pop_last (DBusList **list) 680 { 681 DBusList *link; 682 void *data; 683 684 link = _dbus_list_get_last_link (list); 685 if (link == NULL) 686 return NULL; 687 688 data = link->data; 689 _dbus_list_remove_link (list, link); 690 691 return data; 692 } 693 694 #ifdef DBUS_BUILD_TESTS 695 /** 696 * Removes the last link in the list and returns it. This is a 697 * constant-time operation. 698 * 699 * @param list address of the list head. 700 * @returns the last link in the list, or #NULL for an empty list. 701 */ 702 DBusList* 703 _dbus_list_pop_last_link (DBusList **list) 704 { 705 DBusList *link; 706 707 link = _dbus_list_get_last_link (list); 708 if (link == NULL) 709 return NULL; 710 711 _dbus_list_unlink (list, link); 712 713 return link; 714 } 715 #endif /* DBUS_BUILD_TESTS */ 716 717 /** 718 * Copies a list. This is a linear-time operation. If there isn't 719 * enough memory to copy the entire list, the destination list will be 720 * set to #NULL. 721 * 722 * @param list address of the head of the list to copy. 723 * @param dest address where the copied list should be placed. 724 * @returns #TRUE on success, #FALSE if not enough memory. 725 */ 726 dbus_bool_t 727 _dbus_list_copy (DBusList **list, 728 DBusList **dest) 729 { 730 DBusList *link; 731 732 _dbus_assert (list != dest); 733 734 *dest = NULL; 735 736 link = *list; 737 while (link != NULL) 738 { 739 if (!_dbus_list_append (dest, link->data)) 740 { 741 /* free what we have so far */ 742 _dbus_list_clear (dest); 743 return FALSE; 744 } 745 746 link = _dbus_list_get_next_link (list, link); 747 } 748 749 return TRUE; 750 } 751 752 /** 753 * Gets the length of a list. This is a linear-time 754 * operation. 755 * 756 * @param list address of the head of the list 757 * @returns number of elements in the list. 758 */ 759 int 760 _dbus_list_get_length (DBusList **list) 761 { 762 DBusList *link; 763 int length; 764 765 length = 0; 766 767 link = *list; 768 while (link != NULL) 769 { 770 ++length; 771 772 link = _dbus_list_get_next_link (list, link); 773 } 774 775 return length; 776 } 777 778 /** 779 * Calls the given function for each element in the list. The 780 * function is passed the list element as its first argument, and the 781 * given data as its second argument. 782 * 783 * @param list address of the head of the list. 784 * @param function function to call for each element. 785 * @param data extra data for the function. 786 * 787 */ 788 void 789 _dbus_list_foreach (DBusList **list, 790 DBusForeachFunction function, 791 void *data) 792 { 793 DBusList *link; 794 795 link = *list; 796 while (link != NULL) 797 { 798 DBusList *next = _dbus_list_get_next_link (list, link); 799 800 (* function) (link->data, data); 801 802 link = next; 803 } 804 } 805 806 /** 807 * Check whether length is exactly one. 808 * 809 * @param list the list 810 * @returns #TRUE if length is exactly one 811 */ 812 dbus_bool_t 813 _dbus_list_length_is_one (DBusList **list) 814 { 815 return (*list != NULL && 816 (*list)->next == *list); 817 } 818 819 /** @} */ 820 821 #ifdef DBUS_BUILD_TESTS 822 #include "dbus-test.h" 823 #include <stdio.h> 824 825 static void 826 verify_list (DBusList **list) 827 { 828 DBusList *link; 829 int length; 830 831 link = *list; 832 833 if (link == NULL) 834 return; 835 836 if (link->next == link) 837 { 838 _dbus_assert (link->prev == link); 839 _dbus_assert (*list == link); 840 return; 841 } 842 843 length = 0; 844 do 845 { 846 length += 1; 847 _dbus_assert (link->prev->next == link); 848 _dbus_assert (link->next->prev == link); 849 link = link->next; 850 } 851 while (link != *list); 852 853 _dbus_assert (length == _dbus_list_get_length (list)); 854 855 if (length == 1) 856 _dbus_assert (_dbus_list_length_is_one (list)); 857 else 858 _dbus_assert (!_dbus_list_length_is_one (list)); 859 } 860 861 static dbus_bool_t 862 is_ascending_sequence (DBusList **list) 863 { 864 DBusList *link; 865 int prev; 866 867 prev = _DBUS_INT_MIN; 868 869 link = _dbus_list_get_first_link (list); 870 while (link != NULL) 871 { 872 int v = _DBUS_POINTER_TO_INT (link->data); 873 874 if (v <= prev) 875 return FALSE; 876 877 prev = v; 878 879 link = _dbus_list_get_next_link (list, link); 880 } 881 882 return TRUE; 883 } 884 885 static dbus_bool_t 886 is_descending_sequence (DBusList **list) 887 { 888 DBusList *link; 889 int prev; 890 891 prev = _DBUS_INT_MAX; 892 893 link = _dbus_list_get_first_link (list); 894 while (link != NULL) 895 { 896 int v = _DBUS_POINTER_TO_INT (link->data); 897 898 if (v >= prev) 899 return FALSE; 900 901 prev = v; 902 903 link = _dbus_list_get_next_link (list, link); 904 } 905 906 return TRUE; 907 } 908 909 static dbus_bool_t 910 all_even_values (DBusList **list) 911 { 912 DBusList *link; 913 914 link = _dbus_list_get_first_link (list); 915 while (link != NULL) 916 { 917 int v = _DBUS_POINTER_TO_INT (link->data); 918 919 if ((v % 2) != 0) 920 return FALSE; 921 922 link = _dbus_list_get_next_link (list, link); 923 } 924 925 return TRUE; 926 } 927 928 static dbus_bool_t 929 all_odd_values (DBusList **list) 930 { 931 DBusList *link; 932 933 link = _dbus_list_get_first_link (list); 934 while (link != NULL) 935 { 936 int v = _DBUS_POINTER_TO_INT (link->data); 937 938 if ((v % 2) == 0) 939 return FALSE; 940 941 link = _dbus_list_get_next_link (list, link); 942 } 943 944 return TRUE; 945 } 946 947 static dbus_bool_t 948 lists_equal (DBusList **list1, 949 DBusList **list2) 950 { 951 DBusList *link1; 952 DBusList *link2; 953 954 link1 = _dbus_list_get_first_link (list1); 955 link2 = _dbus_list_get_first_link (list2); 956 while (link1 && link2) 957 { 958 if (link1->data != link2->data) 959 return FALSE; 960 961 link1 = _dbus_list_get_next_link (list1, link1); 962 link2 = _dbus_list_get_next_link (list2, link2); 963 } 964 965 if (link1 || link2) 966 return FALSE; 967 968 return TRUE; 969 } 970 971 /** 972 * @ingroup DBusListInternals 973 * Unit test for DBusList 974 * @returns #TRUE on success. 975 */ 976 dbus_bool_t 977 _dbus_list_test (void) 978 { 979 DBusList *list1; 980 DBusList *list2; 981 DBusList *link1; 982 DBusList *link2; 983 DBusList *copy1; 984 DBusList *copy2; 985 int i; 986 987 list1 = NULL; 988 list2 = NULL; 989 990 /* Test append and prepend */ 991 992 i = 0; 993 while (i < 10) 994 { 995 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i))) 996 _dbus_assert_not_reached ("could not allocate for append"); 997 998 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i))) 999 _dbus_assert_not_reached ("count not allocate for prepend"); 1000 ++i; 1001 1002 verify_list (&list1); 1003 verify_list (&list2); 1004 1005 _dbus_assert (_dbus_list_get_length (&list1) == i); 1006 _dbus_assert (_dbus_list_get_length (&list2) == i); 1007 } 1008 1009 _dbus_assert (is_ascending_sequence (&list1)); 1010 _dbus_assert (is_descending_sequence (&list2)); 1011 1012 /* Test list clear */ 1013 _dbus_list_clear (&list1); 1014 _dbus_list_clear (&list2); 1015 1016 verify_list (&list1); 1017 verify_list (&list2); 1018 1019 /* Test get_first, get_last, pop_first, pop_last */ 1020 1021 i = 0; 1022 while (i < 10) 1023 { 1024 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1025 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1026 ++i; 1027 } 1028 1029 --i; 1030 while (i >= 0) 1031 { 1032 void *got_data1; 1033 void *got_data2; 1034 1035 void *data1; 1036 void *data2; 1037 1038 got_data1 = _dbus_list_get_last (&list1); 1039 got_data2 = _dbus_list_get_first (&list2); 1040 1041 data1 = _dbus_list_pop_last (&list1); 1042 data2 = _dbus_list_pop_first (&list2); 1043 1044 _dbus_assert (got_data1 == data1); 1045 _dbus_assert (got_data2 == data2); 1046 1047 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 1048 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 1049 1050 verify_list (&list1); 1051 verify_list (&list2); 1052 1053 _dbus_assert (is_ascending_sequence (&list1)); 1054 _dbus_assert (is_descending_sequence (&list2)); 1055 1056 --i; 1057 } 1058 1059 _dbus_assert (list1 == NULL); 1060 _dbus_assert (list2 == NULL); 1061 1062 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */ 1063 1064 i = 0; 1065 while (i < 10) 1066 { 1067 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1068 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1069 ++i; 1070 } 1071 1072 --i; 1073 while (i >= 0) 1074 { 1075 DBusList *got_link1; 1076 DBusList *got_link2; 1077 1078 DBusList *link1; 1079 DBusList *link2; 1080 1081 void *data1; 1082 void *data2; 1083 1084 got_link1 = _dbus_list_get_last_link (&list1); 1085 got_link2 = _dbus_list_get_first_link (&list2); 1086 1087 link1 = _dbus_list_pop_last_link (&list1); 1088 link2 = _dbus_list_pop_first_link (&list2); 1089 1090 _dbus_assert (got_link1 == link1); 1091 _dbus_assert (got_link2 == link2); 1092 1093 data1 = link1->data; 1094 data2 = link2->data; 1095 1096 _dbus_list_free_link (link1); 1097 _dbus_list_free_link (link2); 1098 1099 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 1100 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 1101 1102 verify_list (&list1); 1103 verify_list (&list2); 1104 1105 _dbus_assert (is_ascending_sequence (&list1)); 1106 _dbus_assert (is_descending_sequence (&list2)); 1107 1108 --i; 1109 } 1110 1111 _dbus_assert (list1 == NULL); 1112 _dbus_assert (list2 == NULL); 1113 1114 /* Test iteration */ 1115 1116 i = 0; 1117 while (i < 10) 1118 { 1119 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1120 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1121 ++i; 1122 1123 verify_list (&list1); 1124 verify_list (&list2); 1125 1126 _dbus_assert (_dbus_list_get_length (&list1) == i); 1127 _dbus_assert (_dbus_list_get_length (&list2) == i); 1128 } 1129 1130 _dbus_assert (is_ascending_sequence (&list1)); 1131 _dbus_assert (is_descending_sequence (&list2)); 1132 1133 --i; 1134 link2 = _dbus_list_get_first_link (&list2); 1135 while (link2 != NULL) 1136 { 1137 verify_list (&link2); /* pretend this link is the head */ 1138 1139 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 1140 1141 link2 = _dbus_list_get_next_link (&list2, link2); 1142 --i; 1143 } 1144 1145 i = 0; 1146 link1 = _dbus_list_get_first_link (&list1); 1147 while (link1 != NULL) 1148 { 1149 verify_list (&link1); /* pretend this link is the head */ 1150 1151 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 1152 1153 link1 = _dbus_list_get_next_link (&list1, link1); 1154 ++i; 1155 } 1156 1157 --i; 1158 link1 = _dbus_list_get_last_link (&list1); 1159 while (link1 != NULL) 1160 { 1161 verify_list (&link1); /* pretend this link is the head */ 1162 1163 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 1164 1165 link1 = _dbus_list_get_prev_link (&list1, link1); 1166 --i; 1167 } 1168 1169 _dbus_list_clear (&list1); 1170 _dbus_list_clear (&list2); 1171 1172 /* Test remove */ 1173 1174 i = 0; 1175 while (i < 10) 1176 { 1177 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1178 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1179 ++i; 1180 } 1181 1182 --i; 1183 while (i >= 0) 1184 { 1185 if ((i % 2) == 0) 1186 { 1187 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 1188 _dbus_assert_not_reached ("element should have been in list"); 1189 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 1190 _dbus_assert_not_reached ("element should have been in list"); 1191 1192 verify_list (&list1); 1193 verify_list (&list2); 1194 } 1195 --i; 1196 } 1197 1198 _dbus_assert (all_odd_values (&list1)); 1199 _dbus_assert (all_odd_values (&list2)); 1200 1201 _dbus_list_clear (&list1); 1202 _dbus_list_clear (&list2); 1203 1204 /* test removing the other half of the elements */ 1205 1206 i = 0; 1207 while (i < 10) 1208 { 1209 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1210 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1211 ++i; 1212 } 1213 1214 --i; 1215 while (i >= 0) 1216 { 1217 if ((i % 2) != 0) 1218 { 1219 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 1220 _dbus_assert_not_reached ("element should have been in list"); 1221 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 1222 _dbus_assert_not_reached ("element should have been in list"); 1223 1224 verify_list (&list1); 1225 verify_list (&list2); 1226 } 1227 --i; 1228 } 1229 1230 _dbus_assert (all_even_values (&list1)); 1231 _dbus_assert (all_even_values (&list2)); 1232 1233 /* clear list using remove_link */ 1234 while (list1 != NULL) 1235 { 1236 _dbus_list_remove_link (&list1, list1); 1237 verify_list (&list1); 1238 } 1239 while (list2 != NULL) 1240 { 1241 _dbus_list_remove_link (&list2, list2); 1242 verify_list (&list2); 1243 } 1244 1245 /* Test remove link more generally */ 1246 i = 0; 1247 while (i < 10) 1248 { 1249 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1250 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1251 ++i; 1252 } 1253 1254 --i; 1255 link2 = _dbus_list_get_first_link (&list2); 1256 while (link2 != NULL) 1257 { 1258 DBusList *next = _dbus_list_get_next_link (&list2, link2); 1259 1260 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 1261 1262 if ((i % 2) == 0) 1263 _dbus_list_remove_link (&list2, link2); 1264 1265 verify_list (&list2); 1266 1267 link2 = next; 1268 --i; 1269 } 1270 1271 _dbus_assert (all_odd_values (&list2)); 1272 _dbus_list_clear (&list2); 1273 1274 i = 0; 1275 link1 = _dbus_list_get_first_link (&list1); 1276 while (link1 != NULL) 1277 { 1278 DBusList *next = _dbus_list_get_next_link (&list1, link1); 1279 1280 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 1281 1282 if ((i % 2) != 0) 1283 _dbus_list_remove_link (&list1, link1); 1284 1285 verify_list (&list1); 1286 1287 link1 = next; 1288 ++i; 1289 } 1290 1291 _dbus_assert (all_even_values (&list1)); 1292 _dbus_list_clear (&list1); 1293 1294 /* Test copying a list */ 1295 i = 0; 1296 while (i < 10) 1297 { 1298 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 1299 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 1300 ++i; 1301 } 1302 1303 /* bad pointers, because they are allowed in the copy dest */ 1304 copy1 = _DBUS_INT_TO_POINTER (0x342234); 1305 copy2 = _DBUS_INT_TO_POINTER (23); 1306 1307 _dbus_list_copy (&list1, ©1); 1308 verify_list (&list1); 1309 verify_list (©1); 1310 _dbus_assert (lists_equal (&list1, ©1)); 1311 1312 _dbus_list_copy (&list2, ©2); 1313 verify_list (&list2); 1314 verify_list (©2); 1315 _dbus_assert (lists_equal (&list2, ©2)); 1316 1317 /* Now test copying empty lists */ 1318 _dbus_list_clear (&list1); 1319 _dbus_list_clear (&list2); 1320 _dbus_list_clear (©1); 1321 _dbus_list_clear (©2); 1322 1323 /* bad pointers, because they are allowed in the copy dest */ 1324 copy1 = _DBUS_INT_TO_POINTER (0x342234); 1325 copy2 = _DBUS_INT_TO_POINTER (23); 1326 1327 _dbus_list_copy (&list1, ©1); 1328 verify_list (&list1); 1329 verify_list (©1); 1330 _dbus_assert (lists_equal (&list1, ©1)); 1331 1332 _dbus_list_copy (&list2, ©2); 1333 verify_list (&list2); 1334 verify_list (©2); 1335 _dbus_assert (lists_equal (&list2, ©2)); 1336 1337 _dbus_list_clear (&list1); 1338 _dbus_list_clear (&list2); 1339 1340 /* insert_before on empty list */ 1341 _dbus_list_insert_before (&list1, NULL, 1342 _DBUS_INT_TO_POINTER (0)); 1343 verify_list (&list1); 1344 1345 /* inserting before first element */ 1346 _dbus_list_insert_before (&list1, list1, 1347 _DBUS_INT_TO_POINTER (2)); 1348 verify_list (&list1); 1349 _dbus_assert (is_descending_sequence (&list1)); 1350 1351 /* inserting in the middle */ 1352 _dbus_list_insert_before (&list1, list1->next, 1353 _DBUS_INT_TO_POINTER (1)); 1354 verify_list (&list1); 1355 _dbus_assert (is_descending_sequence (&list1)); 1356 1357 /* using insert_before to append */ 1358 _dbus_list_insert_before (&list1, NULL, 1359 _DBUS_INT_TO_POINTER (-1)); 1360 verify_list (&list1); 1361 _dbus_assert (is_descending_sequence (&list1)); 1362 1363 _dbus_list_clear (&list1); 1364 1365 /* insert_after on empty list */ 1366 _dbus_list_insert_after (&list1, NULL, 1367 _DBUS_INT_TO_POINTER (0)); 1368 verify_list (&list1); 1369 1370 /* inserting after first element */ 1371 _dbus_list_insert_after (&list1, list1, 1372 _DBUS_INT_TO_POINTER (1)); 1373 verify_list (&list1); 1374 _dbus_assert (is_ascending_sequence (&list1)); 1375 1376 /* inserting at the end */ 1377 _dbus_list_insert_after (&list1, list1->next, 1378 _DBUS_INT_TO_POINTER (2)); 1379 verify_list (&list1); 1380 _dbus_assert (is_ascending_sequence (&list1)); 1381 1382 /* using insert_after to prepend */ 1383 _dbus_list_insert_after (&list1, NULL, 1384 _DBUS_INT_TO_POINTER (-1)); 1385 verify_list (&list1); 1386 _dbus_assert (is_ascending_sequence (&list1)); 1387 1388 _dbus_list_clear (&list1); 1389 1390 /* using remove_last */ 1391 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)); 1392 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)); 1393 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)); 1394 1395 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2)); 1396 1397 verify_list (&list1); 1398 _dbus_assert (is_ascending_sequence (&list1)); 1399 1400 _dbus_list_clear (&list1); 1401 1402 return TRUE; 1403 } 1404 1405 #endif 1406