/**
 * @file  kc_map.c
 * @brief マップモジュール
 * @copyright  2003 - 2023  Nomura Kei
 */
#include <stdlib.h>
#include <string.h>

#include <kc_lock_guard.h>
#include <kc_memory.h>
#include <kc_map.h>

#define KC_MAP_CAPACITY_MAX (65536)

/**
 * KcMapEntry 情報
 */
typedef struct KcMapEntry_
{
	char *key;				  //!< キー
	size_t key_size;		  //!< キーのためのメモリ割り当てサイズ
	void *value;			  //!< 値
	size_t size;			  //!< 値のサイズ
	struct KcMapEntry_ *next; //!< 次のエントリへのポインタ
	struct KcMapEntry_ *prev; //!< 一つ前のエントリへのポインタ
} KcMapEntry;

/**
 * KcMap 管理情報
 */
typedef struct
{
	mtx_t mutex;		//!< ロック用
	KcMapEntry **table; //!< ハッシュ用テーブル
	size_t table_size;	//!< ハッシュ用テーブルサイズ
	size_t size;		//!< 要素数
} KcMapInfo;

// =============================================================================
//  プロトタイプ宣言
// =============================================================================

static size_t KcMap_size(struct KcMap_ *map);
static void *KcMap_put(struct KcMap_ *map, const char *key, const void *obj, size_t size);
static void *KcMap_get(struct KcMap_ *map, const char *key, size_t *size);
static void KcMap_remove(struct KcMap_ *map, const char *key);
static void KcMap_clear(struct KcMap_ *map);
static void KcMap_entries(struct KcMap_ *map, bool (*handler)(const char *key, const void *val, size_t size, void *args), void *args);
static size_t KcMap_capacity(size_t cap);
static KcMapEntry *KcMapEntry_new(const char *key, const void *obj, size_t size);
static size_t KcMapEntry_key_size(const char *key);
static KcMapEntry *KcMapEntry_search(KcMapInfo *info, const char *key);

/**
 * マップ を構築します。
 *
 * @return cap マップのキー管理容量
 */
KcMap *KcMap_new(size_t cap)
{
	// KcMap の管理構造
	// +--------------+
	// | KcMap        |
	// |  ...         |
	// |  _info  -----------+
	// +--------------+     |
	// | <_info>      | <---+
	// | **table -----------+
	// | table_size   |     |
	// +--------------+     |
	// | <table>      | <---+
	// |              |
	// +--------------+
	size_t new_cap = KcMap_capacity(cap);
	KcMap *map = (KcMap *)malloc(
		sizeof(KcMap) + sizeof(KcMapInfo) + (sizeof(KcMapEntry) * new_cap));
	if (map != NULL)
	{
		map->size = KcMap_size;
		map->put = KcMap_put;
		map->get = KcMap_get;
		map->remove = KcMap_remove;
		map->clear = KcMap_clear;
		map->entries = KcMap_entries;
		map->_info = (map + 1);

		KcMapInfo *info = (KcMapInfo *)map->_info;
		info->table = (KcMapEntry **)(info + 1);
		info->table_size = new_cap;
		for (int i = 0; i < (int)new_cap; i++)
		{ // Table 初期化
			info->table[i] = NULL;
		}

		mtx_init(&(info->mutex), mtx_plain | mtx_recursive);
		info->size = 0;
	}
	return map;
}

/**
 * マップを破棄します。
 * @param map 破棄するマップ
 */
void KcMap_delete(KcMap *map)
{
	map->clear(map);
	free(map);
}

/**
 * 指定されたキーに対応するハッシュコードを返します。
 */
int KcMap_hash_code(const char *key)
{
	int code = 0;
	const char *ch = key;
	while (*ch != '\0')
	{
		code = code * 31 + *ch;
		ch++;
	}
	return code;
}

/**
 * マップに格納されている要素の数を返します。
 *
 * @param map 対象マップ
 * @return 要素の数
 */
static size_t KcMap_size(struct KcMap_ *map)
{
	KcMapInfo *info = (KcMapInfo *)map->_info;
	int size = -1;
	kc_lock_guard(&(info->mutex))
	{
		size = info->size;
	}
	return size;
}

/**
 * マップに要素を追加します。
 * オブジェクトはコピーして追加されます。
 * 追加に失敗した場合、NULL が返されます。
 *
 * @param map  対象マップ
 * @param key  キー
 * @param obj  キーに対応するオブジェクト
 * @param size オブジェクトのサイズ
 * @return 追加したオブジェクトへのポインタ
 */
static void *KcMap_put(struct KcMap_ *map, const char *key, const void *obj, size_t size)
{
	KcMapInfo *info = (KcMapInfo *)map->_info;
	int hash = KcMap_hash_code(key);
	KcMapEntry *entry = KcMapEntry_new(key, obj, size);
	if (entry != NULL)
	{
		kc_lock_guard(&(info->mutex))
		{ // 既に同じキーが登録されている場合、一度削除する。
			map->remove(map, key);

			// table_size は 2のべき乗
			// => -1 した値は、その値を上限として全てのビットが立つ。
			// 例) 8 -> (8-1) = 0b00000111
			// AND を取ると hash は、0-7 のテーブルのインデックス範囲となる。
			hash = hash & (info->table_size - 1);

			KcMapEntry *tmp_entry = info->table[hash];
			if (tmp_entry == NULL)
			{ // テーブルに入っていないため、先頭に設定
				info->table[hash] = entry;
				info->size++;
			}
			else
			{
				while (tmp_entry->next != NULL)
				{ // テーブルの先のリンクがなくなるまでたどる
					tmp_entry = tmp_entry->next;
				}
				tmp_entry->next = entry;
				entry->prev = tmp_entry;
				info->size++;
			}
		}
		return entry->value;
	}
	else
	{
		return NULL;
	}
}

/**
 * 指定されたキーに対応するオブジェクトを取得します。
 * オブジェクトは参照が渡されます。
 * size が NULL でない場合、取得されたオブジェクトのサイズが格納されます。
 *
 * @param map  対象マップ
 * @param key  キー
 * @param size オブジェクトのサイズ
 * @return オブジェクトへのポインタ
 */
static void *KcMap_get(struct KcMap_ *map, const char *key, size_t *size)
{
	KcMapInfo *info = (KcMapInfo *)map->_info;
	void *res_obj = NULL;
	kc_lock_guard(&(info->mutex))
	{
		KcMapEntry *entry = KcMapEntry_search(info, key);
		if (entry != NULL)
		{
			if (size)
			{
				*size = entry->size;
			}
			res_obj = entry->value;
		}
	}
	return res_obj;
}

/**
 * 指定されたキーに対応するオブジェクトを削除します。
 *
 * @param map  対象マップ
 * @param key  キー
 */
static void KcMap_remove(struct KcMap_ *map, const char *key)
{
	KcMapInfo *info = (KcMapInfo *)map->_info;
	kc_lock_guard(&(info->mutex))
	{
		// 指定されたキーに対応するエントリを探す。
		KcMapEntry *remove_entry = KcMapEntry_search(info, key);
		if (remove_entry != NULL)
		{
			if (remove_entry->prev)
			{ // 削除対象がテーブルの先のリストにある
				remove_entry->prev->next = remove_entry->next;
				if (remove_entry->next)
				{
					remove_entry->next->prev = remove_entry->prev;
				}
			}
			else
			{ // 削除対象が table の配列要素
				int hash = KcMap_hash_code(key);
				hash = hash & (info->table_size - 1);
				info->table[hash] = remove_entry->next;
				if (remove_entry->next)
				{
					remove_entry->next->prev = NULL;
				}
			}
			free(remove_entry);
			info->size--;
		}
	}
}

/**
 * マップ内のすべての要素を対象リストから削除します。
 *
 * @param list 対象リスト
 */
static void KcMap_clear(struct KcMap_ *map)
{
	KcMapInfo *info = (KcMapInfo *)map->_info;
	kc_lock_guard(&(info->mutex))
	{
		KcMapEntry *tmp_entry;
		for (int i = 0; i < (int)info->table_size; i++)
		{
			for (KcMapEntry *entry = info->table[i]; entry != NULL; entry = tmp_entry)
			{
				tmp_entry = entry->next;
				free(entry);
			}
			info->table[i] = NULL;
		}
		info->size = 0;
	}
}

/**
 * マップに格納されている要素を引数に、指定されたハンドラを実行します。
 * ハンドラ関数が false を返す場合、呼出し処置は中断されます。
 *
 * @param map 対象マップ
 * @param handler ハンドラ関数
 * @param args ハンドラ関数に渡されるユーザーデータ
 */
static void KcMap_entries(struct KcMap_ *map, bool (*handler)(const char *key, const void *val, size_t size, void *args), void *args)
{
	KcMapInfo *info = (KcMapInfo *)map->_info;
	kc_lock_guard(&(info->mutex))
	{
		bool is_continue = true;
		for (int i = 0; (i < (int)info->table_size) && is_continue; i++)
		{
			for (KcMapEntry *entry = info->table[i]; (entry != NULL && is_continue); entry = entry->next)
			{
				is_continue = handler(entry->key, entry->value, entry->size, args);
			}
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
//
// [内部関数]
//

/**
 * 指定された容量を 2 のべき乗に揃えます。
 * cap に 0 または、 KC_MAP_CAPACITY_MAX より大きい値が指定された場合、
 * KC_MAP_CAPACITY_MAP の容量となります。
 *
 * @param cap 容量
 * @return 調整された容量
 */
static size_t KcMap_capacity(size_t cap)
{
	size_t new_cap = 1;
	if ((cap < 1) || (KC_MAP_CAPACITY_MAX < cap))
	{
		new_cap = KC_MAP_CAPACITY_MAX;
	}
	else
	{
		while (new_cap < cap)
		{
			new_cap <<= 1;
		}
	}
	return new_cap;
}

/**
 * KcMapEntry を生成します。
 * 生成に失敗した場合、NULL を返します。
 *
 * @param key キー
 * @param obj 値
 * @param size 値のサイズ
 * @return 生成された KeyMapEntry
 */
static KcMapEntry *KcMapEntry_new(const char *key, const void *obj, size_t size)
{
	// KcMapEntry の構成
	// +--------------+
	// | <KcMapEntry> |
	// | key -------------+
	// | value -----------|--+
	// | size         |   |  |
	// | next         |   |  |
	// +--------------+   |  |
	// | <key>        |<--+  |
	// | <value>      |<-----+
	// +--------------+
	size_t key_size = KcMapEntry_key_size(key);
	size_t new_size = sizeof(KcMapEntry) + key_size + size;
	KcMapEntry *entry = (KcMapEntry *)malloc(new_size);
	if (entry != NULL)
	{
		entry->key = (char *)(entry + 1);
		entry->key_size = key_size;
		entry->value = &entry->key[entry->key_size];
		entry->size = size;
		entry->next = NULL;
		entry->prev = NULL;
		strncpy(entry->key, key, entry->key_size);
		memcpy(entry->value, obj, size);
	}
	return entry;
}

/**
 * キーのメモリ割り当てサイズを取得します。
 * キーのメモリ割り当ては、ポインタの整数倍に揃えられます。
 *
 * @param key キー
 * @return キーのメモリ割り当てサイズ
 */
static size_t KcMapEntry_key_size(const char *key)
{
	size_t size = strlen(key) + 1;
	int nmemb = size / sizeof(void *);
	return (sizeof(void *) * (nmemb + 1));
}

/**
 * 指定されたキーに対応するエントリを取得します。
 *
 * @param info マップ情報
 * @param key キー
 * @return キーに対応するエントリ
 */
static KcMapEntry *KcMapEntry_search(
	KcMapInfo *info, const char *key)
{
	int hash = KcMap_hash_code(key);
	hash = hash & (info->table_size - 1);
	KcMapEntry *entry = (info->table)[hash];
	while (entry != NULL)
	{
		if (strcmp(entry->key, key) == 0)
		{ // キーが一致
			break;
		}
		entry = entry->next;
	}
	return entry;
}