tmap.cpp

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

#include "TMap.h"
//****************************************** TMapStringToPtr -> ***********************************************//
//
TMapStringToPtr::TMapStringToPtr()
{
	m_pHashTable = TNULL;
	m_nHashTableSize = 17;	// default size
	m_nCount = 0;
	m_pFreeList = TNULL;
	m_pBlocks = TNULL;
	m_nBlockSize = 10;
}

TMapStringToPtr::TMapStringToPtr( int nBlockSize )
{
	m_pHashTable = TNULL;
	m_nHashTableSize = 17;	// default size
	m_nCount = 0;
	m_pFreeList = TNULL;
	m_pBlocks = TNULL;
	m_nBlockSize = nBlockSize;
}

TMapStringToPtr::~TMapStringToPtr()
{
	RemoveAll();
	assert( m_nCount==0 );
}

TBOOL TMapStringToPtr::Lookup( TLPCSTR key,void *& rValue ) const
{
	TUINT nHash;
	CAssoc * pAssoc = GetAssocAt( key,nHash );
	if( pAssoc==TNULL )
		return TFALSE;	// not in map

	rValue = pAssoc->value;
	return TTRUE;
}

TBOOL TMapStringToPtr::LookupKey( TLPCSTR key,TLPCSTR & rkey ) const
{
	TUINT nHash;
	CAssoc * pAssoc = GetAssocAt( key,nHash );
	if( pAssoc==TNULL )
		return TFALSE;	// not in map;
	rkey = pAssoc->key;
	return TTRUE;
}

void *& TMapStringToPtr::operator[]( TLPCSTR key )
{
	TUINT nHash;
	CAssoc * pAssoc;
	if( (pAssoc=GetAssocAt(key,nHash)) == TNULL )
	{
		if( m_pHashTable==TNULL )
			InitHashTable( m_nHashTableSize );

		pAssoc = NewAssoc();
		pAssoc->nHashValue = nHash;

		int nLen = strlen( key );
		assert( nLen<=MAX_HASHKEY_LEN-1 );
		strcpy( pAssoc->key,key );

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

TBOOL TMapStringToPtr::RemoveKey( TLPCSTR key )	// remove key - return TTRUE if remove
{
	if( m_pHashTable==TNULL )
		return TFALSE;	// nothing in the table

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

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

void TMapStringToPtr::RemoveAll()
{
	if( m_pHashTable != TNULL )
	{
		delete [] m_pHashTable;
		m_pHashTable = TNULL;
	}
	m_nCount = 0;
	m_pFreeList = TNULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = TNULL;
}

void TMapStringToPtr::GetNextAssoc( TPOSITION & rNextPosition,char *& rKey,void *& rValue) const
{
	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
	//strcpy( rKey,pAssocRet->key );
	rKey = pAssocRet->key;
	rValue = pAssocRet->value;
}

void TMapStringToPtr::InitHashTable( TUINT nHashSize,TBOOL bAllocNow )
{
	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];
#ifdef _UNITTEST_
		 //        m_pHashTable = TNULL;
#endif
		if( m_pHashTable==TNULL )
		{
			char szException[60]={0};
			sprintf( szException,"%s:%d",__FILE__,__LINE__ );
			//printf(szException);
			return;
		}
		memset( m_pHashTable,0,sizeof(CAssoc *) * nHashSize );
	}
	m_nHashTableSize = nHashSize;
}

inline TUINT TMapStringToPtr::HashKey( TLPCSTR key ) const
{
	TUINT nHash = 0;
	while( *key )
	{
		nHash = (nHash<<5) + nHash + *key++;
	}
	return nHash;
}

TMapStringToPtr::CAssoc * TMapStringToPtr::NewAssoc()
{
	if( m_pFreeList==TNULL )
	{
		// add another block
		TPlex * newBlock = TPlex::Create( m_pBlocks,m_nBlockSize,sizeof(TMapStringToPtr::CAssoc) );
		// chain them into free list
		TMapStringToPtr::CAssoc * pAssoc = (TMapStringToPtr::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

	TMapStringToPtr::CAssoc * pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	m_nCount++;
	assert( m_nCount>0 );	// make sure we don't overflow
	memset( pAssoc->key,0,sizeof(pAssoc->key) / sizeof(char) );
	pAssoc->value = 0;
	return pAssoc;
}

void TMapStringToPtr::FreeAssoc( TMapStringToPtr::CAssoc * pAssoc )
{
	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();
}

TMapStringToPtr::CAssoc * TMapStringToPtr::GetAssocAt( TLPCSTR key,TUINT & nHash ) const	// find association (or return TNULL)
{
	nHash = HashKey(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( strcmp(pAssoc->key,key)==0 )
			return pAssoc;
	}
	return TNULL;
}
//
//****************************************** <- TMapStringToPtr ***********************************************//


//////////////////////////////////////////////////////////////////////