diff options
Diffstat (limited to 'src/3rd_party/dbus-1.7.8/dbus/dbus-hash.c')
| -rw-r--r-- | src/3rd_party/dbus-1.7.8/dbus/dbus-hash.c | 1831 |
1 files changed, 0 insertions, 1831 deletions
diff --git a/src/3rd_party/dbus-1.7.8/dbus/dbus-hash.c b/src/3rd_party/dbus-1.7.8/dbus/dbus-hash.c deleted file mode 100644 index c80835aaaf..0000000000 --- a/src/3rd_party/dbus-1.7.8/dbus/dbus-hash.c +++ /dev/null @@ -1,1831 +0,0 @@ -/* -*- 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; - -_DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter)); - -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); -static unsigned int string_hash (const char *str); -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_UINTPTR: - table->find_function = find_direct_function; - break; - case DBUS_HASH_STRING: - table->find_function = find_string_function; - 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; -} - -/** - * 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; -} - -/** 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); -} - -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_INT: - case DBUS_HASH_UINTPTR: - 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; -} - -/** - * 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; -} - -/** - * 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; -} - -/** - * 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; -} - -/** - * 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; -} - -/** - * 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; -} - -/** - * 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_ENABLE_EMBEDDED_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; -} - -/** - * @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; - 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; - - len = sprintf (keys[i], "Hash key %d", i); - _dbus_assert (*(keys[i] + len) == '\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; - - /* 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; - - _dbus_assert (count_entries (table1) == i + 1); - _dbus_assert (count_entries (table2) == i + 1); - _dbus_assert (count_entries (table3) == 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); - - ++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_assert (count_entries (table1) == i); - _dbus_assert (count_entries (table2) == i); - _dbus_assert (count_entries (table3) == i); - - --i; - } - - _dbus_hash_table_ref (table1); - _dbus_hash_table_ref (table2); - _dbus_hash_table_ref (table3); - _dbus_hash_table_unref (table1); - _dbus_hash_table_unref (table2); - _dbus_hash_table_unref (table3); - _dbus_hash_table_unref (table1); - _dbus_hash_table_unref (table2); - _dbus_hash_table_unref (table3); - 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_ENABLE_EMBEDDED_TESTS */ |