D-Bus
1.10.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 /* Protected by _DBUS_LOCK (list) */ 00039 static DBusMemPool *list_pool; 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 if (!_DBUS_LOCK (list)) 00060 return FALSE; 00061 00062 if (list_pool == NULL) 00063 { 00064 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE); 00065 00066 if (list_pool == NULL) 00067 { 00068 _DBUS_UNLOCK (list); 00069 return NULL; 00070 } 00071 00072 link = _dbus_mem_pool_alloc (list_pool); 00073 if (link == NULL) 00074 { 00075 _dbus_mem_pool_free (list_pool); 00076 list_pool = NULL; 00077 _DBUS_UNLOCK (list); 00078 return NULL; 00079 } 00080 } 00081 else 00082 { 00083 link = _dbus_mem_pool_alloc (list_pool); 00084 } 00085 00086 if (link) 00087 link->data = data; 00088 00089 _DBUS_UNLOCK (list); 00090 00091 return link; 00092 } 00093 00094 static void 00095 free_link (DBusList *link) 00096 { 00097 if (!_DBUS_LOCK (list)) 00098 _dbus_assert_not_reached ("we should have initialized global locks " 00099 "before we allocated a linked-list link"); 00100 00101 if (_dbus_mem_pool_dealloc (list_pool, link)) 00102 { 00103 _dbus_mem_pool_free (list_pool); 00104 list_pool = NULL; 00105 } 00106 00107 _DBUS_UNLOCK (list); 00108 } 00109 00110 static void 00111 link_before (DBusList **list, 00112 DBusList *before_this_link, 00113 DBusList *link) 00114 { 00115 if (*list == NULL) 00116 { 00117 link->prev = link; 00118 link->next = link; 00119 *list = link; 00120 } 00121 else 00122 { 00123 link->next = before_this_link; 00124 link->prev = before_this_link->prev; 00125 before_this_link->prev = link; 00126 link->prev->next = link; 00127 00128 if (before_this_link == *list) 00129 *list = link; 00130 } 00131 } 00132 00133 static void 00134 link_after (DBusList **list, 00135 DBusList *after_this_link, 00136 DBusList *link) 00137 { 00138 if (*list == NULL) 00139 { 00140 link->prev = link; 00141 link->next = link; 00142 *list = link; 00143 } 00144 else 00145 { 00146 link->prev = after_this_link; 00147 link->next = after_this_link->next; 00148 after_this_link->next = link; 00149 link->next->prev = link; 00150 } 00151 } 00152 00153 #ifdef DBUS_ENABLE_STATS 00154 void 00155 _dbus_list_get_stats (dbus_uint32_t *in_use_p, 00156 dbus_uint32_t *in_free_list_p, 00157 dbus_uint32_t *allocated_p) 00158 { 00159 if (!_DBUS_LOCK (list)) 00160 { 00161 *in_use_p = 0; 00162 *in_free_list_p = 0; 00163 *allocated_p = 0; 00164 return; 00165 } 00166 00167 _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p); 00168 _DBUS_UNLOCK (list); 00169 } 00170 #endif 00171 00241 DBusList* 00242 _dbus_list_alloc_link (void *data) 00243 { 00244 return alloc_link (data); 00245 } 00246 00253 void 00254 _dbus_list_free_link (DBusList *link) 00255 { 00256 free_link (link); 00257 } 00258 00259 00269 dbus_bool_t 00270 _dbus_list_append (DBusList **list, 00271 void *data) 00272 { 00273 if (!_dbus_list_prepend (list, data)) 00274 return FALSE; 00275 00276 /* Now cycle the list forward one so the prepended node is the tail */ 00277 *list = (*list)->next; 00278 00279 return TRUE; 00280 } 00281 00291 dbus_bool_t 00292 _dbus_list_prepend (DBusList **list, 00293 void *data) 00294 { 00295 DBusList *link; 00296 00297 link = alloc_link (data); 00298 if (link == NULL) 00299 return FALSE; 00300 00301 link_before (list, *list, link); 00302 00303 return TRUE; 00304 } 00305 00314 void 00315 _dbus_list_append_link (DBusList **list, 00316 DBusList *link) 00317 { 00318 _dbus_list_prepend_link (list, link); 00319 00320 /* Now cycle the list forward one so the prepended node is the tail */ 00321 *list = (*list)->next; 00322 } 00323 00332 void 00333 _dbus_list_prepend_link (DBusList **list, 00334 DBusList *link) 00335 { 00336 link_before (list, *list, link); 00337 } 00338 00347 dbus_bool_t 00348 _dbus_list_insert_after (DBusList **list, 00349 DBusList *after_this_link, 00350 void *data) 00351 { 00352 DBusList *link; 00353 00354 if (after_this_link == NULL) 00355 return _dbus_list_prepend (list, data); 00356 else 00357 { 00358 link = alloc_link (data); 00359 if (link == NULL) 00360 return FALSE; 00361 00362 link_after (list, after_this_link, link); 00363 } 00364 00365 return TRUE; 00366 } 00367 00375 void 00376 _dbus_list_insert_before_link (DBusList **list, 00377 DBusList *before_this_link, 00378 DBusList *link) 00379 { 00380 if (before_this_link == NULL) 00381 _dbus_list_append_link (list, link); 00382 else 00383 link_before (list, before_this_link, link); 00384 } 00385 00393 void 00394 _dbus_list_insert_after_link (DBusList **list, 00395 DBusList *after_this_link, 00396 DBusList *link) 00397 { 00398 if (after_this_link == NULL) 00399 _dbus_list_prepend_link (list, link); 00400 else 00401 link_after (list, after_this_link, link); 00402 } 00403 00414 dbus_bool_t 00415 _dbus_list_remove (DBusList **list, 00416 void *data) 00417 { 00418 DBusList *link; 00419 00420 link = *list; 00421 while (link != NULL) 00422 { 00423 if (link->data == data) 00424 { 00425 _dbus_list_remove_link (list, link); 00426 return TRUE; 00427 } 00428 00429 link = _dbus_list_get_next_link (list, link); 00430 } 00431 00432 return FALSE; 00433 } 00434 00445 dbus_bool_t 00446 _dbus_list_remove_last (DBusList **list, 00447 void *data) 00448 { 00449 DBusList *link; 00450 00451 link = _dbus_list_find_last (list, data); 00452 if (link) 00453 { 00454 _dbus_list_remove_link (list, link); 00455 return TRUE; 00456 } 00457 else 00458 return FALSE; 00459 } 00460 00471 DBusList* 00472 _dbus_list_find_last (DBusList **list, 00473 void *data) 00474 { 00475 DBusList *link; 00476 00477 link = _dbus_list_get_last_link (list); 00478 00479 while (link != NULL) 00480 { 00481 if (link->data == data) 00482 return link; 00483 00484 link = _dbus_list_get_prev_link (list, link); 00485 } 00486 00487 return NULL; 00488 } 00489 00498 void 00499 _dbus_list_unlink (DBusList **list, 00500 DBusList *link) 00501 { 00502 if (link->next == link) 00503 { 00504 /* one-element list */ 00505 *list = NULL; 00506 } 00507 else 00508 { 00509 link->prev->next = link->next; 00510 link->next->prev = link->prev; 00511 00512 if (*list == link) 00513 *list = link->next; 00514 } 00515 00516 link->next = NULL; 00517 link->prev = NULL; 00518 } 00519 00526 void 00527 _dbus_list_remove_link (DBusList **list, 00528 DBusList *link) 00529 { 00530 _dbus_list_unlink (list, link); 00531 free_link (link); 00532 } 00533 00541 void 00542 _dbus_list_clear (DBusList **list) 00543 { 00544 DBusList *link; 00545 00546 link = *list; 00547 while (link != NULL) 00548 { 00549 DBusList *next = _dbus_list_get_next_link (list, link); 00550 00551 free_link (link); 00552 00553 link = next; 00554 } 00555 00556 *list = NULL; 00557 } 00558 00566 DBusList* 00567 _dbus_list_get_first_link (DBusList **list) 00568 { 00569 return *list; 00570 } 00571 00579 DBusList* 00580 _dbus_list_get_last_link (DBusList **list) 00581 { 00582 if (*list == NULL) 00583 return NULL; 00584 else 00585 return (*list)->prev; 00586 } 00587 00595 void* 00596 _dbus_list_get_last (DBusList **list) 00597 { 00598 if (*list == NULL) 00599 return NULL; 00600 else 00601 return (*list)->prev->data; 00602 } 00603 00611 void* 00612 _dbus_list_get_first (DBusList **list) 00613 { 00614 if (*list == NULL) 00615 return NULL; 00616 else 00617 return (*list)->data; 00618 } 00619 00627 DBusList* 00628 _dbus_list_pop_first_link (DBusList **list) 00629 { 00630 DBusList *link; 00631 00632 link = _dbus_list_get_first_link (list); 00633 if (link == NULL) 00634 return NULL; 00635 00636 _dbus_list_unlink (list, link); 00637 00638 return link; 00639 } 00640 00648 void* 00649 _dbus_list_pop_first (DBusList **list) 00650 { 00651 DBusList *link; 00652 void *data; 00653 00654 link = _dbus_list_get_first_link (list); 00655 if (link == NULL) 00656 return NULL; 00657 00658 data = link->data; 00659 _dbus_list_remove_link (list, link); 00660 00661 return data; 00662 } 00663 00671 void* 00672 _dbus_list_pop_last (DBusList **list) 00673 { 00674 DBusList *link; 00675 void *data; 00676 00677 link = _dbus_list_get_last_link (list); 00678 if (link == NULL) 00679 return NULL; 00680 00681 data = link->data; 00682 _dbus_list_remove_link (list, link); 00683 00684 return data; 00685 } 00686 00696 dbus_bool_t 00697 _dbus_list_copy (DBusList **list, 00698 DBusList **dest) 00699 { 00700 DBusList *link; 00701 00702 _dbus_assert (list != dest); 00703 00704 *dest = NULL; 00705 00706 link = *list; 00707 while (link != NULL) 00708 { 00709 if (!_dbus_list_append (dest, link->data)) 00710 { 00711 /* free what we have so far */ 00712 _dbus_list_clear (dest); 00713 return FALSE; 00714 } 00715 00716 link = _dbus_list_get_next_link (list, link); 00717 } 00718 00719 return TRUE; 00720 } 00721 00729 int 00730 _dbus_list_get_length (DBusList **list) 00731 { 00732 DBusList *link; 00733 int length; 00734 00735 length = 0; 00736 00737 link = *list; 00738 while (link != NULL) 00739 { 00740 ++length; 00741 00742 link = _dbus_list_get_next_link (list, link); 00743 } 00744 00745 return length; 00746 } 00747 00758 void 00759 _dbus_list_foreach (DBusList **list, 00760 DBusForeachFunction function, 00761 void *data) 00762 { 00763 DBusList *link; 00764 00765 link = *list; 00766 while (link != NULL) 00767 { 00768 DBusList *next = _dbus_list_get_next_link (list, link); 00769 00770 (* function) (link->data, data); 00771 00772 link = next; 00773 } 00774 } 00775 00782 dbus_bool_t 00783 _dbus_list_length_is_one (DBusList **list) 00784 { 00785 return (*list != NULL && 00786 (*list)->next == *list); 00787 } 00788 00791 #ifdef DBUS_ENABLE_EMBEDDED_TESTS 00792 #include "dbus-test.h" 00793 #include <stdio.h> 00794 00795 static void 00796 verify_list (DBusList **list) 00797 { 00798 DBusList *link; 00799 int length; 00800 00801 link = *list; 00802 00803 if (link == NULL) 00804 return; 00805 00806 if (link->next == link) 00807 { 00808 _dbus_assert (link->prev == link); 00809 _dbus_assert (*list == link); 00810 return; 00811 } 00812 00813 length = 0; 00814 do 00815 { 00816 length += 1; 00817 _dbus_assert (link->prev->next == link); 00818 _dbus_assert (link->next->prev == link); 00819 link = link->next; 00820 } 00821 while (link != *list); 00822 00823 _dbus_assert (length == _dbus_list_get_length (list)); 00824 00825 if (length == 1) 00826 _dbus_assert (_dbus_list_length_is_one (list)); 00827 else 00828 _dbus_assert (!_dbus_list_length_is_one (list)); 00829 } 00830 00831 static dbus_bool_t 00832 is_ascending_sequence (DBusList **list) 00833 { 00834 DBusList *link; 00835 int prev; 00836 00837 prev = _DBUS_INT_MIN; 00838 00839 link = _dbus_list_get_first_link (list); 00840 while (link != NULL) 00841 { 00842 int v = _DBUS_POINTER_TO_INT (link->data); 00843 00844 if (v <= prev) 00845 return FALSE; 00846 00847 prev = v; 00848 00849 link = _dbus_list_get_next_link (list, link); 00850 } 00851 00852 return TRUE; 00853 } 00854 00855 static dbus_bool_t 00856 is_descending_sequence (DBusList **list) 00857 { 00858 DBusList *link; 00859 int prev; 00860 00861 prev = _DBUS_INT_MAX; 00862 00863 link = _dbus_list_get_first_link (list); 00864 while (link != NULL) 00865 { 00866 int v = _DBUS_POINTER_TO_INT (link->data); 00867 00868 if (v >= prev) 00869 return FALSE; 00870 00871 prev = v; 00872 00873 link = _dbus_list_get_next_link (list, link); 00874 } 00875 00876 return TRUE; 00877 } 00878 00879 static dbus_bool_t 00880 all_even_values (DBusList **list) 00881 { 00882 DBusList *link; 00883 00884 link = _dbus_list_get_first_link (list); 00885 while (link != NULL) 00886 { 00887 int v = _DBUS_POINTER_TO_INT (link->data); 00888 00889 if ((v % 2) != 0) 00890 return FALSE; 00891 00892 link = _dbus_list_get_next_link (list, link); 00893 } 00894 00895 return TRUE; 00896 } 00897 00898 static dbus_bool_t 00899 all_odd_values (DBusList **list) 00900 { 00901 DBusList *link; 00902 00903 link = _dbus_list_get_first_link (list); 00904 while (link != NULL) 00905 { 00906 int v = _DBUS_POINTER_TO_INT (link->data); 00907 00908 if ((v % 2) == 0) 00909 return FALSE; 00910 00911 link = _dbus_list_get_next_link (list, link); 00912 } 00913 00914 return TRUE; 00915 } 00916 00917 static dbus_bool_t 00918 lists_equal (DBusList **list1, 00919 DBusList **list2) 00920 { 00921 DBusList *link1; 00922 DBusList *link2; 00923 00924 link1 = _dbus_list_get_first_link (list1); 00925 link2 = _dbus_list_get_first_link (list2); 00926 while (link1 && link2) 00927 { 00928 if (link1->data != link2->data) 00929 return FALSE; 00930 00931 link1 = _dbus_list_get_next_link (list1, link1); 00932 link2 = _dbus_list_get_next_link (list2, link2); 00933 } 00934 00935 if (link1 || link2) 00936 return FALSE; 00937 00938 return TRUE; 00939 } 00940 00946 dbus_bool_t 00947 _dbus_list_test (void) 00948 { 00949 DBusList *list1; 00950 DBusList *list2; 00951 DBusList *link1; 00952 DBusList *link2; 00953 DBusList *copy1; 00954 DBusList *copy2; 00955 int i; 00956 00957 list1 = NULL; 00958 list2 = NULL; 00959 00960 /* Test append and prepend */ 00961 00962 i = 0; 00963 while (i < 10) 00964 { 00965 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i))) 00966 _dbus_assert_not_reached ("could not allocate for append"); 00967 00968 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i))) 00969 _dbus_assert_not_reached ("count not allocate for prepend"); 00970 ++i; 00971 00972 verify_list (&list1); 00973 verify_list (&list2); 00974 00975 _dbus_assert (_dbus_list_get_length (&list1) == i); 00976 _dbus_assert (_dbus_list_get_length (&list2) == i); 00977 } 00978 00979 _dbus_assert (is_ascending_sequence (&list1)); 00980 _dbus_assert (is_descending_sequence (&list2)); 00981 00982 /* Test list clear */ 00983 _dbus_list_clear (&list1); 00984 _dbus_list_clear (&list2); 00985 00986 verify_list (&list1); 00987 verify_list (&list2); 00988 00989 /* Test get_first, get_last, pop_first, pop_last */ 00990 00991 i = 0; 00992 while (i < 10) 00993 { 00994 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 00995 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 00996 ++i; 00997 } 00998 00999 --i; 01000 while (i >= 0) 01001 { 01002 void *got_data1; 01003 void *got_data2; 01004 01005 void *data1; 01006 void *data2; 01007 01008 got_data1 = _dbus_list_get_last (&list1); 01009 got_data2 = _dbus_list_get_first (&list2); 01010 01011 data1 = _dbus_list_pop_last (&list1); 01012 data2 = _dbus_list_pop_first (&list2); 01013 01014 _dbus_assert (got_data1 == data1); 01015 _dbus_assert (got_data2 == data2); 01016 01017 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01018 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01019 01020 verify_list (&list1); 01021 verify_list (&list2); 01022 01023 _dbus_assert (is_ascending_sequence (&list1)); 01024 _dbus_assert (is_descending_sequence (&list2)); 01025 01026 --i; 01027 } 01028 01029 _dbus_assert (list1 == NULL); 01030 _dbus_assert (list2 == NULL); 01031 01032 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */ 01033 01034 i = 0; 01035 while (i < 10) 01036 { 01037 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01038 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01039 ++i; 01040 } 01041 01042 --i; 01043 while (i >= 0) 01044 { 01045 DBusList *got_link1; 01046 DBusList *got_link2; 01047 01048 DBusList *link2; 01049 01050 void *data1_indirect; 01051 void *data1; 01052 void *data2; 01053 01054 got_link1 = _dbus_list_get_last_link (&list1); 01055 got_link2 = _dbus_list_get_first_link (&list2); 01056 01057 link2 = _dbus_list_pop_first_link (&list2); 01058 01059 _dbus_assert (got_link2 == link2); 01060 01061 data1_indirect = got_link1->data; 01062 /* this call makes got_link1 invalid */ 01063 data1 = _dbus_list_pop_last (&list1); 01064 _dbus_assert (data1 == data1_indirect); 01065 data2 = link2->data; 01066 01067 _dbus_list_free_link (link2); 01068 01069 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01070 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01071 01072 verify_list (&list1); 01073 verify_list (&list2); 01074 01075 _dbus_assert (is_ascending_sequence (&list1)); 01076 _dbus_assert (is_descending_sequence (&list2)); 01077 01078 --i; 01079 } 01080 01081 _dbus_assert (list1 == NULL); 01082 _dbus_assert (list2 == NULL); 01083 01084 /* Test iteration */ 01085 01086 i = 0; 01087 while (i < 10) 01088 { 01089 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01090 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01091 ++i; 01092 01093 verify_list (&list1); 01094 verify_list (&list2); 01095 01096 _dbus_assert (_dbus_list_get_length (&list1) == i); 01097 _dbus_assert (_dbus_list_get_length (&list2) == i); 01098 } 01099 01100 _dbus_assert (is_ascending_sequence (&list1)); 01101 _dbus_assert (is_descending_sequence (&list2)); 01102 01103 --i; 01104 link2 = _dbus_list_get_first_link (&list2); 01105 while (link2 != NULL) 01106 { 01107 verify_list (&link2); /* pretend this link is the head */ 01108 01109 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01110 01111 link2 = _dbus_list_get_next_link (&list2, link2); 01112 --i; 01113 } 01114 01115 i = 0; 01116 link1 = _dbus_list_get_first_link (&list1); 01117 while (link1 != NULL) 01118 { 01119 verify_list (&link1); /* pretend this link is the head */ 01120 01121 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01122 01123 link1 = _dbus_list_get_next_link (&list1, link1); 01124 ++i; 01125 } 01126 01127 --i; 01128 link1 = _dbus_list_get_last_link (&list1); 01129 while (link1 != NULL) 01130 { 01131 verify_list (&link1); /* pretend this link is the head */ 01132 01133 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01134 01135 link1 = _dbus_list_get_prev_link (&list1, link1); 01136 --i; 01137 } 01138 01139 _dbus_list_clear (&list1); 01140 _dbus_list_clear (&list2); 01141 01142 /* Test remove */ 01143 01144 i = 0; 01145 while (i < 10) 01146 { 01147 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01148 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01149 ++i; 01150 } 01151 01152 --i; 01153 while (i >= 0) 01154 { 01155 if ((i % 2) == 0) 01156 { 01157 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01158 _dbus_assert_not_reached ("element should have been in list"); 01159 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01160 _dbus_assert_not_reached ("element should have been in list"); 01161 01162 verify_list (&list1); 01163 verify_list (&list2); 01164 } 01165 --i; 01166 } 01167 01168 _dbus_assert (all_odd_values (&list1)); 01169 _dbus_assert (all_odd_values (&list2)); 01170 01171 _dbus_list_clear (&list1); 01172 _dbus_list_clear (&list2); 01173 01174 /* test removing the other half of the elements */ 01175 01176 i = 0; 01177 while (i < 10) 01178 { 01179 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01180 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01181 ++i; 01182 } 01183 01184 --i; 01185 while (i >= 0) 01186 { 01187 if ((i % 2) != 0) 01188 { 01189 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01190 _dbus_assert_not_reached ("element should have been in list"); 01191 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01192 _dbus_assert_not_reached ("element should have been in list"); 01193 01194 verify_list (&list1); 01195 verify_list (&list2); 01196 } 01197 --i; 01198 } 01199 01200 _dbus_assert (all_even_values (&list1)); 01201 _dbus_assert (all_even_values (&list2)); 01202 01203 /* clear list using remove_link */ 01204 while (list1 != NULL) 01205 { 01206 _dbus_list_remove_link (&list1, list1); 01207 verify_list (&list1); 01208 } 01209 while (list2 != NULL) 01210 { 01211 _dbus_list_remove_link (&list2, list2); 01212 verify_list (&list2); 01213 } 01214 01215 /* Test remove link more generally */ 01216 i = 0; 01217 while (i < 10) 01218 { 01219 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01220 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01221 ++i; 01222 } 01223 01224 --i; 01225 link2 = _dbus_list_get_first_link (&list2); 01226 while (link2 != NULL) 01227 { 01228 DBusList *next = _dbus_list_get_next_link (&list2, link2); 01229 01230 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01231 01232 if ((i % 2) == 0) 01233 _dbus_list_remove_link (&list2, link2); 01234 01235 verify_list (&list2); 01236 01237 link2 = next; 01238 --i; 01239 } 01240 01241 _dbus_assert (all_odd_values (&list2)); 01242 _dbus_list_clear (&list2); 01243 01244 i = 0; 01245 link1 = _dbus_list_get_first_link (&list1); 01246 while (link1 != NULL) 01247 { 01248 DBusList *next = _dbus_list_get_next_link (&list1, link1); 01249 01250 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01251 01252 if ((i % 2) != 0) 01253 _dbus_list_remove_link (&list1, link1); 01254 01255 verify_list (&list1); 01256 01257 link1 = next; 01258 ++i; 01259 } 01260 01261 _dbus_assert (all_even_values (&list1)); 01262 _dbus_list_clear (&list1); 01263 01264 /* Test copying a list */ 01265 i = 0; 01266 while (i < 10) 01267 { 01268 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01269 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01270 ++i; 01271 } 01272 01273 /* bad pointers, because they are allowed in the copy dest */ 01274 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01275 copy2 = _DBUS_INT_TO_POINTER (23); 01276 01277 _dbus_list_copy (&list1, ©1); 01278 verify_list (&list1); 01279 verify_list (©1); 01280 _dbus_assert (lists_equal (&list1, ©1)); 01281 01282 _dbus_list_copy (&list2, ©2); 01283 verify_list (&list2); 01284 verify_list (©2); 01285 _dbus_assert (lists_equal (&list2, ©2)); 01286 01287 /* Now test copying empty lists */ 01288 _dbus_list_clear (&list1); 01289 _dbus_list_clear (&list2); 01290 _dbus_list_clear (©1); 01291 _dbus_list_clear (©2); 01292 01293 /* bad pointers, because they are allowed in the copy dest */ 01294 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01295 copy2 = _DBUS_INT_TO_POINTER (23); 01296 01297 _dbus_list_copy (&list1, ©1); 01298 verify_list (&list1); 01299 verify_list (©1); 01300 _dbus_assert (lists_equal (&list1, ©1)); 01301 01302 _dbus_list_copy (&list2, ©2); 01303 verify_list (&list2); 01304 verify_list (©2); 01305 _dbus_assert (lists_equal (&list2, ©2)); 01306 01307 _dbus_list_clear (&list1); 01308 _dbus_list_clear (&list2); 01309 01310 /* insert_after on empty list */ 01311 _dbus_list_insert_after (&list1, NULL, 01312 _DBUS_INT_TO_POINTER (0)); 01313 verify_list (&list1); 01314 01315 /* inserting after first element */ 01316 _dbus_list_insert_after (&list1, list1, 01317 _DBUS_INT_TO_POINTER (1)); 01318 verify_list (&list1); 01319 _dbus_assert (is_ascending_sequence (&list1)); 01320 01321 /* inserting at the end */ 01322 _dbus_list_insert_after (&list1, list1->next, 01323 _DBUS_INT_TO_POINTER (2)); 01324 verify_list (&list1); 01325 _dbus_assert (is_ascending_sequence (&list1)); 01326 01327 /* using insert_after to prepend */ 01328 _dbus_list_insert_after (&list1, NULL, 01329 _DBUS_INT_TO_POINTER (-1)); 01330 verify_list (&list1); 01331 _dbus_assert (is_ascending_sequence (&list1)); 01332 01333 _dbus_list_clear (&list1); 01334 01335 /* using remove_last */ 01336 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)); 01337 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)); 01338 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)); 01339 01340 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2)); 01341 01342 verify_list (&list1); 01343 _dbus_assert (is_ascending_sequence (&list1)); 01344 01345 _dbus_list_clear (&list1); 01346 01347 return TRUE; 01348 } 01349 01350 #endif