| /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ |
| /* 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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 <config.h> |
| #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) \ |
| (((((intptr_t) (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_UINTPTR: |
| 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); |
| } |
| } |
| |
| /** |
| * Removed all entries from a hash table. |
| * |
| * @param table the hash table to remove all entries from. |
| */ |
| void |
| _dbus_hash_table_remove_all (DBusHashTable *table) |
| { |
| DBusHashIter iter; |
| _dbus_hash_iter_init (table, &iter); |
| while (_dbus_hash_iter_next (&iter)) |
| { |
| _dbus_hash_iter_remove_entry(&iter); |
| } |
| } |
| |
| 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_UINTPTR. |
| * |
| * @param iter the hash table iterator. |
| */ |
| uintptr_t |
| _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter) |
| { |
| DBusRealHashIter *real; |
| |
| real = (DBusRealHashIter*) iter; |
| |
| _dbus_assert (real->table != NULL); |
| _dbus_assert (real->entry != NULL); |
| |
| return (uintptr_t) 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_UINTPTR: |
| 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_UINTPTR. 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_uintptr (DBusHashTable *table, |
| uintptr_t key) |
| { |
| DBusHashEntry *entry; |
| |
| _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); |
| |
| 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_uintptr (DBusHashTable *table, |
| uintptr_t key) |
| { |
| DBusHashEntry *entry; |
| DBusHashEntry **bucket; |
| |
| _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); |
| |
| 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_uintptr (DBusHashTable *table, |
| uintptr_t key, |
| void *value) |
| { |
| DBusHashEntry *entry; |
| |
| _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); |
| |
| 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 <stdio.h> |
| |
| /* 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_UINTPTR, |
| 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_uintptr (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_uintptr (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_uintptr (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 */ |