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