/* 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;
}
