Merge branch 'dbus-1.4'
[platform/upstream/dbus.git] / dbus / dbus-hash.c
1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
3  * 
4  * Copyright (C) 2002  Red Hat, Inc.
5  * Copyright (c) 1991-1993 The Regents of the University of California.
6  * Copyright (c) 1994 Sun Microsystems, Inc.
7  * 
8  * Hash table implementation based on generic/tclHash.c from the Tcl
9  * source code. The original Tcl license applies to portions of the
10  * code from tclHash.c; the Tcl license follows this standad D-Bus 
11  * license information.
12  *
13  * Licensed under the Academic Free License version 2.1
14  * 
15  * This program is free software; you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation; either version 2 of the License, or
18  * (at your option) any later version.
19  *
20  * This program is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23  * GNU General Public License for more details.
24  * 
25  * You should have received a copy of the GNU General Public License
26  * along with this program; if not, write to the Free Software
27  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
28  *
29  */
30 /* 
31  * The following copyright applies to code from the Tcl distribution.
32  *
33  * Copyright (c) 1991-1993 The Regents of the University of California.
34  * Copyright (c) 1994 Sun Microsystems, Inc.
35  *
36  * This software is copyrighted by the Regents of the University of
37  * California, Sun Microsystems, Inc., Scriptics Corporation, and
38  * other parties.  The following terms apply to all files associated
39  * with the software unless explicitly disclaimed in individual files.
40  * 
41  * The authors hereby grant permission to use, copy, modify,
42  * distribute, and license this software and its documentation for any
43  * purpose, provided that existing copyright notices are retained in
44  * all copies and that this notice is included verbatim in any
45  * distributions. No written agreement, license, or royalty fee is
46  * required for any of the authorized uses.  Modifications to this
47  * software may be copyrighted by their authors and need not follow
48  * the licensing terms described here, provided that the new terms are
49  * clearly indicated on the first page of each file where they apply.
50  * 
51  * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
52  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
53  * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
54  * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
55  * OF THE POSSIBILITY OF SUCH DAMAGE.
56  * 
57  * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
58  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
59  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
60  * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
61  * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
62  * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
63  * 
64  * GOVERNMENT USE: If you are acquiring this software on behalf of the
65  * U.S. government, the Government shall have only "Restricted Rights"
66  * in the software and related documentation as defined in the Federal
67  * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
68  * are acquiring the software on behalf of the Department of Defense,
69  * the software shall be classified as "Commercial Computer Software"
70  * and the Government shall have only "Restricted Rights" as defined
71  * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
72  * foregoing, the authors grant the U.S. Government and others acting
73  * in its behalf permission to use and distribute the software in
74  * accordance with the terms specified in this license.
75  */
76
77 #include <config.h>
78 #include "dbus-hash.h"
79 #include "dbus-internals.h"
80 #include "dbus-mempool.h"
81
82 /**
83  * @defgroup DBusHashTable Hash table
84  * @ingroup  DBusInternals
85  * @brief DBusHashTable data structure
86  *
87  * Types and functions related to DBusHashTable.
88  */
89
90 /**
91  * @defgroup DBusHashTableInternals Hash table implementation details
92  * @ingroup  DBusInternals
93  * @brief DBusHashTable implementation details
94  *
95  * The guts of DBusHashTable.
96  *
97  * @{
98  */
99
100 /**
101  * When there are this many entries per bucket, on average, rebuild
102  * the hash table to make it larger.
103  */
104 #define REBUILD_MULTIPLIER  3
105
106 /**
107  * Takes a preliminary integer hash value and produces an index into a
108  * hash tables bucket list.  The idea is to make it so that
109  * preliminary values that are arbitrarily similar will end up in
110  * different buckets.  The hash function was taken from a
111  * random-number generator. (This is used to hash integers.)
112  *
113  * The down_shift drops off the high bits of the hash index, and
114  * decreases as we increase the number of hash buckets (to keep more
115  * range in the hash index). The mask also strips high bits and strips
116  * fewer high bits as the number of hash buckets increases.
117  * I don't understand two things: why is the initial downshift 28
118  * to keep 4 bits when the initial mask is 011 to keep 2 bits,
119  * and why do we have both a mask and a downshift?
120  * 
121  */
122 #define RANDOM_INDEX(table, i) \
123     (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
124
125 /**
126  * Initial number of buckets in hash table (hash table statically
127  * allocates its buckets for this size and below).
128  * The initial mask has to be synced to this.
129  */
130 #define DBUS_SMALL_HASH_TABLE 4
131
132 /**
133  * Typedef for DBusHashEntry
134  */
135 typedef struct DBusHashEntry DBusHashEntry;
136
137 /**
138  * @brief Internal representation of a hash entry.
139  * 
140  * A single entry (key-value pair) in the hash table.
141  * Internal to hash table implementation.
142  */
143 struct DBusHashEntry
144 {
145   DBusHashEntry *next;    /**< Pointer to next entry in this
146                            * hash bucket, or #NULL for end of
147                            * chain.
148                            */
149   void *key;              /**< Hash key */
150   void *value;            /**< Hash value */
151 };
152
153 /**
154  * Function used to find and optionally create a hash entry.
155  */
156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable        *table,
157                                                   void                 *key,
158                                                   dbus_bool_t           create_if_not_found,
159                                                   DBusHashEntry      ***bucket,
160                                                   DBusPreallocatedHash *preallocated);
161
162 /**
163  * @brief Internals of DBusHashTable.
164  * 
165  * Hash table internals. Hash tables are opaque objects, they must be
166  * used via accessor functions.
167  */
168 struct DBusHashTable {
169   int refcount;                       /**< Reference count */
170   
171   DBusHashEntry **buckets;            /**< Pointer to bucket array.  Each
172                                        * element points to first entry in
173                                        * bucket's hash chain, or #NULL.
174                                        */
175   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
176                                        /**< Bucket array used for small tables
177                                         * (to avoid mallocs and frees).
178                                         */
179   int n_buckets;                       /**< Total number of buckets allocated
180                                         * at **buckets.
181                                         */
182   int n_entries;                       /**< Total number of entries present
183                                         * in table.
184                                         */
185   int hi_rebuild_size;                 /**< Enlarge table when n_entries gets
186                                         * to be this large.
187                                         */
188   int lo_rebuild_size;                 /**< Shrink table when n_entries gets
189                                         * below this.
190                                         */
191   int down_shift;                      /**< Shift count used in hashing
192                                         * function.  Designed to use high-
193                                         * order bits of randomized keys.
194                                         */
195   int mask;                            /**< Mask value used in hashing
196                                         * function.
197                                         */
198   DBusHashType key_type;               /**< Type of keys used in this table */
199
200
201   DBusFindEntryFunction find_function; /**< Function for finding entries */
202
203   DBusFreeFunction free_key_function;   /**< Function to free keys */
204   DBusFreeFunction free_value_function; /**< Function to free values */
205
206   DBusMemPool *entry_pool;              /**< Memory pool for hash entries */
207 };
208
209 /** 
210  * @brief Internals of DBusHashIter.
211  */
212 typedef struct
213 {
214   DBusHashTable *table;     /**< Pointer to table containing entry. */
215   DBusHashEntry **bucket;   /**< Pointer to bucket that points to
216                              * first entry in this entry's chain:
217                              * used for deleting the entry.
218                              */
219   DBusHashEntry *entry;      /**< Current hash entry */
220   DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
221   int next_bucket;           /**< index of next bucket */
222   int n_entries_on_init;     /**< used to detect table resize since initialization */
223 } DBusRealHashIter;
224
225 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
226
227 static DBusHashEntry* find_direct_function      (DBusHashTable          *table,
228                                                  void                   *key,
229                                                  dbus_bool_t             create_if_not_found,
230                                                  DBusHashEntry        ***bucket,
231                                                  DBusPreallocatedHash   *preallocated);
232 static DBusHashEntry* find_string_function      (DBusHashTable          *table,
233                                                  void                   *key,
234                                                  dbus_bool_t             create_if_not_found,
235                                                  DBusHashEntry        ***bucket,
236                                                  DBusPreallocatedHash   *preallocated);
237 static unsigned int   string_hash               (const char             *str);
238 static void           rebuild_table             (DBusHashTable          *table);
239 static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
240 static void           remove_entry              (DBusHashTable          *table,
241                                                  DBusHashEntry         **bucket,
242                                                  DBusHashEntry          *entry);
243 static void           free_entry                (DBusHashTable          *table,
244                                                  DBusHashEntry          *entry);
245 static void           free_entry_data           (DBusHashTable          *table,
246                                                  DBusHashEntry          *entry);
247
248
249 /** @} */
250
251 /**
252  * @addtogroup DBusHashTable
253  * @{
254  */
255
256 /**
257  * @typedef DBusHashIter
258  *
259  * Public opaque hash table iterator object.
260  */
261
262 /**
263  * @typedef DBusHashTable
264  *
265  * Public opaque hash table object.
266  */
267
268 /**
269  * @typedef DBusHashType
270  *
271  * Indicates the type of a key in the hash table.
272  */
273
274 /**
275  * Constructs a new hash table. Should be freed with
276  * _dbus_hash_table_unref(). If memory cannot be
277  * allocated for the hash table, returns #NULL.
278  *
279  * @param type the type of hash key to use.
280  * @param key_free_function function to free hash keys.
281  * @param value_free_function function to free hash values.
282  * @returns a new DBusHashTable or #NULL if no memory.
283  */
284 DBusHashTable*
285 _dbus_hash_table_new (DBusHashType     type,
286                       DBusFreeFunction key_free_function,
287                       DBusFreeFunction value_free_function)
288 {
289   DBusHashTable *table;
290   DBusMemPool *entry_pool;
291   
292   table = dbus_new0 (DBusHashTable, 1);
293   if (table == NULL)
294     return NULL;
295
296   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
297   if (entry_pool == NULL)
298     {
299       dbus_free (table);
300       return NULL;
301     }
302   
303   table->refcount = 1;
304   table->entry_pool = entry_pool;
305   
306   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
307   
308   table->buckets = table->static_buckets;  
309   table->n_buckets = DBUS_SMALL_HASH_TABLE;
310   table->n_entries = 0;
311   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
312   table->lo_rebuild_size = 0;
313   table->down_shift = 28;
314   table->mask = 3;
315   table->key_type = type;
316
317   _dbus_assert (table->mask < table->n_buckets);
318   
319   switch (table->key_type)
320     {
321     case DBUS_HASH_INT:
322     case DBUS_HASH_UINTPTR:
323       table->find_function = find_direct_function;
324       break;
325     case DBUS_HASH_STRING:
326       table->find_function = find_string_function;
327       break;
328     default:
329       _dbus_assert_not_reached ("Unknown hash table type");
330       break;
331     }
332
333   table->free_key_function = key_free_function;
334   table->free_value_function = value_free_function;
335
336   return table;
337 }
338
339
340 /**
341  * Increments the reference count for a hash table.
342  *
343  * @param table the hash table to add a reference to.
344  * @returns the hash table.
345  */
346 DBusHashTable *
347 _dbus_hash_table_ref (DBusHashTable *table)
348 {
349   table->refcount += 1;
350   
351   return table;
352 }
353
354 /**
355  * Decrements the reference count for a hash table,
356  * freeing the hash table if the count reaches zero.
357  *
358  * @param table the hash table to remove a reference from.
359  */
360 void
361 _dbus_hash_table_unref (DBusHashTable *table)
362 {
363   table->refcount -= 1;
364
365   if (table->refcount == 0)
366     {
367 #if 0
368       DBusHashEntry *entry;
369       DBusHashEntry *next;
370       int i;
371
372       /* Free the entries in the table. */
373       for (i = 0; i < table->n_buckets; i++)
374         {
375           entry = table->buckets[i];
376           while (entry != NULL)
377             {
378               next = entry->next;
379
380               free_entry (table, entry);
381               
382               entry = next;
383             }
384         }
385 #else
386       DBusHashEntry *entry;
387       int i;
388
389       /* Free the entries in the table. */
390       for (i = 0; i < table->n_buckets; i++)
391         {
392           entry = table->buckets[i];
393           while (entry != NULL)
394             {
395               free_entry_data (table, entry);
396               
397               entry = entry->next;
398             }
399         }
400       /* We can do this very quickly with memory pools ;-) */
401       _dbus_mem_pool_free (table->entry_pool);
402 #endif
403       
404       /* Free the bucket array, if it was dynamically allocated. */
405       if (table->buckets != table->static_buckets)
406         dbus_free (table->buckets);
407
408       dbus_free (table);
409     }
410 }
411
412 /**
413  * Removed all entries from a hash table.
414  *
415  * @param table the hash table to remove all entries from.
416  */
417 void
418 _dbus_hash_table_remove_all (DBusHashTable *table)
419 {
420   DBusHashIter iter;
421   _dbus_hash_iter_init (table, &iter);
422   while (_dbus_hash_iter_next (&iter))
423     {
424       _dbus_hash_iter_remove_entry(&iter);
425     }
426 }
427
428 static DBusHashEntry*
429 alloc_entry (DBusHashTable *table)
430 {
431   DBusHashEntry *entry;
432
433   entry = _dbus_mem_pool_alloc (table->entry_pool);
434   
435   return entry;
436 }
437
438 static void
439 free_entry_data (DBusHashTable  *table,
440                  DBusHashEntry  *entry)
441 {
442   if (table->free_key_function)
443     (* table->free_key_function) (entry->key);
444   if (table->free_value_function)
445     (* table->free_value_function) (entry->value);
446 }
447
448 static void
449 free_entry (DBusHashTable  *table,
450             DBusHashEntry  *entry)
451 {
452   free_entry_data (table, entry);
453   _dbus_mem_pool_dealloc (table->entry_pool, entry);
454 }
455
456 static void
457 remove_entry (DBusHashTable  *table,
458               DBusHashEntry **bucket,
459               DBusHashEntry  *entry)
460 {
461   _dbus_assert (table != NULL);
462   _dbus_assert (bucket != NULL);
463   _dbus_assert (*bucket != NULL);  
464   _dbus_assert (entry != NULL);
465   
466   if (*bucket == entry)
467     *bucket = entry->next;
468   else
469     {
470       DBusHashEntry *prev;
471       prev = *bucket;
472
473       while (prev->next != entry)
474         prev = prev->next;      
475       
476       _dbus_assert (prev != NULL);
477
478       prev->next = entry->next;
479     }
480   
481   table->n_entries -= 1;
482   free_entry (table, entry);
483 }
484
485 /**
486  * Initializes a hash table iterator. To iterate over all entries in a
487  * hash table, use the following code (the printf assumes a hash
488  * from strings to strings obviously):
489  *
490  * @code
491  * DBusHashIter iter;
492  *
493  * _dbus_hash_iter_init (table, &iter);
494  * while (_dbus_hash_iter_next (&iter))
495  *   {
496  *      printf ("The first key is %s and value is %s\n",
497  *              _dbus_hash_iter_get_string_key (&iter),
498  *              _dbus_hash_iter_get_value (&iter));
499  *   }
500  * 
501  * 
502  * @endcode
503  *
504  * The iterator is initialized pointing "one before" the first hash
505  * entry. The first call to _dbus_hash_iter_next() moves it onto
506  * the first valid entry or returns #FALSE if the hash table is
507  * empty. Subsequent calls move to the next valid entry or return
508  * #FALSE if there are no more entries.
509  *
510  * Note that it is guaranteed to be safe to remove a hash entry during
511  * iteration, but it is not safe to add a hash entry.
512  * 
513  * @param table the hash table to iterate over.
514  * @param iter the iterator to initialize.
515  */
516 void
517 _dbus_hash_iter_init (DBusHashTable *table,
518                       DBusHashIter  *iter)
519 {
520   DBusRealHashIter *real;
521   
522   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
523   
524   real = (DBusRealHashIter*) iter;
525
526   real->table = table;
527   real->bucket = NULL;
528   real->entry = NULL;
529   real->next_entry = NULL;
530   real->next_bucket = 0;
531   real->n_entries_on_init = table->n_entries;
532 }
533
534 /**
535  * Move the hash iterator forward one step, to the next hash entry.
536  * The documentation for _dbus_hash_iter_init() explains in more
537  * detail.
538  *
539  * @param iter the iterator to move forward.
540  * @returns #FALSE if there are no more entries to move to.
541  */
542 dbus_bool_t
543 _dbus_hash_iter_next (DBusHashIter  *iter)
544 {
545   DBusRealHashIter *real;
546   
547   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
548   
549   real = (DBusRealHashIter*) iter;
550
551   /* if this assertion failed someone probably added hash entries
552    * during iteration, which is bad.
553    */
554   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
555   
556   /* Remember that real->entry may have been deleted */
557   
558   while (real->next_entry == NULL)
559     {
560       if (real->next_bucket >= real->table->n_buckets)
561         {
562           /* invalidate iter and return false */
563           real->entry = NULL;
564           real->table = NULL;
565           real->bucket = NULL;
566           return FALSE;
567         }
568
569       real->bucket = &(real->table->buckets[real->next_bucket]);
570       real->next_entry = *(real->bucket);
571       real->next_bucket += 1;
572     }
573
574   _dbus_assert (real->next_entry != NULL);
575   _dbus_assert (real->bucket != NULL);
576   
577   real->entry = real->next_entry;
578   real->next_entry = real->entry->next;
579   
580   return TRUE;
581 }
582
583 /**
584  * Removes the current entry from the hash table.
585  * If a key_free_function or value_free_function
586  * was provided to _dbus_hash_table_new(),
587  * frees the key and/or value for this entry.
588  *
589  * @param iter the hash table iterator.
590  */
591 void
592 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
593 {
594   DBusRealHashIter *real;
595
596   real = (DBusRealHashIter*) iter;
597
598   _dbus_assert (real->table != NULL);
599   _dbus_assert (real->entry != NULL);
600   _dbus_assert (real->bucket != NULL);
601   
602   remove_entry (real->table, real->bucket, real->entry);
603
604   real->entry = NULL; /* make it crash if you try to use this entry */
605 }
606
607 /**
608  * Gets the value of the current entry.
609  *
610  * @param iter the hash table iterator.
611  */
612 void*
613 _dbus_hash_iter_get_value (DBusHashIter *iter)
614 {
615   DBusRealHashIter *real;
616
617   real = (DBusRealHashIter*) iter;
618
619   _dbus_assert (real->table != NULL);
620   _dbus_assert (real->entry != NULL);
621
622   return real->entry->value;
623 }
624
625 /**
626  * Sets the value of the current entry.
627  * If the hash table has a value_free_function
628  * it will be used to free the previous value.
629  * The hash table will own the passed-in value
630  * (it will not be copied).
631  *
632  * @param iter the hash table iterator.
633  * @param value the new value.
634  */
635 void
636 _dbus_hash_iter_set_value (DBusHashIter *iter,
637                            void         *value)
638 {
639   DBusRealHashIter *real;
640
641   real = (DBusRealHashIter*) iter;
642
643   _dbus_assert (real->table != NULL);
644   _dbus_assert (real->entry != NULL);
645
646   if (real->table->free_value_function && value != real->entry->value)    
647     (* real->table->free_value_function) (real->entry->value);
648   
649   real->entry->value = value;
650 }
651
652 /**
653  * Gets the key for the current entry.
654  * Only works for hash tables of type #DBUS_HASH_INT.
655  *
656  * @param iter the hash table iterator.
657  */
658 int
659 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
660 {
661   DBusRealHashIter *real;
662
663   real = (DBusRealHashIter*) iter;
664
665   _dbus_assert (real->table != NULL);
666   _dbus_assert (real->entry != NULL);
667
668   return _DBUS_POINTER_TO_INT (real->entry->key);
669 }
670
671 /**
672  * Gets the key for the current entry.
673  * Only works for hash tables of type #DBUS_HASH_UINTPTR.
674  *
675  * @param iter the hash table iterator.
676  */
677 uintptr_t
678 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
679 {
680   DBusRealHashIter *real;
681
682   real = (DBusRealHashIter*) iter;
683
684   _dbus_assert (real->table != NULL);
685   _dbus_assert (real->entry != NULL);
686
687   return (uintptr_t) real->entry->key;
688 }
689
690 /**
691  * Gets the key for the current entry.
692  * Only works for hash tables of type #DBUS_HASH_STRING
693  * @param iter the hash table iterator.
694  */
695 const char*
696 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
697 {
698   DBusRealHashIter *real;
699
700   real = (DBusRealHashIter*) iter;
701
702   _dbus_assert (real->table != NULL);
703   _dbus_assert (real->entry != NULL);
704
705   return real->entry->key;
706 }
707
708 /**
709  * A low-level but efficient interface for manipulating the hash
710  * table.  It's efficient because you can get, set, and optionally
711  * create the hash entry while only running the hash function one
712  * time.
713  *
714  * Note that while calling _dbus_hash_iter_next() on the iterator
715  * filled in by this function may work, it's completely
716  * undefined which entries are after this iter and which
717  * are before it. So it would be silly to iterate using this
718  * iterator.
719  *
720  * If the hash entry is created, its value will be initialized
721  * to all bits zero.
722  *
723  * #FALSE may be returned due to memory allocation failure, or
724  * because create_if_not_found was #FALSE and the entry
725  * did not exist.
726  *
727  * If create_if_not_found is #TRUE and the entry is created, the hash
728  * table takes ownership of the key that's passed in.
729  *
730  * For a hash table of type #DBUS_HASH_INT, cast the int
731  * key to the key parameter using #_DBUS_INT_TO_POINTER().
732  * 
733  * @param table the hash table.
734  * @param key the hash key.
735  * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
736  * @param iter the iterator to initialize.
737  * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
738  */
739 dbus_bool_t
740 _dbus_hash_iter_lookup (DBusHashTable *table,
741                         void          *key,
742                         dbus_bool_t    create_if_not_found,
743                         DBusHashIter  *iter)
744 {
745   DBusRealHashIter *real;
746   DBusHashEntry *entry;
747   DBusHashEntry **bucket;
748   
749   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
750   
751   real = (DBusRealHashIter*) iter;
752
753   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
754
755   if (entry == NULL)
756     return FALSE;
757   
758   real->table = table;
759   real->bucket = bucket;
760   real->entry = entry;
761   real->next_entry = entry->next;
762   real->next_bucket = (bucket - table->buckets) + 1;
763   real->n_entries_on_init = table->n_entries; 
764
765   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
766   
767   return TRUE;
768 }
769
770 static void
771 add_allocated_entry (DBusHashTable   *table,
772                      DBusHashEntry   *entry,
773                      unsigned int     idx,
774                      void            *key,
775                      DBusHashEntry ***bucket)
776 {
777   DBusHashEntry **b;  
778   
779   entry->key = key;
780   
781   b = &(table->buckets[idx]);
782   entry->next = *b;
783   *b = entry;
784
785   if (bucket)
786     *bucket = b;
787   
788   table->n_entries += 1;
789
790   /* note we ONLY rebuild when ADDING - because you can iterate over a
791    * table and remove entries safely.
792    */
793   if (table->n_entries >= table->hi_rebuild_size ||
794       table->n_entries < table->lo_rebuild_size)
795     rebuild_table (table);
796 }
797
798 static DBusHashEntry*
799 add_entry (DBusHashTable        *table, 
800            unsigned int          idx,
801            void                 *key,
802            DBusHashEntry      ***bucket,
803            DBusPreallocatedHash *preallocated)
804 {
805   DBusHashEntry  *entry;
806
807   if (preallocated == NULL)
808     {
809       entry = alloc_entry (table);
810       if (entry == NULL)
811         {
812           if (bucket)
813             *bucket = NULL;
814           return NULL;
815         }
816     }
817   else
818     {
819       entry = (DBusHashEntry*) preallocated;
820     }
821
822   add_allocated_entry (table, entry, idx, key, bucket);
823
824   return entry;
825 }
826
827 /* This is g_str_hash from GLib which was
828  * extensively discussed/tested/profiled
829  */
830 static unsigned int
831 string_hash (const char *str)
832 {
833   const char *p = str;
834   unsigned int h = *p;
835
836   if (h)
837     for (p += 1; *p != '\0'; p++)
838       h = (h << 5) - h + *p;
839
840   return h;
841 }
842
843 /** Key comparison function */
844 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
845
846 static DBusHashEntry*
847 find_generic_function (DBusHashTable        *table,
848                        void                 *key,
849                        unsigned int          idx,
850                        KeyCompareFunc        compare_func,
851                        dbus_bool_t           create_if_not_found,
852                        DBusHashEntry      ***bucket,
853                        DBusPreallocatedHash *preallocated)
854 {
855   DBusHashEntry *entry;
856
857   if (bucket)
858     *bucket = NULL;
859
860   /* Search all of the entries in this bucket. */
861   entry = table->buckets[idx];
862   while (entry != NULL)
863     {
864       if ((compare_func == NULL && key == entry->key) ||
865           (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
866         {
867           if (bucket)
868             *bucket = &(table->buckets[idx]);
869
870           if (preallocated)
871             _dbus_hash_table_free_preallocated_entry (table, preallocated);
872           
873           return entry;
874         }
875       
876       entry = entry->next;
877     }
878
879   if (create_if_not_found)
880     entry = add_entry (table, idx, key, bucket, preallocated);
881   else if (preallocated)
882     _dbus_hash_table_free_preallocated_entry (table, preallocated);
883   
884   return entry;
885 }
886
887 static DBusHashEntry*
888 find_string_function (DBusHashTable        *table,
889                       void                 *key,
890                       dbus_bool_t           create_if_not_found,
891                       DBusHashEntry      ***bucket,
892                       DBusPreallocatedHash *preallocated)
893 {
894   unsigned int idx;
895   
896   idx = string_hash (key) & table->mask;
897
898   return find_generic_function (table, key, idx,
899                                 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
900                                 preallocated);
901 }
902
903 static DBusHashEntry*
904 find_direct_function (DBusHashTable        *table,
905                       void                 *key,
906                       dbus_bool_t           create_if_not_found,
907                       DBusHashEntry      ***bucket,
908                       DBusPreallocatedHash *preallocated)
909 {
910   unsigned int idx;
911   
912   idx = RANDOM_INDEX (table, key) & table->mask;
913
914
915   return find_generic_function (table, key, idx,
916                                 NULL, create_if_not_found, bucket,
917                                 preallocated);
918 }
919
920 static void
921 rebuild_table (DBusHashTable *table)
922 {
923   int old_size;
924   int new_buckets;
925   DBusHashEntry **old_buckets;
926   DBusHashEntry **old_chain;
927   DBusHashEntry *entry;
928   dbus_bool_t growing;
929   
930   /*
931    * Allocate and initialize the new bucket array, and set up
932    * hashing constants for new array size.
933    */
934
935   growing = table->n_entries >= table->hi_rebuild_size;
936   
937   old_size = table->n_buckets;
938   old_buckets = table->buckets;
939
940   if (growing)
941     {
942       /* overflow paranoia */
943       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
944           table->down_shift >= 0)
945         new_buckets = table->n_buckets * 4;
946       else
947         return; /* can't grow anymore */
948     }
949   else
950     {
951       new_buckets = table->n_buckets / 4;
952       if (new_buckets < DBUS_SMALL_HASH_TABLE)
953         return; /* don't bother shrinking this far */
954     }
955
956   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
957   if (table->buckets == NULL)
958     {
959       /* out of memory, yay - just don't reallocate, the table will
960        * still work, albeit more slowly.
961        */
962       table->buckets = old_buckets;
963       return;
964     }
965
966   table->n_buckets = new_buckets;
967   
968   if (growing)
969     {
970       table->lo_rebuild_size = table->hi_rebuild_size;
971       table->hi_rebuild_size *= 4;
972       
973       table->down_shift -= 2;               /* keep 2 more high bits */
974       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
975     }
976   else
977     {
978       table->hi_rebuild_size = table->lo_rebuild_size;
979       table->lo_rebuild_size /= 4;
980
981       table->down_shift += 2;         /* keep 2 fewer high bits */
982       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
983     }
984
985 #if 0
986   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
987           growing ? "GROW" : "SHRINK",
988           table->lo_rebuild_size,
989           table->hi_rebuild_size,
990           table->down_shift,
991           table->mask);
992 #endif
993   
994   _dbus_assert (table->lo_rebuild_size >= 0);
995   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
996   _dbus_assert (table->mask != 0);
997   /* the mask is essentially the max index */
998   _dbus_assert (table->mask < table->n_buckets);
999   
1000   /*
1001    * Rehash all of the existing entries into the new bucket array.
1002    */
1003
1004   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1005     {
1006       for (entry = *old_chain; entry != NULL; entry = *old_chain)
1007         {
1008           unsigned int idx;
1009           DBusHashEntry **bucket;
1010           
1011           *old_chain = entry->next;
1012           switch (table->key_type)
1013             {
1014             case DBUS_HASH_STRING:
1015               idx = string_hash (entry->key) & table->mask;
1016               break;
1017             case DBUS_HASH_INT:
1018             case DBUS_HASH_UINTPTR:
1019               idx = RANDOM_INDEX (table, entry->key);
1020               break;
1021             default:
1022               idx = 0;
1023               _dbus_assert_not_reached ("Unknown hash table type");
1024               break;
1025             }
1026           
1027           bucket = &(table->buckets[idx]);
1028           entry->next = *bucket;
1029           *bucket = entry;
1030         }
1031     }
1032   
1033   /* Free the old bucket array, if it was dynamically allocated. */
1034
1035   if (old_buckets != table->static_buckets)
1036     dbus_free (old_buckets);
1037 }
1038
1039 /**
1040  * Looks up the value for a given string in a hash table
1041  * of type #DBUS_HASH_STRING. Returns %NULL if the value
1042  * is not present. (A not-present entry is indistinguishable
1043  * from an entry with a value of %NULL.)
1044  * @param table the hash table.
1045  * @param key the string to look up.
1046  * @returns the value of the hash entry.
1047  */
1048 void*
1049 _dbus_hash_table_lookup_string (DBusHashTable *table,
1050                                 const char    *key)
1051 {
1052   DBusHashEntry *entry;
1053
1054   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1055   
1056   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1057
1058   if (entry)
1059     return entry->value;
1060   else
1061     return NULL;
1062 }
1063
1064 /**
1065  * Looks up the value for a given integer in a hash table
1066  * of type #DBUS_HASH_INT. Returns %NULL if the value
1067  * is not present. (A not-present entry is indistinguishable
1068  * from an entry with a value of %NULL.)
1069  * @param table the hash table.
1070  * @param key the integer to look up.
1071  * @returns the value of the hash entry.
1072  */
1073 void*
1074 _dbus_hash_table_lookup_int (DBusHashTable *table,
1075                              int            key)
1076 {
1077   DBusHashEntry *entry;
1078
1079   _dbus_assert (table->key_type == DBUS_HASH_INT);
1080   
1081   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1082
1083   if (entry)
1084     return entry->value;
1085   else
1086     return NULL;
1087 }
1088
1089 /**
1090  * Looks up the value for a given integer in a hash table
1091  * of type #DBUS_HASH_UINTPTR. Returns %NULL if the value
1092  * is not present. (A not-present entry is indistinguishable
1093  * from an entry with a value of %NULL.)
1094  * @param table the hash table.
1095  * @param key the integer to look up.
1096  * @returns the value of the hash entry.
1097  */
1098 void*
1099 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
1100                                  uintptr_t      key)
1101 {
1102   DBusHashEntry *entry;
1103
1104   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1105   
1106   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1107
1108   if (entry)
1109     return entry->value;
1110   else
1111     return NULL;
1112 }
1113
1114 /**
1115  * Removes the hash entry for the given key. If no hash entry
1116  * for the key exists, does nothing.
1117  *
1118  * @param table the hash table.
1119  * @param key the hash key.
1120  * @returns #TRUE if the entry existed
1121  */
1122 dbus_bool_t
1123 _dbus_hash_table_remove_string (DBusHashTable *table,
1124                                 const char    *key)
1125 {
1126   DBusHashEntry *entry;
1127   DBusHashEntry **bucket;
1128   
1129   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1130   
1131   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1132
1133   if (entry)
1134     {
1135       remove_entry (table, bucket, entry);
1136       return TRUE;
1137     }
1138   else
1139     return FALSE;
1140 }
1141
1142 /**
1143  * Removes the hash entry for the given key. If no hash entry
1144  * for the key exists, does nothing.
1145  *
1146  * @param table the hash table.
1147  * @param key the hash key.
1148  * @returns #TRUE if the entry existed
1149  */
1150 dbus_bool_t
1151 _dbus_hash_table_remove_int (DBusHashTable *table,
1152                              int            key)
1153 {
1154   DBusHashEntry *entry;
1155   DBusHashEntry **bucket;
1156   
1157   _dbus_assert (table->key_type == DBUS_HASH_INT);
1158   
1159   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1160   
1161   if (entry)
1162     {
1163       remove_entry (table, bucket, entry);
1164       return TRUE;
1165     }
1166   else
1167     return FALSE;
1168 }
1169
1170 /**
1171  * Removes the hash entry for the given key. If no hash entry
1172  * for the key exists, does nothing.
1173  *
1174  * @param table the hash table.
1175  * @param key the hash key.
1176  * @returns #TRUE if the entry existed
1177  */
1178 dbus_bool_t
1179 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
1180                                  uintptr_t      key)
1181 {
1182   DBusHashEntry *entry;
1183   DBusHashEntry **bucket;
1184   
1185   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1186   
1187   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1188   
1189   if (entry)
1190     {
1191       remove_entry (table, bucket, entry);
1192       return TRUE;
1193     }
1194   else
1195     return FALSE;
1196 }
1197
1198 /**
1199  * Creates a hash entry with the given key and value.
1200  * The key and value are not copied; they are stored
1201  * in the hash table by reference. If an entry with the
1202  * given key already exists, the previous key and value
1203  * are overwritten (and freed if the hash table has
1204  * a key_free_function and/or value_free_function).
1205  *
1206  * Returns #FALSE if memory for the new hash entry
1207  * can't be allocated.
1208  * 
1209  * @param table the hash table.
1210  * @param key the hash entry key.
1211  * @param value the hash entry value.
1212  */
1213 dbus_bool_t
1214 _dbus_hash_table_insert_string (DBusHashTable *table,
1215                                 char          *key,
1216                                 void          *value)
1217 {
1218   DBusPreallocatedHash *preallocated;
1219
1220   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1221
1222   preallocated = _dbus_hash_table_preallocate_entry (table);
1223   if (preallocated == NULL)
1224     return FALSE;
1225
1226   _dbus_hash_table_insert_string_preallocated (table, preallocated,
1227                                                key, value);
1228   
1229   return TRUE;
1230 }
1231
1232 /**
1233  * Creates a hash entry with the given key and value.
1234  * The key and value are not copied; they are stored
1235  * in the hash table by reference. If an entry with the
1236  * given key already exists, the previous key and value
1237  * are overwritten (and freed if the hash table has
1238  * a key_free_function and/or value_free_function).
1239  *
1240  * Returns #FALSE if memory for the new hash entry
1241  * can't be allocated.
1242  * 
1243  * @param table the hash table.
1244  * @param key the hash entry key.
1245  * @param value the hash entry value.
1246  */
1247 dbus_bool_t
1248 _dbus_hash_table_insert_int (DBusHashTable *table,
1249                              int            key,
1250                              void          *value)
1251 {
1252   DBusHashEntry *entry;
1253
1254   _dbus_assert (table->key_type == DBUS_HASH_INT);
1255   
1256   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1257
1258   if (entry == NULL)
1259     return FALSE; /* no memory */
1260
1261   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1262     (* table->free_key_function) (entry->key);
1263   
1264   if (table->free_value_function && entry->value != value)
1265     (* table->free_value_function) (entry->value);
1266   
1267   entry->key = _DBUS_INT_TO_POINTER (key);
1268   entry->value = value;
1269
1270   return TRUE;
1271 }
1272
1273 /**
1274  * Creates a hash entry with the given key and value.
1275  * The key and value are not copied; they are stored
1276  * in the hash table by reference. If an entry with the
1277  * given key already exists, the previous key and value
1278  * are overwritten (and freed if the hash table has
1279  * a key_free_function and/or value_free_function).
1280  *
1281  * Returns #FALSE if memory for the new hash entry
1282  * can't be allocated.
1283  * 
1284  * @param table the hash table.
1285  * @param key the hash entry key.
1286  * @param value the hash entry value.
1287  */
1288 dbus_bool_t
1289 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
1290                                  uintptr_t      key,
1291                                  void          *value)
1292 {
1293   DBusHashEntry *entry;
1294
1295   _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1296   
1297   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1298
1299   if (entry == NULL)
1300     return FALSE; /* no memory */
1301
1302   if (table->free_key_function && entry->key != (void*) key)
1303     (* table->free_key_function) (entry->key);
1304   
1305   if (table->free_value_function && entry->value != value)
1306     (* table->free_value_function) (entry->value);
1307   
1308   entry->key = (void*) key;
1309   entry->value = value;
1310
1311   return TRUE;
1312 }
1313
1314 /**
1315  * Preallocate an opaque data blob that allows us to insert into the
1316  * hash table at a later time without allocating any memory.
1317  *
1318  * @param table the hash table
1319  * @returns the preallocated data, or #NULL if no memory
1320  */
1321 DBusPreallocatedHash*
1322 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
1323 {
1324   DBusHashEntry *entry;
1325   
1326   entry = alloc_entry (table);
1327
1328   return (DBusPreallocatedHash*) entry;
1329 }
1330
1331 /**
1332  * Frees an opaque DBusPreallocatedHash that was *not* used
1333  * in order to insert into the hash table.
1334  *
1335  * @param table the hash table
1336  * @param preallocated the preallocated data
1337  */
1338 void
1339 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
1340                                           DBusPreallocatedHash *preallocated)
1341 {
1342   DBusHashEntry *entry;
1343
1344   _dbus_assert (preallocated != NULL);
1345   
1346   entry = (DBusHashEntry*) preallocated;
1347   
1348   /* Don't use free_entry(), since this entry has no key/data */
1349   _dbus_mem_pool_dealloc (table->entry_pool, entry);
1350 }
1351
1352 /**
1353  * Inserts a string-keyed entry into the hash table, using a
1354  * preallocated data block from
1355  * _dbus_hash_table_preallocate_entry(). This function cannot fail due
1356  * to lack of memory. The DBusPreallocatedHash object is consumed and
1357  * should not be reused or freed. Otherwise this function works
1358  * just like _dbus_hash_table_insert_string().
1359  *
1360  * @param table the hash table
1361  * @param preallocated the preallocated data
1362  * @param key the hash key
1363  * @param value the value 
1364  */
1365 void
1366 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
1367                                              DBusPreallocatedHash *preallocated,
1368                                              char                 *key,
1369                                              void                 *value)
1370 {
1371   DBusHashEntry *entry;
1372
1373   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1374   _dbus_assert (preallocated != NULL);
1375   
1376   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1377
1378   _dbus_assert (entry != NULL);
1379   
1380   if (table->free_key_function && entry->key != key)
1381     (* table->free_key_function) (entry->key);
1382
1383   if (table->free_value_function && entry->value != value)
1384     (* table->free_value_function) (entry->value);
1385       
1386   entry->key = key;
1387   entry->value = value;
1388 }
1389
1390 /**
1391  * Gets the number of hash entries in a hash table.
1392  *
1393  * @param table the hash table.
1394  * @returns the number of entries in the table.
1395  */
1396 int
1397 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1398 {
1399   return table->n_entries;
1400 }
1401
1402 /** @} */
1403
1404 #ifdef DBUS_BUILD_TESTS
1405 #include "dbus-test.h"
1406 #include <stdio.h>
1407
1408 /* If you're wondering why the hash table test takes
1409  * forever to run, it's because we call this function
1410  * in inner loops thus making things quadratic.
1411  */
1412 static int
1413 count_entries (DBusHashTable *table)
1414 {
1415   DBusHashIter iter;
1416   int count;
1417
1418   count = 0;
1419   _dbus_hash_iter_init (table, &iter);
1420   while (_dbus_hash_iter_next (&iter))
1421     ++count;
1422
1423   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1424   
1425   return count;
1426 }
1427
1428 /**
1429  * @ingroup DBusHashTableInternals
1430  * Unit test for DBusHashTable
1431  * @returns #TRUE on success.
1432  */
1433 dbus_bool_t
1434 _dbus_hash_test (void)
1435 {
1436   int i;
1437   DBusHashTable *table1;
1438   DBusHashTable *table2;
1439   DBusHashTable *table3;
1440   DBusHashIter iter;
1441 #define N_HASH_KEYS 5000
1442   char **keys;
1443   dbus_bool_t ret = FALSE;
1444
1445   keys = dbus_new (char *, N_HASH_KEYS);
1446   if (keys == NULL)
1447     _dbus_assert_not_reached ("no memory");
1448
1449   for (i = 0; i < N_HASH_KEYS; i++)
1450     {
1451       keys[i] = dbus_malloc (128);
1452
1453       if (keys[i] == NULL)
1454         _dbus_assert_not_reached ("no memory");
1455     }
1456
1457   printf ("Computing test hash keys...\n");
1458   i = 0;
1459   while (i < N_HASH_KEYS)
1460     {
1461       int len;
1462
1463       len = sprintf (keys[i], "Hash key %d", i);
1464       _dbus_assert (*(keys[i] + len) == '\0');
1465       ++i;
1466     }
1467   printf ("... done.\n");
1468   
1469   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1470                                  dbus_free, dbus_free);
1471   if (table1 == NULL)
1472     goto out;
1473
1474   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1475                                  NULL, dbus_free);
1476   if (table2 == NULL)
1477     goto out;
1478
1479   table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
1480                                  NULL, dbus_free);
1481   if (table3 == NULL)
1482     goto out;
1483
1484   /* Insert and remove a bunch of stuff, counting the table in between
1485    * to be sure it's not broken and that iteration works
1486    */
1487   i = 0;
1488   while (i < 3000)
1489     {
1490       void *value;
1491       char *key;
1492
1493       key = _dbus_strdup (keys[i]);
1494       if (key == NULL)
1495         goto out;
1496       value = _dbus_strdup ("Value!");
1497       if (value == NULL)
1498         goto out;
1499       
1500       if (!_dbus_hash_table_insert_string (table1,
1501                                            key, value))
1502         goto out;
1503
1504       value = _dbus_strdup (keys[i]);
1505       if (value == NULL)
1506         goto out;
1507       
1508       if (!_dbus_hash_table_insert_int (table2,
1509                                         i, value))
1510         goto out;
1511
1512       value = _dbus_strdup (keys[i]);
1513       if (value == NULL)
1514         goto out;
1515       
1516       if (!_dbus_hash_table_insert_uintptr (table3,
1517                                           i, value))
1518         goto out;
1519
1520       _dbus_assert (count_entries (table1) == i + 1);
1521       _dbus_assert (count_entries (table2) == i + 1);
1522       _dbus_assert (count_entries (table3) == i + 1);
1523
1524       value = _dbus_hash_table_lookup_string (table1, keys[i]);
1525       _dbus_assert (value != NULL);
1526       _dbus_assert (strcmp (value, "Value!") == 0);
1527
1528       value = _dbus_hash_table_lookup_int (table2, i);
1529       _dbus_assert (value != NULL);
1530       _dbus_assert (strcmp (value, keys[i]) == 0);
1531
1532       value = _dbus_hash_table_lookup_uintptr (table3, i);
1533       _dbus_assert (value != NULL);
1534       _dbus_assert (strcmp (value, keys[i]) == 0);
1535
1536       ++i;
1537     }
1538
1539   --i;
1540   while (i >= 0)
1541     {
1542       _dbus_hash_table_remove_string (table1,
1543                                       keys[i]);
1544
1545       _dbus_hash_table_remove_int (table2, i);
1546
1547       _dbus_hash_table_remove_uintptr (table3, i);
1548
1549       _dbus_assert (count_entries (table1) == i);
1550       _dbus_assert (count_entries (table2) == i);
1551       _dbus_assert (count_entries (table3) == i);
1552
1553       --i;
1554     }
1555
1556   _dbus_hash_table_ref (table1);
1557   _dbus_hash_table_ref (table2);
1558   _dbus_hash_table_ref (table3);
1559   _dbus_hash_table_unref (table1);
1560   _dbus_hash_table_unref (table2);
1561   _dbus_hash_table_unref (table3);
1562   _dbus_hash_table_unref (table1);
1563   _dbus_hash_table_unref (table2);
1564   _dbus_hash_table_unref (table3);
1565   table3 = NULL;
1566
1567   /* Insert a bunch of stuff then check
1568    * that iteration works correctly (finds the right
1569    * values, iter_set_value works, etc.)
1570    */
1571   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1572                                  dbus_free, dbus_free);
1573   if (table1 == NULL)
1574     goto out;
1575   
1576   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1577                                  NULL, dbus_free);
1578   if (table2 == NULL)
1579     goto out;
1580   
1581   i = 0;
1582   while (i < 5000)
1583     {
1584       char *key;
1585       void *value;      
1586       
1587       key = _dbus_strdup (keys[i]);
1588       if (key == NULL)
1589         goto out;
1590       value = _dbus_strdup ("Value!");
1591       if (value == NULL)
1592         goto out;
1593       
1594       if (!_dbus_hash_table_insert_string (table1,
1595                                            key, value))
1596         goto out;
1597
1598       value = _dbus_strdup (keys[i]);
1599       if (value == NULL)
1600         goto out;
1601       
1602       if (!_dbus_hash_table_insert_int (table2,
1603                                         i, value))
1604         goto out;
1605       
1606       _dbus_assert (count_entries (table1) == i + 1);
1607       _dbus_assert (count_entries (table2) == i + 1);
1608       
1609       ++i;
1610     }
1611
1612   _dbus_hash_iter_init (table1, &iter);
1613   while (_dbus_hash_iter_next (&iter))
1614     {
1615       const char *key;
1616       void *value;
1617
1618       key = _dbus_hash_iter_get_string_key (&iter);
1619       value = _dbus_hash_iter_get_value (&iter);
1620
1621       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1622
1623       value = _dbus_strdup ("Different value!");
1624       if (value == NULL)
1625         goto out;
1626       
1627       _dbus_hash_iter_set_value (&iter, value);
1628
1629       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1630     }
1631   
1632   _dbus_hash_iter_init (table1, &iter);
1633   while (_dbus_hash_iter_next (&iter))
1634     {
1635       _dbus_hash_iter_remove_entry (&iter);
1636       _dbus_assert (count_entries (table1) == i - 1);
1637       --i;
1638     }
1639
1640   _dbus_hash_iter_init (table2, &iter);
1641   while (_dbus_hash_iter_next (&iter))
1642     {
1643       int key;
1644       void *value;
1645
1646       key = _dbus_hash_iter_get_int_key (&iter);
1647       value = _dbus_hash_iter_get_value (&iter);
1648
1649       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1650
1651       value = _dbus_strdup ("Different value!");
1652       if (value == NULL)
1653         goto out;
1654       
1655       _dbus_hash_iter_set_value (&iter, value);
1656
1657       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1658     }
1659
1660   i = count_entries (table2);
1661   _dbus_hash_iter_init (table2, &iter);
1662   while (_dbus_hash_iter_next (&iter))
1663     {
1664       _dbus_hash_iter_remove_entry (&iter);
1665       _dbus_assert (count_entries (table2) + 1 == i);
1666       --i;
1667     }
1668
1669   /* add/remove interleaved, to check that we grow/shrink the table
1670    * appropriately
1671    */
1672   i = 0;
1673   while (i < 1000)
1674     {
1675       char *key;
1676       void *value;
1677             
1678       key = _dbus_strdup (keys[i]);
1679       if (key == NULL)
1680         goto out;
1681
1682       value = _dbus_strdup ("Value!");
1683       if (value == NULL)
1684         goto out;
1685       
1686       if (!_dbus_hash_table_insert_string (table1,
1687                                            key, value))
1688         goto out;
1689       
1690       ++i;
1691     }
1692
1693   --i;
1694   while (i >= 0)
1695     {
1696       char *key;
1697       void *value;      
1698       
1699       key = _dbus_strdup (keys[i]);
1700       if (key == NULL)
1701         goto out;
1702       value = _dbus_strdup ("Value!");
1703       if (value == NULL)
1704         goto out;
1705
1706       if (!_dbus_hash_table_remove_string (table1, keys[i]))
1707         goto out;
1708       
1709       if (!_dbus_hash_table_insert_string (table1,
1710                                            key, value))
1711         goto out;
1712
1713       if (!_dbus_hash_table_remove_string (table1, keys[i]))
1714         goto out;
1715       
1716       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
1717       
1718       --i;
1719     }
1720
1721   /* nuke these tables */
1722   _dbus_hash_table_unref (table1);
1723   _dbus_hash_table_unref (table2);
1724
1725
1726   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1727    * be sure that interface works.
1728    */
1729   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1730                                  dbus_free, dbus_free);
1731   if (table1 == NULL)
1732     goto out;
1733   
1734   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1735                                  NULL, dbus_free);
1736   if (table2 == NULL)
1737     goto out;
1738   
1739   i = 0;
1740   while (i < 3000)
1741     {
1742       void *value;
1743       char *key;
1744
1745       key = _dbus_strdup (keys[i]);
1746       if (key == NULL)
1747         goto out;
1748       value = _dbus_strdup ("Value!");
1749       if (value == NULL)
1750         goto out;
1751       
1752       if (!_dbus_hash_iter_lookup (table1,
1753                                    key, TRUE, &iter))
1754         goto out;
1755       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1756       _dbus_hash_iter_set_value (&iter, value);
1757
1758       value = _dbus_strdup (keys[i]);
1759       if (value == NULL)
1760         goto out;
1761
1762       if (!_dbus_hash_iter_lookup (table2,
1763                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1764         goto out;
1765       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1766       _dbus_hash_iter_set_value (&iter, value); 
1767       
1768       _dbus_assert (count_entries (table1) == i + 1);
1769       _dbus_assert (count_entries (table2) == i + 1);
1770
1771       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1772         goto out;
1773       
1774       value = _dbus_hash_iter_get_value (&iter);
1775       _dbus_assert (value != NULL);
1776       _dbus_assert (strcmp (value, "Value!") == 0);
1777
1778       /* Iterate just to be sure it works, though
1779        * it's a stupid thing to do
1780        */
1781       while (_dbus_hash_iter_next (&iter))
1782         ;
1783       
1784       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1785         goto out;
1786
1787       value = _dbus_hash_iter_get_value (&iter);
1788       _dbus_assert (value != NULL);
1789       _dbus_assert (strcmp (value, keys[i]) == 0);
1790
1791       /* Iterate just to be sure it works, though
1792        * it's a stupid thing to do
1793        */
1794       while (_dbus_hash_iter_next (&iter))
1795         ;
1796       
1797       ++i;
1798     }
1799
1800   --i;
1801   while (i >= 0)
1802     {
1803       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1804         _dbus_assert_not_reached ("hash entry should have existed");
1805       _dbus_hash_iter_remove_entry (&iter);
1806       
1807       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1808         _dbus_assert_not_reached ("hash entry should have existed");
1809       _dbus_hash_iter_remove_entry (&iter);
1810
1811       _dbus_assert (count_entries (table1) == i);
1812       _dbus_assert (count_entries (table2) == i);
1813
1814       --i;
1815     }
1816
1817   _dbus_hash_table_unref (table1);
1818   _dbus_hash_table_unref (table2);
1819
1820   ret = TRUE;
1821
1822  out:
1823   for (i = 0; i < N_HASH_KEYS; i++)
1824     dbus_free (keys[i]);
1825
1826   dbus_free (keys);
1827   
1828   return ret;
1829 }
1830
1831 #endif /* DBUS_BUILD_TESTS */