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

Generated on Tue Feb 24 16:40:39 2009 for D-Bus by  doxygen 1.5.1