/*
 * HashTable - ハッシュテーブル。
 *
 * Date: 2014-04-10
 * Author: Leonardone
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG_FLAG 1

#if DEBUG_FLAG
#  define DebugDo(d) d
#else
#  define DebugDo(d)
#endif

/* --- hashtable.h --- */

#define MINIMUM_HASHTABLESIZE (0x0002)
#define MAXIMUM_HASHTABLESIZE (0x7FFF)

struct _hashtable;
struct _tabledata;

typedef struct _hashtable HashTable, *LPHashTable;
typedef struct _tabledata TableData, *LPTableData;

extern LPHashTable newHashTable(int tablesize);
extern void releaseHashTable(LPHashTable htable);
extern int addDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size);
extern int getDataFromHashTable(const LPHashTable htable, const char *key, void *data, const int size);
extern int removeDataFromHashTable(LPHashTable htable, const char *key);
extern int existKeyInHashTable(LPHashTable htable, const char *key);
extern int setDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size);
extern int countDataInHashTable(LPHashTable htable);
extern int getAllKeysInHashTable(const LPHashTable htable, int (*func)(const char *key));

struct _hashtable {
	int count;
	int tablesize;
	LPTableData *table;
};

struct _tabledata {
	char *key;
	void *data;
	int size;
	LPTableData next;
};

/* --- hashtable_static.h --- */

#define HASH_DEEP (5)

static int hash(const char *key, const int tablesize);
static LPTableData *searchPlace(const LPHashTable htable, const char *key);
static void releaseTableData(LPTableData ptbdata, int chain);

/* --- test.c --- */

int addIntIntoHashTable(LPHashTable htable, const char *key, const int value) {
	return addDataIntoHashTable(htable, key, &value, sizeof(int));
}

int getIntFromHashTable(const LPHashTable htable, const char *key, int *value) {
	return getDataFromHashTable(htable, key, (void*)value, sizeof(int));
}

int setIntIntoHashTable(LPHashTable htable, const char *key, const int value) {
	return setDataIntoHashTable(htable, key, &value, sizeof(int));
}

int func1(const char* key) {
	printf("key: %s\n", key);
	return 0;
}

int main(void) {
	
	LPHashTable htable = newHashTable(1024);
	int v = 0;
	
	addIntIntoHashTable(htable, "foo", 111);
	addIntIntoHashTable(htable, "bar", 222);
	addIntIntoHashTable(htable, "baz", 333);
	addIntIntoHashTable(htable, "fuga", 987);
	addIntIntoHashTable(htable, "piyo", 654);
	

	printf("cnt: %d\n", htable->count);
	printf("cnt: %d\n", countDataInHashTable(htable));

	addIntIntoHashTable(htable, "hoge", 123);
	addIntIntoHashTable(htable, "hoge", 345);
	getIntFromHashTable(htable, "hoge", &v);
	printf("get: %d\n", v);

	printf("cnt: %d\n", countDataInHashTable(htable));

	setIntIntoHashTable(htable, "hoge", 345);
	setIntIntoHashTable(htable, "foobar", 999);
	getIntFromHashTable(htable, "hoge", &v);
	printf("get: %d\n", v);

	printf("cnt: %d\n", countDataInHashTable(htable));
	
	getAllKeysInHashTable(htable, func1);
	
	removeDataFromHashTable(htable, "baz");
	removeDataFromHashTable(htable, "baz");
	removeDataFromHashTable(htable, "test");

	printf("cnt: %d\n", countDataInHashTable(htable));

	printf("sch: %d\n", searchPlace(htable, "hoge"));
	printf("sch: %d\n", searchPlace(htable, "abc"));
	printf("*sch: %d\n", *searchPlace(htable, "hoge"));
	printf("*sch: %d\n", *searchPlace(htable, "abc"));
	printf("*sch-d: %d\n", *(int*)(*searchPlace(htable, "hoge"))->data);
	printf("*sch-d: %d\n", *(int*)(*searchPlace(htable, "bar"))->data);

	printf("ext: %d\n", existKeyInHashTable(htable, "hoge"));
	printf("ext: %d\n", existKeyInHashTable(htable, "abc"));
	printf("ext: %d\n", existKeyInHashTable(htable, "foo"));
	printf("ext: %d\n", existKeyInHashTable(htable, "baz"));
	printf("ext: %d\n", existKeyInHashTable(htable, "fuga"));
	printf("ext: %d\n", existKeyInHashTable(htable, "piyo"));
	
	releaseHashTable(htable);
	
	return 0;
}

/* --- hashtable.c --- */

/* +++ extern functions +++ */

/**
 * 新しいHashTableを作る。
 * @param tablesize
 * @return
 */
LPHashTable newHashTable(const int tablesize) {
	/* calloc は 0 で初期化される */
	LPHashTable htable;
	if (tablesize < MINIMUM_HASHTABLESIZE || tablesize > MAXIMUM_HASHTABLESIZE) {
		return NULL; /* 引数エラー */ 
	}
	htable = (LPHashTable)calloc(1, sizeof(HashTable));
	if (htable == NULL) {
		return NULL; /* メモリ確保失敗 */
	}
	htable->table = (LPTableData *)calloc(tablesize, sizeof(LPTableData));
	if (htable->table == NULL) {
		free(htable);
		return NULL; /* メモリ確保失敗 */
	}
	htable->tablesize = tablesize;
	DebugDo(printf("init HashTable(%d)\n", tablesize));
	return htable;
}

/**
 * HashTableをメモリから解放する。
 * @param htable
 */
void releaseHashTable(LPHashTable htable) {
	int i;
	int tablesize;
	LPTableData *ptbdata;
	if (htable == NULL) {
		return; /* ぬるぽ */
	}
	tablesize = htable->tablesize;
	for (i = 0; i < tablesize; ++i) {
		ptbdata = htable->table + i;
		if (*ptbdata != NULL) {
			releaseTableData(*ptbdata, 1);
		}
	}
	free(htable->table);
	free(htable);
	DebugDo(printf("release HashTable(%d)\n", tablesize));
}

/**
 * HashTableにデータを追加する。既にキー名が存在する場合は失敗する。
 * @param htable
 * @param key
 * @param data
 * @param size
 * @return
 */
int addDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size) {
	int len;
	LPTableData *ptbdata;
	if (htable == NULL || key == NULL || data == NULL || size < 1) {
		return 0; /* 引数エラー */
	}
	ptbdata = searchPlace(htable, key);
	if (*ptbdata == NULL) {
		*ptbdata = (LPTableData)calloc(1, sizeof(TableData));
		if (*ptbdata == NULL) {
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->key = (char *)calloc(len, sizeof(char));
		if ((*ptbdata)->key == NULL) {
			free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->data = calloc(size, 1);
		if ((*ptbdata)->data == NULL) {
			free((*ptbdata)->key);
			free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		len = strlen(key) + 1;
		memcpy((*ptbdata)->key, key, len);
		memcpy((*ptbdata)->data, data, size);
		(*ptbdata)->size = size;
		++(htable->count);
		DebugDo(printf("add(success): %s\n", key));
		return 1;
	}
	DebugDo(printf("add(failure): %s\n", key));
	return 2;
}

/**
 * HashTableからキー名のデータを取得する。
 * @param htable
 * @param key
 * @param data
 * @param size
 * @return
 */
int getDataFromHashTable(const LPHashTable htable, const char *key, void *data, const int size) {
	int minsize;
	LPTableData tbdata;
	if (htable == NULL || key == NULL || data == NULL || size < 1) {
		return 0; /* 引数エラー */
	}
	tbdata = *searchPlace(htable, key);
	if (tbdata != NULL) {
		if (strcmp(tbdata->key, key) == 0) {
			minsize = tbdata->size < size ? tbdata->size : size;
			memcpy(data, tbdata->data, minsize);
			DebugDo(printf("get(success): %s\n", key));
			return minsize;
		}
		tbdata = tbdata->next;
	}
	DebugDo(printf("get(failure): %s\n", key));
	return 0;
}

/**
 * HashTableにデータを書き込む。既にキー名のデータがある場合は上書きする。
 * @param htable
 * @param key
 * @param data
 * @param size
 * @return
 */
int setDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size) {
	int len;
	int ret = 1;
	void *temp;
	LPTableData *ptbdata;
	if (htable == NULL || key == NULL || data == NULL || size < 1) {
		return 0; /* 引数エラー */
	}
	ptbdata = searchPlace(htable, key);
	if (*ptbdata == NULL) {
		*ptbdata = (LPTableData)calloc(1, sizeof(TableData));
		if (*ptbdata == NULL) {
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->key = (char *)calloc(len, sizeof(char));
		if ((*ptbdata)->key == NULL) {
			free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->data = calloc(size, 1);
		if ((*ptbdata)->data == NULL) {
			free((*ptbdata)->key);
			free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		len = strlen(key) + 1;
		memcpy((*ptbdata)->key, key, len);
		(*ptbdata)->size = size;
		++(htable->count);
		DebugDo(printf("set/new(success): %s\n", key));
	} else {
		if ((*ptbdata)->size != size) {
			temp = realloc((*ptbdata)->data, size);
			if (temp == NULL) {
				return 0; /* メモリ確保失敗 */
			}
			(*ptbdata)->data = temp;
			(*ptbdata)->size = size;
		}
		ret = 2;
		DebugDo(printf("set/update(success): %s\n", key));
	}
	memcpy((*ptbdata)->data, data, size);
	return ret;
}

/**
 * HashTable内の指定キー名のデータを削除する。
 * @param htable HashTable。
 * @param key    キー名。
 * @return 削除できたら(1)、失敗したら(0)。
 */
int removeDataFromHashTable(LPHashTable htable, const char *key) {
	LPTableData *ptbdata;
	LPTableData tbdata;
	if (htable == NULL || key == NULL) {
		return 0; /* ぬるぽ */
	}
	ptbdata = searchPlace(htable, key);
	if (*ptbdata != NULL) {
		tbdata = *ptbdata;
		*ptbdata = tbdata->next;
		releaseTableData(tbdata, 0);
		--(htable->count);
		DebugDo(printf("remove(success): %s\n", key));
		return 1;
	}
	DebugDo(printf("remove(failure): %s\n", key));
	return 0;
}

/**
 * HashTable内にキー名のデータが存在するか書くにする。
 * @param htable HashTable。
 * @param key    探すキー名。
 * @return 存在すれば(1)、存在しなければ(0)。
 */
int existKeyInHashTable(LPHashTable htable, const char *key) {
	if (htable == NULL || key == NULL) {
		return 0; /* ぬるぽ */
	}
	return *searchPlace(htable, key) != NULL;
}

/**
 * HashTable内のデータ数を返す。
 * @param htable HashTable。
 * @return データ数。
 */
int countDataInHashTable(LPHashTable htable) {
	if (htable == NULL) {
		return 0; /* ぬるぽ */
	}
	return htable->count;
}

/**
 * HashTable内のキー名を全て取得する。
 * @param htable
 * @param func
 * @return
 */
int getAllKeysInHashTable(const LPHashTable htable, int (*func)(const char *key)) {
	int i;
	int ret;
	int tablesize;
	LPTableData *ptbdata;
	LPTableData tbdata;
	if (htable == NULL || func == NULL) {
		return 0;
	}
	DebugDo(printf("allkey(start)\n"));
	ptbdata = htable->table;
	tablesize = htable->tablesize;
	for (i = 0; i < tablesize; ++i) {
		tbdata = *ptbdata;
		while (tbdata != NULL) {
			ret = (*func)(tbdata->key);
			if (ret) {
				DebugDo(printf("allkey(stop)\n"));
				return 2;
			}
			tbdata = tbdata->next;
		}
		++ptbdata;
	}
	DebugDo(printf("allkey(done)\n"));
	return 1;
}

/* +++ static functions +++ */

/**
 * ハッシュ関数。キー名からハッシュ値を生成する。
 * @param key        キー名。
 * @param tablesize  ハッシュ値の制限値。
 * @return ハッシュ値。
 */
int hash(const char *key, const int tablesize) {
	int i;
	int v = (int)*key;
	for (i = 0; i < HASH_DEEP && *key != '\0'; i++) {
		v ^= (int)(*key) * (int)(*(key + 1));
		++key;
	}
	return v % tablesize;
}

/**
 * HashTableからキー名のデータを格納する場所(アドレス)を探す。
 * @param htable キー名を探すHashTable。
 * @param key    探すキー名。
 * @return 格納されてる場所(アドレス)。
 */
LPTableData *searchPlace(const LPHashTable htable, const char *key) {
	int h = hash(key, htable->tablesize);
	LPTableData *ptbdata = htable->table + h;
	while (*ptbdata != NULL) {
		if (strcmp((*ptbdata)->key, key) == 0) {
			break;
		}
		ptbdata = &(*ptbdata)->next;
	}
	DebugDo(printf("hash(%d): %s\n", h, key));
	return ptbdata;
}

/**
 * TableDataをメモリから解放する。
 * @param ptbdata 解放するデータ。
 * @param chain   nextにあるTableDataも解放する(1)かしない(0)か。
 */
void releaseTableData(LPTableData tbdata, int chain) {
	if (tbdata == NULL) {
		return;
	}
	if (chain) {
		releaseTableData(tbdata->next, chain);
	}
	DebugDo(printf("release TableData: %s\n", tbdata->key));
	free(tbdata->key);
	free(tbdata->data);
	free(tbdata);
}