/*
 *	ght_hash_table.c
 *
 *	Generic Hash Table (GHT)
 *
 *	* Sat Jun 06 15:36:36 JST 2015 Naoyuki Sawa
 *	- 1st リリース。
 *	- 「libghthash - Generic Hash Table (GHT)」(http://www.bth.se/people/ska/sim_home/libghthash.html)互換モジュールです。
 *	  関数仕様はlibghthashと同じで、実装は独自です。
 *	  オリジナル版のlibghthashは速度性能を重視して実装されているようですが、当実装は省メモリを優先して単純に実装しました。
 *	- 関数仕様や使用例は、オリジナル版のlibghthashのドキュメントを参照してください。
 *	  オリジナル版のlibghthashを、/clip/tool/libghthash.7z に保存しておきました。
 *	* Sun Jul 12 21:50:47 JST 2015 Naoyuki Sawa
 *	- ght_set_rehash(),ght_rehash()を対応しました。
 *	  速度性能を重視しない方針でこれらの関数には対応していませんでしたが、メモリ効率が改善するために対応する事にしました。
 *	  これまでは、ght_create()の引数に有る程度大きな値を指定する必要が有り、実際の要素数が少ない時に無駄が生じていました。
 *	  今後は、常に'ght_create(0);ght_set_rehash(p_ht,1)'で良く、要素数の増減に応じて自動的にテーブルサイズが調整されます。
 */
#include "clip.h"
/****************************************************************************
 *	ローカル関数
 ****************************************************************************/
static int ght_get_hash_value(ght_hash_table_t* p_ht, int i_key_size, const void* p_key_data) {
	return (unsigned)one_at_a_time_hash(p_key_data, i_key_size) % (unsigned)p_ht->i_table_size;
}
/*--------------------------------------------------------------------------*/
//Search for an element in a bucket.
static ght_hash_entry_t* ght_search_in_bucket(ght_hash_table_t* p_ht, int i_key_size, const void* p_key_data) {
	int l_key = ght_get_hash_value(p_ht, i_key_size, p_key_data);
	LIST_ENTRY* list_head = &p_ht->le_bucket[l_key];
	LIST_ENTRY* list_entry = list_head->Flink;
	while(list_entry != list_head) {
		ght_hash_entry_t* p_e = CONTAINING_RECORD(list_entry, ght_hash_entry_t, le_bucket);
		if((p_e->i_key_size == i_key_size) && !memcmp(p_e->key_data, p_key_data, i_key_size)) { return p_e; }
		list_entry = list_entry->Flink;
	}
	return NULL;
}
/*--------------------------------------------------------------------------*/
static void ght_check_rehash(ght_hash_table_t* p_ht) {
	if(p_ht->flag.b_rehash) {
		//現在の要素数を取得する。ただし、要素数が(0)の場合は(1)として、以下の計算を行う。
		int i_size = ght_size(p_ht);
		if(!i_size) { i_size = 1; }
		//現在のテーブルサイズが、要素数の半分未満,又は,二倍超過ならば、要素数に合わせる。
		if((p_ht->i_table_size < (i_size / 2)) ||
		   (p_ht->i_table_size > (i_size * 2))) { ght_rehash(p_ht, i_size); }
		//以上の処理によって、テーブルサイズが要素数の半分以上〜二倍以下の範囲に追従する。
	}
}
/****************************************************************************
 *	グローバル関数
 ****************************************************************************/
//Create a new hash table.
ght_hash_table_t* ght_create(int i_table_size) {
	ght_hash_table_t* p_ht;
	p_ht = calloc(sizeof(ght_hash_table_t), 1);
	if(!p_ht) { DIE(); }
	InitializeListHead(&p_ht->le_iterator);
	ght_rehash(p_ht, i_table_size);
	return p_ht;
}
/*--------------------------------------------------------------------------*/
//Get the number of items in the hash table.
int ght_size(ght_hash_table_t* p_ht) {
	ght_iterator_t iterator;
	void* p_entry_data;
	const void* p_key_data;
	int i_size = 0;
	for(p_entry_data = ght_first(p_ht, &iterator, &p_key_data);
	    p_entry_data;
	    p_entry_data = ght_next( p_ht, &iterator, &p_key_data)) { i_size++; }
	return i_size;
}
/*--------------------------------------------------------------------------*/
//Get the size of the hash table.
int ght_table_size(ght_hash_table_t* p_ht) {
	return p_ht->i_table_size;
}
/*--------------------------------------------------------------------------*/
//Insert an entry into the hash table.
int ght_insert(ght_hash_table_t* p_ht, void* p_entry_data, int i_key_size, const void* p_key_data) {
	ght_hash_entry_t* p_e;
	int l_key;
	if(!p_entry_data) { DIE(); }
	if(ght_get(p_ht, i_key_size, p_key_data)) { return -1; }	//Don't insert if the key is already present.
	p_e = calloc(sizeof(ght_hash_entry_t) + i_key_size, 1);
	if(!p_e) { DIE(); }
	InsertTailList(&p_ht->le_iterator, &p_e->le_iterator);
	l_key = ght_get_hash_value(p_ht, i_key_size, p_key_data);
	InsertTailList(&p_ht->le_bucket[l_key], &p_e->le_bucket);
	p_e->p_entry_data = p_entry_data;
	p_e->i_key_size = i_key_size;
	memcpy(p_e->key_data, p_key_data, i_key_size);
	ght_check_rehash(p_ht);
	return 0;
}
/*--------------------------------------------------------------------------*/
//Get an entry from the hash table.
void* ght_get(ght_hash_table_t* p_ht, int i_key_size, const void* p_key_data) {
	ght_hash_entry_t* p_e;
	p_e = ght_search_in_bucket(p_ht, i_key_size, p_key_data);
	if(!p_e) { return NULL; }
	return p_e->p_entry_data;
}
/*--------------------------------------------------------------------------*/
//Replace an entry from the hash table.
void* ght_replace(ght_hash_table_t* p_ht, void* p_entry_data, int i_key_size, const void* p_key_data) {
	ght_hash_entry_t* p_e;
	void* p_old_data;
	p_e = ght_search_in_bucket(p_ht, i_key_size, p_key_data);
	if(!p_e) { return NULL; }
	p_old_data = p_e->p_entry_data;
	p_e->p_entry_data = p_entry_data;
	return p_old_data;
}
/*--------------------------------------------------------------------------*/
//Remove an entry from the hash table.
void* ght_remove(ght_hash_table_t* p_ht, int i_key_size, const void* p_key_data) {
	ght_hash_entry_t* p_e;
	void* p_old_data;
	p_e = ght_search_in_bucket(p_ht, i_key_size, p_key_data);
	if(!p_e) { return NULL; }
	RemoveEntryList(&p_e->le_iterator);
	RemoveEntryList(&p_e->le_bucket);
	p_old_data = p_e->p_entry_data;
	free(p_e);
	ght_check_rehash(p_ht);
	return p_old_data;
}
/*--------------------------------------------------------------------------*/
//Get the first entry in an iteration.
void* ght_first(ght_hash_table_t* p_ht, ght_iterator_t* p_iterator, const void** pp_key_data) {
	int i_key_size;
	return ght_first_keysize(p_ht, p_iterator, pp_key_data, &i_key_size);
}
void* ght_first_keysize(ght_hash_table_t* p_ht, ght_iterator_t* p_iterator, const void** pp_key_data, int* p_key_size) {
	LIST_ENTRY* list_head = &p_ht->le_iterator;
	LIST_ENTRY* list_entry = list_head->Flink;
	p_iterator->le_next = list_entry;
	return ght_next_keysize(p_ht, p_iterator, pp_key_data, p_key_size);
}
/*--------------------------------------------------------------------------*/
//Get the next entry in an iteration.
void* ght_next(ght_hash_table_t* p_ht, ght_iterator_t* p_iterator, const void** pp_key_data) {
	int i_key_size;
	return ght_next_keysize(p_ht, p_iterator, pp_key_data, &i_key_size);
}
void* ght_next_keysize(ght_hash_table_t* p_ht, ght_iterator_t* p_iterator, const void** pp_key_data, int* p_key_size) {
	LIST_ENTRY* list_head = &p_ht->le_iterator;
	LIST_ENTRY* list_entry = p_iterator->le_next;
	if(list_entry != list_head) {
		ght_hash_entry_t* p_e = CONTAINING_RECORD(list_entry, ght_hash_entry_t, le_iterator);
		p_iterator->le_next = list_entry->Flink;											//イテレータは次のノードを指しているので、イテレーションの中で当該ノードをght_remove()しても安全です。
		*pp_key_data = p_e->key_data;
		*p_key_size = p_e->i_key_size;
		return p_e->p_entry_data;
	}
	return NULL;
}
/*--------------------------------------------------------------------------*/
//Finalize (free) a hash table.
void ght_finalize(ght_hash_table_t* p_ht) {
	ght_iterator_t iterator;
	void* p_entry_data;
	const void* p_key_data;
	int i_key_size;
	for(p_entry_data = ght_first_keysize(p_ht, &iterator, &p_key_data, &i_key_size);
	    p_entry_data;
	    p_entry_data = ght_next_keysize( p_ht, &iterator, &p_key_data, &i_key_size)) { ght_remove(p_ht, i_key_size, p_key_data); }		//イテレータは次のノードを指しているので、イテレーションの中で当該ノードをght_remove()しても安全です。
	free(p_ht->le_bucket);
	free(p_ht);
}
/*--------------------------------------------------------------------------*/
//Set the rehashing status of the table.
void ght_set_rehash(ght_hash_table_t* p_ht, int b_rehash) {
	p_ht->flag.b_rehash = b_rehash;
}
/*--------------------------------------------------------------------------*/
//Rehash the hash table.
void ght_rehash(ght_hash_table_t* p_ht, int i_table_size) {
	LIST_ENTRY* list_head = &p_ht->le_iterator;
	LIST_ENTRY* list_entry = list_head->Flink;
	int i, l_key;
	//Reallocate the new bucket with the new size.
	if(i_table_size < 1) { i_table_size = 1; }
	p_ht->i_table_size = i_table_size;
	p_ht->le_bucket = realloc(p_ht->le_bucket, sizeof(LIST_ENTRY) * i_table_size);
	if(!p_ht->le_bucket) { DIE(); }
	for(i = 0; i < i_table_size; i++) { InitializeListHead(&p_ht->le_bucket[i]); }
	//Walk through all elements in the table and insert them into the new bucket.
	while(list_entry != list_head) {
		ght_hash_entry_t* p_e = CONTAINING_RECORD(list_entry, ght_hash_entry_t, le_iterator);
		l_key = ght_get_hash_value(p_ht, p_e->i_key_size, p_e->key_data);
		InsertTailList(&p_ht->le_bucket[l_key], &p_e->le_bucket);
		list_entry = list_entry->Flink;
	}
}
