dbus-hash.c

00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
00002 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
00003  * 
00004  * Copyright (C) 2002  Red Hat, Inc.
00005  * Copyright (c) 1991-1993 The Regents of the University of California.
00006  * Copyright (c) 1994 Sun Microsystems, Inc.
00007  * 
00008  * Hash table implementation based on generic/tclHash.c from the Tcl
00009  * source code. The original Tcl license applies to portions of the
00010  * code from tclHash.c; the Tcl license follows this standad D-Bus 
00011  * license information.
00012  *
00013  * Licensed under the Academic Free License version 2.1
00014  * 
00015  * This program is free software; you can redistribute it and/or modify
00016  * it under the terms of the GNU General Public License as published by
00017  * the Free Software Foundation; either version 2 of the License, or
00018  * (at your option) any later version.
00019  *
00020  * This program is distributed in the hope that it will be useful,
00021  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00022  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00023  * GNU General Public License for more details.
00024  * 
00025  * You should have received a copy of the GNU General Public License
00026  * along with this program; if not, write to the Free Software
00027  * Foundation, Inc., 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 
00430 void
00431 _dbus_hash_table_remove_all (DBusHashTable *table)
00432 {
00433   DBusHashIter iter;
00434   _dbus_hash_iter_init (table, &iter);
00435   while (_dbus_hash_iter_next (&iter))
00436     {
00437       _dbus_hash_iter_remove_entry(&iter);
00438     }
00439 }
00440 
00441 static DBusHashEntry*
00442 alloc_entry (DBusHashTable *table)
00443 {
00444   DBusHashEntry *entry;
00445 
00446   entry = _dbus_mem_pool_alloc (table->entry_pool);
00447   
00448   return entry;
00449 }
00450 
00451 static void
00452 free_entry_data (DBusHashTable  *table,
00453                  DBusHashEntry  *entry)
00454 {
00455   if (table->free_key_function)
00456     (* table->free_key_function) (entry->key);
00457   if (table->free_value_function)
00458     (* table->free_value_function) (entry->value);
00459 }
00460 
00461 static void
00462 free_entry (DBusHashTable  *table,
00463             DBusHashEntry  *entry)
00464 {
00465   free_entry_data (table, entry);
00466   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00467 }
00468 
00469 static void
00470 remove_entry (DBusHashTable  *table,
00471               DBusHashEntry **bucket,
00472               DBusHashEntry  *entry)
00473 {
00474   _dbus_assert (table != NULL);
00475   _dbus_assert (bucket != NULL);
00476   _dbus_assert (*bucket != NULL);  
00477   _dbus_assert (entry != NULL);
00478   
00479   if (*bucket == entry)
00480     *bucket = entry->next;
00481   else
00482     {
00483       DBusHashEntry *prev;
00484       prev = *bucket;
00485 
00486       while (prev->next != entry)
00487         prev = prev->next;      
00488       
00489       _dbus_assert (prev != NULL);
00490 
00491       prev->next = entry->next;
00492     }
00493   
00494   table->n_entries -= 1;
00495   free_entry (table, entry);
00496 }
00497 
00529 void
00530 _dbus_hash_iter_init (DBusHashTable *table,
00531                       DBusHashIter  *iter)
00532 {
00533   DBusRealHashIter *real;
00534   
00535   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00536   
00537   real = (DBusRealHashIter*) iter;
00538 
00539   real->table = table;
00540   real->bucket = NULL;
00541   real->entry = NULL;
00542   real->next_entry = NULL;
00543   real->next_bucket = 0;
00544   real->n_entries_on_init = table->n_entries;
00545 }
00546 
00555 dbus_bool_t
00556 _dbus_hash_iter_next (DBusHashIter  *iter)
00557 {
00558   DBusRealHashIter *real;
00559   
00560   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00561   
00562   real = (DBusRealHashIter*) iter;
00563 
00564   /* if this assertion failed someone probably added hash entries
00565    * during iteration, which is bad.
00566    */
00567   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00568   
00569   /* Remember that real->entry may have been deleted */
00570   
00571   while (real->next_entry == NULL)
00572     {
00573       if (real->next_bucket >= real->table->n_buckets)
00574         {
00575           /* invalidate iter and return false */
00576           real->entry = NULL;
00577           real->table = NULL;
00578           real->bucket = NULL;
00579           return FALSE;
00580         }
00581 
00582       real->bucket = &(real->table->buckets[real->next_bucket]);
00583       real->next_entry = *(real->bucket);
00584       real->next_bucket += 1;
00585     }
00586 
00587   _dbus_assert (real->next_entry != NULL);
00588   _dbus_assert (real->bucket != NULL);
00589   
00590   real->entry = real->next_entry;
00591   real->next_entry = real->entry->next;
00592   
00593   return TRUE;
00594 }
00595 
00604 void
00605 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00606 {
00607   DBusRealHashIter *real;
00608 
00609   real = (DBusRealHashIter*) iter;
00610 
00611   _dbus_assert (real->table != NULL);
00612   _dbus_assert (real->entry != NULL);
00613   _dbus_assert (real->bucket != NULL);
00614   
00615   remove_entry (real->table, real->bucket, real->entry);
00616 
00617   real->entry = NULL; /* make it crash if you try to use this entry */
00618 }
00619 
00625 void*
00626 _dbus_hash_iter_get_value (DBusHashIter *iter)
00627 {
00628   DBusRealHashIter *real;
00629 
00630   real = (DBusRealHashIter*) iter;
00631 
00632   _dbus_assert (real->table != NULL);
00633   _dbus_assert (real->entry != NULL);
00634 
00635   return real->entry->value;
00636 }
00637 
00648 void
00649 _dbus_hash_iter_set_value (DBusHashIter *iter,
00650                            void         *value)
00651 {
00652   DBusRealHashIter *real;
00653 
00654   real = (DBusRealHashIter*) iter;
00655 
00656   _dbus_assert (real->table != NULL);
00657   _dbus_assert (real->entry != NULL);
00658 
00659   if (real->table->free_value_function && value != real->entry->value)    
00660     (* real->table->free_value_function) (real->entry->value);
00661   
00662   real->entry->value = value;
00663 }
00664 
00671 int
00672 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00673 {
00674   DBusRealHashIter *real;
00675 
00676   real = (DBusRealHashIter*) iter;
00677 
00678   _dbus_assert (real->table != NULL);
00679   _dbus_assert (real->entry != NULL);
00680 
00681   return _DBUS_POINTER_TO_INT (real->entry->key);
00682 }
00683 
00690 unsigned long
00691 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
00692 {
00693   DBusRealHashIter *real;
00694 
00695   real = (DBusRealHashIter*) iter;
00696 
00697   _dbus_assert (real->table != NULL);
00698   _dbus_assert (real->entry != NULL);
00699 
00700   return (unsigned long) real->entry->key;
00701 }
00702 
00708 const char*
00709 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00710 {
00711   DBusRealHashIter *real;
00712 
00713   real = (DBusRealHashIter*) iter;
00714 
00715   _dbus_assert (real->table != NULL);
00716   _dbus_assert (real->entry != NULL);
00717 
00718   return real->entry->key;
00719 }
00720 
00721 #ifdef DBUS_BUILD_TESTS
00722 
00727 const char*
00728 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
00729 {
00730   DBusRealHashIter *real;
00731 
00732   real = (DBusRealHashIter*) iter;
00733 
00734   _dbus_assert (real->table != NULL);
00735   _dbus_assert (real->entry != NULL);
00736 
00737   return real->entry->key;
00738 }
00739 #endif /* DBUS_BUILD_TESTS */
00740 
00772 dbus_bool_t
00773 _dbus_hash_iter_lookup (DBusHashTable *table,
00774                         void          *key,
00775                         dbus_bool_t    create_if_not_found,
00776                         DBusHashIter  *iter)
00777 {
00778   DBusRealHashIter *real;
00779   DBusHashEntry *entry;
00780   DBusHashEntry **bucket;
00781   
00782   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00783   
00784   real = (DBusRealHashIter*) iter;
00785 
00786   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00787 
00788   if (entry == NULL)
00789     return FALSE;
00790   
00791   real->table = table;
00792   real->bucket = bucket;
00793   real->entry = entry;
00794   real->next_entry = entry->next;
00795   real->next_bucket = (bucket - table->buckets) + 1;
00796   real->n_entries_on_init = table->n_entries; 
00797 
00798   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00799   
00800   return TRUE;
00801 }
00802 
00803 static void
00804 add_allocated_entry (DBusHashTable   *table,
00805                      DBusHashEntry   *entry,
00806                      unsigned int     idx,
00807                      void            *key,
00808                      DBusHashEntry ***bucket)
00809 {
00810   DBusHashEntry **b;  
00811   
00812   entry->key = key;
00813   
00814   b = &(table->buckets[idx]);
00815   entry->next = *b;
00816   *b = entry;
00817 
00818   if (bucket)
00819     *bucket = b;
00820   
00821   table->n_entries += 1;
00822 
00823   /* note we ONLY rebuild when ADDING - because you can iterate over a
00824    * table and remove entries safely.
00825    */
00826   if (table->n_entries >= table->hi_rebuild_size ||
00827       table->n_entries < table->lo_rebuild_size)
00828     rebuild_table (table);
00829 }
00830 
00831 static DBusHashEntry*
00832 add_entry (DBusHashTable        *table, 
00833            unsigned int          idx,
00834            void                 *key,
00835            DBusHashEntry      ***bucket,
00836            DBusPreallocatedHash *preallocated)
00837 {
00838   DBusHashEntry  *entry;
00839 
00840   if (preallocated == NULL)
00841     {
00842       entry = alloc_entry (table);
00843       if (entry == NULL)
00844         {
00845           if (bucket)
00846             *bucket = NULL;
00847           return NULL;
00848         }
00849     }
00850   else
00851     {
00852       entry = (DBusHashEntry*) preallocated;
00853     }
00854 
00855   add_allocated_entry (table, entry, idx, key, bucket);
00856 
00857   return entry;
00858 }
00859 
00860 /* This is g_str_hash from GLib which was
00861  * extensively discussed/tested/profiled
00862  */
00863 static unsigned int
00864 string_hash (const char *str)
00865 {
00866   const char *p = str;
00867   unsigned int h = *p;
00868 
00869   if (h)
00870     for (p += 1; *p != '\0'; p++)
00871       h = (h << 5) - h + *p;
00872 
00873   return h;
00874 }
00875 
00876 #ifdef DBUS_BUILD_TESTS
00877 /* This hashes a memory block with two nul-terminated strings
00878  * in it, used in dbus-object-registry.c at the moment.
00879  */
00880 static unsigned int
00881 two_strings_hash (const char *str)
00882 {
00883   const char *p = str;
00884   unsigned int h = *p;
00885 
00886   if (h)
00887     for (p += 1; *p != '\0'; p++)
00888       h = (h << 5) - h + *p;
00889 
00890   for (p += 1; *p != '\0'; p++)
00891     h = (h << 5) - h + *p;
00892   
00893   return h;
00894 }
00895 #endif /* DBUS_BUILD_TESTS */
00896 
00898 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00899 
00900 static DBusHashEntry*
00901 find_generic_function (DBusHashTable        *table,
00902                        void                 *key,
00903                        unsigned int          idx,
00904                        KeyCompareFunc        compare_func,
00905                        dbus_bool_t           create_if_not_found,
00906                        DBusHashEntry      ***bucket,
00907                        DBusPreallocatedHash *preallocated)
00908 {
00909   DBusHashEntry *entry;
00910 
00911   if (bucket)
00912     *bucket = NULL;
00913 
00914   /* Search all of the entries in this bucket. */
00915   entry = table->buckets[idx];
00916   while (entry != NULL)
00917     {
00918       if ((compare_func == NULL && key == entry->key) ||
00919           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00920         {
00921           if (bucket)
00922             *bucket = &(table->buckets[idx]);
00923 
00924           if (preallocated)
00925             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00926           
00927           return entry;
00928         }
00929       
00930       entry = entry->next;
00931     }
00932 
00933   if (create_if_not_found)
00934     entry = add_entry (table, idx, key, bucket, preallocated);
00935   else if (preallocated)
00936     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00937   
00938   return entry;
00939 }
00940 
00941 static DBusHashEntry*
00942 find_string_function (DBusHashTable        *table,
00943                       void                 *key,
00944                       dbus_bool_t           create_if_not_found,
00945                       DBusHashEntry      ***bucket,
00946                       DBusPreallocatedHash *preallocated)
00947 {
00948   unsigned int idx;
00949   
00950   idx = string_hash (key) & table->mask;
00951 
00952   return find_generic_function (table, key, idx,
00953                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00954                                 preallocated);
00955 }
00956 
00957 #ifdef DBUS_BUILD_TESTS
00958 static int
00959 two_strings_cmp (const char *a,
00960                  const char *b)
00961 {
00962   size_t len_a;
00963   size_t len_b;
00964   int res;
00965   
00966   res = strcmp (a, b);
00967   if (res != 0)
00968     return res;
00969 
00970   len_a = strlen (a);
00971   len_b = strlen (b);
00972 
00973   return strcmp (a + len_a + 1, b + len_b + 1);
00974 }
00975 #endif
00976 
00977 #ifdef DBUS_BUILD_TESTS
00978 static DBusHashEntry*
00979 find_two_strings_function (DBusHashTable        *table,
00980                            void                 *key,
00981                            dbus_bool_t           create_if_not_found,
00982                            DBusHashEntry      ***bucket,
00983                            DBusPreallocatedHash *preallocated)
00984 {
00985   unsigned int idx;
00986   
00987   idx = two_strings_hash (key) & table->mask;
00988 
00989   return find_generic_function (table, key, idx,
00990                                 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
00991                                 preallocated);
00992 }
00993 #endif /* DBUS_BUILD_TESTS */
00994 
00995 static DBusHashEntry*
00996 find_direct_function (DBusHashTable        *table,
00997                       void                 *key,
00998                       dbus_bool_t           create_if_not_found,
00999                       DBusHashEntry      ***bucket,
01000                       DBusPreallocatedHash *preallocated)
01001 {
01002   unsigned int idx;
01003   
01004   idx = RANDOM_INDEX (table, key) & table->mask;
01005 
01006 
01007   return find_generic_function (table, key, idx,
01008                                 NULL, create_if_not_found, bucket,
01009                                 preallocated);
01010 }
01011 
01012 static void
01013 rebuild_table (DBusHashTable *table)
01014 {
01015   int old_size;
01016   int new_buckets;
01017   DBusHashEntry **old_buckets;
01018   DBusHashEntry **old_chain;
01019   DBusHashEntry *entry;
01020   dbus_bool_t growing;
01021   
01022   /*
01023    * Allocate and initialize the new bucket array, and set up
01024    * hashing constants for new array size.
01025    */
01026 
01027   growing = table->n_entries >= table->hi_rebuild_size;
01028   
01029   old_size = table->n_buckets;
01030   old_buckets = table->buckets;
01031 
01032   if (growing)
01033     {
01034       /* overflow paranoia */
01035       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
01036           table->down_shift >= 0)
01037         new_buckets = table->n_buckets * 4;
01038       else
01039         return; /* can't grow anymore */
01040     }
01041   else
01042     {
01043       new_buckets = table->n_buckets / 4;
01044       if (new_buckets < DBUS_SMALL_HASH_TABLE)
01045         return; /* don't bother shrinking this far */
01046     }
01047 
01048   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
01049   if (table->buckets == NULL)
01050     {
01051       /* out of memory, yay - just don't reallocate, the table will
01052        * still work, albeit more slowly.
01053        */
01054       table->buckets = old_buckets;
01055       return;
01056     }
01057 
01058   table->n_buckets = new_buckets;
01059   
01060   if (growing)
01061     {
01062       table->lo_rebuild_size = table->hi_rebuild_size;
01063       table->hi_rebuild_size *= 4;
01064       
01065       table->down_shift -= 2;               /* keep 2 more high bits */
01066       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
01067     }
01068   else
01069     {
01070       table->hi_rebuild_size = table->lo_rebuild_size;
01071       table->lo_rebuild_size /= 4;
01072 
01073       table->down_shift += 2;         /* keep 2 fewer high bits */
01074       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
01075     }
01076 
01077 #if 0
01078   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
01079           growing ? "GROW" : "SHRINK",
01080           table->lo_rebuild_size,
01081           table->hi_rebuild_size,
01082           table->down_shift,
01083           table->mask);
01084 #endif
01085   
01086   _dbus_assert (table->lo_rebuild_size >= 0);
01087   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01088   _dbus_assert (table->mask != 0);
01089   /* the mask is essentially the max index */
01090   _dbus_assert (table->mask < table->n_buckets);
01091   
01092   /*
01093    * Rehash all of the existing entries into the new bucket array.
01094    */
01095 
01096   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01097     {
01098       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01099         {
01100           unsigned int idx;
01101           DBusHashEntry **bucket;
01102           
01103           *old_chain = entry->next;
01104           switch (table->key_type)
01105             {
01106             case DBUS_HASH_STRING:
01107               idx = string_hash (entry->key) & table->mask;
01108               break;
01109             case DBUS_HASH_TWO_STRINGS:
01110 #ifdef DBUS_BUILD_TESTS
01111               idx = two_strings_hash (entry->key) & table->mask;
01112 #else
01113               idx = 0;
01114               _dbus_assert_not_reached ("two-strings is not enabled");
01115 #endif
01116               break;
01117             case DBUS_HASH_INT:
01118             case DBUS_HASH_ULONG:
01119             case DBUS_HASH_POINTER:
01120               idx = RANDOM_INDEX (table, entry->key);
01121               break;
01122             default:
01123               idx = 0;
01124               _dbus_assert_not_reached ("Unknown hash table type");
01125               break;
01126             }
01127           
01128           bucket = &(table->buckets[idx]);
01129           entry->next = *bucket;
01130           *bucket = entry;
01131         }
01132     }
01133   
01134   /* Free the old bucket array, if it was dynamically allocated. */
01135 
01136   if (old_buckets != table->static_buckets)
01137     dbus_free (old_buckets);
01138 }
01139 
01149 void*
01150 _dbus_hash_table_lookup_string (DBusHashTable *table,
01151                                 const char    *key)
01152 {
01153   DBusHashEntry *entry;
01154 
01155   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01156   
01157   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01158 
01159   if (entry)
01160     return entry->value;
01161   else
01162     return NULL;
01163 }
01164 
01165 #ifdef DBUS_BUILD_TESTS
01166 
01175 void*
01176 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
01177                                      const char    *key)
01178 {
01179   DBusHashEntry *entry;
01180 
01181   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01182   
01183   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01184 
01185   if (entry)
01186     return entry->value;
01187   else
01188     return NULL;
01189 }
01190 #endif /* DBUS_BUILD_TESTS */
01191 
01201 void*
01202 _dbus_hash_table_lookup_int (DBusHashTable *table,
01203                              int            key)
01204 {
01205   DBusHashEntry *entry;
01206 
01207   _dbus_assert (table->key_type == DBUS_HASH_INT);
01208   
01209   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01210 
01211   if (entry)
01212     return entry->value;
01213   else
01214     return NULL;
01215 }
01216 
01217 #ifdef DBUS_BUILD_TESTS
01218 /* disabled since it's only used for testing */
01228 void*
01229 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01230                                  void          *key)
01231 {
01232   DBusHashEntry *entry;
01233 
01234   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01235   
01236   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01237 
01238   if (entry)
01239     return entry->value;
01240   else
01241     return NULL;
01242 }
01243 #endif /* DBUS_BUILD_TESTS */
01244 
01254 void*
01255 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
01256                                unsigned long  key)
01257 {
01258   DBusHashEntry *entry;
01259 
01260   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01261   
01262   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01263 
01264   if (entry)
01265     return entry->value;
01266   else
01267     return NULL;
01268 }
01269 
01278 dbus_bool_t
01279 _dbus_hash_table_remove_string (DBusHashTable *table,
01280                                 const char    *key)
01281 {
01282   DBusHashEntry *entry;
01283   DBusHashEntry **bucket;
01284   
01285   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01286   
01287   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01288 
01289   if (entry)
01290     {
01291       remove_entry (table, bucket, entry);
01292       return TRUE;
01293     }
01294   else
01295     return FALSE;
01296 }
01297 
01298 #ifdef DBUS_BUILD_TESTS
01299 
01307 dbus_bool_t
01308 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
01309                                      const char    *key)
01310 {
01311   DBusHashEntry *entry;
01312   DBusHashEntry **bucket;
01313   
01314   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01315   
01316   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01317 
01318   if (entry)
01319     {
01320       remove_entry (table, bucket, entry);
01321       return TRUE;
01322     }
01323   else
01324     return FALSE;
01325 }
01326 #endif /* DBUS_BUILD_TESTS */
01327 
01336 dbus_bool_t
01337 _dbus_hash_table_remove_int (DBusHashTable *table,
01338                              int            key)
01339 {
01340   DBusHashEntry *entry;
01341   DBusHashEntry **bucket;
01342   
01343   _dbus_assert (table->key_type == DBUS_HASH_INT);
01344   
01345   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01346   
01347   if (entry)
01348     {
01349       remove_entry (table, bucket, entry);
01350       return TRUE;
01351     }
01352   else
01353     return FALSE;
01354 }
01355 
01356 #ifdef DBUS_BUILD_TESTS
01357 /* disabled since it's only used for testing */
01366 dbus_bool_t
01367 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01368                                  void          *key)
01369 {
01370   DBusHashEntry *entry;
01371   DBusHashEntry **bucket;
01372   
01373   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01374   
01375   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01376   
01377   if (entry)
01378     {
01379       remove_entry (table, bucket, entry);
01380       return TRUE;
01381     }
01382   else
01383     return FALSE;
01384 }
01385 #endif /* DBUS_BUILD_TESTS */
01386 
01395 dbus_bool_t
01396 _dbus_hash_table_remove_ulong (DBusHashTable *table,
01397                                unsigned long  key)
01398 {
01399   DBusHashEntry *entry;
01400   DBusHashEntry **bucket;
01401   
01402   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01403   
01404   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01405   
01406   if (entry)
01407     {
01408       remove_entry (table, bucket, entry);
01409       return TRUE;
01410     }
01411   else
01412     return FALSE;
01413 }
01414 
01430 dbus_bool_t
01431 _dbus_hash_table_insert_string (DBusHashTable *table,
01432                                 char          *key,
01433                                 void          *value)
01434 {
01435   DBusPreallocatedHash *preallocated;
01436 
01437   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01438 
01439   preallocated = _dbus_hash_table_preallocate_entry (table);
01440   if (preallocated == NULL)
01441     return FALSE;
01442 
01443   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01444                                                key, value);
01445   
01446   return TRUE;
01447 }
01448 
01449 #ifdef DBUS_BUILD_TESTS
01450 
01465 dbus_bool_t
01466 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
01467                                      char          *key,
01468                                      void          *value)
01469 {
01470   DBusHashEntry *entry;
01471   
01472   _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01473   
01474   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01475 
01476   if (entry == NULL)
01477     return FALSE; /* no memory */
01478 
01479   if (table->free_key_function && entry->key != key)
01480     (* table->free_key_function) (entry->key);
01481   
01482   if (table->free_value_function && entry->value != value)
01483     (* table->free_value_function) (entry->value);
01484   
01485   entry->key = key;
01486   entry->value = value;
01487 
01488   return TRUE;
01489 }
01490 #endif /* DBUS_BUILD_TESTS */
01491 
01507 dbus_bool_t
01508 _dbus_hash_table_insert_int (DBusHashTable *table,
01509                              int            key,
01510                              void          *value)
01511 {
01512   DBusHashEntry *entry;
01513 
01514   _dbus_assert (table->key_type == DBUS_HASH_INT);
01515   
01516   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01517 
01518   if (entry == NULL)
01519     return FALSE; /* no memory */
01520 
01521   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01522     (* table->free_key_function) (entry->key);
01523   
01524   if (table->free_value_function && entry->value != value)
01525     (* table->free_value_function) (entry->value);
01526   
01527   entry->key = _DBUS_INT_TO_POINTER (key);
01528   entry->value = value;
01529 
01530   return TRUE;
01531 }
01532 
01533 #ifdef DBUS_BUILD_TESTS
01534 /* disabled since it's only used for testing */
01550 dbus_bool_t
01551 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01552                                  void          *key,
01553                                  void          *value)
01554 {
01555   DBusHashEntry *entry;
01556 
01557   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01558   
01559   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01560 
01561   if (entry == NULL)
01562     return FALSE; /* no memory */
01563 
01564   if (table->free_key_function && entry->key != key)
01565     (* table->free_key_function) (entry->key);
01566   
01567   if (table->free_value_function && entry->value != value)
01568     (* table->free_value_function) (entry->value);
01569   
01570   entry->key = key;
01571   entry->value = value;
01572 
01573   return TRUE;
01574 }
01575 #endif /* DBUS_BUILD_TESTS */
01576 
01592 dbus_bool_t
01593 _dbus_hash_table_insert_ulong (DBusHashTable *table,
01594                                unsigned long  key,
01595                                void          *value)
01596 {
01597   DBusHashEntry *entry;
01598 
01599   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01600   
01601   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01602 
01603   if (entry == NULL)
01604     return FALSE; /* no memory */
01605 
01606   if (table->free_key_function && entry->key != (void*) key)
01607     (* table->free_key_function) (entry->key);
01608   
01609   if (table->free_value_function && entry->value != value)
01610     (* table->free_value_function) (entry->value);
01611   
01612   entry->key = (void*) key;
01613   entry->value = value;
01614 
01615   return TRUE;
01616 }
01617 
01625 DBusPreallocatedHash*
01626 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01627 {
01628   DBusHashEntry *entry;
01629   
01630   entry = alloc_entry (table);
01631 
01632   return (DBusPreallocatedHash*) entry;
01633 }
01634 
01642 void
01643 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01644                                           DBusPreallocatedHash *preallocated)
01645 {
01646   DBusHashEntry *entry;
01647 
01648   _dbus_assert (preallocated != NULL);
01649   
01650   entry = (DBusHashEntry*) preallocated;
01651   
01652   /* Don't use free_entry(), since this entry has no key/data */
01653   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01654 }
01655 
01669 void
01670 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01671                                              DBusPreallocatedHash *preallocated,
01672                                              char                 *key,
01673                                              void                 *value)
01674 {
01675   DBusHashEntry *entry;
01676 
01677   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01678   _dbus_assert (preallocated != NULL);
01679   
01680   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01681 
01682   _dbus_assert (entry != NULL);
01683   
01684   if (table->free_key_function && entry->key != key)
01685     (* table->free_key_function) (entry->key);
01686 
01687   if (table->free_value_function && entry->value != value)
01688     (* table->free_value_function) (entry->value);
01689       
01690   entry->key = key;
01691   entry->value = value;
01692 }
01693 
01700 int
01701 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01702 {
01703   return table->n_entries;
01704 }
01705 
01708 #ifdef DBUS_BUILD_TESTS
01709 #include "dbus-test.h"
01710 #include <stdio.h>
01711 
01712 /* If you're wondering why the hash table test takes
01713  * forever to run, it's because we call this function
01714  * in inner loops thus making things quadratic.
01715  */
01716 static int
01717 count_entries (DBusHashTable *table)
01718 {
01719   DBusHashIter iter;
01720   int count;
01721 
01722   count = 0;
01723   _dbus_hash_iter_init (table, &iter);
01724   while (_dbus_hash_iter_next (&iter))
01725     ++count;
01726 
01727   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01728   
01729   return count;
01730 }
01731 
01732 /* Copy the foo\0bar\0 double string thing */
01733 static char*
01734 _dbus_strdup2 (const char *str)
01735 {
01736   size_t len;
01737   char *copy;
01738   
01739   if (str == NULL)
01740     return NULL;
01741   
01742   len = strlen (str);
01743   len += strlen ((str + len + 1));
01744 
01745   copy = dbus_malloc (len + 2);
01746   if (copy == NULL)
01747     return NULL;
01748 
01749   memcpy (copy, str, len + 2);
01750   
01751   return copy;
01752 }
01753 
01759 dbus_bool_t
01760 _dbus_hash_test (void)
01761 {
01762   int i;
01763   DBusHashTable *table1;
01764   DBusHashTable *table2;
01765   DBusHashTable *table3;
01766   DBusHashTable *table4;
01767   DBusHashIter iter;
01768 #define N_HASH_KEYS 5000
01769   char **keys;
01770   dbus_bool_t ret = FALSE;
01771 
01772   keys = dbus_new (char *, N_HASH_KEYS);
01773   if (keys == NULL)
01774     _dbus_assert_not_reached ("no memory");
01775 
01776   for (i = 0; i < N_HASH_KEYS; i++)
01777     {
01778       keys[i] = dbus_malloc (128);
01779 
01780       if (keys[i] == NULL)
01781         _dbus_assert_not_reached ("no memory");
01782     }
01783 
01784   printf ("Computing test hash keys...\n");
01785   i = 0;
01786   while (i < N_HASH_KEYS)
01787     {
01788       int len;
01789 
01790       /* all the hash keys are TWO_STRINGS, but
01791        * then we can also use those as regular strings.
01792        */
01793       
01794       len = sprintf (keys[i], "Hash key %d", i);
01795       sprintf (keys[i] + len + 1, "Two string %d", i);
01796       _dbus_assert (*(keys[i] + len) == '\0');
01797       _dbus_assert (*(keys[i] + len + 1) != '\0');
01798       ++i;
01799     }
01800   printf ("... done.\n");
01801   
01802   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01803                                  dbus_free, dbus_free);
01804   if (table1 == NULL)
01805     goto out;
01806 
01807   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01808                                  NULL, dbus_free);
01809   if (table2 == NULL)
01810     goto out;
01811 
01812   table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
01813                                  NULL, dbus_free);
01814   if (table3 == NULL)
01815     goto out;
01816 
01817   table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
01818                                  dbus_free, dbus_free);
01819   if (table4 == NULL)
01820     goto out;
01821 
01822   
01823   /* Insert and remove a bunch of stuff, counting the table in between
01824    * to be sure it's not broken and that iteration works
01825    */
01826   i = 0;
01827   while (i < 3000)
01828     {
01829       void *value;
01830       char *key;
01831 
01832       key = _dbus_strdup (keys[i]);
01833       if (key == NULL)
01834         goto out;
01835       value = _dbus_strdup ("Value!");
01836       if (value == NULL)
01837         goto out;
01838       
01839       if (!_dbus_hash_table_insert_string (table1,
01840                                            key, value))
01841         goto out;
01842 
01843       value = _dbus_strdup (keys[i]);
01844       if (value == NULL)
01845         goto out;
01846       
01847       if (!_dbus_hash_table_insert_int (table2,
01848                                         i, value))
01849         goto out;
01850 
01851       value = _dbus_strdup (keys[i]);
01852       if (value == NULL)
01853         goto out;
01854       
01855       if (!_dbus_hash_table_insert_ulong (table3,
01856                                           i, value))
01857         goto out;
01858 
01859       key = _dbus_strdup2 (keys[i]);
01860       if (key == NULL)
01861         goto out;
01862       value = _dbus_strdup ("Value!");
01863       if (value == NULL)
01864         goto out;
01865       
01866       if (!_dbus_hash_table_insert_two_strings (table4,
01867                                                 key, value))
01868         goto out;
01869       
01870       _dbus_assert (count_entries (table1) == i + 1);
01871       _dbus_assert (count_entries (table2) == i + 1);
01872       _dbus_assert (count_entries (table3) == i + 1);
01873       _dbus_assert (count_entries (table4) == i + 1);
01874 
01875       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01876       _dbus_assert (value != NULL);
01877       _dbus_assert (strcmp (value, "Value!") == 0);
01878 
01879       value = _dbus_hash_table_lookup_int (table2, i);
01880       _dbus_assert (value != NULL);
01881       _dbus_assert (strcmp (value, keys[i]) == 0);
01882 
01883       value = _dbus_hash_table_lookup_ulong (table3, i);
01884       _dbus_assert (value != NULL);
01885       _dbus_assert (strcmp (value, keys[i]) == 0);
01886 
01887       value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01888       _dbus_assert (value != NULL);
01889       _dbus_assert (strcmp (value, "Value!") == 0);
01890       
01891       ++i;
01892     }
01893 
01894   --i;
01895   while (i >= 0)
01896     {
01897       _dbus_hash_table_remove_string (table1,
01898                                       keys[i]);
01899 
01900       _dbus_hash_table_remove_int (table2, i);
01901 
01902       _dbus_hash_table_remove_ulong (table3, i); 
01903 
01904       _dbus_hash_table_remove_two_strings (table4,
01905                                            keys[i]);
01906       
01907       _dbus_assert (count_entries (table1) == i);
01908       _dbus_assert (count_entries (table2) == i);
01909       _dbus_assert (count_entries (table3) == i);
01910       _dbus_assert (count_entries (table4) == i);
01911 
01912       --i;
01913     }
01914 
01915   _dbus_hash_table_ref (table1);
01916   _dbus_hash_table_ref (table2);
01917   _dbus_hash_table_ref (table3);
01918   _dbus_hash_table_ref (table4);
01919   _dbus_hash_table_unref (table1);
01920   _dbus_hash_table_unref (table2);
01921   _dbus_hash_table_unref (table3);
01922   _dbus_hash_table_unref (table4);
01923   _dbus_hash_table_unref (table1);
01924   _dbus_hash_table_unref (table2);
01925   _dbus_hash_table_unref (table3);
01926   _dbus_hash_table_unref (table4);
01927   table3 = NULL;
01928 
01929   /* Insert a bunch of stuff then check
01930    * that iteration works correctly (finds the right
01931    * values, iter_set_value works, etc.)
01932    */
01933   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01934                                  dbus_free, dbus_free);
01935   if (table1 == NULL)
01936     goto out;
01937   
01938   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01939                                  NULL, dbus_free);
01940   if (table2 == NULL)
01941     goto out;
01942   
01943   i = 0;
01944   while (i < 5000)
01945     {
01946       char *key;
01947       void *value;      
01948       
01949       key = _dbus_strdup (keys[i]);
01950       if (key == NULL)
01951         goto out;
01952       value = _dbus_strdup ("Value!");
01953       if (value == NULL)
01954         goto out;
01955       
01956       if (!_dbus_hash_table_insert_string (table1,
01957                                            key, value))
01958         goto out;
01959 
01960       value = _dbus_strdup (keys[i]);
01961       if (value == NULL)
01962         goto out;
01963       
01964       if (!_dbus_hash_table_insert_int (table2,
01965                                         i, value))
01966         goto out;
01967       
01968       _dbus_assert (count_entries (table1) == i + 1);
01969       _dbus_assert (count_entries (table2) == i + 1);
01970       
01971       ++i;
01972     }
01973 
01974   _dbus_hash_iter_init (table1, &iter);
01975   while (_dbus_hash_iter_next (&iter))
01976     {
01977       const char *key;
01978       void *value;
01979 
01980       key = _dbus_hash_iter_get_string_key (&iter);
01981       value = _dbus_hash_iter_get_value (&iter);
01982 
01983       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01984 
01985       value = _dbus_strdup ("Different value!");
01986       if (value == NULL)
01987         goto out;
01988       
01989       _dbus_hash_iter_set_value (&iter, value);
01990 
01991       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01992     }
01993   
01994   _dbus_hash_iter_init (table1, &iter);
01995   while (_dbus_hash_iter_next (&iter))
01996     {
01997       _dbus_hash_iter_remove_entry (&iter);
01998       _dbus_assert (count_entries (table1) == i - 1);
01999       --i;
02000     }
02001 
02002   _dbus_hash_iter_init (table2, &iter);
02003   while (_dbus_hash_iter_next (&iter))
02004     {
02005       int key;
02006       void *value;
02007 
02008       key = _dbus_hash_iter_get_int_key (&iter);
02009       value = _dbus_hash_iter_get_value (&iter);
02010 
02011       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02012 
02013       value = _dbus_strdup ("Different value!");
02014       if (value == NULL)
02015         goto out;
02016       
02017       _dbus_hash_iter_set_value (&iter, value);
02018 
02019       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02020     }
02021 
02022   i = count_entries (table2);
02023   _dbus_hash_iter_init (table2, &iter);
02024   while (_dbus_hash_iter_next (&iter))
02025     {
02026       _dbus_hash_iter_remove_entry (&iter);
02027       _dbus_assert (count_entries (table2) + 1 == i);
02028       --i;
02029     }
02030 
02031   /* add/remove interleaved, to check that we grow/shrink the table
02032    * appropriately
02033    */
02034   i = 0;
02035   while (i < 1000)
02036     {
02037       char *key;
02038       void *value;
02039             
02040       key = _dbus_strdup (keys[i]);
02041       if (key == NULL)
02042         goto out;
02043 
02044       value = _dbus_strdup ("Value!");
02045       if (value == NULL)
02046         goto out;
02047       
02048       if (!_dbus_hash_table_insert_string (table1,
02049                                            key, value))
02050         goto out;
02051       
02052       ++i;
02053     }
02054 
02055   --i;
02056   while (i >= 0)
02057     {
02058       char *key;
02059       void *value;      
02060       
02061       key = _dbus_strdup (keys[i]);
02062       if (key == NULL)
02063         goto out;
02064       value = _dbus_strdup ("Value!");
02065       if (value == NULL)
02066         goto out;
02067 
02068       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02069         goto out;
02070       
02071       if (!_dbus_hash_table_insert_string (table1,
02072                                            key, value))
02073         goto out;
02074 
02075       if (!_dbus_hash_table_remove_string (table1, keys[i]))
02076         goto out;
02077       
02078       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
02079       
02080       --i;
02081     }
02082 
02083   /* nuke these tables */
02084   _dbus_hash_table_unref (table1);
02085   _dbus_hash_table_unref (table2);
02086 
02087 
02088   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
02089    * be sure that interface works.
02090    */
02091   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
02092                                  dbus_free, dbus_free);
02093   if (table1 == NULL)
02094     goto out;
02095   
02096   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
02097                                  NULL, dbus_free);
02098   if (table2 == NULL)
02099     goto out;
02100   
02101   i = 0;
02102   while (i < 3000)
02103     {
02104       void *value;
02105       char *key;
02106 
02107       key = _dbus_strdup (keys[i]);
02108       if (key == NULL)
02109         goto out;
02110       value = _dbus_strdup ("Value!");
02111       if (value == NULL)
02112         goto out;
02113       
02114       if (!_dbus_hash_iter_lookup (table1,
02115                                    key, TRUE, &iter))
02116         goto out;
02117       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02118       _dbus_hash_iter_set_value (&iter, value);
02119 
02120       value = _dbus_strdup (keys[i]);
02121       if (value == NULL)
02122         goto out;
02123 
02124       if (!_dbus_hash_iter_lookup (table2,
02125                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
02126         goto out;
02127       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02128       _dbus_hash_iter_set_value (&iter, value); 
02129       
02130       _dbus_assert (count_entries (table1) == i + 1);
02131       _dbus_assert (count_entries (table2) == i + 1);
02132 
02133       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02134         goto out;
02135       
02136       value = _dbus_hash_iter_get_value (&iter);
02137       _dbus_assert (value != NULL);
02138       _dbus_assert (strcmp (value, "Value!") == 0);
02139 
02140       /* Iterate just to be sure it works, though
02141        * it's a stupid thing to do
02142        */
02143       while (_dbus_hash_iter_next (&iter))
02144         ;
02145       
02146       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02147         goto out;
02148 
02149       value = _dbus_hash_iter_get_value (&iter);
02150       _dbus_assert (value != NULL);
02151       _dbus_assert (strcmp (value, keys[i]) == 0);
02152 
02153       /* Iterate just to be sure it works, though
02154        * it's a stupid thing to do
02155        */
02156       while (_dbus_hash_iter_next (&iter))
02157         ;
02158       
02159       ++i;
02160     }
02161 
02162   --i;
02163   while (i >= 0)
02164     {
02165       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02166         _dbus_assert_not_reached ("hash entry should have existed");
02167       _dbus_hash_iter_remove_entry (&iter);
02168       
02169       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02170         _dbus_assert_not_reached ("hash entry should have existed");
02171       _dbus_hash_iter_remove_entry (&iter);
02172 
02173       _dbus_assert (count_entries (table1) == i);
02174       _dbus_assert (count_entries (table2) == i);
02175 
02176       --i;
02177     }
02178 
02179   _dbus_hash_table_unref (table1);
02180   _dbus_hash_table_unref (table2);
02181 
02182   ret = TRUE;
02183 
02184  out:
02185   for (i = 0; i < N_HASH_KEYS; i++)
02186     dbus_free (keys[i]);
02187 
02188   dbus_free (keys);
02189   
02190   return ret;
02191 }
02192 
02193 #endif /* DBUS_BUILD_TESTS */

Generated on Tue Feb 24 16:40:39 2009 for D-Bus by  doxygen 1.5.1