D-Bus
1.4.16
|
00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ 00002 /* dbus-list.c Generic linked list utility (internal to D-Bus implementation) 00003 * 00004 * Copyright (C) 2002 Red Hat, Inc. 00005 * 00006 * Licensed under the Academic Free License version 2.1 00007 * 00008 * This program is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU General Public License as published by 00010 * the Free Software Foundation; either version 2 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * This program is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU General Public License 00019 * along with this program; if not, write to the Free Software 00020 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00021 * 00022 */ 00023 00024 #include <config.h> 00025 #include "dbus-internals.h" 00026 #include "dbus-list.h" 00027 #include "dbus-mempool.h" 00028 #include "dbus-threads-internal.h" 00029 00038 static DBusMemPool *list_pool; 00039 _DBUS_DEFINE_GLOBAL_LOCK (list); 00040 00051 /* the mem pool is probably a speed hit, with the thread 00052 * lock, though it does still save memory - unknown. 00053 */ 00054 static DBusList* 00055 alloc_link (void *data) 00056 { 00057 DBusList *link; 00058 00059 _DBUS_LOCK (list); 00060 00061 if (list_pool == NULL) 00062 { 00063 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE); 00064 00065 if (list_pool == NULL) 00066 { 00067 _DBUS_UNLOCK (list); 00068 return NULL; 00069 } 00070 00071 link = _dbus_mem_pool_alloc (list_pool); 00072 if (link == NULL) 00073 { 00074 _dbus_mem_pool_free (list_pool); 00075 list_pool = NULL; 00076 _DBUS_UNLOCK (list); 00077 return NULL; 00078 } 00079 } 00080 else 00081 { 00082 link = _dbus_mem_pool_alloc (list_pool); 00083 } 00084 00085 if (link) 00086 link->data = data; 00087 00088 _DBUS_UNLOCK (list); 00089 00090 return link; 00091 } 00092 00093 static void 00094 free_link (DBusList *link) 00095 { 00096 _DBUS_LOCK (list); 00097 if (_dbus_mem_pool_dealloc (list_pool, link)) 00098 { 00099 _dbus_mem_pool_free (list_pool); 00100 list_pool = NULL; 00101 } 00102 00103 _DBUS_UNLOCK (list); 00104 } 00105 00106 static void 00107 link_before (DBusList **list, 00108 DBusList *before_this_link, 00109 DBusList *link) 00110 { 00111 if (*list == NULL) 00112 { 00113 link->prev = link; 00114 link->next = link; 00115 *list = link; 00116 } 00117 else 00118 { 00119 link->next = before_this_link; 00120 link->prev = before_this_link->prev; 00121 before_this_link->prev = link; 00122 link->prev->next = link; 00123 00124 if (before_this_link == *list) 00125 *list = link; 00126 } 00127 } 00128 00129 static void 00130 link_after (DBusList **list, 00131 DBusList *after_this_link, 00132 DBusList *link) 00133 { 00134 if (*list == NULL) 00135 { 00136 link->prev = link; 00137 link->next = link; 00138 *list = link; 00139 } 00140 else 00141 { 00142 link->prev = after_this_link; 00143 link->next = after_this_link->next; 00144 after_this_link->next = link; 00145 link->next->prev = link; 00146 } 00147 } 00148 00218 DBusList* 00219 _dbus_list_alloc_link (void *data) 00220 { 00221 return alloc_link (data); 00222 } 00223 00230 void 00231 _dbus_list_free_link (DBusList *link) 00232 { 00233 free_link (link); 00234 } 00235 00236 00246 dbus_bool_t 00247 _dbus_list_append (DBusList **list, 00248 void *data) 00249 { 00250 if (!_dbus_list_prepend (list, data)) 00251 return FALSE; 00252 00253 /* Now cycle the list forward one so the prepended node is the tail */ 00254 *list = (*list)->next; 00255 00256 return TRUE; 00257 } 00258 00268 dbus_bool_t 00269 _dbus_list_prepend (DBusList **list, 00270 void *data) 00271 { 00272 DBusList *link; 00273 00274 link = alloc_link (data); 00275 if (link == NULL) 00276 return FALSE; 00277 00278 link_before (list, *list, link); 00279 00280 return TRUE; 00281 } 00282 00291 void 00292 _dbus_list_append_link (DBusList **list, 00293 DBusList *link) 00294 { 00295 _dbus_list_prepend_link (list, link); 00296 00297 /* Now cycle the list forward one so the prepended node is the tail */ 00298 *list = (*list)->next; 00299 } 00300 00309 void 00310 _dbus_list_prepend_link (DBusList **list, 00311 DBusList *link) 00312 { 00313 link_before (list, *list, link); 00314 } 00315 00316 #ifdef DBUS_BUILD_TESTS 00317 00325 dbus_bool_t 00326 _dbus_list_insert_before (DBusList **list, 00327 DBusList *before_this_link, 00328 void *data) 00329 { 00330 DBusList *link; 00331 00332 if (before_this_link == NULL) 00333 return _dbus_list_append (list, data); 00334 else 00335 { 00336 link = alloc_link (data); 00337 if (link == NULL) 00338 return FALSE; 00339 00340 link_before (list, before_this_link, link); 00341 } 00342 00343 return TRUE; 00344 } 00345 #endif /* DBUS_BUILD_TESTS */ 00346 00355 dbus_bool_t 00356 _dbus_list_insert_after (DBusList **list, 00357 DBusList *after_this_link, 00358 void *data) 00359 { 00360 DBusList *link; 00361 00362 if (after_this_link == NULL) 00363 return _dbus_list_prepend (list, data); 00364 else 00365 { 00366 link = alloc_link (data); 00367 if (link == NULL) 00368 return FALSE; 00369 00370 link_after (list, after_this_link, link); 00371 } 00372 00373 return TRUE; 00374 } 00375 00383 void 00384 _dbus_list_insert_before_link (DBusList **list, 00385 DBusList *before_this_link, 00386 DBusList *link) 00387 { 00388 if (before_this_link == NULL) 00389 _dbus_list_append_link (list, link); 00390 else 00391 link_before (list, before_this_link, link); 00392 } 00393 00401 void 00402 _dbus_list_insert_after_link (DBusList **list, 00403 DBusList *after_this_link, 00404 DBusList *link) 00405 { 00406 if (after_this_link == NULL) 00407 _dbus_list_prepend_link (list, link); 00408 else 00409 link_after (list, after_this_link, link); 00410 } 00411 00422 dbus_bool_t 00423 _dbus_list_remove (DBusList **list, 00424 void *data) 00425 { 00426 DBusList *link; 00427 00428 link = *list; 00429 while (link != NULL) 00430 { 00431 if (link->data == data) 00432 { 00433 _dbus_list_remove_link (list, link); 00434 return TRUE; 00435 } 00436 00437 link = _dbus_list_get_next_link (list, link); 00438 } 00439 00440 return FALSE; 00441 } 00442 00453 dbus_bool_t 00454 _dbus_list_remove_last (DBusList **list, 00455 void *data) 00456 { 00457 DBusList *link; 00458 00459 link = _dbus_list_find_last (list, data); 00460 if (link) 00461 { 00462 _dbus_list_remove_link (list, link); 00463 return TRUE; 00464 } 00465 else 00466 return FALSE; 00467 } 00468 00479 DBusList* 00480 _dbus_list_find_last (DBusList **list, 00481 void *data) 00482 { 00483 DBusList *link; 00484 00485 link = _dbus_list_get_last_link (list); 00486 00487 while (link != NULL) 00488 { 00489 if (link->data == data) 00490 return link; 00491 00492 link = _dbus_list_get_prev_link (list, link); 00493 } 00494 00495 return NULL; 00496 } 00497 00506 void 00507 _dbus_list_unlink (DBusList **list, 00508 DBusList *link) 00509 { 00510 if (link->next == link) 00511 { 00512 /* one-element list */ 00513 *list = NULL; 00514 } 00515 else 00516 { 00517 link->prev->next = link->next; 00518 link->next->prev = link->prev; 00519 00520 if (*list == link) 00521 *list = link->next; 00522 } 00523 00524 link->next = NULL; 00525 link->prev = NULL; 00526 } 00527 00534 void 00535 _dbus_list_remove_link (DBusList **list, 00536 DBusList *link) 00537 { 00538 _dbus_list_unlink (list, link); 00539 free_link (link); 00540 } 00541 00549 void 00550 _dbus_list_clear (DBusList **list) 00551 { 00552 DBusList *link; 00553 00554 link = *list; 00555 while (link != NULL) 00556 { 00557 DBusList *next = _dbus_list_get_next_link (list, link); 00558 00559 free_link (link); 00560 00561 link = next; 00562 } 00563 00564 *list = NULL; 00565 } 00566 00574 DBusList* 00575 _dbus_list_get_first_link (DBusList **list) 00576 { 00577 return *list; 00578 } 00579 00587 DBusList* 00588 _dbus_list_get_last_link (DBusList **list) 00589 { 00590 if (*list == NULL) 00591 return NULL; 00592 else 00593 return (*list)->prev; 00594 } 00595 00603 void* 00604 _dbus_list_get_last (DBusList **list) 00605 { 00606 if (*list == NULL) 00607 return NULL; 00608 else 00609 return (*list)->prev->data; 00610 } 00611 00619 void* 00620 _dbus_list_get_first (DBusList **list) 00621 { 00622 if (*list == NULL) 00623 return NULL; 00624 else 00625 return (*list)->data; 00626 } 00627 00635 DBusList* 00636 _dbus_list_pop_first_link (DBusList **list) 00637 { 00638 DBusList *link; 00639 00640 link = _dbus_list_get_first_link (list); 00641 if (link == NULL) 00642 return NULL; 00643 00644 _dbus_list_unlink (list, link); 00645 00646 return link; 00647 } 00648 00656 void* 00657 _dbus_list_pop_first (DBusList **list) 00658 { 00659 DBusList *link; 00660 void *data; 00661 00662 link = _dbus_list_get_first_link (list); 00663 if (link == NULL) 00664 return NULL; 00665 00666 data = link->data; 00667 _dbus_list_remove_link (list, link); 00668 00669 return data; 00670 } 00671 00679 void* 00680 _dbus_list_pop_last (DBusList **list) 00681 { 00682 DBusList *link; 00683 void *data; 00684 00685 link = _dbus_list_get_last_link (list); 00686 if (link == NULL) 00687 return NULL; 00688 00689 data = link->data; 00690 _dbus_list_remove_link (list, link); 00691 00692 return data; 00693 } 00694 00695 #ifdef DBUS_BUILD_TESTS 00696 00703 DBusList* 00704 _dbus_list_pop_last_link (DBusList **list) 00705 { 00706 DBusList *link; 00707 00708 link = _dbus_list_get_last_link (list); 00709 if (link == NULL) 00710 return NULL; 00711 00712 _dbus_list_unlink (list, link); 00713 00714 return link; 00715 } 00716 #endif /* DBUS_BUILD_TESTS */ 00717 00727 dbus_bool_t 00728 _dbus_list_copy (DBusList **list, 00729 DBusList **dest) 00730 { 00731 DBusList *link; 00732 00733 _dbus_assert (list != dest); 00734 00735 *dest = NULL; 00736 00737 link = *list; 00738 while (link != NULL) 00739 { 00740 if (!_dbus_list_append (dest, link->data)) 00741 { 00742 /* free what we have so far */ 00743 _dbus_list_clear (dest); 00744 return FALSE; 00745 } 00746 00747 link = _dbus_list_get_next_link (list, link); 00748 } 00749 00750 return TRUE; 00751 } 00752 00760 int 00761 _dbus_list_get_length (DBusList **list) 00762 { 00763 DBusList *link; 00764 int length; 00765 00766 length = 0; 00767 00768 link = *list; 00769 while (link != NULL) 00770 { 00771 ++length; 00772 00773 link = _dbus_list_get_next_link (list, link); 00774 } 00775 00776 return length; 00777 } 00778 00789 void 00790 _dbus_list_foreach (DBusList **list, 00791 DBusForeachFunction function, 00792 void *data) 00793 { 00794 DBusList *link; 00795 00796 link = *list; 00797 while (link != NULL) 00798 { 00799 DBusList *next = _dbus_list_get_next_link (list, link); 00800 00801 (* function) (link->data, data); 00802 00803 link = next; 00804 } 00805 } 00806 00813 dbus_bool_t 00814 _dbus_list_length_is_one (DBusList **list) 00815 { 00816 return (*list != NULL && 00817 (*list)->next == *list); 00818 } 00819 00822 #ifdef DBUS_BUILD_TESTS 00823 #include "dbus-test.h" 00824 #include <stdio.h> 00825 00826 static void 00827 verify_list (DBusList **list) 00828 { 00829 DBusList *link; 00830 int length; 00831 00832 link = *list; 00833 00834 if (link == NULL) 00835 return; 00836 00837 if (link->next == link) 00838 { 00839 _dbus_assert (link->prev == link); 00840 _dbus_assert (*list == link); 00841 return; 00842 } 00843 00844 length = 0; 00845 do 00846 { 00847 length += 1; 00848 _dbus_assert (link->prev->next == link); 00849 _dbus_assert (link->next->prev == link); 00850 link = link->next; 00851 } 00852 while (link != *list); 00853 00854 _dbus_assert (length == _dbus_list_get_length (list)); 00855 00856 if (length == 1) 00857 _dbus_assert (_dbus_list_length_is_one (list)); 00858 else 00859 _dbus_assert (!_dbus_list_length_is_one (list)); 00860 } 00861 00862 static dbus_bool_t 00863 is_ascending_sequence (DBusList **list) 00864 { 00865 DBusList *link; 00866 int prev; 00867 00868 prev = _DBUS_INT_MIN; 00869 00870 link = _dbus_list_get_first_link (list); 00871 while (link != NULL) 00872 { 00873 int v = _DBUS_POINTER_TO_INT (link->data); 00874 00875 if (v <= prev) 00876 return FALSE; 00877 00878 prev = v; 00879 00880 link = _dbus_list_get_next_link (list, link); 00881 } 00882 00883 return TRUE; 00884 } 00885 00886 static dbus_bool_t 00887 is_descending_sequence (DBusList **list) 00888 { 00889 DBusList *link; 00890 int prev; 00891 00892 prev = _DBUS_INT_MAX; 00893 00894 link = _dbus_list_get_first_link (list); 00895 while (link != NULL) 00896 { 00897 int v = _DBUS_POINTER_TO_INT (link->data); 00898 00899 if (v >= prev) 00900 return FALSE; 00901 00902 prev = v; 00903 00904 link = _dbus_list_get_next_link (list, link); 00905 } 00906 00907 return TRUE; 00908 } 00909 00910 static dbus_bool_t 00911 all_even_values (DBusList **list) 00912 { 00913 DBusList *link; 00914 00915 link = _dbus_list_get_first_link (list); 00916 while (link != NULL) 00917 { 00918 int v = _DBUS_POINTER_TO_INT (link->data); 00919 00920 if ((v % 2) != 0) 00921 return FALSE; 00922 00923 link = _dbus_list_get_next_link (list, link); 00924 } 00925 00926 return TRUE; 00927 } 00928 00929 static dbus_bool_t 00930 all_odd_values (DBusList **list) 00931 { 00932 DBusList *link; 00933 00934 link = _dbus_list_get_first_link (list); 00935 while (link != NULL) 00936 { 00937 int v = _DBUS_POINTER_TO_INT (link->data); 00938 00939 if ((v % 2) == 0) 00940 return FALSE; 00941 00942 link = _dbus_list_get_next_link (list, link); 00943 } 00944 00945 return TRUE; 00946 } 00947 00948 static dbus_bool_t 00949 lists_equal (DBusList **list1, 00950 DBusList **list2) 00951 { 00952 DBusList *link1; 00953 DBusList *link2; 00954 00955 link1 = _dbus_list_get_first_link (list1); 00956 link2 = _dbus_list_get_first_link (list2); 00957 while (link1 && link2) 00958 { 00959 if (link1->data != link2->data) 00960 return FALSE; 00961 00962 link1 = _dbus_list_get_next_link (list1, link1); 00963 link2 = _dbus_list_get_next_link (list2, link2); 00964 } 00965 00966 if (link1 || link2) 00967 return FALSE; 00968 00969 return TRUE; 00970 } 00971 00977 dbus_bool_t 00978 _dbus_list_test (void) 00979 { 00980 DBusList *list1; 00981 DBusList *list2; 00982 DBusList *link1; 00983 DBusList *link2; 00984 DBusList *copy1; 00985 DBusList *copy2; 00986 int i; 00987 00988 list1 = NULL; 00989 list2 = NULL; 00990 00991 /* Test append and prepend */ 00992 00993 i = 0; 00994 while (i < 10) 00995 { 00996 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i))) 00997 _dbus_assert_not_reached ("could not allocate for append"); 00998 00999 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i))) 01000 _dbus_assert_not_reached ("count not allocate for prepend"); 01001 ++i; 01002 01003 verify_list (&list1); 01004 verify_list (&list2); 01005 01006 _dbus_assert (_dbus_list_get_length (&list1) == i); 01007 _dbus_assert (_dbus_list_get_length (&list2) == i); 01008 } 01009 01010 _dbus_assert (is_ascending_sequence (&list1)); 01011 _dbus_assert (is_descending_sequence (&list2)); 01012 01013 /* Test list clear */ 01014 _dbus_list_clear (&list1); 01015 _dbus_list_clear (&list2); 01016 01017 verify_list (&list1); 01018 verify_list (&list2); 01019 01020 /* Test get_first, get_last, pop_first, pop_last */ 01021 01022 i = 0; 01023 while (i < 10) 01024 { 01025 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01026 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01027 ++i; 01028 } 01029 01030 --i; 01031 while (i >= 0) 01032 { 01033 void *got_data1; 01034 void *got_data2; 01035 01036 void *data1; 01037 void *data2; 01038 01039 got_data1 = _dbus_list_get_last (&list1); 01040 got_data2 = _dbus_list_get_first (&list2); 01041 01042 data1 = _dbus_list_pop_last (&list1); 01043 data2 = _dbus_list_pop_first (&list2); 01044 01045 _dbus_assert (got_data1 == data1); 01046 _dbus_assert (got_data2 == data2); 01047 01048 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01049 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01050 01051 verify_list (&list1); 01052 verify_list (&list2); 01053 01054 _dbus_assert (is_ascending_sequence (&list1)); 01055 _dbus_assert (is_descending_sequence (&list2)); 01056 01057 --i; 01058 } 01059 01060 _dbus_assert (list1 == NULL); 01061 _dbus_assert (list2 == NULL); 01062 01063 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */ 01064 01065 i = 0; 01066 while (i < 10) 01067 { 01068 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01069 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01070 ++i; 01071 } 01072 01073 --i; 01074 while (i >= 0) 01075 { 01076 DBusList *got_link1; 01077 DBusList *got_link2; 01078 01079 DBusList *link1; 01080 DBusList *link2; 01081 01082 void *data1; 01083 void *data2; 01084 01085 got_link1 = _dbus_list_get_last_link (&list1); 01086 got_link2 = _dbus_list_get_first_link (&list2); 01087 01088 link1 = _dbus_list_pop_last_link (&list1); 01089 link2 = _dbus_list_pop_first_link (&list2); 01090 01091 _dbus_assert (got_link1 == link1); 01092 _dbus_assert (got_link2 == link2); 01093 01094 data1 = link1->data; 01095 data2 = link2->data; 01096 01097 _dbus_list_free_link (link1); 01098 _dbus_list_free_link (link2); 01099 01100 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01101 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01102 01103 verify_list (&list1); 01104 verify_list (&list2); 01105 01106 _dbus_assert (is_ascending_sequence (&list1)); 01107 _dbus_assert (is_descending_sequence (&list2)); 01108 01109 --i; 01110 } 01111 01112 _dbus_assert (list1 == NULL); 01113 _dbus_assert (list2 == NULL); 01114 01115 /* Test iteration */ 01116 01117 i = 0; 01118 while (i < 10) 01119 { 01120 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01121 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01122 ++i; 01123 01124 verify_list (&list1); 01125 verify_list (&list2); 01126 01127 _dbus_assert (_dbus_list_get_length (&list1) == i); 01128 _dbus_assert (_dbus_list_get_length (&list2) == i); 01129 } 01130 01131 _dbus_assert (is_ascending_sequence (&list1)); 01132 _dbus_assert (is_descending_sequence (&list2)); 01133 01134 --i; 01135 link2 = _dbus_list_get_first_link (&list2); 01136 while (link2 != NULL) 01137 { 01138 verify_list (&link2); /* pretend this link is the head */ 01139 01140 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01141 01142 link2 = _dbus_list_get_next_link (&list2, link2); 01143 --i; 01144 } 01145 01146 i = 0; 01147 link1 = _dbus_list_get_first_link (&list1); 01148 while (link1 != NULL) 01149 { 01150 verify_list (&link1); /* pretend this link is the head */ 01151 01152 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01153 01154 link1 = _dbus_list_get_next_link (&list1, link1); 01155 ++i; 01156 } 01157 01158 --i; 01159 link1 = _dbus_list_get_last_link (&list1); 01160 while (link1 != NULL) 01161 { 01162 verify_list (&link1); /* pretend this link is the head */ 01163 01164 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01165 01166 link1 = _dbus_list_get_prev_link (&list1, link1); 01167 --i; 01168 } 01169 01170 _dbus_list_clear (&list1); 01171 _dbus_list_clear (&list2); 01172 01173 /* Test remove */ 01174 01175 i = 0; 01176 while (i < 10) 01177 { 01178 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01179 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01180 ++i; 01181 } 01182 01183 --i; 01184 while (i >= 0) 01185 { 01186 if ((i % 2) == 0) 01187 { 01188 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01189 _dbus_assert_not_reached ("element should have been in list"); 01190 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01191 _dbus_assert_not_reached ("element should have been in list"); 01192 01193 verify_list (&list1); 01194 verify_list (&list2); 01195 } 01196 --i; 01197 } 01198 01199 _dbus_assert (all_odd_values (&list1)); 01200 _dbus_assert (all_odd_values (&list2)); 01201 01202 _dbus_list_clear (&list1); 01203 _dbus_list_clear (&list2); 01204 01205 /* test removing the other half of the elements */ 01206 01207 i = 0; 01208 while (i < 10) 01209 { 01210 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01211 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01212 ++i; 01213 } 01214 01215 --i; 01216 while (i >= 0) 01217 { 01218 if ((i % 2) != 0) 01219 { 01220 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01221 _dbus_assert_not_reached ("element should have been in list"); 01222 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01223 _dbus_assert_not_reached ("element should have been in list"); 01224 01225 verify_list (&list1); 01226 verify_list (&list2); 01227 } 01228 --i; 01229 } 01230 01231 _dbus_assert (all_even_values (&list1)); 01232 _dbus_assert (all_even_values (&list2)); 01233 01234 /* clear list using remove_link */ 01235 while (list1 != NULL) 01236 { 01237 _dbus_list_remove_link (&list1, list1); 01238 verify_list (&list1); 01239 } 01240 while (list2 != NULL) 01241 { 01242 _dbus_list_remove_link (&list2, list2); 01243 verify_list (&list2); 01244 } 01245 01246 /* Test remove link more generally */ 01247 i = 0; 01248 while (i < 10) 01249 { 01250 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01251 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01252 ++i; 01253 } 01254 01255 --i; 01256 link2 = _dbus_list_get_first_link (&list2); 01257 while (link2 != NULL) 01258 { 01259 DBusList *next = _dbus_list_get_next_link (&list2, link2); 01260 01261 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01262 01263 if ((i % 2) == 0) 01264 _dbus_list_remove_link (&list2, link2); 01265 01266 verify_list (&list2); 01267 01268 link2 = next; 01269 --i; 01270 } 01271 01272 _dbus_assert (all_odd_values (&list2)); 01273 _dbus_list_clear (&list2); 01274 01275 i = 0; 01276 link1 = _dbus_list_get_first_link (&list1); 01277 while (link1 != NULL) 01278 { 01279 DBusList *next = _dbus_list_get_next_link (&list1, link1); 01280 01281 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01282 01283 if ((i % 2) != 0) 01284 _dbus_list_remove_link (&list1, link1); 01285 01286 verify_list (&list1); 01287 01288 link1 = next; 01289 ++i; 01290 } 01291 01292 _dbus_assert (all_even_values (&list1)); 01293 _dbus_list_clear (&list1); 01294 01295 /* Test copying a list */ 01296 i = 0; 01297 while (i < 10) 01298 { 01299 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01300 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01301 ++i; 01302 } 01303 01304 /* bad pointers, because they are allowed in the copy dest */ 01305 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01306 copy2 = _DBUS_INT_TO_POINTER (23); 01307 01308 _dbus_list_copy (&list1, ©1); 01309 verify_list (&list1); 01310 verify_list (©1); 01311 _dbus_assert (lists_equal (&list1, ©1)); 01312 01313 _dbus_list_copy (&list2, ©2); 01314 verify_list (&list2); 01315 verify_list (©2); 01316 _dbus_assert (lists_equal (&list2, ©2)); 01317 01318 /* Now test copying empty lists */ 01319 _dbus_list_clear (&list1); 01320 _dbus_list_clear (&list2); 01321 _dbus_list_clear (©1); 01322 _dbus_list_clear (©2); 01323 01324 /* bad pointers, because they are allowed in the copy dest */ 01325 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01326 copy2 = _DBUS_INT_TO_POINTER (23); 01327 01328 _dbus_list_copy (&list1, ©1); 01329 verify_list (&list1); 01330 verify_list (©1); 01331 _dbus_assert (lists_equal (&list1, ©1)); 01332 01333 _dbus_list_copy (&list2, ©2); 01334 verify_list (&list2); 01335 verify_list (©2); 01336 _dbus_assert (lists_equal (&list2, ©2)); 01337 01338 _dbus_list_clear (&list1); 01339 _dbus_list_clear (&list2); 01340 01341 /* insert_before on empty list */ 01342 _dbus_list_insert_before (&list1, NULL, 01343 _DBUS_INT_TO_POINTER (0)); 01344 verify_list (&list1); 01345 01346 /* inserting before first element */ 01347 _dbus_list_insert_before (&list1, list1, 01348 _DBUS_INT_TO_POINTER (2)); 01349 verify_list (&list1); 01350 _dbus_assert (is_descending_sequence (&list1)); 01351 01352 /* inserting in the middle */ 01353 _dbus_list_insert_before (&list1, list1->next, 01354 _DBUS_INT_TO_POINTER (1)); 01355 verify_list (&list1); 01356 _dbus_assert (is_descending_sequence (&list1)); 01357 01358 /* using insert_before to append */ 01359 _dbus_list_insert_before (&list1, NULL, 01360 _DBUS_INT_TO_POINTER (-1)); 01361 verify_list (&list1); 01362 _dbus_assert (is_descending_sequence (&list1)); 01363 01364 _dbus_list_clear (&list1); 01365 01366 /* insert_after on empty list */ 01367 _dbus_list_insert_after (&list1, NULL, 01368 _DBUS_INT_TO_POINTER (0)); 01369 verify_list (&list1); 01370 01371 /* inserting after first element */ 01372 _dbus_list_insert_after (&list1, list1, 01373 _DBUS_INT_TO_POINTER (1)); 01374 verify_list (&list1); 01375 _dbus_assert (is_ascending_sequence (&list1)); 01376 01377 /* inserting at the end */ 01378 _dbus_list_insert_after (&list1, list1->next, 01379 _DBUS_INT_TO_POINTER (2)); 01380 verify_list (&list1); 01381 _dbus_assert (is_ascending_sequence (&list1)); 01382 01383 /* using insert_after to prepend */ 01384 _dbus_list_insert_after (&list1, NULL, 01385 _DBUS_INT_TO_POINTER (-1)); 01386 verify_list (&list1); 01387 _dbus_assert (is_ascending_sequence (&list1)); 01388 01389 _dbus_list_clear (&list1); 01390 01391 /* using remove_last */ 01392 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)); 01393 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)); 01394 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)); 01395 01396 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2)); 01397 01398 verify_list (&list1); 01399 _dbus_assert (is_ascending_sequence (&list1)); 01400 01401 _dbus_list_clear (&list1); 01402 01403 return TRUE; 01404 } 01405 01406 #endif