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-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   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 #ifdef DBUS_BUILD_TESTS
00130 static void
00131 link_after (DBusList **list,
00132             DBusList  *after_this_link,
00133             DBusList  *link)
00134 {
00135   if (*list == NULL)
00136     {
00137       link->prev = link;
00138       link->next = link;
00139       *list = link;
00140     }
00141   else
00142     {
00143       link->prev = after_this_link;
00144       link->next = after_this_link->next;
00145       after_this_link->next = link;
00146       link->next->prev = link;
00147     }
00148 }
00149 #endif /* DBUS_BUILD_TESTS */
00150 
00220 DBusList*
00221 _dbus_list_alloc_link (void *data)
00222 {
00223   return alloc_link (data);
00224 }
00225 
00232 void
00233 _dbus_list_free_link (DBusList *link)
00234 {
00235   free_link (link);
00236 }
00237 
00238 
00248 dbus_bool_t
00249 _dbus_list_append (DBusList **list,
00250                    void      *data)
00251 {
00252   if (!_dbus_list_prepend (list, data))
00253     return FALSE;
00254 
00255   /* Now cycle the list forward one so the prepended node is the tail */
00256   *list = (*list)->next;
00257 
00258   return TRUE;
00259 }
00260 
00270 dbus_bool_t
00271 _dbus_list_prepend (DBusList **list,
00272                     void      *data)
00273 {
00274   DBusList *link;
00275 
00276   link = alloc_link (data);
00277   if (link == NULL)
00278     return FALSE;
00279 
00280   link_before (list, *list, link);
00281 
00282   return TRUE;
00283 }
00284 
00293 void
00294 _dbus_list_append_link (DBusList **list,
00295                         DBusList *link)
00296 {
00297   _dbus_list_prepend_link (list, link);
00298 
00299   /* Now cycle the list forward one so the prepended node is the tail */
00300   *list = (*list)->next;
00301 }
00302 
00311 void
00312 _dbus_list_prepend_link (DBusList **list,
00313                          DBusList *link)
00314 {
00315   link_before (list, *list, link);
00316 }
00317 
00318 #ifdef DBUS_BUILD_TESTS
00319 
00327 dbus_bool_t
00328 _dbus_list_insert_before (DBusList **list,
00329                           DBusList  *before_this_link,
00330                           void      *data)
00331 {
00332   DBusList *link;
00333   
00334   if (before_this_link == NULL)
00335     return _dbus_list_append (list, data);
00336   else
00337     {
00338       link = alloc_link (data);
00339       if (link == NULL)
00340         return FALSE;
00341   
00342       link_before (list, before_this_link, link);
00343     }
00344   
00345   return TRUE;
00346 }
00347 #endif /* DBUS_BUILD_TESTS */
00348 
00349 #ifdef DBUS_BUILD_TESTS
00350 
00358 dbus_bool_t
00359 _dbus_list_insert_after (DBusList **list,
00360                          DBusList  *after_this_link,
00361                          void      *data)
00362 {
00363   DBusList *link;  
00364 
00365   if (after_this_link == NULL)
00366     return _dbus_list_prepend (list, data);
00367   else
00368     {
00369       link = alloc_link (data);
00370       if (link == NULL)
00371         return FALSE;
00372   
00373       link_after (list, after_this_link, link);
00374     }
00375   
00376   return TRUE;
00377 }
00378 #endif /* DBUS_BUILD_TESTS */
00379 
00387 void
00388 _dbus_list_insert_before_link (DBusList **list,
00389                                DBusList  *before_this_link,
00390                                DBusList  *link)
00391 {
00392   if (before_this_link == NULL)
00393     _dbus_list_append_link (list, link);
00394   else
00395     link_before (list, before_this_link, link);
00396 }
00397 
00398 #ifdef DBUS_BUILD_TESTS
00399 
00406 void
00407 _dbus_list_insert_after_link (DBusList **list,
00408                               DBusList  *after_this_link,
00409                               DBusList  *link)
00410 {
00411   if (after_this_link == NULL)
00412     _dbus_list_prepend_link (list, link);
00413   else  
00414     link_after (list, after_this_link, link);
00415 }
00416 #endif /* DBUS_BUILD_TESTS */
00417 
00428 dbus_bool_t
00429 _dbus_list_remove (DBusList **list,
00430                    void      *data)
00431 {
00432   DBusList *link;
00433 
00434   link = *list;
00435   while (link != NULL)
00436     {
00437       if (link->data == data)
00438         {
00439           _dbus_list_remove_link (list, link);
00440           return TRUE;
00441         }
00442       
00443       link = _dbus_list_get_next_link (list, link);
00444     }
00445 
00446   return FALSE;
00447 }
00448 
00459 dbus_bool_t
00460 _dbus_list_remove_last (DBusList **list,
00461                         void      *data)
00462 {
00463   DBusList *link;
00464 
00465   link = _dbus_list_find_last (list, data);
00466   if (link)
00467     {
00468       _dbus_list_remove_link (list, link);
00469       return TRUE;
00470     }
00471   else
00472     return FALSE;
00473 }
00474 
00485 DBusList*
00486 _dbus_list_find_last (DBusList **list,
00487                       void      *data)
00488 {
00489   DBusList *link;
00490 
00491   link = _dbus_list_get_last_link (list);
00492 
00493   while (link != NULL)
00494     {
00495       if (link->data == data)
00496         return link;
00497       
00498       link = _dbus_list_get_prev_link (list, link);
00499     }
00500 
00501   return NULL;
00502 }
00503 
00512 void
00513 _dbus_list_unlink (DBusList **list,
00514                    DBusList  *link)
00515 {
00516   if (link->next == link)
00517     {
00518       /* one-element list */
00519       *list = NULL;
00520     }
00521   else
00522     {      
00523       link->prev->next = link->next;
00524       link->next->prev = link->prev;
00525       
00526       if (*list == link)
00527         *list = link->next;
00528     }
00529 
00530   link->next = NULL;
00531   link->prev = NULL;
00532 }
00533 
00540 void
00541 _dbus_list_remove_link (DBusList **list,
00542                         DBusList  *link)
00543 {
00544   _dbus_list_unlink (list, link);
00545   free_link (link);
00546 }
00547 
00555 void
00556 _dbus_list_clear (DBusList **list)
00557 {
00558   DBusList *link;
00559 
00560   link = *list;
00561   while (link != NULL)
00562     {
00563       DBusList *next = _dbus_list_get_next_link (list, link);
00564       
00565       free_link (link);
00566       
00567       link = next;
00568     }
00569 
00570   *list = NULL;
00571 }
00572 
00580 DBusList*
00581 _dbus_list_get_first_link (DBusList **list)
00582 {
00583   return *list;
00584 }
00585 
00593 DBusList*
00594 _dbus_list_get_last_link (DBusList **list)
00595 {
00596   if (*list == NULL)
00597     return NULL;
00598   else
00599     return (*list)->prev;
00600 }
00601 
00609 void*
00610 _dbus_list_get_last (DBusList **list)
00611 {
00612   if (*list == NULL)
00613     return NULL;
00614   else
00615     return (*list)->prev->data;
00616 }
00617 
00625 void*
00626 _dbus_list_get_first (DBusList **list)
00627 {
00628   if (*list == NULL)
00629     return NULL;
00630   else
00631     return (*list)->data;
00632 }
00633 
00641 DBusList*
00642 _dbus_list_pop_first_link (DBusList **list)
00643 {
00644   DBusList *link;
00645   
00646   link = _dbus_list_get_first_link (list);
00647   if (link == NULL)
00648     return NULL;
00649 
00650   _dbus_list_unlink (list, link);
00651 
00652   return link;
00653 }
00654 
00662 void*
00663 _dbus_list_pop_first (DBusList **list)
00664 {
00665   DBusList *link;
00666   void *data;
00667   
00668   link = _dbus_list_get_first_link (list);
00669   if (link == NULL)
00670     return NULL;
00671   
00672   data = link->data;
00673   _dbus_list_remove_link (list, link);
00674 
00675   return data;
00676 }
00677 
00685 void*
00686 _dbus_list_pop_last (DBusList **list)
00687 {
00688   DBusList *link;
00689   void *data;
00690   
00691   link = _dbus_list_get_last_link (list);
00692   if (link == NULL)
00693     return NULL;
00694   
00695   data = link->data;
00696   _dbus_list_remove_link (list, link);
00697 
00698   return data;
00699 }
00700 
00701 #ifdef DBUS_BUILD_TESTS
00702 
00709 DBusList*
00710 _dbus_list_pop_last_link (DBusList **list)
00711 {
00712   DBusList *link;
00713   
00714   link = _dbus_list_get_last_link (list);
00715   if (link == NULL)
00716     return NULL;
00717 
00718   _dbus_list_unlink (list, link);
00719 
00720   return link;
00721 }
00722 #endif /* DBUS_BUILD_TESTS */
00723 
00733 dbus_bool_t
00734 _dbus_list_copy (DBusList **list,
00735                  DBusList **dest)
00736 {
00737   DBusList *link;
00738 
00739   _dbus_assert (list != dest);
00740 
00741   *dest = NULL;
00742   
00743   link = *list;
00744   while (link != NULL)
00745     {
00746       if (!_dbus_list_append (dest, link->data))
00747         {
00748           /* free what we have so far */
00749           _dbus_list_clear (dest);
00750           return FALSE;
00751         }
00752       
00753       link = _dbus_list_get_next_link (list, link);
00754     }
00755 
00756   return TRUE;
00757 }
00758 
00766 int
00767 _dbus_list_get_length (DBusList **list)
00768 {
00769   DBusList *link;
00770   int length;
00771 
00772   length = 0;
00773   
00774   link = *list;
00775   while (link != NULL)
00776     {
00777       ++length;
00778       
00779       link = _dbus_list_get_next_link (list, link);
00780     }
00781 
00782   return length;
00783 }
00784 
00795 void
00796 _dbus_list_foreach (DBusList          **list,
00797                     DBusForeachFunction function,
00798                     void               *data)
00799 {
00800   DBusList *link;
00801 
00802   link = *list;
00803   while (link != NULL)
00804     {
00805       DBusList *next = _dbus_list_get_next_link (list, link);
00806       
00807       (* function) (link->data, data);
00808       
00809       link = next;
00810     }
00811 }
00812 
00819 dbus_bool_t
00820 _dbus_list_length_is_one (DBusList **list)
00821 {
00822   return (*list != NULL &&
00823           (*list)->next == *list);
00824 }
00825 
00828 #ifdef DBUS_BUILD_TESTS
00829 #include "dbus-test.h"
00830 #include <stdio.h>
00831 
00832 static void
00833 verify_list (DBusList **list)
00834 {
00835   DBusList *link;
00836   int length;
00837   
00838   link = *list;
00839 
00840   if (link == NULL)
00841     return;
00842 
00843   if (link->next == link)
00844     {
00845       _dbus_assert (link->prev == link);
00846       _dbus_assert (*list == link);
00847       return;
00848     }
00849 
00850   length = 0;
00851   do
00852     {
00853       length += 1;
00854       _dbus_assert (link->prev->next == link);
00855       _dbus_assert (link->next->prev == link);
00856       link = link->next;
00857     }
00858   while (link != *list);
00859 
00860   _dbus_assert (length == _dbus_list_get_length (list));
00861 
00862   if (length == 1)
00863     _dbus_assert (_dbus_list_length_is_one (list));
00864   else
00865     _dbus_assert (!_dbus_list_length_is_one (list));
00866 }
00867 
00868 static dbus_bool_t
00869 is_ascending_sequence (DBusList **list)
00870 {
00871   DBusList *link;
00872   int prev;
00873 
00874   prev = _DBUS_INT_MIN;
00875   
00876   link = _dbus_list_get_first_link (list);
00877   while (link != NULL)
00878     {
00879       int v = _DBUS_POINTER_TO_INT (link->data);
00880       
00881       if (v <= prev)
00882         return FALSE;
00883 
00884       prev = v;
00885       
00886       link = _dbus_list_get_next_link (list, link);
00887     }
00888 
00889   return TRUE;
00890 }
00891 
00892 static dbus_bool_t
00893 is_descending_sequence (DBusList **list)
00894 {
00895   DBusList *link;
00896   int prev;
00897 
00898   prev = _DBUS_INT_MAX;
00899   
00900   link = _dbus_list_get_first_link (list);
00901   while (link != NULL)
00902     {
00903       int v = _DBUS_POINTER_TO_INT (link->data);
00904 
00905       if (v >= prev)
00906         return FALSE;
00907 
00908       prev = v;
00909       
00910       link = _dbus_list_get_next_link (list, link);
00911     }
00912 
00913   return TRUE;
00914 }
00915 
00916 static dbus_bool_t
00917 all_even_values (DBusList **list)
00918 {
00919   DBusList *link;
00920   
00921   link = _dbus_list_get_first_link (list);
00922   while (link != NULL)
00923     {
00924       int v = _DBUS_POINTER_TO_INT (link->data);
00925 
00926       if ((v % 2) != 0)
00927         return FALSE;
00928       
00929       link = _dbus_list_get_next_link (list, link);
00930     }
00931 
00932   return TRUE;
00933 }
00934 
00935 static dbus_bool_t
00936 all_odd_values (DBusList **list)
00937 {
00938   DBusList *link;
00939   
00940   link = _dbus_list_get_first_link (list);
00941   while (link != NULL)
00942     {
00943       int v = _DBUS_POINTER_TO_INT (link->data);
00944 
00945       if ((v % 2) == 0)
00946         return FALSE;
00947       
00948       link = _dbus_list_get_next_link (list, link);
00949     }
00950 
00951   return TRUE;
00952 }
00953 
00954 static dbus_bool_t
00955 lists_equal (DBusList **list1,
00956              DBusList **list2)
00957 {
00958   DBusList *link1;
00959   DBusList *link2;
00960   
00961   link1 = _dbus_list_get_first_link (list1);
00962   link2 = _dbus_list_get_first_link (list2);
00963   while (link1 && link2)
00964     {
00965       if (link1->data != link2->data)
00966         return FALSE;
00967       
00968       link1 = _dbus_list_get_next_link (list1, link1);
00969       link2 = _dbus_list_get_next_link (list2, link2);
00970     }
00971 
00972   if (link1 || link2)
00973     return FALSE;
00974 
00975   return TRUE;
00976 }
00977 
00983 dbus_bool_t
00984 _dbus_list_test (void)
00985 {
00986   DBusList *list1;
00987   DBusList *list2;
00988   DBusList *link1;
00989   DBusList *link2;
00990   DBusList *copy1;
00991   DBusList *copy2;
00992   int i;
00993   
00994   list1 = NULL;
00995   list2 = NULL;
00996 
00997   /* Test append and prepend */
00998   
00999   i = 0;
01000   while (i < 10)
01001     {
01002       if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
01003         _dbus_assert_not_reached ("could not allocate for append");
01004       
01005       if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
01006         _dbus_assert_not_reached ("count not allocate for prepend");
01007       ++i;
01008 
01009       verify_list (&list1);
01010       verify_list (&list2);
01011       
01012       _dbus_assert (_dbus_list_get_length (&list1) == i);
01013       _dbus_assert (_dbus_list_get_length (&list2) == i);
01014     }
01015 
01016   _dbus_assert (is_ascending_sequence (&list1));
01017   _dbus_assert (is_descending_sequence (&list2));
01018 
01019   /* Test list clear */
01020   _dbus_list_clear (&list1);
01021   _dbus_list_clear (&list2);
01022 
01023   verify_list (&list1);
01024   verify_list (&list2);
01025 
01026   /* Test get_first, get_last, pop_first, pop_last */
01027   
01028   i = 0;
01029   while (i < 10)
01030     {
01031       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01032       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01033       ++i;
01034     }
01035 
01036   --i;
01037   while (i >= 0)
01038     {
01039       void *got_data1;
01040       void *got_data2;
01041       
01042       void *data1;
01043       void *data2;
01044 
01045       got_data1 = _dbus_list_get_last (&list1);
01046       got_data2 = _dbus_list_get_first (&list2);
01047       
01048       data1 = _dbus_list_pop_last (&list1);
01049       data2 = _dbus_list_pop_first (&list2);
01050 
01051       _dbus_assert (got_data1 == data1);
01052       _dbus_assert (got_data2 == data2);
01053       
01054       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
01055       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
01056 
01057       verify_list (&list1);
01058       verify_list (&list2);
01059 
01060       _dbus_assert (is_ascending_sequence (&list1));
01061       _dbus_assert (is_descending_sequence (&list2));
01062       
01063       --i;
01064     }
01065 
01066   _dbus_assert (list1 == NULL);
01067   _dbus_assert (list2 == NULL);
01068 
01069   /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
01070   
01071   i = 0;
01072   while (i < 10)
01073     {
01074       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01075       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01076       ++i;
01077     }
01078 
01079   --i;
01080   while (i >= 0)
01081     {
01082       DBusList *got_link1;
01083       DBusList *got_link2;
01084 
01085       DBusList *link1;
01086       DBusList *link2;
01087       
01088       void *data1;
01089       void *data2;
01090       
01091       got_link1 = _dbus_list_get_last_link (&list1);
01092       got_link2 = _dbus_list_get_first_link (&list2);
01093       
01094       link1 = _dbus_list_pop_last_link (&list1);
01095       link2 = _dbus_list_pop_first_link (&list2);
01096 
01097       _dbus_assert (got_link1 == link1);
01098       _dbus_assert (got_link2 == link2);
01099 
01100       data1 = link1->data;
01101       data2 = link2->data;
01102 
01103       _dbus_list_free_link (link1);
01104       _dbus_list_free_link (link2);
01105       
01106       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
01107       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
01108 
01109       verify_list (&list1);
01110       verify_list (&list2);
01111 
01112       _dbus_assert (is_ascending_sequence (&list1));
01113       _dbus_assert (is_descending_sequence (&list2));
01114       
01115       --i;
01116     }
01117 
01118   _dbus_assert (list1 == NULL);
01119   _dbus_assert (list2 == NULL);
01120   
01121   /* Test iteration */
01122   
01123   i = 0;
01124   while (i < 10)
01125     {
01126       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01127       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01128       ++i;
01129 
01130       verify_list (&list1);
01131       verify_list (&list2);
01132       
01133       _dbus_assert (_dbus_list_get_length (&list1) == i);
01134       _dbus_assert (_dbus_list_get_length (&list2) == i);
01135     }
01136 
01137   _dbus_assert (is_ascending_sequence (&list1));
01138   _dbus_assert (is_descending_sequence (&list2));
01139 
01140   --i;
01141   link2 = _dbus_list_get_first_link (&list2);
01142   while (link2 != NULL)
01143     {
01144       verify_list (&link2); /* pretend this link is the head */
01145       
01146       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
01147       
01148       link2 = _dbus_list_get_next_link (&list2, link2);
01149       --i;
01150     }
01151 
01152   i = 0;
01153   link1 = _dbus_list_get_first_link (&list1);
01154   while (link1 != NULL)
01155     {
01156       verify_list (&link1); /* pretend this link is the head */
01157       
01158       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
01159       
01160       link1 = _dbus_list_get_next_link (&list1, link1);
01161       ++i;
01162     }
01163 
01164   --i;
01165   link1 = _dbus_list_get_last_link (&list1);
01166   while (link1 != NULL)
01167     {
01168       verify_list (&link1); /* pretend this link is the head */
01169 
01170       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
01171       
01172       link1 = _dbus_list_get_prev_link (&list1, link1);
01173       --i;
01174     }
01175 
01176   _dbus_list_clear (&list1);
01177   _dbus_list_clear (&list2);
01178 
01179   /* Test remove */
01180   
01181   i = 0;
01182   while (i < 10)
01183     {
01184       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01185       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01186       ++i;
01187     }
01188 
01189   --i;
01190   while (i >= 0)
01191     {
01192       if ((i % 2) == 0)
01193         {
01194           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
01195             _dbus_assert_not_reached ("element should have been in list");
01196           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
01197             _dbus_assert_not_reached ("element should have been in list");
01198 
01199           verify_list (&list1);
01200           verify_list (&list2);
01201         }
01202       --i;
01203     }
01204 
01205   _dbus_assert (all_odd_values (&list1));
01206   _dbus_assert (all_odd_values (&list2));
01207 
01208   _dbus_list_clear (&list1);
01209   _dbus_list_clear (&list2);
01210 
01211   /* test removing the other half of the elements */
01212   
01213   i = 0;
01214   while (i < 10)
01215     {
01216       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01217       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01218       ++i;
01219     }
01220 
01221   --i;
01222   while (i >= 0)
01223     {
01224       if ((i % 2) != 0)
01225         {
01226           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
01227             _dbus_assert_not_reached ("element should have been in list");
01228           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
01229             _dbus_assert_not_reached ("element should have been in list");
01230 
01231           verify_list (&list1);
01232           verify_list (&list2);
01233         }
01234       --i;
01235     }
01236 
01237   _dbus_assert (all_even_values (&list1));
01238   _dbus_assert (all_even_values (&list2));
01239 
01240   /* clear list using remove_link */
01241   while (list1 != NULL)
01242     {
01243       _dbus_list_remove_link (&list1, list1);
01244       verify_list (&list1);
01245     }
01246   while (list2 != NULL)
01247     {
01248       _dbus_list_remove_link (&list2, list2);
01249       verify_list (&list2);
01250     }
01251 
01252   /* Test remove link more generally */
01253   i = 0;
01254   while (i < 10)
01255     {
01256       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01257       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01258       ++i;
01259     }
01260 
01261   --i;
01262   link2 = _dbus_list_get_first_link (&list2);
01263   while (link2 != NULL)
01264     {
01265       DBusList *next = _dbus_list_get_next_link (&list2, link2);
01266       
01267       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
01268 
01269       if ((i % 2) == 0)
01270         _dbus_list_remove_link (&list2, link2);
01271 
01272       verify_list (&list2);
01273       
01274       link2 = next;
01275       --i;
01276     }
01277 
01278   _dbus_assert (all_odd_values (&list2));  
01279   _dbus_list_clear (&list2);
01280   
01281   i = 0;
01282   link1 = _dbus_list_get_first_link (&list1);
01283   while (link1 != NULL)
01284     {
01285       DBusList *next = _dbus_list_get_next_link (&list1, link1);
01286 
01287       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
01288 
01289       if ((i % 2) != 0)
01290         _dbus_list_remove_link (&list1, link1);
01291 
01292       verify_list (&list1);
01293       
01294       link1 = next;
01295       ++i;
01296     }
01297 
01298   _dbus_assert (all_even_values (&list1));
01299   _dbus_list_clear (&list1);
01300 
01301   /* Test copying a list */
01302   i = 0;
01303   while (i < 10)
01304     {
01305       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
01306       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
01307       ++i;
01308     }
01309 
01310   /* bad pointers, because they are allowed in the copy dest */
01311   copy1 = _DBUS_INT_TO_POINTER (0x342234);
01312   copy2 = _DBUS_INT_TO_POINTER (23);
01313   
01314   _dbus_list_copy (&list1, &copy1);
01315   verify_list (&list1);
01316   verify_list (&copy1);
01317   _dbus_assert (lists_equal (&list1, &copy1));
01318   
01319   _dbus_list_copy (&list2, &copy2);
01320   verify_list (&list2);
01321   verify_list (&copy2);
01322   _dbus_assert (lists_equal (&list2, &copy2));
01323 
01324   /* Now test copying empty lists */
01325   _dbus_list_clear (&list1);
01326   _dbus_list_clear (&list2);
01327   _dbus_list_clear (&copy1);
01328   _dbus_list_clear (&copy2);
01329   
01330   /* bad pointers, because they are allowed in the copy dest */
01331   copy1 = _DBUS_INT_TO_POINTER (0x342234);
01332   copy2 = _DBUS_INT_TO_POINTER (23);
01333   
01334   _dbus_list_copy (&list1, &copy1);
01335   verify_list (&list1);
01336   verify_list (&copy1);
01337   _dbus_assert (lists_equal (&list1, &copy1));
01338   
01339   _dbus_list_copy (&list2, &copy2);
01340   verify_list (&list2);
01341   verify_list (&copy2);
01342   _dbus_assert (lists_equal (&list2, &copy2));
01343 
01344   _dbus_list_clear (&list1);
01345   _dbus_list_clear (&list2);
01346   
01347   /* insert_before on empty list */
01348   _dbus_list_insert_before (&list1, NULL,
01349                             _DBUS_INT_TO_POINTER (0));
01350   verify_list (&list1);
01351 
01352   /* inserting before first element */
01353   _dbus_list_insert_before (&list1, list1,
01354                             _DBUS_INT_TO_POINTER (2));
01355   verify_list (&list1);
01356   _dbus_assert (is_descending_sequence (&list1));
01357 
01358   /* inserting in the middle */
01359   _dbus_list_insert_before (&list1, list1->next,
01360                             _DBUS_INT_TO_POINTER (1));
01361   verify_list (&list1);
01362   _dbus_assert (is_descending_sequence (&list1));  
01363 
01364   /* using insert_before to append */
01365   _dbus_list_insert_before (&list1, NULL,
01366                             _DBUS_INT_TO_POINTER (-1));
01367   verify_list (&list1);
01368   _dbus_assert (is_descending_sequence (&list1));
01369   
01370   _dbus_list_clear (&list1);
01371 
01372   /* insert_after on empty list */
01373   _dbus_list_insert_after (&list1, NULL,
01374                            _DBUS_INT_TO_POINTER (0));
01375   verify_list (&list1);
01376 
01377   /* inserting after first element */
01378   _dbus_list_insert_after (&list1, list1,
01379                            _DBUS_INT_TO_POINTER (1));
01380   verify_list (&list1);
01381   _dbus_assert (is_ascending_sequence (&list1));
01382 
01383   /* inserting at the end */
01384   _dbus_list_insert_after (&list1, list1->next,
01385                            _DBUS_INT_TO_POINTER (2));
01386   verify_list (&list1);
01387   _dbus_assert (is_ascending_sequence (&list1));
01388 
01389   /* using insert_after to prepend */
01390   _dbus_list_insert_after (&list1, NULL,
01391                            _DBUS_INT_TO_POINTER (-1));
01392   verify_list (&list1);
01393   _dbus_assert (is_ascending_sequence (&list1));
01394   
01395   _dbus_list_clear (&list1);
01396 
01397   /* using remove_last */
01398   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
01399   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
01400   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
01401 
01402   _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
01403   
01404   verify_list (&list1);
01405   _dbus_assert (is_ascending_sequence (&list1));
01406   
01407   _dbus_list_clear (&list1);
01408   
01409   return TRUE;
01410 }
01411 
01412 #endif

Generated on Fri Sep 30 19:45:35 2005 for D-BUS by  doxygen 1.4.4