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

Generated on Tue Feb 10 18:14:03 2004 for D-BUS by doxygen 1.3.5