Main Page | Modules | Data Structures | File List | Data Fields | Related Pages

dbus-list.c

00001 /* -*- mode: C; c-file-style: "gnu" -*- */ 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00021 * 00022 */ 00023 00024 #include "dbus-internals.h" 00025 #include "dbus-list.h" 00026 #include "dbus-mempool.h" 00027 #include "dbus-threads.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 if (!_DBUS_LOCK (list)) 00059 return NULL; 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 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 00353 dbus_bool_t 00354 _dbus_list_insert_after (DBusList **list, 00355 DBusList *after_this_link, 00356 void *data) 00357 { 00358 DBusList *link; 00359 00360 if (after_this_link == NULL) 00361 return _dbus_list_prepend (list, data); 00362 else 00363 { 00364 link = alloc_link (data); 00365 if (link == NULL) 00366 return FALSE; 00367 00368 link_after (list, after_this_link, link); 00369 } 00370 00371 return TRUE; 00372 } 00373 00381 void 00382 _dbus_list_insert_before_link (DBusList **list, 00383 DBusList *before_this_link, 00384 DBusList *link) 00385 { 00386 if (before_this_link == NULL) 00387 _dbus_list_append_link (list, link); 00388 else 00389 link_before (list, before_this_link, link); 00390 } 00391 00399 void 00400 _dbus_list_insert_after_link (DBusList **list, 00401 DBusList *after_this_link, 00402 DBusList *link) 00403 { 00404 if (after_this_link == NULL) 00405 _dbus_list_prepend_link (list, link); 00406 else 00407 link_after (list, after_this_link, link); 00408 } 00409 00420 dbus_bool_t 00421 _dbus_list_remove (DBusList **list, 00422 void *data) 00423 { 00424 DBusList *link; 00425 00426 link = *list; 00427 while (link != NULL) 00428 { 00429 if (link->data == data) 00430 { 00431 _dbus_list_remove_link (list, link); 00432 return TRUE; 00433 } 00434 00435 link = _dbus_list_get_next_link (list, link); 00436 } 00437 00438 return FALSE; 00439 } 00440 00451 dbus_bool_t 00452 _dbus_list_remove_last (DBusList **list, 00453 void *data) 00454 { 00455 DBusList *link; 00456 00457 link = _dbus_list_find_last (list, data); 00458 if (link) 00459 { 00460 _dbus_list_remove_link (list, link); 00461 return TRUE; 00462 } 00463 else 00464 return FALSE; 00465 } 00466 00477 DBusList* 00478 _dbus_list_find_last (DBusList **list, 00479 void *data) 00480 { 00481 DBusList *link; 00482 00483 link = _dbus_list_get_last_link (list); 00484 00485 while (link != NULL) 00486 { 00487 if (link->data == data) 00488 return link; 00489 00490 link = _dbus_list_get_prev_link (list, link); 00491 } 00492 00493 return NULL; 00494 } 00495 00504 void 00505 _dbus_list_unlink (DBusList **list, 00506 DBusList *link) 00507 { 00508 if (link->next == link) 00509 { 00510 /* one-element list */ 00511 *list = NULL; 00512 } 00513 else 00514 { 00515 link->prev->next = link->next; 00516 link->next->prev = link->prev; 00517 00518 if (*list == link) 00519 *list = link->next; 00520 } 00521 00522 link->next = NULL; 00523 link->prev = NULL; 00524 } 00525 00532 void 00533 _dbus_list_remove_link (DBusList **list, 00534 DBusList *link) 00535 { 00536 _dbus_list_unlink (list, link); 00537 free_link (link); 00538 } 00539 00547 void 00548 _dbus_list_clear (DBusList **list) 00549 { 00550 DBusList *link; 00551 00552 link = *list; 00553 while (link != NULL) 00554 { 00555 DBusList *next = _dbus_list_get_next_link (list, link); 00556 00557 free_link (link); 00558 00559 link = next; 00560 } 00561 00562 *list = NULL; 00563 } 00564 00572 DBusList* 00573 _dbus_list_get_first_link (DBusList **list) 00574 { 00575 return *list; 00576 } 00577 00585 DBusList* 00586 _dbus_list_get_last_link (DBusList **list) 00587 { 00588 if (*list == NULL) 00589 return NULL; 00590 else 00591 return (*list)->prev; 00592 } 00593 00601 void* 00602 _dbus_list_get_last (DBusList **list) 00603 { 00604 if (*list == NULL) 00605 return NULL; 00606 else 00607 return (*list)->prev->data; 00608 } 00609 00617 void* 00618 _dbus_list_get_first (DBusList **list) 00619 { 00620 if (*list == NULL) 00621 return NULL; 00622 else 00623 return (*list)->data; 00624 } 00625 00633 DBusList* 00634 _dbus_list_pop_first_link (DBusList **list) 00635 { 00636 DBusList *link; 00637 00638 link = _dbus_list_get_first_link (list); 00639 if (link == NULL) 00640 return NULL; 00641 00642 _dbus_list_unlink (list, link); 00643 00644 return link; 00645 } 00646 00654 void* 00655 _dbus_list_pop_first (DBusList **list) 00656 { 00657 DBusList *link; 00658 void *data; 00659 00660 link = _dbus_list_get_first_link (list); 00661 if (link == NULL) 00662 return NULL; 00663 00664 data = link->data; 00665 _dbus_list_remove_link (list, link); 00666 00667 return data; 00668 } 00669 00677 void* 00678 _dbus_list_pop_last (DBusList **list) 00679 { 00680 DBusList *link; 00681 void *data; 00682 00683 link = _dbus_list_get_last_link (list); 00684 if (link == NULL) 00685 return NULL; 00686 00687 data = link->data; 00688 _dbus_list_remove_link (list, link); 00689 00690 return data; 00691 } 00692 00700 DBusList* 00701 _dbus_list_pop_last_link (DBusList **list) 00702 { 00703 DBusList *link; 00704 00705 link = _dbus_list_get_last_link (list); 00706 if (link == NULL) 00707 return NULL; 00708 00709 _dbus_list_unlink (list, link); 00710 00711 return link; 00712 } 00713 00723 dbus_bool_t 00724 _dbus_list_copy (DBusList **list, 00725 DBusList **dest) 00726 { 00727 DBusList *link; 00728 00729 _dbus_assert (list != dest); 00730 00731 *dest = NULL; 00732 00733 link = *list; 00734 while (link != NULL) 00735 { 00736 if (!_dbus_list_append (dest, link->data)) 00737 { 00738 /* free what we have so far */ 00739 _dbus_list_clear (dest); 00740 return FALSE; 00741 } 00742 00743 link = _dbus_list_get_next_link (list, link); 00744 } 00745 00746 return TRUE; 00747 } 00748 00756 int 00757 _dbus_list_get_length (DBusList **list) 00758 { 00759 DBusList *link; 00760 int length; 00761 00762 length = 0; 00763 00764 link = *list; 00765 while (link != NULL) 00766 { 00767 ++length; 00768 00769 link = _dbus_list_get_next_link (list, link); 00770 } 00771 00772 return length; 00773 } 00774 00785 void 00786 _dbus_list_foreach (DBusList **list, 00787 DBusForeachFunction function, 00788 void *data) 00789 { 00790 DBusList *link; 00791 00792 link = *list; 00793 while (link != NULL) 00794 { 00795 DBusList *next = _dbus_list_get_next_link (list, link); 00796 00797 (* function) (link->data, data); 00798 00799 link = next; 00800 } 00801 } 00802 00809 dbus_bool_t 00810 _dbus_list_length_is_one (DBusList **list) 00811 { 00812 return (*list != NULL && 00813 (*list)->next == *list); 00814 } 00815 00818 #ifdef DBUS_BUILD_TESTS 00819 #include "dbus-test.h" 00820 #include <stdio.h> 00821 00822 static void 00823 verify_list (DBusList **list) 00824 { 00825 DBusList *link; 00826 int length; 00827 00828 link = *list; 00829 00830 if (link == NULL) 00831 return; 00832 00833 if (link->next == link) 00834 { 00835 _dbus_assert (link->prev == link); 00836 _dbus_assert (*list == link); 00837 return; 00838 } 00839 00840 length = 0; 00841 do 00842 { 00843 length += 1; 00844 _dbus_assert (link->prev->next == link); 00845 _dbus_assert (link->next->prev == link); 00846 link = link->next; 00847 } 00848 while (link != *list); 00849 00850 _dbus_assert (length == _dbus_list_get_length (list)); 00851 00852 if (length == 1) 00853 _dbus_assert (_dbus_list_length_is_one (list)); 00854 else 00855 _dbus_assert (!_dbus_list_length_is_one (list)); 00856 } 00857 00858 static dbus_bool_t 00859 is_ascending_sequence (DBusList **list) 00860 { 00861 DBusList *link; 00862 int prev; 00863 00864 prev = _DBUS_INT_MIN; 00865 00866 link = _dbus_list_get_first_link (list); 00867 while (link != NULL) 00868 { 00869 int v = _DBUS_POINTER_TO_INT (link->data); 00870 00871 if (v <= prev) 00872 return FALSE; 00873 00874 prev = v; 00875 00876 link = _dbus_list_get_next_link (list, link); 00877 } 00878 00879 return TRUE; 00880 } 00881 00882 static dbus_bool_t 00883 is_descending_sequence (DBusList **list) 00884 { 00885 DBusList *link; 00886 int prev; 00887 00888 prev = _DBUS_INT_MAX; 00889 00890 link = _dbus_list_get_first_link (list); 00891 while (link != NULL) 00892 { 00893 int v = _DBUS_POINTER_TO_INT (link->data); 00894 00895 if (v >= prev) 00896 return FALSE; 00897 00898 prev = v; 00899 00900 link = _dbus_list_get_next_link (list, link); 00901 } 00902 00903 return TRUE; 00904 } 00905 00906 static dbus_bool_t 00907 all_even_values (DBusList **list) 00908 { 00909 DBusList *link; 00910 00911 link = _dbus_list_get_first_link (list); 00912 while (link != NULL) 00913 { 00914 int v = _DBUS_POINTER_TO_INT (link->data); 00915 00916 if ((v % 2) != 0) 00917 return FALSE; 00918 00919 link = _dbus_list_get_next_link (list, link); 00920 } 00921 00922 return TRUE; 00923 } 00924 00925 static dbus_bool_t 00926 all_odd_values (DBusList **list) 00927 { 00928 DBusList *link; 00929 00930 link = _dbus_list_get_first_link (list); 00931 while (link != NULL) 00932 { 00933 int v = _DBUS_POINTER_TO_INT (link->data); 00934 00935 if ((v % 2) == 0) 00936 return FALSE; 00937 00938 link = _dbus_list_get_next_link (list, link); 00939 } 00940 00941 return TRUE; 00942 } 00943 00944 static dbus_bool_t 00945 lists_equal (DBusList **list1, 00946 DBusList **list2) 00947 { 00948 DBusList *link1; 00949 DBusList *link2; 00950 00951 link1 = _dbus_list_get_first_link (list1); 00952 link2 = _dbus_list_get_first_link (list2); 00953 while (link1 && link2) 00954 { 00955 if (link1->data != link2->data) 00956 return FALSE; 00957 00958 link1 = _dbus_list_get_next_link (list1, link1); 00959 link2 = _dbus_list_get_next_link (list2, link2); 00960 } 00961 00962 if (link1 || link2) 00963 return FALSE; 00964 00965 return TRUE; 00966 } 00967 00973 dbus_bool_t 00974 _dbus_list_test (void) 00975 { 00976 DBusList *list1; 00977 DBusList *list2; 00978 DBusList *link1; 00979 DBusList *link2; 00980 DBusList *copy1; 00981 DBusList *copy2; 00982 int i; 00983 00984 list1 = NULL; 00985 list2 = NULL; 00986 00987 /* Test append and prepend */ 00988 00989 i = 0; 00990 while (i < 10) 00991 { 00992 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i))) 00993 _dbus_assert_not_reached ("could not allocate for append"); 00994 00995 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i))) 00996 _dbus_assert_not_reached ("count not allocate for prepend"); 00997 ++i; 00998 00999 verify_list (&list1); 01000 verify_list (&list2); 01001 01002 _dbus_assert (_dbus_list_get_length (&list1) == i); 01003 _dbus_assert (_dbus_list_get_length (&list2) == i); 01004 } 01005 01006 _dbus_assert (is_ascending_sequence (&list1)); 01007 _dbus_assert (is_descending_sequence (&list2)); 01008 01009 /* Test list clear */ 01010 _dbus_list_clear (&list1); 01011 _dbus_list_clear (&list2); 01012 01013 verify_list (&list1); 01014 verify_list (&list2); 01015 01016 /* Test get_first, get_last, pop_first, pop_last */ 01017 01018 i = 0; 01019 while (i < 10) 01020 { 01021 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01022 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01023 ++i; 01024 } 01025 01026 --i; 01027 while (i >= 0) 01028 { 01029 void *got_data1; 01030 void *got_data2; 01031 01032 void *data1; 01033 void *data2; 01034 01035 got_data1 = _dbus_list_get_last (&list1); 01036 got_data2 = _dbus_list_get_first (&list2); 01037 01038 data1 = _dbus_list_pop_last (&list1); 01039 data2 = _dbus_list_pop_first (&list2); 01040 01041 _dbus_assert (got_data1 == data1); 01042 _dbus_assert (got_data2 == data2); 01043 01044 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01045 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01046 01047 verify_list (&list1); 01048 verify_list (&list2); 01049 01050 _dbus_assert (is_ascending_sequence (&list1)); 01051 _dbus_assert (is_descending_sequence (&list2)); 01052 01053 --i; 01054 } 01055 01056 _dbus_assert (list1 == NULL); 01057 _dbus_assert (list2 == NULL); 01058 01059 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */ 01060 01061 i = 0; 01062 while (i < 10) 01063 { 01064 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01065 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01066 ++i; 01067 } 01068 01069 --i; 01070 while (i >= 0) 01071 { 01072 DBusList *got_link1; 01073 DBusList *got_link2; 01074 01075 DBusList *link1; 01076 DBusList *link2; 01077 01078 void *data1; 01079 void *data2; 01080 01081 got_link1 = _dbus_list_get_last_link (&list1); 01082 got_link2 = _dbus_list_get_first_link (&list2); 01083 01084 link1 = _dbus_list_pop_last_link (&list1); 01085 link2 = _dbus_list_pop_first_link (&list2); 01086 01087 _dbus_assert (got_link1 == link1); 01088 _dbus_assert (got_link2 == link2); 01089 01090 data1 = link1->data; 01091 data2 = link2->data; 01092 01093 _dbus_list_free_link (link1); 01094 _dbus_list_free_link (link2); 01095 01096 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i); 01097 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i); 01098 01099 verify_list (&list1); 01100 verify_list (&list2); 01101 01102 _dbus_assert (is_ascending_sequence (&list1)); 01103 _dbus_assert (is_descending_sequence (&list2)); 01104 01105 --i; 01106 } 01107 01108 _dbus_assert (list1 == NULL); 01109 _dbus_assert (list2 == NULL); 01110 01111 /* Test iteration */ 01112 01113 i = 0; 01114 while (i < 10) 01115 { 01116 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01117 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01118 ++i; 01119 01120 verify_list (&list1); 01121 verify_list (&list2); 01122 01123 _dbus_assert (_dbus_list_get_length (&list1) == i); 01124 _dbus_assert (_dbus_list_get_length (&list2) == i); 01125 } 01126 01127 _dbus_assert (is_ascending_sequence (&list1)); 01128 _dbus_assert (is_descending_sequence (&list2)); 01129 01130 --i; 01131 link2 = _dbus_list_get_first_link (&list2); 01132 while (link2 != NULL) 01133 { 01134 verify_list (&link2); /* pretend this link is the head */ 01135 01136 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01137 01138 link2 = _dbus_list_get_next_link (&list2, link2); 01139 --i; 01140 } 01141 01142 i = 0; 01143 link1 = _dbus_list_get_first_link (&list1); 01144 while (link1 != NULL) 01145 { 01146 verify_list (&link1); /* pretend this link is the head */ 01147 01148 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01149 01150 link1 = _dbus_list_get_next_link (&list1, link1); 01151 ++i; 01152 } 01153 01154 --i; 01155 link1 = _dbus_list_get_last_link (&list1); 01156 while (link1 != NULL) 01157 { 01158 verify_list (&link1); /* pretend this link is the head */ 01159 01160 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01161 01162 link1 = _dbus_list_get_prev_link (&list1, link1); 01163 --i; 01164 } 01165 01166 _dbus_list_clear (&list1); 01167 _dbus_list_clear (&list2); 01168 01169 /* Test remove */ 01170 01171 i = 0; 01172 while (i < 10) 01173 { 01174 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01175 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01176 ++i; 01177 } 01178 01179 --i; 01180 while (i >= 0) 01181 { 01182 if ((i % 2) == 0) 01183 { 01184 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01185 _dbus_assert_not_reached ("element should have been in list"); 01186 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01187 _dbus_assert_not_reached ("element should have been in list"); 01188 01189 verify_list (&list1); 01190 verify_list (&list2); 01191 } 01192 --i; 01193 } 01194 01195 _dbus_assert (all_odd_values (&list1)); 01196 _dbus_assert (all_odd_values (&list2)); 01197 01198 _dbus_list_clear (&list1); 01199 _dbus_list_clear (&list2); 01200 01201 /* test removing the other half of the elements */ 01202 01203 i = 0; 01204 while (i < 10) 01205 { 01206 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01207 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01208 ++i; 01209 } 01210 01211 --i; 01212 while (i >= 0) 01213 { 01214 if ((i % 2) != 0) 01215 { 01216 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i))) 01217 _dbus_assert_not_reached ("element should have been in list"); 01218 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i))) 01219 _dbus_assert_not_reached ("element should have been in list"); 01220 01221 verify_list (&list1); 01222 verify_list (&list2); 01223 } 01224 --i; 01225 } 01226 01227 _dbus_assert (all_even_values (&list1)); 01228 _dbus_assert (all_even_values (&list2)); 01229 01230 /* clear list using remove_link */ 01231 while (list1 != NULL) 01232 { 01233 _dbus_list_remove_link (&list1, list1); 01234 verify_list (&list1); 01235 } 01236 while (list2 != NULL) 01237 { 01238 _dbus_list_remove_link (&list2, list2); 01239 verify_list (&list2); 01240 } 01241 01242 /* Test remove link more generally */ 01243 i = 0; 01244 while (i < 10) 01245 { 01246 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01247 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01248 ++i; 01249 } 01250 01251 --i; 01252 link2 = _dbus_list_get_first_link (&list2); 01253 while (link2 != NULL) 01254 { 01255 DBusList *next = _dbus_list_get_next_link (&list2, link2); 01256 01257 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i); 01258 01259 if ((i % 2) == 0) 01260 _dbus_list_remove_link (&list2, link2); 01261 01262 verify_list (&list2); 01263 01264 link2 = next; 01265 --i; 01266 } 01267 01268 _dbus_assert (all_odd_values (&list2)); 01269 _dbus_list_clear (&list2); 01270 01271 i = 0; 01272 link1 = _dbus_list_get_first_link (&list1); 01273 while (link1 != NULL) 01274 { 01275 DBusList *next = _dbus_list_get_next_link (&list1, link1); 01276 01277 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i); 01278 01279 if ((i % 2) != 0) 01280 _dbus_list_remove_link (&list1, link1); 01281 01282 verify_list (&list1); 01283 01284 link1 = next; 01285 ++i; 01286 } 01287 01288 _dbus_assert (all_even_values (&list1)); 01289 _dbus_list_clear (&list1); 01290 01291 /* Test copying a list */ 01292 i = 0; 01293 while (i < 10) 01294 { 01295 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)); 01296 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)); 01297 ++i; 01298 } 01299 01300 /* bad pointers, because they are allowed in the copy dest */ 01301 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01302 copy2 = _DBUS_INT_TO_POINTER (23); 01303 01304 _dbus_list_copy (&list1, &copy1); 01305 verify_list (&list1); 01306 verify_list (&copy1); 01307 _dbus_assert (lists_equal (&list1, &copy1)); 01308 01309 _dbus_list_copy (&list2, &copy2); 01310 verify_list (&list2); 01311 verify_list (&copy2); 01312 _dbus_assert (lists_equal (&list2, &copy2)); 01313 01314 /* Now test copying empty lists */ 01315 _dbus_list_clear (&list1); 01316 _dbus_list_clear (&list2); 01317 _dbus_list_clear (&copy1); 01318 _dbus_list_clear (&copy2); 01319 01320 /* bad pointers, because they are allowed in the copy dest */ 01321 copy1 = _DBUS_INT_TO_POINTER (0x342234); 01322 copy2 = _DBUS_INT_TO_POINTER (23); 01323 01324 _dbus_list_copy (&list1, &copy1); 01325 verify_list (&list1); 01326 verify_list (&copy1); 01327 _dbus_assert (lists_equal (&list1, &copy1)); 01328 01329 _dbus_list_copy (&list2, &copy2); 01330 verify_list (&list2); 01331 verify_list (&copy2); 01332 _dbus_assert (lists_equal (&list2, &copy2)); 01333 01334 _dbus_list_clear (&list1); 01335 _dbus_list_clear (&list2); 01336 01337 /* insert_before on empty list */ 01338 _dbus_list_insert_before (&list1, NULL, 01339 _DBUS_INT_TO_POINTER (0)); 01340 verify_list (&list1); 01341 01342 /* inserting before first element */ 01343 _dbus_list_insert_before (&list1, list1, 01344 _DBUS_INT_TO_POINTER (2)); 01345 verify_list (&list1); 01346 _dbus_assert (is_descending_sequence (&list1)); 01347 01348 /* inserting in the middle */ 01349 _dbus_list_insert_before (&list1, list1->next, 01350 _DBUS_INT_TO_POINTER (1)); 01351 verify_list (&list1); 01352 _dbus_assert (is_descending_sequence (&list1)); 01353 01354 /* using insert_before to append */ 01355 _dbus_list_insert_before (&list1, NULL, 01356 _DBUS_INT_TO_POINTER (-1)); 01357 verify_list (&list1); 01358 _dbus_assert (is_descending_sequence (&list1)); 01359 01360 _dbus_list_clear (&list1); 01361 01362 /* insert_after on empty list */ 01363 _dbus_list_insert_after (&list1, NULL, 01364 _DBUS_INT_TO_POINTER (0)); 01365 verify_list (&list1); 01366 01367 /* inserting after first element */ 01368 _dbus_list_insert_after (&list1, list1, 01369 _DBUS_INT_TO_POINTER (1)); 01370 verify_list (&list1); 01371 _dbus_assert (is_ascending_sequence (&list1)); 01372 01373 /* inserting at the end */ 01374 _dbus_list_insert_after (&list1, list1->next, 01375 _DBUS_INT_TO_POINTER (2)); 01376 verify_list (&list1); 01377 _dbus_assert (is_ascending_sequence (&list1)); 01378 01379 /* using insert_after to prepend */ 01380 _dbus_list_insert_after (&list1, NULL, 01381 _DBUS_INT_TO_POINTER (-1)); 01382 verify_list (&list1); 01383 _dbus_assert (is_ascending_sequence (&list1)); 01384 01385 _dbus_list_clear (&list1); 01386 01387 /* using remove_last */ 01388 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)); 01389 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)); 01390 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)); 01391 01392 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2)); 01393 01394 verify_list (&list1); 01395 _dbus_assert (is_ascending_sequence (&list1)); 01396 01397 _dbus_list_clear (&list1); 01398 01399 return TRUE; 01400 } 01401 01402 #endif

Generated on Mon Aug 16 17:40:08 2004 for D-BUS by doxygen 1.3.8