?? tmap.h
字號:
#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__
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -