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