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

dbus-hash.c

00001 /* -*- mode: C; c-file-style: "gnu" -*- */
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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 "dbus-hash.h"
00078 #include "dbus-internals.h"
00079 #include "dbus-mempool.h"
00080 
00103 #define REBUILD_MULTIPLIER  3
00104 
00121 #define RANDOM_INDEX(table, i) \
00122     (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
00123 
00129 #define DBUS_SMALL_HASH_TABLE 4
00130 
00134 typedef struct DBusHashEntry DBusHashEntry;
00135 
00142 struct DBusHashEntry
00143 {
00144   DBusHashEntry *next;    
00148   void *key;              
00149   void *value;            
00150 };
00151 
00155 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable        *table,
00156                                                   void                 *key,
00157                                                   dbus_bool_t           create_if_not_found,
00158                                                   DBusHashEntry      ***bucket,
00159                                                   DBusPreallocatedHash *preallocated);
00160 
00167 struct DBusHashTable {
00168   int refcount;                       
00170   DBusHashEntry **buckets;            
00174   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
00178   int n_buckets;                       
00181   int n_entries;                       
00184   int hi_rebuild_size;                 
00187   int lo_rebuild_size;                 
00190   int down_shift;                      
00194   int mask;                            
00197   DBusHashType key_type;               
00200   DBusFindEntryFunction find_function; 
00202   DBusFreeFunction free_key_function;   
00203   DBusFreeFunction free_value_function; 
00205   DBusMemPool *entry_pool;              
00206 };
00207 
00211 typedef struct
00212 {
00213   DBusHashTable *table;     
00214   DBusHashEntry **bucket;   
00218   DBusHashEntry *entry;      
00219   DBusHashEntry *next_entry; 
00220   int next_bucket;           
00221   int n_entries_on_init;     
00222 } DBusRealHashIter;
00223 
00224 static DBusHashEntry* find_direct_function      (DBusHashTable          *table,
00225                                                  void                   *key,
00226                                                  dbus_bool_t             create_if_not_found,
00227                                                  DBusHashEntry        ***bucket,
00228                                                  DBusPreallocatedHash   *preallocated);
00229 static DBusHashEntry* find_string_function      (DBusHashTable          *table,
00230                                                  void                   *key,
00231                                                  dbus_bool_t             create_if_not_found,
00232                                                  DBusHashEntry        ***bucket,
00233                                                  DBusPreallocatedHash   *preallocated);
00234 static DBusHashEntry* find_two_strings_function (DBusHashTable          *table,
00235                                                  void                   *key,
00236                                                  dbus_bool_t             create_if_not_found,
00237                                                  DBusHashEntry        ***bucket,
00238                                                  DBusPreallocatedHash   *preallocated);
00239 static unsigned int   string_hash               (const char             *str);
00240 static unsigned int   two_strings_hash          (const char             *str);
00241 static void           rebuild_table             (DBusHashTable          *table);
00242 static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
00243 static void           remove_entry              (DBusHashTable          *table,
00244                                                  DBusHashEntry         **bucket,
00245                                                  DBusHashEntry          *entry);
00246 static void           free_entry                (DBusHashTable          *table,
00247                                                  DBusHashEntry          *entry);
00248 static void           free_entry_data           (DBusHashTable          *table,
00249                                                  DBusHashEntry          *entry);
00250 
00251 
00287 DBusHashTable*
00288 _dbus_hash_table_new (DBusHashType     type,
00289                       DBusFreeFunction key_free_function,
00290                       DBusFreeFunction value_free_function)
00291 {
00292   DBusHashTable *table;
00293   DBusMemPool *entry_pool;
00294   
00295   table = dbus_new0 (DBusHashTable, 1);
00296   if (table == NULL)
00297     return NULL;
00298 
00299   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00300   if (entry_pool == NULL)
00301     {
00302       dbus_free (table);
00303       return NULL;
00304     }
00305   
00306   table->refcount = 1;
00307   table->entry_pool = entry_pool;
00308   
00309   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00310   
00311   table->buckets = table->static_buckets;  
00312   table->n_buckets = DBUS_SMALL_HASH_TABLE;
00313   table->n_entries = 0;
00314   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00315   table->lo_rebuild_size = 0;
00316   table->down_shift = 28;
00317   table->mask = 3;
00318   table->key_type = type;
00319 
00320   _dbus_assert (table->mask < table->n_buckets);
00321   
00322   switch (table->key_type)
00323     {
00324     case DBUS_HASH_INT:
00325     case DBUS_HASH_POINTER:
00326     case DBUS_HASH_ULONG:
00327       table->find_function = find_direct_function;
00328       break;
00329     case DBUS_HASH_STRING:
00330       table->find_function = find_string_function;
00331       break;
00332     case DBUS_HASH_TWO_STRINGS:
00333       table->find_function = find_two_strings_function;
00334       break;
00335     default:
00336       _dbus_assert_not_reached ("Unknown hash table type");
00337       break;
00338     }
00339 
00340   table->free_key_function = key_free_function;
00341   table->free_value_function = value_free_function;
00342 
00343   return table;
00344 }
00345 
00346 
00353 DBusHashTable *
00354 _dbus_hash_table_ref (DBusHashTable *table)
00355 {
00356   table->refcount += 1;
00357   
00358   return table;
00359 }
00360 
00367 void
00368 _dbus_hash_table_unref (DBusHashTable *table)
00369 {
00370   table->refcount -= 1;
00371 
00372   if (table->refcount == 0)
00373     {
00374 #if 0
00375       DBusHashEntry *entry;
00376       DBusHashEntry *next;
00377       int i;
00378 
00379       /* Free the entries in the table. */
00380       for (i = 0; i < table->n_buckets; i++)
00381         {
00382           entry = table->buckets[i];
00383           while (entry != NULL)
00384             {
00385               next = entry->next;
00386 
00387               free_entry (table, entry);
00388               
00389               entry = next;
00390             }
00391         }
00392 #else
00393       DBusHashEntry *entry;
00394       int i;
00395 
00396       /* Free the entries in the table. */
00397       for (i = 0; i < table->n_buckets; i++)
00398         {
00399           entry = table->buckets[i];
00400           while (entry != NULL)
00401             {
00402               free_entry_data (table, entry);
00403               
00404               entry = entry->next;
00405             }
00406         }
00407       /* We can do this very quickly with memory pools ;-) */
00408       _dbus_mem_pool_free (table->entry_pool);
00409 #endif
00410       
00411       /* Free the bucket array, if it was dynamically allocated. */
00412       if (table->buckets != table->static_buckets)
00413         dbus_free (table->buckets);
00414 
00415       dbus_free (table);
00416     }
00417 }
00418 
00419 static DBusHashEntry*
00420 alloc_entry (DBusHashTable *table)
00421 {
00422   DBusHashEntry *entry;
00423 
00424   entry = _dbus_mem_pool_alloc (table->entry_pool);
00425   
00426   return entry;
00427 }
00428 
00429 static void
00430 free_entry_data (DBusHashTable  *table,
00431                  DBusHashEntry  *entry)
00432 {
00433   if (table->free_key_function)
00434     (* table->free_key_function) (entry->key);
00435   if (table->free_value_function)
00436     (* table->free_value_function) (entry->value);
00437 }
00438 
00439 static void
00440 free_entry (DBusHashTable  *table,
00441             DBusHashEntry  *entry)
00442 {
00443   free_entry_data (table, entry);
00444   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00445 }
00446 
00447 static void
00448 remove_entry (DBusHashTable  *table,
00449               DBusHashEntry **bucket,
00450               DBusHashEntry  *entry)
00451 {
00452   _dbus_assert (table != NULL);
00453   _dbus_assert (bucket != NULL);
00454   _dbus_assert (*bucket != NULL);  
00455   _dbus_assert (entry != NULL);
00456   
00457   if (*bucket == entry)
00458     *bucket = entry->next;
00459   else
00460     {
00461       DBusHashEntry *prev;
00462       prev = *bucket;
00463 
00464       while (prev->next != entry)
00465         prev = prev->next;      
00466       
00467       _dbus_assert (prev != NULL);
00468 
00469       prev->next = entry->next;
00470     }
00471   
00472   table->n_entries -= 1;
00473   free_entry (table, entry);
00474 }
00475 
00507 void
00508 _dbus_hash_iter_init (DBusHashTable *table,
00509                       DBusHashIter  *iter)
00510 {
00511   DBusRealHashIter *real;
00512   
00513   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00514   
00515   real = (DBusRealHashIter*) iter;
00516 
00517   real->table = table;
00518   real->bucket = NULL;
00519   real->entry = NULL;
00520   real->next_entry = NULL;
00521   real->next_bucket = 0;
00522   real->n_entries_on_init = table->n_entries;
00523 }
00524 
00533 dbus_bool_t
00534 _dbus_hash_iter_next (DBusHashIter  *iter)
00535 {
00536   DBusRealHashIter *real;
00537   
00538   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00539   
00540   real = (DBusRealHashIter*) iter;
00541 
00542   /* if this assertion failed someone probably added hash entries
00543    * during iteration, which is bad.
00544    */
00545   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00546   
00547   /* Remember that real->entry may have been deleted */
00548   
00549   while (real->next_entry == NULL)
00550     {
00551       if (real->next_bucket >= real->table->n_buckets)
00552         {
00553           /* invalidate iter and return false */
00554           real->entry = NULL;
00555           real->table = NULL;
00556           real->bucket = NULL;
00557           return FALSE;
00558         }
00559 
00560       real->bucket = &(real->table->buckets[real->next_bucket]);
00561       real->next_entry = *(real->bucket);
00562       real->next_bucket += 1;
00563     }
00564 
00565   _dbus_assert (real->next_entry != NULL);
00566   _dbus_assert (real->bucket != NULL);
00567   
00568   real->entry = real->next_entry;
00569   real->next_entry = real->entry->next;
00570   
00571   return TRUE;
00572 }
00573 
00582 void
00583 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00584 {
00585   DBusRealHashIter *real;
00586 
00587   real = (DBusRealHashIter*) iter;
00588 
00589   _dbus_assert (real->table != NULL);
00590   _dbus_assert (real->entry != NULL);
00591   _dbus_assert (real->bucket != NULL);
00592   
00593   remove_entry (real->table, real->bucket, real->entry);
00594 
00595   real->entry = NULL; /* make it crash if you try to use this entry */
00596 }
00597 
00603 void*
00604 _dbus_hash_iter_get_value (DBusHashIter *iter)
00605 {
00606   DBusRealHashIter *real;
00607 
00608   real = (DBusRealHashIter*) iter;
00609 
00610   _dbus_assert (real->table != NULL);
00611   _dbus_assert (real->entry != NULL);
00612 
00613   return real->entry->value;
00614 }
00615 
00626 void
00627 _dbus_hash_iter_set_value (DBusHashIter *iter,
00628                            void         *value)
00629 {
00630   DBusRealHashIter *real;
00631 
00632   real = (DBusRealHashIter*) iter;
00633 
00634   _dbus_assert (real->table != NULL);
00635   _dbus_assert (real->entry != NULL);
00636 
00637   if (real->table->free_value_function && value != real->entry->value)    
00638     (* real->table->free_value_function) (real->entry->value);
00639   
00640   real->entry->value = value;
00641 }
00642 
00649 int
00650 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00651 {
00652   DBusRealHashIter *real;
00653 
00654   real = (DBusRealHashIter*) iter;
00655 
00656   _dbus_assert (real->table != NULL);
00657   _dbus_assert (real->entry != NULL);
00658 
00659   return _DBUS_POINTER_TO_INT (real->entry->key);
00660 }
00661 
00668 unsigned long
00669 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
00670 {
00671   DBusRealHashIter *real;
00672 
00673   real = (DBusRealHashIter*) iter;
00674 
00675   _dbus_assert (real->table != NULL);
00676   _dbus_assert (real->entry != NULL);
00677 
00678   return (unsigned long) real->entry->key;
00679 }
00680 
00686 const char*
00687 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00688 {
00689   DBusRealHashIter *real;
00690 
00691   real = (DBusRealHashIter*) iter;
00692 
00693   _dbus_assert (real->table != NULL);
00694   _dbus_assert (real->entry != NULL);
00695 
00696   return real->entry->key;
00697 }
00698 
00704 const char*
00705 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
00706 {
00707   DBusRealHashIter *real;
00708 
00709   real = (DBusRealHashIter*) iter;
00710 
00711   _dbus_assert (real->table != NULL);
00712   _dbus_assert (real->entry != NULL);
00713 
00714   return real->entry->key;
00715 }
00716 
00748 dbus_bool_t
00749 _dbus_hash_iter_lookup (DBusHashTable *table,
00750                         void          *key,
00751                         dbus_bool_t    create_if_not_found,
00752                         DBusHashIter  *iter)
00753 {
00754   DBusRealHashIter *real;
00755   DBusHashEntry *entry;
00756   DBusHashEntry **bucket;
00757   
00758   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00759   
00760   real = (DBusRealHashIter*) iter;
00761 
00762   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00763 
00764   if (entry == NULL)
00765     return FALSE;
00766   
00767   real->table = table;
00768   real->bucket = bucket;
00769   real->entry = entry;
00770   real->next_entry = entry->next;
00771   real->next_bucket = (bucket - table->buckets) + 1;
00772   real->n_entries_on_init = table->n_entries; 
00773 
00774   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00775   
00776   return TRUE;
00777 }
00778 
00779 static void
00780 add_allocated_entry (DBusHashTable   *table,
00781                      DBusHashEntry   *entry,
00782                      unsigned int     idx,
00783                      void            *key,
00784                      DBusHashEntry ***bucket)
00785 {
00786   DBusHashEntry **b;  
00787   
00788   entry->key = key;
00789   
00790   b = &(table->buckets[idx]);
00791   entry->next = *b;
00792   *b = entry;
00793 
00794   if (bucket)
00795     *bucket = b;
00796   
00797   table->n_entries += 1;
00798 
00799   /* note we ONLY rebuild when ADDING - because you can iterate over a
00800    * table and remove entries safely.
00801    */
00802   if (table->n_entries >= table->hi_rebuild_size ||
00803       table->n_entries < table->lo_rebuild_size)
00804     rebuild_table (table);
00805 }
00806 
00807 static DBusHashEntry*
00808 add_entry (DBusHashTable        *table, 
00809            unsigned int          idx,
00810            void                 *key,
00811            DBusHashEntry      ***bucket,
00812            DBusPreallocatedHash *preallocated)
00813 {
00814   DBusHashEntry  *entry;
00815 
00816   if (preallocated == NULL)
00817     {
00818       entry = alloc_entry (table);
00819       if (entry == NULL)
00820         {
00821           if (bucket)
00822             *bucket = NULL;
00823           return NULL;
00824         }
00825     }
00826   else
00827     {
00828       entry = (DBusHashEntry*) preallocated;
00829     }
00830 
00831   add_allocated_entry (table, entry, idx, key, bucket);
00832 
00833   return entry;
00834 }
00835 
00836 /* This is g_str_hash from GLib which was
00837  * extensively discussed/tested/profiled
00838  */
00839 static unsigned int
00840 string_hash (const char *str)
00841 {
00842   const char *p = str;
00843   unsigned int h = *p;
00844 
00845   if (h)
00846     for (p += 1; *p != '\0'; p++)
00847       h = (h << 5) - h + *p;
00848 
00849   return h;
00850 }
00851 
00852 /* This hashes a memory block with two nul-terminated strings
00853  * in it, used in dbus-object-registry.c at the moment.
00854  */
00855 static unsigned int
00856 two_strings_hash (const char *str)
00857 {
00858   const char *p = str;
00859   unsigned int h = *p;
00860 
00861   if (h)
00862     for (p += 1; *p != '\0'; p++)
00863       h = (h << 5) - h + *p;
00864 
00865   for (p += 1; *p != '\0'; p++)
00866     h = (h << 5) - h + *p;
00867   
00868   return h;
00869 }
00870 
00872 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00873 
00874 static DBusHashEntry*
00875 find_generic_function (DBusHashTable        *table,
00876                        void                 *key,
00877                        unsigned int          idx,
00878                        KeyCompareFunc        compare_func,
00879                        dbus_bool_t           create_if_not_found,
00880                        DBusHashEntry      ***bucket,
00881                        DBusPreallocatedHash *preallocated)
00882 {
00883   DBusHashEntry *entry;
00884 
00885   if (bucket)
00886     *bucket = NULL;
00887 
00888   /* Search all of the entries in this bucket. */
00889   entry = table->buckets[idx];
00890   while (entry != NULL)
00891     {
00892       if ((compare_func == NULL && key == entry->key) ||
00893           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00894         {
00895           if (bucket)
00896             *bucket = &(table->buckets[idx]);
00897 
00898           if (preallocated)
00899             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00900           
00901           return entry;
00902         }
00903       
00904       entry = entry->next;
00905     }
00906 
00907   if (create_if_not_found)
00908     entry = add_entry (table, idx, key, bucket, preallocated);
00909   else if (preallocated)
00910     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00911   
00912   return entry;
00913 }
00914 
00915 static DBusHashEntry*
00916 find_string_function (DBusHashTable        *table,
00917                       void                 *key,
00918                       dbus_bool_t           create_if_not_found,
00919                       DBusHashEntry      ***bucket,
00920                       DBusPreallocatedHash *preallocated)
00921 {
00922   unsigned int idx;
00923   
00924   idx = string_hash (key) & table->mask;
00925 
00926   return find_generic_function (table, key, idx,
00927                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00928                                 preallocated);
00929 }
00930 
00931 static int
00932 two_strings_cmp (const char *a,
00933                  const char *b)
00934 {
00935   size_t len_a;
00936   size_t len_b;
00937   int res;
00938   
00939   res = strcmp (a, b);
00940   if (res != 0)
00941     return res;
00942 
00943   len_a = strlen (a);
00944   len_b = strlen (b);
00945 
00946   return strcmp (a + len_a + 1, b + len_b + 1);
00947 }
00948 
00949 static DBusHashEntry*
00950 find_two_strings_function (DBusHashTable        *table,
00951                            void                 *key,
00952                            dbus_bool_t           create_if_not_found,
00953                            DBusHashEntry      ***bucket,
00954                            DBusPreallocatedHash *preallocated)
00955 {
00956   unsigned int idx;
00957   
00958   idx = two_strings_hash (key) & table->mask;
00959 
00960   return find_generic_function (table, key, idx,
00961                                 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
00962                                 preallocated);
00963 }
00964 
00965 static DBusHashEntry*
00966 find_direct_function (DBusHashTable        *table,
00967                       void                 *key,
00968                       dbus_bool_t           create_if_not_found,
00969                       DBusHashEntry      ***bucket,
00970                       DBusPreallocatedHash *preallocated)
00971 {
00972   unsigned int idx;
00973   
00974   idx = RANDOM_INDEX (table, key) & table->mask;
00975 
00976 
00977   return find_generic_function (table, key, idx,
00978                                 NULL, create_if_not_found, bucket,
00979                                 preallocated);
00980 }
00981 
00982 static void
00983 rebuild_table (DBusHashTable *table)
00984 {
00985   int old_size;
00986   int new_buckets;
00987   DBusHashEntry **old_buckets;
00988   DBusHashEntry **old_chain;
00989   DBusHashEntry *entry;
00990   dbus_bool_t growing;
00991   
00992   /*
00993    * Allocate and initialize the new bucket array, and set up
00994    * hashing constants for new array size.
00995    */
00996 
00997   growing = table->n_entries >= table->hi_rebuild_size;
00998   
00999   old_size = table->n_buckets;
01000   old_buckets = table->buckets;
01001 
01002   if (growing)
01003     {
01004       /* overflow paranoia */
01005       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
01006           table->down_shift >= 0)
01007         new_buckets = table->n_buckets * 4;
01008       else
01009         return; /* can't grow anymore */
01010     }
01011   else
01012     {
01013       new_buckets = table->n_buckets / 4;
01014       if (new_buckets < DBUS_SMALL_HASH_TABLE)
01015         return; /* don't bother shrinking this far */
01016     }
01017 
01018   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
01019   if (table->buckets == NULL)
01020     {
01021       /* out of memory, yay - just don't reallocate, the table will
01022        * still work, albeit more slowly.
01023        */
01024       table->buckets = old_buckets;
01025       return;
01026     }
01027 
01028   table->n_buckets = new_buckets;
01029   
01030   if (growing)
01031     {
01032       table->lo_rebuild_size = table->hi_rebuild_size;
01033       table->hi_rebuild_size *= 4;
01034       
01035       table->down_shift -= 2;               /* keep 2 more high bits */
01036       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
01037     }
01038   else
01039     {
01040       table->hi_rebuild_size = table->lo_rebuild_size;
01041       table->lo_rebuild_size /= 4;
01042 
01043       table->down_shift += 2;         /* keep 2 fewer high bits */
01044       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
01045     }
01046 
01047 #if 0
01048   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
01049           growing ? "GROW" : "SHRINK",
01050           table->lo_rebuild_size,
01051           table->hi_rebuild_size,
01052           table->down_shift,
01053           table->mask);
01054 #endif
01055   
01056   _dbus_assert (table->lo_rebuild_size >= 0);
01057   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01058   _dbus_assert (table->mask != 0);
01059   /* the mask is essentially the max index */
01060   _dbus_assert (table->mask < table->n_buckets);
01061   
01062   /*
01063    * Rehash all of the existing entries into the new bucket array.
01064    */
01065 
01066   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01067     {
01068       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01069         {
01070           unsigned int idx;
01071           DBusHashEntry **bucket;
01072           
01073           *old_chain = entry->next;
01074           switch (table->key_type)
01075             {
01076             case DBUS_HASH_STRING:
01077               idx = string_hash (entry->key) & table->mask;
01078               break;
01079             case DBUS_HASH_TWO_STRINGS:
01080               idx = two_strings_hash (entry->key) & table->mask;
01081               break;
01082             case DBUS_HASH_INT:
01083             case DBUS_HASH_ULONG:
01084             case DBUS_HASH_POINTER:
01085               idx = RANDOM_INDEX (table, entry->key);
01086               break;
01087             default:
01088               idx = 0;
01089               _dbus_assert_not_reached ("Unknown hash table type");
01090               break;
01091             }
01092           
01093           bucket = &(table->buckets[idx]);
01094           entry->next = *bucket;
01095           *bucket = entry;
01096         }
01097     }
01098   
01099   /* Free the old bucket array, if it was dynamically allocated. */
01100 
01101   if (old_buckets != table->static_buckets)
01102     dbus_free (old_buckets);
01103 }
01104 
01114 void*
01115 _dbus_hash_table_lookup_string (DBusHashTable *table,
01116                                 const char    *key)
01117 {
01118   DBusHashEntry *entry;
01119 
01120   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01121   
01122   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01123 
01124   if (entry)
01125     return entry->value;
01126   else
01127     return NULL;
01128 }
01129 
01139 void*
01140 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
01141                                      const char    *key)
01142 {
01143   DBusHashEntry *entry;
01144 
01145   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01146   
01147   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01148 
01149   if (entry)
01150     return entry->value;
01151   else
01152     return NULL;
01153 }
01154 
01164 void*
01165 _dbus_hash_table_lookup_int (DBusHashTable *table,
01166                              int            key)
01167 {
01168   DBusHashEntry *entry;
01169 
01170   _dbus_assert (table->key_type == DBUS_HASH_INT);
01171   
01172   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01173 
01174   if (entry)
01175     return entry->value;
01176   else
01177     return NULL;
01178 }
01179 
01180 #ifdef DBUS_BUILD_TESTS
01181 /* disabled since it's only used for testing */
01191 void*
01192 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01193                                  void          *key)
01194 {
01195   DBusHashEntry *entry;
01196 
01197   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01198   
01199   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01200 
01201   if (entry)
01202     return entry->value;
01203   else
01204     return NULL;
01205 }
01206 #endif /* DBUS_BUILD_TESTS */
01207 
01217 void*
01218 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
01219                                unsigned long  key)
01220 {
01221   DBusHashEntry *entry;
01222 
01223   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01224   
01225   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01226 
01227   if (entry)
01228     return entry->value;
01229   else
01230     return NULL;
01231 }
01232 
01241 dbus_bool_t
01242 _dbus_hash_table_remove_string (DBusHashTable *table,
01243                                 const char    *key)
01244 {
01245   DBusHashEntry *entry;
01246   DBusHashEntry **bucket;
01247   
01248   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01249   
01250   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01251 
01252   if (entry)
01253     {
01254       remove_entry (table, bucket, entry);
01255       return TRUE;
01256     }
01257   else
01258     return FALSE;
01259 }
01260 
01269 dbus_bool_t
01270 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
01271                                      const char    *key)
01272 {
01273   DBusHashEntry *entry;
01274   DBusHashEntry **bucket;
01275   
01276   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01277   
01278   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01279 
01280   if (entry)
01281     {
01282       remove_entry (table, bucket, entry);
01283       return TRUE;
01284     }
01285   else
01286     return FALSE;
01287 }
01288 
01297 dbus_bool_t
01298 _dbus_hash_table_remove_int (DBusHashTable *table,
01299                              int            key)
01300 {
01301   DBusHashEntry *entry;
01302   DBusHashEntry **bucket;
01303   
01304   _dbus_assert (table->key_type == DBUS_HASH_INT);
01305   
01306   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01307   
01308   if (entry)
01309     {
01310       remove_entry (table, bucket, entry);
01311       return TRUE;
01312     }
01313   else
01314     return FALSE;
01315 }
01316 
01317 #ifdef DBUS_BUILD_TESTS
01318 /* disabled since it's only used for testing */
01327 dbus_bool_t
01328 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01329                                  void          *key)
01330 {
01331   DBusHashEntry *entry;
01332   DBusHashEntry **bucket;
01333   
01334   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01335   
01336   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01337   
01338   if (entry)
01339     {
01340       remove_entry (table, bucket, entry);
01341       return TRUE;
01342     }
01343   else
01344     return FALSE;
01345 }
01346 #endif /* DBUS_BUILD_TESTS */
01347 
01356 dbus_bool_t
01357 _dbus_hash_table_remove_ulong (DBusHashTable *table,
01358                                unsigned long  key)
01359 {
01360   DBusHashEntry *entry;
01361   DBusHashEntry **bucket;
01362   
01363   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01364   
01365   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01366   
01367   if (entry)
01368     {
01369       remove_entry (table, bucket, entry);
01370       return TRUE;
01371     }
01372   else
01373     return FALSE;
01374 }
01375 
01391 dbus_bool_t
01392 _dbus_hash_table_insert_string (DBusHashTable *table,
01393                                 char          *key,
01394                                 void          *value)
01395 {
01396   DBusPreallocatedHash *preallocated;
01397 
01398   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01399 
01400   preallocated = _dbus_hash_table_preallocate_entry (table);
01401   if (preallocated == NULL)
01402     return FALSE;
01403 
01404   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01405                                                key, value);
01406   
01407   return TRUE;
01408 }
01409 
01425 dbus_bool_t
01426 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
01427                                      char          *key,
01428                                      void          *value)
01429 {
01430   DBusHashEntry *entry;
01431   
01432   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01433   
01434   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01435 
01436   if (entry == NULL)
01437     return FALSE; /* no memory */
01438 
01439   if (table->free_key_function && entry->key != key)
01440     (* table->free_key_function) (entry->key);
01441   
01442   if (table->free_value_function && entry->value != value)
01443     (* table->free_value_function) (entry->value);
01444   
01445   entry->key = key;
01446   entry->value = value;
01447 
01448   return TRUE;
01449 }
01450 
01466 dbus_bool_t
01467 _dbus_hash_table_insert_int (DBusHashTable *table,
01468                              int            key,
01469                              void          *value)
01470 {
01471   DBusHashEntry *entry;
01472 
01473   _dbus_assert (table->key_type == DBUS_HASH_INT);
01474   
01475   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01476 
01477   if (entry == NULL)
01478     return FALSE; /* no memory */
01479 
01480   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01481     (* table->free_key_function) (entry->key);
01482   
01483   if (table->free_value_function && entry->value != value)
01484     (* table->free_value_function) (entry->value);
01485   
01486   entry->key = _DBUS_INT_TO_POINTER (key);
01487   entry->value = value;
01488 
01489   return TRUE;
01490 }
01491 
01492 #ifdef DBUS_BUILD_TESTS
01493 /* disabled since it's only used for testing */
01509 dbus_bool_t
01510 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01511                                  void          *key,
01512                                  void          *value)
01513 {
01514   DBusHashEntry *entry;
01515 
01516   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01517   
01518   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01519 
01520   if (entry == NULL)
01521     return FALSE; /* no memory */
01522 
01523   if (table->free_key_function && entry->key != key)
01524     (* table->free_key_function) (entry->key);
01525   
01526   if (table->free_value_function && entry->value != value)
01527     (* table->free_value_function) (entry->value);
01528   
01529   entry->key = key;
01530   entry->value = value;
01531 
01532   return TRUE;
01533 }
01534 #endif /* DBUS_BUILD_TESTS */
01535 
01551 dbus_bool_t
01552 _dbus_hash_table_insert_ulong (DBusHashTable *table,
01553                                unsigned long  key,
01554                                void          *value)
01555 {
01556   DBusHashEntry *entry;
01557 
01558   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01559   
01560   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01561 
01562   if (entry == NULL)
01563     return FALSE; /* no memory */
01564 
01565   if (table->free_key_function && entry->key != (void*) key)
01566     (* table->free_key_function) (entry->key);
01567   
01568   if (table->free_value_function && entry->value != value)
01569     (* table->free_value_function) (entry->value);
01570   
01571   entry->key = (void*) key;
01572   entry->value = value;
01573 
01574   return TRUE;
01575 }
01576 
01584 DBusPreallocatedHash*
01585 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01586 {
01587   DBusHashEntry *entry;
01588   
01589   entry = alloc_entry (table);
01590 
01591   return (DBusPreallocatedHash*) entry;
01592 }
01593 
01601 void
01602 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01603                                           DBusPreallocatedHash *preallocated)
01604 {
01605   DBusHashEntry *entry;
01606 
01607   _dbus_assert (preallocated != NULL);
01608   
01609   entry = (DBusHashEntry*) preallocated;
01610   
01611   /* Don't use free_entry(), since this entry has no key/data */
01612   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01613 }
01614 
01628 void
01629 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01630                                              DBusPreallocatedHash *preallocated,
01631                                              char                 *key,
01632                                              void                 *value)
01633 {
01634   DBusHashEntry *entry;
01635 
01636   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01637   _dbus_assert (preallocated != NULL);
01638   
01639   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01640 
01641   _dbus_assert (entry != NULL);
01642   
01643   if (table->free_key_function && entry->key != key)
01644     (* table->free_key_function) (entry->key);
01645 
01646   if (table->free_value_function && entry->value != value)
01647     (* table->free_value_function) (entry->value);
01648       
01649   entry->key = key;
01650   entry->value = value;
01651 }
01652 
01659 int
01660 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01661 {
01662   return table->n_entries;
01663 }
01664 
01667 #ifdef DBUS_BUILD_TESTS
01668 #include "dbus-test.h"
01669 #include <stdio.h>
01670 
01671 /* If you're wondering why the hash table test takes
01672  * forever to run, it's because we call this function
01673  * in inner loops thus making things quadratic.
01674  */
01675 static int
01676 count_entries (DBusHashTable *table)
01677 {
01678   DBusHashIter iter;
01679   int count;
01680 
01681   count = 0;
01682   _dbus_hash_iter_init (table, &iter);
01683   while (_dbus_hash_iter_next (&iter))
01684     ++count;
01685 
01686   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01687   
01688   return count;
01689 }
01690 
01691 /* Copy the foo\0bar\0 double string thing */
01692 static char*
01693 _dbus_strdup2 (const char *str)
01694 {
01695   size_t len;
01696   char *copy;
01697   
01698   if (str == NULL)
01699     return NULL;
01700   
01701   len = strlen (str);
01702   len += strlen ((str + len + 1));
01703 
01704   copy = dbus_malloc (len + 2);
01705   if (copy == NULL)
01706     return NULL;
01707 
01708   memcpy (copy, str, len + 2);
01709   
01710   return copy;
01711 }
01712 
01718 dbus_bool_t
01719 _dbus_hash_test (void)
01720 {
01721   int i;
01722   DBusHashTable *table1;
01723   DBusHashTable *table2;
01724   DBusHashTable *table3;
01725   DBusHashTable *table4;
01726   DBusHashIter iter;
01727 #define N_HASH_KEYS 5000
01728   char **keys;
01729   dbus_bool_t ret = FALSE;
01730 
01731   keys = dbus_new (char *, N_HASH_KEYS);
01732   if (keys == NULL)
01733     _dbus_assert_not_reached ("no memory");
01734 
01735   for (i = 0; i < N_HASH_KEYS; i++)
01736     {
01737       keys[i] = dbus_malloc (128);
01738 
01739       if (keys[i] == NULL)
01740         _dbus_assert_not_reached ("no memory");
01741     }
01742 
01743   printf ("Computing test hash keys...\n");
01744   i = 0;
01745   while (i < N_HASH_KEYS)
01746     {
01747       int len;
01748 
01749       /* all the hash keys are TWO_STRINGS, but
01750        * then we can also use those as regular strings.
01751        */
01752       
01753       len = sprintf (keys[i], "Hash key %d", i);
01754       sprintf (keys[i] + len + 1, "Two string %d", i);
01755       _dbus_assert (*(keys[i] + len) == '\0');
01756       _dbus_assert (*(keys[i] + len + 1) != '\0');
01757       ++i;
01758     }
01759   printf ("... done.\n");
01760   
01761   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01762                                  dbus_free, dbus_free);
01763   if (table1 == NULL)
01764     goto out;
01765 
01766   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01767                                  NULL, dbus_free);
01768   if (table2 == NULL)
01769     goto out;
01770 
01771   table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
01772                                  NULL, dbus_free);
01773   if (table3 == NULL)
01774     goto out;
01775 
01776   table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
01777                                  dbus_free, dbus_free);
01778   if (table4 == NULL)
01779     goto out;
01780 
01781   
01782   /* Insert and remove a bunch of stuff, counting the table in between
01783    * to be sure it's not broken and that iteration works
01784    */
01785   i = 0;
01786   while (i < 3000)
01787     {
01788       void *value;
01789       char *key;
01790 
01791       key = _dbus_strdup (keys[i]);
01792       if (key == NULL)
01793         goto out;
01794       value = _dbus_strdup ("Value!");
01795       if (value == NULL)
01796         goto out;
01797       
01798       if (!_dbus_hash_table_insert_string (table1,
01799                                            key, value))
01800         goto out;
01801 
01802       value = _dbus_strdup (keys[i]);
01803       if (value == NULL)
01804         goto out;
01805       
01806       if (!_dbus_hash_table_insert_int (table2,
01807                                         i, value))
01808         goto out;
01809 
01810       value = _dbus_strdup (keys[i]);
01811       if (value == NULL)
01812         goto out;
01813       
01814       if (!_dbus_hash_table_insert_ulong (table3,
01815                                           i, value))
01816         goto out;
01817 
01818       key = _dbus_strdup2 (keys[i]);
01819       if (key == NULL)
01820         goto out;
01821       value = _dbus_strdup ("Value!");
01822       if (value == NULL)
01823         goto out;
01824       
01825       if (!_dbus_hash_table_insert_two_strings (table4,
01826                                                 key, value))
01827         goto out;
01828       
01829       _dbus_assert (count_entries (table1) == i + 1);
01830       _dbus_assert (count_entries (table2) == i + 1);
01831       _dbus_assert (count_entries (table3) == i + 1);
01832       _dbus_assert (count_entries (table4) == i + 1);
01833 
01834       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01835       _dbus_assert (value != NULL);
01836       _dbus_assert (strcmp (value, "Value!") == 0);
01837 
01838       value = _dbus_hash_table_lookup_int (table2, i);
01839       _dbus_assert (value != NULL);
01840       _dbus_assert (strcmp (value, keys[i]) == 0);
01841 
01842       value = _dbus_hash_table_lookup_ulong (table3, i);
01843       _dbus_assert (value != NULL);
01844       _dbus_assert (strcmp (value, keys[i]) == 0);
01845 
01846       value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01847       _dbus_assert (value != NULL);
01848       _dbus_assert (strcmp (value, "Value!") == 0);
01849       
01850       ++i;
01851     }
01852 
01853   --i;
01854   while (i >= 0)
01855     {
01856       _dbus_hash_table_remove_string (table1,
01857                                       keys[i]);
01858 
01859       _dbus_hash_table_remove_int (table2, i);
01860 
01861       _dbus_hash_table_remove_ulong (table3, i); 
01862 
01863       _dbus_hash_table_remove_two_strings (table4,
01864                                            keys[i]);
01865       
01866       _dbus_assert (count_entries (table1) == i);
01867       _dbus_assert (count_entries (table2) == i);
01868       _dbus_assert (count_entries (table3) == i);
01869       _dbus_assert (count_entries (table4) == i);
01870 
01871       --i;
01872     }
01873 
01874   _dbus_hash_table_ref (table1);
01875   _dbus_hash_table_ref (table2);
01876   _dbus_hash_table_ref (table3);
01877   _dbus_hash_table_ref (table4);
01878   _dbus_hash_table_unref (table1);
01879   _dbus_hash_table_unref (table2);
01880   _dbus_hash_table_unref (table3);
01881   _dbus_hash_table_unref (table4);
01882   _dbus_hash_table_unref (table1);
01883   _dbus_hash_table_unref (table2);
01884   _dbus_hash_table_unref (table3);
01885   _dbus_hash_table_unref (table4);
01886   table3 = NULL;
01887 
01888   /* Insert a bunch of stuff then check
01889    * that iteration works correctly (finds the right
01890    * values, iter_set_value works, etc.)
01891    */
01892   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01893                                  dbus_free, dbus_free);
01894   if (table1 == NULL)
01895     goto out;
01896   
01897   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01898                                  NULL, dbus_free);
01899   if (table2 == NULL)
01900     goto out;
01901   
01902   i = 0;
01903   while (i < 5000)
01904     {
01905       char *key;
01906       void *value;      
01907       
01908       key = _dbus_strdup (keys[i]);
01909       if (key == NULL)
01910         goto out;
01911       value = _dbus_strdup ("Value!");
01912       if (value == NULL)
01913         goto out;
01914       
01915       if (!_dbus_hash_table_insert_string (table1,
01916                                            key, value))
01917         goto out;
01918 
01919       value = _dbus_strdup (keys[i]);
01920       if (value == NULL)
01921         goto out;
01922       
01923       if (!_dbus_hash_table_insert_int (table2,
01924                                         i, value))
01925         goto out;
01926       
01927       _dbus_assert (count_entries (table1) == i + 1);
01928       _dbus_assert (count_entries (table2) == i + 1);
01929       
01930       ++i;
01931     }
01932 
01933   _dbus_hash_iter_init (table1, &iter);
01934   while (_dbus_hash_iter_next (&iter))
01935     {
01936       const char *key;
01937       void *value;
01938 
01939       key = _dbus_hash_iter_get_string_key (&iter);
01940       value = _dbus_hash_iter_get_value (&iter);
01941 
01942       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01943 
01944       value = _dbus_strdup ("Different value!");
01945       if (value == NULL)
01946         goto out;
01947       
01948       _dbus_hash_iter_set_value (&iter, value);
01949 
01950       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01951     }
01952   
01953   _dbus_hash_iter_init (table1, &iter);
01954   while (_dbus_hash_iter_next (&iter))
01955     {
01956       _dbus_hash_iter_remove_entry (&iter);
01957       _dbus_assert (count_entries (table1) == i - 1);
01958       --i;
01959     }
01960 
01961   _dbus_hash_iter_init (table2, &iter);
01962   while (_dbus_hash_iter_next (&iter))
01963     {
01964       int key;
01965       void *value;
01966 
01967       key = _dbus_hash_iter_get_int_key (&iter);
01968       value = _dbus_hash_iter_get_value (&iter);
01969 
01970       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01971 
01972       value = _dbus_strdup ("Different value!");
01973       if (value == NULL)
01974         goto out;
01975       
01976       _dbus_hash_iter_set_value (&iter, value);
01977 
01978       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01979     }
01980 
01981   i = count_entries (table2);
01982   _dbus_hash_iter_init (table2, &iter);
01983   while (_dbus_hash_iter_next (&iter))
01984     {
01985       _dbus_hash_iter_remove_entry (&iter);
01986       _dbus_assert (count_entries (table2) + 1 == i);
01987       --i;
01988     }
01989 
01990   /* add/remove interleaved, to check that we grow/shrink the table
01991    * appropriately
01992    */
01993   i = 0;
01994   while (i < 1000)
01995     {
01996       char *key;
01997       void *value;
01998             
01999       key = _dbus_strdup (keys[i]);
02000       if (key == NULL)
02001         goto out;
02002 
02003       value = _dbus_strdup ("Value!");
02004       if (value == NULL)
02005         goto out;
02006       
02007       if (!_dbus_hash_table_insert_string (table1,
02008                                            key, value))
02009         goto out;
02010       
02011       ++i;
02012     }
02013 
02014   --i;
02015   while (i >= 0)
02016     {
02017       char *key;
02018       void *value;      
02019       
02020       key = _dbus_strdup (keys[i]);
02021       if (key == NULL)
02022         goto out;
02023       value = _dbus_strdup ("Value!");
02024       if (value == NULL)
02025         goto out;
02026 
02027       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02028         goto out;
02029       
02030       if (!_dbus_hash_table_insert_string (table1,
02031                                            key, value))
02032         goto out;
02033 
02034       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02035         goto out;
02036       
02037       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
02038       
02039       --i;
02040     }
02041 
02042   /* nuke these tables */
02043   _dbus_hash_table_unref (table1);
02044   _dbus_hash_table_unref (table2);
02045 
02046 
02047   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
02048    * be sure that interface works.
02049    */
02050   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
02051                                  dbus_free, dbus_free);
02052   if (table1 == NULL)
02053     goto out;
02054   
02055   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
02056                                  NULL, dbus_free);
02057   if (table2 == NULL)
02058     goto out;
02059   
02060   i = 0;
02061   while (i < 3000)
02062     {
02063       void *value;
02064       char *key;
02065 
02066       key = _dbus_strdup (keys[i]);
02067       if (key == NULL)
02068         goto out;
02069       value = _dbus_strdup ("Value!");
02070       if (value == NULL)
02071         goto out;
02072       
02073       if (!_dbus_hash_iter_lookup (table1,
02074                                    key, TRUE, &iter))
02075         goto out;
02076       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02077       _dbus_hash_iter_set_value (&iter, value);
02078 
02079       value = _dbus_strdup (keys[i]);
02080       if (value == NULL)
02081         goto out;
02082 
02083       if (!_dbus_hash_iter_lookup (table2,
02084                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
02085         goto out;
02086       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02087       _dbus_hash_iter_set_value (&iter, value); 
02088       
02089       _dbus_assert (count_entries (table1) == i + 1);
02090       _dbus_assert (count_entries (table2) == i + 1);
02091 
02092       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02093         goto out;
02094       
02095       value = _dbus_hash_iter_get_value (&iter);
02096       _dbus_assert (value != NULL);
02097       _dbus_assert (strcmp (value, "Value!") == 0);
02098 
02099       /* Iterate just to be sure it works, though
02100        * it's a stupid thing to do
02101        */
02102       while (_dbus_hash_iter_next (&iter))
02103         ;
02104       
02105       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02106         goto out;
02107 
02108       value = _dbus_hash_iter_get_value (&iter);
02109       _dbus_assert (value != NULL);
02110       _dbus_assert (strcmp (value, keys[i]) == 0);
02111 
02112       /* Iterate just to be sure it works, though
02113        * it's a stupid thing to do
02114        */
02115       while (_dbus_hash_iter_next (&iter))
02116         ;
02117       
02118       ++i;
02119     }
02120 
02121   --i;
02122   while (i >= 0)
02123     {
02124       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02125         _dbus_assert_not_reached ("hash entry should have existed");
02126       _dbus_hash_iter_remove_entry (&iter);
02127       
02128       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02129         _dbus_assert_not_reached ("hash entry should have existed");
02130       _dbus_hash_iter_remove_entry (&iter);
02131 
02132       _dbus_assert (count_entries (table1) == i);
02133       _dbus_assert (count_entries (table2) == i);
02134 
02135       --i;
02136     }
02137 
02138   _dbus_hash_table_unref (table1);
02139   _dbus_hash_table_unref (table2);
02140 
02141   ret = TRUE;
02142 
02143  out:
02144   for (i = 0; i < N_HASH_KEYS; i++)
02145     dbus_free (keys[i]);
02146 
02147   dbus_free (keys);
02148   
02149   return ret;
02150 }
02151 
02152 #endif /* DBUS_BUILD_TESTS */

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