#ifdef HAVE_SGEN_GC
#include <mono/metadata/sgen-gc.h>
+#include <mono/metadata/sgen-hash-table.h>
+#include <mono/utils/mono-counters.h>
+
+#ifdef HEAVY_STATISTICS
+static long long stat_lookups;
+static long long stat_lookup_iterations;
+static long long stat_lookup_max_iterations;
+#endif
static void
rehash (SgenHashTable *hash_table)
{
SgenHashTableEntry **old_hash = hash_table->table;
- int old_hash_size = hash_table->size;
- int i;
- unsigned int hash;
+ guint old_hash_size = hash_table->size;
+ guint i, hash, new_size;
SgenHashTableEntry **new_hash;
SgenHashTableEntry *entry, *next;
- int new_size;
if (!old_hash) {
- mono_sgen_register_fixed_internal_mem_type (hash_table->entry_mem_type,
+ sgen_register_fixed_internal_mem_type (hash_table->entry_mem_type,
sizeof (SgenHashTableEntry*) + sizeof (gpointer) + hash_table->data_size);
new_size = 13;
} else {
new_size = g_spaced_primes_closest (hash_table->num_entries);
}
- new_hash = mono_sgen_alloc_internal_dynamic (new_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
+ new_hash = sgen_alloc_internal_dynamic (new_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type, TRUE);
for (i = 0; i < old_hash_size; ++i) {
for (entry = old_hash [i]; entry; entry = next) {
hash = hash_table->hash_func (entry->key) % new_size;
new_hash [hash] = entry;
}
}
- mono_sgen_free_internal_dynamic (old_hash, old_hash_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
+ sgen_free_internal_dynamic (old_hash, old_hash_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
hash_table->table = new_hash;
hash_table->size = new_size;
}
{
if (hash_table->num_entries >= hash_table->size * 2)
rehash (hash_table);
+
+ SGEN_ASSERT (1, hash_table->size, "rehash guarantees size > 0");
}
static SgenHashTableEntry*
-lookup (SgenHashTable *hash_table, gpointer key, int *_hash)
+lookup (SgenHashTable *hash_table, gpointer key, guint *_hash)
{
SgenHashTableEntry *entry;
- int hash;
+ guint hash;
+ GEqualFunc equal = hash_table->equal_func;
+#ifdef HEAVY_STATISTICS
+ long long iterations = 0;
+ ++stat_lookups;
+#endif
if (!hash_table->size)
return NULL;
*_hash = hash;
for (entry = hash_table->table [hash]; entry; entry = entry->next) {
- if (entry->key == key)
+#ifdef HEAVY_STATISTICS
+ ++stat_lookup_iterations;
+ ++iterations;
+ if (iterations > stat_lookup_max_iterations)
+ stat_lookup_max_iterations = iterations;
+#endif
+ if ((equal && equal (entry->key, key)) || (!equal && entry->key == key))
return entry;
}
return NULL;
}
gpointer
-mono_sgen_hash_table_lookup (SgenHashTable *hash_table, gpointer key)
+sgen_hash_table_lookup (SgenHashTable *hash_table, gpointer key)
{
SgenHashTableEntry *entry = lookup (hash_table, key, NULL);
if (!entry)
}
gboolean
-mono_sgen_hash_table_replace (SgenHashTable *hash_table, gpointer key, gpointer data)
+sgen_hash_table_replace (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
{
- int hash;
+ guint hash;
SgenHashTableEntry *entry;
rehash_if_necessary (hash_table);
entry = lookup (hash_table, key, &hash);
if (entry) {
- memcpy (entry->data, data, hash_table->data_size);
+ if (old_value)
+ memcpy (old_value, entry->data, hash_table->data_size);
+ memcpy (entry->data, new_value, hash_table->data_size);
return FALSE;
}
- entry = mono_sgen_alloc_internal (hash_table->entry_mem_type);
+ entry = sgen_alloc_internal (hash_table->entry_mem_type);
entry->key = key;
- memcpy (entry->data, data, hash_table->data_size);
+ memcpy (entry->data, new_value, hash_table->data_size);
entry->next = hash_table->table [hash];
hash_table->table [hash] = entry;
hash_table->num_entries++;
return TRUE;
+}
+
+gboolean
+sgen_hash_table_set_value (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
+{
+ guint hash;
+ SgenHashTableEntry *entry;
+
+ entry = lookup (hash_table, key, &hash);
+
+ if (entry) {
+ if (old_value)
+ memcpy (old_value, entry->data, hash_table->data_size);
+ memcpy (entry->data, new_value, hash_table->data_size);
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+gboolean
+sgen_hash_table_set_key (SgenHashTable *hash_table, gpointer old_key, gpointer new_key)
+{
+ guint hash;
+ SgenHashTableEntry *entry;
+
+ entry = lookup (hash_table, old_key, &hash);
+
+ if (entry) {
+ entry->key = new_key;
+ return TRUE;
+ }
+ return FALSE;
}
gboolean
-mono_sgen_hash_table_remove (SgenHashTable *hash_table, gpointer key, gpointer data_return)
+sgen_hash_table_remove (SgenHashTable *hash_table, gpointer key, gpointer data_return)
{
SgenHashTableEntry *entry, *prev;
- int hash;
+ guint hash;
+ GEqualFunc equal = hash_table->equal_func;
rehash_if_necessary (hash_table);
hash = hash_table->hash_func (key) % hash_table->size;
prev = NULL;
for (entry = hash_table->table [hash]; entry; entry = entry->next) {
- if (entry->key == key) {
+ if ((equal && equal (entry->key, key)) || (!equal && entry->key == key)) {
if (prev)
prev->next = entry->next;
else
if (data_return)
memcpy (data_return, entry->data, hash_table->data_size);
- mono_sgen_free_internal (entry, hash_table->entry_mem_type);
+ sgen_free_internal (entry, hash_table->entry_mem_type);
return TRUE;
}
}
void
-mono_sgen_hash_table_clean (SgenHashTable *hash_table)
+sgen_hash_table_clean (SgenHashTable *hash_table)
{
- int i;
+ guint i;
if (!hash_table->size) {
- g_assert (!hash_table->table);
- g_assert (!hash_table->num_entries);
+ SGEN_ASSERT (1, !hash_table->table, "clean should reset hash_table->table");
+ SGEN_ASSERT (1, !hash_table->num_entries, "clean should reset hash_table->num_entries");
return;
}
SgenHashTableEntry *entry = hash_table->table [i];
while (entry) {
SgenHashTableEntry *next = entry->next;
- mono_sgen_free_internal (entry, hash_table->entry_mem_type);
+ sgen_free_internal (entry, hash_table->entry_mem_type);
entry = next;
}
}
- mono_sgen_free_internal_dynamic (hash_table->table, hash_table->size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
+ sgen_free_internal_dynamic (hash_table->table, hash_table->size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
hash_table->table = NULL;
hash_table->size = 0;
hash_table->num_entries = 0;
}
+void
+sgen_init_hash_table (void)
+{
+#ifdef HEAVY_STATISTICS
+ mono_counters_register ("Hash table lookups", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_lookups);
+ mono_counters_register ("Hash table lookup iterations", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_lookup_iterations);
+ mono_counters_register ("Hash table lookup max iterations", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_lookup_max_iterations);
+#endif
+}
+
#endif
projects / mono.git / blobdiff