#if !defined(__STR_HASH_H__)
|
#define __STR_HASH_H__
|
|
using namespace std;
|
|
#include <stdio.h>
|
#include <string.h>
|
#include <stdlib.h>
|
|
/* Hash element class entity */
|
template <class T>
|
class CStrHashElem
|
{
|
public:
|
CStrHashElem<T> ()
|
{
|
pStrKey = 0;
|
pAtom = 0;
|
pNext = 0;
|
}
|
~CStrHashElem<T> ()
|
{
|
if (pStrKey)
|
{
|
delete [] pStrKey;
|
pStrKey = 0;
|
}
|
if (pAtom)
|
{
|
delete pAtom;
|
pAtom = 0;
|
}
|
}
|
|
char *pStrKey;
|
T *pAtom;
|
CStrHashElem *pNext;
|
};
|
|
/* Hash table and its operaions */
|
template <class T>
|
class CStrHash
|
{
|
public:
|
CStrHash<T>(int iSlots = 20);
|
~CStrHash<T>();
|
|
bool Insert(const char *pStr, T *pObj);
|
bool Find(const char *pStr, T *&pObj);
|
bool Remove(const char *pStr);
|
bool Remove(const char *pStr, const char FileName[], int Line, const char Function[]);
|
//only remove node from a list , not release the dynamic memory (node content pointer)
|
bool Remove2(const char *pStr, const char FileName[], int Line, const char Function[]);
|
bool Remove2(const char *pStr, T *&pObj);
|
int Size() {return m_iLength;}
|
|
CStrHashElem<T> **m_ppHashSlots;
|
int m_iNumSlots;
|
|
private:
|
int m_iLength;
|
int GetHashIndex(const char *pStr);
|
};
|
|
template <class T>
|
CStrHash<T>::CStrHash(int iSlots)
|
{
|
if (iSlots < 5)
|
iSlots = 5;
|
|
m_ppHashSlots = (CStrHashElem<T> **)new char[sizeof(void *) * iSlots];
|
if (0 == m_ppHashSlots)
|
{
|
printf("new CHashElem<T> ** failure! \n");
|
exit(1);
|
}
|
for (int i=0; i<iSlots; i++)
|
m_ppHashSlots[i] = 0;
|
|
m_iNumSlots = iSlots;
|
m_iLength = 0;
|
}
|
|
template <class T>
|
CStrHash<T>::~CStrHash()
|
{
|
if (m_ppHashSlots)
|
{
|
CStrHashElem<T> *pHe = 0;
|
for (int i=0; i<m_iNumSlots; i++)
|
{
|
pHe = m_ppHashSlots[i];
|
while (pHe)
|
{
|
CStrHashElem<T> *pNext = pHe->pNext;
|
delete pHe;
|
pHe = pNext;
|
}
|
}
|
delete [] m_ppHashSlots;
|
m_ppHashSlots = 0;
|
}
|
}
|
|
template <class T>
|
bool CStrHash<T>::Insert(const char *pStr, T *pObj)
|
{
|
//-------- Check input parameter exception --------//
|
if (NULL == pStr)
|
{
|
printf("%s: pStr is null at %s:%d!", __FUNCTION__, __FILE__, __LINE__);
|
return false;
|
}
|
else
|
{
|
if (strlen(pStr) == 0)
|
{
|
printf("%s: pStr is empty string at %s:%d!", __FUNCTION__, __FILE__, __LINE__);
|
}
|
}
|
//------------------- Check end -------------------//
|
|
int len;
|
unsigned int num = (unsigned int)GetHashIndex(pStr) % m_iNumSlots;
|
if (num >= 0)
|
{
|
if (m_ppHashSlots[num])
|
{
|
CStrHashElem<T> *pIns = m_ppHashSlots[num];
|
while (pIns->pNext)
|
{
|
pIns = pIns->pNext;
|
}
|
pIns->pNext = new CStrHashElem<T>;
|
if (pIns->pNext != NULL)
|
{
|
pIns->pNext->pNext = 0;
|
pIns->pNext->pAtom = pObj;
|
len = strlen(pStr);
|
pIns->pNext->pStrKey = new char[len+1];
|
if (pIns->pNext->pStrKey != NULL)
|
{
|
strcpy(pIns->pNext->pStrKey, pStr);
|
m_iLength++;
|
|
return true;
|
}
|
else
|
{
|
delete pIns->pNext;
|
pIns->pNext = NULL;
|
}
|
}
|
}
|
else
|
{
|
m_ppHashSlots[num] = new CStrHashElem<T>;
|
if (m_ppHashSlots[num] != NULL)
|
{
|
m_ppHashSlots[num]->pNext = 0;
|
m_ppHashSlots[num]->pAtom = pObj;
|
len = strlen(pStr);
|
m_ppHashSlots[num]->pStrKey = new char[len+1];
|
if (m_ppHashSlots[num]->pStrKey != NULL)
|
{
|
strcpy(m_ppHashSlots[num]->pStrKey, pStr);
|
m_iLength++;
|
|
return true;
|
}
|
else
|
{
|
delete m_ppHashSlots[num];
|
m_ppHashSlots[num] = NULL;
|
}
|
}
|
}
|
}
|
|
printf("CStrHash Insert Failure! \n");
|
|
return false;
|
}
|
|
template <class T>
|
bool CStrHash<T>::Find(const char *pStr, T *&pObj)
|
{
|
unsigned int num = (unsigned int)GetHashIndex(pStr) % m_iNumSlots;
|
if (num >= 0)
|
{
|
CStrHashElem<T> *pElem = m_ppHashSlots[num];
|
while (pElem)
|
{
|
if (strcmp(pElem->pStrKey, pStr) == 0)
|
{
|
pObj = pElem->pAtom;
|
|
return true;
|
}
|
pElem = pElem->pNext;
|
}
|
}
|
|
// printf("CStrHash Find Failure! \n");
|
|
pObj = NULL;
|
return false;
|
}
|
|
template <class T>
|
bool CStrHash<T>::Remove(const char *pStr, const char FileName[], int Line, const char Function[])
|
{
|
if (pStr != NULL)
|
{
|
unsigned int num = (unsigned int)GetHashIndex(pStr) % m_iNumSlots;
|
if (num >= 0)
|
{
|
CStrHashElem<T> *pElem = m_ppHashSlots[num];
|
CStrHashElem<T> *pPrev = 0;
|
while (pElem)
|
{
|
if (strcmp(pElem->pStrKey, pStr) == 0)
|
{
|
if (pPrev)
|
{
|
pPrev->pNext = pElem->pNext;
|
}
|
else
|
{
|
m_ppHashSlots[num] = pElem->pNext;
|
}
|
delete pElem;
|
m_iLength--;
|
|
return true;
|
}
|
pPrev = pElem;
|
pElem = pElem->pNext;
|
}
|
}
|
|
printf("%s: CStrHash Remove <%s> Failure at %s:%d! \n", Function, pStr, FileName, Line);
|
}
|
else
|
{
|
printf("%s: CStrHash Remove <null> Failure at %s:%d! \n", Function, FileName, Line);
|
}
|
|
return false;
|
}
|
|
template <class T>
|
bool CStrHash<T>::Remove2(const char *pStr, const char FileName[], int Line, const char Function[])
|
{
|
if (pStr != NULL)
|
{
|
unsigned int num = (unsigned int)GetHashIndex(pStr) % m_iNumSlots;
|
if (num >= 0)
|
{
|
CStrHashElem<T> *pElem = m_ppHashSlots[num];
|
CStrHashElem<T> *pPrev = 0;
|
while (pElem)
|
{
|
if (strcmp(pElem->pStrKey, pStr) == 0)
|
{
|
if (pPrev)
|
{
|
pPrev->pNext = pElem->pNext;
|
}
|
else
|
{
|
m_ppHashSlots[num] = pElem->pNext;
|
}
|
/****/
|
pElem->pAtom = NULL; //not release node content pointer
|
/****/
|
delete pElem;
|
m_iLength--;
|
|
// printf("%s: CStrHash Remove2 <%s> Success at %s:%d! \n", Function, pStr, FileName, Line);
|
|
return true;
|
}
|
pPrev = pElem;
|
pElem = pElem->pNext;
|
}
|
}
|
|
printf("%s: CStrHash Remove2 <%s> Failure at %s:%d! \n", Function, pStr, FileName, Line);
|
}
|
else
|
{
|
printf("%s: CStrHash Remove2 <null> Failure at %s:%d! \n", Function, FileName, Line);
|
}
|
|
return false;
|
}
|
|
template <class T>
|
bool CStrHash<T>::Remove2(const char *pStr, T *&pObj)
|
{
|
if (pStr != NULL)
|
{
|
unsigned int num = (unsigned int)GetHashIndex(pStr) % m_iNumSlots;
|
if (num >= 0)
|
{
|
CStrHashElem<T> *pElem = m_ppHashSlots[num];
|
CStrHashElem<T> *pPrev = 0;
|
while (pElem)
|
{
|
if (strcmp(pElem->pStrKey, pStr) == 0)
|
{
|
if (pPrev)
|
{
|
pPrev->pNext = pElem->pNext;
|
}
|
else
|
{
|
m_ppHashSlots[num] = pElem->pNext;
|
}
|
/****/
|
pObj = pElem->pAtom;
|
pElem->pAtom = NULL; //not release node content pointer
|
/****/
|
delete pElem;
|
m_iLength--;
|
|
return true;
|
}
|
pPrev = pElem;
|
pElem = pElem->pNext;
|
}
|
}
|
|
printf("CStrHash Remove2 <%s> Failure! \n", pStr);
|
}
|
else
|
{
|
printf("CStrHash Remove2 <null> Failure! \n");
|
}
|
|
pObj = NULL;
|
return false;
|
}
|
template <class T>
|
bool CStrHash<T>::Remove(const char *pStr)
|
{
|
unsigned int num = (unsigned int)GetHashIndex(pStr) % m_iNumSlots;
|
if (num >= 0)
|
{
|
CStrHashElem<T> *pElem = m_ppHashSlots[num];
|
CStrHashElem<T> *pPrev = 0;
|
while (pElem)
|
{
|
if (strcmp(pElem->pStrKey, pStr) == 0)
|
{
|
if (pPrev)
|
{
|
pPrev->pNext = pElem->pNext;
|
}
|
else
|
{
|
m_ppHashSlots[num] = pElem->pNext;
|
}
|
delete pElem;
|
m_iLength--;
|
|
return true;
|
}
|
pPrev = pElem;
|
pElem = pElem->pNext;
|
}
|
}
|
|
printf("CStrHash Remove Failure! \n");
|
|
return false;
|
}
|
template <class T>
|
int CStrHash<T>::GetHashIndex(const char *pStr)
|
{
|
unsigned long nHash = 0;
|
|
if (pStr != NULL)
|
{
|
while (*pStr)
|
{
|
nHash = (nHash << 5) + nHash + *pStr++;
|
}
|
}
|
|
return (nHash % m_iNumSlots);
|
}
|
|
#endif //#if !defined(__STR_HASH_H__)
|
