汎用的なハッシュテーブル作ってみた
いつもの通りデバッグしていないからまともに動くかわからんけど。
名前もコメントも適当だぜ！
詳しくは書かんが、GPhashFuncが汎用関数で、ChashFuncがカスタマイズ関数ですよー。
2012/5/20追記：Linuxで使ってみたら盛大に落ちる。配列Indexに-1を入れてら。修正途中です・・・。どういう設計だったか忘れたので、修正困難。
2012/5/25追記： 末尾にあるリンク先のプロジェクトは、一応修正できたと思う。
●GPhashFunc.h
#ifndef _GPHASHFUNC_H_
#define _GPHASHFUNC_H_
/* General Purpus Hash functions */
#include "hashDef.h"
typedef WORD (*HASHFUNC)(BYTE* hashKey, WORD hashKeyLen);
enum HASH_BUFF_FLAG{
HASH_BUFF_ACTIVE,
HASH_BUFF_DEACTIVE
};
/* hash buffer */
struct Hash_buff_t{
BYTE *hashKey;
SWORD backwardIndex;
SWORD forwardIndex;
BYTE activeFlag;
};
/* Hash custom manager */
struct Hash_CSTM_mng_t{
/* Hash Function */
WORD hashKeyLen;
HASHFUNC hash_func;
/* Hash Table */
WORD hashTblSize;
struct Hash_buff_t *hashTbl;
/* Hash Buffer */
WORD hashBuffListSize;
struct Hash_buff_t *hashBuffList;
BYTE *hashKeyBuff; /* sizeof hashKeyLen*hashBuffListSize */
};
/* hash manager */
struct Hash_mng_t{
struct Hash_CSTM_mng_t customHash;
/* Empty HashBuffer Index */
SWORD emptyHashBuff_head;
SWORD emptyHashBuff_tail;
};
/* function declare */
/* Initialize */
RESULT initHash(
struct Hash_mng_t *hashMng,
struct Hash_buff_t *hashTbl,
WORD HashTblSize,
struct Hash_buff_t *hashBuffList,
BYTE *hashKeyBuff,
WORD hashBuffListSize,
HASHFUNC hash_func,
WORD hashKeyLen
);
/* get Hash Value */
RESULT getHashValue(
struct Hash_mng_t *hashMng,
BYTE *hashKey,
WORD *hashValue
);
/* Regist Hash Value */
RESULT regHashValue(
struct Hash_mng_t *hashMng,
BYTE *hashKey, /* (in) Hash Key Array */
WORD *hashBuffIndex /* (out) Hash BuffIndex */
);
/* Deregist Hash Value */
RESULT deregHashValue(
struct Hash_mng_t *hashMng,
BYTE *hashKey, /* (in) Hash Key Array */
WORD *hashBuffIndex /* (out) Hash BuffIndex */
);
/* Get Hash Buffer Index from Hash Value */
RESULT getHashBuffIndex(
struct Hash_mng_t *hashMng,
BYTE *hashKey,
WORD *hashBuffIndex
);
#endif
●GPhashFunc.c
/* General Purpus Functions Definition */
#include <string.h>
#include "GPhashFunc.h"
/* function declare */
/*---inner functions-------------*/
static RESULT checkHasnMng(
struct Hash_mng_t *hashMng
){
RESULT result = COM_NG;
/* error check */
if(hashMng == NULL){
goto func_end;
}
/* Hash Function */
if(hashMng->customHash.hashKeyLen <= 0 ||
hashMng->customHash.hashKeyLen > SWORD_MAX){
goto func_end;
}
if(hashMng->customHash.hash_func == NULL){
goto func_end;
}
/* Hash Table */
if(hashMng->customHash.hashTblSize <= 0 ||
hashMng->customHash.hashTblSize > SWORD_MAX){
goto func_end;
}
if(hashMng->customHash.hashTbl == NULL){
goto func_end;
}
/* Hash Buffer */
if(hashMng->customHash.hashBuffListSize <= 0 ||
hashMng->customHash.hashBuffListSize > SWORD_MAX){
goto func_end;
}
if(hashMng->customHash.hashBuffList == NULL){
goto func_end;
}
result = COM_OK;
func_end:
return result;
}
/*---external functions-------------*/
/* Initialize */
RESULT initHash(
struct Hash_mng_t *hashMng,
struct Hash_buff_t *hashTbl,
WORD hashTblSize,
struct Hash_buff_t *hashBuffList,
BYTE *hashKeyBuff,
WORD hashBuffListSize,
HASHFUNC hash_func,
WORD hashKeyLen
){
WORD index = 0;
RESULT result = COM_NG;
/* Error Check */
if(hashMng == NULL){
goto func_end;
}
if(hash_func == NULL){
goto func_end;
}
if(hashKeyLen <= 0 ||
hashKeyLen > SWORD_MAX){
goto func_end;
}
if(hashTblSize <= 0 ||
hashTblSize > SWORD_MAX){
goto func_end;
}
if(hashTbl == NULL){
goto func_end;
}
if(hashBuffListSize <= 0 ||
hashBuffListSize > SWORD_MAX){
goto func_end;
}
if(hashBuffList == NULL){
goto func_end;
}
if(hashKeyBuff == NULL){
goto func_end;
}
/* Hash Function */
hashMng->customHash.hashKeyLen = hashKeyLen;
hashMng->customHash.hash_func = hash_func;
/* Hash Table */
hashMng->customHash.hashTblSize = hashTblSize;
hashMng->customHash.hashTbl = hashTbl;
/* Hash Buffer */
hashMng->customHash.hashBuffListSize = hashBuffListSize;
hashMng->customHash.hashBuffList = hashBuffList;
hashMng->customHash.hashKeyBuff = hashKeyBuff;
hashMng->emptyHashBuff_head = 0;
hashMng->emptyHashBuff_tail = hashBuffListSize-1;
/* set Hash Table first value */
for(index = 0; hashTblSize > index; index++){
hashMng->customHash.hashBuffList[index].forwardIndex = -1;
hashMng->customHash.hashBuffList[index].backwardIndex = -1;
}
/* make Empty Hash Buffer List */
for(index = 0; hashBuffListSize > index; index++){
if(index == hashBuffListSize-1){
hashMng->customHash.hashBuffList[index].forwardIndex = -1;
} else {
hashMng->customHash.hashBuffList[index].forwardIndex = index+1;
}
if(index == 0){
hashMng->customHash.hashBuffList[index].backwardIndex = -1;
} else {
hashMng->customHash.hashBuffList[index].backwardIndex = index-1;
}
hashMng->customHash.hashBuffList[index].hashKey = &(hashKeyBuff[hashKeyLen*index]);
}
result = COM_OK;
func_end:
return result;
}
/* get Hash Value */
RESULT getHashValue(
struct Hash_mng_t *hashMng,
BYTE *hashKey,
WORD *hashValue
){
RESULT result = COM_NG;
if(checkHasnMng(hashMng) == COM_NG){
goto func_end;
}
if(hashKey == NULL){
goto func_end;
}
if(hashValue == NULL){
goto func_end;
}
*hashValue = (*hashMng->customHash.hash_func)(
hashKey,
hashMng->customHash.hashKeyLen
);
result = COM_OK;
func_end:
return result;
}
/* Regist Hash Value */
RESULT regHashValue(
struct Hash_mng_t *hashMng,
BYTE *hashKey, /* (in) Hash Key Array */
WORD *hashBuffIndex /* (out) Hash BuffIndex */
){
RESULT result = COM_NG;
WORD hashValue = 0;
struct Hash_buff_t *hashBuff;
SWORD entryIndex;
RESULT ret = COM_NG;
/* Is Empty List Exist No Entry? */
if(hashMng->emptyHashBuff_head == -1){
goto func_end;
}
/* get Hash value */
ret = getHashValue(
hashMng,
hashKey,
&hashValue
);
if(ret == COM_NG){
goto func_end;
}
/* regist value */
hashBuff = &(hashMng->customHash.hashTbl[hashValue]);
/* get Entry from EmptyHashBuffer */
entryIndex = hashMng->emptyHashBuff_head;
hashMng->emptyHashBuff_head = hashMng->customHash.hashBuffList[entryIndex].forwardIndex;
if(hashMng->emptyHashBuff_head == -1){
hashMng->emptyHashBuff_tail = -1;
} else {
hashMng->customHash.hashBuffList[hashMng->emptyHashBuff_head].backwardIndex = -1;
}
if(hashBuff->backwardIndex == -1){
/* first entry */
hashBuff->forwardIndex = entryIndex;
}
/* set entry(add new entry to setup Value hashBuffList last Entry) */
hashMng->customHash.hashBuffList[hashBuff->backwardIndex].forwardIndex = entryIndex;
memcpy(
hashMng->customHash.hashBuffList[entryIndex].hashKey,
hashKey,
hashMng->customHash.hashKeyLen);
hashMng->customHash.hashBuffList[entryIndex].backwardIndex = hashBuff->backwardIndex;
hashMng->customHash.hashBuffList[entryIndex].forwardIndex = -1;
hashBuff->backwardIndex = entryIndex;
*hashBuffIndex = entryIndex;
result = COM_OK;
func_end:
return result;
}
/* Deregist Hash Value */
RESULT deregHashValue(
struct Hash_mng_t *hashMng,
BYTE *hashKey, /* (in) Hash Key Array */
WORD *hashBuffIndex /* (out) Hash BuffIndex */
){
RESULT result = COM_NG;
WORD hashValue = 0;
WORD searchIndex;
SWORD entryIndex;
WORD forwardIndex;
WORD backwardIndex;
RESULT ret = COM_NG;
ret = getHashValue(
hashMng,
hashKey,
&hashValue
);
if(ret == COM_NG){
goto func_end;
}
searchIndex = 0;
ret = getHashBuffIndex(
hashMng,
hashKey,
&searchIndex
);
if(ret == COM_NG || searchIndex == -1){
goto func_end;
}
/* delete entry */
forwardIndex = hashMng->customHash.hashBuffList[searchIndex].forwardIndex;
backwardIndex = hashMng->customHash.hashBuffList[searchIndex].backwardIndex;
if(forwardIndex == -1){
if(backwardIndex == -1){
hashMng->customHash.hashTbl[hashValue].forwardIndex = -1;
} else {
hashMng->customHash.hashTbl[hashValue].forwardIndex = backwardIndex;
}
} else {
hashMng->customHash.hashBuffList[backwardIndex].forwardIndex =
hashMng->customHash.hashBuffList[forwardIndex].forwardIndex;
}
if(backwardIndex == -1){
if(forwardIndex == -1){
hashMng->customHash.hashTbl[hashValue].backwardIndex = -1;
} else {
hashMng->customHash.hashTbl[hashValue].backwardIndex = forwardIndex;
}
} else {
hashMng->customHash.hashBuffList[forwardIndex].backwardIndex =
hashMng->customHash.hashBuffList[backwardIndex].backwardIndex;
}
/* Add deleted entry to EmptyHashBuffer last Entry */
entryIndex = hashMng->emptyHashBuff_tail;
hashMng->emptyHashBuff_tail = searchIndex;
memset(
hashMng->customHash.hashBuffList[searchIndex].hashKey,
0xff,
hashMng->customHash.hashKeyLen);
hashMng->customHash.hashBuffList[searchIndex].backwardIndex = -1;
if(entryIndex == -1){
hashMng->customHash.hashBuffList[searchIndex].backwardIndex = -1;
} else {
hashMng->customHash.hashBuffList[entryIndex].forwardIndex = searchIndex;
hashMng->customHash.hashBuffList[searchIndex].backwardIndex = entryIndex;
}
if(hashMng->emptyHashBuff_head == -1){
/* first entry */
hashMng->emptyHashBuff_head = searchIndex;
}
*hashBuffIndex = searchIndex;
result = COM_OK;
func_end:
return result;
}
/* Get Hash Buffer Index from Hash Value */
RESULT getHashBuffIndex(
struct Hash_mng_t *hashMng,
BYTE *hashKey,
WORD *hashBuffIndex
){
WORD hashValue = 0;
struct Hash_buff_t *hashBuff;
SWORD searchIndex;
RESULT result = COM_NG;
RESULT ret = COM_NG;
int cmpResutl;
/* get Hash value */
ret = getHashValue(
hashMng,
hashKey,
&hashValue
);
if(ret == COM_NG){
goto func_end;
}
/* regist value */
hashBuff = &(hashMng->customHash.hashTbl[hashValue]);
searchIndex = hashBuff->forwardIndex;
/* search for hashBufferList's hashKey */
while(searchIndex != -1){
cmpResutl = memcmp(
hashMng->customHash.hashBuffList[searchIndex].hashKey,
hashKey,
hashMng->customHash.hashKeyLen);
if(cmpResutl == 0){
break;
}
searchIndex = hashMng->customHash.hashBuffList[searchIndex].forwardIndex;
}
*hashBuffIndex = searchIndex;
if(searchIndex == -1){
goto func_end;
}
result = COM_OK;
func_end:
return result;
}
●hashDef.h
#ifndef _HASHDEF_H_
#define _HASHDEF_H_
typedef unsigned long DWORD;
typedef unsigned int WORD;
typedef int SWORD;
typedef unsigned char BYTE;
typedef char RESULT;
#define COM_OK (0)
#define COM_NG (-1)
#define SWORD_MAX (2147483647)
#endif
●ChashFunc.h
#ifndef _CHASHFUNC_H_
#define _CHASHFUNC_H_
/* custom Hash Functions */
#include "hashDef.h"
RESULT initCHash();
/* get Custom Hash Value */
RESULT getCHashValue(
BYTE *hashKey,
WORD *hashValue
);
/* Regist Custom Hash Value */
RESULT regCHashValue(
BYTE *hashKey, /* (in) Hash Key Array */
WORD value /* (in) set Value */
);
/* Deregist Custom Hash Value */
RESULT deregCHashValue(
BYTE *hashKey /* (in) Hash Key Array */
);
/* Get Hash Buffer Index from Hash Value */
RESULT getCHashBuffValue(
BYTE *hashKey,
WORD *value
);
#endif
●ChashFunc.c
#include <stdlib.h>
#include "GPhashFunc.h"
#include "ChashDef.h"
static struct Hash_mng_t hashMng;
static struct Hash_buff_t hashTbl[HASH_TBL_SIZE];
static BYTE hashKeyBuff[HASH_BUFF_SIZE];
static struct Hash_buff_t hashBuffList[HASH_BUFF_SIZE];
static struct Chash_value_tbl_t chashValueTbl[HASH_BUFF_SIZE];
static WORD charTOdecimal(char d1, char d2)
{
char data[3];
data[0] = d2;
data[1] = d1;
data[2] ='\0';
return atoi(data);
}
static WORD chashfunc(
BYTE* hashKey,
WORD hashKeyLen
){
WORD index = 0;
WORD result = 0;
WORD result1 = 0;
WORD result2 = 0;
WORD data[5];
data[0] = charTOdecimal(hashKey[0], hashKey[1]);
data[1] = charTOdecimal(hashKey[2], hashKey[3]);
data[2] = charTOdecimal(hashKey[4], hashKey[5]);
data[3] = charTOdecimal(hashKey[6], hashKey[7]);
result1 =(((data[3]*43 + data[2])*43 + data[1])*43 + data[0]) % 768;
data[0] = charTOdecimal(hashKey[ 8], hashKey[ 9]);
data[1] = charTOdecimal(hashKey[10], hashKey[11]);
data[2] = charTOdecimal(hashKey[12], hashKey[13]);
data[3] = charTOdecimal(hashKey[14], hashKey[15]);
result2 =(((data[3]*43 + data[2])*43 + data[1])*43 + data[0]) % 768;
result = (result1 + result2) % 768;
return result;
}
/* Initialize */
RESULT initCHash(
){
return initHash(
&hashMng,
hashTbl,
HASH_TBL_SIZE,
hashBuffList,
hashKeyBuff,
HASH_BUFF_SIZE,
&chashfunc,
HASH_KEY_SIZE
);
}
/* get Hash Value */
RESULT getCHashValue(
BYTE *hashKey,
WORD *hashValue
){
RESULT result = COM_NG;
result = getHashValue(
&hashMng,
hashKey,
hashValue
);
return result;
}
/* Regist Hash Value */
RESULT regCHashValue(
BYTE *hashKey, /* (in) Hash Key Array */
WORD value /* (in) set Value */
){
WORD hashBuffIndex;
RESULT result = COM_NG;
RESULT ret = COM_NG;
ret = regHashValue(
&hashMng,
hashKey, /* (in) Hash Key Array */
&hashBuffIndex /* (out) Hash BuffIndex */
);
if(ret == COM_OK){
if(hashBuffIndex < HASH_BUFF_SIZE){
chashValueTbl[hashBuffIndex].value = value;
result = COM_OK;
}
}
return result;
}
/* Deregist Hash Value */
RESULT deregCHashValue(
BYTE *hashKey /* (in) Hash Key Array */
){
WORD hashBuffIndex;
RESULT result = COM_NG;
RESULT ret = COM_NG;
ret = deregHashValue(
&hashMng,
hashKey, /* (in) Hash Key Array */
&hashBuffIndex /* (out) Hash BuffIndex */
);
if(ret == COM_OK){
if(hashBuffIndex < HASH_BUFF_SIZE){
chashValueTbl[hashBuffIndex].value = -1;
result = COM_OK;
}
}
return result;
}
RESULT getCHashBuffValue(
BYTE *hashKey,
WORD *value
){
WORD hashBuffIndex;
RESULT result = COM_NG;
RESULT ret = COM_NG;
ret = getHashBuffIndex(
&hashMng,
hashKey,
&hashBuffIndex
);
if(ret == COM_OK){
if(hashBuffIndex < HASH_BUFF_SIZE){
*value = chashValueTbl[hashBuffIndex].value;
result = COM_OK;
}
}
return result;
}
●ChashDef.h
#ifndef _CHASHDEF_H_
#define _CHASHDEF_H_
#include "hashDef.h"
#define HASH_TBL_SIZE (768)
#define HASH_BUFF_SIZE (HASH_TBL_SIZE*2)
#define HASH_KEY_SIZE (15)
struct Chash_value_tbl_t{
WORD value;
};
#endif
●main.c
#include <stdio.h>
#include "hashDef.h"
#include "ChashFunc.h"
int main()
{
RESULT ret1 = 0;
RESULT ret2 = 0;
RESULT ret3 = 0;
WORD value = 0;
BYTE haskKey[] = {'0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', '0', '1', '2', '3', '4', };
initCHash();
ret1 = regCHashValue(haskKey, 123);
ret2 = getCHashBuffValue(haskKey, &value);
ret3 = deregCHashValue(haskKey);
value = 0;
ret1 = regCHashValue(haskKey, 456);
ret2 = getCHashBuffValue(haskKey, &value);
ret3 = deregCHashValue(haskKey);
return 0;
}
やべ、＜＞を考えずにはっつけたから、途中がどうなっているかわからんや。
修正完？ うまくいったみたい。だと思うんだけど。
« 今飲んでいる酒 | トップページ | 情報処理技術者試験「ネットワークスペシャリスト」を申し込んだ »
コメント