/* Libvisual - The audio visualisation framework.
 * 
 * Copyright (C) 2004, 2005, 2006 Dennis Smit <ds@nerds-incorporated.org>
 *
 * Authors: Dennis Smit <ds@nerds-incorporated.org>
 *
 * $Id: lv_hashmap.c,v 1.11 2006/02/17 22:00:17 synap Exp $
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1
 * 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include "lv_common.h"
#include "lv_hashmap.h"

#define HASHMAP_ITERCONTEXT(obj)                           (VISUAL_CHECK_CAST ((obj), HashmapIterContext))


typedef struct _HashmapIterContext HashmapIterContext;

struct _HashmapIterContext {
	VisObject	*object;

	int		 index;
	int		 retrieved;
	int		 first;

	VisListEntry	*le;
};


static int hashmap_destroy (VisCollection *collection);
static int hashmap_chain_destroy (VisHashmap *hashmap, VisList *list);
static int hashmap_size (VisCollection *collection);
static VisCollectionIter *hashmap_iter (VisCollection *collection);

static void hashmap_iter_assign (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext, int index);
static int hashmap_iter_has_more (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
static void hashmap_iter_next (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
static void *hashmap_iter_get_data (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);

static int integer_hash (uint32_t key);
static int string_hash (char *key);
static int get_hash (VisHashmap *hashmap, void *key, VisHashmapKeyType keytype);

static int create_table (VisHashmap *hashmap);


static int hashmap_destroy (VisCollection *collection)
{
	VisCollectionDestroyerFunc destroyer;
	VisHashmap *hashmap = VISUAL_HASHMAP (collection);
	VisHashmapEntry *mentry;
	int i;

	for (i = 0; i < hashmap->size; i++)
		hashmap_chain_destroy (hashmap, &hashmap->table[i].list);

	if (hashmap->table != NULL)
		visual_mem_free (hashmap->table);

	hashmap->table = NULL;

	return VISUAL_OK;
}

/* We can't use collection dtor because we need to chain up (HashChainElem -> DataElem) */
static int hashmap_chain_destroy (VisHashmap *hashmap, VisList *list)
{
	VisCollectionDestroyerFunc destroyer;
	VisHashmapChainEntry *mentry;
	VisListEntry *le = NULL;

	destroyer = visual_collection_get_destroyer (VISUAL_COLLECTION (hashmap));

	if (destroyer == NULL) {
		while ((mentry = visual_list_next (list, &le)) != NULL)
			visual_list_destroy (list, &le);
	} else {
		while ((mentry = visual_list_next (list, &le)) != NULL) {
			destroyer (mentry->data);
			visual_list_destroy (list, &le);
		}
	}
}

static int hashmap_list_entry_destroyer (void *data)
{
	VisHashmapChainEntry *mentry = VISUAL_HASHMAPCHAINENTRY (data);

	if (mentry == NULL)
		return -1;

	if (mentry->keytype == VISUAL_HASHMAP_KEY_TYPE_STRING) {
		visual_mem_free (mentry->key.string);
	}

	return visual_mem_free (mentry);
}

static int hashmap_size (VisCollection *collection)
{
	VisHashmap *hashmap = VISUAL_HASHMAP (collection);

	return hashmap->size;
}

static VisCollectionIter *hashmap_iter (VisCollection *collection)
{
	VisCollectionIter *iter;
	HashmapIterContext *context;
	VisHashmap *hashmap = VISUAL_HASHMAP (collection);

	context = visual_mem_new0 (HashmapIterContext, 1);

	/* Do the VisObject initialization */
	visual_object_initialize (VISUAL_OBJECT (context), TRUE, NULL);
	context->index = 0;
	context->le = NULL;
	context->retrieved = FALSE;
	context->first = TRUE;

	iter = visual_collection_iter_new (hashmap_iter_assign, hashmap_iter_next, hashmap_iter_has_more,
			hashmap_iter_get_data, collection, VISUAL_OBJECT (context));

	return iter;
}

static void hashmap_iter_assign (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext, int index)
{
	VisHashmap *hashmap = VISUAL_HASHMAP (collection);
	int i;

	if (index >= hashmap->tablesize)
		return;

	for (i = 0; i < index; i++) {
		hashmap_iter_next (iter, collection, itercontext);
	}
}

static int hashmap_iter_has_more (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
{
	VisHashmap *hashmap = VISUAL_HASHMAP (collection);
	HashmapIterContext *context = HASHMAP_ITERCONTEXT (itercontext);

	if (context->index >= hashmap->tablesize)
		return FALSE;

	/* First entry */
	if (context->first) {
		context->first = FALSE;

		for (; context->index < hashmap->tablesize; context->index++) {
			if (visual_collection_size (VISUAL_COLLECTION (&hashmap->table[context->index].list)) > 0) {
				context->le = hashmap->table[context->index].list.head;
				context->retrieved = FALSE;

				return TRUE;
			}
		}
	}

	/* Check for next chain entry */
	if (context->le != NULL && context->le->next != NULL) {
		context->le = context->le->next;

		return TRUE;
	}

	/* No next in chain, next array entry */
	context->index++;
	for (; context->index < hashmap->tablesize; context->index++) {
		if (visual_collection_size (VISUAL_COLLECTION (&hashmap->table[context->index].list)) > 0) {
			context->le = hashmap->table[context->index].list.head;
			context->retrieved = FALSE;

			return TRUE;
		}
	}

	return FALSE;
}

static void hashmap_iter_next (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
{
	VisHashmap *hashmap = VISUAL_HASHMAP (collection);
	HashmapIterContext *context = HASHMAP_ITERCONTEXT (itercontext);

	if (context->retrieved == FALSE) {
		if (context->first == TRUE) {
			hashmap_iter_has_more (iter, collection, itercontext);

			context->first = FALSE;
		}

		context->retrieved = TRUE;

		return;
	}

	hashmap_iter_has_more (iter, collection, itercontext);
	context->retrieved = TRUE;

	return;
}

static void *hashmap_iter_get_data (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
{
	HashmapIterContext *context = HASHMAP_ITERCONTEXT (itercontext);
	VisHashmapChainEntry *mentry;

	mentry = context->le->data;

	return mentry->data;
}


/* Thomas Wang's 32 bit Mix Function: http://www.concentric.net/~Ttwang/tech/inthash.htm */
static int integer_hash (uint32_t key)
{
	key += ~(key << 15);
	key ^=  (key >> 10);
	key +=  (key << 3);
	key ^=  (key >> 6);
	key += ~(key << 11);
	key ^=  (key >> 16);

	return key;
}

/* X31 HASH found in g_str_hash */
static int string_hash (char *key)
{
	char *p;
	int hash = 0;

	for (p = key; *p != '\0'; p++)
		hash = (hash << 5) - hash  + *p;

	return hash;
}

static int get_hash (VisHashmap *hashmap, void *key, VisHashmapKeyType keytype)
{
	if (keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER)
		return integer_hash (*((uint32_t *) key)) % hashmap->tablesize;
	else if (keytype = VISUAL_HASHMAP_KEY_TYPE_STRING)
		return string_hash ((char *) key) % hashmap->tablesize;

	return 0;
}

static int create_table (VisHashmap *hashmap)
{
	int i;

	hashmap->table = visual_mem_new0 (VisHashmapEntry, hashmap->tablesize);

	/* Initialize first entry */
	visual_list_init (&hashmap->table[0].list, hashmap_list_entry_destroyer);

	/* Copy the entries to increase speed */
	for (i = 1; i < hashmap->tablesize; i *= 2) {
		int n = (i + i) > hashmap->tablesize ? hashmap->tablesize - i : i;

		visual_mem_copy (&hashmap->table[i], &hashmap->table[0], sizeof (VisHashmapEntry) * n);
	}

	return VISUAL_OK;
}


/**
 * @defgroup VisHashmap VisHashmap
 * @{
 */

/**
 * Creates a new VisHashmap.
 * 
 * @return A newly allocated VisHashmap.
 */
VisHashmap *visual_hashmap_new (VisCollectionDestroyerFunc destroyer)
{
	VisHashmap *hashmap;

	hashmap = visual_mem_new0 (VisHashmap, 1);

	visual_hashmap_init (hashmap, destroyer);

	/* do the visobject initialization */
	visual_object_set_allocated (VISUAL_OBJECT (hashmap), TRUE);
	visual_object_ref (VISUAL_OBJECT (hashmap));

	return hashmap;
}

int visual_hashmap_init (VisHashmap *hashmap, VisCollectionDestroyerFunc destroyer)
{
	visual_log_return_val_if_fail (hashmap != NULL, -VISUAL_ERROR_HASHMAP_NULL);

	/* Do the VisObject initialization */
	visual_object_clear (VISUAL_OBJECT (hashmap));
	visual_object_set_dtor (VISUAL_OBJECT (hashmap), visual_collection_dtor);
	visual_object_set_allocated (VISUAL_OBJECT (hashmap), FALSE);

	/* Set the VisCollection data */
	visual_collection_set_destroyer (VISUAL_COLLECTION (hashmap), destroyer);
	visual_collection_set_destroy_func (VISUAL_COLLECTION (hashmap), hashmap_destroy);
	visual_collection_set_size_func (VISUAL_COLLECTION (hashmap), hashmap_size);
	visual_collection_set_iter_func (VISUAL_COLLECTION (hashmap), hashmap_iter);

	/* Set the VisHashmap data */
	hashmap->tablesize = VISUAL_HASHMAP_START_SIZE;
	hashmap->size = 0;
	hashmap->table = NULL;

	return VISUAL_OK;
}

int visual_hashmap_put (VisHashmap *hashmap, void *key, VisHashmapKeyType keytype, void *data)
{
	VisHashmapChainEntry *mentry;
	VisListEntry *le = NULL;
	VisList *chain;
	int hash;

	visual_log_return_val_if_fail (hashmap != NULL, -VISUAL_ERROR_HASHMAP_NULL);

	/* Create initial hashtable */
	if (hashmap->table == NULL)
		create_table (hashmap);

	hash = get_hash (hashmap, key, keytype);

	chain = &hashmap->table[hash].list;

	/* Iterate list to check if the key is already in the chain */
	if (keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER) {
		while ((mentry = visual_list_next (chain, &le)) != NULL) {
			if (mentry->keytype == keytype) {

				if (keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER &&
						mentry->key.integer != *((uint32_t *) key))
					continue;
				else if (keytype == VISUAL_HASHMAP_KEY_TYPE_STRING &&
						strcmp (mentry->key.string, (char *) key) != 0)
					continue;

				mentry->data = data;

				return VISUAL_OK;
			}
		}
	}

	/* Key not in chain, append at end */
	mentry = visual_mem_new0 (VisHashmapChainEntry, 1);

	mentry->keytype = keytype;

	if (keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER)
		mentry->key.integer = *((uint32_t *) key);
	else if (keytype == VISUAL_HASHMAP_KEY_TYPE_STRING)
		mentry->key.string = strdup ((char *) key);

	mentry->data = data;

	visual_list_add (chain, mentry);

	hashmap->size++;

	return VISUAL_OK;
}

int visual_hashmap_put_integer (VisHashmap *hashmap, uint32_t key, void *data)
{
	return visual_hashmap_put (hashmap, &key, VISUAL_HASHMAP_KEY_TYPE_INTEGER, data);
}

int visual_hashmap_put_string (VisHashmap *hashmap, char *key, void *data)
{
	return visual_hashmap_put (hashmap, key, VISUAL_HASHMAP_KEY_TYPE_STRING, data);
}

int visual_hashmap_remove (VisHashmap *hashmap, void *key, VisHashmapKeyType keytype, int destroy)
{
	VisCollectionDestroyerFunc destroyer;
	VisHashmapChainEntry *mentry;
	VisListEntry *le = NULL;
	VisList *chain;
	int hash;

	visual_log_return_val_if_fail (hashmap != NULL, -VISUAL_ERROR_HASHMAP_NULL);

	if (hashmap->table == NULL)
		return -VISUAL_ERROR_HASHMAP_NOT_IN_MAP;

	hash = get_hash (hashmap, key, keytype);

	chain = &hashmap->table[hash].list;

	/* Iterate list to check if the key is in the chain */
	while ((mentry = visual_list_next (chain, &le)) != NULL) {
		if (mentry->keytype == keytype) {

			if (keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER &&
					mentry->key.integer != *((uint32_t *) key))
				continue;
			else if (keytype == VISUAL_HASHMAP_KEY_TYPE_STRING &&
					strcmp (mentry->key.string, (char *) key) != 0)
				continue;

			if (destroy != FALSE) {
				destroyer = visual_collection_get_destroyer (VISUAL_COLLECTION (hashmap));

				destroyer (mentry->data);
				visual_list_destroy (chain, &le);
			} else {
				visual_list_destroy (chain, &le);
			}

			hashmap->size--;

			return VISUAL_OK;
		}
	}

	return -VISUAL_ERROR_HASHMAP_NOT_IN_MAP;
}

int visual_hashmap_remove_integer (VisHashmap *hashmap, uint32_t key, int destroy)
{
	return visual_hashmap_remove (hashmap, &key, VISUAL_HASHMAP_KEY_TYPE_INTEGER, destroy);
}

int visual_hashmap_remove_string (VisHashmap *hashmap, char *key, int destroy)
{
	return visual_hashmap_remove (hashmap, key, VISUAL_HASHMAP_KEY_TYPE_STRING, destroy);
}

void *visual_hashmap_get (VisHashmap *hashmap, void *key, VisHashmapKeyType keytype)
{
	VisHashmapChainEntry *mentry;
	VisListEntry *le = NULL;
	VisList *chain;
	int hash;

	visual_log_return_val_if_fail (hashmap != NULL, NULL);

	/* Create initial hashtable */
	if (hashmap->table == NULL)
		return NULL;

	hash = get_hash (hashmap, key, keytype);

	chain = &hashmap->table[hash].list;

	/* Iterate list to check if the key is already in the chain */
	while ((mentry = visual_list_next (chain, &le)) != NULL) {
		if (mentry->keytype == keytype) {
			if (keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER &&
					mentry->key.integer != *((uint32_t *) key))
				continue;
			else if (keytype == VISUAL_HASHMAP_KEY_TYPE_STRING &&
					strcmp (mentry->key.string, (char *) key) != 0)
				continue;

			return mentry->data;
		}
	}

	return NULL;
}

void *visual_hashmap_get_integer (VisHashmap *hashmap, uint32_t key)
{
	return visual_hashmap_get (hashmap, &key, VISUAL_HASHMAP_KEY_TYPE_INTEGER);
}

void *visual_hashmap_get_string (VisHashmap *hashmap, char *key)
{
	return visual_hashmap_get (hashmap, key, VISUAL_HASHMAP_KEY_TYPE_STRING);
}

int visual_hashmap_set_table_size (VisHashmap *hashmap, int tablesize)
{
	int oldsize;

	visual_log_return_val_if_fail (hashmap != NULL, -VISUAL_ERROR_HASHMAP_NULL);

	/* Table was not empty, rehash */
	if (hashmap->table != NULL) {
		VisHashmap tempmap;

		visual_hashmap_init (&tempmap, NULL);

		tempmap.table = hashmap->table;
		tempmap.tablesize = hashmap->tablesize;
		tempmap.size = hashmap->size;

		VisCollectionIter *iter = visual_collection_get_iter (VISUAL_COLLECTION (hashmap));

		hashmap->tablesize = tablesize;
		create_table (hashmap);

		/* Rehash all entries */
		while (visual_collection_iter_has_more (iter) == TRUE) {
			VisHashmapChainEntry *mentry = visual_collection_iter_get_data (iter);

			if (mentry->keytype == VISUAL_HASHMAP_KEY_TYPE_INTEGER) {
				visual_hashmap_put_integer (hashmap, mentry->key.integer, mentry->data);

			} else if (mentry->keytype == VISUAL_HASHMAP_KEY_TYPE_STRING) {
				visual_hashmap_put_string (hashmap, mentry->key.string, mentry->data);

			}
		}

		/* Free old table */
		visual_object_unref (VISUAL_OBJECT (&tempmap));

	} else {
		hashmap->tablesize = tablesize;
		create_table (hashmap);
	}

	return VISUAL_OK;
}

int visual_hashmap_get_table_size (VisHashmap *hashmap)
{
	visual_log_return_val_if_fail (hashmap != NULL, -VISUAL_ERROR_HASHMAP_NULL);

	return hashmap->tablesize;
}

/**
 * @}
 */