#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__)