/*
|
* ghashtable.c: Hashtable implementation
|
*
|
* Author:
|
* Miguel de Icaza (miguel@novell.com)
|
*
|
* (C) 2006 Novell, Inc.
|
*
|
* Permission is hereby granted, free of charge, to any person obtaining
|
* a copy of this software and associated documentation files (the
|
* "Software"), to deal in the Software without restriction, including
|
* without limitation the rights to use, copy, modify, merge, publish,
|
* distribute, sublicense, and/or sell copies of the Software, and to
|
* permit persons to whom the Software is furnished to do so, subject to
|
* the following conditions:
|
*
|
* The above copyright notice and this permission notice shall be
|
* included in all copies or substantial portions of the Software.
|
*
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
|
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
|
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
|
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
|
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
*/
|
#include <stdio.h>
|
#include <math.h>
|
#include <glib.h>
|
|
typedef struct _Slot Slot;
|
|
struct _Slot {
|
gpointer key;
|
gpointer value;
|
Slot *next;
|
};
|
|
static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
|
|
struct _GHashTable {
|
GHashFunc hash_func;
|
GEqualFunc key_equal_func;
|
|
Slot **table;
|
int table_size;
|
int in_use;
|
int threshold;
|
int last_rehash;
|
GDestroyNotify value_destroy_func, key_destroy_func;
|
};
|
|
typedef struct {
|
GHashTable *ht;
|
int slot_index;
|
Slot *slot;
|
} Iter;
|
|
static const guint prime_tbl[] = {
|
11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
|
1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
|
47431, 71143, 106721, 160073, 240101, 360163,
|
540217, 810343, 1215497, 1823231, 2734867, 4102283,
|
6153409, 9230113, 13845163
|
};
|
|
static gboolean
|
test_prime (int x)
|
{
|
if ((x & 1) != 0) {
|
int n;
|
for (n = 3; n< (int)sqrt (x); n += 2) {
|
if ((x % n) == 0)
|
return FALSE;
|
}
|
return TRUE;
|
}
|
// There is only one even prime - 2.
|
return (x == 2);
|
}
|
|
static int
|
calc_prime (int x)
|
{
|
int i;
|
|
for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
|
if (test_prime (i))
|
return i;
|
}
|
return x;
|
}
|
|
guint
|
g_spaced_primes_closest (guint x)
|
{
|
int i;
|
|
for (i = 0; i < G_N_ELEMENTS (prime_tbl); i++) {
|
if (x <= prime_tbl [i])
|
return prime_tbl [i];
|
}
|
return calc_prime (x);
|
}
|
|
GHashTable *
|
g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
|
{
|
GHashTable *hash;
|
|
if (hash_func == NULL)
|
hash_func = g_direct_hash;
|
if (key_equal_func == NULL)
|
key_equal_func = g_direct_equal;
|
hash = g_new0 (GHashTable, 1);
|
|
hash->hash_func = hash_func;
|
hash->key_equal_func = key_equal_func;
|
|
hash->table_size = g_spaced_primes_closest (1);
|
hash->table = g_new0 (Slot *, hash->table_size);
|
hash->last_rehash = hash->table_size;
|
|
return hash;
|
}
|
|
GHashTable *
|
g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
|
GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
|
{
|
GHashTable *hash = g_hash_table_new (hash_func, key_equal_func);
|
if (hash == NULL)
|
return NULL;
|
|
hash->key_destroy_func = key_destroy_func;
|
hash->value_destroy_func = value_destroy_func;
|
|
return hash;
|
}
|
|
#if 0
|
static void
|
dump_hash_table (GHashTable *hash)
|
{
|
int i;
|
|
for (i = 0; i < hash->table_size; i++) {
|
Slot *s;
|
|
for (s = hash->table [i]; s != NULL; s = s->next){
|
guint hashcode = (*hash->hash_func) (s->key);
|
guint slot = (hashcode) % hash->table_size;
|
printf ("key %p hash %x on slot %d correct slot %d tb size %d\n", s->key, hashcode, i, slot, hash->table_size);
|
}
|
}
|
}
|
#endif
|
|
#ifdef SANITY_CHECK
|
static void
|
sanity_check (GHashTable *hash)
|
{
|
int i;
|
|
for (i = 0; i < hash->table_size; i++) {
|
Slot *s;
|
|
for (s = hash->table [i]; s != NULL; s = s->next){
|
guint hashcode = (*hash->hash_func) (s->key);
|
guint slot = (hashcode) % hash->table_size;
|
if (slot != i) {
|
dump_hashcode_func = 1;
|
hashcode = (*hash->hash_func) (s->key);
|
dump_hashcode_func = 0;
|
g_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
|
}
|
}
|
}
|
}
|
#else
|
|
#define sanity_check(HASH) do {}while(0)
|
|
#endif
|
|
static void
|
do_rehash (GHashTable *hash)
|
{
|
int current_size, i;
|
Slot **table;
|
|
/* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
|
hash->last_rehash = hash->table_size;
|
current_size = hash->table_size;
|
hash->table_size = g_spaced_primes_closest (hash->in_use);
|
/* printf ("New size: %d\n", hash->table_size); */
|
table = hash->table;
|
hash->table = g_new0 (Slot *, hash->table_size);
|
|
for (i = 0; i < current_size; i++){
|
Slot *s, *next;
|
|
for (s = table [i]; s != NULL; s = next){
|
guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
|
next = s->next;
|
|
s->next = hash->table [hashcode];
|
hash->table [hashcode] = s;
|
}
|
}
|
g_free (table);
|
}
|
|
static void
|
rehash (GHashTable *hash)
|
{
|
int diff = ABS (hash->last_rehash - hash->in_use);
|
|
/* These are the factors to play with to change the rehashing strategy */
|
/* I played with them with a large range, and could not really get */
|
/* something that was too good, maybe the tests are not that great */
|
if (!(diff * 0.75 > hash->table_size * 2))
|
return;
|
do_rehash (hash);
|
sanity_check (hash);
|
}
|
|
void
|
g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
|
{
|
guint hashcode;
|
Slot *s;
|
GEqualFunc equal;
|
|
g_return_if_fail (hash != NULL);
|
sanity_check (hash);
|
|
equal = hash->key_equal_func;
|
if (hash->in_use >= hash->threshold)
|
rehash (hash);
|
|
hashcode = ((*hash->hash_func) (key)) % hash->table_size;
|
for (s = hash->table [hashcode]; s != NULL; s = s->next){
|
if ((*equal) (s->key, key)){
|
if (replace){
|
if (hash->key_destroy_func != NULL)
|
(*hash->key_destroy_func)(s->key);
|
s->key = key;
|
}
|
if (hash->value_destroy_func != NULL)
|
(*hash->value_destroy_func) (s->value);
|
s->value = value;
|
sanity_check (hash);
|
return;
|
}
|
}
|
s = g_new (Slot, 1);
|
s->key = key;
|
s->value = value;
|
s->next = hash->table [hashcode];
|
hash->table [hashcode] = s;
|
hash->in_use++;
|
sanity_check (hash);
|
}
|
|
GList*
|
g_hash_table_get_keys (GHashTable *hash)
|
{
|
GHashTableIter iter;
|
GList *rv = NULL;
|
gpointer key;
|
|
g_hash_table_iter_init (&iter, hash);
|
|
while (g_hash_table_iter_next (&iter, &key, NULL))
|
rv = g_list_prepend (rv, key);
|
|
return g_list_reverse (rv);
|
}
|
|
GList*
|
g_hash_table_get_values (GHashTable *hash)
|
{
|
GHashTableIter iter;
|
GList *rv = NULL;
|
gpointer value;
|
|
g_hash_table_iter_init (&iter, hash);
|
|
while (g_hash_table_iter_next (&iter, NULL, &value))
|
rv = g_list_prepend (rv, value);
|
|
return g_list_reverse (rv);
|
}
|
|
|
guint
|
g_hash_table_size (GHashTable *hash)
|
{
|
g_return_val_if_fail (hash != NULL, 0);
|
|
return hash->in_use;
|
}
|
|
gpointer
|
g_hash_table_lookup (GHashTable *hash, gconstpointer key)
|
{
|
gpointer orig_key, value;
|
|
if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
|
return value;
|
else
|
return NULL;
|
}
|
|
gboolean
|
g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
|
{
|
GEqualFunc equal;
|
Slot *s;
|
guint hashcode;
|
|
g_return_val_if_fail (hash != NULL, FALSE);
|
sanity_check (hash);
|
equal = hash->key_equal_func;
|
|
hashcode = ((*hash->hash_func) (key)) % hash->table_size;
|
|
for (s = hash->table [hashcode]; s != NULL; s = s->next){
|
if ((*equal)(s->key, key)){
|
if (orig_key)
|
*orig_key = s->key;
|
if (value)
|
*value = s->value;
|
return TRUE;
|
}
|
}
|
return FALSE;
|
}
|
|
void
|
g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
|
{
|
int i;
|
|
g_return_if_fail (hash != NULL);
|
g_return_if_fail (func != NULL);
|
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s;
|
|
for (s = hash->table [i]; s != NULL; s = s->next)
|
(*func)(s->key, s->value, user_data);
|
}
|
}
|
|
gpointer
|
g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
|
{
|
int i;
|
|
g_return_val_if_fail (hash != NULL, NULL);
|
g_return_val_if_fail (predicate != NULL, NULL);
|
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s;
|
|
for (s = hash->table [i]; s != NULL; s = s->next)
|
if ((*predicate)(s->key, s->value, user_data))
|
return s->value;
|
}
|
return NULL;
|
}
|
|
void
|
g_hash_table_remove_all (GHashTable *hash)
|
{
|
int i;
|
|
g_return_if_fail (hash != NULL);
|
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s;
|
|
while (hash->table [i]) {
|
s = hash->table [i];
|
g_hash_table_remove (hash, s->key);
|
}
|
}
|
}
|
|
gboolean
|
g_hash_table_remove (GHashTable *hash, gconstpointer key)
|
{
|
GEqualFunc equal;
|
Slot *s, *last;
|
guint hashcode;
|
|
g_return_val_if_fail (hash != NULL, FALSE);
|
sanity_check (hash);
|
equal = hash->key_equal_func;
|
|
hashcode = ((*hash->hash_func)(key)) % hash->table_size;
|
last = NULL;
|
for (s = hash->table [hashcode]; s != NULL; s = s->next){
|
if ((*equal)(s->key, key)){
|
if (hash->key_destroy_func != NULL)
|
(*hash->key_destroy_func)(s->key);
|
if (hash->value_destroy_func != NULL)
|
(*hash->value_destroy_func)(s->value);
|
if (last == NULL)
|
hash->table [hashcode] = s->next;
|
else
|
last->next = s->next;
|
g_free (s);
|
hash->in_use--;
|
sanity_check (hash);
|
return TRUE;
|
}
|
last = s;
|
}
|
sanity_check (hash);
|
return FALSE;
|
}
|
|
guint
|
g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
|
{
|
int i;
|
int count = 0;
|
|
g_return_val_if_fail (hash != NULL, 0);
|
g_return_val_if_fail (func != NULL, 0);
|
|
sanity_check (hash);
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s, *last;
|
|
last = NULL;
|
for (s = hash->table [i]; s != NULL; ){
|
if ((*func)(s->key, s->value, user_data)){
|
Slot *n;
|
|
if (hash->key_destroy_func != NULL)
|
(*hash->key_destroy_func)(s->key);
|
if (hash->value_destroy_func != NULL)
|
(*hash->value_destroy_func)(s->value);
|
if (last == NULL){
|
hash->table [i] = s->next;
|
n = s->next;
|
} else {
|
last->next = s->next;
|
n = last->next;
|
}
|
g_free (s);
|
hash->in_use--;
|
count++;
|
s = n;
|
} else {
|
last = s;
|
s = s->next;
|
}
|
}
|
}
|
sanity_check (hash);
|
if (count > 0)
|
rehash (hash);
|
return count;
|
}
|
|
gboolean
|
g_hash_table_steal (GHashTable *hash, gconstpointer key)
|
{
|
GEqualFunc equal;
|
Slot *s, *last;
|
guint hashcode;
|
|
g_return_val_if_fail (hash != NULL, FALSE);
|
sanity_check (hash);
|
equal = hash->key_equal_func;
|
|
hashcode = ((*hash->hash_func)(key)) % hash->table_size;
|
last = NULL;
|
for (s = hash->table [hashcode]; s != NULL; s = s->next){
|
if ((*equal)(s->key, key)) {
|
if (last == NULL)
|
hash->table [hashcode] = s->next;
|
else
|
last->next = s->next;
|
g_free (s);
|
hash->in_use--;
|
sanity_check (hash);
|
return TRUE;
|
}
|
last = s;
|
}
|
sanity_check (hash);
|
return FALSE;
|
|
}
|
|
guint
|
g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
|
{
|
int i;
|
int count = 0;
|
|
g_return_val_if_fail (hash != NULL, 0);
|
g_return_val_if_fail (func != NULL, 0);
|
|
sanity_check (hash);
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s, *last;
|
|
last = NULL;
|
for (s = hash->table [i]; s != NULL; ){
|
if ((*func)(s->key, s->value, user_data)){
|
Slot *n;
|
|
if (last == NULL){
|
hash->table [i] = s->next;
|
n = s->next;
|
} else {
|
last->next = s->next;
|
n = last->next;
|
}
|
g_free (s);
|
hash->in_use--;
|
count++;
|
s = n;
|
} else {
|
last = s;
|
s = s->next;
|
}
|
}
|
}
|
sanity_check (hash);
|
if (count > 0)
|
rehash (hash);
|
return count;
|
}
|
|
void
|
g_hash_table_destroy (GHashTable *hash)
|
{
|
int i;
|
|
g_return_if_fail (hash != NULL);
|
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s, *next;
|
|
for (s = hash->table [i]; s != NULL; s = next){
|
next = s->next;
|
|
if (hash->key_destroy_func != NULL)
|
(*hash->key_destroy_func)(s->key);
|
if (hash->value_destroy_func != NULL)
|
(*hash->value_destroy_func)(s->value);
|
g_free (s);
|
}
|
}
|
g_free (hash->table);
|
|
g_free (hash);
|
}
|
|
void
|
g_hash_table_print_stats (GHashTable *table)
|
{
|
int i, max_chain_index, chain_size, max_chain_size;
|
Slot *node;
|
|
max_chain_size = 0;
|
max_chain_index = -1;
|
for (i = 0; i < table->table_size; i++) {
|
chain_size = 0;
|
for (node = table->table [i]; node; node = node->next)
|
chain_size ++;
|
if (chain_size > max_chain_size) {
|
max_chain_size = chain_size;
|
max_chain_index = i;
|
}
|
}
|
|
printf ("Size: %d Table Size: %d Max Chain Length: %d at %d\n", table->in_use, table->table_size, max_chain_size, max_chain_index);
|
}
|
|
void
|
g_hash_table_iter_init (GHashTableIter *it, GHashTable *hash_table)
|
{
|
Iter *iter = (Iter*)it;
|
|
memset (iter, 0, sizeof (Iter));
|
iter->ht = hash_table;
|
iter->slot_index = -1;
|
}
|
|
gboolean g_hash_table_iter_next (GHashTableIter *it, gpointer *key, gpointer *value)
|
{
|
Iter *iter = (Iter*)it;
|
|
GHashTable *hash = iter->ht;
|
|
g_assert (iter->slot_index != -2);
|
g_assert (sizeof (Iter) <= sizeof (GHashTableIter));
|
|
if (!iter->slot) {
|
while (TRUE) {
|
iter->slot_index ++;
|
if (iter->slot_index >= hash->table_size) {
|
iter->slot_index = -2;
|
return FALSE;
|
}
|
if (hash->table [iter->slot_index])
|
break;
|
}
|
iter->slot = hash->table [iter->slot_index];
|
}
|
|
if (key)
|
*key = iter->slot->key;
|
if (value)
|
*value = iter->slot->value;
|
iter->slot = iter->slot->next;
|
|
return TRUE;
|
}
|
|
gboolean
|
g_direct_equal (gconstpointer v1, gconstpointer v2)
|
{
|
return v1 == v2;
|
}
|
|
guint
|
g_direct_hash (gconstpointer v1)
|
{
|
return GPOINTER_TO_UINT (v1);
|
}
|
|
gboolean
|
g_int_equal (gconstpointer v1, gconstpointer v2)
|
{
|
return *(gint *)v1 == *(gint *)v2;
|
}
|
|
guint
|
g_int_hash (gconstpointer v1)
|
{
|
return *(guint *)v1;
|
}
|
|
gboolean
|
g_str_equal (gconstpointer v1, gconstpointer v2)
|
{
|
return strcmp (v1, v2) == 0;
|
}
|
|
guint
|
g_str_hash (gconstpointer v1)
|
{
|
guint hash = 0;
|
char *p = (char *) v1;
|
|
while (*p++)
|
hash = (hash << 5) - (hash + *p);
|
|
return hash;
|
}
|
