D-Bus 1.4.0

dbus-hash.c

00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
00002 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
00003  * 
00004  * Copyright (C) 2002  Red Hat, Inc.
00005  * Copyright (c) 1991-1993 The Regents of the University of California.
00006  * Copyright (c) 1994 Sun Microsystems, Inc.
00007  * 
00008  * Hash table implementation based on generic/tclHash.c from the Tcl
00009  * source code. The original Tcl license applies to portions of the
00010  * code from tclHash.c; the Tcl license follows this standad D-Bus 
00011  * license information.
00012  *
00013  * Licensed under the Academic Free License version 2.1
00014  * 
00015  * This program is free software; you can redistribute it and/or modify
00016  * it under the terms of the GNU General Public License as published by
00017  * the Free Software Foundation; either version 2 of the License, or
00018  * (at your option) any later version.
00019  *
00020  * This program is distributed in the hope that it will be useful,
00021  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00022  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00023  * GNU General Public License for more details.
00024  * 
00025  * You should have received a copy of the GNU General Public License
00026  * along with this program; if not, write to the Free Software
00027  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
00028  *
00029  */
00030 /* 
00031  * The following copyright applies to code from the Tcl distribution.
00032  *
00033  * Copyright (c) 1991-1993 The Regents of the University of California.
00034  * Copyright (c) 1994 Sun Microsystems, Inc.
00035  *
00036  * This software is copyrighted by the Regents of the University of
00037  * California, Sun Microsystems, Inc., Scriptics Corporation, and
00038  * other parties.  The following terms apply to all files associated
00039  * with the software unless explicitly disclaimed in individual files.
00040  * 
00041  * The authors hereby grant permission to use, copy, modify,
00042  * distribute, and license this software and its documentation for any
00043  * purpose, provided that existing copyright notices are retained in
00044  * all copies and that this notice is included verbatim in any
00045  * distributions. No written agreement, license, or royalty fee is
00046  * required for any of the authorized uses.  Modifications to this
00047  * software may be copyrighted by their authors and need not follow
00048  * the licensing terms described here, provided that the new terms are
00049  * clearly indicated on the first page of each file where they apply.
00050  * 
00051  * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
00052  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
00053  * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
00054  * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
00055  * OF THE POSSIBILITY OF SUCH DAMAGE.
00056  * 
00057  * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
00058  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
00059  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
00060  * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
00061  * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
00062  * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
00063  * 
00064  * GOVERNMENT USE: If you are acquiring this software on behalf of the
00065  * U.S. government, the Government shall have only "Restricted Rights"
00066  * in the software and related documentation as defined in the Federal
00067  * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
00068  * are acquiring the software on behalf of the Department of Defense,
00069  * the software shall be classified as "Commercial Computer Software"
00070  * and the Government shall have only "Restricted Rights" as defined
00071  * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
00072  * foregoing, the authors grant the U.S. Government and others acting
00073  * in its behalf permission to use and distribute the software in
00074  * accordance with the terms specified in this license.
00075  */
00076 
00077 #include <config.h>
00078 #include "dbus-hash.h"
00079 #include "dbus-internals.h"
00080 #include "dbus-mempool.h"
00081 
00104 #define REBUILD_MULTIPLIER  3
00105 
00122 #define RANDOM_INDEX(table, i) \
00123     (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
00124 
00130 #define DBUS_SMALL_HASH_TABLE 4
00131 
00135 typedef struct DBusHashEntry DBusHashEntry;
00136 
00143 struct DBusHashEntry
00144 {
00145   DBusHashEntry *next;    
00149   void *key;              
00150   void *value;            
00151 };
00152 
00156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable        *table,
00157                                                   void                 *key,
00158                                                   dbus_bool_t           create_if_not_found,
00159                                                   DBusHashEntry      ***bucket,
00160                                                   DBusPreallocatedHash *preallocated);
00161 
00168 struct DBusHashTable {
00169   int refcount;                       
00171   DBusHashEntry **buckets;            
00175   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
00179   int n_buckets;                       
00182   int n_entries;                       
00185   int hi_rebuild_size;                 
00188   int lo_rebuild_size;                 
00191   int down_shift;                      
00195   int mask;                            
00198   DBusHashType key_type;               
00201   DBusFindEntryFunction find_function; 
00203   DBusFreeFunction free_key_function;   
00204   DBusFreeFunction free_value_function; 
00206   DBusMemPool *entry_pool;              
00207 };
00208 
00212 typedef struct
00213 {
00214   DBusHashTable *table;     
00215   DBusHashEntry **bucket;   
00219   DBusHashEntry *entry;      
00220   DBusHashEntry *next_entry; 
00221   int next_bucket;           
00222   int n_entries_on_init;     
00223 } DBusRealHashIter;
00224 
00225 static DBusHashEntry* find_direct_function      (DBusHashTable          *table,
00226                                                  void                   *key,
00227                                                  dbus_bool_t             create_if_not_found,
00228                                                  DBusHashEntry        ***bucket,
00229                                                  DBusPreallocatedHash   *preallocated);
00230 static DBusHashEntry* find_string_function      (DBusHashTable          *table,
00231                                                  void                   *key,
00232                                                  dbus_bool_t             create_if_not_found,
00233                                                  DBusHashEntry        ***bucket,
00234                                                  DBusPreallocatedHash   *preallocated);
00235 #ifdef DBUS_BUILD_TESTS
00236 static DBusHashEntry* find_two_strings_function (DBusHashTable          *table,
00237                                                  void                   *key,
00238                                                  dbus_bool_t             create_if_not_found,
00239                                                  DBusHashEntry        ***bucket,
00240                                                  DBusPreallocatedHash   *preallocated);
00241 #endif
00242 static unsigned int   string_hash               (const char             *str);
00243 #ifdef DBUS_BUILD_TESTS
00244 static unsigned int   two_strings_hash          (const char             *str);
00245 #endif
00246 static void           rebuild_table             (DBusHashTable          *table);
00247 static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
00248 static void           remove_entry              (DBusHashTable          *table,
00249                                                  DBusHashEntry         **bucket,
00250                                                  DBusHashEntry          *entry);
00251 static void           free_entry                (DBusHashTable          *table,
00252                                                  DBusHashEntry          *entry);
00253 static void           free_entry_data           (DBusHashTable          *table,
00254                                                  DBusHashEntry          *entry);
00255 
00256 
00292 DBusHashTable*
00293 _dbus_hash_table_new (DBusHashType     type,
00294                       DBusFreeFunction key_free_function,
00295                       DBusFreeFunction value_free_function)
00296 {
00297   DBusHashTable *table;
00298   DBusMemPool *entry_pool;
00299   
00300   table = dbus_new0 (DBusHashTable, 1);
00301   if (table == NULL)
00302     return NULL;
00303 
00304   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00305   if (entry_pool == NULL)
00306     {
00307       dbus_free (table);
00308       return NULL;
00309     }
00310   
00311   table->refcount = 1;
00312   table->entry_pool = entry_pool;
00313   
00314   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00315   
00316   table->buckets = table->static_buckets;  
00317   table->n_buckets = DBUS_SMALL_HASH_TABLE;
00318   table->n_entries = 0;
00319   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00320   table->lo_rebuild_size = 0;
00321   table->down_shift = 28;
00322   table->mask = 3;
00323   table->key_type = type;
00324 
00325   _dbus_assert (table->mask < table->n_buckets);
00326   
00327   switch (table->key_type)
00328     {
00329     case DBUS_HASH_INT:
00330     case DBUS_HASH_POINTER:
00331     case DBUS_HASH_UINTPTR:
00332       table->find_function = find_direct_function;
00333       break;
00334     case DBUS_HASH_STRING:
00335       table->find_function = find_string_function;
00336       break;
00337     case DBUS_HASH_TWO_STRINGS:
00338 #ifdef DBUS_BUILD_TESTS
00339       table->find_function = find_two_strings_function;
00340 #endif
00341       break;
00342     default:
00343       _dbus_assert_not_reached ("Unknown hash table type");
00344       break;
00345     }
00346 
00347   table->free_key_function = key_free_function;
00348   table->free_value_function = value_free_function;
00349 
00350   return table;
00351 }
00352 
00353 
00360 DBusHashTable *
00361 _dbus_hash_table_ref (DBusHashTable *table)
00362 {
00363   table->refcount += 1;
00364   
00365   return table;
00366 }
00367 
00374 void
00375 _dbus_hash_table_unref (DBusHashTable *table)
00376 {
00377   table->refcount -= 1;
00378 
00379   if (table->refcount == 0)
00380     {
00381 #if 0
00382       DBusHashEntry *entry;
00383       DBusHashEntry *next;
00384       int i;
00385 
00386       /* Free the entries in the table. */
00387       for (i = 0; i < table->n_buckets; i++)
00388         {
00389           entry = table->buckets[i];
00390           while (entry != NULL)
00391             {
00392               next = entry->next;
00393 
00394               free_entry (table, entry);
00395               
00396               entry = next;
00397             }
00398         }
00399 #else
00400       DBusHashEntry *entry;
00401       int i;
00402 
00403       /* Free the entries in the table. */
00404       for (i = 0; i < table->n_buckets; i++)
00405         {
00406           entry = table->buckets[i];
00407           while (entry != NULL)
00408             {
00409               free_entry_data (table, entry);
00410               
00411               entry = entry->next;
00412             }
00413         }
00414       /* We can do this very quickly with memory pools ;-) */
00415       _dbus_mem_pool_free (table->entry_pool);
00416 #endif
00417       
00418       /* Free the bucket array, if it was dynamically allocated. */
00419       if (table->buckets != table->static_buckets)
00420         dbus_free (table->buckets);
00421 
00422       dbus_free (table);
00423     }
00424 }
00425 
00431 void
00432 _dbus_hash_table_remove_all (DBusHashTable *table)
00433 {
00434   DBusHashIter iter;
00435   _dbus_hash_iter_init (table, &iter);
00436   while (_dbus_hash_iter_next (&iter))
00437     {
00438       _dbus_hash_iter_remove_entry(&iter);
00439     }
00440 }
00441 
00442 static DBusHashEntry*
00443 alloc_entry (DBusHashTable *table)
00444 {
00445   DBusHashEntry *entry;
00446 
00447   entry = _dbus_mem_pool_alloc (table->entry_pool);
00448   
00449   return entry;
00450 }
00451 
00452 static void
00453 free_entry_data (DBusHashTable  *table,
00454                  DBusHashEntry  *entry)
00455 {
00456   if (table->free_key_function)
00457     (* table->free_key_function) (entry->key);
00458   if (table->free_value_function)
00459     (* table->free_value_function) (entry->value);
00460 }
00461 
00462 static void
00463 free_entry (DBusHashTable  *table,
00464             DBusHashEntry  *entry)
00465 {
00466   free_entry_data (table, entry);
00467   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00468 }
00469 
00470 static void
00471 remove_entry (DBusHashTable  *table,
00472               DBusHashEntry **bucket,
00473               DBusHashEntry  *entry)
00474 {
00475   _dbus_assert (table != NULL);
00476   _dbus_assert (bucket != NULL);
00477   _dbus_assert (*bucket != NULL);  
00478   _dbus_assert (entry != NULL);
00479   
00480   if (*bucket == entry)
00481     *bucket = entry->next;
00482   else
00483     {
00484       DBusHashEntry *prev;
00485       prev = *bucket;
00486 
00487       while (prev->next != entry)
00488         prev = prev->next;      
00489       
00490       _dbus_assert (prev != NULL);
00491 
00492       prev->next = entry->next;
00493     }
00494   
00495   table->n_entries -= 1;
00496   free_entry (table, entry);
00497 }
00498 
00530 void
00531 _dbus_hash_iter_init (DBusHashTable *table,
00532                       DBusHashIter  *iter)
00533 {
00534   DBusRealHashIter *real;
00535   
00536   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00537   
00538   real = (DBusRealHashIter*) iter;
00539 
00540   real->table = table;
00541   real->bucket = NULL;
00542   real->entry = NULL;
00543   real->next_entry = NULL;
00544   real->next_bucket = 0;
00545   real->n_entries_on_init = table->n_entries;
00546 }
00547 
00556 dbus_bool_t
00557 _dbus_hash_iter_next (DBusHashIter  *iter)
00558 {
00559   DBusRealHashIter *real;
00560   
00561   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00562   
00563   real = (DBusRealHashIter*) iter;
00564 
00565   /* if this assertion failed someone probably added hash entries
00566    * during iteration, which is bad.
00567    */
00568   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00569   
00570   /* Remember that real->entry may have been deleted */
00571   
00572   while (real->next_entry == NULL)
00573     {
00574       if (real->next_bucket >= real->table->n_buckets)
00575         {
00576           /* invalidate iter and return false */
00577           real->entry = NULL;
00578           real->table = NULL;
00579           real->bucket = NULL;
00580           return FALSE;
00581         }
00582 
00583       real->bucket = &(real->table->buckets[real->next_bucket]);
00584       real->next_entry = *(real->bucket);
00585       real->next_bucket += 1;
00586     }
00587 
00588   _dbus_assert (real->next_entry != NULL);
00589   _dbus_assert (real->bucket != NULL);
00590   
00591   real->entry = real->next_entry;
00592   real->next_entry = real->entry->next;
00593   
00594   return TRUE;
00595 }
00596 
00605 void
00606 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00607 {
00608   DBusRealHashIter *real;
00609 
00610   real = (DBusRealHashIter*) iter;
00611 
00612   _dbus_assert (real->table != NULL);
00613   _dbus_assert (real->entry != NULL);
00614   _dbus_assert (real->bucket != NULL);
00615   
00616   remove_entry (real->table, real->bucket, real->entry);
00617 
00618   real->entry = NULL; /* make it crash if you try to use this entry */
00619 }
00620 
00626 void*
00627 _dbus_hash_iter_get_value (DBusHashIter *iter)
00628 {
00629   DBusRealHashIter *real;
00630 
00631   real = (DBusRealHashIter*) iter;
00632 
00633   _dbus_assert (real->table != NULL);
00634   _dbus_assert (real->entry != NULL);
00635 
00636   return real->entry->value;
00637 }
00638 
00649 void
00650 _dbus_hash_iter_set_value (DBusHashIter *iter,
00651                            void         *value)
00652 {
00653   DBusRealHashIter *real;
00654 
00655   real = (DBusRealHashIter*) iter;
00656 
00657   _dbus_assert (real->table != NULL);
00658   _dbus_assert (real->entry != NULL);
00659 
00660   if (real->table->free_value_function && value != real->entry->value)    
00661     (* real->table->free_value_function) (real->entry->value);
00662   
00663   real->entry->value = value;
00664 }
00665 
00672 int
00673 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00674 {
00675   DBusRealHashIter *real;
00676 
00677   real = (DBusRealHashIter*) iter;
00678 
00679   _dbus_assert (real->table != NULL);
00680   _dbus_assert (real->entry != NULL);
00681 
00682   return _DBUS_POINTER_TO_INT (real->entry->key);
00683 }
00684 
00691 uintptr_t
00692 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
00693 {
00694   DBusRealHashIter *real;
00695 
00696   real = (DBusRealHashIter*) iter;
00697 
00698   _dbus_assert (real->table != NULL);
00699   _dbus_assert (real->entry != NULL);
00700 
00701   return (uintptr_t) real->entry->key;
00702 }
00703 
00709 const char*
00710 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00711 {
00712   DBusRealHashIter *real;
00713 
00714   real = (DBusRealHashIter*) iter;
00715 
00716   _dbus_assert (real->table != NULL);
00717   _dbus_assert (real->entry != NULL);
00718 
00719   return real->entry->key;
00720 }
00721 
00722 #ifdef DBUS_BUILD_TESTS
00723 
00728 const char*
00729 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
00730 {
00731   DBusRealHashIter *real;
00732 
00733   real = (DBusRealHashIter*) iter;
00734 
00735   _dbus_assert (real->table != NULL);
00736   _dbus_assert (real->entry != NULL);
00737 
00738   return real->entry->key;
00739 }
00740 #endif /* DBUS_BUILD_TESTS */
00741 
00773 dbus_bool_t
00774 _dbus_hash_iter_lookup (DBusHashTable *table,
00775                         void          *key,
00776                         dbus_bool_t    create_if_not_found,
00777                         DBusHashIter  *iter)
00778 {
00779   DBusRealHashIter *real;
00780   DBusHashEntry *entry;
00781   DBusHashEntry **bucket;
00782   
00783   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00784   
00785   real = (DBusRealHashIter*) iter;
00786 
00787   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00788 
00789   if (entry == NULL)
00790     return FALSE;
00791   
00792   real->table = table;
00793   real->bucket = bucket;
00794   real->entry = entry;
00795   real->next_entry = entry->next;
00796   real->next_bucket = (bucket - table->buckets) + 1;
00797   real->n_entries_on_init = table->n_entries; 
00798 
00799   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00800   
00801   return TRUE;
00802 }
00803 
00804 static void
00805 add_allocated_entry (DBusHashTable   *table,
00806                      DBusHashEntry   *entry,
00807                      unsigned int     idx,
00808                      void            *key,
00809                      DBusHashEntry ***bucket)
00810 {
00811   DBusHashEntry **b;  
00812   
00813   entry->key = key;
00814   
00815   b = &(table->buckets[idx]);
00816   entry->next = *b;
00817   *b = entry;
00818 
00819   if (bucket)
00820     *bucket = b;
00821   
00822   table->n_entries += 1;
00823 
00824   /* note we ONLY rebuild when ADDING - because you can iterate over a
00825    * table and remove entries safely.
00826    */
00827   if (table->n_entries >= table->hi_rebuild_size ||
00828       table->n_entries < table->lo_rebuild_size)
00829     rebuild_table (table);
00830 }
00831 
00832 static DBusHashEntry*
00833 add_entry (DBusHashTable        *table, 
00834            unsigned int          idx,
00835            void                 *key,
00836            DBusHashEntry      ***bucket,
00837            DBusPreallocatedHash *preallocated)
00838 {
00839   DBusHashEntry  *entry;
00840 
00841   if (preallocated == NULL)
00842     {
00843       entry = alloc_entry (table);
00844       if (entry == NULL)
00845         {
00846           if (bucket)
00847             *bucket = NULL;
00848           return NULL;
00849         }
00850     }
00851   else
00852     {
00853       entry = (DBusHashEntry*) preallocated;
00854     }
00855 
00856   add_allocated_entry (table, entry, idx, key, bucket);
00857 
00858   return entry;
00859 }
00860 
00861 /* This is g_str_hash from GLib which was
00862  * extensively discussed/tested/profiled
00863  */
00864 static unsigned int
00865 string_hash (const char *str)
00866 {
00867   const char *p = str;
00868   unsigned int h = *p;
00869 
00870   if (h)
00871     for (p += 1; *p != '\0'; p++)
00872       h = (h << 5) - h + *p;
00873 
00874   return h;
00875 }
00876 
00877 #ifdef DBUS_BUILD_TESTS
00878 /* This hashes a memory block with two nul-terminated strings
00879  * in it, used in dbus-object-registry.c at the moment.
00880  */
00881 static unsigned int
00882 two_strings_hash (const char *str)
00883 {
00884   const char *p = str;
00885   unsigned int h = *p;
00886 
00887   if (h)
00888     for (p += 1; *p != '\0'; p++)
00889       h = (h << 5) - h + *p;
00890 
00891   for (p += 1; *p != '\0'; p++)
00892     h = (h << 5) - h + *p;
00893   
00894   return h;
00895 }
00896 #endif /* DBUS_BUILD_TESTS */
00897 
00899 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00900 
00901 static DBusHashEntry*
00902 find_generic_function (DBusHashTable        *table,
00903                        void                 *key,
00904                        unsigned int          idx,
00905                        KeyCompareFunc        compare_func,
00906                        dbus_bool_t           create_if_not_found,
00907                        DBusHashEntry      ***bucket,
00908                        DBusPreallocatedHash *preallocated)
00909 {
00910   DBusHashEntry *entry;
00911 
00912   if (bucket)
00913     *bucket = NULL;
00914 
00915   /* Search all of the entries in this bucket. */
00916   entry = table->buckets[idx];
00917   while (entry != NULL)
00918     {
00919       if ((compare_func == NULL && key == entry->key) ||
00920           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00921         {
00922           if (bucket)
00923             *bucket = &(table->buckets[idx]);
00924 
00925           if (preallocated)
00926             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00927           
00928           return entry;
00929         }
00930       
00931       entry = entry->next;
00932     }
00933 
00934   if (create_if_not_found)
00935     entry = add_entry (table, idx, key, bucket, preallocated);
00936   else if (preallocated)
00937     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00938   
00939   return entry;
00940 }
00941 
00942 static DBusHashEntry*
00943 find_string_function (DBusHashTable        *table,
00944                       void                 *key,
00945                       dbus_bool_t           create_if_not_found,
00946                       DBusHashEntry      ***bucket,
00947                       DBusPreallocatedHash *preallocated)
00948 {
00949   unsigned int idx;
00950   
00951   idx = string_hash (key) & table->mask;
00952 
00953   return find_generic_function (table, key, idx,
00954                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00955                                 preallocated);
00956 }
00957 
00958 #ifdef DBUS_BUILD_TESTS
00959 static int
00960 two_strings_cmp (const char *a,
00961                  const char *b)
00962 {
00963   size_t len_a;
00964   size_t len_b;
00965   int res;
00966   
00967   res = strcmp (a, b);
00968   if (res != 0)
00969     return res;
00970 
00971   len_a = strlen (a);
00972   len_b = strlen (b);
00973 
00974   return strcmp (a + len_a + 1, b + len_b + 1);
00975 }
00976 #endif
00977 
00978 #ifdef DBUS_BUILD_TESTS
00979 static DBusHashEntry*
00980 find_two_strings_function (DBusHashTable        *table,
00981                            void                 *key,
00982                            dbus_bool_t           create_if_not_found,
00983                            DBusHashEntry      ***bucket,
00984                            DBusPreallocatedHash *preallocated)
00985 {
00986   unsigned int idx;
00987   
00988   idx = two_strings_hash (key) & table->mask;
00989 
00990   return find_generic_function (table, key, idx,
00991                                 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
00992                                 preallocated);
00993 }
00994 #endif /* DBUS_BUILD_TESTS */
00995 
00996 static DBusHashEntry*
00997 find_direct_function (DBusHashTable        *table,
00998                       void                 *key,
00999                       dbus_bool_t           create_if_not_found,
01000                       DBusHashEntry      ***bucket,
01001                       DBusPreallocatedHash *preallocated)
01002 {
01003   unsigned int idx;
01004   
01005   idx = RANDOM_INDEX (table, key) & table->mask;
01006 
01007 
01008   return find_generic_function (table, key, idx,
01009                                 NULL, create_if_not_found, bucket,
01010                                 preallocated);
01011 }
01012 
01013 static void
01014 rebuild_table (DBusHashTable *table)
01015 {
01016   int old_size;
01017   int new_buckets;
01018   DBusHashEntry **old_buckets;
01019   DBusHashEntry **old_chain;
01020   DBusHashEntry *entry;
01021   dbus_bool_t growing;
01022   
01023   /*
01024    * Allocate and initialize the new bucket array, and set up
01025    * hashing constants for new array size.
01026    */
01027 
01028   growing = table->n_entries >= table->hi_rebuild_size;
01029   
01030   old_size = table->n_buckets;
01031   old_buckets = table->buckets;
01032 
01033   if (growing)
01034     {
01035       /* overflow paranoia */
01036       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
01037           table->down_shift >= 0)
01038         new_buckets = table->n_buckets * 4;
01039       else
01040         return; /* can't grow anymore */
01041     }
01042   else
01043     {
01044       new_buckets = table->n_buckets / 4;
01045       if (new_buckets < DBUS_SMALL_HASH_TABLE)
01046         return; /* don't bother shrinking this far */
01047     }
01048 
01049   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
01050   if (table->buckets == NULL)
01051     {
01052       /* out of memory, yay - just don't reallocate, the table will
01053        * still work, albeit more slowly.
01054        */
01055       table->buckets = old_buckets;
01056       return;
01057     }
01058 
01059   table->n_buckets = new_buckets;
01060   
01061   if (growing)
01062     {
01063       table->lo_rebuild_size = table->hi_rebuild_size;
01064       table->hi_rebuild_size *= 4;
01065       
01066       table->down_shift -= 2;               /* keep 2 more high bits */
01067       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
01068     }
01069   else
01070     {
01071       table->hi_rebuild_size = table->lo_rebuild_size;
01072       table->lo_rebuild_size /= 4;
01073 
01074       table->down_shift += 2;         /* keep 2 fewer high bits */
01075       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
01076     }
01077 
01078 #if 0
01079   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
01080           growing ? "GROW" : "SHRINK",
01081           table->lo_rebuild_size,
01082           table->hi_rebuild_size,
01083           table->down_shift,
01084           table->mask);
01085 #endif
01086   
01087   _dbus_assert (table->lo_rebuild_size >= 0);
01088   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01089   _dbus_assert (table->mask != 0);
01090   /* the mask is essentially the max index */
01091   _dbus_assert (table->mask < table->n_buckets);
01092   
01093   /*
01094    * Rehash all of the existing entries into the new bucket array.
01095    */
01096 
01097   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01098     {
01099       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01100         {
01101           unsigned int idx;
01102           DBusHashEntry **bucket;
01103           
01104           *old_chain = entry->next;
01105           switch (table->key_type)
01106             {
01107             case DBUS_HASH_STRING:
01108               idx = string_hash (entry->key) & table->mask;
01109               break;
01110             case DBUS_HASH_TWO_STRINGS:
01111 #ifdef DBUS_BUILD_TESTS
01112               idx = two_strings_hash (entry->key) & table->mask;
01113 #else
01114               idx = 0;
01115               _dbus_assert_not_reached ("two-strings is not enabled");
01116 #endif
01117               break;
01118             case DBUS_HASH_INT:
01119             case DBUS_HASH_UINTPTR:
01120             case DBUS_HASH_POINTER:
01121               idx = RANDOM_INDEX (table, entry->key);
01122               break;
01123             default:
01124               idx = 0;
01125               _dbus_assert_not_reached ("Unknown hash table type");
01126               break;
01127             }
01128           
01129           bucket = &(table->buckets[idx]);
01130           entry->next = *bucket;
01131           *bucket = entry;
01132         }
01133     }
01134   
01135   /* Free the old bucket array, if it was dynamically allocated. */
01136 
01137   if (old_buckets != table->static_buckets)
01138     dbus_free (old_buckets);
01139 }
01140 
01150 void*
01151 _dbus_hash_table_lookup_string (DBusHashTable *table,
01152                                 const char    *key)
01153 {
01154   DBusHashEntry *entry;
01155 
01156   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01157   
01158   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01159 
01160   if (entry)
01161     return entry->value;
01162   else
01163     return NULL;
01164 }
01165 
01166 #ifdef DBUS_BUILD_TESTS
01167 
01176 void*
01177 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
01178                                      const char    *key)
01179 {
01180   DBusHashEntry *entry;
01181 
01182   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01183   
01184   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01185 
01186   if (entry)
01187     return entry->value;
01188   else
01189     return NULL;
01190 }
01191 #endif /* DBUS_BUILD_TESTS */
01192 
01202 void*
01203 _dbus_hash_table_lookup_int (DBusHashTable *table,
01204                              int            key)
01205 {
01206   DBusHashEntry *entry;
01207 
01208   _dbus_assert (table->key_type == DBUS_HASH_INT);
01209   
01210   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01211 
01212   if (entry)
01213     return entry->value;
01214   else
01215     return NULL;
01216 }
01217 
01218 #ifdef DBUS_BUILD_TESTS
01219 /* disabled since it's only used for testing */
01229 void*
01230 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01231                                  void          *key)
01232 {
01233   DBusHashEntry *entry;
01234 
01235   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01236   
01237   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01238 
01239   if (entry)
01240     return entry->value;
01241   else
01242     return NULL;
01243 }
01244 #endif /* DBUS_BUILD_TESTS */
01245 
01255 void*
01256 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
01257                                  uintptr_t      key)
01258 {
01259   DBusHashEntry *entry;
01260 
01261   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01262   
01263   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01264 
01265   if (entry)
01266     return entry->value;
01267   else
01268     return NULL;
01269 }
01270 
01279 dbus_bool_t
01280 _dbus_hash_table_remove_string (DBusHashTable *table,
01281                                 const char    *key)
01282 {
01283   DBusHashEntry *entry;
01284   DBusHashEntry **bucket;
01285   
01286   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01287   
01288   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01289 
01290   if (entry)
01291     {
01292       remove_entry (table, bucket, entry);
01293       return TRUE;
01294     }
01295   else
01296     return FALSE;
01297 }
01298 
01299 #ifdef DBUS_BUILD_TESTS
01300 
01308 dbus_bool_t
01309 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
01310                                      const char    *key)
01311 {
01312   DBusHashEntry *entry;
01313   DBusHashEntry **bucket;
01314   
01315   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01316   
01317   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01318 
01319   if (entry)
01320     {
01321       remove_entry (table, bucket, entry);
01322       return TRUE;
01323     }
01324   else
01325     return FALSE;
01326 }
01327 #endif /* DBUS_BUILD_TESTS */
01328 
01337 dbus_bool_t
01338 _dbus_hash_table_remove_int (DBusHashTable *table,
01339                              int            key)
01340 {
01341   DBusHashEntry *entry;
01342   DBusHashEntry **bucket;
01343   
01344   _dbus_assert (table->key_type == DBUS_HASH_INT);
01345   
01346   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01347   
01348   if (entry)
01349     {
01350       remove_entry (table, bucket, entry);
01351       return TRUE;
01352     }
01353   else
01354     return FALSE;
01355 }
01356 
01357 #ifdef DBUS_BUILD_TESTS
01358 /* disabled since it's only used for testing */
01367 dbus_bool_t
01368 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01369                                  void          *key)
01370 {
01371   DBusHashEntry *entry;
01372   DBusHashEntry **bucket;
01373   
01374   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01375   
01376   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01377   
01378   if (entry)
01379     {
01380       remove_entry (table, bucket, entry);
01381       return TRUE;
01382     }
01383   else
01384     return FALSE;
01385 }
01386 #endif /* DBUS_BUILD_TESTS */
01387 
01396 dbus_bool_t
01397 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
01398                                  uintptr_t      key)
01399 {
01400   DBusHashEntry *entry;
01401   DBusHashEntry **bucket;
01402   
01403   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01404   
01405   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01406   
01407   if (entry)
01408     {
01409       remove_entry (table, bucket, entry);
01410       return TRUE;
01411     }
01412   else
01413     return FALSE;
01414 }
01415 
01431 dbus_bool_t
01432 _dbus_hash_table_insert_string (DBusHashTable *table,
01433                                 char          *key,
01434                                 void          *value)
01435 {
01436   DBusPreallocatedHash *preallocated;
01437 
01438   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01439 
01440   preallocated = _dbus_hash_table_preallocate_entry (table);
01441   if (preallocated == NULL)
01442     return FALSE;
01443 
01444   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01445                                                key, value);
01446   
01447   return TRUE;
01448 }
01449 
01450 #ifdef DBUS_BUILD_TESTS
01451 
01466 dbus_bool_t
01467 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
01468                                      char          *key,
01469                                      void          *value)
01470 {
01471   DBusHashEntry *entry;
01472   
01473   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01474   
01475   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01476 
01477   if (entry == NULL)
01478     return FALSE; /* no memory */
01479 
01480   if (table->free_key_function && entry->key != key)
01481     (* table->free_key_function) (entry->key);
01482   
01483   if (table->free_value_function && entry->value != value)
01484     (* table->free_value_function) (entry->value);
01485   
01486   entry->key = key;
01487   entry->value = value;
01488 
01489   return TRUE;
01490 }
01491 #endif /* DBUS_BUILD_TESTS */
01492 
01508 dbus_bool_t
01509 _dbus_hash_table_insert_int (DBusHashTable *table,
01510                              int            key,
01511                              void          *value)
01512 {
01513   DBusHashEntry *entry;
01514 
01515   _dbus_assert (table->key_type == DBUS_HASH_INT);
01516   
01517   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01518 
01519   if (entry == NULL)
01520     return FALSE; /* no memory */
01521 
01522   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01523     (* table->free_key_function) (entry->key);
01524   
01525   if (table->free_value_function && entry->value != value)
01526     (* table->free_value_function) (entry->value);
01527   
01528   entry->key = _DBUS_INT_TO_POINTER (key);
01529   entry->value = value;
01530 
01531   return TRUE;
01532 }
01533 
01534 #ifdef DBUS_BUILD_TESTS
01535 /* disabled since it's only used for testing */
01551 dbus_bool_t
01552 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01553                                  void          *key,
01554                                  void          *value)
01555 {
01556   DBusHashEntry *entry;
01557 
01558   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01559   
01560   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01561 
01562   if (entry == NULL)
01563     return FALSE; /* no memory */
01564 
01565   if (table->free_key_function && entry->key != key)
01566     (* table->free_key_function) (entry->key);
01567   
01568   if (table->free_value_function && entry->value != value)
01569     (* table->free_value_function) (entry->value);
01570   
01571   entry->key = key;
01572   entry->value = value;
01573 
01574   return TRUE;
01575 }
01576 #endif /* DBUS_BUILD_TESTS */
01577 
01593 dbus_bool_t
01594 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
01595                                  uintptr_t      key,
01596                                  void          *value)
01597 {
01598   DBusHashEntry *entry;
01599 
01600   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01601   
01602   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01603 
01604   if (entry == NULL)
01605     return FALSE; /* no memory */
01606 
01607   if (table->free_key_function && entry->key != (void*) key)
01608     (* table->free_key_function) (entry->key);
01609   
01610   if (table->free_value_function && entry->value != value)
01611     (* table->free_value_function) (entry->value);
01612   
01613   entry->key = (void*) key;
01614   entry->value = value;
01615 
01616   return TRUE;
01617 }
01618 
01626 DBusPreallocatedHash*
01627 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01628 {
01629   DBusHashEntry *entry;
01630   
01631   entry = alloc_entry (table);
01632 
01633   return (DBusPreallocatedHash*) entry;
01634 }
01635 
01643 void
01644 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01645                                           DBusPreallocatedHash *preallocated)
01646 {
01647   DBusHashEntry *entry;
01648 
01649   _dbus_assert (preallocated != NULL);
01650   
01651   entry = (DBusHashEntry*) preallocated;
01652   
01653   /* Don't use free_entry(), since this entry has no key/data */
01654   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01655 }
01656 
01670 void
01671 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01672                                              DBusPreallocatedHash *preallocated,
01673                                              char                 *key,
01674                                              void                 *value)
01675 {
01676   DBusHashEntry *entry;
01677 
01678   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01679   _dbus_assert (preallocated != NULL);
01680   
01681   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01682 
01683   _dbus_assert (entry != NULL);
01684   
01685   if (table->free_key_function && entry->key != key)
01686     (* table->free_key_function) (entry->key);
01687 
01688   if (table->free_value_function && entry->value != value)
01689     (* table->free_value_function) (entry->value);
01690       
01691   entry->key = key;
01692   entry->value = value;
01693 }
01694 
01701 int
01702 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01703 {
01704   return table->n_entries;
01705 }
01706 
01709 #ifdef DBUS_BUILD_TESTS
01710 #include "dbus-test.h"
01711 #include <stdio.h>
01712 
01713 /* If you're wondering why the hash table test takes
01714  * forever to run, it's because we call this function
01715  * in inner loops thus making things quadratic.
01716  */
01717 static int
01718 count_entries (DBusHashTable *table)
01719 {
01720   DBusHashIter iter;
01721   int count;
01722 
01723   count = 0;
01724   _dbus_hash_iter_init (table, &iter);
01725   while (_dbus_hash_iter_next (&iter))
01726     ++count;
01727 
01728   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01729   
01730   return count;
01731 }
01732 
01733 /* Copy the foo\0bar\0 double string thing */
01734 static char*
01735 _dbus_strdup2 (const char *str)
01736 {
01737   size_t len;
01738   char *copy;
01739   
01740   if (str == NULL)
01741     return NULL;
01742   
01743   len = strlen (str);
01744   len += strlen ((str + len + 1));
01745 
01746   copy = dbus_malloc (len + 2);
01747   if (copy == NULL)
01748     return NULL;
01749 
01750   memcpy (copy, str, len + 2);
01751   
01752   return copy;
01753 }
01754 
01760 dbus_bool_t
01761 _dbus_hash_test (void)
01762 {
01763   int i;
01764   DBusHashTable *table1;
01765   DBusHashTable *table2;
01766   DBusHashTable *table3;
01767   DBusHashTable *table4;
01768   DBusHashIter iter;
01769 #define N_HASH_KEYS 5000
01770   char **keys;
01771   dbus_bool_t ret = FALSE;
01772 
01773   keys = dbus_new (char *, N_HASH_KEYS);
01774   if (keys == NULL)
01775     _dbus_assert_not_reached ("no memory");
01776 
01777   for (i = 0; i < N_HASH_KEYS; i++)
01778     {
01779       keys[i] = dbus_malloc (128);
01780 
01781       if (keys[i] == NULL)
01782         _dbus_assert_not_reached ("no memory");
01783     }
01784 
01785   printf ("Computing test hash keys...\n");
01786   i = 0;
01787   while (i < N_HASH_KEYS)
01788     {
01789       int len;
01790 
01791       /* all the hash keys are TWO_STRINGS, but
01792        * then we can also use those as regular strings.
01793        */
01794       
01795       len = sprintf (keys[i], "Hash key %d", i);
01796       sprintf (keys[i] + len + 1, "Two string %d", i);
01797       _dbus_assert (*(keys[i] + len) == '\0');
01798       _dbus_assert (*(keys[i] + len + 1) != '\0');
01799       ++i;
01800     }
01801   printf ("... done.\n");
01802   
01803   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01804                                  dbus_free, dbus_free);
01805   if (table1 == NULL)
01806     goto out;
01807 
01808   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01809                                  NULL, dbus_free);
01810   if (table2 == NULL)
01811     goto out;
01812 
01813   table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
01814                                  NULL, dbus_free);
01815   if (table3 == NULL)
01816     goto out;
01817 
01818   table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
01819                                  dbus_free, dbus_free);
01820   if (table4 == NULL)
01821     goto out;
01822 
01823   
01824   /* Insert and remove a bunch of stuff, counting the table in between
01825    * to be sure it's not broken and that iteration works
01826    */
01827   i = 0;
01828   while (i < 3000)
01829     {
01830       void *value;
01831       char *key;
01832 
01833       key = _dbus_strdup (keys[i]);
01834       if (key == NULL)
01835         goto out;
01836       value = _dbus_strdup ("Value!");
01837       if (value == NULL)
01838         goto out;
01839       
01840       if (!_dbus_hash_table_insert_string (table1,
01841                                            key, value))
01842         goto out;
01843 
01844       value = _dbus_strdup (keys[i]);
01845       if (value == NULL)
01846         goto out;
01847       
01848       if (!_dbus_hash_table_insert_int (table2,
01849                                         i, value))
01850         goto out;
01851 
01852       value = _dbus_strdup (keys[i]);
01853       if (value == NULL)
01854         goto out;
01855       
01856       if (!_dbus_hash_table_insert_uintptr (table3,
01857                                           i, value))
01858         goto out;
01859 
01860       key = _dbus_strdup2 (keys[i]);
01861       if (key == NULL)
01862         goto out;
01863       value = _dbus_strdup ("Value!");
01864       if (value == NULL)
01865         goto out;
01866       
01867       if (!_dbus_hash_table_insert_two_strings (table4,
01868                                                 key, value))
01869         goto out;
01870       
01871       _dbus_assert (count_entries (table1) == i + 1);
01872       _dbus_assert (count_entries (table2) == i + 1);
01873       _dbus_assert (count_entries (table3) == i + 1);
01874       _dbus_assert (count_entries (table4) == i + 1);
01875 
01876       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01877       _dbus_assert (value != NULL);
01878       _dbus_assert (strcmp (value, "Value!") == 0);
01879 
01880       value = _dbus_hash_table_lookup_int (table2, i);
01881       _dbus_assert (value != NULL);
01882       _dbus_assert (strcmp (value, keys[i]) == 0);
01883 
01884       value = _dbus_hash_table_lookup_uintptr (table3, i);
01885       _dbus_assert (value != NULL);
01886       _dbus_assert (strcmp (value, keys[i]) == 0);
01887 
01888       value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01889       _dbus_assert (value != NULL);
01890       _dbus_assert (strcmp (value, "Value!") == 0);
01891       
01892       ++i;
01893     }
01894 
01895   --i;
01896   while (i >= 0)
01897     {
01898       _dbus_hash_table_remove_string (table1,
01899                                       keys[i]);
01900 
01901       _dbus_hash_table_remove_int (table2, i);
01902 
01903       _dbus_hash_table_remove_uintptr (table3, i);
01904 
01905       _dbus_hash_table_remove_two_strings (table4,
01906                                            keys[i]);
01907       
01908       _dbus_assert (count_entries (table1) == i);
01909       _dbus_assert (count_entries (table2) == i);
01910       _dbus_assert (count_entries (table3) == i);
01911       _dbus_assert (count_entries (table4) == i);
01912 
01913       --i;
01914     }
01915 
01916   _dbus_hash_table_ref (table1);
01917   _dbus_hash_table_ref (table2);
01918   _dbus_hash_table_ref (table3);
01919   _dbus_hash_table_ref (table4);
01920   _dbus_hash_table_unref (table1);
01921   _dbus_hash_table_unref (table2);
01922   _dbus_hash_table_unref (table3);
01923   _dbus_hash_table_unref (table4);
01924   _dbus_hash_table_unref (table1);
01925   _dbus_hash_table_unref (table2);
01926   _dbus_hash_table_unref (table3);
01927   _dbus_hash_table_unref (table4);
01928   table3 = NULL;
01929 
01930   /* Insert a bunch of stuff then check
01931    * that iteration works correctly (finds the right
01932    * values, iter_set_value works, etc.)
01933    */
01934   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01935                                  dbus_free, dbus_free);
01936   if (table1 == NULL)
01937     goto out;
01938   
01939   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01940                                  NULL, dbus_free);
01941   if (table2 == NULL)
01942     goto out;
01943   
01944   i = 0;
01945   while (i < 5000)
01946     {
01947       char *key;
01948       void *value;      
01949       
01950       key = _dbus_strdup (keys[i]);
01951       if (key == NULL)
01952         goto out;
01953       value = _dbus_strdup ("Value!");
01954       if (value == NULL)
01955         goto out;
01956       
01957       if (!_dbus_hash_table_insert_string (table1,
01958                                            key, value))
01959         goto out;
01960 
01961       value = _dbus_strdup (keys[i]);
01962       if (value == NULL)
01963         goto out;
01964       
01965       if (!_dbus_hash_table_insert_int (table2,
01966                                         i, value))
01967         goto out;
01968       
01969       _dbus_assert (count_entries (table1) == i + 1);
01970       _dbus_assert (count_entries (table2) == i + 1);
01971       
01972       ++i;
01973     }
01974 
01975   _dbus_hash_iter_init (table1, &iter);
01976   while (_dbus_hash_iter_next (&iter))
01977     {
01978       const char *key;
01979       void *value;
01980 
01981       key = _dbus_hash_iter_get_string_key (&iter);
01982       value = _dbus_hash_iter_get_value (&iter);
01983 
01984       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01985 
01986       value = _dbus_strdup ("Different value!");
01987       if (value == NULL)
01988         goto out;
01989       
01990       _dbus_hash_iter_set_value (&iter, value);
01991 
01992       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01993     }
01994   
01995   _dbus_hash_iter_init (table1, &iter);
01996   while (_dbus_hash_iter_next (&iter))
01997     {
01998       _dbus_hash_iter_remove_entry (&iter);
01999       _dbus_assert (count_entries (table1) == i - 1);
02000       --i;
02001     }
02002 
02003   _dbus_hash_iter_init (table2, &iter);
02004   while (_dbus_hash_iter_next (&iter))
02005     {
02006       int key;
02007       void *value;
02008 
02009       key = _dbus_hash_iter_get_int_key (&iter);
02010       value = _dbus_hash_iter_get_value (&iter);
02011 
02012       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02013 
02014       value = _dbus_strdup ("Different value!");
02015       if (value == NULL)
02016         goto out;
02017       
02018       _dbus_hash_iter_set_value (&iter, value);
02019 
02020       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02021     }
02022 
02023   i = count_entries (table2);
02024   _dbus_hash_iter_init (table2, &iter);
02025   while (_dbus_hash_iter_next (&iter))
02026     {
02027       _dbus_hash_iter_remove_entry (&iter);
02028       _dbus_assert (count_entries (table2) + 1 == i);
02029       --i;
02030     }
02031 
02032   /* add/remove interleaved, to check that we grow/shrink the table
02033    * appropriately
02034    */
02035   i = 0;
02036   while (i < 1000)
02037     {
02038       char *key;
02039       void *value;
02040             
02041       key = _dbus_strdup (keys[i]);
02042       if (key == NULL)
02043         goto out;
02044 
02045       value = _dbus_strdup ("Value!");
02046       if (value == NULL)
02047         goto out;
02048       
02049       if (!_dbus_hash_table_insert_string (table1,
02050                                            key, value))
02051         goto out;
02052       
02053       ++i;
02054     }
02055 
02056   --i;
02057   while (i >= 0)
02058     {
02059       char *key;
02060       void *value;      
02061       
02062       key = _dbus_strdup (keys[i]);
02063       if (key == NULL)
02064         goto out;
02065       value = _dbus_strdup ("Value!");
02066       if (value == NULL)
02067         goto out;
02068 
02069       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02070         goto out;
02071       
02072       if (!_dbus_hash_table_insert_string (table1,
02073                                            key, value))
02074         goto out;
02075 
02076       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02077         goto out;
02078       
02079       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
02080       
02081       --i;
02082     }
02083 
02084   /* nuke these tables */
02085   _dbus_hash_table_unref (table1);
02086   _dbus_hash_table_unref (table2);
02087 
02088 
02089   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
02090    * be sure that interface works.
02091    */
02092   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
02093                                  dbus_free, dbus_free);
02094   if (table1 == NULL)
02095     goto out;
02096   
02097   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
02098                                  NULL, dbus_free);
02099   if (table2 == NULL)
02100     goto out;
02101   
02102   i = 0;
02103   while (i < 3000)
02104     {
02105       void *value;
02106       char *key;
02107 
02108       key = _dbus_strdup (keys[i]);
02109       if (key == NULL)
02110         goto out;
02111       value = _dbus_strdup ("Value!");
02112       if (value == NULL)
02113         goto out;
02114       
02115       if (!_dbus_hash_iter_lookup (table1,
02116                                    key, TRUE, &iter))
02117         goto out;
02118       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02119       _dbus_hash_iter_set_value (&iter, value);
02120 
02121       value = _dbus_strdup (keys[i]);
02122       if (value == NULL)
02123         goto out;
02124 
02125       if (!_dbus_hash_iter_lookup (table2,
02126                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
02127         goto out;
02128       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02129       _dbus_hash_iter_set_value (&iter, value); 
02130       
02131       _dbus_assert (count_entries (table1) == i + 1);
02132       _dbus_assert (count_entries (table2) == i + 1);
02133 
02134       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02135         goto out;
02136       
02137       value = _dbus_hash_iter_get_value (&iter);
02138       _dbus_assert (value != NULL);
02139       _dbus_assert (strcmp (value, "Value!") == 0);
02140 
02141       /* Iterate just to be sure it works, though
02142        * it's a stupid thing to do
02143        */
02144       while (_dbus_hash_iter_next (&iter))
02145         ;
02146       
02147       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02148         goto out;
02149 
02150       value = _dbus_hash_iter_get_value (&iter);
02151       _dbus_assert (value != NULL);
02152       _dbus_assert (strcmp (value, keys[i]) == 0);
02153 
02154       /* Iterate just to be sure it works, though
02155        * it's a stupid thing to do
02156        */
02157       while (_dbus_hash_iter_next (&iter))
02158         ;
02159       
02160       ++i;
02161     }
02162 
02163   --i;
02164   while (i >= 0)
02165     {
02166       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02167         _dbus_assert_not_reached ("hash entry should have existed");
02168       _dbus_hash_iter_remove_entry (&iter);
02169       
02170       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02171         _dbus_assert_not_reached ("hash entry should have existed");
02172       _dbus_hash_iter_remove_entry (&iter);
02173 
02174       _dbus_assert (count_entries (table1) == i);
02175       _dbus_assert (count_entries (table2) == i);
02176 
02177       --i;
02178     }
02179 
02180   _dbus_hash_table_unref (table1);
02181   _dbus_hash_table_unref (table2);
02182 
02183   ret = TRUE;
02184 
02185  out:
02186   for (i = 0; i < N_HASH_KEYS; i++)
02187     dbus_free (keys[i]);
02188 
02189   dbus_free (keys);
02190   
02191   return ret;
02192 }
02193 
02194 #endif /* DBUS_BUILD_TESTS */