hashtable.h

墨香最新私服

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "stdafx.h"

typedef void* YHTPOSITION;

template <class T>
class CYHHashTable
{	
	struct BUCKET;
	
public:
	struct LIST
	{
		LIST*		pNext;
		LIST*		pPrv;
		BUCKET*		pBucket;
		LIST()		{pNext = NULL; pPrv = NULL; pBucket = NULL;}
	};
	
private:
	struct BUCKET
	{
		DWORD		dwKey;
		T*			pVoid;
		LIST*		pList;
		BUCKET*		pNext;
		BUCKET*		pPrv;
		BUCKET(T* pvoid,DWORD key)	{pVoid = pvoid;dwKey = key; pNext = NULL; pPrv = NULL;}
		
	};
	
	protected:
		DWORD				m_dwDataNum;
		DWORD				m_dwMaxBucketNum;
		BUCKET**			m_ppBucketTable;
		LIST*				m_pListHead;
		LIST*				m_pListTail;
		LIST*				m_pListCur;
		
		BUCKET*				m_pCurBucket;
		BUCKET*				m_pLastBucket;
		DWORD				m_MultiDataKey;
		
	public:
		DWORD	inline		GetDataNum() {return m_dwDataNum;}
		bool				Initialize(DWORD dwMaxBucketNum)
		{
			m_dwDataNum = 0;
			m_dwMaxBucketNum = dwMaxBucketNum;
			m_ppBucketTable = NULL;
			m_pListHead = NULL;
			m_pListTail = NULL;
			m_pListCur = NULL;
			
			m_ppBucketTable = new BUCKET*[m_dwMaxBucketNum];
			
			if (!m_ppBucketTable)
				return false;
			
			memset(m_ppBucketTable,0,sizeof(BUCKET*)*m_dwMaxBucketNum);
			
			return true;
			
		}
		
		LIST*				AddList(BUCKET* pBucket)
		{
			LIST*	cur = NULL;
			LIST*	prv = NULL;
			LIST*	next = NULL;
			
			if (!m_pListHead)
			{
				m_pListCur = m_pListHead = new LIST;
				m_pListTail = m_pListCur;
				m_pListCur->pBucket = pBucket;
				pBucket->pList = m_pListHead;
				return m_pListHead;
			}
			else 
			{
				cur = m_pListTail->pNext = new LIST;
				cur->pPrv = m_pListTail;
				m_pListTail = cur;
				cur->pBucket = pBucket;
				pBucket->pList = cur;
				return cur;
			}
			return NULL;
		}
		void				RemoveList(LIST* pList)
		{
			
			LIST*	cur = pList;
			LIST*	prv = pList->pPrv;
			LIST*	next = pList->pNext;
			
			
			if(pList == m_pListCur)
				m_pListCur = next;
			
			if (prv)
				prv->pNext = next;
			else 
				m_pListHead = next;
			
			if (next)
				next->pPrv = prv;
			else
				m_pListTail = prv;
			
			delete pList;
			pList = NULL;
			
		}
		
		
		bool				Add(T* pVoid,DWORD dwKey)
		{
			DWORD index = dwKey % m_dwMaxBucketNum;
			
			BUCKET*	cur = NULL;
			BUCKET*	prv = NULL;
			BUCKET*	next = NULL;
			
			
			if (!m_ppBucketTable[index])
			{
				
				m_ppBucketTable[index] = new BUCKET(pVoid,dwKey);
				m_ppBucketTable[index]->pList = AddList(m_ppBucketTable[index]);
				
				goto seg_ok;
			}
			else 
			{
				cur = m_ppBucketTable[index];
				while (cur)
				{
//					if (cur->dwKey == dwKey)
//						return false;
					
					prv = cur;
					cur = cur->pNext;
					
				}
				cur = prv->pNext = new BUCKET(pVoid,dwKey);
				cur->pPrv = prv;
				cur->pList = AddList(cur);
				
				goto seg_ok;
				
			}
seg_ok:
			m_dwDataNum++;
			
			return true;
		}
		
		T*					GetData(DWORD dwKey)
		{
			DWORD index = dwKey%m_dwMaxBucketNum;
			
			BUCKET* pBucket = m_ppBucketTable[index];
			
			while(pBucket)
			{
				if (pBucket->dwKey == dwKey)
				{
					return pBucket->pVoid;
				}
				pBucket = pBucket->pNext;
			}
			return NULL;
			
		}
		
		T*			 		GetData()
		{
			T*	pVoid;
			if (m_pListCur)
			{
				pVoid = m_pListCur->pBucket->pVoid;
				m_pListCur = m_pListCur->pNext;
				return pVoid;
			}
			else 
				return NULL;
			
			return pVoid;
		}		
		T*			 		GetDataPos(YHTPOSITION* ppList)
		{
			T*	pVoid;
			if (*ppList)
			{
				pVoid = (*((LIST**)ppList))->pBucket->pVoid;
				*ppList = (*((LIST**)ppList))->pNext;
				return pVoid;
			}
			else 
				return NULL;
			
			return pVoid;
		}

		void				StartGetMultiData(DWORD dwKey)
		{
			DWORD index = dwKey%m_dwMaxBucketNum;			
			m_pCurBucket = m_ppBucketTable[index];
			m_pLastBucket = NULL;
			m_MultiDataKey = dwKey;
		}		
		T*					GetMultiData()
		{
			while(m_pCurBucket)
			{
				if (m_pCurBucket->dwKey == m_MultiDataKey)
				{
					m_pLastBucket = m_pCurBucket;
					m_pCurBucket = m_pCurBucket->pNext;
					return m_pLastBucket->pVoid;
				}
				m_pCurBucket = m_pCurBucket->pNext;
			}
			return NULL;
		}
		void				RemoveCurMultiData()
		{
			DWORD dwIndex = m_MultiDataKey%m_dwMaxBucketNum;
			BUCKET*	cur = m_pLastBucket;
			BUCKET*	prv = NULL;
			BUCKET*	next = NULL;

			prv = cur->pPrv;
			next = cur->pNext;
			if (!prv)
				m_ppBucketTable[dwIndex] = next;
			else 
				prv->pNext = next;
			
			if (next)
				next->pPrv = prv;
			
			RemoveList(cur->pList);
			delete cur;
			cur = NULL;
			m_dwDataNum--;
		}

		
		inline 		void	SetPositionHead() {m_pListCur = m_pListHead;}
		inline 		YHTPOSITION	GetPositionHead() {return m_pListHead;}
		void				Remove(DWORD dwKey)
		{
			DWORD dwIndex = dwKey%m_dwMaxBucketNum;
			
			BUCKET*	cur = m_ppBucketTable[dwIndex];
			BUCKET*	prv = NULL;
			BUCKET*	next = NULL;
			
			while (cur)
			{
				if (cur->dwKey == dwKey)
				{
					prv = cur->pPrv;
					next = cur->pNext;
					if (!prv)
						m_ppBucketTable[dwIndex] = next;
					else 
						prv->pNext = next;
					
					if (next)
						next->pPrv = prv;
					
					RemoveList(cur->pList);
					delete cur;
					cur = NULL;
					m_dwDataNum--;
					return;
				}
				cur = cur->pNext;
			}
		}
		
		void				RemoveAll()
		{
			LIST*	cur = m_pListHead;
			LIST*	next = NULL;
			
			while (cur)
			{
				next = cur->pNext;
				delete cur->pBucket;
				delete cur;
				cur = next;
			}
			m_dwDataNum = 0;
			m_pListHead = NULL;
			
			if(m_ppBucketTable)
				memset(m_ppBucketTable,0,sizeof(BUCKET*)*m_dwMaxBucketNum);
		}
		
		CYHHashTable()
		{
			m_dwDataNum = 0;
			m_dwMaxBucketNum = 0;
			m_ppBucketTable = NULL;
			m_pListHead = NULL;
			m_pListTail = NULL;
			m_pListCur = NULL;
		}
		
		~CYHHashTable()
		{
			RemoveAll();
			if (m_ppBucketTable)
			{
				delete [] m_ppBucketTable;
				m_ppBucketTable = NULL;
			}
		}
};

#endif