/* -*- mode: C; c-file-style: "gnu" -*- */ /* dbus-hash.c Generic hash table utility (internal to D-BUS implementation) * * Copyright (C) 2002 Red Hat, Inc. * Copyright (c) 1991-1993 The Regents of the University of California. * Copyright (c) 1994 Sun Microsystems, Inc. * * Hash table implementation based on generic/tclHash.c from the Tcl * source code. The original Tcl license applies to portions of the * code from tclHash.c; the Tcl license follows this standad D-BUS * license information. * * Licensed under the Academic Free License version 2.1 * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ /* * The following copyright applies to code from the Tcl distribution. * * Copyright (c) 1991-1993 The Regents of the University of California. * Copyright (c) 1994 Sun Microsystems, Inc. * * This software is copyrighted by the Regents of the University of * California, Sun Microsystems, Inc., Scriptics Corporation, and * other parties. The following terms apply to all files associated * with the software unless explicitly disclaimed in individual files. * * The authors hereby grant permission to use, copy, modify, * distribute, and license this software and its documentation for any * purpose, provided that existing copyright notices are retained in * all copies and that this notice is included verbatim in any * distributions. No written agreement, license, or royalty fee is * required for any of the authorized uses. Modifications to this * software may be copyrighted by their authors and need not follow * the licensing terms described here, provided that the new terms are * clearly indicated on the first page of each file where they apply. * * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. * * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. * * GOVERNMENT USE: If you are acquiring this software on behalf of the * U.S. government, the Government shall have only "Restricted Rights" * in the software and related documentation as defined in the Federal * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you * are acquiring the software on behalf of the Department of Defense, * the software shall be classified as "Commercial Computer Software" * and the Government shall have only "Restricted Rights" as defined * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the * foregoing, the authors grant the U.S. Government and others acting * in its behalf permission to use and distribute the software in * accordance with the terms specified in this license. */ #include "dbus-hash.h" #include "dbus-internals.h" #include "dbus-mempool.h" /** * @defgroup DBusHashTable Hash table * @ingroup DBusInternals * @brief DBusHashTable data structure * * Types and functions related to DBusHashTable. */ /** * @defgroup DBusHashTableInternals Hash table implementation details * @ingroup DBusInternals * @brief DBusHashTable implementation details * * The guts of DBusHashTable. * * @{ */ /** * When there are this many entries per bucket, on average, rebuild * the hash table to make it larger. */ #define REBUILD_MULTIPLIER 3 /** * Takes a preliminary integer hash value and produces an index into a * hash tables bucket list. The idea is to make it so that * preliminary values that are arbitrarily similar will end up in * different buckets. The hash function was taken from a * random-number generator. (This is used to hash integers.) * * The down_shift drops off the high bits of the hash index, and * decreases as we increase the number of hash buckets (to keep more * range in the hash index). The mask also strips high bits and strips * fewer high bits as the number of hash buckets increases. * I don't understand two things: why is the initial downshift 28 * to keep 4 bits when the initial mask is 011 to keep 2 bits, * and why do we have both a mask and a downshift? * */ #define RANDOM_INDEX(table, i) \ (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask) /** * Initial number of buckets in hash table (hash table statically * allocates its buckets for this size and below). * The initial mask has to be synced to this. */ #define DBUS_SMALL_HASH_TABLE 4 /** * Typedef for DBusHashEntry */ typedef struct DBusHashEntry DBusHashEntry; /** * @brief Internal representation of a hash entry. * * A single entry (key-value pair) in the hash table. * Internal to hash table implementation. */ struct DBusHashEntry { DBusHashEntry *next; /**< Pointer to next entry in this * hash bucket, or #NULL for end of * chain. */ void *key; /**< Hash key */ void *value; /**< Hash value */ }; /** * Function used to find and optionally create a hash entry. */ typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated); /** * @brief Internals of DBusHashTable. * * Hash table internals. Hash tables are opaque objects, they must be * used via accessor functions. */ struct DBusHashTable { int refcount; /**< Reference count */ DBusHashEntry **buckets; /**< Pointer to bucket array. Each * element points to first entry in * bucket's hash chain, or #NULL. */ DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE]; /**< Bucket array used for small tables * (to avoid mallocs and frees). */ int n_buckets; /**< Total number of buckets allocated * at **buckets. */ int n_entries; /**< Total number of entries present * in table. */ int hi_rebuild_size; /**< Enlarge table when n_entries gets * to be this large. */ int lo_rebuild_size; /**< Shrink table when n_entries gets * below this. */ int down_shift; /**< Shift count used in hashing * function. Designed to use high- * order bits of randomized keys. */ int mask; /**< Mask value used in hashing * function. */ DBusHashType key_type; /**< Type of keys used in this table */ DBusFindEntryFunction find_function; /**< Function for finding entries */ DBusFreeFunction free_key_function; /**< Function to free keys */ DBusFreeFunction free_value_function; /**< Function to free values */ DBusMemPool *entry_pool; /**< Memory pool for hash entries */ }; /** * @brief Internals of DBusHashIter. */ typedef struct { DBusHashTable *table; /**< Pointer to table containing entry. */ DBusHashEntry **bucket; /**< Pointer to bucket that points to * first entry in this entry's chain: * used for deleting the entry. */ DBusHashEntry *entry; /**< Current hash entry */ DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */ int next_bucket; /**< index of next bucket */ int n_entries_on_init; /**< used to detect table resize since initialization */ } DBusRealHashIter; static DBusHashEntry* find_direct_function (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated); static DBusHashEntry* find_string_function (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated); #ifdef DBUS_BUILD_TESTS static DBusHashEntry* find_two_strings_function (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated); #endif static unsigned int string_hash (const char *str); #ifdef DBUS_BUILD_TESTS static unsigned int two_strings_hash (const char *str); #endif static void rebuild_table (DBusHashTable *table); static DBusHashEntry* alloc_entry (DBusHashTable *table); static void remove_entry (DBusHashTable *table, DBusHashEntry **bucket, DBusHashEntry *entry); static void free_entry (DBusHashTable *table, DBusHashEntry *entry); static void free_entry_data (DBusHashTable *table, DBusHashEntry *entry); /** @} */ /** * @addtogroup DBusHashTable * @{ */ /** * @typedef DBusHashIter * * Public opaque hash table iterator object. */ /** * @typedef DBusHashTable * * Public opaque hash table object. */ /** * @typedef DBusHashType * * Indicates the type of a key in the hash table. */ /** * Constructs a new hash table. Should be freed with * _dbus_hash_table_unref(). If memory cannot be * allocated for the hash table, returns #NULL. * * @param type the type of hash key to use. * @param key_free_function function to free hash keys. * @param value_free_function function to free hash values. * @returns a new DBusHashTable or #NULL if no memory. */ DBusHashTable* _dbus_hash_table_new (DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function) { DBusHashTable *table; DBusMemPool *entry_pool; table = dbus_new0 (DBusHashTable, 1); if (table == NULL) return NULL; entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); if (entry_pool == NULL) { dbus_free (table); return NULL; } table->refcount = 1; table->entry_pool = entry_pool; _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); table->buckets = table->static_buckets; table->n_buckets = DBUS_SMALL_HASH_TABLE; table->n_entries = 0; table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; table->lo_rebuild_size = 0; table->down_shift = 28; table->mask = 3; table->key_type = type; _dbus_assert (table->mask < table->n_buckets); switch (table->key_type) { case DBUS_HASH_INT: case DBUS_HASH_POINTER: case DBUS_HASH_ULONG: table->find_function = find_direct_function; break; case DBUS_HASH_STRING: table->find_function = find_string_function; break; case DBUS_HASH_TWO_STRINGS: #ifdef DBUS_BUILD_TESTS table->find_function = find_two_strings_function; #endif break; default: _dbus_assert_not_reached ("Unknown hash table type"); break; } table->free_key_function = key_free_function; table->free_value_function = value_free_function; return table; } /** * Increments the reference count for a hash table. * * @param table the hash table to add a reference to. * @returns the hash table. */ DBusHashTable * _dbus_hash_table_ref (DBusHashTable *table) { table->refcount += 1; return table; } /** * Decrements the reference count for a hash table, * freeing the hash table if the count reaches zero. * * @param table the hash table to remove a reference from. */ void _dbus_hash_table_unref (DBusHashTable *table) { table->refcount -= 1; if (table->refcount == 0) { #if 0 DBusHashEntry *entry; DBusHashEntry *next; int i; /* Free the entries in the table. */ for (i = 0; i < table->n_buckets; i++) { entry = table->buckets[i]; while (entry != NULL) { next = entry->next; free_entry (table, entry); entry = next; } } #else DBusHashEntry *entry; int i; /* Free the entries in the table. */ for (i = 0; i < table->n_buckets; i++) { entry = table->buckets[i]; while (entry != NULL) { free_entry_data (table, entry); entry = entry->next; } } /* We can do this very quickly with memory pools ;-) */ _dbus_mem_pool_free (table->entry_pool); #endif /* Free the bucket array, if it was dynamically allocated. */ if (table->buckets != table->static_buckets) dbus_free (table->buckets); dbus_free (table); } } static DBusHashEntry* alloc_entry (DBusHashTable *table) { DBusHashEntry *entry; entry = _dbus_mem_pool_alloc (table->entry_pool); return entry; } static void free_entry_data (DBusHashTable *table, DBusHashEntry *entry) { if (table->free_key_function) (* table->free_key_function) (entry->key); if (table->free_value_function) (* table->free_value_function) (entry->value); } static void free_entry (DBusHashTable *table, DBusHashEntry *entry) { free_entry_data (table, entry); _dbus_mem_pool_dealloc (table->entry_pool, entry); } static void remove_entry (DBusHashTable *table, DBusHashEntry **bucket, DBusHashEntry *entry) { _dbus_assert (table != NULL); _dbus_assert (bucket != NULL); _dbus_assert (*bucket != NULL); _dbus_assert (entry != NULL); if (*bucket == entry) *bucket = entry->next; else { DBusHashEntry *prev; prev = *bucket; while (prev->next != entry) prev = prev->next; _dbus_assert (prev != NULL); prev->next = entry->next; } table->n_entries -= 1; free_entry (table, entry); } /** * Initializes a hash table iterator. To iterate over all entries in a * hash table, use the following code (the printf assumes a hash * from strings to strings obviously): * * @code * DBusHashIter iter; * * _dbus_hash_iter_init (table, &iter); * while (_dbus_hash_iter_next (&iter)) * { * printf ("The first key is %s and value is %s\n", * _dbus_hash_iter_get_string_key (&iter), * _dbus_hash_iter_get_value (&iter)); * } * * * @endcode * * The iterator is initialized pointing "one before" the first hash * entry. The first call to _dbus_hash_iter_next() moves it onto * the first valid entry or returns #FALSE if the hash table is * empty. Subsequent calls move to the next valid entry or return * #FALSE if there are no more entries. * * Note that it is guaranteed to be safe to remove a hash entry during * iteration, but it is not safe to add a hash entry. * * @param table the hash table to iterate over. * @param iter the iterator to initialize. */ void _dbus_hash_iter_init (DBusHashTable *table, DBusHashIter *iter) { DBusRealHashIter *real; _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); real = (DBusRealHashIter*) iter; real->table = table; real->bucket = NULL; real->entry = NULL; real->next_entry = NULL; real->next_bucket = 0; real->n_entries_on_init = table->n_entries; } /** * Move the hash iterator forward one step, to the next hash entry. * The documentation for _dbus_hash_iter_init() explains in more * detail. * * @param iter the iterator to move forward. * @returns #FALSE if there are no more entries to move to. */ dbus_bool_t _dbus_hash_iter_next (DBusHashIter *iter) { DBusRealHashIter *real; _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); real = (DBusRealHashIter*) iter; /* if this assertion failed someone probably added hash entries * during iteration, which is bad. */ _dbus_assert (real->n_entries_on_init >= real->table->n_entries); /* Remember that real->entry may have been deleted */ while (real->next_entry == NULL) { if (real->next_bucket >= real->table->n_buckets) { /* invalidate iter and return false */ real->entry = NULL; real->table = NULL; real->bucket = NULL; return FALSE; } real->bucket = &(real->table->buckets[real->next_bucket]); real->next_entry = *(real->bucket); real->next_bucket += 1; } _dbus_assert (real->next_entry != NULL); _dbus_assert (real->bucket != NULL); real->entry = real->next_entry; real->next_entry = real->entry->next; return TRUE; } /** * Removes the current entry from the hash table. * If a key_free_function or value_free_function * was provided to _dbus_hash_table_new(), * frees the key and/or value for this entry. * * @param iter the hash table iterator. */ void _dbus_hash_iter_remove_entry (DBusHashIter *iter) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); _dbus_assert (real->bucket != NULL); remove_entry (real->table, real->bucket, real->entry); real->entry = NULL; /* make it crash if you try to use this entry */ } /** * Gets the value of the current entry. * * @param iter the hash table iterator. */ void* _dbus_hash_iter_get_value (DBusHashIter *iter) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); return real->entry->value; } /** * Sets the value of the current entry. * If the hash table has a value_free_function * it will be used to free the previous value. * The hash table will own the passed-in value * (it will not be copied). * * @param iter the hash table iterator. * @param value the new value. */ void _dbus_hash_iter_set_value (DBusHashIter *iter, void *value) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); if (real->table->free_value_function && value != real->entry->value) (* real->table->free_value_function) (real->entry->value); real->entry->value = value; } /** * Gets the key for the current entry. * Only works for hash tables of type #DBUS_HASH_INT. * * @param iter the hash table iterator. */ int _dbus_hash_iter_get_int_key (DBusHashIter *iter) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); return _DBUS_POINTER_TO_INT (real->entry->key); } /** * Gets the key for the current entry. * Only works for hash tables of type #DBUS_HASH_ULONG. * * @param iter the hash table iterator. */ unsigned long _dbus_hash_iter_get_ulong_key (DBusHashIter *iter) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); return (unsigned long) real->entry->key; } /** * Gets the key for the current entry. * Only works for hash tables of type #DBUS_HASH_STRING * @param iter the hash table iterator. */ const char* _dbus_hash_iter_get_string_key (DBusHashIter *iter) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); return real->entry->key; } #ifdef DBUS_BUILD_TESTS /** * Gets the key for the current entry. * Only works for hash tables of type #DBUS_HASH_TWO_STRINGS * @param iter the hash table iterator. */ const char* _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter) { DBusRealHashIter *real; real = (DBusRealHashIter*) iter; _dbus_assert (real->table != NULL); _dbus_assert (real->entry != NULL); return real->entry->key; } #endif /* DBUS_BUILD_TESTS */ /** * A low-level but efficient interface for manipulating the hash * table. It's efficient because you can get, set, and optionally * create the hash entry while only running the hash function one * time. * * Note that while calling _dbus_hash_iter_next() on the iterator * filled in by this function may work, it's completely * undefined which entries are after this iter and which * are before it. So it would be silly to iterate using this * iterator. * * If the hash entry is created, its value will be initialized * to all bits zero. * * #FALSE may be returned due to memory allocation failure, or * because create_if_not_found was #FALSE and the entry * did not exist. * * If create_if_not_found is #TRUE and the entry is created, the hash * table takes ownership of the key that's passed in. * * For a hash table of type #DBUS_HASH_INT, cast the int * key to the key parameter using #_DBUS_INT_TO_POINTER(). * * @param table the hash table. * @param key the hash key. * @param create_if_not_found if #TRUE, create the entry if it didn't exist. * @param iter the iterator to initialize. * @returns #TRUE if the hash entry now exists (and the iterator is thus valid). */ dbus_bool_t _dbus_hash_iter_lookup (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashIter *iter) { DBusRealHashIter *real; DBusHashEntry *entry; DBusHashEntry **bucket; _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); real = (DBusRealHashIter*) iter; entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); if (entry == NULL) return FALSE; real->table = table; real->bucket = bucket; real->entry = entry; real->next_entry = entry->next; real->next_bucket = (bucket - table->buckets) + 1; real->n_entries_on_init = table->n_entries; _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); return TRUE; } static void add_allocated_entry (DBusHashTable *table, DBusHashEntry *entry, unsigned int idx, void *key, DBusHashEntry ***bucket) { DBusHashEntry **b; entry->key = key; b = &(table->buckets[idx]); entry->next = *b; *b = entry; if (bucket) *bucket = b; table->n_entries += 1; /* note we ONLY rebuild when ADDING - because you can iterate over a * table and remove entries safely. */ if (table->n_entries >= table->hi_rebuild_size || table->n_entries < table->lo_rebuild_size) rebuild_table (table); } static DBusHashEntry* add_entry (DBusHashTable *table, unsigned int idx, void *key, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated) { DBusHashEntry *entry; if (preallocated == NULL) { entry = alloc_entry (table); if (entry == NULL) { if (bucket) *bucket = NULL; return NULL; } } else { entry = (DBusHashEntry*) preallocated; } add_allocated_entry (table, entry, idx, key, bucket); return entry; } /* This is g_str_hash from GLib which was * extensively discussed/tested/profiled */ static unsigned int string_hash (const char *str) { const char *p = str; unsigned int h = *p; if (h) for (p += 1; *p != '\0'; p++) h = (h << 5) - h + *p; return h; } #ifdef DBUS_BUILD_TESTS /* This hashes a memory block with two nul-terminated strings * in it, used in dbus-object-registry.c at the moment. */ static unsigned int two_strings_hash (const char *str) { const char *p = str; unsigned int h = *p; if (h) for (p += 1; *p != '\0'; p++) h = (h << 5) - h + *p; for (p += 1; *p != '\0'; p++) h = (h << 5) - h + *p; return h; } #endif /* DBUS_BUILD_TESTS */ /** Key comparison function */ typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); static DBusHashEntry* find_generic_function (DBusHashTable *table, void *key, unsigned int idx, KeyCompareFunc compare_func, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated) { DBusHashEntry *entry; if (bucket) *bucket = NULL; /* Search all of the entries in this bucket. */ entry = table->buckets[idx]; while (entry != NULL) { if ((compare_func == NULL && key == entry->key) || (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) { if (bucket) *bucket = &(table->buckets[idx]); if (preallocated) _dbus_hash_table_free_preallocated_entry (table, preallocated); return entry; } entry = entry->next; } if (create_if_not_found) entry = add_entry (table, idx, key, bucket, preallocated); else if (preallocated) _dbus_hash_table_free_preallocated_entry (table, preallocated); return entry; } static DBusHashEntry* find_string_function (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated) { unsigned int idx; idx = string_hash (key) & table->mask; return find_generic_function (table, key, idx, (KeyCompareFunc) strcmp, create_if_not_found, bucket, preallocated); } #ifdef DBUS_BUILD_TESTS static int two_strings_cmp (const char *a, const char *b) { size_t len_a; size_t len_b; int res; res = strcmp (a, b); if (res != 0) return res; len_a = strlen (a); len_b = strlen (b); return strcmp (a + len_a + 1, b + len_b + 1); } #endif #ifdef DBUS_BUILD_TESTS static DBusHashEntry* find_two_strings_function (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated) { unsigned int idx; idx = two_strings_hash (key) & table->mask; return find_generic_function (table, key, idx, (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket, preallocated); } #endif /* DBUS_BUILD_TESTS */ static DBusHashEntry* find_direct_function (DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated) { unsigned int idx; idx = RANDOM_INDEX (table, key) & table->mask; return find_generic_function (table, key, idx, NULL, create_if_not_found, bucket, preallocated); } static void rebuild_table (DBusHashTable *table) { int old_size; int new_buckets; DBusHashEntry **old_buckets; DBusHashEntry **old_chain; DBusHashEntry *entry; dbus_bool_t growing; /* * Allocate and initialize the new bucket array, and set up * hashing constants for new array size. */ growing = table->n_entries >= table->hi_rebuild_size; old_size = table->n_buckets; old_buckets = table->buckets; if (growing) { /* overflow paranoia */ if (table->n_buckets < _DBUS_INT_MAX / 4 && table->down_shift >= 0) new_buckets = table->n_buckets * 4; else return; /* can't grow anymore */ } else { new_buckets = table->n_buckets / 4; if (new_buckets < DBUS_SMALL_HASH_TABLE) return; /* don't bother shrinking this far */ } table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); if (table->buckets == NULL) { /* out of memory, yay - just don't reallocate, the table will * still work, albeit more slowly. */ table->buckets = old_buckets; return; } table->n_buckets = new_buckets; if (growing) { table->lo_rebuild_size = table->hi_rebuild_size; table->hi_rebuild_size *= 4; table->down_shift -= 2; /* keep 2 more high bits */ table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ } else { table->hi_rebuild_size = table->lo_rebuild_size; table->lo_rebuild_size /= 4; table->down_shift += 2; /* keep 2 fewer high bits */ table->mask = table->mask >> 2; /* keep 2 fewer high bits */ } #if 0 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", growing ? "GROW" : "SHRINK", table->lo_rebuild_size, table->hi_rebuild_size, table->down_shift, table->mask); #endif _dbus_assert (table->lo_rebuild_size >= 0); _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); _dbus_assert (table->mask != 0); /* the mask is essentially the max index */ _dbus_assert (table->mask < table->n_buckets); /* * Rehash all of the existing entries into the new bucket array. */ for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) { for (entry = *old_chain; entry != NULL; entry = *old_chain) { unsigned int idx; DBusHashEntry **bucket; *old_chain = entry->next; switch (table->key_type) { case DBUS_HASH_STRING: idx = string_hash (entry->key) & table->mask; break; case DBUS_HASH_TWO_STRINGS: #ifdef DBUS_BUILD_TESTS idx = two_strings_hash (entry->key) & table->mask; #else idx = 0; _dbus_assert_not_reached ("two-strings is not enabled"); #endif break; case DBUS_HASH_INT: case DBUS_HASH_ULONG: case DBUS_HASH_POINTER: idx = RANDOM_INDEX (table, entry->key); break; default: idx = 0; _dbus_assert_not_reached ("Unknown hash table type"); break; } bucket = &(table->buckets[idx]); entry->next = *bucket; *bucket = entry; } } /* Free the old bucket array, if it was dynamically allocated. */ if (old_buckets != table->static_buckets) dbus_free (old_buckets); } /** * Looks up the value for a given string in a hash table * of type #DBUS_HASH_STRING. Returns %NULL if the value * is not present. (A not-present entry is indistinguishable * from an entry with a value of %NULL.) * @param table the hash table. * @param key the string to look up. * @returns the value of the hash entry. */ void* _dbus_hash_table_lookup_string (DBusHashTable *table, const char *key) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_STRING); entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); if (entry) return entry->value; else return NULL; } #ifdef DBUS_BUILD_TESTS /** * Looks up the value for a given string in a hash table * of type #DBUS_HASH_TWO_STRINGS. Returns %NULL if the value * is not present. (A not-present entry is indistinguishable * from an entry with a value of %NULL.) * @param table the hash table. * @param key the string to look up. * @returns the value of the hash entry. */ void* _dbus_hash_table_lookup_two_strings (DBusHashTable *table, const char *key) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); if (entry) return entry->value; else return NULL; } #endif /* DBUS_BUILD_TESTS */ /** * Looks up the value for a given integer in a hash table * of type #DBUS_HASH_INT. Returns %NULL if the value * is not present. (A not-present entry is indistinguishable * from an entry with a value of %NULL.) * @param table the hash table. * @param key the integer to look up. * @returns the value of the hash entry. */ void* _dbus_hash_table_lookup_int (DBusHashTable *table, int key) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_INT); entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); if (entry) return entry->value; else return NULL; } #ifdef DBUS_BUILD_TESTS /* disabled since it's only used for testing */ /** * Looks up the value for a given integer in a hash table * of type #DBUS_HASH_POINTER. Returns %NULL if the value * is not present. (A not-present entry is indistinguishable * from an entry with a value of %NULL.) * @param table the hash table. * @param key the integer to look up. * @returns the value of the hash entry. */ void* _dbus_hash_table_lookup_pointer (DBusHashTable *table, void *key) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_POINTER); entry = (* table->find_function) (table, key, FALSE, NULL, NULL); if (entry) return entry->value; else return NULL; } #endif /* DBUS_BUILD_TESTS */ /** * Looks up the value for a given integer in a hash table * of type #DBUS_HASH_ULONG. Returns %NULL if the value * is not present. (A not-present entry is indistinguishable * from an entry with a value of %NULL.) * @param table the hash table. * @param key the integer to look up. * @returns the value of the hash entry. */ void* _dbus_hash_table_lookup_ulong (DBusHashTable *table, unsigned long key) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_ULONG); entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); if (entry) return entry->value; else return NULL; } /** * Removes the hash entry for the given key. If no hash entry * for the key exists, does nothing. * * @param table the hash table. * @param key the hash key. * @returns #TRUE if the entry existed */ dbus_bool_t _dbus_hash_table_remove_string (DBusHashTable *table, const char *key) { DBusHashEntry *entry; DBusHashEntry **bucket; _dbus_assert (table->key_type == DBUS_HASH_STRING); entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); if (entry) { remove_entry (table, bucket, entry); return TRUE; } else return FALSE; } #ifdef DBUS_BUILD_TESTS /** * Removes the hash entry for the given key. If no hash entry * for the key exists, does nothing. * * @param table the hash table. * @param key the hash key. * @returns #TRUE if the entry existed */ dbus_bool_t _dbus_hash_table_remove_two_strings (DBusHashTable *table, const char *key) { DBusHashEntry *entry; DBusHashEntry **bucket; _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); if (entry) { remove_entry (table, bucket, entry); return TRUE; } else return FALSE; } #endif /* DBUS_BUILD_TESTS */ /** * Removes the hash entry for the given key. If no hash entry * for the key exists, does nothing. * * @param table the hash table. * @param key the hash key. * @returns #TRUE if the entry existed */ dbus_bool_t _dbus_hash_table_remove_int (DBusHashTable *table, int key) { DBusHashEntry *entry; DBusHashEntry **bucket; _dbus_assert (table->key_type == DBUS_HASH_INT); entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); if (entry) { remove_entry (table, bucket, entry); return TRUE; } else return FALSE; } #ifdef DBUS_BUILD_TESTS /* disabled since it's only used for testing */ /** * Removes the hash entry for the given key. If no hash entry * for the key exists, does nothing. * * @param table the hash table. * @param key the hash key. * @returns #TRUE if the entry existed */ dbus_bool_t _dbus_hash_table_remove_pointer (DBusHashTable *table, void *key) { DBusHashEntry *entry; DBusHashEntry **bucket; _dbus_assert (table->key_type == DBUS_HASH_POINTER); entry = (* table->find_function) (table, key, FALSE, &bucket, NULL); if (entry) { remove_entry (table, bucket, entry); return TRUE; } else return FALSE; } #endif /* DBUS_BUILD_TESTS */ /** * Removes the hash entry for the given key. If no hash entry * for the key exists, does nothing. * * @param table the hash table. * @param key the hash key. * @returns #TRUE if the entry existed */ dbus_bool_t _dbus_hash_table_remove_ulong (DBusHashTable *table, unsigned long key) { DBusHashEntry *entry; DBusHashEntry **bucket; _dbus_assert (table->key_type == DBUS_HASH_ULONG); entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); if (entry) { remove_entry (table, bucket, entry); return TRUE; } else return FALSE; } /** * Creates a hash entry with the given key and value. * The key and value are not copied; they are stored * in the hash table by reference. If an entry with the * given key already exists, the previous key and value * are overwritten (and freed if the hash table has * a key_free_function and/or value_free_function). * * Returns #FALSE if memory for the new hash entry * can't be allocated. * * @param table the hash table. * @param key the hash entry key. * @param value the hash entry value. */ dbus_bool_t _dbus_hash_table_insert_string (DBusHashTable *table, char *key, void *value) { DBusPreallocatedHash *preallocated; _dbus_assert (table->key_type == DBUS_HASH_STRING); preallocated = _dbus_hash_table_preallocate_entry (table); if (preallocated == NULL) return FALSE; _dbus_hash_table_insert_string_preallocated (table, preallocated, key, value); return TRUE; } #ifdef DBUS_BUILD_TESTS /** * Creates a hash entry with the given key and value. * The key and value are not copied; they are stored * in the hash table by reference. If an entry with the * given key already exists, the previous key and value * are overwritten (and freed if the hash table has * a key_free_function and/or value_free_function). * * Returns #FALSE if memory for the new hash entry * can't be allocated. * * @param table the hash table. * @param key the hash entry key. * @param value the hash entry value. */ dbus_bool_t _dbus_hash_table_insert_two_strings (DBusHashTable *table, char *key, void *value) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); entry = (* table->find_function) (table, key, TRUE, NULL, NULL); if (entry == NULL) return FALSE; /* no memory */ if (table->free_key_function && entry->key != key) (* table->free_key_function) (entry->key); if (table->free_value_function && entry->value != value) (* table->free_value_function) (entry->value); entry->key = key; entry->value = value; return TRUE; } #endif /* DBUS_BUILD_TESTS */ /** * Creates a hash entry with the given key and value. * The key and value are not copied; they are stored * in the hash table by reference. If an entry with the * given key already exists, the previous key and value * are overwritten (and freed if the hash table has * a key_free_function and/or value_free_function). * * Returns #FALSE if memory for the new hash entry * can't be allocated. * * @param table the hash table. * @param key the hash entry key. * @param value the hash entry value. */ dbus_bool_t _dbus_hash_table_insert_int (DBusHashTable *table, int key, void *value) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_INT); entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); if (entry == NULL) return FALSE; /* no memory */ if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) (* table->free_key_function) (entry->key); if (table->free_value_function && entry->value != value) (* table->free_value_function) (entry->value); entry->key = _DBUS_INT_TO_POINTER (key); entry->value = value; return TRUE; } #ifdef DBUS_BUILD_TESTS /* disabled since it's only used for testing */ /** * Creates a hash entry with the given key and value. * The key and value are not copied; they are stored * in the hash table by reference. If an entry with the * given key already exists, the previous key and value * are overwritten (and freed if the hash table has * a key_free_function and/or value_free_function). * * Returns #FALSE if memory for the new hash entry * can't be allocated. * * @param table the hash table. * @param key the hash entry key. * @param value the hash entry value. */ dbus_bool_t _dbus_hash_table_insert_pointer (DBusHashTable *table, void *key, void *value) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_POINTER); entry = (* table->find_function) (table, key, TRUE, NULL, NULL); if (entry == NULL) return FALSE; /* no memory */ if (table->free_key_function && entry->key != key) (* table->free_key_function) (entry->key); if (table->free_value_function && entry->value != value) (* table->free_value_function) (entry->value); entry->key = key; entry->value = value; return TRUE; } #endif /* DBUS_BUILD_TESTS */ /** * Creates a hash entry with the given key and value. * The key and value are not copied; they are stored * in the hash table by reference. If an entry with the * given key already exists, the previous key and value * are overwritten (and freed if the hash table has * a key_free_function and/or value_free_function). * * Returns #FALSE if memory for the new hash entry * can't be allocated. * * @param table the hash table. * @param key the hash entry key. * @param value the hash entry value. */ dbus_bool_t _dbus_hash_table_insert_ulong (DBusHashTable *table, unsigned long key, void *value) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_ULONG); entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); if (entry == NULL) return FALSE; /* no memory */ if (table->free_key_function && entry->key != (void*) key) (* table->free_key_function) (entry->key); if (table->free_value_function && entry->value != value) (* table->free_value_function) (entry->value); entry->key = (void*) key; entry->value = value; return TRUE; } /** * Preallocate an opaque data blob that allows us to insert into the * hash table at a later time without allocating any memory. * * @param table the hash table * @returns the preallocated data, or #NULL if no memory */ DBusPreallocatedHash* _dbus_hash_table_preallocate_entry (DBusHashTable *table) { DBusHashEntry *entry; entry = alloc_entry (table); return (DBusPreallocatedHash*) entry; } /** * Frees an opaque DBusPreallocatedHash that was *not* used * in order to insert into the hash table. * * @param table the hash table * @param preallocated the preallocated data */ void _dbus_hash_table_free_preallocated_entry (DBusHashTable *table, DBusPreallocatedHash *preallocated) { DBusHashEntry *entry; _dbus_assert (preallocated != NULL); entry = (DBusHashEntry*) preallocated; /* Don't use free_entry(), since this entry has no key/data */ _dbus_mem_pool_dealloc (table->entry_pool, entry); } /** * Inserts a string-keyed entry into the hash table, using a * preallocated data block from * _dbus_hash_table_preallocate_entry(). This function cannot fail due * to lack of memory. The DBusPreallocatedHash object is consumed and * should not be reused or freed. Otherwise this function works * just like _dbus_hash_table_insert_string(). * * @param table the hash table * @param preallocated the preallocated data * @param key the hash key * @param value the value */ void _dbus_hash_table_insert_string_preallocated (DBusHashTable *table, DBusPreallocatedHash *preallocated, char *key, void *value) { DBusHashEntry *entry; _dbus_assert (table->key_type == DBUS_HASH_STRING); _dbus_assert (preallocated != NULL); entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); _dbus_assert (entry != NULL); if (table->free_key_function && entry->key != key) (* table->free_key_function) (entry->key); if (table->free_value_function && entry->value != value) (* table->free_value_function) (entry->value); entry->key = key; entry->value = value; } /** * Gets the number of hash entries in a hash table. * * @param table the hash table. * @returns the number of entries in the table. */ int _dbus_hash_table_get_n_entries (DBusHashTable *table) { return table->n_entries; } /** @} */ #ifdef DBUS_BUILD_TESTS #include "dbus-test.h" #include /* If you're wondering why the hash table test takes * forever to run, it's because we call this function * in inner loops thus making things quadratic. */ static int count_entries (DBusHashTable *table) { DBusHashIter iter; int count; count = 0; _dbus_hash_iter_init (table, &iter); while (_dbus_hash_iter_next (&iter)) ++count; _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); return count; } /* Copy the foo\0bar\0 double string thing */ static char* _dbus_strdup2 (const char *str) { size_t len; char *copy; if (str == NULL) return NULL; len = strlen (str); len += strlen ((str + len + 1)); copy = dbus_malloc (len + 2); if (copy == NULL) return NULL; memcpy (copy, str, len + 2); return copy; } /** * @ingroup DBusHashTableInternals * Unit test for DBusHashTable * @returns #TRUE on success. */ dbus_bool_t _dbus_hash_test (void) { int i; DBusHashTable *table1; DBusHashTable *table2; DBusHashTable *table3; DBusHashTable *table4; DBusHashIter iter; #define N_HASH_KEYS 5000 char **keys; dbus_bool_t ret = FALSE; keys = dbus_new (char *, N_HASH_KEYS); if (keys == NULL) _dbus_assert_not_reached ("no memory"); for (i = 0; i < N_HASH_KEYS; i++) { keys[i] = dbus_malloc (128); if (keys[i] == NULL) _dbus_assert_not_reached ("no memory"); } printf ("Computing test hash keys...\n"); i = 0; while (i < N_HASH_KEYS) { int len; /* all the hash keys are TWO_STRINGS, but * then we can also use those as regular strings. */ len = sprintf (keys[i], "Hash key %d", i); sprintf (keys[i] + len + 1, "Two string %d", i); _dbus_assert (*(keys[i] + len) == '\0'); _dbus_assert (*(keys[i] + len + 1) != '\0'); ++i; } printf ("... done.\n"); table1 = _dbus_hash_table_new (DBUS_HASH_STRING, dbus_free, dbus_free); if (table1 == NULL) goto out; table2 = _dbus_hash_table_new (DBUS_HASH_INT, NULL, dbus_free); if (table2 == NULL) goto out; table3 = _dbus_hash_table_new (DBUS_HASH_ULONG, NULL, dbus_free); if (table3 == NULL) goto out; table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS, dbus_free, dbus_free); if (table4 == NULL) goto out; /* Insert and remove a bunch of stuff, counting the table in between * to be sure it's not broken and that iteration works */ i = 0; while (i < 3000) { void *value; char *key; key = _dbus_strdup (keys[i]); if (key == NULL) goto out; value = _dbus_strdup ("Value!"); if (value == NULL) goto out; if (!_dbus_hash_table_insert_string (table1, key, value)) goto out; value = _dbus_strdup (keys[i]); if (value == NULL) goto out; if (!_dbus_hash_table_insert_int (table2, i, value)) goto out; value = _dbus_strdup (keys[i]); if (value == NULL) goto out; if (!_dbus_hash_table_insert_ulong (table3, i, value)) goto out; key = _dbus_strdup2 (keys[i]); if (key == NULL) goto out; value = _dbus_strdup ("Value!"); if (value == NULL) goto out; if (!_dbus_hash_table_insert_two_strings (table4, key, value)) goto out; _dbus_assert (count_entries (table1) == i + 1); _dbus_assert (count_entries (table2) == i + 1); _dbus_assert (count_entries (table3) == i + 1); _dbus_assert (count_entries (table4) == i + 1); value = _dbus_hash_table_lookup_string (table1, keys[i]); _dbus_assert (value != NULL); _dbus_assert (strcmp (value, "Value!") == 0); value = _dbus_hash_table_lookup_int (table2, i); _dbus_assert (value != NULL); _dbus_assert (strcmp (value, keys[i]) == 0); value = _dbus_hash_table_lookup_ulong (table3, i); _dbus_assert (value != NULL); _dbus_assert (strcmp (value, keys[i]) == 0); value = _dbus_hash_table_lookup_two_strings (table4, keys[i]); _dbus_assert (value != NULL); _dbus_assert (strcmp (value, "Value!") == 0); ++i; } --i; while (i >= 0) { _dbus_hash_table_remove_string (table1, keys[i]); _dbus_hash_table_remove_int (table2, i); _dbus_hash_table_remove_ulong (table3, i); _dbus_hash_table_remove_two_strings (table4, keys[i]); _dbus_assert (count_entries (table1) == i); _dbus_assert (count_entries (table2) == i); _dbus_assert (count_entries (table3) == i); _dbus_assert (count_entries (table4) == i); --i; } _dbus_hash_table_ref (table1); _dbus_hash_table_ref (table2); _dbus_hash_table_ref (table3); _dbus_hash_table_ref (table4); _dbus_hash_table_unref (table1); _dbus_hash_table_unref (table2); _dbus_hash_table_unref (table3); _dbus_hash_table_unref (table4); _dbus_hash_table_unref (table1); _dbus_hash_table_unref (table2); _dbus_hash_table_unref (table3); _dbus_hash_table_unref (table4); table3 = NULL; /* Insert a bunch of stuff then check * that iteration works correctly (finds the right * values, iter_set_value works, etc.) */ table1 = _dbus_hash_table_new (DBUS_HASH_STRING, dbus_free, dbus_free); if (table1 == NULL) goto out; table2 = _dbus_hash_table_new (DBUS_HASH_INT, NULL, dbus_free); if (table2 == NULL) goto out; i = 0; while (i < 5000) { char *key; void *value; key = _dbus_strdup (keys[i]); if (key == NULL) goto out; value = _dbus_strdup ("Value!"); if (value == NULL) goto out; if (!_dbus_hash_table_insert_string (table1, key, value)) goto out; value = _dbus_strdup (keys[i]); if (value == NULL) goto out; if (!_dbus_hash_table_insert_int (table2, i, value)) goto out; _dbus_assert (count_entries (table1) == i + 1); _dbus_assert (count_entries (table2) == i + 1); ++i; } _dbus_hash_iter_init (table1, &iter); while (_dbus_hash_iter_next (&iter)) { const char *key; void *value; key = _dbus_hash_iter_get_string_key (&iter); value = _dbus_hash_iter_get_value (&iter); _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); value = _dbus_strdup ("Different value!"); if (value == NULL) goto out; _dbus_hash_iter_set_value (&iter, value); _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); } _dbus_hash_iter_init (table1, &iter); while (_dbus_hash_iter_next (&iter)) { _dbus_hash_iter_remove_entry (&iter); _dbus_assert (count_entries (table1) == i - 1); --i; } _dbus_hash_iter_init (table2, &iter); while (_dbus_hash_iter_next (&iter)) { int key; void *value; key = _dbus_hash_iter_get_int_key (&iter); value = _dbus_hash_iter_get_value (&iter); _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); value = _dbus_strdup ("Different value!"); if (value == NULL) goto out; _dbus_hash_iter_set_value (&iter, value); _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); } i = count_entries (table2); _dbus_hash_iter_init (table2, &iter); while (_dbus_hash_iter_next (&iter)) { _dbus_hash_iter_remove_entry (&iter); _dbus_assert (count_entries (table2) + 1 == i); --i; } /* add/remove interleaved, to check that we grow/shrink the table * appropriately */ i = 0; while (i < 1000) { char *key; void *value; key = _dbus_strdup (keys[i]); if (key == NULL) goto out; value = _dbus_strdup ("Value!"); if (value == NULL) goto out; if (!_dbus_hash_table_insert_string (table1, key, value)) goto out; ++i; } --i; while (i >= 0) { char *key; void *value; key = _dbus_strdup (keys[i]); if (key == NULL) goto out; value = _dbus_strdup ("Value!"); if (value == NULL) goto out; if (!_dbus_hash_table_remove_string (table1, keys[i])) goto out; if (!_dbus_hash_table_insert_string (table1, key, value)) goto out; if (!_dbus_hash_table_remove_string (table1, keys[i])) goto out; _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); --i; } /* nuke these tables */ _dbus_hash_table_unref (table1); _dbus_hash_table_unref (table2); /* Now do a bunch of things again using _dbus_hash_iter_lookup() to * be sure that interface works. */ table1 = _dbus_hash_table_new (DBUS_HASH_STRING, dbus_free, dbus_free); if (table1 == NULL) goto out; table2 = _dbus_hash_table_new (DBUS_HASH_INT, NULL, dbus_free); if (table2 == NULL) goto out; i = 0; while (i < 3000) { void *value; char *key; key = _dbus_strdup (keys[i]); if (key == NULL) goto out; value = _dbus_strdup ("Value!"); if (value == NULL) goto out; if (!_dbus_hash_iter_lookup (table1, key, TRUE, &iter)) goto out; _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); _dbus_hash_iter_set_value (&iter, value); value = _dbus_strdup (keys[i]); if (value == NULL) goto out; if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), TRUE, &iter)) goto out; _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); _dbus_hash_iter_set_value (&iter, value); _dbus_assert (count_entries (table1) == i + 1); _dbus_assert (count_entries (table2) == i + 1); if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) goto out; value = _dbus_hash_iter_get_value (&iter); _dbus_assert (value != NULL); _dbus_assert (strcmp (value, "Value!") == 0); /* Iterate just to be sure it works, though * it's a stupid thing to do */ while (_dbus_hash_iter_next (&iter)) ; if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) goto out; value = _dbus_hash_iter_get_value (&iter); _dbus_assert (value != NULL); _dbus_assert (strcmp (value, keys[i]) == 0); /* Iterate just to be sure it works, though * it's a stupid thing to do */ while (_dbus_hash_iter_next (&iter)) ; ++i; } --i; while (i >= 0) { if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) _dbus_assert_not_reached ("hash entry should have existed"); _dbus_hash_iter_remove_entry (&iter); if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) _dbus_assert_not_reached ("hash entry should have existed"); _dbus_hash_iter_remove_entry (&iter); _dbus_assert (count_entries (table1) == i); _dbus_assert (count_entries (table2) == i); --i; } _dbus_hash_table_unref (table1); _dbus_hash_table_unref (table2); ret = TRUE; out: for (i = 0; i < N_HASH_KEYS; i++) dbus_free (keys[i]); dbus_free (keys); return ret; } #endif /* DBUS_BUILD_TESTS */