D-Bus 1.6.12
|
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 00149 #ifdef DBUS_ENABLE_STATS 00150 void 00151 _dbus_list_get_stats (dbus_uint32_t *in_use_p, 00152 dbus_uint32_t *in_free_list_p, 00153 dbus_uint32_t *allocated_p) 00154 { 00155 _DBUS_LOCK (list); 00156 _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p); 00157 _DBUS_UNLOCK (list); 00158 } 00159 #endif 00160 00230 DBusList* 00231 _dbus_list_alloc_link (void *data) 00232 { 00233 return alloc_link (data); 00234 } 00235 00242 void 00243 _dbus_list_free_link (DBusList *link) 00244 { 00245 free_link (link); 00246 } 00247 00248 00258 dbus_bool_t 00259 _dbus_list_append (DBusList **list, 00260 void *data) 00261 { 00262 if (!_dbus_list_prepend (list, data)) 00263 return FALSE; 00264 00265 /* Now cycle the list forward one so the prepended node is the tail */ 00266 *list = (*list)->next; 00267 00268 return TRUE; 00269 } 00270 00280 dbus_bool_t 00281 _dbus_list_prepend (DBusList **list, 00282 void *data) 00283 { 00284 DBusList *link; 00285 00286 link = alloc_link (data); 00287 if (link == NULL) 00288 return FALSE; 00289 00290 link_before (list, *list, link); 00291 00292 return TRUE; 00293 } 00294 00303 void 00304 _dbus_list_append_link (DBusList **list, 00305 DBusList *link) 00306 { 00307 _dbus_list_prepend_link (list, link); 00308 00309 /* Now cycle the list forward one so the prepended node is the tail */ 00310 *list = (*list)->next; 00311 } 00312 00321 void 00322 _dbus_list_prepend_link (DBusList **list, 00323 DBusList *link) 00324 { 00325 link_before (list, *list, link); 00326 } 00327 00336 dbus_bool_t 00337 _dbus_list_insert_after (DBusList **list, 00338 DBusList *after_this_link, 00339 void *data) 00340 { 00341 DBusList *link; 00342 00343 if (after_this_link == NULL) 00344 return _dbus_list_prepend (list, data); 00345 else 00346 { 00347 link = alloc_link (data); 00348 if (link == NULL) 00349 return FALSE; 00350 00351 link_after (list, after_this_link, link); 00352 } 00353 00354 return TRUE; 00355 } 00356 00364 void 00365 _dbus_list_insert_before_link (DBusList **list, 00366 DBusList *before_this_link, 00367 DBusList *link) 00368 { 00369 if (before_this_link == NULL) 00370 _dbus_list_append_link (list, link); 00371 else 00372 link_before (list, before_this_link, link); 00373 } 00374 00382 void 00383 _dbus_list_insert_after_link (DBusList **list, 00384 DBusList *after_this_link, 00385 DBusList *link) 00386 { 00387 if (after_this_link == NULL) 00388 _dbus_list_prepend_link (list, link); 00389 else 00390 link_after (list, after_this_link, link); 00391 } 00392 00403 dbus_bool_t 00404 _dbus_list_remove (DBusList **list, 00405 void *data) 00406 { 00407 DBusList *link; 00408 00409 link = *list; 00410 while (link != NULL) 00411 { 00412 if (link->data == data) 00413 { 00414 _dbus_list_remove_link (list, link); 00415 return TRUE; 00416 } 00417 00418 link = _dbus_list_get_next_link (list, link); 00419 } 00420 00421 return FALSE; 00422 } 00423 00434 dbus_bool_t 00435 _dbus_list_remove_last (DBusList **list, 00436 void *data) 00437 { 00438 DBusList *link; 00439 00440 link = _dbus_list_find_last (list, data); 00441 if (link) 00442 { 00443 _dbus_list_remove_link (list, link); 00444 return TRUE; 00445 } 00446 else 00447 return FALSE; 00448 } 00449 00460 DBusList* 00461 _dbus_list_find_last (DBusList **list, 00462 void *data) 00463 { 00464 DBusList *link; 00465 00466 link = _dbus_list_get_last_link (list); 00467 00468 while (link != NULL) 00469 { 00470 if (link->data == data) 00471 return link; 00472 00473 link = _dbus_list_get_prev_link (list, link); 00474 } 00475 00476 return NULL; 00477 } 00478 00487 void 00488 _dbus_list_unlink (DBusList **list, 00489 DBusList *link) 00490 { 00491 if (link->next == link) 00492 { 00493 /* one-element list */ 00494 *list = NULL; 00495 } 00496 else 00497 { 00498 link->prev->next = link->next; 00499 link->next->prev = link->prev; 00500 00501 if (*list == link) 00502 *list = link->next; 00503 } 00504 00505 link->next = NULL; 00506 link->prev = NULL; 00507 } 00508 00515 void 00516 _dbus_list_remove_link (DBusList **list, 00517 DBusList *link) 00518 { 00519 _dbus_list_unlink (list, link); 00520 free_link (link); 00521 } 00522 00530 void 00531 _dbus_list_clear (DBusList **list) 00532 { 00533 DBusList *link; 00534 00535 link = *list; 00536 while (link != NULL) 00537 { 00538 DBusList *next = _dbus_list_get_next_link (list, link); 00539 00540 free_link (link); 00541 00542 link = next; 00543 } 00544 00545 *list = NULL; 00546 } 00547 00555 DBusList* 00556 _dbus_list_get_first_link (DBusList **list) 00557 { 00558 return *list; 00559 } 00560 00568 DBusList* 00569 _dbus_list_get_last_link (DBusList **list) 00570 { 00571 if (*list == NULL) 00572 return NULL; 00573 else 00574 return (*list)->prev; 00575 } 00576 00584 void* 00585 _dbus_list_get_last (DBusList **list) 00586 { 00587 if (*list == NULL) 00588 return NULL; 00589 else 00590 return (*list)->prev->data; 00591 } 00592 00600 void* 00601 _dbus_list_get_first (DBusList **list) 00602 { 00603 if (*list == NULL) 00604 return NULL; 00605 else 00606 return (*list)->data; 00607 } 00608 00616 DBusList* 00617 _dbus_list_pop_first_link (DBusList **list) 00618 { 00619 DBusList *link; 00620 00621 link = _dbus_list_get_first_link (list); 00622 if (link == NULL) 00623 return NULL; 00624 00625 _dbus_list_unlink (list, link); 00626 00627 return link; 00628 } 00629 00637 void* 00638 _dbus_list_pop_first (DBusList **list) 00639 { 00640 DBusList *link; 00641 void *data; 00642 00643 link = _dbus_list_get_first_link (list); 00644 if (link == NULL) 00645 return NULL; 00646 00647 data = link->data; 00648 _dbus_list_remove_link (list, link); 00649 00650 return data; 00651 } 00652 00660 void* 00661 _dbus_list_pop_last (DBusList **list) 00662 { 00663 DBusList *link; 00664 void *data; 00665 00666 link = _dbus_list_get_last_link (list); 00667 if (link == NULL) 00668 return NULL; 00669 00670 data = link->data; 00671 _dbus_list_remove_link (list, link); 00672 00673 return data; 00674 } 00675 00685 dbus_bool_t 00686 _dbus_list_copy (DBusList **list, 00687 DBusList **dest) 00688 { 00689 DBusList *link; 00690 00691 _dbus_assert (list != dest); 00692 00693 *dest = NULL; 00694 00695 link = *list; 00696 while (link != NULL) 00697 { 00698 if (!_dbus_list_append (dest, link->data)) 00699 { 00700 /* free what we have so far */ 00701 _dbus_list_clear (dest); 00702 return FALSE; 00703 } 00704 00705 link = _dbus_list_get_next_link (list, link); 00706 } 00707 00708 return TRUE; 00709 } 00710 00718 int 00719 _dbus_list_get_length (DBusList **list) 00720 { 00721 DBusList *link; 00722 int length; 00723 00724 length = 0; 00725 00726 link = *list; 00727 while (link != NULL) 00728 { 00729 ++length; 00730 00731 link = _dbus_list_get_next_link (list, link); 00732 } 00733 00734 return length; 00735 } 00736 00747 void 00748 _dbus_list_foreach (DBusList **list, 00749 DBusForeachFunction function, 00750 void *data) 00751 { 00752 DBusList *link; 00753 00754 link = *list; 00755 while (link != NULL) 00756 { 00757 DBusList *next = _dbus_list_get_next_link (list, link); 00758 00759 (* function) (link->data, data); 00760 00761 link = next; 00762 } 00763 } 00764 00771 dbus_bool_t 00772 _dbus_list_length_is_one (DBusList **list) 00773 { 00774 return (*list != NULL && 00775 (*list)->next == *list); 00776 } 00777 00780 #ifdef DBUS_BUILD_TESTS 00781 #include "dbus-test.h" 00782 #include <stdio.h> 00783 00784 static void 00785 verify_list (DBusList **list) 00786 { 00787 DBusList *link; 00788 int length; 00789 00790 link = *list; 00791 00792 if (link == NULL) 00793 return; 00794 00795 if (link->next == link) 00796 { 00797 _dbus_assert (link->prev == link); 00798 _dbus_assert (*list == link); 00799 return; 00800 } 00801 00802 length = 0; 00803 do 00804 { 00805 length += 1; 00806 _dbus_assert (link->prev->next == link); 00807 _dbus_assert (link->next->prev == link); 00808 link = link->next; 00809 } 00810 while (link != *list); 00811 00812 _dbus_assert (length == _dbus_list_get_length (list)); 00813 00814 if (length == 1) 00815 _dbus_assert (_dbus_list_length_is_one (list)); 00816 else 00817 _dbus_assert (!_dbus_list_length_is_one (list)); 00818 } 00819 00820 static dbus_bool_t 00821 is_ascending_sequence (DBusList **list) 00822 { 00823 DBusList *link; 00824 int prev; 00825 00826 prev = _DBUS_INT_MIN; 00827 00828 link = _dbus_list_get_first_link (list); 00829 while (link != NULL) 00830 { 00831 int v = _DBUS_POINTER_TO_INT (link->data); 00832 00833 if (v <= prev) 00834 return FALSE; 00835 00836 prev = v; 00837 00838 link = _dbus_list_get_next_link (list, link); 00839 } 00840 00841 return TRUE; 00842 } 00843 00844 static dbus_bool_t 00845 is_descending_sequence (DBusList **list) 00846 { 00847 DBusList *link; 00848 int prev; 00849 00850 prev = _DBUS_INT_MAX; 00851 00852 link = _dbus_list_get_first_link (list); 00853 while (link != NULL) 00854 { 00855 int v = _DBUS_POINTER_TO_INT (link->data); 00856 00857 if (v >= prev) 00858 return FALSE; 00859 00860 prev = v; 00861 00862 link = _dbus_list_get_next_link (list, link); 00863 } 00864 00865 return TRUE; 00866 } 00867 00868 static dbus_bool_t 00869 all_even_values (DBusList **list) 00870 { 00871 DBusList *link; 00872 00873 link = _dbus_list_get_first_link (list); 00874 while (link != NULL) 00875 { 00876 int v = _DBUS_POINTER_TO_INT (link->data); 00877 00878 if ((v % 2) != 0) 00879 return FALSE; 00880 00881 link = _dbus_list_get_next_link (list, link); 00882 } 00883 00884 return TRUE; 00885 } 00886 00887 static dbus_bool_t 00888 all_odd_values (DBusList **list) 00889 { 00890 DBusList *link; 00891 00892 link = _dbus_list_get_first_link (list); 00893 while (link != NULL) 00894 { 00895 int v = _DBUS_POINTER_TO_INT (link->data); 00896 00897 if ((v % 2) == 0) 00898 return FALSE; 00899 00900 link = _dbus_list_get_next_link (list, link); 00901 } 00902 00903 return TRUE; 00904 } 00905 00906 static dbus_bool_t 00907 lists_equal (DBusList **list1, 00908 DBusList **list2) 00909 { 00910 DBusList *link1; 00911 DBusList *link2; 00912 00913 link1 = _dbus_list_get_first_link (list1); 00914 link2 = _dbus_list_get_first_link (list2); 00915 while (link1 && link2) 00916 { 00917 if (link1->data != link2->data) 00918 return FALSE; 00919 00920 link1 = _dbus_list_get_next_link (list1, link1); 00921 link2 = _dbus_list_get_next_link (list2, link2); 00922 } 00923 00924 if (link1 || link2) 00925 return FALSE; 00926 00927 return TRUE; 00928 } 00929 00935 dbus_bool_t 00936 _dbus_list_test (void) 00937 { 00938 DBusList *list1; 00939 DBusList *list2; 00940 DBusList *link1; 00941 DBusList *link2; 00942 DBusList *copy1; 00943 DBusList *copy2; 00944 int i; 00945 00946 list1 = NULL; 00947 list2 = NULL; 00948 00949 /* Test append and prepend */ 00950 00951 i = 0; 00952 while (i < 10) 00953 { 00954 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i))) 00955 _dbus_assert_not_reached ("could not allocate for append"); 00956 00957 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i))) 00958 _dbus_assert_not_reached ("count not allocate for prepend"); 00959 ++i; 00960 00961 verify_list (&list1); 00962 verify_list (&list2); 00963 00964 _dbus_assert (_dbus_list_get_length (&list1) == i); 00965 _dbus_assert (_dbus_list_get_length (&list2) == i); 00966 } 00967 00968 _dbus_assert (is_ascending_sequence (&list1)); 00969 _dbus_assert (is_descending_sequence (&list2)); 00970 00971 /* Test list clear */ 00972 _dbus_list_clear (&list1); 00973 _dbus_list_clear (&list2); 00974 00975 verify_list (&list1); 00976 verify_list (&list2); 00977 00978 /* Test get_first, get_last, pop_first, pop_last */ 00979 00980 i = 0; 00981 while (i < 10) 00982 { 00983 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 00984 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 00985 ++i; 00986 } 00987 00988 --i; 00989 while (i >= 0) 00990 { 00991 void *got_data1; 00992 void *got_data2; 00993 00994 void *data1; 00995 void *data2; 00996 00997 got_data1 = _dbus_list_get_last (&list1); 00998 got_data2 = _dbus_list_get_first (&list2); 00999 01000 data1 = _dbus_list_pop_last (&list1); 01001 data2 = _dbus_list_pop_first (&list2); 01002 01003 _dbus_assert (got_data1 == data1); 01004 _dbus_assert (got_data2 == data2); 01005 01006 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01007 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01008 01009 verify_list (&list1); 01010 verify_list (&list2); 01011 01012 _dbus_assert (is_ascending_sequence (&list1)); 01013 _dbus_assert (is_descending_sequence (&list2)); 01014 01015 --i; 01016 } 01017 01018 _dbus_assert (list1 == NULL); 01019 _dbus_assert (list2 == NULL); 01020 01021 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */ 01022 01023 i = 0; 01024 while (i < 10) 01025 { 01026 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01027 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01028 ++i; 01029 } 01030 01031 --i; 01032 while (i >= 0) 01033 { 01034 DBusList *got_link1; 01035 DBusList *got_link2; 01036 01037 DBusList *link2; 01038 01039 void *data1_indirect; 01040 void *data1; 01041 void *data2; 01042 01043 got_link1 = _dbus_list_get_last_link (&list1); 01044 got_link2 = _dbus_list_get_first_link (&list2); 01045 01046 link2 = _dbus_list_pop_first_link (&list2); 01047 01048 _dbus_assert (got_link2 == link2); 01049 01050 data1_indirect = got_link1->data; 01051 /* this call makes got_link1 invalid */ 01052 data1 = _dbus_list_pop_last (&list1); 01053 _dbus_assert (data1 == data1_indirect); 01054 data2 = link2->data; 01055 01056 _dbus_list_free_link (link2); 01057 01058 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01059 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01060 01061 verify_list (&list1); 01062 verify_list (&list2); 01063 01064 _dbus_assert (is_ascending_sequence (&list1)); 01065 _dbus_assert (is_descending_sequence (&list2)); 01066 01067 --i; 01068 } 01069 01070 _dbus_assert (list1 == NULL); 01071 _dbus_assert (list2 == NULL); 01072 01073 /* Test iteration */ 01074 01075 i = 0; 01076 while (i < 10) 01077 { 01078 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01079 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01080 ++i; 01081 01082 verify_list (&list1); 01083 verify_list (&list2); 01084 01085 _dbus_assert (_dbus_list_get_length (&list1) == i); 01086 _dbus_assert (_dbus_list_get_length (&list2) == i); 01087 } 01088 01089 _dbus_assert (is_ascending_sequence (&list1)); 01090 _dbus_assert (is_descending_sequence (&list2)); 01091 01092 --i; 01093 link2 = _dbus_list_get_first_link (&list2); 01094 while (link2 != NULL) 01095 { 01096 verify_list (&link2); /* pretend this link is the head */ 01097 01098 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01099 01100 link2 = _dbus_list_get_next_link (&list2, link2); 01101 --i; 01102 } 01103 01104 i = 0; 01105 link1 = _dbus_list_get_first_link (&list1); 01106 while (link1 != NULL) 01107 { 01108 verify_list (&link1); /* pretend this link is the head */ 01109 01110 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01111 01112 link1 = _dbus_list_get_next_link (&list1, link1); 01113 ++i; 01114 } 01115 01116 --i; 01117 link1 = _dbus_list_get_last_link (&list1); 01118 while (link1 != NULL) 01119 { 01120 verify_list (&link1); /* pretend this link is the head */ 01121 01122 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01123 01124 link1 = _dbus_list_get_prev_link (&list1, link1); 01125 --i; 01126 } 01127 01128 _dbus_list_clear (&list1); 01129 _dbus_list_clear (&list2); 01130 01131 /* Test remove */ 01132 01133 i = 0; 01134 while (i < 10) 01135 { 01136 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01137 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01138 ++i; 01139 } 01140 01141 --i; 01142 while (i >= 0) 01143 { 01144 if ((i % 2) == 0) 01145 { 01146 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01147 _dbus_assert_not_reached ("element should have been in list"); 01148 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01149 _dbus_assert_not_reached ("element should have been in list"); 01150 01151 verify_list (&list1); 01152 verify_list (&list2); 01153 } 01154 --i; 01155 } 01156 01157 _dbus_assert (all_odd_values (&list1)); 01158 _dbus_assert (all_odd_values (&list2)); 01159 01160 _dbus_list_clear (&list1); 01161 _dbus_list_clear (&list2); 01162 01163 /* test removing the other half of the elements */ 01164 01165 i = 0; 01166 while (i < 10) 01167 { 01168 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01169 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01170 ++i; 01171 } 01172 01173 --i; 01174 while (i >= 0) 01175 { 01176 if ((i % 2) != 0) 01177 { 01178 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01179 _dbus_assert_not_reached ("element should have been in list"); 01180 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01181 _dbus_assert_not_reached ("element should have been in list"); 01182 01183 verify_list (&list1); 01184 verify_list (&list2); 01185 } 01186 --i; 01187 } 01188 01189 _dbus_assert (all_even_values (&list1)); 01190 _dbus_assert (all_even_values (&list2)); 01191 01192 /* clear list using remove_link */ 01193 while (list1 != NULL) 01194 { 01195 _dbus_list_remove_link (&list1, list1); 01196 verify_list (&list1); 01197 } 01198 while (list2 != NULL) 01199 { 01200 _dbus_list_remove_link (&list2, list2); 01201 verify_list (&list2); 01202 } 01203 01204 /* Test remove link more generally */ 01205 i = 0; 01206 while (i < 10) 01207 { 01208 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01209 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01210 ++i; 01211 } 01212 01213 --i; 01214 link2 = _dbus_list_get_first_link (&list2); 01215 while (link2 != NULL) 01216 { 01217 DBusList *next = _dbus_list_get_next_link (&list2, link2); 01218 01219 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01220 01221 if ((i % 2) == 0) 01222 _dbus_list_remove_link (&list2, link2); 01223 01224 verify_list (&list2); 01225 01226 link2 = next; 01227 --i; 01228 } 01229 01230 _dbus_assert (all_odd_values (&list2)); 01231 _dbus_list_clear (&list2); 01232 01233 i = 0; 01234 link1 = _dbus_list_get_first_link (&list1); 01235 while (link1 != NULL) 01236 { 01237 DBusList *next = _dbus_list_get_next_link (&list1, link1); 01238 01239 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01240 01241 if ((i % 2) != 0) 01242 _dbus_list_remove_link (&list1, link1); 01243 01244 verify_list (&list1); 01245 01246 link1 = next; 01247 ++i; 01248 } 01249 01250 _dbus_assert (all_even_values (&list1)); 01251 _dbus_list_clear (&list1); 01252 01253 /* Test copying a list */ 01254 i = 0; 01255 while (i < 10) 01256 { 01257 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01258 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01259 ++i; 01260 } 01261 01262 /* bad pointers, because they are allowed in the copy dest */ 01263 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01264 copy2 = _DBUS_INT_TO_POINTER (23); 01265 01266 _dbus_list_copy (&list1, ©1); 01267 verify_list (&list1); 01268 verify_list (©1); 01269 _dbus_assert (lists_equal (&list1, ©1)); 01270 01271 _dbus_list_copy (&list2, ©2); 01272 verify_list (&list2); 01273 verify_list (©2); 01274 _dbus_assert (lists_equal (&list2, ©2)); 01275 01276 /* Now test copying empty lists */ 01277 _dbus_list_clear (&list1); 01278 _dbus_list_clear (&list2); 01279 _dbus_list_clear (©1); 01280 _dbus_list_clear (©2); 01281 01282 /* bad pointers, because they are allowed in the copy dest */ 01283 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01284 copy2 = _DBUS_INT_TO_POINTER (23); 01285 01286 _dbus_list_copy (&list1, ©1); 01287 verify_list (&list1); 01288 verify_list (©1); 01289 _dbus_assert (lists_equal (&list1, ©1)); 01290 01291 _dbus_list_copy (&list2, ©2); 01292 verify_list (&list2); 01293 verify_list (©2); 01294 _dbus_assert (lists_equal (&list2, ©2)); 01295 01296 _dbus_list_clear (&list1); 01297 _dbus_list_clear (&list2); 01298 01299 /* insert_after on empty list */ 01300 _dbus_list_insert_after (&list1, NULL, 01301 _DBUS_INT_TO_POINTER (0)); 01302 verify_list (&list1); 01303 01304 /* inserting after first element */ 01305 _dbus_list_insert_after (&list1, list1, 01306 _DBUS_INT_TO_POINTER (1)); 01307 verify_list (&list1); 01308 _dbus_assert (is_ascending_sequence (&list1)); 01309 01310 /* inserting at the end */ 01311 _dbus_list_insert_after (&list1, list1->next, 01312 _DBUS_INT_TO_POINTER (2)); 01313 verify_list (&list1); 01314 _dbus_assert (is_ascending_sequence (&list1)); 01315 01316 /* using insert_after to prepend */ 01317 _dbus_list_insert_after (&list1, NULL, 01318 _DBUS_INT_TO_POINTER (-1)); 01319 verify_list (&list1); 01320 _dbus_assert (is_ascending_sequence (&list1)); 01321 01322 _dbus_list_clear (&list1); 01323 01324 /* using remove_last */ 01325 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)); 01326 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)); 01327 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)); 01328 01329 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2)); 01330 01331 verify_list (&list1); 01332 _dbus_assert (is_ascending_sequence (&list1)); 01333 01334 _dbus_list_clear (&list1); 01335 01336 return TRUE; 01337 } 01338 01339 #endif