/**
 * \file
 *
 * 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 "config.h"

#ifdef HAVE_SGEN_GC

#include <string.h>

#include <mono/sgen/sgen-gc.h>
#include <mono/sgen/sgen-hash-table.h>

#ifdef HEAVY_STATISTICS
static guint64 stat_lookups;
static guint64 stat_lookup_iterations;
static guint64 stat_lookup_max_iterations;
#endif

static void
rehash (SgenHashTable *hash_table)
{
	SgenHashTableEntry **old_hash = hash_table->table;
	guint old_hash_size = hash_table->size;
	guint i, hash, new_size;
	SgenHashTableEntry **new_hash;
	SgenHashTableEntry *entry, *next;

	if (!old_hash) {
		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 = (SgenHashTableEntry **)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;
			next = entry->next;
			entry->next = new_hash [hash];
			new_hash [hash] = entry;
		}
	}
	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;
}

static void
rehash_if_necessary (SgenHashTable *hash_table)
{
	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, guint *_hash)
{
	SgenHashTableEntry *entry;
	guint hash;
	GEqualFunc equal = hash_table->equal_func;
#ifdef HEAVY_STATISTICS
	guint64 iterations = 0;
	++stat_lookups;
#endif

	if (!hash_table->size)
		return NULL;

	hash = hash_table->hash_func (key) % hash_table->size;
	if (_hash)
		*_hash = hash;

	for (entry = hash_table->table [hash]; entry; entry = entry->next) {
#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
sgen_hash_table_lookup (SgenHashTable *hash_table, gpointer key)
{
	SgenHashTableEntry *entry = lookup (hash_table, key, NULL);
	if (!entry)
		return NULL;
	return entry->data;
}

gboolean
sgen_hash_table_replace (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
{
	guint hash;
	SgenHashTableEntry *entry;

	rehash_if_necessary (hash_table);
	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 FALSE;
	}

	entry = (SgenHashTableEntry *)sgen_alloc_internal (hash_table->entry_mem_type);
	entry->key = key;
	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
sgen_hash_table_remove (SgenHashTable *hash_table, gpointer key, gpointer data_return)
{
	SgenHashTableEntry *entry, *prev;
	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 ((equal && equal (entry->key, key)) || (!equal && entry->key == key)) {
			if (prev)
				prev->next = entry->next;
			else
				hash_table->table [hash] = entry->next;

			hash_table->num_entries--;

			if (data_return)
				memcpy (data_return, entry->data, hash_table->data_size);

			sgen_free_internal (entry, hash_table->entry_mem_type);

			return TRUE;
		}
		prev = entry;
	}

	return FALSE;
}

void
sgen_hash_table_clean (SgenHashTable *hash_table)
{
	guint i;

	if (!hash_table->size) {
		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;
	}

	for (i = 0; i < hash_table->size; ++i) {
		SgenHashTableEntry *entry = hash_table->table [i];
		while (entry) {
			SgenHashTableEntry *next = entry->next;
			sgen_free_internal (entry, hash_table->entry_mem_type);
			entry = next;
		}
	}

	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_ULONG, &stat_lookups);
	mono_counters_register ("Hash table lookup iterations", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_lookup_iterations);
	mono_counters_register ("Hash table lookup max iterations", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_lookup_max_iterations);
#endif
}

#endif