tmap.h

TFixedAlloc类是一个非常不错的使用与Linux和windows跨平台的内存分配工具

#ifndef __TMap_H__
#define __TMap_H__
//#include "TypeDef.h"
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "TPlex.h" //Define class TPlex

#define MAX_HASHKEY_LEN		40

template< class ARG_KEY >
inline TUINT HashKey( ARG_KEY key )
{
	// default identity hash - works for most primitive values
	return ((TUINT)(void*)(TDWORD)key) >> 4;
}

template< class TYPE, class ARG_TYPE >
TBOOL CompareElements( const TYPE * pElement1, const ARG_TYPE * pElement2 )
{
	return *pElement1 == *pElement2;
}

//****************************************** TMap -> ***********************************************//
//
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class TMap  
{
protected:
	// Association
	struct CAssoc
	{
		CAssoc * pNext;
		TUINT nHashValue;	// needed for efficient iteration
		KEY key;
		VALUE value;
	};
public:
// Construction
	TMap(int nBlockSize = 10);
	virtual ~TMap();

// Attributes
	// number of elements
	int GetCount() const;
	TBOOL IsEmpty() const;

	// Lookup
	TBOOL Lookup( ARG_KEY key,VALUE& rValue ) const;

// Operations
	// Lookup and add if not there
	VALUE& operator[]( ARG_KEY key );

	// add a new (key,value) pair
	void SetAt( ARG_KEY key,ARG_VALUE newValue );

	// removing existing (key,?) pair
	TBOOL RemoveKey( ARG_KEY key );    //待查???
	void RemoveAll();

	// iterating all (key,value) pairs
	TPOSITION GetStartPosition() const;
	void GetNextAssoc( TPOSITION& rNextPosition,KEY& rKey,VALUE& rValue ) const;

	// advanced features for derived classes
	TUINT GetHashTableSize() const;
	void InitHashTable( TUINT hashSize,TBOOL bAllocNow = TTRUE );

// Implementation
protected:
	CAssoc ** m_pHashTable;
	TUINT m_nHashTableSize;
	int m_nCount;
	CAssoc * m_pFreeList;
	struct TPlex * m_pBlocks;
	int m_nBlockSize;

	CAssoc * NewAssoc();
	void FreeAssoc( CAssoc * );
	CAssoc * GetAssocAt( ARG_KEY,TUINT& ) const;

	//void Serialize( CArchive& );

};
// TMap<KEY, ARG_KEY, VALUE, ARG_VALUE> in-of-line functions
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
inline int TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::GetCount() const
	{ return m_nCount; }
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
inline TBOOL TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::IsEmpty() const
	{ return m_nCount == 0; }
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
inline void TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::SetAt( ARG_KEY key, ARG_VALUE newValue )
	{ (*this)[ key ] = newValue; }
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
inline TPOSITION TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::GetStartPosition() const
	{ return (m_nCount == 0) ? TNULL : TBEFORE_START_POSITION; }
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
inline TUINT TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::GetHashTableSize() const
	{ return m_nHashTableSize; }
// TMap<KEY, ARG_KEY, VALUE, ARG_VALUE> out-of-line functions
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::TMap( int nBlockSize )
{
	assert( nBlockSize>0 );

	m_pHashTable = TNULL;
	m_nHashTableSize = 17;	//default size
	m_nCount = 0;
	m_pFreeList = TNULL;
	m_pBlocks = TNULL;
	m_nBlockSize = nBlockSize;
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::~TMap()
{
	RemoveAll();
	assert( m_nCount==0 );
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
TBOOL TMap< KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup( ARG_KEY key, VALUE& rValue ) const
{
	//ASSERT_VALID( this );
	TUINT nHash;
	CAssoc * pAssoc = GetAssocAt( key,nHash );
	if( pAssoc==TNULL )
		return TFALSE; // not in map
	rValue = pAssoc->value;
	return TTRUE;
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
VALUE& TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::operator[]( ARG_KEY key )
{
	//ASSERT_VALID( this );

	TUINT nHash;
	CAssoc * pAssoc;
	if( (pAssoc=GetAssocAt(key,nHash))==TNULL )
	{
		if( m_pHashTable==TNULL )
			InitHashTable( m_nHashTableSize );

		// it doesn't exist ,add a new Association
		pAssoc = NewAssoc();
		pAssoc->nHashValue = nHash;
		pAssoc->key = key;
		// 'pAssoc->value' is a constructed object , nothing more

		// put into hash table
		pAssoc->pNext = m_pHashTable[nHash];
		m_pHashTable[nHash] = pAssoc;
	}
	return pAssoc->value;	// return new reference
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
TBOOL TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::RemoveKey( ARG_KEY key )	// remove key - return TRUE if removed
{
	//ASSERT_VALID( this );
	if( m_pHashTable==TNULL )
		return TFALSE;	// nothing in the table

	CAssoc ** ppAssocPrev;
	ppAssocPrev = &m_pHashTable[ HashKey<ARG_KEY>(key) % m_nHashTableSize ];

	CAssoc * pAssoc;
	for( pAssoc = *ppAssocPrev; pAssoc!=TNULL; pAssoc = pAssoc->pNext )
	{
		if( CompareElements(&pAssoc->key,&key) ) 
		{
			// remove it
			*ppAssocPrev = pAssoc->pNext;	//remove from list
			FreeAssoc( pAssoc );
			return TTRUE;
		}
		ppAssocPrev = & pAssoc->pNext;
	}
	return TFALSE;	// not found
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
void TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::RemoveAll()
{
	//ASSERT_VALID( this );
	if( m_pHashTable!=TNULL )
	{
		// destroy elements (values and keys)
		for( TUINT nHash=0; nHash < m_nHashTableSize; nHash++ )
		{
			CAssoc * pAssoc;
			for( pAssoc = m_pHashTable[nHash]; pAssoc!=TNULL; pAssoc = pAssoc->pNext )  
			{
				//DestructElements<VALUE>(&pAssoc->value, 1);
				//DestructElements<KEY>(&pAssoc->key, 1);
			}
		}
	}
	// free hash table
	delete [] m_pHashTable;
	m_pHashTable = TNULL;

	m_nCount = 0;
	m_pFreeList = TNULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = TNULL;
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
void TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::GetNextAssoc( TPOSITION& rNextPosition,KEY& rKey, VALUE& rValue ) const
{
	//ASSERT_VALID( this );
	assert( m_pHashTable!=TNULL );	//never call on empty map
	
	CAssoc * pAssocRet = (CAssoc *)rNextPosition;
	assert( pAssocRet!=TNULL );

	if( pAssocRet==(CAssoc *)TBEFORE_START_POSITION )
	{
		// find the first association
		for( TUINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++ )
			if( (pAssocRet = m_pHashTable[nBucket]) != TNULL )
				break;
		assert( pAssocRet != TNULL );	// must find something
	}

	// find next association
	CAssoc * pAssocNext;
	if( (pAssocNext = pAssocRet->pNext) == TNULL )
	{
		// go to next bucket
		for( TUINT nBucket = pAssocRet->nHashValue+1; nBucket<m_nHashTableSize; nBucket++ )
			if( (pAssocNext=m_pHashTable[nBucket]) != TNULL )
				break;
	}
	
	rNextPosition = (TPOSITION) pAssocNext;

	//fill in return data
	rKey = pAssocRet->key;
	rValue = pAssocRet->value;
}

// Used to force allocation of a hash table or to override the default
//   hash table size of (which is fairly small)
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
void TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::InitHashTable( TUINT nHashSize, TBOOL bAllocNow )
{
	//ASSERT_VALID( this );
	assert( m_nCount==0 );
	assert( nHashSize>0 );

	if( m_pHashTable!=TNULL )
	{
		// free hash table
		delete [] m_pHashTable;
		m_pHashTable = TNULL;
	}

	if( bAllocNow )
	{
		m_pHashTable = new CAssoc*[nHashSize];
		memset( m_pHashTable,0,sizeof(CAssoc *)*nHashSize );
	}
	m_nHashTableSize = nHashSize;
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::CAssoc*
TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::NewAssoc()
{
	if( m_pFreeList==TNULL )
	{
		// add another block
		TPlex * newBlock = TPlex::Create( m_pBlocks,m_nBlockSize,sizeof(TMap::CAssoc) );
		// chain them into free list
		TMap::CAssoc * pAssoc = (TMap::CAssoc *)newBlock->data();
		// free in reverse order to make it easier to debug
		pAssoc += m_nBlockSize - 1;
		for( int i = m_nBlockSize-1; i>=0; i--,pAssoc-- )
		{
			pAssoc->pNext = m_pFreeList;
			m_pFreeList = pAssoc;
		}
	}
	assert( m_pFreeList!=TNULL ); //we must have something

	TMap::CAssoc * pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	m_nCount ++;
	assert( m_nCount>0 );	//make sure we don't overflow
	//ConstructElements<KEY>(&pAssoc->key, 1);
	//ConstructElements<VALUE>(&pAssoc->value, 1);   // special construct values
	return pAssoc;
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
void TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::FreeAssoc( TMap::CAssoc* pAssoc )
{
	//DestructElements<VALUE>(&pAssoc->value, 1);
	//DestructElements<KEY>(&pAssoc->key, 1);
	pAssoc->pNext = m_pFreeList;
	m_pFreeList = pAssoc;
	m_nCount--;
	assert( m_nCount>=0 );	// make sure we don't underflow

	// if no more elements, cleanup completely
	if( m_nCount==0 )
		RemoveAll();
}

template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::CAssoc*
TMap< KEY, ARG_KEY, VALUE, ARG_VALUE >::GetAssocAt( ARG_KEY key, TUINT& nHash ) const // find association (or return TNULL)
{
	nHash = HashKey<ARG_KEY>(key) % m_nHashTableSize;

	if( m_pHashTable==TNULL )
		return TNULL;
	// see if it exists
	CAssoc * pAssoc;
	for( pAssoc = m_pHashTable[nHash]; pAssoc!=TNULL; pAssoc=pAssoc->pNext )
	{
		if( CompareElements(&pAssoc->key,&key) )
			return pAssoc;
	}
	return TNULL;
}
//
//****************************************** <- TMap ***********************************************//
//**************************************************************************************************//
//****************************************** TMapStringToPtr -> ***********************************************//
//
class TMapStringToPtr
{
public:
	struct CAssoc
	{
		CAssoc * pNext;
		TUINT nHashValue;
		char key[MAX_HASHKEY_LEN];
		void * value;
	};
public:
	TMapStringToPtr();
	TMapStringToPtr( int nBlockSize );
	virtual ~TMapStringToPtr();

	int GetCount() const;
	TBOOL IsEmpty() const;

	TBOOL Lookup( TLPCSTR key,void *& rValue ) const;
	TBOOL LookupKey( TLPCSTR key,TLPCSTR & rkey ) const;

	void *& operator[]( TLPCSTR key );

	void SetAt( TLPCSTR key,void * newValue );

	TBOOL RemoveKey( TLPCSTR key );
	void RemoveAll();

	TPOSITION GetStartPosition() const;
	void GetNextAssoc( TPOSITION & rNextPosition,char *& rKey,void *& rValue) const;


	TUINT GetHashTableSize() const;
	void InitHashTable( TUINT hashSize,TBOOL bAllocNow = TTRUE );

	TUINT HashKey( TLPCSTR key ) const;

protected:
	CAssoc ** m_pHashTable;
	TUINT m_nHashTableSize;
	int m_nCount;
	CAssoc * m_pFreeList;
	struct TPlex * m_pBlocks;
	int m_nBlockSize;

	CAssoc * NewAssoc();
	void FreeAssoc( CAssoc * );
	CAssoc * GetAssocAt( TLPCSTR ,TUINT & ) const;

protected:
	typedef char * BASE_KEY;
	typedef TLPCSTR BASE_ARG_KEY;
	typedef void * BASE_VALUE;
	typedef void * BASE_ARG_VALUE;
};
// TMapStringToPtr in-of-line functions
inline int TMapStringToPtr::GetCount() const
{
	return m_nCount;
}
inline TBOOL TMapStringToPtr::IsEmpty() const
{
	return m_nCount==0;
}
inline void TMapStringToPtr::SetAt( TLPCSTR key,void * newValue )
{
	(*this)[key] = newValue;
}
inline TPOSITION TMapStringToPtr::GetStartPosition() const
{
	return (m_nCount==0) ? TNULL : TBEFORE_START_POSITION;
}
inline TUINT TMapStringToPtr::GetHashTableSize() const
{
	return m_nHashTableSize;
}
//
//****************************************** <- TMapStringToPtr ***********************************************//
//*************************************************************************************************************//
//****************************************** TTypedPtrMap -> ***********************************************//
//
template< class BASE_CLASS, class KEY, class VALUE >
class TTypedPtrMap : public BASE_CLASS
{
public:
// construction
	TTypedPtrMap( int nBlockSize = 10 )
		: BASE_CLASS( nBlockSize ) {};

	// Lookup
	//ZBOOL Lookup(ZLPCSTR key, VALUE& rValue) const
	//	{ return BASE_CLASS::Lookup(key, (BASE_CLASS::BASE_VALUE&)rValue); }

	TBOOL Lookup( TLPCSTR key,VALUE & rValue ) const
	{
		return BASE_CLASS::Lookup(key,(void *&)rValue);
	}

	// Lookup and add if not there
	VALUE& operator[]( TLPCSTR key )
	{
		return (VALUE&)BASE_CLASS::operator[]( key );
	}

	// add a new key( key,value) pair
	void SetAt( KEY key,VALUE newValue )
	{
		return BASE_CLASS::SetAt(key,newValue);
	}

	//removing existing(key ,?) pair
	TBOOL RemoveKey( KEY key )
	{
		return BASE_CLASS::RemoveKey( key );
	}

	// iteration
	//void GetNextAssoc( TPOSITION& rPosition, KEY& rKey, VALUE& rValue) const
	//	{ BASE_CLASS::GetNextAssoc(rPosition, (char*&)rKey,
	//		(BASE_CLASS::BASE_VALUE&)rValue); }

	void GetNextAssoc( TPOSITION& rPosition,KEY& rKey,VALUE& rValue) const
	{
		BASE_CLASS::GetNextAssoc( rPosition, (char*&)rKey,(void*&)rValue);
	}
};
//
//****************************************** <- TTypedPtrMap ***********************************************//
#endif //__TMap_H__