hash实现

头文件及定义
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;
   }
}