/* vim: ts=4 sw=4 sts=4 ff=unix fenc=utf-8 :
 * =====================================================================
 *  sc_map.c
 *  Copyright (c)  2003 - 2011  sys0tem
 *  LICENSE :
 *	LGPL (GNU Lesser General Public License - Version 3,29 June 2007)
 *	http://www.gnu.org/copyleft/lesser.html
 *	or
 *	EPL (Eclipse Public License - v1.0)
 *	http://www.eclipse.org/legal/epl-v10.html
 * =====================================================================
 */
#include <string.h>
#include <sc_os.h>
#include <sc_error.h>
#include <sc_mmgr.h>
#include <sc_list.h>
#include <sc_map.h>


#define SC_MAP_CAPACITY_MAX (65536)


/* ---------------------------------------------------------------------
 *  プロトタイプ宣言
 * ---------------------------------------------------------------------
 */
static void* SC_Map_put(SC_Map* map, const char* key, const void* obj, size_t size);
static void* SC_Map_get(SC_Map* map, const char* key, size_t* size);
static char* SC_Map_putStr(SC_Map* map, const char* key, const char* obj);
static char* SC_Map_getStr(SC_Map* map, const char* key);
static void  SC_Map_remove(SC_Map* map, const char* key);
static void  SC_Map_clear(SC_Map* map);
static void  SC_Map_entries(SC_Map* map, bool (*handler)(char* key, void* val, size_t size));

static size_t SC_Map_capacity(size_t cap);
static SC_Map_Entry* SC_Map_newEntry(const char* key, const void* obj, size_t size);
static SC_Map_Entry* SC_Map_search(SC_Map* map, const char* key);
static SC_Map_Entry* SC_Map_searchPrev(SC_Map* map, const char* key, int* hash);

/**
 * SC_Map を生成します。
 * Map の生成に失敗した場合、NULL を返します。
 *
 * @param  cap ハッシュテーブルサイズ
 * @return SC_Map
 */
/* メモリ配置は以下のとおり。
 * +--------------------------------+
 * | SC_Map      : Map 構造愛       |
 * | _table[cap] : ハッシュテーブル |
 * +--------------------------------+
 */
SC_Map* SC_Map_new(size_t cap)
{
	SC_Map*      map;
	size_t       i;
	size_t       size;
	size_t       newCap = SC_Map_capacity(cap);

	size = sizeof(SC_Map) + (sizeof(SC_Map_Entry) * newCap);
	map  = (SC_Map*) malloc(size);
	if (map == NULL)
	{	/* メモリ確保失敗	*/
		return NULL;
	}

	map->_table   = (SC_Map_Entry**)(map + 1);
	for (i = 0; i < newCap; i++)
	{	/* NULL に初期化	*/
		map->_table[i] = NULL;
	}
	map->_tblSize = newCap;
	map->size     = 0;
	map->put      = SC_Map_put;
	map->putStr   = SC_Map_putStr;
	map->get      = SC_Map_get;
	map->getStr   = SC_Map_getStr;
	map->remove   = SC_Map_remove;
	map->clear    = SC_Map_clear;
	map->entries  = SC_Map_entries;
	return map;
}


/**
 * マップを破棄します。
 * [注意] 参照していた値も破棄されます。
 *
 * @param map マップ
 */
void SC_Map_delete(SC_Map* map)
{
	map->clear(map);
	free(map);
}


/**
 * 指定された文字列のハッシュコードを生成して返します。
 *
 * @paam key 文字列
 * @return ハッシュコード
 */
int SC_Map_hashCode(const char* key)
{
	int         code = 0;
	const char* c    = key;
	while (*c != '\0')
	{
		code = code * 31 + *c;
		c++;
	}
	return code;
}

/* ---------------------------------------------------------------------
 *  以下、内部でのみ使用する関数
 * ---------------------------------------------------------------------
 */

/**
 * マップに、キーとオブジェクトを追加します。
 * オブジェクトはコピーされ、マップに保持されます。
 * メモリの確保に失敗した場合、エラーコード SC_ENOMEM がセットされ、
 * NULL が返されます。
 *
 * @param map マップ
 * @param key キー
 * @param obj キーに対応するオブジェクト
 * @param size 値のサイズ
 * @return 追加したオブジェクト
 */
static
void* SC_Map_put(SC_Map* map, const char* key, const void* obj, size_t size)
{
	SC_Map_Entry* entry;
	SC_Map_Entry* tmpEntry;
	int           hash = SC_Map_hashCode(key);

	/* エントリ生成	*/
	entry = SC_Map_newEntry(key, obj, size);
	if (entry == NULL)
	{	/* メモリ確保失敗	*/
		return NULL;
	}

	/* 既に同じキーが登録されている場合、一度削除する	*/
	map->remove(map, key);

	/* _tblSize が 2 のべき乗のため、-1 した値は
	 * その値を上限としてすべてのビットがたつ。
	 * 例) 8 -> (8-1) = 0b00000111
	 *     ANDをとると、hash は 0～7 の範囲となる。
	 */
	hash     = hash & (map->_tblSize - 1);
	tmpEntry = map->_table[hash];
	if (tmpEntry == NULL)
	{	/* テーブルに入っていないので、テーブルの先頭に設定	*/
		map->_table[hash] = entry;
		map->size++;
		return entry->value;
	}

	/* 既にテーブルが埋まっている⇒リンクをたどる */
	while (tmpEntry->next != NULL)
	{
		tmpEntry = tmpEntry->next;
	}
	tmpEntry->next = entry;
	map->size++;
	return entry->value;
}


/**
 * マップより、指定されたキーに対応する値を取得します。
 * size が NULL 出ない場合、取得した値のサイズが格納されます。
 * キーに対応する値がない場合、NULL が返されます。
 *
 * @param map マップ
 * @param key キー
 * @param size 取得した値のサイズ格納用
 * @return 値
 */
static
void* SC_Map_get(SC_Map* map, const char* key, size_t* size)
{
	SC_Map_Entry* entry;

	entry = SC_Map_search(map, key);
	if (entry == NULL)
	{	/* 見つからない	*/
		return NULL;
	}

	if (size != NULL)
	{	/* size が NULL でない場合、サイズを設定する	*/
		*size = entry->size;
	}
	return entry->value;
}


/**
 * マップに、キーと文字列を追加します。
 * 文字列はコピーされ、マップに保持されます。
 * メモリの確保に失敗した場合、エラーコード SC_ENOMEM がセットされ、
 * NULL が返されます。
 *
 * @param map マップ
 * @param key キー
 * @param obj キーに対応する文字列
 * @return 追加した文字列
 */
static
char* SC_Map_putStr(SC_Map* map, const char* key, const char* obj)
{
	size_t size = strlen(obj) + 1;	/* 文字列長 + '\0'	*/
	return map->put(map, key, obj, size);
}


/**
 * マップより、指定されたキーに対応する文字列を取得します。
 * キーに対応する値がない場合、NULL が返されます。
 *
 * @param map マップ
 * @param key キー
 * @return 文字列
 */
static
char* SC_Map_getStr(SC_Map* map, const char* key)
{
	return (char*) map->get(map, key, NULL);
}


/**
 * マップより、指定されたキーに対応する値を削除します。
 * キーに対応する値がない場合なにもしません。
 *
 * @param map マップ
 * @param key キー
 */
static
void  SC_Map_remove(SC_Map* map, const char* key)
{
	int hash;
	SC_Map_Entry* entry;
	SC_Map_Entry* delEntry;

	entry = SC_Map_searchPrev(map, key, &hash);

	if (hash == -1)
	{	/* 対応するエントリなし	*/
		return;
	}

	if (entry == NULL)
	{	/* _table の配列要素	*/
		delEntry = map->_table[hash];
		map->_table[hash] = delEntry->next;
	}
	else
	{
		delEntry    = entry->next;
		entry->next = delEntry->next;
	}
	free(delEntry);
	map->size--;
}


/**
 * マップをクリアします。
 */
static
void  SC_Map_clear(SC_Map* map)
{
	size_t i;
	SC_Map_Entry* entry;
	SC_Map_Entry* next;
	for (i = 0; i < map->_tblSize; i++)
	{
		if (map->_table[i] != NULL)
		{
			entry = map->_table[i];
			next  = map->_table[i]->next;
			while (entry != NULL)
			{
				free(entry);
				entry = next;
				if (next != NULL)
				{
					next = next->next;
				}
			}
			map->_table[i] = NULL;
		}
	}
	map->size = 0;
}


/**
 * マップに格納されている全エントリ分、
 * handler を呼び出します。
 * 途中で中断する場合は、handler の戻り値を false にしてください。
 *
 * @param map マップ
 * @param handler ハンドラ関数
 */
static
void  SC_Map_entries(SC_Map* map, bool (*handler)(char* key, void* val, size_t size))
{
	bool   isContinue;
	size_t i;
	SC_Map_Entry* entry;
	for (i = 0; i < map->_tblSize; i++)
	{
		if (map->_table[i] != NULL)
		{
			entry = map->_table[i];
			while (entry != NULL)
			{
				isContinue = handler(entry->key, entry->value, entry->size);
				if (!isContinue)
				{
					return;
				}
				entry     = entry->next;
			}
		}
	}
}


/**
 * 容量を 2 のべき乗にそろえます。
 * cap に 0、SC_MAP_CAPACITY_MAX より大きい値が
 * 指定された場合、SC_MAP_CAPACITY_MAX の容量となります。
 *
 * @param cap 容量
 * @return そろえられた容量
 */
static
size_t SC_Map_capacity(size_t cap)
{
	size_t newCap = 1;
	if ((cap < 1) || (SC_MAP_CAPACITY_MAX < cap))
	{
		newCap = SC_MAP_CAPACITY_MAX;
		return newCap;
	}
	while (newCap < cap)
	{
		newCap <<= 1;
	}
	return newCap;
}


/**
 * 新たな SC_Map_Entry を生成します。
 * 生成に失敗した場合 NULL を返します。
 *
 * @param key  キー
 * @param obj  値
 * @param size 値のサイズ
 * @return 新たな SC_Map_Entry
 */
/*
 * 生成される SC_Map_Entry のメモリマップは以下のようになる
 *  +----------------+
 *  | SC_Map_Entry   |
 *  | key  ->A       |
 *  | value->B       |
 *  | size           |
 *  | next ->NULL    |
 *  +----------------+
 * A| key            |
 *  +----------------+
 * B| value          |
 *  +----------------+
 */
static
SC_Map_Entry* SC_Map_newEntry(const char* key, const void* obj, size_t size)
{
	SC_Map_Entry* entry;
	size_t keySize = strlen(key) + 1;
	size_t newSize = size + sizeof(SC_Map_Entry) + keySize;

	entry = (SC_Map_Entry*) malloc(newSize);
	if (entry == NULL)
	{	/* メモリ確保失敗	*/
		return NULL;
	}

	/* 各値の設定 */
	entry->key   = (char*)(entry + 1);
	entry->value = &entry->key[keySize];
	entry->size  = size;
	entry->next  = NULL;
	strncpy(entry->key, key, keySize);
	memcpy(entry->value, obj, size);
	return entry;
}


/**
 * 指定されたキーに対応するエントリを取得します。
 *
 * @param map マップ
 * @param key キー
 */
static
SC_Map_Entry* SC_Map_search(SC_Map* map, const char* key)
{
	SC_Map_Entry* entry;
	int           hash;
	int           ret;

	hash  = SC_Map_hashCode(key);
	hash  = hash & (map->_tblSize - 1);
	entry = map->_table[hash];
	while (entry != NULL)
	{
		ret = strcmp(entry->key, key);
		if (ret == 0)
		{	/* キーが一致	*/
			return entry;
		}
		entry = entry->next;
	}
	return NULL;
}


/**
 * 指定されたキーのひとつ前のエントリを取得します。
 * キーに対応するエントリがない場合、hash に -1 が設定されます。
 * エントリが _table 配列内の要素の場合、NULL が返され、
 * hash にハッシュ値が設定されます。
 *
 * @param map  マップ
 * @param key  キー
 * @param hash ハッシュ値格納用
 * @return エントリ
 */
static
SC_Map_Entry* SC_Map_searchPrev(SC_Map* map, const char* key, int* hash)
{
	SC_Map_Entry* prev = NULL;
	SC_Map_Entry* entry;
	int           ret;

	*hash = SC_Map_hashCode(key);
	*hash = *hash & (map->_tblSize - 1);
	entry = map->_table[*hash];

	while (entry != NULL)
	{
		ret = strcmp(entry->key, key);
		if (ret == 0)
		{	/* キーが一致	*/
			return prev;
		}
		prev  = entry;
		entry = entry->next;
	}
	/* キーに該当するエントリなし	*/
	*hash = -1;
	return NULL;
}

