D-Bus  1.4.18
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 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
00226 
00227 static DBusHashEntry* find_direct_function      (DBusHashTable          *table,
00228                                                  void                   *key,
00229                                                  dbus_bool_t             create_if_not_found,
00230                                                  DBusHashEntry        ***bucket,
00231                                                  DBusPreallocatedHash   *preallocated);
00232 static DBusHashEntry* find_string_function      (DBusHashTable          *table,
00233                                                  void                   *key,
00234                                                  dbus_bool_t             create_if_not_found,
00235                                                  DBusHashEntry        ***bucket,
00236                                                  DBusPreallocatedHash   *preallocated);
00237 #ifdef DBUS_BUILD_TESTS
00238 static DBusHashEntry* find_two_strings_function (DBusHashTable          *table,
00239                                                  void                   *key,
00240                                                  dbus_bool_t             create_if_not_found,
00241                                                  DBusHashEntry        ***bucket,
00242                                                  DBusPreallocatedHash   *preallocated);
00243 #endif
00244 static unsigned int   string_hash               (const char             *str);
00245 #ifdef DBUS_BUILD_TESTS
00246 static unsigned int   two_strings_hash          (const char             *str);
00247 #endif
00248 static void           rebuild_table             (DBusHashTable          *table);
00249 static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
00250 static void           remove_entry              (DBusHashTable          *table,
00251                                                  DBusHashEntry         **bucket,
00252                                                  DBusHashEntry          *entry);
00253 static void           free_entry                (DBusHashTable          *table,
00254                                                  DBusHashEntry          *entry);
00255 static void           free_entry_data           (DBusHashTable          *table,
00256                                                  DBusHashEntry          *entry);
00257 
00258 
00294 DBusHashTable*
00295 _dbus_hash_table_new (DBusHashType     type,
00296                       DBusFreeFunction key_free_function,
00297                       DBusFreeFunction value_free_function)
00298 {
00299   DBusHashTable *table;
00300   DBusMemPool *entry_pool;
00301   
00302   table = dbus_new0 (DBusHashTable, 1);
00303   if (table == NULL)
00304     return NULL;
00305 
00306   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00307   if (entry_pool == NULL)
00308     {
00309       dbus_free (table);
00310       return NULL;
00311     }
00312   
00313   table->refcount = 1;
00314   table->entry_pool = entry_pool;
00315   
00316   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00317   
00318   table->buckets = table->static_buckets;  
00319   table->n_buckets = DBUS_SMALL_HASH_TABLE;
00320   table->n_entries = 0;
00321   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00322   table->lo_rebuild_size = 0;
00323   table->down_shift = 28;
00324   table->mask = 3;
00325   table->key_type = type;
00326 
00327   _dbus_assert (table->mask < table->n_buckets);
00328   
00329   switch (table->key_type)
00330     {
00331     case DBUS_HASH_INT:
00332     case DBUS_HASH_POINTER:
00333     case DBUS_HASH_UINTPTR:
00334       table->find_function = find_direct_function;
00335       break;
00336     case DBUS_HASH_STRING:
00337       table->find_function = find_string_function;
00338       break;
00339     case DBUS_HASH_TWO_STRINGS:
00340 #ifdef DBUS_BUILD_TESTS
00341       table->find_function = find_two_strings_function;
00342 #endif
00343       break;
00344     default:
00345       _dbus_assert_not_reached ("Unknown hash table type");
00346       break;
00347     }
00348 
00349   table->free_key_function = key_free_function;
00350   table->free_value_function = value_free_function;
00351 
00352   return table;
00353 }
00354 
00355 
00362 DBusHashTable *
00363 _dbus_hash_table_ref (DBusHashTable *table)
00364 {
00365   table->refcount += 1;
00366   
00367   return table;
00368 }
00369 
00376 void
00377 _dbus_hash_table_unref (DBusHashTable *table)
00378 {
00379   table->refcount -= 1;
00380 
00381   if (table->refcount == 0)
00382     {
00383 #if 0
00384       DBusHashEntry *entry;
00385       DBusHashEntry *next;
00386       int i;
00387 
00388       /* Free the entries in the table. */
00389       for (i = 0; i < table->n_buckets; i++)
00390         {
00391           entry = table->buckets[i];
00392           while (entry != NULL)
00393             {
00394               next = entry->next;
00395 
00396               free_entry (table, entry);
00397               
00398               entry = next;
00399             }
00400         }
00401 #else
00402       DBusHashEntry *entry;
00403       int i;
00404 
00405       /* Free the entries in the table. */
00406       for (i = 0; i < table->n_buckets; i++)
00407         {
00408           entry = table->buckets[i];
00409           while (entry != NULL)
00410             {
00411               free_entry_data (table, entry);
00412               
00413               entry = entry->next;
00414             }
00415         }
00416       /* We can do this very quickly with memory pools ;-) */
00417       _dbus_mem_pool_free (table->entry_pool);
00418 #endif
00419       
00420       /* Free the bucket array, if it was dynamically allocated. */
00421       if (table->buckets != table->static_buckets)
00422         dbus_free (table->buckets);
00423 
00424       dbus_free (table);
00425     }
00426 }
00427 
00433 void
00434 _dbus_hash_table_remove_all (DBusHashTable *table)
00435 {
00436   DBusHashIter iter;
00437   _dbus_hash_iter_init (table, &iter);
00438   while (_dbus_hash_iter_next (&iter))
00439     {
00440       _dbus_hash_iter_remove_entry(&iter);
00441     }
00442 }
00443 
00444 static DBusHashEntry*
00445 alloc_entry (DBusHashTable *table)
00446 {
00447   DBusHashEntry *entry;
00448 
00449   entry = _dbus_mem_pool_alloc (table->entry_pool);
00450   
00451   return entry;
00452 }
00453 
00454 static void
00455 free_entry_data (DBusHashTable  *table,
00456                  DBusHashEntry  *entry)
00457 {
00458   if (table->free_key_function)
00459     (* table->free_key_function) (entry->key);
00460   if (table->free_value_function)
00461     (* table->free_value_function) (entry->value);
00462 }
00463 
00464 static void
00465 free_entry (DBusHashTable  *table,
00466             DBusHashEntry  *entry)
00467 {
00468   free_entry_data (table, entry);
00469   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00470 }
00471 
00472 static void
00473 remove_entry (DBusHashTable  *table,
00474               DBusHashEntry **bucket,
00475               DBusHashEntry  *entry)
00476 {
00477   _dbus_assert (table != NULL);
00478   _dbus_assert (bucket != NULL);
00479   _dbus_assert (*bucket != NULL);  
00480   _dbus_assert (entry != NULL);
00481   
00482   if (*bucket == entry)
00483     *bucket = entry->next;
00484   else
00485     {
00486       DBusHashEntry *prev;
00487       prev = *bucket;
00488 
00489       while (prev->next != entry)
00490         prev = prev->next;      
00491       
00492       _dbus_assert (prev != NULL);
00493 
00494       prev->next = entry->next;
00495     }
00496   
00497   table->n_entries -= 1;
00498   free_entry (table, entry);
00499 }
00500 
00532 void
00533 _dbus_hash_iter_init (DBusHashTable *table,
00534                       DBusHashIter  *iter)
00535 {
00536   DBusRealHashIter *real;
00537   
00538   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00539   
00540   real = (DBusRealHashIter*) iter;
00541 
00542   real->table = table;
00543   real->bucket = NULL;
00544   real->entry = NULL;
00545   real->next_entry = NULL;
00546   real->next_bucket = 0;
00547   real->n_entries_on_init = table->n_entries;
00548 }
00549 
00558 dbus_bool_t
00559 _dbus_hash_iter_next (DBusHashIter  *iter)
00560 {
00561   DBusRealHashIter *real;
00562   
00563   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00564   
00565   real = (DBusRealHashIter*) iter;
00566 
00567   /* if this assertion failed someone probably added hash entries
00568    * during iteration, which is bad.
00569    */
00570   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00571   
00572   /* Remember that real->entry may have been deleted */
00573   
00574   while (real->next_entry == NULL)
00575     {
00576       if (real->next_bucket >= real->table->n_buckets)
00577         {
00578           /* invalidate iter and return false */
00579           real->entry = NULL;
00580           real->table = NULL;
00581           real->bucket = NULL;
00582           return FALSE;
00583         }
00584 
00585       real->bucket = &(real->table->buckets[real->next_bucket]);
00586       real->next_entry = *(real->bucket);
00587       real->next_bucket += 1;
00588     }
00589 
00590   _dbus_assert (real->next_entry != NULL);
00591   _dbus_assert (real->bucket != NULL);
00592   
00593   real->entry = real->next_entry;
00594   real->next_entry = real->entry->next;
00595   
00596   return TRUE;
00597 }
00598 
00607 void
00608 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00609 {
00610   DBusRealHashIter *real;
00611 
00612   real = (DBusRealHashIter*) iter;
00613 
00614   _dbus_assert (real->table != NULL);
00615   _dbus_assert (real->entry != NULL);
00616   _dbus_assert (real->bucket != NULL);
00617   
00618   remove_entry (real->table, real->bucket, real->entry);
00619 
00620   real->entry = NULL; /* make it crash if you try to use this entry */
00621 }
00622 
00628 void*
00629 _dbus_hash_iter_get_value (DBusHashIter *iter)
00630 {
00631   DBusRealHashIter *real;
00632 
00633   real = (DBusRealHashIter*) iter;
00634 
00635   _dbus_assert (real->table != NULL);
00636   _dbus_assert (real->entry != NULL);
00637 
00638   return real->entry->value;
00639 }
00640 
00651 void
00652 _dbus_hash_iter_set_value (DBusHashIter *iter,
00653                            void         *value)
00654 {
00655   DBusRealHashIter *real;
00656 
00657   real = (DBusRealHashIter*) iter;
00658 
00659   _dbus_assert (real->table != NULL);
00660   _dbus_assert (real->entry != NULL);
00661 
00662   if (real->table->free_value_function && value != real->entry->value)    
00663     (* real->table->free_value_function) (real->entry->value);
00664   
00665   real->entry->value = value;
00666 }
00667 
00674 int
00675 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00676 {
00677   DBusRealHashIter *real;
00678 
00679   real = (DBusRealHashIter*) iter;
00680 
00681   _dbus_assert (real->table != NULL);
00682   _dbus_assert (real->entry != NULL);
00683 
00684   return _DBUS_POINTER_TO_INT (real->entry->key);
00685 }
00686 
00693 uintptr_t
00694 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
00695 {
00696   DBusRealHashIter *real;
00697 
00698   real = (DBusRealHashIter*) iter;
00699 
00700   _dbus_assert (real->table != NULL);
00701   _dbus_assert (real->entry != NULL);
00702 
00703   return (uintptr_t) real->entry->key;
00704 }
00705 
00711 const char*
00712 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00713 {
00714   DBusRealHashIter *real;
00715 
00716   real = (DBusRealHashIter*) iter;
00717 
00718   _dbus_assert (real->table != NULL);
00719   _dbus_assert (real->entry != NULL);
00720 
00721   return real->entry->key;
00722 }
00723 
00724 #ifdef DBUS_BUILD_TESTS
00725 
00730 const char*
00731 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
00732 {
00733   DBusRealHashIter *real;
00734 
00735   real = (DBusRealHashIter*) iter;
00736 
00737   _dbus_assert (real->table != NULL);
00738   _dbus_assert (real->entry != NULL);
00739 
00740   return real->entry->key;
00741 }
00742 #endif /* DBUS_BUILD_TESTS */
00743 
00775 dbus_bool_t
00776 _dbus_hash_iter_lookup (DBusHashTable *table,
00777                         void          *key,
00778                         dbus_bool_t    create_if_not_found,
00779                         DBusHashIter  *iter)
00780 {
00781   DBusRealHashIter *real;
00782   DBusHashEntry *entry;
00783   DBusHashEntry **bucket;
00784   
00785   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00786   
00787   real = (DBusRealHashIter*) iter;
00788 
00789   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00790 
00791   if (entry == NULL)
00792     return FALSE;
00793   
00794   real->table = table;
00795   real->bucket = bucket;
00796   real->entry = entry;
00797   real->next_entry = entry->next;
00798   real->next_bucket = (bucket - table->buckets) + 1;
00799   real->n_entries_on_init = table->n_entries; 
00800 
00801   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00802   
00803   return TRUE;
00804 }
00805 
00806 static void
00807 add_allocated_entry (DBusHashTable   *table,
00808                      DBusHashEntry   *entry,
00809                      unsigned int     idx,
00810                      void            *key,
00811                      DBusHashEntry ***bucket)
00812 {
00813   DBusHashEntry **b;  
00814   
00815   entry->key = key;
00816   
00817   b = &(table->buckets[idx]);
00818   entry->next = *b;
00819   *b = entry;
00820 
00821   if (bucket)
00822     *bucket = b;
00823   
00824   table->n_entries += 1;
00825 
00826   /* note we ONLY rebuild when ADDING - because you can iterate over a
00827    * table and remove entries safely.
00828    */
00829   if (table->n_entries >= table->hi_rebuild_size ||
00830       table->n_entries < table->lo_rebuild_size)
00831     rebuild_table (table);
00832 }
00833 
00834 static DBusHashEntry*
00835 add_entry (DBusHashTable        *table, 
00836            unsigned int          idx,
00837            void                 *key,
00838            DBusHashEntry      ***bucket,
00839            DBusPreallocatedHash *preallocated)
00840 {
00841   DBusHashEntry  *entry;
00842 
00843   if (preallocated == NULL)
00844     {
00845       entry = alloc_entry (table);
00846       if (entry == NULL)
00847         {
00848           if (bucket)
00849             *bucket = NULL;
00850           return NULL;
00851         }
00852     }
00853   else
00854     {
00855       entry = (DBusHashEntry*) preallocated;
00856     }
00857 
00858   add_allocated_entry (table, entry, idx, key, bucket);
00859 
00860   return entry;
00861 }
00862 
00863 /* This is g_str_hash from GLib which was
00864  * extensively discussed/tested/profiled
00865  */
00866 static unsigned int
00867 string_hash (const char *str)
00868 {
00869   const char *p = str;
00870   unsigned int h = *p;
00871 
00872   if (h)
00873     for (p += 1; *p != '\0'; p++)
00874       h = (h << 5) - h + *p;
00875 
00876   return h;
00877 }
00878 
00879 #ifdef DBUS_BUILD_TESTS
00880 /* This hashes a memory block with two nul-terminated strings
00881  * in it, used in dbus-object-registry.c at the moment.
00882  */
00883 static unsigned int
00884 two_strings_hash (const char *str)
00885 {
00886   const char *p = str;
00887   unsigned int h = *p;
00888 
00889   if (h)
00890     for (p += 1; *p != '\0'; p++)
00891       h = (h << 5) - h + *p;
00892 
00893   for (p += 1; *p != '\0'; p++)
00894     h = (h << 5) - h + *p;
00895   
00896   return h;
00897 }
00898 #endif /* DBUS_BUILD_TESTS */
00899 
00901 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00902 
00903 static DBusHashEntry*
00904 find_generic_function (DBusHashTable        *table,
00905                        void                 *key,
00906                        unsigned int          idx,
00907                        KeyCompareFunc        compare_func,
00908                        dbus_bool_t           create_if_not_found,
00909                        DBusHashEntry      ***bucket,
00910                        DBusPreallocatedHash *preallocated)
00911 {
00912   DBusHashEntry *entry;
00913 
00914   if (bucket)
00915     *bucket = NULL;
00916 
00917   /* Search all of the entries in this bucket. */
00918   entry = table->buckets[idx];
00919   while (entry != NULL)
00920     {
00921       if ((compare_func == NULL && key == entry->key) ||
00922           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00923         {
00924           if (bucket)
00925             *bucket = &(table->buckets[idx]);
00926 
00927           if (preallocated)
00928             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00929           
00930           return entry;
00931         }
00932       
00933       entry = entry->next;
00934     }
00935 
00936   if (create_if_not_found)
00937     entry = add_entry (table, idx, key, bucket, preallocated);
00938   else if (preallocated)
00939     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00940   
00941   return entry;
00942 }
00943 
00944 static DBusHashEntry*
00945 find_string_function (DBusHashTable        *table,
00946                       void                 *key,
00947                       dbus_bool_t           create_if_not_found,
00948                       DBusHashEntry      ***bucket,
00949                       DBusPreallocatedHash *preallocated)
00950 {
00951   unsigned int idx;
00952   
00953   idx = string_hash (key) & table->mask;
00954 
00955   return find_generic_function (table, key, idx,
00956                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00957                                 preallocated);
00958 }
00959 
00960 #ifdef DBUS_BUILD_TESTS
00961 static int
00962 two_strings_cmp (const char *a,
00963                  const char *b)
00964 {
00965   size_t len_a;
00966   size_t len_b;
00967   int res;
00968   
00969   res = strcmp (a, b);
00970   if (res != 0)
00971     return res;
00972 
00973   len_a = strlen (a);
00974   len_b = strlen (b);
00975 
00976   return strcmp (a + len_a + 1, b + len_b + 1);
00977 }
00978 #endif
00979 
00980 #ifdef DBUS_BUILD_TESTS
00981 static DBusHashEntry*
00982 find_two_strings_function (DBusHashTable        *table,
00983                            void                 *key,
00984                            dbus_bool_t           create_if_not_found,
00985                            DBusHashEntry      ***bucket,
00986                            DBusPreallocatedHash *preallocated)
00987 {
00988   unsigned int idx;
00989   
00990   idx = two_strings_hash (key) & table->mask;
00991 
00992   return find_generic_function (table, key, idx,
00993                                 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
00994                                 preallocated);
00995 }
00996 #endif /* DBUS_BUILD_TESTS */
00997 
00998 static DBusHashEntry*
00999 find_direct_function (DBusHashTable        *table,
01000                       void                 *key,
01001                       dbus_bool_t           create_if_not_found,
01002                       DBusHashEntry      ***bucket,
01003                       DBusPreallocatedHash *preallocated)
01004 {
01005   unsigned int idx;
01006   
01007   idx = RANDOM_INDEX (table, key) & table->mask;
01008 
01009 
01010   return find_generic_function (table, key, idx,
01011                                 NULL, create_if_not_found, bucket,
01012                                 preallocated);
01013 }
01014 
01015 static void
01016 rebuild_table (DBusHashTable *table)
01017 {
01018   int old_size;
01019   int new_buckets;
01020   DBusHashEntry **old_buckets;
01021   DBusHashEntry **old_chain;
01022   DBusHashEntry *entry;
01023   dbus_bool_t growing;
01024   
01025   /*
01026    * Allocate and initialize the new bucket array, and set up
01027    * hashing constants for new array size.
01028    */
01029 
01030   growing = table->n_entries >= table->hi_rebuild_size;
01031   
01032   old_size = table->n_buckets;
01033   old_buckets = table->buckets;
01034 
01035   if (growing)
01036     {
01037       /* overflow paranoia */
01038       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
01039           table->down_shift >= 0)
01040         new_buckets = table->n_buckets * 4;
01041       else
01042         return; /* can't grow anymore */
01043     }
01044   else
01045     {
01046       new_buckets = table->n_buckets / 4;
01047       if (new_buckets < DBUS_SMALL_HASH_TABLE)
01048         return; /* don't bother shrinking this far */
01049     }
01050 
01051   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
01052   if (table->buckets == NULL)
01053     {
01054       /* out of memory, yay - just don't reallocate, the table will
01055        * still work, albeit more slowly.
01056        */
01057       table->buckets = old_buckets;
01058       return;
01059     }
01060 
01061   table->n_buckets = new_buckets;
01062   
01063   if (growing)
01064     {
01065       table->lo_rebuild_size = table->hi_rebuild_size;
01066       table->hi_rebuild_size *= 4;
01067       
01068       table->down_shift -= 2;               /* keep 2 more high bits */
01069       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
01070     }
01071   else
01072     {
01073       table->hi_rebuild_size = table->lo_rebuild_size;
01074       table->lo_rebuild_size /= 4;
01075 
01076       table->down_shift += 2;         /* keep 2 fewer high bits */
01077       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
01078     }
01079 
01080 #if 0
01081   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
01082           growing ? "GROW" : "SHRINK",
01083           table->lo_rebuild_size,
01084           table->hi_rebuild_size,
01085           table->down_shift,
01086           table->mask);
01087 #endif
01088   
01089   _dbus_assert (table->lo_rebuild_size >= 0);
01090   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01091   _dbus_assert (table->mask != 0);
01092   /* the mask is essentially the max index */
01093   _dbus_assert (table->mask < table->n_buckets);
01094   
01095   /*
01096    * Rehash all of the existing entries into the new bucket array.
01097    */
01098 
01099   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01100     {
01101       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01102         {
01103           unsigned int idx;
01104           DBusHashEntry **bucket;
01105           
01106           *old_chain = entry->next;
01107           switch (table->key_type)
01108             {
01109             case DBUS_HASH_STRING:
01110               idx = string_hash (entry->key) & table->mask;
01111               break;
01112             case DBUS_HASH_TWO_STRINGS:
01113 #ifdef DBUS_BUILD_TESTS
01114               idx = two_strings_hash (entry->key) & table->mask;
01115 #else
01116               idx = 0;
01117               _dbus_assert_not_reached ("two-strings is not enabled");
01118 #endif
01119               break;
01120             case DBUS_HASH_INT:
01121             case DBUS_HASH_UINTPTR:
01122             case DBUS_HASH_POINTER:
01123               idx = RANDOM_INDEX (table, entry->key);
01124               break;
01125             default:
01126               idx = 0;
01127               _dbus_assert_not_reached ("Unknown hash table type");
01128               break;
01129             }
01130           
01131           bucket = &(table->buckets[idx]);
01132           entry->next = *bucket;
01133           *bucket = entry;
01134         }
01135     }
01136   
01137   /* Free the old bucket array, if it was dynamically allocated. */
01138 
01139   if (old_buckets != table->static_buckets)
01140     dbus_free (old_buckets);
01141 }
01142 
01152 void*
01153 _dbus_hash_table_lookup_string (DBusHashTable *table,
01154                                 const char    *key)
01155 {
01156   DBusHashEntry *entry;
01157 
01158   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01159   
01160   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01161 
01162   if (entry)
01163     return entry->value;
01164   else
01165     return NULL;
01166 }
01167 
01168 #ifdef DBUS_BUILD_TESTS
01169 
01178 void*
01179 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
01180                                      const char    *key)
01181 {
01182   DBusHashEntry *entry;
01183 
01184   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01185   
01186   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01187 
01188   if (entry)
01189     return entry->value;
01190   else
01191     return NULL;
01192 }
01193 #endif /* DBUS_BUILD_TESTS */
01194 
01204 void*
01205 _dbus_hash_table_lookup_int (DBusHashTable *table,
01206                              int            key)
01207 {
01208   DBusHashEntry *entry;
01209 
01210   _dbus_assert (table->key_type == DBUS_HASH_INT);
01211   
01212   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01213 
01214   if (entry)
01215     return entry->value;
01216   else
01217     return NULL;
01218 }
01219 
01220 #ifdef DBUS_BUILD_TESTS
01221 /* disabled since it's only used for testing */
01231 void*
01232 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01233                                  void          *key)
01234 {
01235   DBusHashEntry *entry;
01236 
01237   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01238   
01239   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01240 
01241   if (entry)
01242     return entry->value;
01243   else
01244     return NULL;
01245 }
01246 #endif /* DBUS_BUILD_TESTS */
01247 
01257 void*
01258 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
01259                                  uintptr_t      key)
01260 {
01261   DBusHashEntry *entry;
01262 
01263   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01264   
01265   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01266 
01267   if (entry)
01268     return entry->value;
01269   else
01270     return NULL;
01271 }
01272 
01281 dbus_bool_t
01282 _dbus_hash_table_remove_string (DBusHashTable *table,
01283                                 const char    *key)
01284 {
01285   DBusHashEntry *entry;
01286   DBusHashEntry **bucket;
01287   
01288   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01289   
01290   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01291 
01292   if (entry)
01293     {
01294       remove_entry (table, bucket, entry);
01295       return TRUE;
01296     }
01297   else
01298     return FALSE;
01299 }
01300 
01301 #ifdef DBUS_BUILD_TESTS
01302 
01310 dbus_bool_t
01311 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
01312                                      const char    *key)
01313 {
01314   DBusHashEntry *entry;
01315   DBusHashEntry **bucket;
01316   
01317   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01318   
01319   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01320 
01321   if (entry)
01322     {
01323       remove_entry (table, bucket, entry);
01324       return TRUE;
01325     }
01326   else
01327     return FALSE;
01328 }
01329 #endif /* DBUS_BUILD_TESTS */
01330 
01339 dbus_bool_t
01340 _dbus_hash_table_remove_int (DBusHashTable *table,
01341                              int            key)
01342 {
01343   DBusHashEntry *entry;
01344   DBusHashEntry **bucket;
01345   
01346   _dbus_assert (table->key_type == DBUS_HASH_INT);
01347   
01348   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01349   
01350   if (entry)
01351     {
01352       remove_entry (table, bucket, entry);
01353       return TRUE;
01354     }
01355   else
01356     return FALSE;
01357 }
01358 
01359 #ifdef DBUS_BUILD_TESTS
01360 /* disabled since it's only used for testing */
01369 dbus_bool_t
01370 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01371                                  void          *key)
01372 {
01373   DBusHashEntry *entry;
01374   DBusHashEntry **bucket;
01375   
01376   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01377   
01378   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01379   
01380   if (entry)
01381     {
01382       remove_entry (table, bucket, entry);
01383       return TRUE;
01384     }
01385   else
01386     return FALSE;
01387 }
01388 #endif /* DBUS_BUILD_TESTS */
01389 
01398 dbus_bool_t
01399 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
01400                                  uintptr_t      key)
01401 {
01402   DBusHashEntry *entry;
01403   DBusHashEntry **bucket;
01404   
01405   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01406   
01407   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01408   
01409   if (entry)
01410     {
01411       remove_entry (table, bucket, entry);
01412       return TRUE;
01413     }
01414   else
01415     return FALSE;
01416 }
01417 
01433 dbus_bool_t
01434 _dbus_hash_table_insert_string (DBusHashTable *table,
01435                                 char          *key,
01436                                 void          *value)
01437 {
01438   DBusPreallocatedHash *preallocated;
01439 
01440   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01441 
01442   preallocated = _dbus_hash_table_preallocate_entry (table);
01443   if (preallocated == NULL)
01444     return FALSE;
01445 
01446   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01447                                                key, value);
01448   
01449   return TRUE;
01450 }
01451 
01452 #ifdef DBUS_BUILD_TESTS
01453 
01468 dbus_bool_t
01469 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
01470                                      char          *key,
01471                                      void          *value)
01472 {
01473   DBusHashEntry *entry;
01474   
01475   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01476   
01477   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01478 
01479   if (entry == NULL)
01480     return FALSE; /* no memory */
01481 
01482   if (table->free_key_function && entry->key != key)
01483     (* table->free_key_function) (entry->key);
01484   
01485   if (table->free_value_function && entry->value != value)
01486     (* table->free_value_function) (entry->value);
01487   
01488   entry->key = key;
01489   entry->value = value;
01490 
01491   return TRUE;
01492 }
01493 #endif /* DBUS_BUILD_TESTS */
01494 
01510 dbus_bool_t
01511 _dbus_hash_table_insert_int (DBusHashTable *table,
01512                              int            key,
01513                              void          *value)
01514 {
01515   DBusHashEntry *entry;
01516 
01517   _dbus_assert (table->key_type == DBUS_HASH_INT);
01518   
01519   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01520 
01521   if (entry == NULL)
01522     return FALSE; /* no memory */
01523 
01524   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01525     (* table->free_key_function) (entry->key);
01526   
01527   if (table->free_value_function && entry->value != value)
01528     (* table->free_value_function) (entry->value);
01529   
01530   entry->key = _DBUS_INT_TO_POINTER (key);
01531   entry->value = value;
01532 
01533   return TRUE;
01534 }
01535 
01536 #ifdef DBUS_BUILD_TESTS
01537 /* disabled since it's only used for testing */
01553 dbus_bool_t
01554 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01555                                  void          *key,
01556                                  void          *value)
01557 {
01558   DBusHashEntry *entry;
01559 
01560   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01561   
01562   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01563 
01564   if (entry == NULL)
01565     return FALSE; /* no memory */
01566 
01567   if (table->free_key_function && entry->key != key)
01568     (* table->free_key_function) (entry->key);
01569   
01570   if (table->free_value_function && entry->value != value)
01571     (* table->free_value_function) (entry->value);
01572   
01573   entry->key = key;
01574   entry->value = value;
01575 
01576   return TRUE;
01577 }
01578 #endif /* DBUS_BUILD_TESTS */
01579 
01595 dbus_bool_t
01596 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
01597                                  uintptr_t      key,
01598                                  void          *value)
01599 {
01600   DBusHashEntry *entry;
01601 
01602   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01603   
01604   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01605 
01606   if (entry == NULL)
01607     return FALSE; /* no memory */
01608 
01609   if (table->free_key_function && entry->key != (void*) key)
01610     (* table->free_key_function) (entry->key);
01611   
01612   if (table->free_value_function && entry->value != value)
01613     (* table->free_value_function) (entry->value);
01614   
01615   entry->key = (void*) key;
01616   entry->value = value;
01617 
01618   return TRUE;
01619 }
01620 
01628 DBusPreallocatedHash*
01629 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01630 {
01631   DBusHashEntry *entry;
01632   
01633   entry = alloc_entry (table);
01634 
01635   return (DBusPreallocatedHash*) entry;
01636 }
01637 
01645 void
01646 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01647                                           DBusPreallocatedHash *preallocated)
01648 {
01649   DBusHashEntry *entry;
01650 
01651   _dbus_assert (preallocated != NULL);
01652   
01653   entry = (DBusHashEntry*) preallocated;
01654   
01655   /* Don't use free_entry(), since this entry has no key/data */
01656   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01657 }
01658 
01672 void
01673 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01674                                              DBusPreallocatedHash *preallocated,
01675                                              char                 *key,
01676                                              void                 *value)
01677 {
01678   DBusHashEntry *entry;
01679 
01680   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01681   _dbus_assert (preallocated != NULL);
01682   
01683   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01684 
01685   _dbus_assert (entry != NULL);
01686   
01687   if (table->free_key_function && entry->key != key)
01688     (* table->free_key_function) (entry->key);
01689 
01690   if (table->free_value_function && entry->value != value)
01691     (* table->free_value_function) (entry->value);
01692       
01693   entry->key = key;
01694   entry->value = value;
01695 }
01696 
01703 int
01704 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01705 {
01706   return table->n_entries;
01707 }
01708 
01711 #ifdef DBUS_BUILD_TESTS
01712 #include "dbus-test.h"
01713 #include <stdio.h>
01714 
01715 /* If you're wondering why the hash table test takes
01716  * forever to run, it's because we call this function
01717  * in inner loops thus making things quadratic.
01718  */
01719 static int
01720 count_entries (DBusHashTable *table)
01721 {
01722   DBusHashIter iter;
01723   int count;
01724 
01725   count = 0;
01726   _dbus_hash_iter_init (table, &iter);
01727   while (_dbus_hash_iter_next (&iter))
01728     ++count;
01729 
01730   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01731   
01732   return count;
01733 }
01734 
01735 /* Copy the foo\0bar\0 double string thing */
01736 static char*
01737 _dbus_strdup2 (const char *str)
01738 {
01739   size_t len;
01740   char *copy;
01741   
01742   if (str == NULL)
01743     return NULL;
01744   
01745   len = strlen (str);
01746   len += strlen ((str + len + 1));
01747 
01748   copy = dbus_malloc (len + 2);
01749   if (copy == NULL)
01750     return NULL;
01751 
01752   memcpy (copy, str, len + 2);
01753   
01754   return copy;
01755 }
01756 
01762 dbus_bool_t
01763 _dbus_hash_test (void)
01764 {
01765   int i;
01766   DBusHashTable *table1;
01767   DBusHashTable *table2;
01768   DBusHashTable *table3;
01769   DBusHashTable *table4;
01770   DBusHashIter iter;
01771 #define N_HASH_KEYS 5000
01772   char **keys;
01773   dbus_bool_t ret = FALSE;
01774 
01775   keys = dbus_new (char *, N_HASH_KEYS);
01776   if (keys == NULL)
01777     _dbus_assert_not_reached ("no memory");
01778 
01779   for (i = 0; i < N_HASH_KEYS; i++)
01780     {
01781       keys[i] = dbus_malloc (128);
01782 
01783       if (keys[i] == NULL)
01784         _dbus_assert_not_reached ("no memory");
01785     }
01786 
01787   printf ("Computing test hash keys...\n");
01788   i = 0;
01789   while (i < N_HASH_KEYS)
01790     {
01791       int len;
01792 
01793       /* all the hash keys are TWO_STRINGS, but
01794        * then we can also use those as regular strings.
01795        */
01796       
01797       len = sprintf (keys[i], "Hash key %d", i);
01798       sprintf (keys[i] + len + 1, "Two string %d", i);
01799       _dbus_assert (*(keys[i] + len) == '\0');
01800       _dbus_assert (*(keys[i] + len + 1) != '\0');
01801       ++i;
01802     }
01803   printf ("... done.\n");
01804   
01805   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01806                                  dbus_free, dbus_free);
01807   if (table1 == NULL)
01808     goto out;
01809 
01810   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01811                                  NULL, dbus_free);
01812   if (table2 == NULL)
01813     goto out;
01814 
01815   table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
01816                                  NULL, dbus_free);
01817   if (table3 == NULL)
01818     goto out;
01819 
01820   table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
01821                                  dbus_free, dbus_free);
01822   if (table4 == NULL)
01823     goto out;
01824 
01825   
01826   /* Insert and remove a bunch of stuff, counting the table in between
01827    * to be sure it's not broken and that iteration works
01828    */
01829   i = 0;
01830   while (i < 3000)
01831     {
01832       void *value;
01833       char *key;
01834 
01835       key = _dbus_strdup (keys[i]);
01836       if (key == NULL)
01837         goto out;
01838       value = _dbus_strdup ("Value!");
01839       if (value == NULL)
01840         goto out;
01841       
01842       if (!_dbus_hash_table_insert_string (table1,
01843                                            key, value))
01844         goto out;
01845 
01846       value = _dbus_strdup (keys[i]);
01847       if (value == NULL)
01848         goto out;
01849       
01850       if (!_dbus_hash_table_insert_int (table2,
01851                                         i, value))
01852         goto out;
01853 
01854       value = _dbus_strdup (keys[i]);
01855       if (value == NULL)
01856         goto out;
01857       
01858       if (!_dbus_hash_table_insert_uintptr (table3,
01859                                           i, value))
01860         goto out;
01861 
01862       key = _dbus_strdup2 (keys[i]);
01863       if (key == NULL)
01864         goto out;
01865       value = _dbus_strdup ("Value!");
01866       if (value == NULL)
01867         goto out;
01868       
01869       if (!_dbus_hash_table_insert_two_strings (table4,
01870                                                 key, value))
01871         goto out;
01872       
01873       _dbus_assert (count_entries (table1) == i + 1);
01874       _dbus_assert (count_entries (table2) == i + 1);
01875       _dbus_assert (count_entries (table3) == i + 1);
01876       _dbus_assert (count_entries (table4) == i + 1);
01877 
01878       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01879       _dbus_assert (value != NULL);
01880       _dbus_assert (strcmp (value, "Value!") == 0);
01881 
01882       value = _dbus_hash_table_lookup_int (table2, i);
01883       _dbus_assert (value != NULL);
01884       _dbus_assert (strcmp (value, keys[i]) == 0);
01885 
01886       value = _dbus_hash_table_lookup_uintptr (table3, i);
01887       _dbus_assert (value != NULL);
01888       _dbus_assert (strcmp (value, keys[i]) == 0);
01889 
01890       value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01891       _dbus_assert (value != NULL);
01892       _dbus_assert (strcmp (value, "Value!") == 0);
01893       
01894       ++i;
01895     }
01896 
01897   --i;
01898   while (i >= 0)
01899     {
01900       _dbus_hash_table_remove_string (table1,
01901                                       keys[i]);
01902 
01903       _dbus_hash_table_remove_int (table2, i);
01904 
01905       _dbus_hash_table_remove_uintptr (table3, i);
01906 
01907       _dbus_hash_table_remove_two_strings (table4,
01908                                            keys[i]);
01909       
01910       _dbus_assert (count_entries (table1) == i);
01911       _dbus_assert (count_entries (table2) == i);
01912       _dbus_assert (count_entries (table3) == i);
01913       _dbus_assert (count_entries (table4) == i);
01914 
01915       --i;
01916     }
01917 
01918   _dbus_hash_table_ref (table1);
01919   _dbus_hash_table_ref (table2);
01920   _dbus_hash_table_ref (table3);
01921   _dbus_hash_table_ref (table4);
01922   _dbus_hash_table_unref (table1);
01923   _dbus_hash_table_unref (table2);
01924   _dbus_hash_table_unref (table3);
01925   _dbus_hash_table_unref (table4);
01926   _dbus_hash_table_unref (table1);
01927   _dbus_hash_table_unref (table2);
01928   _dbus_hash_table_unref (table3);
01929   _dbus_hash_table_unref (table4);
01930   table3 = NULL;
01931 
01932   /* Insert a bunch of stuff then check
01933    * that iteration works correctly (finds the right
01934    * values, iter_set_value works, etc.)
01935    */
01936   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01937                                  dbus_free, dbus_free);
01938   if (table1 == NULL)
01939     goto out;
01940   
01941   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01942                                  NULL, dbus_free);
01943   if (table2 == NULL)
01944     goto out;
01945   
01946   i = 0;
01947   while (i < 5000)
01948     {
01949       char *key;
01950       void *value;      
01951       
01952       key = _dbus_strdup (keys[i]);
01953       if (key == NULL)
01954         goto out;
01955       value = _dbus_strdup ("Value!");
01956       if (value == NULL)
01957         goto out;
01958       
01959       if (!_dbus_hash_table_insert_string (table1,
01960                                            key, value))
01961         goto out;
01962 
01963       value = _dbus_strdup (keys[i]);
01964       if (value == NULL)
01965         goto out;
01966       
01967       if (!_dbus_hash_table_insert_int (table2,
01968                                         i, value))
01969         goto out;
01970       
01971       _dbus_assert (count_entries (table1) == i + 1);
01972       _dbus_assert (count_entries (table2) == i + 1);
01973       
01974       ++i;
01975     }
01976 
01977   _dbus_hash_iter_init (table1, &iter);
01978   while (_dbus_hash_iter_next (&iter))
01979     {
01980       const char *key;
01981       void *value;
01982 
01983       key = _dbus_hash_iter_get_string_key (&iter);
01984       value = _dbus_hash_iter_get_value (&iter);
01985 
01986       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01987 
01988       value = _dbus_strdup ("Different value!");
01989       if (value == NULL)
01990         goto out;
01991       
01992       _dbus_hash_iter_set_value (&iter, value);
01993 
01994       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01995     }
01996   
01997   _dbus_hash_iter_init (table1, &iter);
01998   while (_dbus_hash_iter_next (&iter))
01999     {
02000       _dbus_hash_iter_remove_entry (&iter);
02001       _dbus_assert (count_entries (table1) == i - 1);
02002       --i;
02003     }
02004 
02005   _dbus_hash_iter_init (table2, &iter);
02006   while (_dbus_hash_iter_next (&iter))
02007     {
02008       int key;
02009       void *value;
02010 
02011       key = _dbus_hash_iter_get_int_key (&iter);
02012       value = _dbus_hash_iter_get_value (&iter);
02013 
02014       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02015 
02016       value = _dbus_strdup ("Different value!");
02017       if (value == NULL)
02018         goto out;
02019       
02020       _dbus_hash_iter_set_value (&iter, value);
02021 
02022       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02023     }
02024 
02025   i = count_entries (table2);
02026   _dbus_hash_iter_init (table2, &iter);
02027   while (_dbus_hash_iter_next (&iter))
02028     {
02029       _dbus_hash_iter_remove_entry (&iter);
02030       _dbus_assert (count_entries (table2) + 1 == i);
02031       --i;
02032     }
02033 
02034   /* add/remove interleaved, to check that we grow/shrink the table
02035    * appropriately
02036    */
02037   i = 0;
02038   while (i < 1000)
02039     {
02040       char *key;
02041       void *value;
02042             
02043       key = _dbus_strdup (keys[i]);
02044       if (key == NULL)
02045         goto out;
02046 
02047       value = _dbus_strdup ("Value!");
02048       if (value == NULL)
02049         goto out;
02050       
02051       if (!_dbus_hash_table_insert_string (table1,
02052                                            key, value))
02053         goto out;
02054       
02055       ++i;
02056     }
02057 
02058   --i;
02059   while (i >= 0)
02060     {
02061       char *key;
02062       void *value;      
02063       
02064       key = _dbus_strdup (keys[i]);
02065       if (key == NULL)
02066         goto out;
02067       value = _dbus_strdup ("Value!");
02068       if (value == NULL)
02069         goto out;
02070 
02071       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02072         goto out;
02073       
02074       if (!_dbus_hash_table_insert_string (table1,
02075                                            key, value))
02076         goto out;
02077 
02078       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02079         goto out;
02080       
02081       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
02082       
02083       --i;
02084     }
02085 
02086   /* nuke these tables */
02087   _dbus_hash_table_unref (table1);
02088   _dbus_hash_table_unref (table2);
02089 
02090 
02091   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
02092    * be sure that interface works.
02093    */
02094   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
02095                                  dbus_free, dbus_free);
02096   if (table1 == NULL)
02097     goto out;
02098   
02099   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
02100                                  NULL, dbus_free);
02101   if (table2 == NULL)
02102     goto out;
02103   
02104   i = 0;
02105   while (i < 3000)
02106     {
02107       void *value;
02108       char *key;
02109 
02110       key = _dbus_strdup (keys[i]);
02111       if (key == NULL)
02112         goto out;
02113       value = _dbus_strdup ("Value!");
02114       if (value == NULL)
02115         goto out;
02116       
02117       if (!_dbus_hash_iter_lookup (table1,
02118                                    key, TRUE, &iter))
02119         goto out;
02120       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02121       _dbus_hash_iter_set_value (&iter, value);
02122 
02123       value = _dbus_strdup (keys[i]);
02124       if (value == NULL)
02125         goto out;
02126 
02127       if (!_dbus_hash_iter_lookup (table2,
02128                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
02129         goto out;
02130       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02131       _dbus_hash_iter_set_value (&iter, value); 
02132       
02133       _dbus_assert (count_entries (table1) == i + 1);
02134       _dbus_assert (count_entries (table2) == i + 1);
02135 
02136       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02137         goto out;
02138       
02139       value = _dbus_hash_iter_get_value (&iter);
02140       _dbus_assert (value != NULL);
02141       _dbus_assert (strcmp (value, "Value!") == 0);
02142 
02143       /* Iterate just to be sure it works, though
02144        * it's a stupid thing to do
02145        */
02146       while (_dbus_hash_iter_next (&iter))
02147         ;
02148       
02149       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02150         goto out;
02151 
02152       value = _dbus_hash_iter_get_value (&iter);
02153       _dbus_assert (value != NULL);
02154       _dbus_assert (strcmp (value, keys[i]) == 0);
02155 
02156       /* Iterate just to be sure it works, though
02157        * it's a stupid thing to do
02158        */
02159       while (_dbus_hash_iter_next (&iter))
02160         ;
02161       
02162       ++i;
02163     }
02164 
02165   --i;
02166   while (i >= 0)
02167     {
02168       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02169         _dbus_assert_not_reached ("hash entry should have existed");
02170       _dbus_hash_iter_remove_entry (&iter);
02171       
02172       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02173         _dbus_assert_not_reached ("hash entry should have existed");
02174       _dbus_hash_iter_remove_entry (&iter);
02175 
02176       _dbus_assert (count_entries (table1) == i);
02177       _dbus_assert (count_entries (table2) == i);
02178 
02179       --i;
02180     }
02181 
02182   _dbus_hash_table_unref (table1);
02183   _dbus_hash_table_unref (table2);
02184 
02185   ret = TRUE;
02186 
02187  out:
02188   for (i = 0; i < N_HASH_KEYS; i++)
02189     dbus_free (keys[i]);
02190 
02191   dbus_free (keys);
02192   
02193   return ret;
02194 }
02195 
02196 #endif /* DBUS_BUILD_TESTS */