/**
|
* \file
|
* A hash table which only stores values in the hash nodes.
|
*
|
* Author:
|
* Miguel de Icaza (miguel@novell.com)
|
* Zoltan Varga (vargaz@gmail.com)
|
*
|
* (C) 2006,2008 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>
|
|
#include "mono-value-hash.h"
|
|
#ifndef G_MAXINT32
|
#define G_MAXINT32 2147483647
|
#endif
|
|
/*
|
* This code is based on eglib/ghashtable.c with work done by Hans Petter Jansson
|
* (hpj@novell.com) to make it use internal probing instead of chaining.
|
*/
|
|
#define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */
|
|
typedef struct _Slot Slot;
|
|
#define GET_VALUE(slot) ((gpointer)((((gsize)((slot)->value)) >> 2) << 2))
|
|
#define SET_VALUE(slot,value) ((slot)->value = (value))
|
|
#define IS_EMPTY(slot) ((gsize)((slot)->value) == 0)
|
#define IS_TOMBSTONE(slot) ((gsize)((slot)->value) & 1)
|
|
#define MAKE_TOMBSTONE(slot) do { (slot)->value = (gpointer)((gsize)((slot)->value) | 1); } while (1)
|
|
#define HASH(table, key) ((table)->hash_func ((key)))
|
|
struct _Slot {
|
/* A NULL value means the slot is empty */
|
/* The tombstone status is stored in the lowest order bit of the value. */
|
gpointer value;
|
};
|
|
static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
|
|
struct _MonoValueHashTable {
|
GHashFunc hash_func;
|
GEqualFunc key_equal_func;
|
MonoValueHashKeyExtractFunc key_extract_func;
|
|
Slot *table;
|
int table_size;
|
int table_mask;
|
int in_use;
|
int n_occupied;
|
GDestroyNotify value_destroy_func, key_destroy_func;
|
};
|
|
static void
|
mono_value_hash_table_set_shift (MonoValueHashTable *hash_table, gint shift)
|
{
|
gint i;
|
guint mask = 0;
|
|
hash_table->table_size = 1 << shift;
|
|
for (i = 0; i < shift; i++) {
|
mask <<= 1;
|
mask |= 1;
|
}
|
|
hash_table->table_mask = mask;
|
}
|
|
static gint
|
mono_value_hash_table_find_closest_shift (gint n)
|
{
|
gint i;
|
|
for (i = 0; n; i++)
|
n >>= 1;
|
|
return i;
|
}
|
|
static void
|
mono_value_hash_table_set_shift_from_size (MonoValueHashTable *hash_table, gint size)
|
{
|
gint shift;
|
|
shift = mono_value_hash_table_find_closest_shift (size);
|
shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
|
|
mono_value_hash_table_set_shift (hash_table, shift);
|
}
|
|
MonoValueHashTable *
|
mono_value_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func, MonoValueHashKeyExtractFunc key_extract)
|
{
|
MonoValueHashTable *hash;
|
|
if (hash_func == NULL)
|
hash_func = g_direct_hash;
|
if (key_equal_func == NULL)
|
key_equal_func = g_direct_equal;
|
hash = g_new0 (MonoValueHashTable, 1);
|
|
hash->hash_func = hash_func;
|
hash->key_equal_func = key_equal_func;
|
hash->key_extract_func = key_extract;
|
|
mono_value_hash_table_set_shift (hash, HASH_TABLE_MIN_SHIFT);
|
hash->table = g_new0 (Slot, hash->table_size);
|
|
return hash;
|
}
|
|
#if 0
|
|
MonoValueHashTable *
|
mono_value_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
|
GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
|
{
|
MonoValueHashTable *hash = mono_value_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;
|
}
|
|
#endif
|
|
static void
|
do_rehash (MonoValueHashTable *hash)
|
{
|
int i;
|
int old_size;
|
Slot *old_table;
|
|
old_size = hash->table_size;
|
old_table = hash->table;
|
|
mono_value_hash_table_set_shift_from_size (hash, hash->in_use * 2);
|
|
/* printf ("New size: %d\n", hash->table_size); */
|
hash->table = g_new0 (Slot, hash->table_size);
|
|
for (i = 0; i < old_size; i++){
|
Slot *s = &old_table [i];
|
Slot *new_s;
|
guint hash_val;
|
guint step = 0;
|
gpointer s_value, s_key;
|
|
if (IS_EMPTY (s) || IS_TOMBSTONE (s))
|
continue;
|
|
s_value = GET_VALUE (s);
|
s_key = hash->key_extract_func (s_value);
|
hash_val = HASH (hash, s_key) & hash->table_mask;
|
new_s = &hash->table [hash_val];
|
|
while (!IS_EMPTY (new_s)) {
|
step++;
|
hash_val += step;
|
hash_val &= hash->table_mask;
|
new_s = &hash->table [hash_val];
|
}
|
|
*new_s = *s;
|
}
|
g_free (old_table);
|
hash->n_occupied = hash->in_use;
|
}
|
|
static void
|
rehash (MonoValueHashTable *hash)
|
{
|
int n_occupied = hash->n_occupied;
|
int table_size = hash->table_size;
|
|
if ((table_size > hash->in_use * 4 && table_size > 1 << HASH_TABLE_MIN_SHIFT) ||
|
(table_size <= n_occupied + (n_occupied / 16)))
|
do_rehash (hash);
|
}
|
|
static void
|
mono_value_hash_table_insert_replace (MonoValueHashTable *hash, gpointer key, gpointer value, gboolean replace)
|
{
|
guint hashcode;
|
Slot *s;
|
guint s_index;
|
GEqualFunc equal;
|
guint first_tombstone = 0;
|
gboolean have_tombstone = FALSE;
|
guint step = 0;
|
|
g_assert (value);
|
g_assert (hash->key_extract_func (value) == key);
|
|
g_return_if_fail (hash != NULL);
|
|
hashcode = HASH (hash, key);
|
|
s_index = hashcode & hash->table_mask;
|
s = &hash->table [s_index];
|
|
equal = hash->key_equal_func;
|
|
while (!IS_EMPTY (s)) {
|
gpointer s_value = GET_VALUE (s);
|
gpointer s_key = hash->key_extract_func (s_value);
|
guint s_key_hash = HASH (hash, s_key);
|
if (s_key_hash == hashcode && (*equal) (s_key, key)) {
|
if (replace){
|
if (hash->key_destroy_func != NULL)
|
(*hash->key_destroy_func)(s_key);
|
}
|
if (hash->value_destroy_func != NULL)
|
(*hash->value_destroy_func) (GET_VALUE (s));
|
SET_VALUE (s, value);
|
return;
|
} else if (IS_TOMBSTONE (s) && !have_tombstone) {
|
first_tombstone = s_index;
|
have_tombstone = TRUE;
|
}
|
|
step++;
|
s_index += step;
|
s_index &= hash->table_mask;
|
s = &hash->table [s_index];
|
}
|
|
if (have_tombstone) {
|
s = &hash->table [first_tombstone];
|
} else {
|
hash->n_occupied++;
|
}
|
|
SET_VALUE (s, value);
|
hash->in_use++;
|
|
rehash (hash);
|
}
|
|
void
|
mono_value_hash_table_insert (MonoValueHashTable *hash, gpointer key, gpointer value)
|
{
|
mono_value_hash_table_insert_replace (hash, key, value, TRUE);
|
}
|
|
static Slot *
|
lookup_internal (MonoValueHashTable *hash, gconstpointer key)
|
{
|
GEqualFunc equal;
|
Slot *s;
|
guint hashcode;
|
guint s_index;
|
guint step = 0;
|
|
hashcode = HASH (hash, key);
|
|
s_index = hashcode & hash->table_mask;
|
s = &hash->table [s_index];
|
|
equal = hash->key_equal_func;
|
|
while (!IS_EMPTY (s)) {
|
gpointer s_value = GET_VALUE (s);
|
gpointer s_key = hash->key_extract_func (s_value);
|
guint s_key_hash = HASH (hash, s_key);
|
if (s_key_hash == hashcode && (*equal) (hash->key_extract_func (s_value), key))
|
return s;
|
|
step++;
|
s_index += step;
|
s_index &= hash->table_mask;
|
s = &hash->table [s_index];
|
}
|
|
return NULL;
|
}
|
|
gpointer
|
mono_value_hash_table_lookup (MonoValueHashTable *hash, gconstpointer key)
|
{
|
Slot *slot = lookup_internal (hash, key);
|
|
if (slot)
|
return GET_VALUE (slot);
|
else
|
return NULL;
|
}
|
|
void
|
mono_value_hash_table_destroy (MonoValueHashTable *hash)
|
{
|
int i;
|
|
g_return_if_fail (hash != NULL);
|
|
for (i = 0; i < hash->table_size; i++){
|
Slot *s = &hash->table [i];
|
|
if (!IS_EMPTY (s) && !IS_TOMBSTONE (s)) {
|
if (hash->key_destroy_func != NULL)
|
(*hash->key_destroy_func)(hash->key_extract_func (GET_VALUE (s)));
|
if (hash->value_destroy_func != NULL)
|
(*hash->value_destroy_func)(GET_VALUE (s));
|
}
|
}
|
g_free (hash->table);
|
|
g_free (hash);
|
}
|
