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 unsigned int   string_hash          (const char             *str);
00235 static void           rebuild_table        (DBusHashTable          *table);
00236 static DBusHashEntry* alloc_entry          (DBusHashTable          *table);
00237 static void           remove_entry         (DBusHashTable          *table,
00238                                             DBusHashEntry         **bucket,
00239                                             DBusHashEntry          *entry);
00240 static void           free_entry           (DBusHashTable          *table,
00241                                             DBusHashEntry          *entry);
00242 static void           free_entry_data      (DBusHashTable          *table,
00243                                             DBusHashEntry          *entry);
00244 
00245 
00281 DBusHashTable*
00282 _dbus_hash_table_new (DBusHashType     type,
00283                       DBusFreeFunction key_free_function,
00284                       DBusFreeFunction value_free_function)
00285 {
00286   DBusHashTable *table;
00287   DBusMemPool *entry_pool;
00288   
00289   table = dbus_new0 (DBusHashTable, 1);
00290   if (table == NULL)
00291     return NULL;
00292 
00293   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00294   if (entry_pool == NULL)
00295     {
00296       dbus_free (table);
00297       return NULL;
00298     }
00299   
00300   table->refcount = 1;
00301   table->entry_pool = entry_pool;
00302   
00303   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00304   
00305   table->buckets = table->static_buckets;  
00306   table->n_buckets = DBUS_SMALL_HASH_TABLE;
00307   table->n_entries = 0;
00308   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00309   table->lo_rebuild_size = 0;
00310   table->down_shift = 28;
00311   table->mask = 3;
00312   table->key_type = type;
00313 
00314   _dbus_assert (table->mask < table->n_buckets);
00315   
00316   switch (table->key_type)
00317     {
00318     case DBUS_HASH_INT:
00319     case DBUS_HASH_POINTER:
00320     case DBUS_HASH_ULONG:
00321       table->find_function = find_direct_function;
00322       break;
00323     case DBUS_HASH_STRING:
00324       table->find_function = find_string_function;
00325       break;
00326     default:
00327       _dbus_assert_not_reached ("Unknown hash table type");
00328       break;
00329     }
00330 
00331   table->free_key_function = key_free_function;
00332   table->free_value_function = value_free_function;
00333 
00334   return table;
00335 }
00336 
00337 
00343 void
00344 _dbus_hash_table_ref (DBusHashTable *table)
00345 {
00346   table->refcount += 1;
00347 }
00348 
00355 void
00356 _dbus_hash_table_unref (DBusHashTable *table)
00357 {
00358   table->refcount -= 1;
00359 
00360   if (table->refcount == 0)
00361     {
00362 #if 0
00363       DBusHashEntry *entry;
00364       DBusHashEntry *next;
00365       int i;
00366 
00367       /* Free the entries in the table. */
00368       for (i = 0; i < table->n_buckets; i++)
00369         {
00370           entry = table->buckets[i];
00371           while (entry != NULL)
00372             {
00373               next = entry->next;
00374 
00375               free_entry (table, entry);
00376               
00377               entry = next;
00378             }
00379         }
00380 #else
00381       DBusHashEntry *entry;
00382       int i;
00383 
00384       /* Free the entries in the table. */
00385       for (i = 0; i < table->n_buckets; i++)
00386         {
00387           entry = table->buckets[i];
00388           while (entry != NULL)
00389             {
00390               free_entry_data (table, entry);
00391               
00392               entry = entry->next;
00393             }
00394         }
00395       /* We can do this very quickly with memory pools ;-) */
00396       _dbus_mem_pool_free (table->entry_pool);
00397 #endif
00398       
00399       /* Free the bucket array, if it was dynamically allocated. */
00400       if (table->buckets != table->static_buckets)
00401         dbus_free (table->buckets);
00402 
00403       dbus_free (table);
00404     }
00405 }
00406 
00407 static DBusHashEntry*
00408 alloc_entry (DBusHashTable *table)
00409 {
00410   DBusHashEntry *entry;
00411 
00412   entry = _dbus_mem_pool_alloc (table->entry_pool);
00413   
00414   return entry;
00415 }
00416 
00417 static void
00418 free_entry_data (DBusHashTable  *table,
00419                  DBusHashEntry  *entry)
00420 {
00421   if (table->free_key_function)
00422     (* table->free_key_function) (entry->key);
00423   if (table->free_value_function)
00424     (* table->free_value_function) (entry->value);
00425 }
00426 
00427 static void
00428 free_entry (DBusHashTable  *table,
00429             DBusHashEntry  *entry)
00430 {
00431   free_entry_data (table, entry);
00432   _dbus_mem_pool_dealloc (table->entry_pool, entry);
00433 }
00434 
00435 static void
00436 remove_entry (DBusHashTable  *table,
00437               DBusHashEntry **bucket,
00438               DBusHashEntry  *entry)
00439 {
00440   _dbus_assert (table != NULL);
00441   _dbus_assert (bucket != NULL);
00442   _dbus_assert (*bucket != NULL);  
00443   _dbus_assert (entry != NULL);
00444   
00445   if (*bucket == entry)
00446     *bucket = entry->next;
00447   else
00448     {
00449       DBusHashEntry *prev;
00450       prev = *bucket;
00451 
00452       while (prev->next != entry)
00453         prev = prev->next;      
00454       
00455       _dbus_assert (prev != NULL);
00456 
00457       prev->next = entry->next;
00458     }
00459   
00460   table->n_entries -= 1;
00461   free_entry (table, entry);
00462 }
00463 
00495 void
00496 _dbus_hash_iter_init (DBusHashTable *table,
00497                       DBusHashIter  *iter)
00498 {
00499   DBusRealHashIter *real;
00500   
00501   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00502   
00503   real = (DBusRealHashIter*) iter;
00504 
00505   real->table = table;
00506   real->bucket = NULL;
00507   real->entry = NULL;
00508   real->next_entry = NULL;
00509   real->next_bucket = 0;
00510   real->n_entries_on_init = table->n_entries;
00511 }
00512 
00521 dbus_bool_t
00522 _dbus_hash_iter_next (DBusHashIter  *iter)
00523 {
00524   DBusRealHashIter *real;
00525   
00526   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00527   
00528   real = (DBusRealHashIter*) iter;
00529 
00530   /* if this assertion failed someone probably added hash entries
00531    * during iteration, which is bad.
00532    */
00533   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00534   
00535   /* Remember that real->entry may have been deleted */
00536   
00537   while (real->next_entry == NULL)
00538     {
00539       if (real->next_bucket >= real->table->n_buckets)
00540         {
00541           /* invalidate iter and return false */
00542           real->entry = NULL;
00543           real->table = NULL;
00544           real->bucket = NULL;
00545           return FALSE;
00546         }
00547 
00548       real->bucket = &(real->table->buckets[real->next_bucket]);
00549       real->next_entry = *(real->bucket);
00550       real->next_bucket += 1;
00551     }
00552 
00553   _dbus_assert (real->next_entry != NULL);
00554   _dbus_assert (real->bucket != NULL);
00555   
00556   real->entry = real->next_entry;
00557   real->next_entry = real->entry->next;
00558   
00559   return TRUE;
00560 }
00561 
00570 void
00571 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00572 {
00573   DBusRealHashIter *real;
00574 
00575   real = (DBusRealHashIter*) iter;
00576 
00577   _dbus_assert (real->table != NULL);
00578   _dbus_assert (real->entry != NULL);
00579   _dbus_assert (real->bucket != NULL);
00580   
00581   remove_entry (real->table, real->bucket, real->entry);
00582 
00583   real->entry = NULL; /* make it crash if you try to use this entry */
00584 }
00585 
00591 void*
00592 _dbus_hash_iter_get_value (DBusHashIter *iter)
00593 {
00594   DBusRealHashIter *real;
00595 
00596   real = (DBusRealHashIter*) iter;
00597 
00598   _dbus_assert (real->table != NULL);
00599   _dbus_assert (real->entry != NULL);
00600 
00601   return real->entry->value;
00602 }
00603 
00614 void
00615 _dbus_hash_iter_set_value (DBusHashIter *iter,
00616                            void         *value)
00617 {
00618   DBusRealHashIter *real;
00619 
00620   real = (DBusRealHashIter*) iter;
00621 
00622   _dbus_assert (real->table != NULL);
00623   _dbus_assert (real->entry != NULL);
00624 
00625   if (real->table->free_value_function && value != real->entry->value)    
00626     (* real->table->free_value_function) (real->entry->value);
00627   
00628   real->entry->value = value;
00629 }
00630 
00637 int
00638 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00639 {
00640   DBusRealHashIter *real;
00641 
00642   real = (DBusRealHashIter*) iter;
00643 
00644   _dbus_assert (real->table != NULL);
00645   _dbus_assert (real->entry != NULL);
00646 
00647   return _DBUS_POINTER_TO_INT (real->entry->key);
00648 }
00649 
00656 unsigned long
00657 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
00658 {
00659   DBusRealHashIter *real;
00660 
00661   real = (DBusRealHashIter*) iter;
00662 
00663   _dbus_assert (real->table != NULL);
00664   _dbus_assert (real->entry != NULL);
00665 
00666   return (unsigned long) real->entry->key;
00667 }
00668 
00674 const char*
00675 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00676 {
00677   DBusRealHashIter *real;
00678 
00679   real = (DBusRealHashIter*) iter;
00680 
00681   _dbus_assert (real->table != NULL);
00682   _dbus_assert (real->entry != NULL);
00683 
00684   return real->entry->key;
00685 }
00686 
00718 dbus_bool_t
00719 _dbus_hash_iter_lookup (DBusHashTable *table,
00720                         void          *key,
00721                         dbus_bool_t    create_if_not_found,
00722                         DBusHashIter  *iter)
00723 {
00724   DBusRealHashIter *real;
00725   DBusHashEntry *entry;
00726   DBusHashEntry **bucket;
00727   
00728   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00729   
00730   real = (DBusRealHashIter*) iter;
00731 
00732   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00733 
00734   if (entry == NULL)
00735     return FALSE;
00736   
00737   real->table = table;
00738   real->bucket = bucket;
00739   real->entry = entry;
00740   real->next_entry = entry->next;
00741   real->next_bucket = (bucket - table->buckets) + 1;
00742   real->n_entries_on_init = table->n_entries; 
00743 
00744   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00745   
00746   return TRUE;
00747 }
00748 
00749 static void
00750 add_allocated_entry (DBusHashTable   *table,
00751                      DBusHashEntry   *entry,
00752                      unsigned int     idx,
00753                      void            *key,
00754                      DBusHashEntry ***bucket)
00755 {
00756   DBusHashEntry **b;  
00757   
00758   entry->key = key;
00759   
00760   b = &(table->buckets[idx]);
00761   entry->next = *b;
00762   *b = entry;
00763 
00764   if (bucket)
00765     *bucket = b;
00766   
00767   table->n_entries += 1;
00768 
00769   /* note we ONLY rebuild when ADDING - because you can iterate over a
00770    * table and remove entries safely.
00771    */
00772   if (table->n_entries >= table->hi_rebuild_size ||
00773       table->n_entries < table->lo_rebuild_size)
00774     rebuild_table (table);
00775 }
00776 
00777 static DBusHashEntry*
00778 add_entry (DBusHashTable        *table, 
00779            unsigned int          idx,
00780            void                 *key,
00781            DBusHashEntry      ***bucket,
00782            DBusPreallocatedHash *preallocated)
00783 {
00784   DBusHashEntry  *entry;
00785 
00786   if (preallocated == NULL)
00787     {
00788       entry = alloc_entry (table);
00789       if (entry == NULL)
00790         {
00791           if (bucket)
00792             *bucket = NULL;
00793           return NULL;
00794         }
00795     }
00796   else
00797     {
00798       entry = (DBusHashEntry*) preallocated;
00799     }
00800 
00801   add_allocated_entry (table, entry, idx, key, bucket);
00802 
00803   return entry;
00804 }
00805 
00806 static unsigned int
00807 string_hash (const char *str)
00808 {
00809   register unsigned int result;
00810   register int c;
00811 
00812   /*
00813    * I tried a zillion different hash functions and asked many other
00814    * people for advice.  Many people had their own favorite functions,
00815    * all different, but no-one had much idea why they were good ones.
00816    * I chose the one below (multiply by 9 and add new character)
00817    * because of the following reasons:
00818    *
00819    * 1. Multiplying by 10 is perfect for keys that are decimal strings,
00820    *    and multiplying by 9 is just about as good.
00821    * 2. Times-9 is (shift-left-3) plus (old).  This means that each
00822    *    character's bits hang around in the low-order bits of the
00823    *    hash value for ever, plus they spread fairly rapidly up to
00824    *    the high-order bits to fill out the hash value.  This seems
00825    *    works well both for decimal and non-decimal strings.
00826    */
00827 
00828   /* FIXME the hash function in GLib is better than this one */
00829   
00830   result = 0;
00831   while (TRUE)
00832     {
00833       c = *str;
00834       str++;
00835       if (c == 0)
00836         break;
00837       
00838       result += (result << 3) + c;
00839     }
00840   
00841   return result;
00842 }
00843 
00844 static DBusHashEntry*
00845 find_string_function (DBusHashTable        *table,
00846                       void                 *key,
00847                       dbus_bool_t           create_if_not_found,
00848                       DBusHashEntry      ***bucket,
00849                       DBusPreallocatedHash *preallocated)
00850 {
00851   DBusHashEntry *entry;
00852   unsigned int idx;
00853 
00854   if (bucket)
00855     *bucket = NULL;
00856   
00857   idx = string_hash (key) & table->mask;
00858 
00859   /* Search all of the entries in this bucket. */
00860   entry = table->buckets[idx];
00861   while (entry != NULL)
00862     {
00863       if (strcmp (key, entry->key) == 0)
00864         {
00865           if (bucket)
00866             *bucket = &(table->buckets[idx]);
00867 
00868           if (preallocated)
00869             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00870           
00871           return entry;
00872         }
00873       
00874       entry = entry->next;
00875     }
00876 
00877   if (create_if_not_found)
00878     entry = add_entry (table, idx, key, bucket, preallocated);
00879   else if (preallocated)
00880     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00881 
00882   return entry;
00883 }
00884 
00885 static DBusHashEntry*
00886 find_direct_function (DBusHashTable        *table,
00887                       void                 *key,
00888                       dbus_bool_t           create_if_not_found,
00889                       DBusHashEntry      ***bucket,
00890                       DBusPreallocatedHash *preallocated)
00891 {
00892   DBusHashEntry *entry;
00893   unsigned int idx;
00894 
00895   if (bucket)
00896     *bucket = NULL;
00897   
00898   idx = RANDOM_INDEX (table, key) & table->mask;
00899 
00900   /* Search all of the entries in this bucket. */
00901   entry = table->buckets[idx];
00902   while (entry != NULL)
00903     {
00904       if (key == entry->key)
00905         {
00906           if (bucket)
00907             *bucket = &(table->buckets[idx]);
00908 
00909           if (preallocated)
00910             _dbus_hash_table_free_preallocated_entry (table, preallocated);
00911           
00912           return entry;
00913         }
00914       
00915       entry = entry->next;
00916     }
00917 
00918   /* Entry not found.  Add a new one to the bucket. */
00919   if (create_if_not_found)
00920     entry = add_entry (table, idx, key, bucket, preallocated);
00921   else if (preallocated)
00922     _dbus_hash_table_free_preallocated_entry (table, preallocated);
00923 
00924   return entry;
00925 }
00926 
00927 static void
00928 rebuild_table (DBusHashTable *table)
00929 {
00930   int old_size;
00931   int new_buckets;
00932   DBusHashEntry **old_buckets;
00933   DBusHashEntry **old_chain;
00934   DBusHashEntry *entry;
00935   dbus_bool_t growing;
00936   
00937   /*
00938    * Allocate and initialize the new bucket array, and set up
00939    * hashing constants for new array size.
00940    */
00941 
00942   growing = table->n_entries >= table->hi_rebuild_size;
00943   
00944   old_size = table->n_buckets;
00945   old_buckets = table->buckets;
00946 
00947   if (growing)
00948     {
00949       /* overflow paranoia */
00950       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
00951           table->down_shift >= 0)
00952         new_buckets = table->n_buckets * 4;
00953       else
00954         return; /* can't grow anymore */
00955     }
00956   else
00957     {
00958       new_buckets = table->n_buckets / 4;
00959       if (new_buckets < DBUS_SMALL_HASH_TABLE)
00960         return; /* don't bother shrinking this far */
00961     }
00962 
00963   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
00964   if (table->buckets == NULL)
00965     {
00966       /* out of memory, yay - just don't reallocate, the table will
00967        * still work, albeit more slowly.
00968        */
00969       table->buckets = old_buckets;
00970       return;
00971     }
00972 
00973   table->n_buckets = new_buckets;
00974   
00975   if (growing)
00976     {
00977       table->lo_rebuild_size = table->hi_rebuild_size;
00978       table->hi_rebuild_size *= 4;
00979       
00980       table->down_shift -= 2;               /* keep 2 more high bits */
00981       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
00982     }
00983   else
00984     {
00985       table->hi_rebuild_size = table->lo_rebuild_size;
00986       table->lo_rebuild_size /= 4;
00987 
00988       table->down_shift += 2;         /* keep 2 fewer high bits */
00989       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
00990     }
00991 
00992 #if 0
00993   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
00994           growing ? "GROW" : "SHRINK",
00995           table->lo_rebuild_size,
00996           table->hi_rebuild_size,
00997           table->down_shift,
00998           table->mask);
00999 #endif
01000   
01001   _dbus_assert (table->lo_rebuild_size >= 0);
01002   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01003   _dbus_assert (table->mask != 0);
01004   /* the mask is essentially the max index */
01005   _dbus_assert (table->mask < table->n_buckets);
01006   
01007   /*
01008    * Rehash all of the existing entries into the new bucket array.
01009    */
01010 
01011   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01012     {
01013       for (entry = *old_chain; entry != NULL; entry = *old_chain)
01014         {
01015           unsigned int idx;
01016           DBusHashEntry **bucket;
01017           
01018           *old_chain = entry->next;
01019           switch (table->key_type)
01020             {
01021             case DBUS_HASH_STRING:
01022               idx = string_hash (entry->key) & table->mask;
01023               break;
01024             case DBUS_HASH_INT:
01025             case DBUS_HASH_ULONG:
01026             case DBUS_HASH_POINTER:
01027               idx = RANDOM_INDEX (table, entry->key);
01028               break;
01029             default:
01030               idx = 0;
01031               _dbus_assert_not_reached ("Unknown hash table type");
01032               break;
01033             }
01034           
01035           bucket = &(table->buckets[idx]);
01036           entry->next = *bucket;
01037           *bucket = entry;
01038         }
01039     }
01040   
01041   /* Free the old bucket array, if it was dynamically allocated. */
01042 
01043   if (old_buckets != table->static_buckets)
01044     dbus_free (old_buckets);
01045 }
01046 
01056 void*
01057 _dbus_hash_table_lookup_string (DBusHashTable *table,
01058                                 const char    *key)
01059 {
01060   DBusHashEntry *entry;
01061 
01062   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01063   
01064   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01065 
01066   if (entry)
01067     return entry->value;
01068   else
01069     return NULL;
01070 }
01071 
01081 void*
01082 _dbus_hash_table_lookup_int (DBusHashTable *table,
01083                              int            key)
01084 {
01085   DBusHashEntry *entry;
01086 
01087   _dbus_assert (table->key_type == DBUS_HASH_INT);
01088   
01089   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01090 
01091   if (entry)
01092     return entry->value;
01093   else
01094     return NULL;
01095 }
01096 
01097 #ifdef DBUS_BUILD_TESTS
01098 /* disabled since it's only used for testing */
01108 void*
01109 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01110                                  void          *key)
01111 {
01112   DBusHashEntry *entry;
01113 
01114   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01115   
01116   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01117 
01118   if (entry)
01119     return entry->value;
01120   else
01121     return NULL;
01122 }
01123 #endif /* DBUS_BUILD_TESTS */
01124 
01134 void*
01135 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
01136                                unsigned long  key)
01137 {
01138   DBusHashEntry *entry;
01139 
01140   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01141   
01142   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01143 
01144   if (entry)
01145     return entry->value;
01146   else
01147     return NULL;
01148 }
01149 
01158 dbus_bool_t
01159 _dbus_hash_table_remove_string (DBusHashTable *table,
01160                                 const char    *key)
01161 {
01162   DBusHashEntry *entry;
01163   DBusHashEntry **bucket;
01164   
01165   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01166   
01167   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01168 
01169   if (entry)
01170     {
01171       remove_entry (table, bucket, entry);
01172       return TRUE;
01173     }
01174   else
01175     return FALSE;
01176 }
01177 
01186 dbus_bool_t
01187 _dbus_hash_table_remove_int (DBusHashTable *table,
01188                              int            key)
01189 {
01190   DBusHashEntry *entry;
01191   DBusHashEntry **bucket;
01192   
01193   _dbus_assert (table->key_type == DBUS_HASH_INT);
01194   
01195   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01196   
01197   if (entry)
01198     {
01199       remove_entry (table, bucket, entry);
01200       return TRUE;
01201     }
01202   else
01203     return FALSE;
01204 }
01205 
01206 #ifdef DBUS_BUILD_TESTS
01207 /* disabled since it's only used for testing */
01216 dbus_bool_t
01217 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01218                                  void          *key)
01219 {
01220   DBusHashEntry *entry;
01221   DBusHashEntry **bucket;
01222   
01223   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01224   
01225   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01226   
01227   if (entry)
01228     {
01229       remove_entry (table, bucket, entry);
01230       return TRUE;
01231     }
01232   else
01233     return FALSE;
01234 }
01235 #endif /* DBUS_BUILD_TESTS */
01236 
01245 dbus_bool_t
01246 _dbus_hash_table_remove_ulong (DBusHashTable *table,
01247                                unsigned long  key)
01248 {
01249   DBusHashEntry *entry;
01250   DBusHashEntry **bucket;
01251   
01252   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01253   
01254   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01255   
01256   if (entry)
01257     {
01258       remove_entry (table, bucket, entry);
01259       return TRUE;
01260     }
01261   else
01262     return FALSE;
01263 }
01264 
01280 dbus_bool_t
01281 _dbus_hash_table_insert_string (DBusHashTable *table,
01282                                 char          *key,
01283                                 void          *value)
01284 {
01285   DBusPreallocatedHash *preallocated;
01286 
01287   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01288 
01289   preallocated = _dbus_hash_table_preallocate_entry (table);
01290   if (preallocated == NULL)
01291     return FALSE;
01292 
01293   _dbus_hash_table_insert_string_preallocated (table, preallocated,
01294                                                key, value);
01295   
01296   return TRUE;
01297 }
01298 
01314 dbus_bool_t
01315 _dbus_hash_table_insert_int (DBusHashTable *table,
01316                              int            key,
01317                              void          *value)
01318 {
01319   DBusHashEntry *entry;
01320 
01321   _dbus_assert (table->key_type == DBUS_HASH_INT);
01322   
01323   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01324 
01325   if (entry == NULL)
01326     return FALSE; /* no memory */
01327 
01328   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01329     (* table->free_key_function) (entry->key);
01330   
01331   if (table->free_value_function && entry->value != value)
01332     (* table->free_value_function) (entry->value);
01333   
01334   entry->key = _DBUS_INT_TO_POINTER (key);
01335   entry->value = value;
01336 
01337   return TRUE;
01338 }
01339 
01340 #ifdef DBUS_BUILD_TESTS
01341 /* disabled since it's only used for testing */
01357 dbus_bool_t
01358 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01359                                  void          *key,
01360                                  void          *value)
01361 {
01362   DBusHashEntry *entry;
01363 
01364   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01365   
01366   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01367 
01368   if (entry == NULL)
01369     return FALSE; /* no memory */
01370 
01371   if (table->free_key_function && entry->key != key)
01372     (* table->free_key_function) (entry->key);
01373   
01374   if (table->free_value_function && entry->value != value)
01375     (* table->free_value_function) (entry->value);
01376   
01377   entry->key = key;
01378   entry->value = value;
01379 
01380   return TRUE;
01381 }
01382 #endif /* DBUS_BUILD_TESTS */
01383 
01399 dbus_bool_t
01400 _dbus_hash_table_insert_ulong (DBusHashTable *table,
01401                                unsigned long  key,
01402                                void          *value)
01403 {
01404   DBusHashEntry *entry;
01405 
01406   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01407   
01408   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01409 
01410   if (entry == NULL)
01411     return FALSE; /* no memory */
01412 
01413   if (table->free_key_function && entry->key != (void*) key)
01414     (* table->free_key_function) (entry->key);
01415   
01416   if (table->free_value_function && entry->value != value)
01417     (* table->free_value_function) (entry->value);
01418   
01419   entry->key = (void*) key;
01420   entry->value = value;
01421 
01422   return TRUE;
01423 }
01424 
01432 DBusPreallocatedHash*
01433 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01434 {
01435   DBusHashEntry *entry;
01436   
01437   entry = alloc_entry (table);
01438 
01439   return (DBusPreallocatedHash*) entry;
01440 }
01441 
01449 void
01450 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
01451                                           DBusPreallocatedHash *preallocated)
01452 {
01453   DBusHashEntry *entry;
01454 
01455   _dbus_assert (preallocated != NULL);
01456   
01457   entry = (DBusHashEntry*) preallocated;
01458   
01459   /* Don't use free_entry(), since this entry has no key/data */
01460   _dbus_mem_pool_dealloc (table->entry_pool, entry);
01461 }
01462 
01476 void
01477 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
01478                                              DBusPreallocatedHash *preallocated,
01479                                              char                 *key,
01480                                              void                 *value)
01481 {
01482   DBusHashEntry *entry;
01483 
01484   _dbus_assert (table->key_type == DBUS_HASH_STRING);
01485   _dbus_assert (preallocated != NULL);
01486   
01487   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01488 
01489   _dbus_assert (entry != NULL);
01490   
01491   if (table->free_key_function && entry->key != key)
01492     (* table->free_key_function) (entry->key);
01493 
01494   if (table->free_value_function && entry->value != value)
01495     (* table->free_value_function) (entry->value);
01496       
01497   entry->key = key;
01498   entry->value = value;
01499 }
01500 
01507 int
01508 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01509 {
01510   return table->n_entries;
01511 }
01512 
01515 #ifdef DBUS_BUILD_TESTS
01516 #include "dbus-test.h"
01517 #include <stdio.h>
01518 
01519 /* If you're wondering why the hash table test takes
01520  * forever to run, it's because we call this function
01521  * in inner loops thus making things quadratic.
01522  */
01523 static int
01524 count_entries (DBusHashTable *table)
01525 {
01526   DBusHashIter iter;
01527   int count;
01528 
01529   count = 0;
01530   _dbus_hash_iter_init (table, &iter);
01531   while (_dbus_hash_iter_next (&iter))
01532     ++count;
01533 
01534   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01535   
01536   return count;
01537 }
01538 
01544 dbus_bool_t
01545 _dbus_hash_test (void)
01546 {
01547   int i;
01548   DBusHashTable *table1;
01549   DBusHashTable *table2;
01550   DBusHashTable *table3;
01551   DBusHashIter iter;
01552 #define N_HASH_KEYS 5000
01553   char **keys;
01554   dbus_bool_t ret = FALSE;
01555 
01556   keys = dbus_new (char *, N_HASH_KEYS);
01557   if (keys == NULL)
01558     _dbus_assert_not_reached ("no memory");
01559 
01560   for (i = 0; i < N_HASH_KEYS; i++)
01561     {
01562       keys[i] = dbus_malloc (128);
01563 
01564       if (keys[i] == NULL)
01565         _dbus_assert_not_reached ("no memory");
01566     }
01567 
01568   printf ("Computing test hash keys...\n");
01569   i = 0;
01570   while (i < N_HASH_KEYS)
01571     {
01572       sprintf (keys[i], "Hash key %d", i); 
01573       ++i;
01574     }
01575   printf ("... done.\n");
01576   
01577   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01578                                  dbus_free, dbus_free);
01579   if (table1 == NULL)
01580     goto out;
01581 
01582   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01583                                  NULL, dbus_free);
01584   if (table2 == NULL)
01585     goto out;
01586 
01587   table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
01588                                  NULL, dbus_free);
01589   if (table3 == NULL)
01590     goto out;
01591   
01592   /* Insert and remove a bunch of stuff, counting the table in between
01593    * to be sure it's not broken and that iteration works
01594    */
01595   i = 0;
01596   while (i < 3000)
01597     {
01598       void *value;
01599       char *key;
01600 
01601       key = _dbus_strdup (keys[i]);
01602       if (key == NULL)
01603         goto out;
01604       value = _dbus_strdup ("Value!");
01605       if (value == NULL)
01606         goto out;
01607       
01608       if (!_dbus_hash_table_insert_string (table1,
01609                                            key, value))
01610         goto out;
01611 
01612       value = _dbus_strdup (keys[i]);
01613       if (value == NULL)
01614         goto out;
01615       
01616       if (!_dbus_hash_table_insert_int (table2,
01617                                         i, value))
01618         goto out;
01619 
01620       value = _dbus_strdup (keys[i]);
01621       if (value == NULL)
01622         goto out;
01623       
01624       if (!_dbus_hash_table_insert_ulong (table3,
01625                                           i, value))
01626         goto out;
01627       
01628       _dbus_assert (count_entries (table1) == i + 1);
01629       _dbus_assert (count_entries (table2) == i + 1);
01630       _dbus_assert (count_entries (table3) == i + 1);
01631 
01632       value = _dbus_hash_table_lookup_string (table1, keys[i]);
01633       _dbus_assert (value != NULL);
01634       _dbus_assert (strcmp (value, "Value!") == 0);
01635 
01636       value = _dbus_hash_table_lookup_int (table2, i);
01637       _dbus_assert (value != NULL);
01638       _dbus_assert (strcmp (value, keys[i]) == 0);
01639 
01640       value = _dbus_hash_table_lookup_ulong (table3, i);
01641       _dbus_assert (value != NULL);
01642       _dbus_assert (strcmp (value, keys[i]) == 0);
01643       
01644       ++i;
01645     }
01646 
01647   --i;
01648   while (i >= 0)
01649     {
01650       _dbus_hash_table_remove_string (table1,
01651                                       keys[i]);
01652 
01653       _dbus_hash_table_remove_int (table2, i);
01654 
01655       _dbus_hash_table_remove_ulong (table3, i); 
01656 
01657       _dbus_assert (count_entries (table1) == i);
01658       _dbus_assert (count_entries (table2) == i);
01659       _dbus_assert (count_entries (table3) == i);
01660 
01661       --i;
01662     }
01663 
01664   _dbus_hash_table_ref (table1);
01665   _dbus_hash_table_ref (table2);
01666   _dbus_hash_table_ref (table3);
01667   _dbus_hash_table_unref (table1);
01668   _dbus_hash_table_unref (table2);
01669   _dbus_hash_table_unref (table3);
01670   _dbus_hash_table_unref (table1);
01671   _dbus_hash_table_unref (table2);
01672   _dbus_hash_table_unref (table3);
01673   table3 = NULL;
01674 
01675   /* Insert a bunch of stuff then check
01676    * that iteration works correctly (finds the right
01677    * values, iter_set_value works, etc.)
01678    */
01679   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01680                                  dbus_free, dbus_free);
01681   if (table1 == NULL)
01682     goto out;
01683   
01684   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01685                                  NULL, dbus_free);
01686   if (table2 == NULL)
01687     goto out;
01688   
01689   i = 0;
01690   while (i < 5000)
01691     {
01692       char *key;
01693       void *value;      
01694       
01695       key = _dbus_strdup (keys[i]);
01696       if (key == NULL)
01697         goto out;
01698       value = _dbus_strdup ("Value!");
01699       if (value == NULL)
01700         goto out;
01701       
01702       if (!_dbus_hash_table_insert_string (table1,
01703                                            key, value))
01704         goto out;
01705 
01706       value = _dbus_strdup (keys[i]);
01707       if (value == NULL)
01708         goto out;
01709       
01710       if (!_dbus_hash_table_insert_int (table2,
01711                                         i, value))
01712         goto out;
01713       
01714       _dbus_assert (count_entries (table1) == i + 1);
01715       _dbus_assert (count_entries (table2) == i + 1);
01716       
01717       ++i;
01718     }
01719 
01720   _dbus_hash_iter_init (table1, &iter);
01721   while (_dbus_hash_iter_next (&iter))
01722     {
01723       const char *key;
01724       void *value;
01725 
01726       key = _dbus_hash_iter_get_string_key (&iter);
01727       value = _dbus_hash_iter_get_value (&iter);
01728 
01729       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01730 
01731       value = _dbus_strdup ("Different value!");
01732       if (value == NULL)
01733         goto out;
01734       
01735       _dbus_hash_iter_set_value (&iter, value);
01736 
01737       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01738     }
01739   
01740   _dbus_hash_iter_init (table1, &iter);
01741   while (_dbus_hash_iter_next (&iter))
01742     {
01743       _dbus_hash_iter_remove_entry (&iter);
01744       _dbus_assert (count_entries (table1) == i - 1);
01745       --i;
01746     }
01747 
01748   _dbus_hash_iter_init (table2, &iter);
01749   while (_dbus_hash_iter_next (&iter))
01750     {
01751       int key;
01752       void *value;
01753 
01754       key = _dbus_hash_iter_get_int_key (&iter);
01755       value = _dbus_hash_iter_get_value (&iter);
01756 
01757       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01758 
01759       value = _dbus_strdup ("Different value!");
01760       if (value == NULL)
01761         goto out;
01762       
01763       _dbus_hash_iter_set_value (&iter, value);
01764 
01765       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01766     }
01767 
01768   i = count_entries (table2);
01769   _dbus_hash_iter_init (table2, &iter);
01770   while (_dbus_hash_iter_next (&iter))
01771     {
01772       _dbus_hash_iter_remove_entry (&iter);
01773       _dbus_assert (count_entries (table2) + 1 == i);
01774       --i;
01775     }
01776 
01777   /* add/remove interleaved, to check that we grow/shrink the table
01778    * appropriately
01779    */
01780   i = 0;
01781   while (i < 1000)
01782     {
01783       char *key;
01784       void *value;
01785             
01786       key = _dbus_strdup (keys[i]);
01787       if (key == NULL)
01788         goto out;
01789 
01790       value = _dbus_strdup ("Value!");
01791       if (value == NULL)
01792         goto out;
01793       
01794       if (!_dbus_hash_table_insert_string (table1,
01795                                            key, value))
01796         goto out;
01797       
01798       ++i;
01799     }
01800 
01801   --i;
01802   while (i >= 0)
01803     {
01804       char *key;
01805       void *value;      
01806       
01807       key = _dbus_strdup (keys[i]);
01808       if (key == NULL)
01809         goto out;
01810       value = _dbus_strdup ("Value!");
01811       if (value == NULL)
01812         goto out;
01813 
01814       if (!_dbus_hash_table_remove_string (table1, keys[i]))
01815         goto out;
01816       
01817       if (!_dbus_hash_table_insert_string (table1,
01818                                            key, value))
01819         goto out;
01820 
01821       if (!_dbus_hash_table_remove_string (table1, keys[i]))
01822         goto out;
01823       
01824       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
01825       
01826       --i;
01827     }
01828 
01829   /* nuke these tables */
01830   _dbus_hash_table_unref (table1);
01831   _dbus_hash_table_unref (table2);
01832 
01833 
01834   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
01835    * be sure that interface works.
01836    */
01837   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01838                                  dbus_free, dbus_free);
01839   if (table1 == NULL)
01840     goto out;
01841   
01842   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01843                                  NULL, dbus_free);
01844   if (table2 == NULL)
01845     goto out;
01846   
01847   i = 0;
01848   while (i < 3000)
01849     {
01850       void *value;
01851       char *key;
01852 
01853       key = _dbus_strdup (keys[i]);
01854       if (key == NULL)
01855         goto out;
01856       value = _dbus_strdup ("Value!");
01857       if (value == NULL)
01858         goto out;
01859       
01860       if (!_dbus_hash_iter_lookup (table1,
01861                                    key, TRUE, &iter))
01862         goto out;
01863       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01864       _dbus_hash_iter_set_value (&iter, value);
01865 
01866       value = _dbus_strdup (keys[i]);
01867       if (value == NULL)
01868         goto out;
01869 
01870       if (!_dbus_hash_iter_lookup (table2,
01871                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
01872         goto out;
01873       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01874       _dbus_hash_iter_set_value (&iter, value); 
01875       
01876       _dbus_assert (count_entries (table1) == i + 1);
01877       _dbus_assert (count_entries (table2) == i + 1);
01878 
01879       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01880         goto out;
01881       
01882       value = _dbus_hash_iter_get_value (&iter);
01883       _dbus_assert (value != NULL);
01884       _dbus_assert (strcmp (value, "Value!") == 0);
01885 
01886       /* Iterate just to be sure it works, though
01887        * it's a stupid thing to do
01888        */
01889       while (_dbus_hash_iter_next (&iter))
01890         ;
01891       
01892       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01893         goto out;
01894 
01895       value = _dbus_hash_iter_get_value (&iter);
01896       _dbus_assert (value != NULL);
01897       _dbus_assert (strcmp (value, keys[i]) == 0);
01898 
01899       /* Iterate just to be sure it works, though
01900        * it's a stupid thing to do
01901        */
01902       while (_dbus_hash_iter_next (&iter))
01903         ;
01904       
01905       ++i;
01906     }
01907 
01908   --i;
01909   while (i >= 0)
01910     {
01911       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01912         _dbus_assert_not_reached ("hash entry should have existed");
01913       _dbus_hash_iter_remove_entry (&iter);
01914       
01915       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01916         _dbus_assert_not_reached ("hash entry should have existed");
01917       _dbus_hash_iter_remove_entry (&iter);
01918 
01919       _dbus_assert (count_entries (table1) == i);
01920       _dbus_assert (count_entries (table2) == i);
01921 
01922       --i;
01923     }
01924 
01925   _dbus_hash_table_unref (table1);
01926   _dbus_hash_table_unref (table2);
01927 
01928   ret = TRUE;
01929 
01930  out:
01931   for (i = 0; i < N_HASH_KEYS; i++)
01932     dbus_free (keys[i]);
01933 
01934   dbus_free (keys);
01935   
01936   return ret;
01937 }
01938 
01939 #endif /* DBUS_BUILD_TESTS */

Generated on Wed Oct 22 14:05:01 2003 for D-BUS by doxygen1.3-rc3