solarhashtable.h

奇迹世界公用文件源代码,研究网络游戏的朋友可以研究下

// SolarHashTable.h: interface for the SolarHashTable class.
// Hash Table Class version 1.0
// source code created by Min-Wook Kim ([e-mail])
// 2004-7-29
// 
//-------------------------------------------------------------------
// History.
// 2004-07-27 : HashTable class was created with MemoryPool
// 2004-07-29 : added m_dwBucketKey
// 2004-12-21 : change class name, CHashTable to SolarHashTable
// 2005-04-26 : added class < KeyType=DWORD >
// 2005-08-08 : added find() method for iterator class 
//-------------------------------------------------------------------
// example)
//
// SolarHashTable<TTT> * hashTable = new SolarHashTable<TTT>;
// hashTable->Initialize(100);
// hashTable->RemoveAll();
// delete hashTable;

// caution) duplicated loop ( duplicated GetNext() traveling ) is bad usage
////////////////////////////////////////////////////////////////////////////

#ifndef __SOLAR_HASH_TABLE_H__
#define __SOLAR_HASH_TABLE_H__

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000


#include "MemoryPoolFactory.h"

using namespace util;

namespace util
{

template <class T, class KeyType=DWORD >
class SolarHashTable
{	
	class HashBucket;

	class HashList
	{
	public:
		HashList *		pNext;
		HashList *		pPrv;
		HashBucket *	pBucket;
	};

	class HashBucket
	{
	public:
		KeyType			dwKey;
		T				TData;
		HashList *		pList;		// 傈眉 滚哦府胶飘
		HashBucket *	pNext;		// 悼老 虐蔼阑 啊瘤绰 滚哦府胶飘俊 措茄 Next
		HashBucket *	pPrv;
		void SetData(T pvoid, KeyType key) { TData = pvoid;dwKey = key; pNext = NULL; pPrv = NULL; }
	};

	BOOL				m_bInited;
protected:
	DWORD				m_dwDataNum;
	DWORD				m_dwMaxBucketNum;
	HashBucket **		m_ppBucketTable;

	/// for iterator
	HashList *			m_pListTail;
	HashList * 			m_pListHead;
	HashList *			m_pListCur;
	
	/// for bucket iterator
	HashBucket *		m_pCurBucket;
	HashBucket*			m_pLastBucket;
	KeyType				m_dwBucketKey;

	// memorypool
	CMemoryPoolFactory<HashBucket>	* m_pHashBucketPool;
	CMemoryPoolFactory<HashList>	* m_pHashListPool;

public:

	SolarHashTable()
	{
		m_dwDataNum			= 0;
		m_dwMaxBucketNum	= 0;
		m_ppBucketTable		= NULL;
		m_pListHead			= NULL;
		m_pListTail			= NULL;
		m_pListCur			= NULL;
		m_pCurBucket		= NULL;
		m_pHashListPool		= NULL;
		m_pHashBucketPool	= NULL;
		m_bInited			= FALSE;
	}

	SolarHashTable( DWORD dwMaxBucketNum )
	{
		m_dwDataNum			= 0;
		m_dwMaxBucketNum	= 0;
		m_ppBucketTable		= NULL;
		m_pListHead			= NULL;
		m_pListTail			= NULL;
		m_pListCur			= NULL;
		m_pCurBucket		= NULL;
		m_pHashListPool		= NULL;
		m_pHashBucketPool	= NULL;
		m_bInited			= FALSE;

		Initialize( dwMaxBucketNum );
	}
	
	virtual ~SolarHashTable()
	{
		RemoveAll();
		if (m_ppBucketTable)
		{
			delete [] m_ppBucketTable;
			m_ppBucketTable = NULL;
		}
		
		if(m_pHashListPool)
		{
			m_pHashListPool->Release();
			delete m_pHashListPool;
			m_pHashListPool = NULL;
		}
		if( m_pHashBucketPool )
		{
			m_pHashBucketPool->Release();
			delete m_pHashBucketPool;
			m_pHashBucketPool = NULL;
		}
	}
	
	inline KeyType		GetDataNum() { return m_dwDataNum; }
	BOOL				Initialize(DWORD dwMaxBucketNum)
	{
		if( m_bInited ) return FALSE;

		ASSERT( NULL == m_pHashBucketPool );
		ASSERT( NULL == m_pHashListPool );
		m_dwDataNum			= 0;
		m_dwMaxBucketNum	= dwMaxBucketNum;
		m_ppBucketTable		= NULL;
		m_pListHead			= NULL;
		m_pListTail			= NULL;
		m_pListCur			= NULL;
		m_pCurBucket		= NULL;
		
		m_pHashBucketPool	= new CMemoryPoolFactory<HashBucket>;
		m_pHashListPool		= new CMemoryPoolFactory<HashList>;
		m_pHashBucketPool->Initialize( dwMaxBucketNum, dwMaxBucketNum/2+1 );
		m_pHashListPool->Initialize( dwMaxBucketNum, dwMaxBucketNum/2+1 );
		
		m_ppBucketTable = new HashBucket *[m_dwMaxBucketNum];
		
		if( !m_ppBucketTable )
			return FALSE;
		
		memset(m_ppBucketTable, 0, sizeof(HashBucket *) * m_dwMaxBucketNum);
		m_bInited			= TRUE;
		return TRUE;
		
	}
	/// don't check for the same key
	BOOL				Add(T TData, KeyType dwKey)
	{
		KeyType index = dwKey % m_dwMaxBucketNum;
		
		HashBucket *	cur = NULL;
		HashBucket *	prv = NULL;
		//HashBucket *	next = NULL;
		
		
		if (!m_ppBucketTable[index])
		{
			
			m_ppBucketTable[index] = m_pHashBucketPool->Alloc();
			m_ppBucketTable[index]->SetData( TData, dwKey );
			m_ppBucketTable[index]->pList = addList(m_ppBucketTable[index]);

		}
		else 
		{
			cur = m_ppBucketTable[index];
			while (cur)
			{
				prv = cur;
				cur = cur->pNext;
			}
			cur = prv->pNext = m_pHashBucketPool->Alloc();
			cur->SetData( TData, dwKey );
			cur->pPrv = prv;
			cur->pList = addList(cur);
			
		}
		m_dwDataNum++;
		
		return TRUE;
	}
	
	T					GetData(KeyType dwKey)
	{
		KeyType index = dwKey % m_dwMaxBucketNum;
		
		HashBucket* pBucket = m_ppBucketTable[index];
		
		while(pBucket)
		{
			if (pBucket->dwKey == dwKey)
			{
				return pBucket->TData;
			}
			pBucket = pBucket->pNext;
		}
		return NULL;
		
	}
	
	T					GetHeadData() { if( !m_pListHead ) return NULL; return m_pListHead->pBucket->TData;	}
	T					GetTailData() { if( !m_pListTail ) return NULL; return m_pListTail->pBucket->TData;	}
	
	/// Iterate List
	inline void			SetFirst() { m_pListCur = m_pListHead; }
	T			 		GetNext()
	{
		if (m_pListCur)
		{
			const T& TData = m_pListCur->pBucket->TData;
			m_pListCur = m_pListCur->pNext;
			return TData;
		}

		return NULL;		
	}

	inline void			SetLast() { m_pListCur = m_pListTail;	}
	T			 		GetPrev()
	{
		if (m_pListCur)
		{
			const T& TData = m_pListCur->pBucket->TData;
			m_pListCur = m_pListCur->pPrv;
			return TData;
		}

		return NULL;		
	}


	
	/// Iterate Bucket Chain List
	void				SetBucketFirst(KeyType dwKey)
	{
		KeyType index = dwKey % m_dwMaxBucketNum;			
		m_dwBucketKey = dwKey;
		m_pCurBucket = m_ppBucketTable[index];
		m_pLastBucket = NULL;
	}		
	T					GetBucketNext()
	{
		while(m_pCurBucket)
		{
			if (m_pCurBucket->dwKey == m_dwBucketKey)
			{
				T	TData = m_pCurBucket->TData;
				m_pLastBucket = m_pCurBucket;
				m_pCurBucket = m_pCurBucket->pNext;
				return TData;
			}
			m_pCurBucket = m_pCurBucket->pNext;
		}
		return NULL;
	}
	void				RemoveCurBucketData()
	{
		KeyType dwIndex = m_dwBucketKey%m_dwMaxBucketNum;
		HashBucket*	cur = m_pLastBucket;
		HashBucket*	prv = NULL;
		HashBucket*	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);
		m_pHashBucketPool->Free(cur);
		cur = NULL;
		--m_dwDataNum;
	}

	
	/// delete bucket, list for (dwKey)
	void				Remove(KeyType dwKey)
	{
		KeyType dwIndex = dwKey % m_dwMaxBucketNum;
		
		HashBucket*	cur = m_ppBucketTable[dwIndex];
		HashBucket*	prv = NULL;
		HashBucket*	next = NULL;
		
		while (cur)
		{
			if (cur->dwKey == dwKey)
			{
				prv = cur->pPrv;
				next = cur->pNext;

				if(cur == m_pCurBucket)			/// for iterator sync
					m_pCurBucket = next;

				if (!prv)
					m_ppBucketTable[dwIndex] = next;
				else 
					prv->pNext = next;
				
				if (next)
					next->pPrv = prv;
				
				removeList(cur->pList);
				m_pHashBucketPool->Free(cur);//delete cur;
				cur = NULL;
				--m_dwDataNum;
				return;
			}
			cur = cur->pNext;
		}
	}

	T					RemoveHead()
	{
		HashList*	cur = m_pListHead;
		if( !cur ) return NULL;
		m_pListHead = m_pListHead->pNext;
		T data = cur->pBucket->TData;

		m_pHashBucketPool->Free(cur->pBucket);	//delete cur->pBucket;
		m_pHashListPool->Free(cur);				//delete cur;

		--m_dwDataNum;

		return data;
	}
	/// delete all of Bucket, List Node
	void				RemoveAll()
	{
		HashList*	cur = m_pListHead;
		HashList*	next = NULL;
		
		while (cur)
		{
			next = cur->pNext;
			m_pHashBucketPool->Free(cur->pBucket);	//delete cur->pBucket;
			m_pHashListPool->Free(cur);				//delete cur;
			cur = next;
		}
		m_dwDataNum = 0;
		m_pListHead = NULL;
		
		if(m_ppBucketTable)
			memset(m_ppBucketTable, 0, sizeof(HashBucket *) * m_dwMaxBucketNum);
	}
	
	//------------------------------------------------------------------------------
	// iterator 
	//------------------------------------------------------------------------------
	class iterator
	{
		friend class SolarHashTable;
		HashList * _current;

	public:
		iterator():_current(NULL){}
		iterator( const iterator & itr ):_current(itr._current){}
		~iterator(){}

		iterator & operator++()
		{
			if( _current ) _current = _current->pNext;
			return *this;
		}
		iterator & operator++( int i )
		{
			if( _current ) _current = _current->pNext;
			return *this;
		}
		iterator & operator--()
		{
			if( _current ) _current = _current->pPrv;
			return *this;
		}
		iterator & operator--( int i )
		{
			if( _current ) _current = _current->pPrv;
			return *this;
		}

		BOOL operator!=( iterator & it )
		{
			return ( it._current != _current );
		}
		BOOL operator==( iterator & it )
		{
			return ( it._current == _current );
		}
		T operator*()
		{
			if( _current ) return _current->pBucket->TData;
			return NULL;
		}
	};

	iterator find( KeyType dwKey )
	{
		KeyType index = dwKey % m_dwMaxBucketNum;

		HashBucket* pBucket = m_ppBucketTable[index];

		while(pBucket)
		{
			if (pBucket->dwKey == dwKey)
			{
				break;
			}
			pBucket = pBucket->pNext;
		}
		iterator it;
		if( pBucket )
			it._current = pBucket->pList;
		else
			it._current = NULL;
		return it;
	}

	iterator begin()
	{
		iterator it;
		it._current = m_pListHead;
		return it;
	}
	iterator end()
	{
		iterator it;
		it._current = NULL;
		return it;
	}

	void erase( iterator & it )
	{
		Remove( it._current->pBucket->dwKey );
	}
	void clear()
	{
		RemoveAll();
		ASSERT( 0 == GetDataNum() );
	}
	
protected:
	HashList *				addList(HashBucket * pBucket)
	{
		HashList*	cur = NULL;
		//HashList*	prv = NULL;
		//HashList*	next = NULL;
		
		if (!m_pListHead)
		{
			m_pListCur = m_pListHead = m_pHashListPool->Alloc();
			m_pListCur->pPrv	= NULL;
			m_pListCur->pNext	= NULL;
			
			m_pListTail = m_pListCur;
			m_pListCur->pBucket = pBucket;
			pBucket->pList = m_pListHead;
			return m_pListHead;
		}
		//else
		{
			cur = m_pListTail->pNext = m_pHashListPool->Alloc();
			cur->pNext	= NULL;
			cur->pPrv	= m_pListTail;
			m_pListTail = cur;
			cur->pBucket = pBucket;
			pBucket->pList = cur;
			return cur;
		}
		//return NULL;
	}
	void				removeList(HashList * pList)
	{
		
	//	HashList*	cur = pList;
		HashList*	prv = pList->pPrv;
		HashList*	next = pList->pNext;
		
		
		if(pList == m_pListCur)		/// for iterator sync
			m_pListCur = next;
		
		if (prv)
			prv->pNext = next;
		else 
			m_pListHead = next;
		
		if (next)
			next->pPrv = prv;
		else
			m_pListTail = prv;
		
		m_pHashListPool->Free(pList);//delete pList;
		pList = NULL;
		
	}
	
};


} /// namespace util




#endif //__SOLAR_HASH_TABLE_H__