// HashTable.cpp: implementation of the CHashTable class.
//
//////////////////////////////////////////////////////////////////////

//#include "stdafx.h"
#include "HashTable.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHashTable::CHashTable()
{
	m_nTableSize = 1000;//default 1000;
	m_pDataList = NULL;
	m_pDataList = new CTableData[m_nTableSize];
}

CHashTable::~CHashTable()
{
	DestoryHashTable();
}

void CHashTable::DestoryHashTable(void)
{
	if (m_pDataList != NULL)
	{
		for (unsigned long i=0; i<m_nTableSize; i++)
		{
			CTableData *pData = m_pDataList + i;
			
			CTableData *pBase = NULL;
			CTableData *pNext = NULL;
			
			while (pData->m_pNext != NULL)
			{
				pBase = pData->m_pNext;
				pNext = pBase;
				pData->m_pNext = NULL;
				
				while (pBase->m_pNext != NULL)
				{
					pNext = pBase->m_pNext;
					delete pBase;
					pBase = pNext;					
				}
				delete pBase;
			}
		}
		
		delete [] m_pDataList;
		m_pDataList = NULL;
		m_nTableSize = 0;
	}
}

unsigned long CHashTable::CreateHashKey(const char *s, unsigned size)
{
	unsigned long h = 0;
	unsigned long g;
	
	if (size == 0)
		size = m_nTableSize;
	
	while (*s) 
	{
		h = (h << 4) + *s++;
		if ((g = (h & 0xf0000000)) != 0) 
		{
			h ^= (g >> 24);
			h ^= g;
		}
	}
	return (h % size);
}

unsigned long CHashTable::SetHashSize(unsigned long nTableSize)
{
	if (m_pDataList != NULL)
	{
		DestoryHashTable();
	}

	m_nTableSize = nTableSize;

	m_pDataList = new CTableData[m_nTableSize];

	return m_nTableSize;
}


/*==================================	
	Insert Data into the table
	return the index
==================================*/ 
unsigned long CHashTable::InsData(char *pData)
{
	CTableData *pTemp = NULL;
	unsigned long nIndex = 0;
	nIndex = CreateHashKey(pData);
	pTemp = m_pDataList + nIndex;

	if (strlen((char *)&pTemp->m_cData) == 0)
	{
		pTemp->m_ulHashKey = nIndex;
		strcpy(pTemp->m_cData, pData);
	}
	else
	{
		while (pTemp->m_pNext != NULL)
		{
			//if find the pData, then return;
			/*
			if (strncmp(pTemp->m_cData, pData, strlen(pTemp->m_cData)) == 0)
			{
				return nIndex;
			}
			*/
			char *p1 = NULL, *p2 = NULL;
			p1 = pTemp->m_cData;
			p2 = pData;
			while (*p1 != '\0')
			{
				if (*p1 != *p2)
					break;
				p1++;
				p2++;
			}
			if (*p1 == *p2)//find
				return nIndex;

			pTemp = pTemp->m_pNext;
		}

		CTableData *pAdd = new CTableData();
		pAdd->m_ulHashKey = nIndex;
		strcpy(pAdd->m_cData, pData);

		pTemp->m_pNext = pAdd;
	}

	return nIndex;
}

/*==================================	
	Locate the data in the Table
	return true if it is exist
==================================*/
bool CHashTable::LocateData(char *pData, int nLen)
{
	CTableData *pTemp = NULL;
	unsigned long nIndex = 0;
	
	nIndex = CreateHashKey(pData);
	pTemp = m_pDataList + nIndex;

	if (strlen((char *)&pTemp->m_cData) == 0)
		return false;

	do 
	{
		if (pTemp->DatanCmp(pData, nLen))
			return true;

		pTemp = pTemp->m_pNext;
		
	} while(pTemp != NULL);

	return false;
}

/*===================================	
	==Delete the data in the Table==
	==return true if del succeed====
====================================*/
bool CHashTable::DelData(char *pData, int nLen)
{
	CTableData *pTemp = NULL;
	CTableData *pBase = NULL;
	unsigned long nIndex = 0;
	
	nIndex = CreateHashKey(pData);
	pTemp = m_pDataList + nIndex;
	
	if (strlen((char *)&pTemp->m_cData) == 0)
		return false;

	pBase = pTemp;
	
	bool bBaseNode = true;
	do 
	{
		if (pTemp->DatanCmp(pData, nLen))
		{
			if (bBaseNode)
			{
				pTemp->m_ulHashKey = 0;
				pTemp->m_pNext = NULL;
				memset(&pTemp->m_cData, 0, sizeof(pTemp->m_cData));
			}
			else
			{
				pBase->m_pNext = pTemp->m_pNext;
				delete pTemp;
			}
			return true;
		}

		pBase = pTemp;
		
		pTemp = pTemp->m_pNext;
		bBaseNode = false;
		
	} while(pTemp != NULL);
	
	return false;
}



//CTableData 
CTableData::CTableData()
{
	memset(&m_cData, 0, sizeof(m_cData));
	m_ulHashKey = 0;
	m_pNext = NULL;
}

CTableData::~CTableData()
{

}

bool CTableData::DataCmp(char *pData)
{
	int nLen = strlen(m_cData);
	return DatanCmp(pData, nLen);
}

bool CTableData::DatanCmp(char *pData, int nLen)
{
	if (nLen == 0)
		return false;
	
	if (strncmp((const char *)&m_cData, pData, nLen) == 0)
		return true;
	else
		return false;
}