#if !defined(__INT_HASH_H__)
|
#define __INT_HASH_H__
|
|
using namespace std;
|
|
#include <stdio.h>
|
#include <stdlib.h>
|
|
/* Hash element class entity */
|
template <class T>
|
class CHashElem
|
{
|
public:
|
CHashElem<T> ()
|
{
|
key = 0;
|
pAtom = 0;
|
pNext = 0;
|
}
|
~CHashElem<T> ()
|
{
|
if (pAtom)
|
{
|
delete pAtom;
|
pAtom = 0;
|
}
|
}
|
|
int key;
|
T *pAtom;
|
CHashElem *pNext;
|
};
|
|
/* Hash table and its operaions */
|
template <class T>
|
class CIntHash
|
{
|
public:
|
CIntHash<T>(int iSlots = 100);
|
~CIntHash<T>();
|
|
bool Insert(const int key, T *pObj);
|
bool Find(const int key, T *&pObj);
|
bool Remove(const int key);
|
int Size() {return m_iLength;}
|
|
CHashElem<T> **m_ppHashSlots;
|
int m_iNumSlots;
|
|
private:
|
int m_iLength;
|
};
|
|
template <class T>
|
CIntHash<T>::CIntHash(int iSlots)
|
{
|
if (iSlots < 5)
|
iSlots = 5;
|
|
m_ppHashSlots = (CHashElem<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>
|
CIntHash<T>::~CIntHash()
|
{
|
if (m_ppHashSlots)
|
{
|
CHashElem<T> *pHe = 0;
|
for (int i=0; i<m_iNumSlots; i++)
|
{
|
pHe = m_ppHashSlots[i];
|
while (pHe)
|
{
|
CHashElem<T> *pNext = pHe->pNext;
|
delete pHe;
|
pHe = pNext;
|
}
|
}
|
delete [] m_ppHashSlots;
|
m_ppHashSlots = 0;
|
}
|
}
|
|
template <class T>
|
bool CIntHash<T>::Insert(const int key, T *pObj)
|
{
|
unsigned int num = (unsigned int)key % m_iNumSlots;
|
if (num >= 0)
|
{
|
if (m_ppHashSlots[num])
|
{
|
CHashElem<T> *pIns = m_ppHashSlots[num];
|
while (pIns->pNext)
|
{
|
pIns = pIns->pNext;
|
}
|
pIns->pNext = new CHashElem<T>;
|
pIns->pNext->pNext = 0;
|
pIns->pNext->pAtom = pObj;
|
pIns->pNext->key = key;
|
m_iLength++;
|
|
return true;
|
}
|
else
|
{
|
m_ppHashSlots[num] = new CHashElem<T>;
|
m_ppHashSlots[num]->pNext = 0;
|
m_ppHashSlots[num]->pAtom = pObj;
|
m_ppHashSlots[num]->key = key;
|
m_iLength++;
|
|
return true;
|
}
|
}
|
|
printf("CIntHash Insert Failure! \n");
|
|
return false;
|
}
|
|
template <class T>
|
bool CIntHash<T>::Find(const int key, T *&pObj)
|
{
|
unsigned int num = (unsigned int)key % m_iNumSlots;
|
if (num >= 0)
|
{
|
CHashElem<T> *pElem = m_ppHashSlots[num];
|
while (pElem)
|
{
|
if (pElem->key == key)
|
{
|
pObj = pElem->pAtom;
|
|
return true;
|
}
|
pElem = pElem->pNext;
|
}
|
}
|
|
printf("CIntHash Find Failure! \n");
|
|
return false;
|
}
|
|
template <class T>
|
bool CIntHash<T>::Remove(const int key)
|
{
|
unsigned int num = (unsigned int)key % m_iNumSlots;
|
if (num >= 0)
|
{
|
CHashElem<T> *pElem = m_ppHashSlots[num];
|
CHashElem<T> *pPrev = 0;
|
while (pElem)
|
{
|
if (pElem->key == key)
|
{
|
if (pPrev)
|
{
|
pPrev->pNext = pElem->pNext;
|
}
|
else
|
{
|
m_ppHashSlots[num] = pElem->pNext;
|
}
|
delete pElem;
|
m_iLength--;
|
|
return true;
|
}
|
pPrev = pElem;
|
pElem = pElem->pNext;
|
}
|
}
|
|
printf("CIntHash Remove Failure! \n");
|
|
return false;
|
}
|
|
#endif //#if !defined(__INT_HASH_H__)
|
