1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
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.
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.
13 * Licensed under the Academic Free License version 2.1
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.
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.
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
31 * The following copyright applies to code from the Tcl distribution.
33 * Copyright (c) 1991-1993 The Regents of the University of California.
34 * Copyright (c) 1994 Sun Microsystems, Inc.
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.
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.
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.
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.
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.
78 #include "dbus-hash.h"
79 #include "dbus-internals.h"
80 #include "dbus-mempool.h"
83 * @defgroup DBusHashTable Hash table
84 * @ingroup DBusInternals
85 * @brief DBusHashTable data structure
87 * Types and functions related to DBusHashTable.
91 * @defgroup DBusHashTableInternals Hash table implementation details
92 * @ingroup DBusInternals
93 * @brief DBusHashTable implementation details
95 * The guts of DBusHashTable.
101 * When there are this many entries per bucket, on average, rebuild
102 * the hash table to make it larger.
104 #define REBUILD_MULTIPLIER 3
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.)
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?
122 #define RANDOM_INDEX(table, i) \
123 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
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.
130 #define DBUS_SMALL_HASH_TABLE 4
133 * Typedef for DBusHashEntry
135 typedef struct DBusHashEntry DBusHashEntry;
138 * @brief Internal representation of a hash entry.
140 * A single entry (key-value pair) in the hash table.
141 * Internal to hash table implementation.
145 DBusHashEntry *next; /**< Pointer to next entry in this
146 * hash bucket, or #NULL for end of
149 void *key; /**< Hash key */
150 void *value; /**< Hash value */
154 * Function used to find and optionally create a hash entry.
156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
158 dbus_bool_t create_if_not_found,
159 DBusHashEntry ***bucket,
160 DBusPreallocatedHash *preallocated);
163 * @brief Internals of DBusHashTable.
165 * Hash table internals. Hash tables are opaque objects, they must be
166 * used via accessor functions.
168 struct DBusHashTable {
169 int refcount; /**< Reference count */
171 DBusHashEntry **buckets; /**< Pointer to bucket array. Each
172 * element points to first entry in
173 * bucket's hash chain, or #NULL.
175 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
176 /**< Bucket array used for small tables
177 * (to avoid mallocs and frees).
179 int n_buckets; /**< Total number of buckets allocated
182 int n_entries; /**< Total number of entries present
185 int hi_rebuild_size; /**< Enlarge table when n_entries gets
188 int lo_rebuild_size; /**< Shrink table when n_entries gets
191 int down_shift; /**< Shift count used in hashing
192 * function. Designed to use high-
193 * order bits of randomized keys.
195 int mask; /**< Mask value used in hashing
198 DBusHashType key_type; /**< Type of keys used in this table */
201 DBusFindEntryFunction find_function; /**< Function for finding entries */
203 DBusFreeFunction free_key_function; /**< Function to free keys */
204 DBusFreeFunction free_value_function; /**< Function to free values */
206 DBusMemPool *entry_pool; /**< Memory pool for hash entries */
210 * @brief Internals of DBusHashIter.
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.
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 */
225 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
227 static DBusHashEntry* find_direct_function (DBusHashTable *table,
229 dbus_bool_t create_if_not_found,
230 DBusHashEntry ***bucket,
231 DBusPreallocatedHash *preallocated);
232 static DBusHashEntry* find_string_function (DBusHashTable *table,
234 dbus_bool_t create_if_not_found,
235 DBusHashEntry ***bucket,
236 DBusPreallocatedHash *preallocated);
237 #ifdef DBUS_BUILD_TESTS
238 static DBusHashEntry* find_two_strings_function (DBusHashTable *table,
240 dbus_bool_t create_if_not_found,
241 DBusHashEntry ***bucket,
242 DBusPreallocatedHash *preallocated);
244 static unsigned int string_hash (const char *str);
245 #ifdef DBUS_BUILD_TESTS
246 static unsigned int two_strings_hash (const char *str);
248 static void rebuild_table (DBusHashTable *table);
249 static DBusHashEntry* alloc_entry (DBusHashTable *table);
250 static void remove_entry (DBusHashTable *table,
251 DBusHashEntry **bucket,
252 DBusHashEntry *entry);
253 static void free_entry (DBusHashTable *table,
254 DBusHashEntry *entry);
255 static void free_entry_data (DBusHashTable *table,
256 DBusHashEntry *entry);
262 * @addtogroup DBusHashTable
267 * @typedef DBusHashIter
269 * Public opaque hash table iterator object.
273 * @typedef DBusHashTable
275 * Public opaque hash table object.
279 * @typedef DBusHashType
281 * Indicates the type of a key in the hash table.
285 * Constructs a new hash table. Should be freed with
286 * _dbus_hash_table_unref(). If memory cannot be
287 * allocated for the hash table, returns #NULL.
289 * @param type the type of hash key to use.
290 * @param key_free_function function to free hash keys.
291 * @param value_free_function function to free hash values.
292 * @returns a new DBusHashTable or #NULL if no memory.
295 _dbus_hash_table_new (DBusHashType type,
296 DBusFreeFunction key_free_function,
297 DBusFreeFunction value_free_function)
299 DBusHashTable *table;
300 DBusMemPool *entry_pool;
302 table = dbus_new0 (DBusHashTable, 1);
306 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
307 if (entry_pool == NULL)
314 table->entry_pool = entry_pool;
316 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
318 table->buckets = table->static_buckets;
319 table->n_buckets = DBUS_SMALL_HASH_TABLE;
320 table->n_entries = 0;
321 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
322 table->lo_rebuild_size = 0;
323 table->down_shift = 28;
325 table->key_type = type;
327 _dbus_assert (table->mask < table->n_buckets);
329 switch (table->key_type)
332 case DBUS_HASH_POINTER:
333 case DBUS_HASH_UINTPTR:
334 table->find_function = find_direct_function;
336 case DBUS_HASH_STRING:
337 table->find_function = find_string_function;
339 case DBUS_HASH_TWO_STRINGS:
340 #ifdef DBUS_BUILD_TESTS
341 table->find_function = find_two_strings_function;
345 _dbus_assert_not_reached ("Unknown hash table type");
349 table->free_key_function = key_free_function;
350 table->free_value_function = value_free_function;
357 * Increments the reference count for a hash table.
359 * @param table the hash table to add a reference to.
360 * @returns the hash table.
363 _dbus_hash_table_ref (DBusHashTable *table)
365 table->refcount += 1;
371 * Decrements the reference count for a hash table,
372 * freeing the hash table if the count reaches zero.
374 * @param table the hash table to remove a reference from.
377 _dbus_hash_table_unref (DBusHashTable *table)
379 table->refcount -= 1;
381 if (table->refcount == 0)
384 DBusHashEntry *entry;
388 /* Free the entries in the table. */
389 for (i = 0; i < table->n_buckets; i++)
391 entry = table->buckets[i];
392 while (entry != NULL)
396 free_entry (table, entry);
402 DBusHashEntry *entry;
405 /* Free the entries in the table. */
406 for (i = 0; i < table->n_buckets; i++)
408 entry = table->buckets[i];
409 while (entry != NULL)
411 free_entry_data (table, entry);
416 /* We can do this very quickly with memory pools ;-) */
417 _dbus_mem_pool_free (table->entry_pool);
420 /* Free the bucket array, if it was dynamically allocated. */
421 if (table->buckets != table->static_buckets)
422 dbus_free (table->buckets);
429 * Removed all entries from a hash table.
431 * @param table the hash table to remove all entries from.
434 _dbus_hash_table_remove_all (DBusHashTable *table)
437 _dbus_hash_iter_init (table, &iter);
438 while (_dbus_hash_iter_next (&iter))
440 _dbus_hash_iter_remove_entry(&iter);
444 static DBusHashEntry*
445 alloc_entry (DBusHashTable *table)
447 DBusHashEntry *entry;
449 entry = _dbus_mem_pool_alloc (table->entry_pool);
455 free_entry_data (DBusHashTable *table,
456 DBusHashEntry *entry)
458 if (table->free_key_function)
459 (* table->free_key_function) (entry->key);
460 if (table->free_value_function)
461 (* table->free_value_function) (entry->value);
465 free_entry (DBusHashTable *table,
466 DBusHashEntry *entry)
468 free_entry_data (table, entry);
469 _dbus_mem_pool_dealloc (table->entry_pool, entry);
473 remove_entry (DBusHashTable *table,
474 DBusHashEntry **bucket,
475 DBusHashEntry *entry)
477 _dbus_assert (table != NULL);
478 _dbus_assert (bucket != NULL);
479 _dbus_assert (*bucket != NULL);
480 _dbus_assert (entry != NULL);
482 if (*bucket == entry)
483 *bucket = entry->next;
489 while (prev->next != entry)
492 _dbus_assert (prev != NULL);
494 prev->next = entry->next;
497 table->n_entries -= 1;
498 free_entry (table, entry);
502 * Initializes a hash table iterator. To iterate over all entries in a
503 * hash table, use the following code (the printf assumes a hash
504 * from strings to strings obviously):
509 * _dbus_hash_iter_init (table, &iter);
510 * while (_dbus_hash_iter_next (&iter))
512 * printf ("The first key is %s and value is %s\n",
513 * _dbus_hash_iter_get_string_key (&iter),
514 * _dbus_hash_iter_get_value (&iter));
520 * The iterator is initialized pointing "one before" the first hash
521 * entry. The first call to _dbus_hash_iter_next() moves it onto
522 * the first valid entry or returns #FALSE if the hash table is
523 * empty. Subsequent calls move to the next valid entry or return
524 * #FALSE if there are no more entries.
526 * Note that it is guaranteed to be safe to remove a hash entry during
527 * iteration, but it is not safe to add a hash entry.
529 * @param table the hash table to iterate over.
530 * @param iter the iterator to initialize.
533 _dbus_hash_iter_init (DBusHashTable *table,
536 DBusRealHashIter *real;
538 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
540 real = (DBusRealHashIter*) iter;
545 real->next_entry = NULL;
546 real->next_bucket = 0;
547 real->n_entries_on_init = table->n_entries;
551 * Move the hash iterator forward one step, to the next hash entry.
552 * The documentation for _dbus_hash_iter_init() explains in more
555 * @param iter the iterator to move forward.
556 * @returns #FALSE if there are no more entries to move to.
559 _dbus_hash_iter_next (DBusHashIter *iter)
561 DBusRealHashIter *real;
563 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
565 real = (DBusRealHashIter*) iter;
567 /* if this assertion failed someone probably added hash entries
568 * during iteration, which is bad.
570 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
572 /* Remember that real->entry may have been deleted */
574 while (real->next_entry == NULL)
576 if (real->next_bucket >= real->table->n_buckets)
578 /* invalidate iter and return false */
585 real->bucket = &(real->table->buckets[real->next_bucket]);
586 real->next_entry = *(real->bucket);
587 real->next_bucket += 1;
590 _dbus_assert (real->next_entry != NULL);
591 _dbus_assert (real->bucket != NULL);
593 real->entry = real->next_entry;
594 real->next_entry = real->entry->next;
600 * Removes the current entry from the hash table.
601 * If a key_free_function or value_free_function
602 * was provided to _dbus_hash_table_new(),
603 * frees the key and/or value for this entry.
605 * @param iter the hash table iterator.
608 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
610 DBusRealHashIter *real;
612 real = (DBusRealHashIter*) iter;
614 _dbus_assert (real->table != NULL);
615 _dbus_assert (real->entry != NULL);
616 _dbus_assert (real->bucket != NULL);
618 remove_entry (real->table, real->bucket, real->entry);
620 real->entry = NULL; /* make it crash if you try to use this entry */
624 * Gets the value of the current entry.
626 * @param iter the hash table iterator.
629 _dbus_hash_iter_get_value (DBusHashIter *iter)
631 DBusRealHashIter *real;
633 real = (DBusRealHashIter*) iter;
635 _dbus_assert (real->table != NULL);
636 _dbus_assert (real->entry != NULL);
638 return real->entry->value;
642 * Sets the value of the current entry.
643 * If the hash table has a value_free_function
644 * it will be used to free the previous value.
645 * The hash table will own the passed-in value
646 * (it will not be copied).
648 * @param iter the hash table iterator.
649 * @param value the new value.
652 _dbus_hash_iter_set_value (DBusHashIter *iter,
655 DBusRealHashIter *real;
657 real = (DBusRealHashIter*) iter;
659 _dbus_assert (real->table != NULL);
660 _dbus_assert (real->entry != NULL);
662 if (real->table->free_value_function && value != real->entry->value)
663 (* real->table->free_value_function) (real->entry->value);
665 real->entry->value = value;
669 * Gets the key for the current entry.
670 * Only works for hash tables of type #DBUS_HASH_INT.
672 * @param iter the hash table iterator.
675 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
677 DBusRealHashIter *real;
679 real = (DBusRealHashIter*) iter;
681 _dbus_assert (real->table != NULL);
682 _dbus_assert (real->entry != NULL);
684 return _DBUS_POINTER_TO_INT (real->entry->key);
688 * Gets the key for the current entry.
689 * Only works for hash tables of type #DBUS_HASH_UINTPTR.
691 * @param iter the hash table iterator.
694 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
696 DBusRealHashIter *real;
698 real = (DBusRealHashIter*) iter;
700 _dbus_assert (real->table != NULL);
701 _dbus_assert (real->entry != NULL);
703 return (uintptr_t) real->entry->key;
707 * Gets the key for the current entry.
708 * Only works for hash tables of type #DBUS_HASH_STRING
709 * @param iter the hash table iterator.
712 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
714 DBusRealHashIter *real;
716 real = (DBusRealHashIter*) iter;
718 _dbus_assert (real->table != NULL);
719 _dbus_assert (real->entry != NULL);
721 return real->entry->key;
724 #ifdef DBUS_BUILD_TESTS
726 * Gets the key for the current entry.
727 * Only works for hash tables of type #DBUS_HASH_TWO_STRINGS
728 * @param iter the hash table iterator.
731 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
733 DBusRealHashIter *real;
735 real = (DBusRealHashIter*) iter;
737 _dbus_assert (real->table != NULL);
738 _dbus_assert (real->entry != NULL);
740 return real->entry->key;
742 #endif /* DBUS_BUILD_TESTS */
745 * A low-level but efficient interface for manipulating the hash
746 * table. It's efficient because you can get, set, and optionally
747 * create the hash entry while only running the hash function one
750 * Note that while calling _dbus_hash_iter_next() on the iterator
751 * filled in by this function may work, it's completely
752 * undefined which entries are after this iter and which
753 * are before it. So it would be silly to iterate using this
756 * If the hash entry is created, its value will be initialized
759 * #FALSE may be returned due to memory allocation failure, or
760 * because create_if_not_found was #FALSE and the entry
763 * If create_if_not_found is #TRUE and the entry is created, the hash
764 * table takes ownership of the key that's passed in.
766 * For a hash table of type #DBUS_HASH_INT, cast the int
767 * key to the key parameter using #_DBUS_INT_TO_POINTER().
769 * @param table the hash table.
770 * @param key the hash key.
771 * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
772 * @param iter the iterator to initialize.
773 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
776 _dbus_hash_iter_lookup (DBusHashTable *table,
778 dbus_bool_t create_if_not_found,
781 DBusRealHashIter *real;
782 DBusHashEntry *entry;
783 DBusHashEntry **bucket;
785 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
787 real = (DBusRealHashIter*) iter;
789 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
795 real->bucket = bucket;
797 real->next_entry = entry->next;
798 real->next_bucket = (bucket - table->buckets) + 1;
799 real->n_entries_on_init = table->n_entries;
801 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
807 add_allocated_entry (DBusHashTable *table,
808 DBusHashEntry *entry,
811 DBusHashEntry ***bucket)
817 b = &(table->buckets[idx]);
824 table->n_entries += 1;
826 /* note we ONLY rebuild when ADDING - because you can iterate over a
827 * table and remove entries safely.
829 if (table->n_entries >= table->hi_rebuild_size ||
830 table->n_entries < table->lo_rebuild_size)
831 rebuild_table (table);
834 static DBusHashEntry*
835 add_entry (DBusHashTable *table,
838 DBusHashEntry ***bucket,
839 DBusPreallocatedHash *preallocated)
841 DBusHashEntry *entry;
843 if (preallocated == NULL)
845 entry = alloc_entry (table);
855 entry = (DBusHashEntry*) preallocated;
858 add_allocated_entry (table, entry, idx, key, bucket);
863 /* This is g_str_hash from GLib which was
864 * extensively discussed/tested/profiled
867 string_hash (const char *str)
873 for (p += 1; *p != '\0'; p++)
874 h = (h << 5) - h + *p;
879 #ifdef DBUS_BUILD_TESTS
880 /* This hashes a memory block with two nul-terminated strings
881 * in it, used in dbus-object-registry.c at the moment.
884 two_strings_hash (const char *str)
890 for (p += 1; *p != '\0'; p++)
891 h = (h << 5) - h + *p;
893 for (p += 1; *p != '\0'; p++)
894 h = (h << 5) - h + *p;
898 #endif /* DBUS_BUILD_TESTS */
900 /** Key comparison function */
901 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
903 static DBusHashEntry*
904 find_generic_function (DBusHashTable *table,
907 KeyCompareFunc compare_func,
908 dbus_bool_t create_if_not_found,
909 DBusHashEntry ***bucket,
910 DBusPreallocatedHash *preallocated)
912 DBusHashEntry *entry;
917 /* Search all of the entries in this bucket. */
918 entry = table->buckets[idx];
919 while (entry != NULL)
921 if ((compare_func == NULL && key == entry->key) ||
922 (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
925 *bucket = &(table->buckets[idx]);
928 _dbus_hash_table_free_preallocated_entry (table, preallocated);
936 if (create_if_not_found)
937 entry = add_entry (table, idx, key, bucket, preallocated);
938 else if (preallocated)
939 _dbus_hash_table_free_preallocated_entry (table, preallocated);
944 static DBusHashEntry*
945 find_string_function (DBusHashTable *table,
947 dbus_bool_t create_if_not_found,
948 DBusHashEntry ***bucket,
949 DBusPreallocatedHash *preallocated)
953 idx = string_hash (key) & table->mask;
955 return find_generic_function (table, key, idx,
956 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
960 #ifdef DBUS_BUILD_TESTS
962 two_strings_cmp (const char *a,
976 return strcmp (a + len_a + 1, b + len_b + 1);
980 #ifdef DBUS_BUILD_TESTS
981 static DBusHashEntry*
982 find_two_strings_function (DBusHashTable *table,
984 dbus_bool_t create_if_not_found,
985 DBusHashEntry ***bucket,
986 DBusPreallocatedHash *preallocated)
990 idx = two_strings_hash (key) & table->mask;
992 return find_generic_function (table, key, idx,
993 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
996 #endif /* DBUS_BUILD_TESTS */
998 static DBusHashEntry*
999 find_direct_function (DBusHashTable *table,
1001 dbus_bool_t create_if_not_found,
1002 DBusHashEntry ***bucket,
1003 DBusPreallocatedHash *preallocated)
1007 idx = RANDOM_INDEX (table, key) & table->mask;
1010 return find_generic_function (table, key, idx,
1011 NULL, create_if_not_found, bucket,
1016 rebuild_table (DBusHashTable *table)
1020 DBusHashEntry **old_buckets;
1021 DBusHashEntry **old_chain;
1022 DBusHashEntry *entry;
1023 dbus_bool_t growing;
1026 * Allocate and initialize the new bucket array, and set up
1027 * hashing constants for new array size.
1030 growing = table->n_entries >= table->hi_rebuild_size;
1032 old_size = table->n_buckets;
1033 old_buckets = table->buckets;
1037 /* overflow paranoia */
1038 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
1039 table->down_shift >= 0)
1040 new_buckets = table->n_buckets * 4;
1042 return; /* can't grow anymore */
1046 new_buckets = table->n_buckets / 4;
1047 if (new_buckets < DBUS_SMALL_HASH_TABLE)
1048 return; /* don't bother shrinking this far */
1051 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
1052 if (table->buckets == NULL)
1054 /* out of memory, yay - just don't reallocate, the table will
1055 * still work, albeit more slowly.
1057 table->buckets = old_buckets;
1061 table->n_buckets = new_buckets;
1065 table->lo_rebuild_size = table->hi_rebuild_size;
1066 table->hi_rebuild_size *= 4;
1068 table->down_shift -= 2; /* keep 2 more high bits */
1069 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
1073 table->hi_rebuild_size = table->lo_rebuild_size;
1074 table->lo_rebuild_size /= 4;
1076 table->down_shift += 2; /* keep 2 fewer high bits */
1077 table->mask = table->mask >> 2; /* keep 2 fewer high bits */
1081 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
1082 growing ? "GROW" : "SHRINK",
1083 table->lo_rebuild_size,
1084 table->hi_rebuild_size,
1089 _dbus_assert (table->lo_rebuild_size >= 0);
1090 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
1091 _dbus_assert (table->mask != 0);
1092 /* the mask is essentially the max index */
1093 _dbus_assert (table->mask < table->n_buckets);
1096 * Rehash all of the existing entries into the new bucket array.
1099 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1101 for (entry = *old_chain; entry != NULL; entry = *old_chain)
1104 DBusHashEntry **bucket;
1106 *old_chain = entry->next;
1107 switch (table->key_type)
1109 case DBUS_HASH_STRING:
1110 idx = string_hash (entry->key) & table->mask;
1112 case DBUS_HASH_TWO_STRINGS:
1113 #ifdef DBUS_BUILD_TESTS
1114 idx = two_strings_hash (entry->key) & table->mask;
1117 _dbus_assert_not_reached ("two-strings is not enabled");
1121 case DBUS_HASH_UINTPTR:
1122 case DBUS_HASH_POINTER:
1123 idx = RANDOM_INDEX (table, entry->key);
1127 _dbus_assert_not_reached ("Unknown hash table type");
1131 bucket = &(table->buckets[idx]);
1132 entry->next = *bucket;
1137 /* Free the old bucket array, if it was dynamically allocated. */
1139 if (old_buckets != table->static_buckets)
1140 dbus_free (old_buckets);
1144 * Looks up the value for a given string in a hash table
1145 * of type #DBUS_HASH_STRING. Returns %NULL if the value
1146 * is not present. (A not-present entry is indistinguishable
1147 * from an entry with a value of %NULL.)
1148 * @param table the hash table.
1149 * @param key the string to look up.
1150 * @returns the value of the hash entry.
1153 _dbus_hash_table_lookup_string (DBusHashTable *table,
1156 DBusHashEntry *entry;
1158 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1160 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1163 return entry->value;
1168 #ifdef DBUS_BUILD_TESTS
1170 * Looks up the value for a given string in a hash table
1171 * of type #DBUS_HASH_TWO_STRINGS. Returns %NULL if the value
1172 * is not present. (A not-present entry is indistinguishable
1173 * from an entry with a value of %NULL.)
1174 * @param table the hash table.
1175 * @param key the string to look up.
1176 * @returns the value of the hash entry.
1179 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
1182 DBusHashEntry *entry;
1184 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
1186 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1189 return entry->value;
1193 #endif /* DBUS_BUILD_TESTS */
1196 * Looks up the value for a given integer in a hash table
1197 * of type #DBUS_HASH_INT. Returns %NULL if the value
1198 * is not present. (A not-present entry is indistinguishable
1199 * from an entry with a value of %NULL.)
1200 * @param table the hash table.
1201 * @param key the integer to look up.
1202 * @returns the value of the hash entry.
1205 _dbus_hash_table_lookup_int (DBusHashTable *table,
1208 DBusHashEntry *entry;
1210 _dbus_assert (table->key_type == DBUS_HASH_INT);
1212 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1215 return entry->value;
1220 #ifdef DBUS_BUILD_TESTS
1221 /* disabled since it's only used for testing */
1223 * Looks up the value for a given integer in a hash table
1224 * of type #DBUS_HASH_POINTER. Returns %NULL if the value
1225 * is not present. (A not-present entry is indistinguishable
1226 * from an entry with a value of %NULL.)
1227 * @param table the hash table.
1228 * @param key the integer to look up.
1229 * @returns the value of the hash entry.
1232 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
1235 DBusHashEntry *entry;
1237 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1239 entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
1242 return entry->value;
1246 #endif /* DBUS_BUILD_TESTS */
1249 * Looks up the value for a given integer in a hash table
1250 * of type #DBUS_HASH_UINTPTR. Returns %NULL if the value
1251 * is not present. (A not-present entry is indistinguishable
1252 * from an entry with a value of %NULL.)
1253 * @param table the hash table.
1254 * @param key the integer to look up.
1255 * @returns the value of the hash entry.
1258 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
1261 DBusHashEntry *entry;
1263 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1265 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1268 return entry->value;
1274 * Removes the hash entry for the given key. If no hash entry
1275 * for the key exists, does nothing.
1277 * @param table the hash table.
1278 * @param key the hash key.
1279 * @returns #TRUE if the entry existed
1282 _dbus_hash_table_remove_string (DBusHashTable *table,
1285 DBusHashEntry *entry;
1286 DBusHashEntry **bucket;
1288 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1290 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1294 remove_entry (table, bucket, entry);
1301 #ifdef DBUS_BUILD_TESTS
1303 * Removes the hash entry for the given key. If no hash entry
1304 * for the key exists, does nothing.
1306 * @param table the hash table.
1307 * @param key the hash key.
1308 * @returns #TRUE if the entry existed
1311 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
1314 DBusHashEntry *entry;
1315 DBusHashEntry **bucket;
1317 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
1319 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1323 remove_entry (table, bucket, entry);
1329 #endif /* DBUS_BUILD_TESTS */
1332 * Removes the hash entry for the given key. If no hash entry
1333 * for the key exists, does nothing.
1335 * @param table the hash table.
1336 * @param key the hash key.
1337 * @returns #TRUE if the entry existed
1340 _dbus_hash_table_remove_int (DBusHashTable *table,
1343 DBusHashEntry *entry;
1344 DBusHashEntry **bucket;
1346 _dbus_assert (table->key_type == DBUS_HASH_INT);
1348 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1352 remove_entry (table, bucket, entry);
1359 #ifdef DBUS_BUILD_TESTS
1360 /* disabled since it's only used for testing */
1362 * Removes the hash entry for the given key. If no hash entry
1363 * for the key exists, does nothing.
1365 * @param table the hash table.
1366 * @param key the hash key.
1367 * @returns #TRUE if the entry existed
1370 _dbus_hash_table_remove_pointer (DBusHashTable *table,
1373 DBusHashEntry *entry;
1374 DBusHashEntry **bucket;
1376 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1378 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
1382 remove_entry (table, bucket, entry);
1388 #endif /* DBUS_BUILD_TESTS */
1391 * Removes the hash entry for the given key. If no hash entry
1392 * for the key exists, does nothing.
1394 * @param table the hash table.
1395 * @param key the hash key.
1396 * @returns #TRUE if the entry existed
1399 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
1402 DBusHashEntry *entry;
1403 DBusHashEntry **bucket;
1405 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1407 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1411 remove_entry (table, bucket, entry);
1419 * Creates a hash entry with the given key and value.
1420 * The key and value are not copied; they are stored
1421 * in the hash table by reference. If an entry with the
1422 * given key already exists, the previous key and value
1423 * are overwritten (and freed if the hash table has
1424 * a key_free_function and/or value_free_function).
1426 * Returns #FALSE if memory for the new hash entry
1427 * can't be allocated.
1429 * @param table the hash table.
1430 * @param key the hash entry key.
1431 * @param value the hash entry value.
1434 _dbus_hash_table_insert_string (DBusHashTable *table,
1438 DBusPreallocatedHash *preallocated;
1440 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1442 preallocated = _dbus_hash_table_preallocate_entry (table);
1443 if (preallocated == NULL)
1446 _dbus_hash_table_insert_string_preallocated (table, preallocated,
1452 #ifdef DBUS_BUILD_TESTS
1454 * Creates a hash entry with the given key and value.
1455 * The key and value are not copied; they are stored
1456 * in the hash table by reference. If an entry with the
1457 * given key already exists, the previous key and value
1458 * are overwritten (and freed if the hash table has
1459 * a key_free_function and/or value_free_function).
1461 * Returns #FALSE if memory for the new hash entry
1462 * can't be allocated.
1464 * @param table the hash table.
1465 * @param key the hash entry key.
1466 * @param value the hash entry value.
1469 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
1473 DBusHashEntry *entry;
1475 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
1477 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1480 return FALSE; /* no memory */
1482 if (table->free_key_function && entry->key != key)
1483 (* table->free_key_function) (entry->key);
1485 if (table->free_value_function && entry->value != value)
1486 (* table->free_value_function) (entry->value);
1489 entry->value = value;
1493 #endif /* DBUS_BUILD_TESTS */
1496 * Creates a hash entry with the given key and value.
1497 * The key and value are not copied; they are stored
1498 * in the hash table by reference. If an entry with the
1499 * given key already exists, the previous key and value
1500 * are overwritten (and freed if the hash table has
1501 * a key_free_function and/or value_free_function).
1503 * Returns #FALSE if memory for the new hash entry
1504 * can't be allocated.
1506 * @param table the hash table.
1507 * @param key the hash entry key.
1508 * @param value the hash entry value.
1511 _dbus_hash_table_insert_int (DBusHashTable *table,
1515 DBusHashEntry *entry;
1517 _dbus_assert (table->key_type == DBUS_HASH_INT);
1519 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1522 return FALSE; /* no memory */
1524 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1525 (* table->free_key_function) (entry->key);
1527 if (table->free_value_function && entry->value != value)
1528 (* table->free_value_function) (entry->value);
1530 entry->key = _DBUS_INT_TO_POINTER (key);
1531 entry->value = value;
1536 #ifdef DBUS_BUILD_TESTS
1537 /* disabled since it's only used for testing */
1539 * Creates a hash entry with the given key and value.
1540 * The key and value are not copied; they are stored
1541 * in the hash table by reference. If an entry with the
1542 * given key already exists, the previous key and value
1543 * are overwritten (and freed if the hash table has
1544 * a key_free_function and/or value_free_function).
1546 * Returns #FALSE if memory for the new hash entry
1547 * can't be allocated.
1549 * @param table the hash table.
1550 * @param key the hash entry key.
1551 * @param value the hash entry value.
1554 _dbus_hash_table_insert_pointer (DBusHashTable *table,
1558 DBusHashEntry *entry;
1560 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1562 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1565 return FALSE; /* no memory */
1567 if (table->free_key_function && entry->key != key)
1568 (* table->free_key_function) (entry->key);
1570 if (table->free_value_function && entry->value != value)
1571 (* table->free_value_function) (entry->value);
1574 entry->value = value;
1578 #endif /* DBUS_BUILD_TESTS */
1581 * Creates a hash entry with the given key and value.
1582 * The key and value are not copied; they are stored
1583 * in the hash table by reference. If an entry with the
1584 * given key already exists, the previous key and value
1585 * are overwritten (and freed if the hash table has
1586 * a key_free_function and/or value_free_function).
1588 * Returns #FALSE if memory for the new hash entry
1589 * can't be allocated.
1591 * @param table the hash table.
1592 * @param key the hash entry key.
1593 * @param value the hash entry value.
1596 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
1600 DBusHashEntry *entry;
1602 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1604 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1607 return FALSE; /* no memory */
1609 if (table->free_key_function && entry->key != (void*) key)
1610 (* table->free_key_function) (entry->key);
1612 if (table->free_value_function && entry->value != value)
1613 (* table->free_value_function) (entry->value);
1615 entry->key = (void*) key;
1616 entry->value = value;
1622 * Preallocate an opaque data blob that allows us to insert into the
1623 * hash table at a later time without allocating any memory.
1625 * @param table the hash table
1626 * @returns the preallocated data, or #NULL if no memory
1628 DBusPreallocatedHash*
1629 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
1631 DBusHashEntry *entry;
1633 entry = alloc_entry (table);
1635 return (DBusPreallocatedHash*) entry;
1639 * Frees an opaque DBusPreallocatedHash that was *not* used
1640 * in order to insert into the hash table.
1642 * @param table the hash table
1643 * @param preallocated the preallocated data
1646 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table,
1647 DBusPreallocatedHash *preallocated)
1649 DBusHashEntry *entry;
1651 _dbus_assert (preallocated != NULL);
1653 entry = (DBusHashEntry*) preallocated;
1655 /* Don't use free_entry(), since this entry has no key/data */
1656 _dbus_mem_pool_dealloc (table->entry_pool, entry);
1660 * Inserts a string-keyed entry into the hash table, using a
1661 * preallocated data block from
1662 * _dbus_hash_table_preallocate_entry(). This function cannot fail due
1663 * to lack of memory. The DBusPreallocatedHash object is consumed and
1664 * should not be reused or freed. Otherwise this function works
1665 * just like _dbus_hash_table_insert_string().
1667 * @param table the hash table
1668 * @param preallocated the preallocated data
1669 * @param key the hash key
1670 * @param value the value
1673 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table,
1674 DBusPreallocatedHash *preallocated,
1678 DBusHashEntry *entry;
1680 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1681 _dbus_assert (preallocated != NULL);
1683 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1685 _dbus_assert (entry != NULL);
1687 if (table->free_key_function && entry->key != key)
1688 (* table->free_key_function) (entry->key);
1690 if (table->free_value_function && entry->value != value)
1691 (* table->free_value_function) (entry->value);
1694 entry->value = value;
1698 * Gets the number of hash entries in a hash table.
1700 * @param table the hash table.
1701 * @returns the number of entries in the table.
1704 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1706 return table->n_entries;
1711 #ifdef DBUS_BUILD_TESTS
1712 #include "dbus-test.h"
1715 /* If you're wondering why the hash table test takes
1716 * forever to run, it's because we call this function
1717 * in inner loops thus making things quadratic.
1720 count_entries (DBusHashTable *table)
1726 _dbus_hash_iter_init (table, &iter);
1727 while (_dbus_hash_iter_next (&iter))
1730 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1735 /* Copy the foo\0bar\0 double string thing */
1737 _dbus_strdup2 (const char *str)
1746 len += strlen ((str + len + 1));
1748 copy = dbus_malloc (len + 2);
1752 memcpy (copy, str, len + 2);
1758 * @ingroup DBusHashTableInternals
1759 * Unit test for DBusHashTable
1760 * @returns #TRUE on success.
1763 _dbus_hash_test (void)
1766 DBusHashTable *table1;
1767 DBusHashTable *table2;
1768 DBusHashTable *table3;
1769 DBusHashTable *table4;
1771 #define N_HASH_KEYS 5000
1773 dbus_bool_t ret = FALSE;
1775 keys = dbus_new (char *, N_HASH_KEYS);
1777 _dbus_assert_not_reached ("no memory");
1779 for (i = 0; i < N_HASH_KEYS; i++)
1781 keys[i] = dbus_malloc (128);
1783 if (keys[i] == NULL)
1784 _dbus_assert_not_reached ("no memory");
1787 printf ("Computing test hash keys...\n");
1789 while (i < N_HASH_KEYS)
1793 /* all the hash keys are TWO_STRINGS, but
1794 * then we can also use those as regular strings.
1797 len = sprintf (keys[i], "Hash key %d", i);
1798 sprintf (keys[i] + len + 1, "Two string %d", i);
1799 _dbus_assert (*(keys[i] + len) == '\0');
1800 _dbus_assert (*(keys[i] + len + 1) != '\0');
1803 printf ("... done.\n");
1805 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1806 dbus_free, dbus_free);
1810 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1815 table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
1820 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
1821 dbus_free, dbus_free);
1826 /* Insert and remove a bunch of stuff, counting the table in between
1827 * to be sure it's not broken and that iteration works
1835 key = _dbus_strdup (keys[i]);
1838 value = _dbus_strdup ("Value!");
1842 if (!_dbus_hash_table_insert_string (table1,
1846 value = _dbus_strdup (keys[i]);
1850 if (!_dbus_hash_table_insert_int (table2,
1854 value = _dbus_strdup (keys[i]);
1858 if (!_dbus_hash_table_insert_uintptr (table3,
1862 key = _dbus_strdup2 (keys[i]);
1865 value = _dbus_strdup ("Value!");
1869 if (!_dbus_hash_table_insert_two_strings (table4,
1873 _dbus_assert (count_entries (table1) == i + 1);
1874 _dbus_assert (count_entries (table2) == i + 1);
1875 _dbus_assert (count_entries (table3) == i + 1);
1876 _dbus_assert (count_entries (table4) == i + 1);
1878 value = _dbus_hash_table_lookup_string (table1, keys[i]);
1879 _dbus_assert (value != NULL);
1880 _dbus_assert (strcmp (value, "Value!") == 0);
1882 value = _dbus_hash_table_lookup_int (table2, i);
1883 _dbus_assert (value != NULL);
1884 _dbus_assert (strcmp (value, keys[i]) == 0);
1886 value = _dbus_hash_table_lookup_uintptr (table3, i);
1887 _dbus_assert (value != NULL);
1888 _dbus_assert (strcmp (value, keys[i]) == 0);
1890 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
1891 _dbus_assert (value != NULL);
1892 _dbus_assert (strcmp (value, "Value!") == 0);
1900 _dbus_hash_table_remove_string (table1,
1903 _dbus_hash_table_remove_int (table2, i);
1905 _dbus_hash_table_remove_uintptr (table3, i);
1907 _dbus_hash_table_remove_two_strings (table4,
1910 _dbus_assert (count_entries (table1) == i);
1911 _dbus_assert (count_entries (table2) == i);
1912 _dbus_assert (count_entries (table3) == i);
1913 _dbus_assert (count_entries (table4) == i);
1918 _dbus_hash_table_ref (table1);
1919 _dbus_hash_table_ref (table2);
1920 _dbus_hash_table_ref (table3);
1921 _dbus_hash_table_ref (table4);
1922 _dbus_hash_table_unref (table1);
1923 _dbus_hash_table_unref (table2);
1924 _dbus_hash_table_unref (table3);
1925 _dbus_hash_table_unref (table4);
1926 _dbus_hash_table_unref (table1);
1927 _dbus_hash_table_unref (table2);
1928 _dbus_hash_table_unref (table3);
1929 _dbus_hash_table_unref (table4);
1932 /* Insert a bunch of stuff then check
1933 * that iteration works correctly (finds the right
1934 * values, iter_set_value works, etc.)
1936 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1937 dbus_free, dbus_free);
1941 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1952 key = _dbus_strdup (keys[i]);
1955 value = _dbus_strdup ("Value!");
1959 if (!_dbus_hash_table_insert_string (table1,
1963 value = _dbus_strdup (keys[i]);
1967 if (!_dbus_hash_table_insert_int (table2,
1971 _dbus_assert (count_entries (table1) == i + 1);
1972 _dbus_assert (count_entries (table2) == i + 1);
1977 _dbus_hash_iter_init (table1, &iter);
1978 while (_dbus_hash_iter_next (&iter))
1983 key = _dbus_hash_iter_get_string_key (&iter);
1984 value = _dbus_hash_iter_get_value (&iter);
1986 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1988 value = _dbus_strdup ("Different value!");
1992 _dbus_hash_iter_set_value (&iter, value);
1994 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1997 _dbus_hash_iter_init (table1, &iter);
1998 while (_dbus_hash_iter_next (&iter))
2000 _dbus_hash_iter_remove_entry (&iter);
2001 _dbus_assert (count_entries (table1) == i - 1);
2005 _dbus_hash_iter_init (table2, &iter);
2006 while (_dbus_hash_iter_next (&iter))
2011 key = _dbus_hash_iter_get_int_key (&iter);
2012 value = _dbus_hash_iter_get_value (&iter);
2014 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
2016 value = _dbus_strdup ("Different value!");
2020 _dbus_hash_iter_set_value (&iter, value);
2022 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
2025 i = count_entries (table2);
2026 _dbus_hash_iter_init (table2, &iter);
2027 while (_dbus_hash_iter_next (&iter))
2029 _dbus_hash_iter_remove_entry (&iter);
2030 _dbus_assert (count_entries (table2) + 1 == i);
2034 /* add/remove interleaved, to check that we grow/shrink the table
2043 key = _dbus_strdup (keys[i]);
2047 value = _dbus_strdup ("Value!");
2051 if (!_dbus_hash_table_insert_string (table1,
2064 key = _dbus_strdup (keys[i]);
2067 value = _dbus_strdup ("Value!");
2071 if (!_dbus_hash_table_remove_string (table1, keys[i]))
2074 if (!_dbus_hash_table_insert_string (table1,
2078 if (!_dbus_hash_table_remove_string (table1, keys[i]))
2081 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
2086 /* nuke these tables */
2087 _dbus_hash_table_unref (table1);
2088 _dbus_hash_table_unref (table2);
2091 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
2092 * be sure that interface works.
2094 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
2095 dbus_free, dbus_free);
2099 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
2110 key = _dbus_strdup (keys[i]);
2113 value = _dbus_strdup ("Value!");
2117 if (!_dbus_hash_iter_lookup (table1,
2120 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
2121 _dbus_hash_iter_set_value (&iter, value);
2123 value = _dbus_strdup (keys[i]);
2127 if (!_dbus_hash_iter_lookup (table2,
2128 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
2130 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
2131 _dbus_hash_iter_set_value (&iter, value);
2133 _dbus_assert (count_entries (table1) == i + 1);
2134 _dbus_assert (count_entries (table2) == i + 1);
2136 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
2139 value = _dbus_hash_iter_get_value (&iter);
2140 _dbus_assert (value != NULL);
2141 _dbus_assert (strcmp (value, "Value!") == 0);
2143 /* Iterate just to be sure it works, though
2144 * it's a stupid thing to do
2146 while (_dbus_hash_iter_next (&iter))
2149 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
2152 value = _dbus_hash_iter_get_value (&iter);
2153 _dbus_assert (value != NULL);
2154 _dbus_assert (strcmp (value, keys[i]) == 0);
2156 /* Iterate just to be sure it works, though
2157 * it's a stupid thing to do
2159 while (_dbus_hash_iter_next (&iter))
2168 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
2169 _dbus_assert_not_reached ("hash entry should have existed");
2170 _dbus_hash_iter_remove_entry (&iter);
2172 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
2173 _dbus_assert_not_reached ("hash entry should have existed");
2174 _dbus_hash_iter_remove_entry (&iter);
2176 _dbus_assert (count_entries (table1) == i);
2177 _dbus_assert (count_entries (table2) == i);
2182 _dbus_hash_table_unref (table1);
2183 _dbus_hash_table_unref (table2);
2188 for (i = 0; i < N_HASH_KEYS; i++)
2189 dbus_free (keys[i]);
2196 #endif /* DBUS_BUILD_TESTS */