/*
 * HashTable - ハッシュテーブル。
 *
 * Date: 2014-04-11
 * Author: Leonardone
 * Version: 2.0
 */
#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

/* --- memory --- */

#define STATIC_MEMORY 1

#if STATIC_MEMORY

#define MEMORY_SIZE (4220)
char buf[MEMORY_SIZE + 1];
int bufptr;

void *myMalloc(size_t s) {
	char *tmp = buf + bufptr;
	DebugDo(printf("free: %d, request: %d\n", MEMORY_SIZE - bufptr, s));
	bufptr += s;
	if (bufptr > MEMORY_SIZE) {
		bufptr -= s;
		return NULL;
	}
	return (void*)tmp;
}

#  define Calloc(s1, s2) myMalloc((s1)*(s2))
#  define Malloc(s)      myMalloc(s)
#  define Realloc(p, s)  myMalloc(s)
#  define Free(p)        
#else
#  define Calloc(s1, s2) calloc(s1, s2)
#  define Malloc(s)      malloc(s)
#  define Realloc(p, s)  realloc(p, s)
#  define Free(p)        free(p)
#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(const int tablesize, int (*keycmp)(const void *key1, const int key1len, const void *key2, const int key2len), int (*hash)(const void *key, const int keylen, const int tablesize));
extern void releaseHashTable(LPHashTable htable);
extern int addDataIntoHashTable(LPHashTable htable, const void *key, const int keylen, const void *data, const int size);
extern int getDataFromHashTable(const LPHashTable htable, const void *key, const int keylen, void *data, const int size);
extern int removeDataFromHashTable(LPHashTable htable, const void *key, const int keylen);
extern int existKeyInHashTable(LPHashTable htable, const void *key, const int keylen);
extern int setDataIntoHashTable(LPHashTable htable, const void *key, const int keylen, const void *data, const int size);
extern int countDataInHashTable(LPHashTable htable);
extern int getAllKeysInHashTable(const LPHashTable htable, int (*func)(const void *key, const int keylen));
extern int getAllDataInHashTable(const LPHashTable htable, int (*func)(const void *key, const int keylen, const void *data, const int size));

struct _hashtable {
	int count;
	int tablesize;
	int (*keycmp)(const void* key1, const int key1len, const void *key2, const int key2len);
	int (*hash)(const void *key, const int keylen, const int tablesize);
	LPTableData *table;
};

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

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

#define HASH_DEEP (5)

static int defaultHash(const void *key, const int keylen, const int tablesize);
static LPTableData *searchPlace(const LPHashTable htable, const void *key, const int keylen);
static void releaseTableData(LPTableData ptbdata, int chain);
static int defaultKeycmp(const void *key1, const int key1len, const void *key2, const int key2len);
static int getHash(const LPHashTable htable, const void *key, const int keylen);

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

int addIntIntoHashTable(LPHashTable htable, const char *key, const int value) {
	int ret = addDataIntoHashTable(htable, key, strlen(key) + 1, &value, sizeof(int));
	if (ret == 1) {
		DebugDo(printf("add(success): %s, value: %d\n", key, value));
	} else if (ret == 2) {
		DebugDo(printf("add(failure): %s, value: %d\n", key, value));
	} else {
		DebugDo(printf("add(fatal error): %s\n", key));
	}
	return ret;
}

int getIntFromHashTable(const LPHashTable htable, const char *key, int *value) {
	int ret = getDataFromHashTable(htable, key, strlen(key) + 1, (void*)value, sizeof(int));
	if (ret) {
		DebugDo(printf("get(success): %s, size: %d\n", key, ret));
	} else {
		DebugDo(printf("get(failure): %s\n", key));
	}
	return ret;
}

int setIntIntoHashTable(LPHashTable htable, const char *key, const int value) {
	int ret = setDataIntoHashTable(htable, key, strlen(key) + 1, &value, sizeof(int));
	if (ret == 1) {
		DebugDo(printf("set/new(success): %s, value: %d\n", key, value));
	} else if (ret == 2) {
		DebugDo(printf("set/update(success): %s, value: %d\n", key, value));
	} else {
		DebugDo(printf("set(fatal error): %s\n", key));
	}
	return ret;
}

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

int func2(const void *key, const int keylen, const void *data, const int size) {
	printf("key: %s, data: %d\n", (char*)key, *(int*)data);
	return 0;
}

int main(void) {
	
	LPHashTable htable = newHashTable(1024, NULL, NULL);
	int v = 0;
	
	if (htable == NULL) {
		printf("init Hashtable(fatal error)\n");
	}
	
	addIntIntoHashTable(htable, "foo", 111);
	addIntIntoHashTable(htable, "bar", 222);
	addIntIntoHashTable(htable, "baz", 333);
	addIntIntoHashTable(htable, "fuga", 987);
	addIntIntoHashTable(htable, "piyo", 654);
	
	if (htable) {
		printf("cnt: %d\n", htable->count);
	}
	printf("cnt: %d\n", countDataInHashTable(htable));

	addIntIntoHashTable(htable, "hoge", 123);
	addIntIntoHashTable(htable, "hoge", 246);
	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);

	getIntFromHashTable(htable, "baz", &v);
	printf("get: %d\n", v);

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

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

	if (htable) { /* 非公開関数なので内部にエラートラップが無い */
		printf("sch: %d\n", (int)searchPlace(htable, "hoge", 5));
		printf("sch: %d\n", (int)searchPlace(htable, "abc", 4));
		printf("*sch: %d\n", (int)*searchPlace(htable, "hoge", 5));
		printf("*sch: %d\n", (int)*searchPlace(htable, "abc", 4));
		if (*searchPlace(htable, "hoge", 5)) {
			printf("*sch-d: %d\n", *(int*)(*searchPlace(htable, "hoge", 5))->data);
		}
		if (*searchPlace(htable, "bar", 4)) {
			printf("*sch-d: %d\n", *(int*)(*searchPlace(htable, "bar", 4))->data);
		}
	}

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

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

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

/**
 * 新しいHashTableを作る。
 * @param tablesize
 * @param keycmp
 * @param hash
 * @return
 */
LPHashTable newHashTable(const int tablesize, 
		int (*keycmp)(const void *key1, const int key1len, const void *key2, const int key2len),
		int (*hash)(const void *key, const int keylen, 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;
	if (keycmp == NULL) {
		htable->keycmp = defaultKeycmp;
	} else {
		htable->keycmp = keycmp;
	}
	if (hash == NULL) {
		htable->hash = defaultHash;
	} else {
		htable->hash = hash;
	}
	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 keylen
 * @param data
 * @param size
 * @return
 */
int addDataIntoHashTable(LPHashTable htable, const void *key, const int keylen, const void *data, const int size) {
	LPTableData *ptbdata;
	if (htable == NULL || key == NULL || data == NULL || size < 1 || keylen < 1) {
		return 0; /* 引数エラー */
	}
	ptbdata = searchPlace(htable, key, keylen);
	if (*ptbdata == NULL) {
		*ptbdata = (LPTableData)Calloc(1, sizeof(TableData));
		if (*ptbdata == NULL) {
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->key = Malloc(keylen);
		if ((*ptbdata)->key == NULL) {
			Free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->data = Malloc(size);
		if ((*ptbdata)->data == NULL) {
			Free((*ptbdata)->key);
			Free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		memcpy((*ptbdata)->key, key, keylen);
		(*ptbdata)->keylen = keylen;
		memcpy((*ptbdata)->data, data, size);
		(*ptbdata)->size = size;
		++(htable->count);
		return 1; /* 成功 */
	}
	return 2; /* キー名重複 */
}

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

/**
 * HashTableにデータを書き込む。既にキー名のデータがある場合は上書きする。
 * @param htable
 * @param key
 * @param keylen
 * @param data
 * @param size
 * @return
 */
int setDataIntoHashTable(LPHashTable htable, const void *key, const int keylen, const void *data, const int size) {
	int ret = 1;
	void *temp;
	LPTableData *ptbdata;
	if (htable == NULL || key == NULL || data == NULL || size < 1 || keylen < 1) {
		return 0; /* 引数エラー */
	}
	ptbdata = searchPlace(htable, key, keylen);
	if (*ptbdata == NULL) {
		*ptbdata = (LPTableData)Calloc(1, sizeof(TableData));
		if (*ptbdata == NULL) {
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->key = Malloc(keylen);
		if ((*ptbdata)->key == NULL) {
			Free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		(*ptbdata)->data = Malloc(size);
		if ((*ptbdata)->data == NULL) {
			Free((*ptbdata)->key);
			Free(*ptbdata);
			*ptbdata = NULL;
			return 0; /* メモリ確保失敗 */
		}
		memcpy((*ptbdata)->key, key, keylen);
		(*ptbdata)->keylen = keylen;
		(*ptbdata)->size = size;
		++(htable->count);
	} else {
		if ((*ptbdata)->size != size) {
			temp = Realloc((*ptbdata)->data, size);
			if (temp == NULL) {
				return 0; /* メモリ確保失敗 */
			}
			(*ptbdata)->data = temp;
			(*ptbdata)->size = size;
		}
		ret = 2;
	}
	memcpy((*ptbdata)->data, data, size);
	return ret;
}

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

/**
 * HashTable内にキー名のデータが存在するか書くにする。
 * @param htable HashTable。
 * @param key    探すキー名。
 * @param keylen
 * @return 存在すれば(1)、存在しなければ(0)。
 */
int existKeyInHashTable(LPHashTable htable, const void *key, const int keylen) {
	if (htable == NULL || key == NULL || keylen < 1) {
		return 0; /* ぬるぽ */
	}
	return *searchPlace(htable, key, keylen) != 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 void *key, const int keylen)) {
	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, tbdata->keylen);
			if (ret) {
				DebugDo(printf("allkey(stop)\n"));
				return 2;
			}
			tbdata = tbdata->next;
		}
		++ptbdata;
	}
	DebugDo(printf("allkey(done)\n"));
	return 1;
}

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

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

/**
 * キーの比較。
 * @param key1
 * @param key1len
 * @param key2
 * @param key2len
 * @return
 */
int defaultKeycmp(const void *key1, const int key1len, const void *key2, const int key2len) {
	if (key1len != key2len) {
		return key1len - key2len;
	}
	return memcmp(key1, key2, key1len);
}

/**
 * ハッシュ関数。キー名からハッシュ値を生成する。
 * @param key        キー名。
 * @param keylen
 * @param tablesize
 * @return ハッシュ値。
 */
int defaultHash(const void *key, const int keylen, const int tablesize) {
	int i;
	char *p = (char*)key;
	int v = (int)*p;
	int lm = keylen - 1;
	for (i = 0; i < HASH_DEEP && i < lm; i++) {
		v ^= (int)(*p) * (int)(*(p + 1));
		++p;
	}
	return v;
}

/**
 * ハッシュ値を取得する。
 * @param htable
 * @param key
 * @param keyleln
 */
int getHash(const LPHashTable htable, const void *key, const int keylen) {
	int h = (*(htable->hash))(key, keylen, htable->tablesize);
	if (h < 0) {
		h = ~h;
	}
	return h % htable->tablesize;
}

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