D-Bus  1.10.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 /* 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, &copy1);
01278   verify_list (&list1);
01279   verify_list (&copy1);
01280   _dbus_assert (lists_equal (&list1, &copy1));
01281   
01282   _dbus_list_copy (&list2, &copy2);
01283   verify_list (&list2);
01284   verify_list (&copy2);
01285   _dbus_assert (lists_equal (&list2, &copy2));
01286 
01287   /* Now test copying empty lists */
01288   _dbus_list_clear (&list1);
01289   _dbus_list_clear (&list2);
01290   _dbus_list_clear (&copy1);
01291   _dbus_list_clear (&copy2);
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, &copy1);
01298   verify_list (&list1);
01299   verify_list (&copy1);
01300   _dbus_assert (lists_equal (&list1, &copy1));
01301   
01302   _dbus_list_copy (&list2, &copy2);
01303   verify_list (&list2);
01304   verify_list (&copy2);
01305   _dbus_assert (lists_equal (&list2, &copy2));
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