D-Bus 1.6.12

dbus-list.c

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, &copy1);
01267   verify_list (&list1);
01268   verify_list (&copy1);
01269   _dbus_assert (lists_equal (&list1, &copy1));
01270   
01271   _dbus_list_copy (&list2, &copy2);
01272   verify_list (&list2);
01273   verify_list (&copy2);
01274   _dbus_assert (lists_equal (&list2, &copy2));
01275 
01276   /* Now test copying empty lists */
01277   _dbus_list_clear (&list1);
01278   _dbus_list_clear (&list2);
01279   _dbus_list_clear (&copy1);
01280   _dbus_list_clear (&copy2);
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, &copy1);
01287   verify_list (&list1);
01288   verify_list (&copy1);
01289   _dbus_assert (lists_equal (&list1, &copy1));
01290   
01291   _dbus_list_copy (&list2, &copy2);
01292   verify_list (&list2);
01293   verify_list (&copy2);
01294   _dbus_assert (lists_equal (&list2, &copy2));
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