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

dbus-list.c

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

Generated on Thu Aug 11 21:11:13 2005 for D-BUS by  doxygen 1.4.0