D-Bus  1.10.12
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 static unsigned int   string_hash               (const char             *str);
00238 static void           rebuild_table             (DBusHashTable          *table);
00239 static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
00240 static void           remove_entry              (DBusHashTable          *table,
00241                                                  DBusHashEntry         **bucket,
00242                                                  DBusHashEntry          *entry);
00243 static void           free_entry                (DBusHashTable          *table,
00244                                                  DBusHashEntry          *entry);
00245 static void           free_entry_data           (DBusHashTable          *table,
00246                                                  DBusHashEntry          *entry);
00247 
00248 
00284 DBusHashTable*
00285 _dbus_hash_table_new (DBusHashType     type,
00286                       DBusFreeFunction key_free_function,
00287                       DBusFreeFunction value_free_function)
00288 {
00289   DBusHashTable *table;
00290   DBusMemPool *entry_pool;
00291   
00292   table = dbus_new0 (DBusHashTable, 1);
00293   if (table == NULL)
00294     return NULL;
00295 
00296   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00297   if (entry_pool == NULL)
00298     {
00299       dbus_free (table);
00300       return NULL;
00301     }
00302   
00303   table->refcount = 1;
00304   table->entry_pool = entry_pool;
00305   
00306   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00307   
00308   table->buckets = table->static_buckets;  
00309   table->n_buckets = DBUS_SMALL_HASH_TABLE;
00310   table->n_entries = 0;
00311   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00312   table->lo_rebuild_size = 0;
00313   table->down_shift = 28;
00314   table->mask = 3;
00315   table->key_type = type;
00316 
00317   _dbus_assert (table->mask < table->n_buckets);
00318   
00319   switch (table->key_type)
00320     {
00321     case DBUS_HASH_INT:
00322     case DBUS_HASH_UINTPTR:
00323       table->find_function = find_direct_function;
00324       break;
00325     case DBUS_HASH_STRING:
00326       table->find_function = find_string_function;
00327       break;
00328     default:
00329       _dbus_assert_not_reached ("Unknown hash table type");
00330       break;
00331     }
00332 
00333   table->free_key_function = key_free_function;
00334   table->free_value_function = value_free_function;
00335 
00336   return table;
00337 }
00338 
00339 
00346 DBusHashTable *
00347 _dbus_hash_table_ref (DBusHashTable *table)
00348 {
00349   table->refcount += 1;
00350   
00351   return table;
00352 }
00353 
00360 void
00361 _dbus_hash_table_unref (DBusHashTable *table)
00362 {
00363   table->refcount -= 1;
00364 
00365   if (table->refcount == 0)
00366     {
00367 #if 0
00368       DBusHashEntry *entry;
00369       DBusHashEntry *next;
00370       int i;
00371 
00372       /* Free the entries in the table. */
00373       for (i = 0; i < table->n_buckets; i++)
00374         {
00375           entry = table->buckets[i];
00376           while (entry != NULL)
00377             {
00378               next = entry->next;
00379 
00380               free_entry (table, entry);
00381               
00382               entry = next;
00383             }
00384         }
00385 #else
00386       DBusHashEntry *entry;
00387       int i;
00388 
00389       /* Free the entries in the table. */
00390       for (i = 0; i < table->n_buckets; i++)
00391         {
00392           entry = table->buckets[i];
00393           while (entry != NULL)
00394             {
00395               free_entry_data (table, entry);
00396               
00397               entry = entry->next;
00398             }
00399         }
00400       /* We can do this very quickly with memory pools ;-) */
00401       _dbus_mem_pool_free (table->entry_pool);
00402 #endif
00403       
00404       /* Free the bucket array, if it was dynamically allocated. */
00405       if (table->buckets != table->static_buckets)
00406         dbus_free (table->buckets);
00407 
00408       dbus_free (table);
00409     }
00410 }
00411 
00417 void
00418 _dbus_hash_table_remove_all (DBusHashTable *table)
00419 {
00420   DBusHashIter iter;
00421   _dbus_hash_iter_init (table, &iter);
00422   while (_dbus_hash_iter_next (&iter))
00423     {
00424       _dbus_hash_iter_remove_entry(&iter);
00425     }
00426 }
00427 
00428 static DBusHashEntry*
00429 alloc_entry (DBusHashTable *table)
00430 {
00431   DBusHashEntry *entry;
00432 
00433   entry = _dbus_mem_pool_alloc (table->entry_pool);
00434   
00435   return entry;
00436 }
00437 
00438 static void
00439 free_entry_data (DBusHashTable  *table,
00440                  DBusHashEntry  *entry)
00441 {
00442   if (table->free_key_function)
00443     (* table->free_key_function) (entry->key);
00444   if (table->free_value_function)
00445     (* table->free_value_function) (entry->value);
00446 }
00447 
00448 static void
00449 free_entry (DBusHashTable  *table,
00450             DBusHashEntry  *entry)
00451 {
00452   free_entry_data (table, entry);
00453   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00454 }
00455 
00456 static void
00457 remove_entry (DBusHashTable  *table,
00458               DBusHashEntry **bucket,
00459               DBusHashEntry  *entry)
00460 {
00461   _dbus_assert (table != NULL);
00462   _dbus_assert (bucket != NULL);
00463   _dbus_assert (*bucket != NULL);  
00464   _dbus_assert (entry != NULL);
00465   
00466   if (*bucket == entry)
00467     *bucket = entry->next;
00468   else
00469     {
00470       DBusHashEntry *prev;
00471       prev = *bucket;
00472 
00473       while (prev->next != entry)
00474         prev = prev->next;      
00475       
00476       _dbus_assert (prev != NULL);
00477 
00478       prev->next = entry->next;
00479     }
00480   
00481   table->n_entries -= 1;
00482   free_entry (table, entry);
00483 }
00484 
00516 void
00517 _dbus_hash_iter_init (DBusHashTable *table,
00518                       DBusHashIter  *iter)
00519 {
00520   DBusRealHashIter *real;
00521   
00522   _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00523   
00524   real = (DBusRealHashIter*) iter;
00525 
00526   real->table = table;
00527   real->bucket = NULL;
00528   real->entry = NULL;
00529   real->next_entry = NULL;
00530   real->next_bucket = 0;
00531   real->n_entries_on_init = table->n_entries;
00532 }
00533 
00542 dbus_bool_t
00543 _dbus_hash_iter_next (DBusHashIter  *iter)
00544 {
00545   DBusRealHashIter *real;
00546   
00547   _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00548   
00549   real = (DBusRealHashIter*) iter;
00550 
00551   /* if this assertion failed someone probably added hash entries
00552    * during iteration, which is bad.
00553    */
00554   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00555   
00556   /* Remember that real->entry may have been deleted */
00557   
00558   while (real->next_entry == NULL)
00559     {
00560       if (real->next_bucket >= real->table->n_buckets)
00561         {
00562           /* invalidate iter and return false */
00563           real->entry = NULL;
00564           real->table = NULL;
00565           real->bucket = NULL;
00566           return FALSE;
00567         }
00568 
00569       real->bucket = &(real->table->buckets[real->next_bucket]);
00570       real->next_entry = *(real->bucket);
00571       real->next_bucket += 1;
00572     }
00573 
00574   _dbus_assert (real->next_entry != NULL);
00575   _dbus_assert (real->bucket != NULL);
00576   
00577   real->entry = real->next_entry;
00578   real->next_entry = real->entry->next;
00579   
00580   return TRUE;
00581 }
00582 
00591 void
00592 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00593 {
00594   DBusRealHashIter *real;
00595 
00596   real = (DBusRealHashIter*) iter;
00597 
00598   _dbus_assert (real->table != NULL);
00599   _dbus_assert (real->entry != NULL);
00600   _dbus_assert (real->bucket != NULL);
00601   
00602   remove_entry (real->table, real->bucket, real->entry);
00603 
00604   real->entry = NULL; /* make it crash if you try to use this entry */
00605 }
00606 
00612 void*
00613 _dbus_hash_iter_get_value (DBusHashIter *iter)
00614 {
00615   DBusRealHashIter *real;
00616 
00617   real = (DBusRealHashIter*) iter;
00618 
00619   _dbus_assert (real->table != NULL);
00620   _dbus_assert (real->entry != NULL);
00621 
00622   return real->entry->value;
00623 }
00624 
00635 void
00636 _dbus_hash_iter_set_value (DBusHashIter *iter,
00637                            void         *value)
00638 {
00639   DBusRealHashIter *real;
00640 
00641   real = (DBusRealHashIter*) iter;
00642 
00643   _dbus_assert (real->table != NULL);
00644   _dbus_assert (real->entry != NULL);
00645 
00646   if (real->table->free_value_function && value != real->entry->value)    
00647     (* real->table->free_value_function) (real->entry->value);
00648   
00649   real->entry->value = value;
00650 }
00651 
00658 int
00659 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00660 {
00661   DBusRealHashIter *real;
00662 
00663   real = (DBusRealHashIter*) iter;
00664 
00665   _dbus_assert (real->table != NULL);
00666   _dbus_assert (real->entry != NULL);
00667 
00668   return _DBUS_POINTER_TO_INT (real->entry->key);
00669 }
00670 
00677 uintptr_t
00678 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
00679 {
00680   DBusRealHashIter *real;
00681 
00682   real = (DBusRealHashIter*) iter;
00683 
00684   _dbus_assert (real->table != NULL);
00685   _dbus_assert (real->entry != NULL);
00686 
00687   return (uintptr_t) real->entry->key;
00688 }
00689 
00695 const char*
00696 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00697 {
00698   DBusRealHashIter *real;
00699 
00700   real = (DBusRealHashIter*) iter;
00701 
00702   _dbus_assert (real->table != NULL);
00703   _dbus_assert (real->entry != NULL);
00704 
00705   return real->entry->key;
00706 }
00707 
00739 dbus_bool_t
00740 _dbus_hash_iter_lookup (DBusHashTable *table,
00741                         void          *key,
00742                         dbus_bool_t    create_if_not_found,
00743                         DBusHashIter  *iter)
00744 {
00745   DBusRealHashIter *real;
00746   DBusHashEntry *entry;
00747   DBusHashEntry **bucket;
00748   
00749   _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00750   
00751   real = (DBusRealHashIter*) iter;
00752 
00753   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00754 
00755   if (entry == NULL)
00756     return FALSE;
00757   
00758   real->table = table;
00759   real->bucket = bucket;
00760   real->entry = entry;
00761   real->next_entry = entry->next;
00762   real->next_bucket = (bucket - table->buckets) + 1;
00763   real->n_entries_on_init = table->n_entries; 
00764 
00765   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00766   
00767   return TRUE;
00768 }
00769 
00770 static void
00771 add_allocated_entry (DBusHashTable   *table,
00772                      DBusHashEntry   *entry,
00773                      unsigned int     idx,
00774                      void            *key,
00775                      DBusHashEntry ***bucket)
00776 {
00777   DBusHashEntry **b;  
00778   
00779   entry->key = key;
00780   
00781   b = &(table->buckets[idx]);
00782   entry->next = *b;
00783   *b = entry;
00784 
00785   if (bucket)
00786     *bucket = b;
00787   
00788   table->n_entries += 1;
00789 
00790   /* note we ONLY rebuild when ADDING - because you can iterate over a
00791    * table and remove entries safely.
00792    */
00793   if (table->n_entries >= table->hi_rebuild_size ||
00794       table->n_entries < table->lo_rebuild_size)
00795     rebuild_table (table);
00796 }
00797 
00798 static DBusHashEntry*
00799 add_entry (DBusHashTable        *table, 
00800            unsigned int          idx,
00801            void                 *key,
00802            DBusHashEntry      ***bucket,
00803            DBusPreallocatedHash *preallocated)
00804 {
00805   DBusHashEntry  *entry;
00806 
00807   if (preallocated == NULL)
00808     {
00809       entry = alloc_entry (table);
00810       if (entry == NULL)
00811         {
00812           if (bucket)
00813             *bucket = NULL;
00814           return NULL;
00815         }
00816     }
00817   else
00818     {
00819       entry = (DBusHashEntry*) preallocated;
00820     }
00821 
00822   add_allocated_entry (table, entry, idx, key, bucket);
00823 
00824   return entry;
00825 }
00826 
00827 /* This is g_str_hash from GLib which was
00828  * extensively discussed/tested/profiled
00829  */
00830 static unsigned int
00831 string_hash (const char *str)
00832 {
00833   const char *p = str;
00834   unsigned int h = *p;
00835 
00836   if (h)
00837     for (p += 1; *p != '\0'; p++)
00838       h = (h << 5) - h + *p;
00839 
00840   return h;
00841 }
00842 
00844 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00845 
00846 static DBusHashEntry*
00847 find_generic_function (DBusHashTable        *table,
00848                        void                 *key,
00849                        unsigned int          idx,
00850                        KeyCompareFunc        compare_func,
00851                        dbus_bool_t           create_if_not_found,
00852                        DBusHashEntry      ***bucket,
00853                        DBusPreallocatedHash *preallocated)
00854 {
00855   DBusHashEntry *entry;
00856 
00857   if (bucket)
00858     *bucket = NULL;
00859 
00860   /* Search all of the entries in this bucket. */
00861   entry = table->buckets[idx];
00862   while (entry != NULL)
00863     {
00864       if ((compare_func == NULL && key == entry->key) ||
00865           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00866         {
00867           if (bucket)
00868             *bucket = &(table->buckets[idx]);
00869 
00870           if (preallocated)
00871             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00872           
00873           return entry;
00874         }
00875       
00876       entry = entry->next;
00877     }
00878 
00879   if (create_if_not_found)
00880     entry = add_entry (table, idx, key, bucket, preallocated);
00881   else if (preallocated)
00882     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00883   
00884   return entry;
00885 }
00886 
00887 static DBusHashEntry*
00888 find_string_function (DBusHashTable        *table,
00889                       void                 *key,
00890                       dbus_bool_t           create_if_not_found,
00891                       DBusHashEntry      ***bucket,
00892                       DBusPreallocatedHash *preallocated)
00893 {
00894   unsigned int idx;
00895   
00896   idx = string_hash (key) & table->mask;
00897 
00898   return find_generic_function (table, key, idx,
00899                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00900                                 preallocated);
00901 }
00902 
00903 static DBusHashEntry*
00904 find_direct_function (DBusHashTable        *table,
00905                       void                 *key,
00906                       dbus_bool_t           create_if_not_found,
00907                       DBusHashEntry      ***bucket,
00908                       DBusPreallocatedHash *preallocated)
00909 {
00910   unsigned int idx;
00911   
00912   idx = RANDOM_INDEX (table, key) & table->mask;
00913 
00914 
00915   return find_generic_function (table, key, idx,
00916                                 NULL, create_if_not_found, bucket,
00917                                 preallocated);
00918 }
00919 
00920 static void
00921 rebuild_table (DBusHashTable *table)
00922 {
00923   int old_size;
00924   int new_buckets;
00925   DBusHashEntry **old_buckets;
00926   DBusHashEntry **old_chain;
00927   DBusHashEntry *entry;
00928   dbus_bool_t growing;
00929   
00930   /*
00931    * Allocate and initialize the new bucket array, and set up
00932    * hashing constants for new array size.
00933    */
00934 
00935   growing = table->n_entries >= table->hi_rebuild_size;
00936   
00937   old_size = table->n_buckets;
00938   old_buckets = table->buckets;
00939 
00940   if (growing)
00941     {
00942       /* overflow paranoia */
00943       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
00944           table->down_shift >= 0)
00945         new_buckets = table->n_buckets * 4;
00946       else
00947         return; /* can't grow anymore */
00948     }
00949   else
00950     {
00951       new_buckets = table->n_buckets / 4;
00952       if (new_buckets < DBUS_SMALL_HASH_TABLE)
00953         return; /* don't bother shrinking this far */
00954     }
00955 
00956   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
00957   if (table->buckets == NULL)
00958     {
00959       /* out of memory, yay - just don't reallocate, the table will
00960        * still work, albeit more slowly.
00961        */
00962       table->buckets = old_buckets;
00963       return;
00964     }
00965 
00966   table->n_buckets = new_buckets;
00967   
00968   if (growing)
00969     {
00970       table->lo_rebuild_size = table->hi_rebuild_size;
00971       table->hi_rebuild_size *= 4;
00972       
00973       table->down_shift -= 2;               /* keep 2 more high bits */
00974       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
00975     }
00976   else
00977     {
00978       table->hi_rebuild_size = table->lo_rebuild_size;
00979       table->lo_rebuild_size /= 4;
00980 
00981       table->down_shift += 2;         /* keep 2 fewer high bits */
00982       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
00983     }
00984 
00985 #if 0
00986   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
00987           growing ? "GROW" : "SHRINK",
00988           table->lo_rebuild_size,
00989           table->hi_rebuild_size,
00990           table->down_shift,
00991           table->mask);
00992 #endif
00993   
00994   _dbus_assert (table->lo_rebuild_size >= 0);
00995   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
00996   _dbus_assert (table->mask != 0);
00997   /* the mask is essentially the max index */
00998   _dbus_assert (table->mask < table->n_buckets);
00999   
01000   /*
01001    * Rehash all of the existing entries into the new bucket array.
01002    */
01003 
01004   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01005     {
01006       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01007         {
01008           unsigned int idx;
01009           DBusHashEntry **bucket;
01010           
01011           *old_chain = entry->next;
01012           switch (table->key_type)
01013             {
01014             case DBUS_HASH_STRING:
01015               idx = string_hash (entry->key) & table->mask;
01016               break;
01017             case DBUS_HASH_INT:
01018             case DBUS_HASH_UINTPTR:
01019               idx = RANDOM_INDEX (table, entry->key);
01020               break;
01021             default:
01022               idx = 0;
01023               _dbus_assert_not_reached ("Unknown hash table type");
01024               break;
01025             }
01026           
01027           bucket = &(table->buckets[idx]);
01028           entry->next = *bucket;
01029           *bucket = entry;
01030         }
01031     }
01032   
01033   /* Free the old bucket array, if it was dynamically allocated. */
01034 
01035   if (old_buckets != table->static_buckets)
01036     dbus_free (old_buckets);
01037 }
01038 
01048 void*
01049 _dbus_hash_table_lookup_string (DBusHashTable *table,
01050                                 const char    *key)
01051 {
01052   DBusHashEntry *entry;
01053 
01054   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01055   
01056   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01057 
01058   if (entry)
01059     return entry->value;
01060   else
01061     return NULL;
01062 }
01063 
01073 void*
01074 _dbus_hash_table_lookup_int (DBusHashTable *table,
01075                              int            key)
01076 {
01077   DBusHashEntry *entry;
01078 
01079   _dbus_assert (table->key_type == DBUS_HASH_INT);
01080   
01081   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01082 
01083   if (entry)
01084     return entry->value;
01085   else
01086     return NULL;
01087 }
01088 
01098 void*
01099 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
01100                                  uintptr_t      key)
01101 {
01102   DBusHashEntry *entry;
01103 
01104   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01105   
01106   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01107 
01108   if (entry)
01109     return entry->value;
01110   else
01111     return NULL;
01112 }
01113 
01122 dbus_bool_t
01123 _dbus_hash_table_remove_string (DBusHashTable *table,
01124                                 const char    *key)
01125 {
01126   DBusHashEntry *entry;
01127   DBusHashEntry **bucket;
01128   
01129   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01130   
01131   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01132 
01133   if (entry)
01134     {
01135       remove_entry (table, bucket, entry);
01136       return TRUE;
01137     }
01138   else
01139     return FALSE;
01140 }
01141 
01150 dbus_bool_t
01151 _dbus_hash_table_remove_int (DBusHashTable *table,
01152                              int            key)
01153 {
01154   DBusHashEntry *entry;
01155   DBusHashEntry **bucket;
01156   
01157   _dbus_assert (table->key_type == DBUS_HASH_INT);
01158   
01159   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01160   
01161   if (entry)
01162     {
01163       remove_entry (table, bucket, entry);
01164       return TRUE;
01165     }
01166   else
01167     return FALSE;
01168 }
01169 
01178 dbus_bool_t
01179 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
01180                                  uintptr_t      key)
01181 {
01182   DBusHashEntry *entry;
01183   DBusHashEntry **bucket;
01184   
01185   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01186   
01187   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01188   
01189   if (entry)
01190     {
01191       remove_entry (table, bucket, entry);
01192       return TRUE;
01193     }
01194   else
01195     return FALSE;
01196 }
01197 
01213 dbus_bool_t
01214 _dbus_hash_table_insert_string (DBusHashTable *table,
01215                                 char          *key,
01216                                 void          *value)
01217 {
01218   DBusPreallocatedHash *preallocated;
01219 
01220   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01221 
01222   preallocated = _dbus_hash_table_preallocate_entry (table);
01223   if (preallocated == NULL)
01224     return FALSE;
01225 
01226   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01227                                                key, value);
01228   
01229   return TRUE;
01230 }
01231 
01247 dbus_bool_t
01248 _dbus_hash_table_insert_int (DBusHashTable *table,
01249                              int            key,
01250                              void          *value)
01251 {
01252   DBusHashEntry *entry;
01253 
01254   _dbus_assert (table->key_type == DBUS_HASH_INT);
01255   
01256   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01257 
01258   if (entry == NULL)
01259     return FALSE; /* no memory */
01260 
01261   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01262     (* table->free_key_function) (entry->key);
01263   
01264   if (table->free_value_function && entry->value != value)
01265     (* table->free_value_function) (entry->value);
01266   
01267   entry->key = _DBUS_INT_TO_POINTER (key);
01268   entry->value = value;
01269 
01270   return TRUE;
01271 }
01272 
01288 dbus_bool_t
01289 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
01290                                  uintptr_t      key,
01291                                  void          *value)
01292 {
01293   DBusHashEntry *entry;
01294 
01295   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01296   
01297   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01298 
01299   if (entry == NULL)
01300     return FALSE; /* no memory */
01301 
01302   if (table->free_key_function && entry->key != (void*) key)
01303     (* table->free_key_function) (entry->key);
01304   
01305   if (table->free_value_function && entry->value != value)
01306     (* table->free_value_function) (entry->value);
01307   
01308   entry->key = (void*) key;
01309   entry->value = value;
01310 
01311   return TRUE;
01312 }
01313 
01321 DBusPreallocatedHash*
01322 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01323 {
01324   DBusHashEntry *entry;
01325   
01326   entry = alloc_entry (table);
01327 
01328   return (DBusPreallocatedHash*) entry;
01329 }
01330 
01338 void
01339 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01340                                           DBusPreallocatedHash *preallocated)
01341 {
01342   DBusHashEntry *entry;
01343 
01344   _dbus_assert (preallocated != NULL);
01345   
01346   entry = (DBusHashEntry*) preallocated;
01347   
01348   /* Don't use free_entry(), since this entry has no key/data */
01349   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01350 }
01351 
01365 void
01366 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01367                                              DBusPreallocatedHash *preallocated,
01368                                              char                 *key,
01369                                              void                 *value)
01370 {
01371   DBusHashEntry *entry;
01372 
01373   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01374   _dbus_assert (preallocated != NULL);
01375   
01376   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01377 
01378   _dbus_assert (entry != NULL);
01379   
01380   if (table->free_key_function && entry->key != key)
01381     (* table->free_key_function) (entry->key);
01382 
01383   if (table->free_value_function && entry->value != value)
01384     (* table->free_value_function) (entry->value);
01385       
01386   entry->key = key;
01387   entry->value = value;
01388 }
01389 
01396 int
01397 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01398 {
01399   return table->n_entries;
01400 }
01401 
01404 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
01405 #include "dbus-test.h"
01406 #include <stdio.h>
01407 
01408 /* If you're wondering why the hash table test takes
01409  * forever to run, it's because we call this function
01410  * in inner loops thus making things quadratic.
01411  */
01412 static int
01413 count_entries (DBusHashTable *table)
01414 {
01415   DBusHashIter iter;
01416   int count;
01417 
01418   count = 0;
01419   _dbus_hash_iter_init (table, &iter);
01420   while (_dbus_hash_iter_next (&iter))
01421     ++count;
01422 
01423   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01424   
01425   return count;
01426 }
01427 
01433 dbus_bool_t
01434 _dbus_hash_test (void)
01435 {
01436   int i;
01437   DBusHashTable *table1;
01438   DBusHashTable *table2;
01439   DBusHashTable *table3;
01440   DBusHashIter iter;
01441 #define N_HASH_KEYS 5000
01442   char **keys;
01443   dbus_bool_t ret = FALSE;
01444 
01445   keys = dbus_new (char *, N_HASH_KEYS);
01446   if (keys == NULL)
01447     _dbus_assert_not_reached ("no memory");
01448 
01449   for (i = 0; i < N_HASH_KEYS; i++)
01450     {
01451       keys[i] = dbus_malloc (128);
01452 
01453       if (keys[i] == NULL)
01454         _dbus_assert_not_reached ("no memory");
01455     }
01456 
01457   printf ("Computing test hash keys...\n");
01458   i = 0;
01459   while (i < N_HASH_KEYS)
01460     {
01461       int len;
01462 
01463       len = sprintf (keys[i], "Hash key %d", i);
01464       _dbus_assert (*(keys[i] + len) == '\0');
01465       ++i;
01466     }
01467   printf ("... done.\n");
01468   
01469   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01470                                  dbus_free, dbus_free);
01471   if (table1 == NULL)
01472     goto out;
01473 
01474   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01475                                  NULL, dbus_free);
01476   if (table2 == NULL)
01477     goto out;
01478 
01479   table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
01480                                  NULL, dbus_free);
01481   if (table3 == NULL)
01482     goto out;
01483 
01484   /* Insert and remove a bunch of stuff, counting the table in between
01485    * to be sure it's not broken and that iteration works
01486    */
01487   i = 0;
01488   while (i < 3000)
01489     {
01490       void *value;
01491       char *key;
01492 
01493       key = _dbus_strdup (keys[i]);
01494       if (key == NULL)
01495         goto out;
01496       value = _dbus_strdup ("Value!");
01497       if (value == NULL)
01498         goto out;
01499       
01500       if (!_dbus_hash_table_insert_string (table1,
01501                                            key, value))
01502         goto out;
01503 
01504       value = _dbus_strdup (keys[i]);
01505       if (value == NULL)
01506         goto out;
01507       
01508       if (!_dbus_hash_table_insert_int (table2,
01509                                         i, value))
01510         goto out;
01511 
01512       value = _dbus_strdup (keys[i]);
01513       if (value == NULL)
01514         goto out;
01515       
01516       if (!_dbus_hash_table_insert_uintptr (table3,
01517                                           i, value))
01518         goto out;
01519 
01520       _dbus_assert (count_entries (table1) == i + 1);
01521       _dbus_assert (count_entries (table2) == i + 1);
01522       _dbus_assert (count_entries (table3) == i + 1);
01523 
01524       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01525       _dbus_assert (value != NULL);
01526       _dbus_assert (strcmp (value, "Value!") == 0);
01527 
01528       value = _dbus_hash_table_lookup_int (table2, i);
01529       _dbus_assert (value != NULL);
01530       _dbus_assert (strcmp (value, keys[i]) == 0);
01531 
01532       value = _dbus_hash_table_lookup_uintptr (table3, i);
01533       _dbus_assert (value != NULL);
01534       _dbus_assert (strcmp (value, keys[i]) == 0);
01535 
01536       ++i;
01537     }
01538 
01539   --i;
01540   while (i >= 0)
01541     {
01542       _dbus_hash_table_remove_string (table1,
01543                                       keys[i]);
01544 
01545       _dbus_hash_table_remove_int (table2, i);
01546 
01547       _dbus_hash_table_remove_uintptr (table3, i);
01548 
01549       _dbus_assert (count_entries (table1) == i);
01550       _dbus_assert (count_entries (table2) == i);
01551       _dbus_assert (count_entries (table3) == i);
01552 
01553       --i;
01554     }
01555 
01556   _dbus_hash_table_ref (table1);
01557   _dbus_hash_table_ref (table2);
01558   _dbus_hash_table_ref (table3);
01559   _dbus_hash_table_unref (table1);
01560   _dbus_hash_table_unref (table2);
01561   _dbus_hash_table_unref (table3);
01562   _dbus_hash_table_unref (table1);
01563   _dbus_hash_table_unref (table2);
01564   _dbus_hash_table_unref (table3);
01565   table3 = NULL;
01566 
01567   /* Insert a bunch of stuff then check
01568    * that iteration works correctly (finds the right
01569    * values, iter_set_value works, etc.)
01570    */
01571   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01572                                  dbus_free, dbus_free);
01573   if (table1 == NULL)
01574     goto out;
01575   
01576   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01577                                  NULL, dbus_free);
01578   if (table2 == NULL)
01579     goto out;
01580   
01581   i = 0;
01582   while (i < 5000)
01583     {
01584       char *key;
01585       void *value;      
01586       
01587       key = _dbus_strdup (keys[i]);
01588       if (key == NULL)
01589         goto out;
01590       value = _dbus_strdup ("Value!");
01591       if (value == NULL)
01592         goto out;
01593       
01594       if (!_dbus_hash_table_insert_string (table1,
01595                                            key, value))
01596         goto out;
01597 
01598       value = _dbus_strdup (keys[i]);
01599       if (value == NULL)
01600         goto out;
01601       
01602       if (!_dbus_hash_table_insert_int (table2,
01603                                         i, value))
01604         goto out;
01605       
01606       _dbus_assert (count_entries (table1) == i + 1);
01607       _dbus_assert (count_entries (table2) == i + 1);
01608       
01609       ++i;
01610     }
01611 
01612   _dbus_hash_iter_init (table1, &iter);
01613   while (_dbus_hash_iter_next (&iter))
01614     {
01615       const char *key;
01616       void *value;
01617 
01618       key = _dbus_hash_iter_get_string_key (&iter);
01619       value = _dbus_hash_iter_get_value (&iter);
01620 
01621       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01622 
01623       value = _dbus_strdup ("Different value!");
01624       if (value == NULL)
01625         goto out;
01626       
01627       _dbus_hash_iter_set_value (&iter, value);
01628 
01629       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01630     }
01631   
01632   _dbus_hash_iter_init (table1, &iter);
01633   while (_dbus_hash_iter_next (&iter))
01634     {
01635       _dbus_hash_iter_remove_entry (&iter);
01636       _dbus_assert (count_entries (table1) == i - 1);
01637       --i;
01638     }
01639 
01640   _dbus_hash_iter_init (table2, &iter);
01641   while (_dbus_hash_iter_next (&iter))
01642     {
01643       int key;
01644       void *value;
01645 
01646       key = _dbus_hash_iter_get_int_key (&iter);
01647       value = _dbus_hash_iter_get_value (&iter);
01648 
01649       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01650 
01651       value = _dbus_strdup ("Different value!");
01652       if (value == NULL)
01653         goto out;
01654       
01655       _dbus_hash_iter_set_value (&iter, value);
01656 
01657       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01658     }
01659 
01660   i = count_entries (table2);
01661   _dbus_hash_iter_init (table2, &iter);
01662   while (_dbus_hash_iter_next (&iter))
01663     {
01664       _dbus_hash_iter_remove_entry (&iter);
01665       _dbus_assert (count_entries (table2) + 1 == i);
01666       --i;
01667     }
01668 
01669   /* add/remove interleaved, to check that we grow/shrink the table
01670    * appropriately
01671    */
01672   i = 0;
01673   while (i < 1000)
01674     {
01675       char *key;
01676       void *value;
01677             
01678       key = _dbus_strdup (keys[i]);
01679       if (key == NULL)
01680         goto out;
01681 
01682       value = _dbus_strdup ("Value!");
01683       if (value == NULL)
01684         goto out;
01685       
01686       if (!_dbus_hash_table_insert_string (table1,
01687                                            key, value))
01688         goto out;
01689       
01690       ++i;
01691     }
01692 
01693   --i;
01694   while (i >= 0)
01695     {
01696       char *key;
01697       void *value;      
01698       
01699       key = _dbus_strdup (keys[i]);
01700       if (key == NULL)
01701         goto out;
01702       value = _dbus_strdup ("Value!");
01703       if (value == NULL)
01704         goto out;
01705 
01706       if (!_dbus_hash_table_remove_string (table1, keys[i]))
01707         goto out;
01708       
01709       if (!_dbus_hash_table_insert_string (table1,
01710                                            key, value))
01711         goto out;
01712 
01713       if (!_dbus_hash_table_remove_string (table1, keys[i]))
01714         goto out;
01715       
01716       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
01717       
01718       --i;
01719     }
01720 
01721   /* nuke these tables */
01722   _dbus_hash_table_unref (table1);
01723   _dbus_hash_table_unref (table2);
01724 
01725 
01726   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
01727    * be sure that interface works.
01728    */
01729   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01730                                  dbus_free, dbus_free);
01731   if (table1 == NULL)
01732     goto out;
01733   
01734   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01735                                  NULL, dbus_free);
01736   if (table2 == NULL)
01737     goto out;
01738   
01739   i = 0;
01740   while (i < 3000)
01741     {
01742       void *value;
01743       char *key;
01744 
01745       key = _dbus_strdup (keys[i]);
01746       if (key == NULL)
01747         goto out;
01748       value = _dbus_strdup ("Value!");
01749       if (value == NULL)
01750         goto out;
01751       
01752       if (!_dbus_hash_iter_lookup (table1,
01753                                    key, TRUE, &iter))
01754         goto out;
01755       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01756       _dbus_hash_iter_set_value (&iter, value);
01757 
01758       value = _dbus_strdup (keys[i]);
01759       if (value == NULL)
01760         goto out;
01761 
01762       if (!_dbus_hash_iter_lookup (table2,
01763                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
01764         goto out;
01765       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01766       _dbus_hash_iter_set_value (&iter, value); 
01767       
01768       _dbus_assert (count_entries (table1) == i + 1);
01769       _dbus_assert (count_entries (table2) == i + 1);
01770 
01771       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01772         goto out;
01773       
01774       value = _dbus_hash_iter_get_value (&iter);
01775       _dbus_assert (value != NULL);
01776       _dbus_assert (strcmp (value, "Value!") == 0);
01777 
01778       /* Iterate just to be sure it works, though
01779        * it's a stupid thing to do
01780        */
01781       while (_dbus_hash_iter_next (&iter))
01782         ;
01783       
01784       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01785         goto out;
01786 
01787       value = _dbus_hash_iter_get_value (&iter);
01788       _dbus_assert (value != NULL);
01789       _dbus_assert (strcmp (value, keys[i]) == 0);
01790 
01791       /* Iterate just to be sure it works, though
01792        * it's a stupid thing to do
01793        */
01794       while (_dbus_hash_iter_next (&iter))
01795         ;
01796       
01797       ++i;
01798     }
01799 
01800   --i;
01801   while (i >= 0)
01802     {
01803       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01804         _dbus_assert_not_reached ("hash entry should have existed");
01805       _dbus_hash_iter_remove_entry (&iter);
01806       
01807       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01808         _dbus_assert_not_reached ("hash entry should have existed");
01809       _dbus_hash_iter_remove_entry (&iter);
01810 
01811       _dbus_assert (count_entries (table1) == i);
01812       _dbus_assert (count_entries (table2) == i);
01813 
01814       --i;
01815     }
01816 
01817   _dbus_hash_table_unref (table1);
01818   _dbus_hash_table_unref (table2);
01819 
01820   ret = TRUE;
01821 
01822  out:
01823   for (i = 0; i < N_HASH_KEYS; i++)
01824     dbus_free (keys[i]);
01825 
01826   dbus_free (keys);
01827   
01828   return ret;
01829 }
01830 
01831 #endif /* DBUS_ENABLE_EMBEDDED_TESTS */