www.pudn.com > WinGOS.rar > map.h

// CMap.h: interface for the CMap class. 
// 
////////////////////////////////////////////////////////////////////// 
 
#ifndef _GOS_MAP_H_ 
#define _GOS_MAP_H_ 
 
#define BEFORE_START_POSITION POSITION(-1) 
#define DEFAULT_HASHTABLESIZE 31 
#define DEFAULT_HASHKEY(key) (*PDWORD(&key) >> 4) 
 
///////////////////////////////////////////////////////////////////////////// 
// CMap inline functions 
 
template 
__inline int CMap::GetSize() const 
	{ return m_nCount; } 
 
template 
__inline BOOL CMap::IsEmpty() const 
	{ return m_nCount == 0; } 
 
template 
__inline void CMap::SetAt(const KEY& key, const VALUE& newValue) 
	{ (*this)[key] = newValue; } 
 
template 
__inline POSITION CMap::GetStartPosition() const 
	{ return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; } 
 
template 
__inline UINT CMap::GetHashTableSize() const 
	{ return _msize(m_pHashTable)/sizeof(CAssoc**); } 
 
///////////////////////////////////////////////////////////////////////////// 
// CMap out-of-line functions 
 
template 
CMap::CMap(int nBlockSize) 
{ 
	m_pHashTable = NULL; 
	m_nCount = 0; 
	m_pFreeList = NULL; 
	m_pBlocks = NULL; 
	m_nBlockSize = nBlockSize; 
	DEBUG_ONLY(nBlockSize=CHeap::ElementCount(sizeof(CAssoc),nBlockSize,sizeof(CPlex*))); 
	ASSERT(m_nBlockSize==nBlockSize); 
} 
 
template 
void CMap::InitHashTable(UINT nHashSize) 
// 
// Used to force allocation of a hash table or to override the default 
//   hash table size of (which is fairly small) 
{ 
	ASSERT(m_nCount == 0); 
	ASSERT(nHashSize > 0); 
 
	if (m_pHashTable != NULL) 
	{ 
		// free hash table 
		delete[] m_pHashTable; 
		m_pHashTable = NULL; 
	} 
 
	m_pHashTable = new CAssoc* [nHashSize]; 
	memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize); 
} 
 
template 
void CMap::RemoveAll() 
{ 
	// free hash table 
	delete[] m_pHashTable; 
	m_pHashTable = NULL; 
 
	m_nCount = 0; 
	m_pFreeList = NULL; 
	m_pBlocks->FreeDataChain(); 
	m_pBlocks = NULL; 
} 
 
template 
CMap::~CMap() 
{ 
	RemoveAll(); 
	ASSERT(m_nCount == 0); 
} 
 
template 
typename CMap::CAssoc* 
CMap::NewAssoc(const KEY& key) 
{ 
	if (m_pFreeList == NULL) 
	{ 
		// add another block 
		CMap::CAssoc* pAssoc = (CMap::CAssoc*)CPlex::CreateHead(m_pBlocks, 
			m_nBlockSize*sizeof(CMap::CAssoc)); 
		// 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 != NULL);  // we must have something 
 
	CMap::CAssoc* pAssoc = m_pFreeList; 
	pAssoc->key=key; 
 
	m_pFreeList = m_pFreeList->pNext; 
	m_nCount++; 
	ASSERT(m_nCount > 0);  // make sure we don't overflow 
	return pAssoc; 
} 
 
template 
void CMap::FreeAssoc(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(); 
} 
 
template 
PVOID CMap::GetAssocAt(const KEY& key, UINT& nHash) const 
// find association (or return NULL) 
{ 
	if (m_pHashTable == NULL) 
	{ 
		nHash = DEFAULT_HASHKEY(key)%DEFAULT_HASHTABLESIZE; 
		return NULL; 
	} 
	nHash = DEFAULT_HASHKEY(key)%GetHashTableSize(); 
 
	// see if it exists 
	CAssoc* pAssoc; 
	for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) 
	{ 
		if(pAssoc->key==key) 
			return pAssoc; 
	} 
	return NULL; 
} 
 
template 
BOOL CMap::Lookup(const KEY& key, VALUE& rValue) const 
{ 
	UINT nHash; 
	CAssoc* pAssoc = (CAssoc*)GetAssocAt(key, nHash); 
	if (pAssoc == NULL) 
		return FALSE;  // not in map 
 
	rValue = pAssoc->value; 
	return TRUE; 
} 
 
template 
VALUE& CMap::operator[](const KEY& key) 
{ 
	UINT nHash; 
	CAssoc* pAssoc; 
	if ((pAssoc = (CAssoc*)GetAssocAt(key, nHash)) == NULL) 
	{ 
		if (m_pHashTable == NULL) 
			InitHashTable(DEFAULT_HASHTABLESIZE); 
 
		// it doesn't exist, add a new Association 
		pAssoc = NewAssoc(key); 
 
		// put into hash table 
		pAssoc->pNext = m_pHashTable[nHash]; 
		m_pHashTable[nHash] = pAssoc; 
	} 
	return pAssoc->value;  // return new reference 
} 
 
template 
BOOL CMap::RemoveKey(const KEY& key) 
// remove key - return TRUE if removed 
{ 
	if (m_pHashTable == NULL) 
		return FALSE;  // nothing in the table 
 
	CAssoc** ppAssocPrev; 
	UINT nHash = DEFAULT_HASHKEY(key)%GetHashTableSize(); 
	ppAssocPrev = &m_pHashTable[nHash]; 
 
	CAssoc* pAssoc; 
	for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) 
	{ 
		if(pAssoc->key=key) 
		{ 
			// remove it 
			*ppAssocPrev = pAssoc->pNext;  // remove from list 
			FreeAssoc(pAssoc); 
			return TRUE; 
		} 
		ppAssocPrev = &pAssoc->pNext; 
	} 
	return FALSE;  // not found 
} 
 
template 
void CMap::GetNextAssoc(POSITION& rNextPosition, 
	KEY& rKey, VALUE& rValue) const 
{ 
	ASSERT(m_pHashTable != NULL);  // never call on empty map 
 
	UINT nHash; 
	UINT nHSize=GetHashTableSize(); 
	CAssoc* pAssocRet = (CAssoc*)rNextPosition; 
	ASSERT(pAssocRet != NULL); 
 
	if (pAssocRet == (CAssoc*) BEFORE_START_POSITION) 
	{ 
		// find the first association 
		for (nHash=0 ; nHash < nHSize; nHash++) 
			if ((pAssocRet = m_pHashTable[nHash]) != NULL) 
				break; 
		ASSERT(pAssocRet != NULL);  // must find something 
	} 
 
	// find next association 
	CAssoc* pAssocNext; 
	if ((pAssocNext = pAssocRet->pNext) == NULL) 
	{ 
		// go to next bucket 
		nHash = DEFAULT_HASKKEY(pAssocRet->key)%nHSize; 
		for (++nHash ; nHash < nHSize; nHash++) 
			if ((pAssocNext = m_pHashTable[nHash]) != NULL) 
				break; 
	} 
 
	rNextPosition = (POSITION) pAssocNext; 
 
	// fill in return data 
	rKey = pAssocRet->key; 
	rValue = pAssocRet->value; 
} 
 
#endif _GOS_MAP_H_