Main Page | Modules | Namespace List | Class Hierarchy | Data Structures | Directories | File List | Namespace Members | 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 #ifdef DBUS_BUILD_TESTS
00235 static DBusHashEntry* find_two_strings_function (DBusHashTable          *table,
00236                                                  void                   *key,
00237                                                  dbus_bool_t             create_if_not_found,
00238                                                  DBusHashEntry        ***bucket,
00239                                                  DBusPreallocatedHash   *preallocated);
00240 #endif
00241 static unsigned int   string_hash               (const char             *str);
00242 #ifdef DBUS_BUILD_TESTS
00243 static unsigned int   two_strings_hash          (const char             *str);
00244 #endif
00245 static void           rebuild_table             (DBusHashTable          *table);
00246 static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
00247 static void           remove_entry              (DBusHashTable          *table,
00248                                                  DBusHashEntry         **bucket,
00249                                                  DBusHashEntry          *entry);
00250 static void           free_entry                (DBusHashTable          *table,
00251                                                  DBusHashEntry          *entry);
00252 static void           free_entry_data           (DBusHashTable          *table,
00253                                                  DBusHashEntry          *entry);
00254 
00255 
00291 DBusHashTable*
00292 _dbus_hash_table_new (DBusHashType     type,
00293                       DBusFreeFunction key_free_function,
00294                       DBusFreeFunction value_free_function)
00295 {
00296   DBusHashTable *table;
00297   DBusMemPool *entry_pool;
00298   
00299   table = dbus_new0 (DBusHashTable, 1);
00300   if (table == NULL)
00301     return NULL;
00302 
00303   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00304   if (entry_pool == NULL)
00305     {
00306       dbus_free (table);
00307       return NULL;
00308     }
00309   
00310   table->refcount = 1;
00311   table->entry_pool = entry_pool;
00312   
00313   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00314   
00315   table->buckets = table->static_buckets;  
00316   table->n_buckets = DBUS_SMALL_HASH_TABLE;
00317   table->n_entries = 0;
00318   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00319   table->lo_rebuild_size = 0;
00320   table->down_shift = 28;
00321   table->mask = 3;
00322   table->key_type = type;
00323 
00324   _dbus_assert (table->mask < table->n_buckets);
00325   
00326   switch (table->key_type)
00327     {
00328     case DBUS_HASH_INT:
00329     case DBUS_HASH_POINTER:
00330     case DBUS_HASH_ULONG:
00331       table->find_function = find_direct_function;
00332       break;
00333     case DBUS_HASH_STRING:
00334       table->find_function = find_string_function;
00335       break;
00336     case DBUS_HASH_TWO_STRINGS:
00337 #ifdef DBUS_BUILD_TESTS
00338       table->find_function = find_two_strings_function;
00339 #endif
00340       break;
00341     default:
00342       _dbus_assert_not_reached ("Unknown hash table type");
00343       break;
00344     }
00345 
00346   table->free_key_function = key_free_function;
00347   table->free_value_function = value_free_function;
00348 
00349   return table;
00350 }
00351 
00352 
00359 DBusHashTable *
00360 _dbus_hash_table_ref (DBusHashTable *table)
00361 {
00362   table->refcount += 1;
00363   
00364   return table;
00365 }
00366 
00373 void
00374 _dbus_hash_table_unref (DBusHashTable *table)
00375 {
00376   table->refcount -= 1;
00377 
00378   if (table->refcount == 0)
00379     {
00380 #if 0
00381       DBusHashEntry *entry;
00382       DBusHashEntry *next;
00383       int i;
00384 
00385       /* Free the entries in the table. */
00386       for (i = 0; i < table->n_buckets; i++)
00387         {
00388           entry = table->buckets[i];
00389           while (entry != NULL)
00390             {
00391               next = entry->next;
00392 
00393               free_entry (table, entry);
00394               
00395               entry = next;
00396             }
00397         }
00398 #else
00399       DBusHashEntry *entry;
00400       int i;
00401 
00402       /* Free the entries in the table. */
00403       for (i = 0; i < table->n_buckets; i++)
00404         {
00405           entry = table->buckets[i];
00406           while (entry != NULL)
00407             {
00408               free_entry_data (table, entry);
00409               
00410               entry = entry->next;
00411             }
00412         }
00413       /* We can do this very quickly with memory pools ;-) */
00414       _dbus_mem_pool_free (table->entry_pool);
00415 #endif
00416       
00417       /* Free the bucket array, if it was dynamically allocated. */
00418       if (table->buckets != table->static_buckets)
00419         dbus_free (table->buckets);
00420 
00421       dbus_free (table);
00422     }
00423 }
00424 
00425 static DBusHashEntry*
00426 alloc_entry (DBusHashTable *table)
00427 {
00428   DBusHashEntry *entry;
00429 
00430   entry = _dbus_mem_pool_alloc (table->entry_pool);
00431   
00432   return entry;
00433 }
00434 
00435 static void
00436 free_entry_data (DBusHashTable  *table,
00437                  DBusHashEntry  *entry)
00438 {
00439   if (table->free_key_function)
00440     (* table->free_key_function) (entry->key);
00441   if (table->free_value_function)
00442     (* table->free_value_function) (entry->value);
00443 }
00444 
00445 static void
00446 free_entry (DBusHashTable  *table,
00447             DBusHashEntry  *entry)
00448 {
00449   free_entry_data (table, entry);
00450   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00451 }
00452 
00453 static void
00454 remove_entry (DBusHashTable  *table,
00455               DBusHashEntry **bucket,
00456               DBusHashEntry  *entry)
00457 {
00458   _dbus_assert (table != NULL);
00459   _dbus_assert (bucket != NULL);
00460   _dbus_assert (*bucket != NULL);  
00461   _dbus_assert (entry != NULL);
00462   
00463   if (*bucket == entry)
00464     *bucket = entry->next;
00465   else
00466     {
00467       DBusHashEntry *prev;
00468       prev = *bucket;
00469 
00470       while (prev->next != entry)
00471         prev = prev->next;      
00472       
00473       _dbus_assert (prev != NULL);
00474 
00475       prev->next = entry->next;
00476     }
00477   
00478   table->n_entries -= 1;
00479   free_entry (table, entry);
00480 }
00481 
00513 void
00514 _dbus_hash_iter_init (DBusHashTable *table,
00515                       DBusHashIter  *iter)
00516 {
00517   DBusRealHashIter *real;
00518   
00519   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00520   
00521   real = (DBusRealHashIter*) iter;
00522 
00523   real->table = table;
00524   real->bucket = NULL;
00525   real->entry = NULL;
00526   real->next_entry = NULL;
00527   real->next_bucket = 0;
00528   real->n_entries_on_init = table->n_entries;
00529 }
00530 
00539 dbus_bool_t
00540 _dbus_hash_iter_next (DBusHashIter  *iter)
00541 {
00542   DBusRealHashIter *real;
00543   
00544   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00545   
00546   real = (DBusRealHashIter*) iter;
00547 
00548   /* if this assertion failed someone probably added hash entries
00549    * during iteration, which is bad.
00550    */
00551   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00552   
00553   /* Remember that real->entry may have been deleted */
00554   
00555   while (real->next_entry == NULL)
00556     {
00557       if (real->next_bucket >= real->table->n_buckets)
00558         {
00559           /* invalidate iter and return false */
00560           real->entry = NULL;
00561           real->table = NULL;
00562           real->bucket = NULL;
00563           return FALSE;
00564         }
00565 
00566       real->bucket = &(real->table->buckets[real->next_bucket]);
00567       real->next_entry = *(real->bucket);
00568       real->next_bucket += 1;
00569     }
00570 
00571   _dbus_assert (real->next_entry != NULL);
00572   _dbus_assert (real->bucket != NULL);
00573   
00574   real->entry = real->next_entry;
00575   real->next_entry = real->entry->next;
00576   
00577   return TRUE;
00578 }
00579 
00588 void
00589 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00590 {
00591   DBusRealHashIter *real;
00592 
00593   real = (DBusRealHashIter*) iter;
00594 
00595   _dbus_assert (real->table != NULL);
00596   _dbus_assert (real->entry != NULL);
00597   _dbus_assert (real->bucket != NULL);
00598   
00599   remove_entry (real->table, real->bucket, real->entry);
00600 
00601   real->entry = NULL; /* make it crash if you try to use this entry */
00602 }
00603 
00609 void*
00610 _dbus_hash_iter_get_value (DBusHashIter *iter)
00611 {
00612   DBusRealHashIter *real;
00613 
00614   real = (DBusRealHashIter*) iter;
00615 
00616   _dbus_assert (real->table != NULL);
00617   _dbus_assert (real->entry != NULL);
00618 
00619   return real->entry->value;
00620 }
00621 
00632 void
00633 _dbus_hash_iter_set_value (DBusHashIter *iter,
00634                            void         *value)
00635 {
00636   DBusRealHashIter *real;
00637 
00638   real = (DBusRealHashIter*) iter;
00639 
00640   _dbus_assert (real->table != NULL);
00641   _dbus_assert (real->entry != NULL);
00642 
00643   if (real->table->free_value_function && value != real->entry->value)    
00644     (* real->table->free_value_function) (real->entry->value);
00645   
00646   real->entry->value = value;
00647 }
00648 
00655 int
00656 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00657 {
00658   DBusRealHashIter *real;
00659 
00660   real = (DBusRealHashIter*) iter;
00661 
00662   _dbus_assert (real->table != NULL);
00663   _dbus_assert (real->entry != NULL);
00664 
00665   return _DBUS_POINTER_TO_INT (real->entry->key);
00666 }
00667 
00674 unsigned long
00675 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
00676 {
00677   DBusRealHashIter *real;
00678 
00679   real = (DBusRealHashIter*) iter;
00680 
00681   _dbus_assert (real->table != NULL);
00682   _dbus_assert (real->entry != NULL);
00683 
00684   return (unsigned long) real->entry->key;
00685 }
00686 
00692 const char*
00693 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00694 {
00695   DBusRealHashIter *real;
00696 
00697   real = (DBusRealHashIter*) iter;
00698 
00699   _dbus_assert (real->table != NULL);
00700   _dbus_assert (real->entry != NULL);
00701 
00702   return real->entry->key;
00703 }
00704 
00705 #ifdef DBUS_BUILD_TESTS
00706 
00711 const char*
00712 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
00713 {
00714   DBusRealHashIter *real;
00715 
00716   real = (DBusRealHashIter*) iter;
00717 
00718   _dbus_assert (real->table != NULL);
00719   _dbus_assert (real->entry != NULL);
00720 
00721   return real->entry->key;
00722 }
00723 #endif /* DBUS_BUILD_TESTS */
00724 
00756 dbus_bool_t
00757 _dbus_hash_iter_lookup (DBusHashTable *table,
00758                         void          *key,
00759                         dbus_bool_t    create_if_not_found,
00760                         DBusHashIter  *iter)
00761 {
00762   DBusRealHashIter *real;
00763   DBusHashEntry *entry;
00764   DBusHashEntry **bucket;
00765   
00766   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00767   
00768   real = (DBusRealHashIter*) iter;
00769 
00770   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00771 
00772   if (entry == NULL)
00773     return FALSE;
00774   
00775   real->table = table;
00776   real->bucket = bucket;
00777   real->entry = entry;
00778   real->next_entry = entry->next;
00779   real->next_bucket = (bucket - table->buckets) + 1;
00780   real->n_entries_on_init = table->n_entries; 
00781 
00782   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00783   
00784   return TRUE;
00785 }
00786 
00787 static void
00788 add_allocated_entry (DBusHashTable   *table,
00789                      DBusHashEntry   *entry,
00790                      unsigned int     idx,
00791                      void            *key,
00792                      DBusHashEntry ***bucket)
00793 {
00794   DBusHashEntry **b;  
00795   
00796   entry->key = key;
00797   
00798   b = &(table->buckets[idx]);
00799   entry->next = *b;
00800   *b = entry;
00801 
00802   if (bucket)
00803     *bucket = b;
00804   
00805   table->n_entries += 1;
00806 
00807   /* note we ONLY rebuild when ADDING - because you can iterate over a
00808    * table and remove entries safely.
00809    */
00810   if (table->n_entries >= table->hi_rebuild_size ||
00811       table->n_entries < table->lo_rebuild_size)
00812     rebuild_table (table);
00813 }
00814 
00815 static DBusHashEntry*
00816 add_entry (DBusHashTable        *table, 
00817            unsigned int          idx,
00818            void                 *key,
00819            DBusHashEntry      ***bucket,
00820            DBusPreallocatedHash *preallocated)
00821 {
00822   DBusHashEntry  *entry;
00823 
00824   if (preallocated == NULL)
00825     {
00826       entry = alloc_entry (table);
00827       if (entry == NULL)
00828         {
00829           if (bucket)
00830             *bucket = NULL;
00831           return NULL;
00832         }
00833     }
00834   else
00835     {
00836       entry = (DBusHashEntry*) preallocated;
00837     }
00838 
00839   add_allocated_entry (table, entry, idx, key, bucket);
00840 
00841   return entry;
00842 }
00843 
00844 /* This is g_str_hash from GLib which was
00845  * extensively discussed/tested/profiled
00846  */
00847 static unsigned int
00848 string_hash (const char *str)
00849 {
00850   const char *p = str;
00851   unsigned int h = *p;
00852 
00853   if (h)
00854     for (p += 1; *p != '\0'; p++)
00855       h = (h << 5) - h + *p;
00856 
00857   return h;
00858 }
00859 
00860 #ifdef DBUS_BUILD_TESTS
00861 /* This hashes a memory block with two nul-terminated strings
00862  * in it, used in dbus-object-registry.c at the moment.
00863  */
00864 static unsigned int
00865 two_strings_hash (const char *str)
00866 {
00867   const char *p = str;
00868   unsigned int h = *p;
00869 
00870   if (h)
00871     for (p += 1; *p != '\0'; p++)
00872       h = (h << 5) - h + *p;
00873 
00874   for (p += 1; *p != '\0'; p++)
00875     h = (h << 5) - h + *p;
00876   
00877   return h;
00878 }
00879 #endif /* DBUS_BUILD_TESTS */
00880 
00882 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00883 
00884 static DBusHashEntry*
00885 find_generic_function (DBusHashTable        *table,
00886                        void                 *key,
00887                        unsigned int          idx,
00888                        KeyCompareFunc        compare_func,
00889                        dbus_bool_t           create_if_not_found,
00890                        DBusHashEntry      ***bucket,
00891                        DBusPreallocatedHash *preallocated)
00892 {
00893   DBusHashEntry *entry;
00894 
00895   if (bucket)
00896     *bucket = NULL;
00897 
00898   /* Search all of the entries in this bucket. */
00899   entry = table->buckets[idx];
00900   while (entry != NULL)
00901     {
00902       if ((compare_func == NULL && key == entry->key) ||
00903           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00904         {
00905           if (bucket)
00906             *bucket = &(table->buckets[idx]);
00907 
00908           if (preallocated)
00909             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00910           
00911           return entry;
00912         }
00913       
00914       entry = entry->next;
00915     }
00916 
00917   if (create_if_not_found)
00918     entry = add_entry (table, idx, key, bucket, preallocated);
00919   else if (preallocated)
00920     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00921   
00922   return entry;
00923 }
00924 
00925 static DBusHashEntry*
00926 find_string_function (DBusHashTable        *table,
00927                       void                 *key,
00928                       dbus_bool_t           create_if_not_found,
00929                       DBusHashEntry      ***bucket,
00930                       DBusPreallocatedHash *preallocated)
00931 {
00932   unsigned int idx;
00933   
00934   idx = string_hash (key) & table->mask;
00935 
00936   return find_generic_function (table, key, idx,
00937                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00938                                 preallocated);
00939 }
00940 
00941 #ifdef DBUS_BUILD_TESTS
00942 static int
00943 two_strings_cmp (const char *a,
00944                  const char *b)
00945 {
00946   size_t len_a;
00947   size_t len_b;
00948   int res;
00949   
00950   res = strcmp (a, b);
00951   if (res != 0)
00952     return res;
00953 
00954   len_a = strlen (a);
00955   len_b = strlen (b);
00956 
00957   return strcmp (a + len_a + 1, b + len_b + 1);
00958 }
00959 #endif
00960 
00961 #ifdef DBUS_BUILD_TESTS
00962 static DBusHashEntry*
00963 find_two_strings_function (DBusHashTable        *table,
00964                            void                 *key,
00965                            dbus_bool_t           create_if_not_found,
00966                            DBusHashEntry      ***bucket,
00967                            DBusPreallocatedHash *preallocated)
00968 {
00969   unsigned int idx;
00970   
00971   idx = two_strings_hash (key) & table->mask;
00972 
00973   return find_generic_function (table, key, idx,
00974                                 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
00975                                 preallocated);
00976 }
00977 #endif /* DBUS_BUILD_TESTS */
00978 
00979 static DBusHashEntry*
00980 find_direct_function (DBusHashTable        *table,
00981                       void                 *key,
00982                       dbus_bool_t           create_if_not_found,
00983                       DBusHashEntry      ***bucket,
00984                       DBusPreallocatedHash *preallocated)
00985 {
00986   unsigned int idx;
00987   
00988   idx = RANDOM_INDEX (table, key) & table->mask;
00989 
00990 
00991   return find_generic_function (table, key, idx,
00992                                 NULL, create_if_not_found, bucket,
00993                                 preallocated);
00994 }
00995 
00996 static void
00997 rebuild_table (DBusHashTable *table)
00998 {
00999   int old_size;
01000   int new_buckets;
01001   DBusHashEntry **old_buckets;
01002   DBusHashEntry **old_chain;
01003   DBusHashEntry *entry;
01004   dbus_bool_t growing;
01005   
01006   /*
01007    * Allocate and initialize the new bucket array, and set up
01008    * hashing constants for new array size.
01009    */
01010 
01011   growing = table->n_entries >= table->hi_rebuild_size;
01012   
01013   old_size = table->n_buckets;
01014   old_buckets = table->buckets;
01015 
01016   if (growing)
01017     {
01018       /* overflow paranoia */
01019       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
01020           table->down_shift >= 0)
01021         new_buckets = table->n_buckets * 4;
01022       else
01023         return; /* can't grow anymore */
01024     }
01025   else
01026     {
01027       new_buckets = table->n_buckets / 4;
01028       if (new_buckets < DBUS_SMALL_HASH_TABLE)
01029         return; /* don't bother shrinking this far */
01030     }
01031 
01032   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
01033   if (table->buckets == NULL)
01034     {
01035       /* out of memory, yay - just don't reallocate, the table will
01036        * still work, albeit more slowly.
01037        */
01038       table->buckets = old_buckets;
01039       return;
01040     }
01041 
01042   table->n_buckets = new_buckets;
01043   
01044   if (growing)
01045     {
01046       table->lo_rebuild_size = table->hi_rebuild_size;
01047       table->hi_rebuild_size *= 4;
01048       
01049       table->down_shift -= 2;               /* keep 2 more high bits */
01050       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
01051     }
01052   else
01053     {
01054       table->hi_rebuild_size = table->lo_rebuild_size;
01055       table->lo_rebuild_size /= 4;
01056 
01057       table->down_shift += 2;         /* keep 2 fewer high bits */
01058       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
01059     }
01060 
01061 #if 0
01062   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
01063           growing ? "GROW" : "SHRINK",
01064           table->lo_rebuild_size,
01065           table->hi_rebuild_size,
01066           table->down_shift,
01067           table->mask);
01068 #endif
01069   
01070   _dbus_assert (table->lo_rebuild_size >= 0);
01071   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01072   _dbus_assert (table->mask != 0);
01073   /* the mask is essentially the max index */
01074   _dbus_assert (table->mask < table->n_buckets);
01075   
01076   /*
01077    * Rehash all of the existing entries into the new bucket array.
01078    */
01079 
01080   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01081     {
01082       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01083         {
01084           unsigned int idx;
01085           DBusHashEntry **bucket;
01086           
01087           *old_chain = entry->next;
01088           switch (table->key_type)
01089             {
01090             case DBUS_HASH_STRING:
01091               idx = string_hash (entry->key) & table->mask;
01092               break;
01093             case DBUS_HASH_TWO_STRINGS:
01094 #ifdef DBUS_BUILD_TESTS
01095               idx = two_strings_hash (entry->key) & table->mask;
01096 #else
01097               idx = 0;
01098               _dbus_assert_not_reached ("two-strings is not enabled");
01099 #endif
01100               break;
01101             case DBUS_HASH_INT:
01102             case DBUS_HASH_ULONG:
01103             case DBUS_HASH_POINTER:
01104               idx = RANDOM_INDEX (table, entry->key);
01105               break;
01106             default:
01107               idx = 0;
01108               _dbus_assert_not_reached ("Unknown hash table type");
01109               break;
01110             }
01111           
01112           bucket = &(table->buckets[idx]);
01113           entry->next = *bucket;
01114           *bucket = entry;
01115         }
01116     }
01117   
01118   /* Free the old bucket array, if it was dynamically allocated. */
01119 
01120   if (old_buckets != table->static_buckets)
01121     dbus_free (old_buckets);
01122 }
01123 
01133 void*
01134 _dbus_hash_table_lookup_string (DBusHashTable *table,
01135                                 const char    *key)
01136 {
01137   DBusHashEntry *entry;
01138 
01139   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01140   
01141   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01142 
01143   if (entry)
01144     return entry->value;
01145   else
01146     return NULL;
01147 }
01148 
01149 #ifdef DBUS_BUILD_TESTS
01150 
01159 void*
01160 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
01161                                      const char    *key)
01162 {
01163   DBusHashEntry *entry;
01164 
01165   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01166   
01167   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01168 
01169   if (entry)
01170     return entry->value;
01171   else
01172     return NULL;
01173 }
01174 #endif /* DBUS_BUILD_TESTS */
01175 
01185 void*
01186 _dbus_hash_table_lookup_int (DBusHashTable *table,
01187                              int            key)
01188 {
01189   DBusHashEntry *entry;
01190 
01191   _dbus_assert (table->key_type == DBUS_HASH_INT);
01192   
01193   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01194 
01195   if (entry)
01196     return entry->value;
01197   else
01198     return NULL;
01199 }
01200 
01201 #ifdef DBUS_BUILD_TESTS
01202 /* disabled since it's only used for testing */
01212 void*
01213 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01214                                  void          *key)
01215 {
01216   DBusHashEntry *entry;
01217 
01218   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01219   
01220   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01221 
01222   if (entry)
01223     return entry->value;
01224   else
01225     return NULL;
01226 }
01227 #endif /* DBUS_BUILD_TESTS */
01228 
01238 void*
01239 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
01240                                unsigned long  key)
01241 {
01242   DBusHashEntry *entry;
01243 
01244   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01245   
01246   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01247 
01248   if (entry)
01249     return entry->value;
01250   else
01251     return NULL;
01252 }
01253 
01262 dbus_bool_t
01263 _dbus_hash_table_remove_string (DBusHashTable *table,
01264                                 const char    *key)
01265 {
01266   DBusHashEntry *entry;
01267   DBusHashEntry **bucket;
01268   
01269   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01270   
01271   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01272 
01273   if (entry)
01274     {
01275       remove_entry (table, bucket, entry);
01276       return TRUE;
01277     }
01278   else
01279     return FALSE;
01280 }
01281 
01282 #ifdef DBUS_BUILD_TESTS
01283 
01291 dbus_bool_t
01292 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
01293                                      const char    *key)
01294 {
01295   DBusHashEntry *entry;
01296   DBusHashEntry **bucket;
01297   
01298   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01299   
01300   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01301 
01302   if (entry)
01303     {
01304       remove_entry (table, bucket, entry);
01305       return TRUE;
01306     }
01307   else
01308     return FALSE;
01309 }
01310 #endif /* DBUS_BUILD_TESTS */
01311 
01320 dbus_bool_t
01321 _dbus_hash_table_remove_int (DBusHashTable *table,
01322                              int            key)
01323 {
01324   DBusHashEntry *entry;
01325   DBusHashEntry **bucket;
01326   
01327   _dbus_assert (table->key_type == DBUS_HASH_INT);
01328   
01329   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01330   
01331   if (entry)
01332     {
01333       remove_entry (table, bucket, entry);
01334       return TRUE;
01335     }
01336   else
01337     return FALSE;
01338 }
01339 
01340 #ifdef DBUS_BUILD_TESTS
01341 /* disabled since it's only used for testing */
01350 dbus_bool_t
01351 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01352                                  void          *key)
01353 {
01354   DBusHashEntry *entry;
01355   DBusHashEntry **bucket;
01356   
01357   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01358   
01359   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01360   
01361   if (entry)
01362     {
01363       remove_entry (table, bucket, entry);
01364       return TRUE;
01365     }
01366   else
01367     return FALSE;
01368 }
01369 #endif /* DBUS_BUILD_TESTS */
01370 
01379 dbus_bool_t
01380 _dbus_hash_table_remove_ulong (DBusHashTable *table,
01381                                unsigned long  key)
01382 {
01383   DBusHashEntry *entry;
01384   DBusHashEntry **bucket;
01385   
01386   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01387   
01388   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01389   
01390   if (entry)
01391     {
01392       remove_entry (table, bucket, entry);
01393       return TRUE;
01394     }
01395   else
01396     return FALSE;
01397 }
01398 
01414 dbus_bool_t
01415 _dbus_hash_table_insert_string (DBusHashTable *table,
01416                                 char          *key,
01417                                 void          *value)
01418 {
01419   DBusPreallocatedHash *preallocated;
01420 
01421   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01422 
01423   preallocated = _dbus_hash_table_preallocate_entry (table);
01424   if (preallocated == NULL)
01425     return FALSE;
01426 
01427   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01428                                                key, value);
01429   
01430   return TRUE;
01431 }
01432 
01433 #ifdef DBUS_BUILD_TESTS
01434 
01449 dbus_bool_t
01450 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
01451                                      char          *key,
01452                                      void          *value)
01453 {
01454   DBusHashEntry *entry;
01455   
01456   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01457   
01458   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01459 
01460   if (entry == NULL)
01461     return FALSE; /* no memory */
01462 
01463   if (table->free_key_function && entry->key != key)
01464     (* table->free_key_function) (entry->key);
01465   
01466   if (table->free_value_function && entry->value != value)
01467     (* table->free_value_function) (entry->value);
01468   
01469   entry->key = key;
01470   entry->value = value;
01471 
01472   return TRUE;
01473 }
01474 #endif /* DBUS_BUILD_TESTS */
01475 
01491 dbus_bool_t
01492 _dbus_hash_table_insert_int (DBusHashTable *table,
01493                              int            key,
01494                              void          *value)
01495 {
01496   DBusHashEntry *entry;
01497 
01498   _dbus_assert (table->key_type == DBUS_HASH_INT);
01499   
01500   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01501 
01502   if (entry == NULL)
01503     return FALSE; /* no memory */
01504 
01505   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01506     (* table->free_key_function) (entry->key);
01507   
01508   if (table->free_value_function && entry->value != value)
01509     (* table->free_value_function) (entry->value);
01510   
01511   entry->key = _DBUS_INT_TO_POINTER (key);
01512   entry->value = value;
01513 
01514   return TRUE;
01515 }
01516 
01517 #ifdef DBUS_BUILD_TESTS
01518 /* disabled since it's only used for testing */
01534 dbus_bool_t
01535 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01536                                  void          *key,
01537                                  void          *value)
01538 {
01539   DBusHashEntry *entry;
01540 
01541   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01542   
01543   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01544 
01545   if (entry == NULL)
01546     return FALSE; /* no memory */
01547 
01548   if (table->free_key_function && entry->key != key)
01549     (* table->free_key_function) (entry->key);
01550   
01551   if (table->free_value_function && entry->value != value)
01552     (* table->free_value_function) (entry->value);
01553   
01554   entry->key = key;
01555   entry->value = value;
01556 
01557   return TRUE;
01558 }
01559 #endif /* DBUS_BUILD_TESTS */
01560 
01576 dbus_bool_t
01577 _dbus_hash_table_insert_ulong (DBusHashTable *table,
01578                                unsigned long  key,
01579                                void          *value)
01580 {
01581   DBusHashEntry *entry;
01582 
01583   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01584   
01585   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01586 
01587   if (entry == NULL)
01588     return FALSE; /* no memory */
01589 
01590   if (table->free_key_function && entry->key != (void*) key)
01591     (* table->free_key_function) (entry->key);
01592   
01593   if (table->free_value_function && entry->value != value)
01594     (* table->free_value_function) (entry->value);
01595   
01596   entry->key = (void*) key;
01597   entry->value = value;
01598 
01599   return TRUE;
01600 }
01601 
01609 DBusPreallocatedHash*
01610 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01611 {
01612   DBusHashEntry *entry;
01613   
01614   entry = alloc_entry (table);
01615 
01616   return (DBusPreallocatedHash*) entry;
01617 }
01618 
01626 void
01627 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01628                                           DBusPreallocatedHash *preallocated)
01629 {
01630   DBusHashEntry *entry;
01631 
01632   _dbus_assert (preallocated != NULL);
01633   
01634   entry = (DBusHashEntry*) preallocated;
01635   
01636   /* Don't use free_entry(), since this entry has no key/data */
01637   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01638 }
01639 
01653 void
01654 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01655                                              DBusPreallocatedHash *preallocated,
01656                                              char                 *key,
01657                                              void                 *value)
01658 {
01659   DBusHashEntry *entry;
01660 
01661   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01662   _dbus_assert (preallocated != NULL);
01663   
01664   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01665 
01666   _dbus_assert (entry != NULL);
01667   
01668   if (table->free_key_function && entry->key != key)
01669     (* table->free_key_function) (entry->key);
01670 
01671   if (table->free_value_function && entry->value != value)
01672     (* table->free_value_function) (entry->value);
01673       
01674   entry->key = key;
01675   entry->value = value;
01676 }
01677 
01684 int
01685 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01686 {
01687   return table->n_entries;
01688 }
01689 
01692 #ifdef DBUS_BUILD_TESTS
01693 #include "dbus-test.h"
01694 #include <stdio.h>
01695 
01696 /* If you're wondering why the hash table test takes
01697  * forever to run, it's because we call this function
01698  * in inner loops thus making things quadratic.
01699  */
01700 static int
01701 count_entries (DBusHashTable *table)
01702 {
01703   DBusHashIter iter;
01704   int count;
01705 
01706   count = 0;
01707   _dbus_hash_iter_init (table, &iter);
01708   while (_dbus_hash_iter_next (&iter))
01709     ++count;
01710 
01711   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01712   
01713   return count;
01714 }
01715 
01716 /* Copy the foo\0bar\0 double string thing */
01717 static char*
01718 _dbus_strdup2 (const char *str)
01719 {
01720   size_t len;
01721   char *copy;
01722   
01723   if (str == NULL)
01724     return NULL;
01725   
01726   len = strlen (str);
01727   len += strlen ((str + len + 1));
01728 
01729   copy = dbus_malloc (len + 2);
01730   if (copy == NULL)
01731     return NULL;
01732 
01733   memcpy (copy, str, len + 2);
01734   
01735   return copy;
01736 }
01737 
01743 dbus_bool_t
01744 _dbus_hash_test (void)
01745 {
01746   int i;
01747   DBusHashTable *table1;
01748   DBusHashTable *table2;
01749   DBusHashTable *table3;
01750   DBusHashTable *table4;
01751   DBusHashIter iter;
01752 #define N_HASH_KEYS 5000
01753   char **keys;
01754   dbus_bool_t ret = FALSE;
01755 
01756   keys = dbus_new (char *, N_HASH_KEYS);
01757   if (keys == NULL)
01758     _dbus_assert_not_reached ("no memory");
01759 
01760   for (i = 0; i < N_HASH_KEYS; i++)
01761     {
01762       keys[i] = dbus_malloc (128);
01763 
01764       if (keys[i] == NULL)
01765         _dbus_assert_not_reached ("no memory");
01766     }
01767 
01768   printf ("Computing test hash keys...\n");
01769   i = 0;
01770   while (i < N_HASH_KEYS)
01771     {
01772       int len;
01773 
01774       /* all the hash keys are TWO_STRINGS, but
01775        * then we can also use those as regular strings.
01776        */
01777       
01778       len = sprintf (keys[i], "Hash key %d", i);
01779       sprintf (keys[i] + len + 1, "Two string %d", i);
01780       _dbus_assert (*(keys[i] + len) == '\0');
01781       _dbus_assert (*(keys[i] + len + 1) != '\0');
01782       ++i;
01783     }
01784   printf ("... done.\n");
01785   
01786   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01787                                  dbus_free, dbus_free);
01788   if (table1 == NULL)
01789     goto out;
01790 
01791   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01792                                  NULL, dbus_free);
01793   if (table2 == NULL)
01794     goto out;
01795 
01796   table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
01797                                  NULL, dbus_free);
01798   if (table3 == NULL)
01799     goto out;
01800 
01801   table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
01802                                  dbus_free, dbus_free);
01803   if (table4 == NULL)
01804     goto out;
01805 
01806   
01807   /* Insert and remove a bunch of stuff, counting the table in between
01808    * to be sure it's not broken and that iteration works
01809    */
01810   i = 0;
01811   while (i < 3000)
01812     {
01813       void *value;
01814       char *key;
01815 
01816       key = _dbus_strdup (keys[i]);
01817       if (key == NULL)
01818         goto out;
01819       value = _dbus_strdup ("Value!");
01820       if (value == NULL)
01821         goto out;
01822       
01823       if (!_dbus_hash_table_insert_string (table1,
01824                                            key, value))
01825         goto out;
01826 
01827       value = _dbus_strdup (keys[i]);
01828       if (value == NULL)
01829         goto out;
01830       
01831       if (!_dbus_hash_table_insert_int (table2,
01832                                         i, value))
01833         goto out;
01834 
01835       value = _dbus_strdup (keys[i]);
01836       if (value == NULL)
01837         goto out;
01838       
01839       if (!_dbus_hash_table_insert_ulong (table3,
01840                                           i, value))
01841         goto out;
01842 
01843       key = _dbus_strdup2 (keys[i]);
01844       if (key == NULL)
01845         goto out;
01846       value = _dbus_strdup ("Value!");
01847       if (value == NULL)
01848         goto out;
01849       
01850       if (!_dbus_hash_table_insert_two_strings (table4,
01851                                                 key, value))
01852         goto out;
01853       
01854       _dbus_assert (count_entries (table1) == i + 1);
01855       _dbus_assert (count_entries (table2) == i + 1);
01856       _dbus_assert (count_entries (table3) == i + 1);
01857       _dbus_assert (count_entries (table4) == i + 1);
01858 
01859       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01860       _dbus_assert (value != NULL);
01861       _dbus_assert (strcmp (value, "Value!") == 0);
01862 
01863       value = _dbus_hash_table_lookup_int (table2, i);
01864       _dbus_assert (value != NULL);
01865       _dbus_assert (strcmp (value, keys[i]) == 0);
01866 
01867       value = _dbus_hash_table_lookup_ulong (table3, i);
01868       _dbus_assert (value != NULL);
01869       _dbus_assert (strcmp (value, keys[i]) == 0);
01870 
01871       value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01872       _dbus_assert (value != NULL);
01873       _dbus_assert (strcmp (value, "Value!") == 0);
01874       
01875       ++i;
01876     }
01877 
01878   --i;
01879   while (i >= 0)
01880     {
01881       _dbus_hash_table_remove_string (table1,
01882                                       keys[i]);
01883 
01884       _dbus_hash_table_remove_int (table2, i);
01885 
01886       _dbus_hash_table_remove_ulong (table3, i); 
01887 
01888       _dbus_hash_table_remove_two_strings (table4,
01889                                            keys[i]);
01890       
01891       _dbus_assert (count_entries (table1) == i);
01892       _dbus_assert (count_entries (table2) == i);
01893       _dbus_assert (count_entries (table3) == i);
01894       _dbus_assert (count_entries (table4) == i);
01895 
01896       --i;
01897     }
01898 
01899   _dbus_hash_table_ref (table1);
01900   _dbus_hash_table_ref (table2);
01901   _dbus_hash_table_ref (table3);
01902   _dbus_hash_table_ref (table4);
01903   _dbus_hash_table_unref (table1);
01904   _dbus_hash_table_unref (table2);
01905   _dbus_hash_table_unref (table3);
01906   _dbus_hash_table_unref (table4);
01907   _dbus_hash_table_unref (table1);
01908   _dbus_hash_table_unref (table2);
01909   _dbus_hash_table_unref (table3);
01910   _dbus_hash_table_unref (table4);
01911   table3 = NULL;
01912 
01913   /* Insert a bunch of stuff then check
01914    * that iteration works correctly (finds the right
01915    * values, iter_set_value works, etc.)
01916    */
01917   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01918                                  dbus_free, dbus_free);
01919   if (table1 == NULL)
01920     goto out;
01921   
01922   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01923                                  NULL, dbus_free);
01924   if (table2 == NULL)
01925     goto out;
01926   
01927   i = 0;
01928   while (i < 5000)
01929     {
01930       char *key;
01931       void *value;      
01932       
01933       key = _dbus_strdup (keys[i]);
01934       if (key == NULL)
01935         goto out;
01936       value = _dbus_strdup ("Value!");
01937       if (value == NULL)
01938         goto out;
01939       
01940       if (!_dbus_hash_table_insert_string (table1,
01941                                            key, value))
01942         goto out;
01943 
01944       value = _dbus_strdup (keys[i]);
01945       if (value == NULL)
01946         goto out;
01947       
01948       if (!_dbus_hash_table_insert_int (table2,
01949                                         i, value))
01950         goto out;
01951       
01952       _dbus_assert (count_entries (table1) == i + 1);
01953       _dbus_assert (count_entries (table2) == i + 1);
01954       
01955       ++i;
01956     }
01957 
01958   _dbus_hash_iter_init (table1, &iter);
01959   while (_dbus_hash_iter_next (&iter))
01960     {
01961       const char *key;
01962       void *value;
01963 
01964       key = _dbus_hash_iter_get_string_key (&iter);
01965       value = _dbus_hash_iter_get_value (&iter);
01966 
01967       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01968 
01969       value = _dbus_strdup ("Different value!");
01970       if (value == NULL)
01971         goto out;
01972       
01973       _dbus_hash_iter_set_value (&iter, value);
01974 
01975       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01976     }
01977   
01978   _dbus_hash_iter_init (table1, &iter);
01979   while (_dbus_hash_iter_next (&iter))
01980     {
01981       _dbus_hash_iter_remove_entry (&iter);
01982       _dbus_assert (count_entries (table1) == i - 1);
01983       --i;
01984     }
01985 
01986   _dbus_hash_iter_init (table2, &iter);
01987   while (_dbus_hash_iter_next (&iter))
01988     {
01989       int key;
01990       void *value;
01991 
01992       key = _dbus_hash_iter_get_int_key (&iter);
01993       value = _dbus_hash_iter_get_value (&iter);
01994 
01995       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01996 
01997       value = _dbus_strdup ("Different value!");
01998       if (value == NULL)
01999         goto out;
02000       
02001       _dbus_hash_iter_set_value (&iter, value);
02002 
02003       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02004     }
02005 
02006   i = count_entries (table2);
02007   _dbus_hash_iter_init (table2, &iter);
02008   while (_dbus_hash_iter_next (&iter))
02009     {
02010       _dbus_hash_iter_remove_entry (&iter);
02011       _dbus_assert (count_entries (table2) + 1 == i);
02012       --i;
02013     }
02014 
02015   /* add/remove interleaved, to check that we grow/shrink the table
02016    * appropriately
02017    */
02018   i = 0;
02019   while (i < 1000)
02020     {
02021       char *key;
02022       void *value;
02023             
02024       key = _dbus_strdup (keys[i]);
02025       if (key == NULL)
02026         goto out;
02027 
02028       value = _dbus_strdup ("Value!");
02029       if (value == NULL)
02030         goto out;
02031       
02032       if (!_dbus_hash_table_insert_string (table1,
02033                                            key, value))
02034         goto out;
02035       
02036       ++i;
02037     }
02038 
02039   --i;
02040   while (i >= 0)
02041     {
02042       char *key;
02043       void *value;      
02044       
02045       key = _dbus_strdup (keys[i]);
02046       if (key == NULL)
02047         goto out;
02048       value = _dbus_strdup ("Value!");
02049       if (value == NULL)
02050         goto out;
02051 
02052       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02053         goto out;
02054       
02055       if (!_dbus_hash_table_insert_string (table1,
02056                                            key, value))
02057         goto out;
02058 
02059       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02060         goto out;
02061       
02062       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
02063       
02064       --i;
02065     }
02066 
02067   /* nuke these tables */
02068   _dbus_hash_table_unref (table1);
02069   _dbus_hash_table_unref (table2);
02070 
02071 
02072   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
02073    * be sure that interface works.
02074    */
02075   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
02076                                  dbus_free, dbus_free);
02077   if (table1 == NULL)
02078     goto out;
02079   
02080   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
02081                                  NULL, dbus_free);
02082   if (table2 == NULL)
02083     goto out;
02084   
02085   i = 0;
02086   while (i < 3000)
02087     {
02088       void *value;
02089       char *key;
02090 
02091       key = _dbus_strdup (keys[i]);
02092       if (key == NULL)
02093         goto out;
02094       value = _dbus_strdup ("Value!");
02095       if (value == NULL)
02096         goto out;
02097       
02098       if (!_dbus_hash_iter_lookup (table1,
02099                                    key, TRUE, &iter))
02100         goto out;
02101       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02102       _dbus_hash_iter_set_value (&iter, value);
02103 
02104       value = _dbus_strdup (keys[i]);
02105       if (value == NULL)
02106         goto out;
02107 
02108       if (!_dbus_hash_iter_lookup (table2,
02109                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
02110         goto out;
02111       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02112       _dbus_hash_iter_set_value (&iter, value); 
02113       
02114       _dbus_assert (count_entries (table1) == i + 1);
02115       _dbus_assert (count_entries (table2) == i + 1);
02116 
02117       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02118         goto out;
02119       
02120       value = _dbus_hash_iter_get_value (&iter);
02121       _dbus_assert (value != NULL);
02122       _dbus_assert (strcmp (value, "Value!") == 0);
02123 
02124       /* Iterate just to be sure it works, though
02125        * it's a stupid thing to do
02126        */
02127       while (_dbus_hash_iter_next (&iter))
02128         ;
02129       
02130       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02131         goto out;
02132 
02133       value = _dbus_hash_iter_get_value (&iter);
02134       _dbus_assert (value != NULL);
02135       _dbus_assert (strcmp (value, keys[i]) == 0);
02136 
02137       /* Iterate just to be sure it works, though
02138        * it's a stupid thing to do
02139        */
02140       while (_dbus_hash_iter_next (&iter))
02141         ;
02142       
02143       ++i;
02144     }
02145 
02146   --i;
02147   while (i >= 0)
02148     {
02149       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02150         _dbus_assert_not_reached ("hash entry should have existed");
02151       _dbus_hash_iter_remove_entry (&iter);
02152       
02153       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02154         _dbus_assert_not_reached ("hash entry should have existed");
02155       _dbus_hash_iter_remove_entry (&iter);
02156 
02157       _dbus_assert (count_entries (table1) == i);
02158       _dbus_assert (count_entries (table2) == i);
02159 
02160       --i;
02161     }
02162 
02163   _dbus_hash_table_unref (table1);
02164   _dbus_hash_table_unref (table2);
02165 
02166   ret = TRUE;
02167 
02168  out:
02169   for (i = 0; i < N_HASH_KEYS; i++)
02170     dbus_free (keys[i]);
02171 
02172   dbus_free (keys);
02173   
02174   return ret;
02175 }
02176 
02177 #endif /* DBUS_BUILD_TESTS */

Generated on Tue Sep 13 01:28:06 2005 for D-BUS by  doxygen 1.4.4