ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > > hash实现

hash实现

作者：mmmike 时间：2019-08-19 15:52:05 0 删除 编辑

头文件及定义

typedef int SymbolsHash;  

typedef enum SymbolType 

{

    undefined=0,

    byteint=1,

    shortint=2,

    integer=3,

    hex=4,

    percent=5,

    octal=6,

    big=7,

    flag=8,

    floating=9,

    string=10,

    bytes=11,

    symbol=12,

    errmsg=13

}SymbolType;

typedef struct _SYMBOL_VALUE

{

union 

{

        char     flag;

        char     byteint;

        short   shortint;

        char     percent;

        long     integer;

        long     hex;

        long     octal;

        long     big[2];

        double   floating;

        char     *string;

        char     *bytes;

        char     *errmsg;

        void     *symbol;

    }value;

    SymbolType     type;

    uint         valid;

    uint         allocated;

}SYMBOL_VALUE,*PSYMBOL_VALUE;

typedef struct _SYMBOL_KEY

{

struct _SYMBOL_KEY *pNext;

SYMBOL_VALUE m_Name;

SYMBOL_VALUE m_Value;

int m_Arg;

int m_Bucket;

}SYMBOL_KEY,*PSYMBOL_KEY;

typedef BOOL (*SymbolHandlerProc)(int Arg);

typedef struct _SYMBOL_HANDLER

{

char *pName;

SymbolHandlerProc pProcFunc;

int m_Flags;

}SYMBOL_HANDLER,*PSYMBOL_HANDLER;

实现

static int SymbolPrimeCheck(int n)

{

    int i,max;

    if(n<=0)

return 1;

    max=n/2;

    for(i=2;i<=max;i++) 

{

        if(n%i==0) 

{

            return 0;

        }

    }

    return 1;

}

static int SymbolPrimeCalc(int PrimeSize)

{

    int count;

    if(PrimeSize<=0)

return 1;

    for(count=PrimeSize;count>0;count--) 

{

        if(SymbolPrimeCheck(count)) 

{

            return count;

        }

    }

    return 1;

}

static int SymbolHashIndex(SYMBOL_HASH_TABLE *pSymHashTab,char *pName)

{

    uint sum;

    int  i;

    if(pSymHashTab==NULL||pName==NULL)

return 0;

    i=sum=0;

    while(*pName) 

{

        sum+=(((int)*pName++)< i=(i+7)%(BITS(int)-BITSPERBYTE);

}

return sum%pSymHashTab->m_Size;

}

static SYMBOL_KEY *SymbolHashFuction(SYMBOL_HASH_TABLE *pSymHashTab,char *pName)

{

if(pSymHashTab==NULL||pName==NULL)

return NULL;

return pSymHashTab->ppSymbolKey[SymbolHashIndex(pSymHashTab,pName)];

}

static SYMBOL_VALUE SymbolValueInteger(long Value)

{

SYMBOL_VALUE SymValue;

memset(&SymValue,0x0,sizeof(SymValue));

SymValue.valid=1;

SymValue.type=integer;

SymValue.value.integer=Value;

return SymValue;

}

static SYMBOL_VALUE SymbolValueSymbol(void *pValue)

{

SYMBOL_VALUE SymValue;

memset(&SymValue,0x0,sizeof(SymValue));

SymValue.valid=1;

SymValue.type=symbol;

SymValue.value.symbol=pValue;

return SymValue;

}

static SYMBOL_VALUE SymbolValueString(char *pValue,int Flag)

{

SYMBOL_VALUE SymValue;

memset(&SymValue,0x0,sizeof(SymValue));

SymValue.valid=1;

SymValue.type=string;

if(Flag&SYM_VALUE_FLAG_ALLOC)

{

SymValue.allocated=1;

SymValue.value.string=SymbolClone(pValue);

}

else

{

SymValue.allocated=0;

SymValue.value.string=(char*)pValue;

}

return SymValue;

}

static void SymbolValueFree(SYMBOL_VALUE*pValue)

{

if(pValue->valid&&pValue->allocated&&pValue->type==string&&pValue->value.string!=NULL)

{

free(pValue->value.string);

}

pValue->type=undefined;

pValue->valid=0;

pValue->allocated=0;

}

static int SymbolHashAlloc(void *pMapArg)

{

void    ***map;

size_t  *mp;

int     handle,len,memsize,incr;

map=(void***)pMapArg;

if(map==NULL)

return -1;

if(*map==NULL)

{

incr=SYM_HASH_INCR;

memsize=(incr+SYM_HASH_OFFSET)*sizeof(void*);

if((mp=malloc(memsize))==NULL)

{

return -1;

}

memset(mp,0,memsize);

mp[SYM_HASH_LEN]=incr;

mp[SYM_HASH_USED]=0;

*map=(void*)&mp[SYM_HASH_OFFSET];

}

else

{

mp=&((*(size_t**)map)[-SYM_HASH_OFFSET]);

}

len=(int)mp[SYM_HASH_LEN];

if(mp[SYM_HASH_USED] {

for(handle=0;handle {

if(mp[handle+SYM_HASH_OFFSET]==0)

{

mp[SYM_HASH_USED]++;

return handle;

}

}

}

else

{

handle=len;

}

len+=SYM_HASH_INCR;

memsize=(len+SYM_HASH_OFFSET)*sizeof(void*);

if((mp=realloc(mp,memsize))==NULL)

{

return -1;

}

*map=(void*)&mp[SYM_HASH_OFFSET];

mp[SYM_HASH_LEN]=len;

memset(&mp[SYM_HASH_OFFSET+len-SYM_HASH_INCR],0,sizeof(size_t*)*SYM_HASH_INCR);

mp[SYM_HASH_USED]++;

return handle;

}

static int SymbolHashFree(void *pMapArg,int Handle)

{

void    ***map;

size_t  *mp;

int     len;

map=(void***)pMapArg;

if(map==NULL)

return -1;

mp=&((*(size_t**)map)[-SYM_HASH_OFFSET]);

if(mp[SYM_HASH_LEN] return -1;

mp[Handle+SYM_HASH_OFFSET]=0;

if(--(mp[SYM_HASH_USED])==0)

{

free((void*)mp);

*map=NULL;

}

if(*map==NULL)

{

Handle=-1;

}

else

{

len=(int)mp[SYM_HASH_LEN];

if(mp[SYM_HASH_USED] {

for(Handle=len-1;Handle>=0;Handle--)

{

if(mp[Handle+SYM_HASH_OFFSET])

break;

}

}

else

{

Handle=len;

}

}

return Handle+1;

}

extern char *SymbolClone(char *pString)

{

char *buf;

if(pString==NULL)

{

pString="";

}

if((buf=malloc(strlen(pString)+1))!=0)

{

strcpy(buf,pString);

}

else

{

return NULL;

}

return buf;

}

extern SymbolsHash SymbolHashCreate(DWORD HashSize)

{

SymbolsHash    SymbolHashH;

SYMBOL_HASH_TABLE   *pSymHashTab;

if(HashSize<2)

{

HashSize=SYM_SMALL_HASH;

}

if((SymbolHashH=SymbolHashAlloc(&ppSymbolHashTable))<0)

{

return -1;

}

if((pSymHashTab=(SYMBOL_HASH_TABLE*)malloc(sizeof(SYMBOL_HASH_TABLE)))==NULL)

{

sSymbolMaxNum=SymbolHashFree(&ppSymbolHashTable,SymbolHashH);

return -1;

}

memset(pSymHashTab,0,sizeof(SYMBOL_HASH_TABLE));

if(SymbolHashH>=sSymbolMaxNum)

{

sSymbolMaxNum=SymbolHashH+1;

}

ppSymbolHashTable[SymbolHashH]=pSymHashTab;

pSymHashTab->m_Size=SymbolPrimeCalc(HashSize);

if((pSymHashTab->ppSymbolKey=(SYMBOL_KEY**)malloc(pSymHashTab->m_Size*sizeof(SYMBOL_KEY*)))==0)

{

SymbolHashFree(&ppSymbolHashTable,SymbolHashH);

free(pSymHashTab);

return -1;

}

memset(pSymHashTab->ppSymbolKey,0,pSymHashTab->m_Size*sizeof(SYMBOL_KEY*));

return SymbolHashH;

}

extern void SymbolHashDestroy(SymbolsHash SymbolHashH)

{

SYMBOL_HASH_TABLE   *pSymHashTable;

SYMBOL_KEY     *pSymbolKey,*pNextKey;

int         i;

if(SymbolHashH<0||SymbolHashH>=sSymbolMaxNum)

return;

pSymHashTable=ppSymbolHashTable[SymbolHashH];

if(pSymHashTable==NULL)

return;

for(i=0;im_Size;i++)

{

for(pSymbolKey=pSymHashTable->ppSymbolKey[i];pSymbolKey;pSymbolKey=pNextKey)

{

pNextKey=pSymbolKey->pNext;

SymbolValueFree(&pSymbolKey->m_Name);

SymbolValueFree(&pSymbolKey->m_Value);

free((void*)pSymbolKey);

pSymbolKey=pNextKey;

}

}

free((void*)pSymHashTable->ppSymbolKey);

sSymbolMaxNum=SymbolHashFree(&ppSymbolHashTable,SymbolHashH);

free((void*)pSymHashTable);

}

extern SYMBOL_KEY *SymbolHashAdd(SymbolsHash SymbolHashH,char *pName,void *pValue,int Arg)

{

SYMBOL_HASH_TABLE   *pSymHashTable;

SYMBOL_KEY     *pSymbolKey,*pLastKey;

char        *cp;

int         hindex;

if(pName==NULL)

return NULL;

if(SymbolHashH<0||SymbolHashH>=sSymbolMaxNum)

return NULL;

pSymHashTable=ppSymbolHashTable[SymbolHashH];

if(pSymHashTable==NULL)

return NULL;

pLastKey=NULL;

hindex=SymbolHashIndex(pSymHashTable,pName);

if((pSymbolKey=pSymHashTable->ppSymbolKey[hindex])!=NULL)

{

for(;pSymbolKey;pSymbolKey=pSymbolKey->pNext)

{

cp=pSymbolKey->m_Name.value.string;

if(cp[0]==pName[0]&&strcmp(cp,pName)==0)

{

break;

}

pLastKey=pSymbolKey;

}

if(pSymbolKey)

{

if(pSymbolKey->m_Value.valid)

{

SymbolValueFree(&pSymbolKey->m_Value);

}

pSymbolKey->m_Value=SymbolValueSymbol(pValue);

pSymbolKey->m_Arg=Arg;

return pSymbolKey;

}

if((pSymbolKey=(SYMBOL_KEY*)malloc(sizeof(SYMBOL_KEY)))==0)

{

return NULL;

}

pSymbolKey->m_Name=SymbolValueString(pName,SYM_VALUE_FLAG_ALLOC);

pSymbolKey->m_Value=SymbolValueSymbol(pValue);

pSymbolKey->pNext=(SYMBOL_KEY*)NULL;

pSymbolKey->m_Arg=Arg;

pSymbolKey->m_Bucket=hindex;

pLastKey->pNext=pSymbolKey;

}

else

{

if((pSymbolKey=(SYMBOL_KEY*)malloc(sizeof(SYMBOL_KEY)))==0)

{

return NULL;

}

pSymHashTable->ppSymbolKey[hindex]=pSymbolKey;

pSymbolKey->pNext=(SYMBOL_KEY*)NULL;

pSymbolKey->m_Value=SymbolValueSymbol(pValue);

pSymbolKey->m_Arg=Arg;

pSymbolKey->m_Name=SymbolValueString(pName,SYM_VALUE_FLAG_ALLOC);

pSymbolKey->m_Bucket=hindex;

}

return pSymbolKey;

}

extern int SymbolHashDel(SymbolsHash SymbolHashH,char *pName)

{

SYMBOL_HASH_TABLE   *pSymHashTable;

SYMBOL_KEY     *pSymbolKey,*pLastKey;

char        *cp;

int         hindex;

if(pName==NULL)

return -1;

if(SymbolHashH<0||SymbolHashH>=sSymbolMaxNum)

return -1;

pSymHashTable=ppSymbolHashTable[SymbolHashH];

if(pSymHashTable==NULL)

return -1;

pLastKey=NULL;

hindex=SymbolHashIndex(pSymHashTable,pName);

if((pSymbolKey=pSymHashTable->ppSymbolKey[hindex])!=NULL)

{

for(;pSymbolKey;pSymbolKey=pSymbolKey->pNext)

{

cp=pSymbolKey->m_Name.value.string;

if(cp[0]==pName[0]&&strcmp(cp,pName)==0)

{

break;

}

pLastKey=pSymbolKey;

}

}

if(pSymbolKey==(SYMBOL_KEY*)NULL)

{

return -1;

}

if(pLastKey)

{

pLastKey->pNext=pSymbolKey->pNext;

}

else

{

pSymHashTable->ppSymbolKey[hindex]=pSymbolKey->pNext;

}

SymbolValueFree(&pSymbolKey->m_Name);

SymbolValueFree(&pSymbolKey->m_Value);

free((void*)pSymbolKey);

return 0;

}

extern SYMBOL_KEY *SymbolHashFind(SymbolsHash SymbolHashH,char *pName)

{

SYMBOL_HASH_TABLE   *pSymHashTable;

SYMBOL_KEY     *pSymbolKey;

char        *cp;

if(pName==NULL||*pName=='\0')

return NULL;

if(SymbolHashH<0||SymbolHashH>=sSymbolMaxNum)

return NULL;

if((pSymHashTable=ppSymbolHashTable[SymbolHashH])==NULL)

{

return NULL;

}

for(pSymbolKey=SymbolHashFuction(pSymHashTable,pName);pSymbolKey;pSymbolKey=pSymbolKey->pNext)

{

cp=pSymbolKey->m_Name.value.string;

if(cp[0]==pName[0]&&strcmp(cp,pName)==0)

{

break;

}

}

return pSymbolKey;

}

extern SYMBOL_KEY *SymbolHashFirst(SymbolsHash SymbolHashH)

{

SYMBOL_HASH_TABLE   *pSymHashTable;

SYMBOL_KEY     *pSymbolKey;

int         i;

if(SymbolHashH<0||SymbolHashH>=sSymbolMaxNum)

{

return 0;

}

pSymHashTable=ppSymbolHashTable[SymbolHashH];

if(pSymHashTable==NULL)

return 0;

for(i=0;im_Size;i++)

{

if((pSymbolKey=pSymHashTable->ppSymbolKey[i])!=0)

{

return pSymbolKey;

}

}

return 0;

}

extern SYMBOL_KEY *SymbolHashNext(SymbolsHash SymbolHashH,SYMBOL_KEY *pLastKey)

{

SYMBOL_HASH_TABLE   *pSymHashTable;

SYMBOL_KEY     *pSymbolKey;

int         i;

if(SymbolHashH<0||SymbolHashH>=sSymbolMaxNum)

{

return NULL;

}

pSymHashTable=ppSymbolHashTable[SymbolHashH];

if(pSymHashTable==NULL)

return NULL;

if(pLastKey==NULL)

{

return SymbolHashFirst(SymbolHashH);

}

if(pLastKey->pNext)

{

return pLastKey->pNext;

}

for(i=pLastKey->m_Bucket+1;im_Size;i++)

{

if((pSymbolKey=pSymHashTable->ppSymbolKey[i])!=0)

{

return pSymbolKey;

}

}

return NULL;

}

测试程序

{

#include "SymbolHash.h"

static SymbolsHash symbolHashH=-1;

SYMBOL_HANDLER     *pSymHandler,*pSymHandler2,*pSymHandler3,*pSymHandler4;

SYMBOL_KEY*pSymbolKey=NULL,*pNextKey=NULL;

symbolHashH=SymbolHashCreate(64);

if((pSymHandler=malloc(sizeof(SYMBOL_HANDLER)))==0)

{

return -1;

}

memset(pSymHandler,0,sizeof(SYMBOL_HANDLER));

pSymHandler->pName=SymbolClone("jsya1");

pSymHandler->pProcFunc=NULL;

pSymHandler->m_Flags=17;

SymbolHashAdd(symbolHashH,pSymHandler->pName,pSymHandler,0);

if((pSymHandler2=malloc(sizeof(SYMBOL_HANDLER)))==0)

{

return -1;

}

memset(pSymHandler2,0,sizeof(SYMBOL_HANDLER));

pSymHandler2->pName=SymbolClone("jsya2");

pSymHandler2->pProcFunc=NULL;

pSymHandler2->m_Flags=27;

SymbolHashAdd(symbolHashH,pSymHandler2->pName,pSymHandler2,0);

if((pSymHandler3=malloc(sizeof(SYMBOL_HANDLER)))==0)

{

return -1;

}

memset(pSymHandler3,0,sizeof(SYMBOL_HANDLER));

pSymHandler3->pName=SymbolClone("jsya3");

pSymHandler3->pProcFunc=NULL;

pSymHandler3->m_Flags=37;

SymbolHashAdd(symbolHashH,pSymHandler3->pName,pSymHandler3,0);

if((pSymHandler4=malloc(sizeof(SYMBOL_HANDLER)))==0)

{

return -1;

}

memset(pSymHandler4,0,sizeof(SYMBOL_HANDLER));

pSymHandler4->pName=SymbolClone("jsya4");

pSymHandler4->pProcFunc=NULL;

pSymHandler4->m_Flags=47;

SymbolHashAdd(symbolHashH,pSymHandler4->pName,pSymHandler4,0);

pSymbolKey=SymbolHashFind(symbolHashH,"jsya2");

if(pSymbolKey!=NULL)

{

SYMBOL_HANDLER  *pTmpSymHandler=NULL;

pTmpSymHandler=pSymbolKey->m_Value.value.symbol;

if(pTmpSymHandler!=NULL)

{

PRINTF("-------name=%s---flag=%d--",pTmpSymHandler->pName,pTmpSymHandler->m_Flags);

}

}

pSymbolKey=SymbolHashFind(symbolHashH,"jsya3");

if(pSymbolKey!=NULL)

{

SYMBOL_HANDLER  *pTmpSymHandler=NULL;

pTmpSymHandler=pSymbolKey->m_Value.value.symbol;

if(pTmpSymHandler!=NULL)

{

PRINTF("---3----name=%s---flag=%d--",pTmpSymHandler->pName,pTmpSymHandler->m_Flags);

}

}

SymbolHashDel(symbolHashH,"jsya3");

if(symbolHashH>=0)

{

SYMBOL_HANDLER  *pTmpSymHandler=NULL;

for(pSymbolKey=SymbolHashFirst(symbolHashH);pSymbolKey;pSymbolKey=pNextKey)

{

pNextKey=SymbolHashNext(symbolHashH,pSymbolKey);

pTmpSymHandler=pSymbolKey->m_Value.value.symbol;

if(pTmpSymHandler!=NULL)

{

PRINTF("------%s-----------",pTmpSymHandler->pName);

if(pTmpSymHandler->pName!=NULL)

free(pTmpSymHandler->pName);

free(pTmpSymHandler);

}

}

SymbolHashDestroy(symbolHashH);

symbolHashH=-1;

}

}

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/2872/viewspace-3166284/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： Java 删除PDF中的附件
下一篇： 没有了~
请登录后发表评论 登录
全部评论
mmmike

注册时间：2019-08-19

  • 博文量
    77
  • 访问量
    550

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593