dbus-hash.c
/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
/* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
*
* Copyright 1991-1993 The Regents of the University of California.
* Copyright 1994 Sun Microsystems, Inc.
* Copyright 2002-2005 Red Hat, Inc.
* Copyright 2003 Joe Shaw
* Copyright 2006 Sjoerd Simons
* Copyright 2010 Fridrich Štrba
* Copyright 2016 Ralf Habacker
* Copyright 2017 Endless Mobile, Inc.
* SPDX-License-Identifier: (AFL-2.1 OR GPL-2.0-or-later) AND TCL
*
* 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"
#include <dbus/dbus-test-tap.h>
#define REBUILD_MULTIPLIER 3
#define RANDOM_INDEX(table, i) \
(((((uintptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
#define DBUS_SMALL_HASH_TABLE 4
typedef struct DBusHashEntry DBusHashEntry;
struct DBusHashEntry
{
DBusHashEntry *next;
void *key;
void *value;
};
typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
void *key,
dbus_bool_t create_if_not_found,
DBusHashEntry ***bucket,
DBusPreallocatedHash *preallocated);
struct DBusHashTable {
int refcount;
DBusHashEntry **buckets;
DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
int n_buckets;
int n_entries;
int hi_rebuild_size;
int lo_rebuild_size;
int down_shift;
int mask;
DBusHashType key_type;
DBusFindEntryFunction find_function;
DBusFreeFunction free_key_function;
DBusFreeFunction free_value_function;
DBusMemPool *entry_pool;
};
typedef struct
{
DBusHashTable *table;
DBusHashEntry **bucket;
DBusHashEntry *entry;
DBusHashEntry *next_entry;
int next_bucket;
int n_entries_on_init;
} 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 dbus_bool_t 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);
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;
}
DBusHashTable *
_dbus_hash_table_ref (DBusHashTable *table)
{
table->refcount += 1;
return table;
}
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);
}
}
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);
}
void
_dbus_hash_iter_init (DBusHashTable *table,
DBusHashIter *iter)
{
DBusRealHashIter *real;
_DBUS_STATIC_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;
}
dbus_bool_t
_dbus_hash_iter_next (DBusHashIter *iter)
{
DBusRealHashIter *real;
_DBUS_STATIC_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;
}
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 */
}
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;
}
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;
}
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);
}
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;
}
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;
}
dbus_bool_t
_dbus_hash_iter_lookup (DBusHashTable *table,
void *key,
dbus_bool_t create_if_not_found,
DBusHashIter *iter)
{
DBusRealHashIter *real;
DBusHashEntry *entry = NULL;
DBusHashEntry **bucket = NULL;
_DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
real = (DBusRealHashIter*) iter;
entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
/* entry == NULL means not found, and either !create_if_not_found or OOM */
if (entry == NULL)
return FALSE;
_dbus_assert (bucket != NULL);
_dbus_assert (table->n_buckets >= 1);
_dbus_assert (bucket >= table->buckets);
_dbus_assert (bucket <= &table->buckets[table->n_buckets - 1]);
if (create_if_not_found)
{
if (table->free_key_function && entry->key != key)
(* table->free_key_function) (entry->key);
entry->key = key;
}
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 (real->next_bucket >= 0);
_dbus_assert (real->next_bucket <= table->n_buckets);
_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)
{
if (!rebuild_table (table))
return;
if (bucket)
{
/* Recalculate hash for the new table size */
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]);
}
}
}
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);
_dbus_assert (bucket == NULL || *bucket != NULL);
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;
}
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);
if (entry == NULL) /* OOM */
return NULL;
_dbus_assert (bucket == NULL || *bucket != NULL);
}
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);
}
/* Return FALSE if nothing happened. */
static dbus_bool_t
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 >= 2)
new_buckets = table->n_buckets * 4;
else
return FALSE; /* can't grow any more */
}
else
{
new_buckets = table->n_buckets / 4;
if (new_buckets < DBUS_SMALL_HASH_TABLE)
return FALSE; /* 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 FALSE;
}
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->down_shift >= 0);
_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);
return TRUE;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
DBusPreallocatedHash*
_dbus_hash_table_preallocate_entry (DBusHashTable *table)
{
DBusHashEntry *entry;
entry = alloc_entry (table);
return (DBusPreallocatedHash*) entry;
}
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);
}
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;
}
int
_dbus_hash_table_get_n_entries (DBusHashTable *table)
{
return table->n_entries;
}
dbus_bool_t
_dbus_hash_table_from_array (DBusHashTable *table, char **array, char delimiter)
{
DBusString key;
DBusString value;
int i;
dbus_bool_t retval = FALSE;
_dbus_assert (table != NULL);
_dbus_assert (array != NULL);
if (!_dbus_string_init (&key))
{
return FALSE;
}
if (!_dbus_string_init (&value))
{
_dbus_string_free (&key);
return FALSE;
}
for (i = 0; array[i] != NULL; i++)
{
if (!_dbus_string_append (&key, array[i]))
break;
if (_dbus_string_split_on_byte (&key, delimiter, &value))
{
char *hash_key, *hash_value;
if (!_dbus_string_steal_data (&key, &hash_key))
break;
if (!_dbus_string_steal_data (&value, &hash_value))
break;
if (!_dbus_hash_table_insert_string (table,
hash_key, hash_value))
break;
}
_dbus_string_set_length (&key, 0);
_dbus_string_set_length (&value, 0);
}
if (array[i] != NULL)
goto out;
retval = TRUE;
out:
_dbus_string_free (&key);
_dbus_string_free (&value);
return retval;
}
char **
_dbus_hash_table_to_array (DBusHashTable *table, char delimiter)
{
int i, length;
DBusString entry;
DBusHashIter iter;
char **array;
_dbus_assert (table != NULL);
length = _dbus_hash_table_get_n_entries (table);
array = dbus_new0 (char *, length + 1);
if (array == NULL)
return NULL;
i = 0;
_dbus_hash_iter_init (table, &iter);
if (!_dbus_string_init (&entry))
{
dbus_free_string_array (array);
return NULL;
}
while (_dbus_hash_iter_next (&iter))
{
const char *key, *value;
key = (const char *) _dbus_hash_iter_get_string_key (&iter);
value = (const char *) _dbus_hash_iter_get_value (&iter);
if (!_dbus_string_append_printf (&entry, "%s%c%s", key, delimiter, value))
break;
if (!_dbus_string_steal_data (&entry, array + i))
break;
i++;
}
_dbus_string_free (&entry);
if (i != length)
{
dbus_free_string_array (array);
array = NULL;
}
return array;
}
DBUS_SMALL_HASH_TABLE
#define DBUS_SMALL_HASH_TABLE
Initial number of buckets in hash table (hash table statically allocates its buckets for this size an...
Definition dbus-hash.c:137
REBUILD_MULTIPLIER
#define REBUILD_MULTIPLIER
When there are this many entries per bucket, on average, rebuild the hash table to make it larger.
Definition dbus-hash.c:111
RANDOM_INDEX
#define RANDOM_INDEX(table, i)
Takes a preliminary integer hash value and produces an index into a hash tables bucket list.
Definition dbus-hash.c:129
DBusFindEntryFunction
DBusHashEntry *(* DBusFindEntryFunction)(DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated)
Function used to find and optionally create a hash entry.
Definition dbus-hash.c:163
_dbus_hash_table_get_n_entries
int _dbus_hash_table_get_n_entries(DBusHashTable *table)
Gets the number of hash entries in a hash table.
Definition dbus-hash.c:1461
_dbus_hash_table_ref
DBusHashTable * _dbus_hash_table_ref(DBusHashTable *table)
Increments the reference count for a hash table.
Definition dbus-hash.c:354
_dbus_hash_table_remove_uintptr
dbus_bool_t _dbus_hash_table_remove_uintptr(DBusHashTable *table, uintptr_t key)
Removes the hash entry for the given key.
Definition dbus-hash.c:1243
_dbus_hash_iter_get_value
void * _dbus_hash_iter_get_value(DBusHashIter *iter)
Gets the value of the current entry.
Definition dbus-hash.c:620
DBusPreallocatedHash
struct DBusPreallocatedHash DBusPreallocatedHash
A preallocated hash entry.
Definition dbus-hash.h:150
_dbus_hash_table_insert_int
dbus_bool_t _dbus_hash_table_insert_int(DBusHashTable *table, int key, void *value)
Creates a hash entry with the given key and value.
Definition dbus-hash.c:1312
_dbus_hash_table_insert_string
dbus_bool_t _dbus_hash_table_insert_string(DBusHashTable *table, char *key, void *value)
Creates a hash entry with the given key and value.
Definition dbus-hash.c:1278
_dbus_hash_table_from_array
dbus_bool_t _dbus_hash_table_from_array(DBusHashTable *table, char **array, char delimiter)
Imports a string array into a hash table The hash table needs to be initialized with string keys,...
Definition dbus-hash.c:1479
_dbus_hash_iter_get_uintptr_key
uintptr_t _dbus_hash_iter_get_uintptr_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition dbus-hash.c:685
_dbus_hash_table_lookup_uintptr
void * _dbus_hash_table_lookup_uintptr(DBusHashTable *table, uintptr_t key)
Looks up the value for a given integer in a hash table of type DBUS_HASH_UINTPTR.
Definition dbus-hash.c:1163
_dbus_hash_table_unref
void _dbus_hash_table_unref(DBusHashTable *table)
Decrements the reference count for a hash table, freeing the hash table if the count reaches zero.
Definition dbus-hash.c:368
KeyCompareFunc
int(* KeyCompareFunc)(const void *key_a, const void *key_b)
Key comparison function.
Definition dbus-hash.c:895
_dbus_hash_iter_next
dbus_bool_t _dbus_hash_iter_next(DBusHashIter *iter)
Move the hash iterator forward one step, to the next hash entry.
Definition dbus-hash.c:550
_dbus_hash_iter_get_int_key
int _dbus_hash_iter_get_int_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition dbus-hash.c:666
_dbus_hash_iter_init
void _dbus_hash_iter_init(DBusHashTable *table, DBusHashIter *iter)
Initializes a hash table iterator.
Definition dbus-hash.c:524
_dbus_hash_table_free_preallocated_entry
void _dbus_hash_table_free_preallocated_entry(DBusHashTable *table, DBusPreallocatedHash *preallocated)
Frees an opaque DBusPreallocatedHash that was not used in order to insert into the hash table.
Definition dbus-hash.c:1403
_dbus_hash_table_new
DBusHashTable * _dbus_hash_table_new(DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function)
Constructs a new hash table.
Definition dbus-hash.c:292
_dbus_hash_table_remove_int
dbus_bool_t _dbus_hash_table_remove_int(DBusHashTable *table, int key)
Removes the hash entry for the given key.
Definition dbus-hash.c:1215
_dbus_hash_table_preallocate_entry
DBusPreallocatedHash * _dbus_hash_table_preallocate_entry(DBusHashTable *table)
Preallocate an opaque data blob that allows us to insert into the hash table at a later time without ...
Definition dbus-hash.c:1386
_dbus_hash_table_remove_string
dbus_bool_t _dbus_hash_table_remove_string(DBusHashTable *table, const char *key)
Removes the hash entry for the given key.
Definition dbus-hash.c:1187
_dbus_hash_table_to_array
char ** _dbus_hash_table_to_array(DBusHashTable *table, char delimiter)
Creates a string array from a hash table.
Definition dbus-hash.c:1544
_dbus_hash_iter_set_value
void _dbus_hash_iter_set_value(DBusHashIter *iter, void *value)
Sets the value of the current entry.
Definition dbus-hash.c:643
DBusHashType
DBusHashType
Indicates the type of a key in the hash table.
Definition dbus-hash.h:68
_dbus_hash_table_lookup_string
void * _dbus_hash_table_lookup_string(DBusHashTable *table, const char *key)
Looks up the value for a given string in a hash table of type DBUS_HASH_STRING.
Definition dbus-hash.c:1113
_dbus_hash_iter_lookup
dbus_bool_t _dbus_hash_iter_lookup(DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashIter *iter)
A low-level but efficient interface for manipulating the hash table.
Definition dbus-hash.c:748
_dbus_hash_table_remove_all
void _dbus_hash_table_remove_all(DBusHashTable *table)
Removed all entries from a hash table.
Definition dbus-hash.c:425
_dbus_hash_iter_get_string_key
const char * _dbus_hash_iter_get_string_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition dbus-hash.c:703
_dbus_hash_table_insert_uintptr
dbus_bool_t _dbus_hash_table_insert_uintptr(DBusHashTable *table, uintptr_t key, void *value)
Creates a hash entry with the given key and value.
Definition dbus-hash.c:1353
_dbus_hash_iter_remove_entry
void _dbus_hash_iter_remove_entry(DBusHashIter *iter)
Removes the current entry from the hash table.
Definition dbus-hash.c:599
_dbus_hash_table_insert_string_preallocated
void _dbus_hash_table_insert_string_preallocated(DBusHashTable *table, DBusPreallocatedHash *preallocated, char *key, void *value)
Inserts a string-keyed entry into the hash table, using a preallocated data block from _dbus_hash_tab...
Definition dbus-hash.c:1430
_dbus_hash_table_lookup_int
void * _dbus_hash_table_lookup_int(DBusHashTable *table, int key)
Looks up the value for a given integer in a hash table of type DBUS_HASH_INT.
Definition dbus-hash.c:1138
DBUS_HASH_INT
@ DBUS_HASH_INT
Hash keys are integers.
Definition dbus-hash.h:70
DBUS_HASH_UINTPTR
@ DBUS_HASH_UINTPTR
Hash keys are integer capable to hold a pointer.
Definition dbus-hash.h:71
DBUS_HASH_STRING
@ DBUS_HASH_STRING
Hash keys are strings.
Definition dbus-hash.h:69
_DBUS_INT_TO_POINTER
#define _DBUS_INT_TO_POINTER(integer)
Safely stuffs an integer into a pointer, to be extracted later with _DBUS_POINTER_TO_INT.
Definition dbus-internals.h:192
_dbus_assert_not_reached
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
Definition dbus-internals.h:164
_dbus_assert
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
Definition dbus-internals.h:153
_DBUS_INT_MAX
#define _DBUS_INT_MAX
Maximum value of type "int".
Definition dbus-internals.h:327
_DBUS_POINTER_TO_INT
#define _DBUS_POINTER_TO_INT(pointer)
Safely casts a void* to an integer; should only be used on void* that actually contain integers,...
Definition dbus-internals.h:191
_DBUS_N_ELEMENTS
#define _DBUS_N_ELEMENTS(array)
Computes the number of elements in a fixed-size array using sizeof().
Definition dbus-internals.h:189
NULL
#define NULL
A null pointer, defined appropriately for C or C++.
Definition dbus-macros.h:51
TRUE
#define TRUE
Expands to "1".
Definition dbus-macros.h:41
FALSE
#define FALSE
Expands to "0".
Definition dbus-macros.h:44
_dbus_mem_pool_alloc
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition dbus-mempool.c:227
_dbus_mem_pool_dealloc
dbus_bool_t _dbus_mem_pool_dealloc(DBusMemPool *pool, void *element)
Deallocates an object previously created with _dbus_mem_pool_alloc().
Definition dbus-mempool.c:366
_dbus_mem_pool_free
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition dbus-mempool.c:200
_dbus_mem_pool_new
DBusMemPool * _dbus_mem_pool_new(int element_size, dbus_bool_t zero_elements)
Creates a new memory pool, or returns NULL on failure.
Definition dbus-mempool.c:148
dbus_free
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
Definition dbus-memory.c:710
DBusFreeFunction
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
Definition dbus-memory.h:65
dbus_new0
#define dbus_new0(type, count)
Safe macro for using dbus_malloc0().
Definition dbus-memory.h:60
dbus_free_string_array
void dbus_free_string_array(char **str_array)
Frees a NULL-terminated array of strings.
Definition dbus-memory.c:758
_dbus_string_set_length
dbus_bool_t _dbus_string_set_length(DBusString *str, int length)
Sets the length of a string.
Definition dbus-string.c:847
_dbus_string_append
dbus_bool_t _dbus_string_append(DBusString *str, const char *buffer)
Appends a nul-terminated C-style string to a DBusString.
Definition dbus-string.c:980
_dbus_string_init
dbus_bool_t _dbus_string_init(DBusString *str)
Initializes a string.
Definition dbus-string.c:182
_dbus_string_steal_data
dbus_bool_t _dbus_string_steal_data(DBusString *str, char **data_return)
Like _dbus_string_get_data(), but removes the gotten data from the original string.
Definition dbus-string.c:686
_dbus_string_split_on_byte
dbus_bool_t _dbus_string_split_on_byte(DBusString *source, unsigned char byte, DBusString *tail)
Looks for the first occurance of a byte, deletes that byte, and moves everything after the byte to th...
Definition dbus-string.c:1529
_dbus_string_free
void _dbus_string_free(DBusString *str)
Frees a string created by _dbus_string_init(), and fills it with the same contents as _DBUS_STRING_IN...
Definition dbus-string.c:278
_dbus_string_append_printf
dbus_bool_t _dbus_string_append_printf(DBusString *str, const char *format,...)
Appends a printf-style formatted string to the DBusString.
Definition dbus-string.c:1147
dbus_bool_t
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition dbus-types.h:37
DBusHashEntry
Internal representation of a hash entry.
Definition dbus-hash.c:151
DBusHashEntry::value
void * value
Hash value.
Definition dbus-hash.c:157
DBusHashEntry::next
DBusHashEntry * next
Pointer to next entry in this hash bucket, or NULL for end of chain.
Definition dbus-hash.c:152
DBusHashEntry::key
void * key
Hash key.
Definition dbus-hash.c:156
DBusHashIter
Hash iterator object.
Definition dbus-hash.h:50
DBusHashTable
Internals of DBusHashTable.
Definition dbus-hash.c:175
DBusHashTable::buckets
DBusHashEntry ** buckets
Pointer to bucket array.
Definition dbus-hash.c:178
DBusHashTable::key_type
DBusHashType key_type
Type of keys used in this table.
Definition dbus-hash.c:205
DBusHashTable::hi_rebuild_size
int hi_rebuild_size
Enlarge table when n_entries gets to be this large.
Definition dbus-hash.c:192
DBusHashTable::n_buckets
int n_buckets
Total number of buckets allocated at **buckets.
Definition dbus-hash.c:186
DBusHashTable::down_shift
int down_shift
Shift count used in hashing function.
Definition dbus-hash.c:198
DBusHashTable::free_key_function
DBusFreeFunction free_key_function
Function to free keys.
Definition dbus-hash.c:210
DBusHashTable::lo_rebuild_size
int lo_rebuild_size
Shrink table when n_entries gets below this.
Definition dbus-hash.c:195
DBusHashTable::find_function
DBusFindEntryFunction find_function
Function for finding entries.
Definition dbus-hash.c:208
DBusHashTable::refcount
int refcount
Reference count.
Definition dbus-hash.c:176
DBusHashTable::entry_pool
DBusMemPool * entry_pool
Memory pool for hash entries.
Definition dbus-hash.c:213
DBusHashTable::mask
int mask
Mask value used in hashing function.
Definition dbus-hash.c:202
DBusHashTable::static_buckets
DBusHashEntry * static_buckets[DBUS_SMALL_HASH_TABLE]
Bucket array used for small tables (to avoid mallocs and frees).
Definition dbus-hash.c:182
DBusHashTable::free_value_function
DBusFreeFunction free_value_function
Function to free values.
Definition dbus-hash.c:211
DBusHashTable::n_entries
int n_entries
Total number of entries present in table.
Definition dbus-hash.c:189
DBusMemPool
Internals fields of DBusMemPool.
Definition dbus-mempool.c:109
DBusRealHashIter
Internals of DBusHashIter.
Definition dbus-hash.c:220
DBusRealHashIter::table
DBusHashTable * table
Pointer to table containing entry.
Definition dbus-hash.c:221
DBusRealHashIter::next_entry
DBusHashEntry * next_entry
Next entry to be iterated onto in current bucket.
Definition dbus-hash.c:227
DBusRealHashIter::entry
DBusHashEntry * entry
Current hash entry.
Definition dbus-hash.c:226
DBusRealHashIter::n_entries_on_init
int n_entries_on_init
used to detect table resize since initialization
Definition dbus-hash.c:229
DBusRealHashIter::bucket
DBusHashEntry ** bucket
Pointer to bucket that points to first entry in this entry's chain: used for deleting the entry.
Definition dbus-hash.c:222
DBusRealHashIter::next_bucket
int next_bucket
index of next bucket
Definition dbus-hash.c:228
DBusString
Definition dbus-string.h:47