growablemap.h

Data Replication Prototype Using ADO

#ifndef GrowableMap_h_
#define GrowableMap_h_

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class CGrowableMap : public CObject
{

enum { START_SIZE = 16 }; 

protected:
	// Association
	struct CAssoc
	{
		CAssoc* pNext;
		UINT nHashValue;  // needed for efficient iteration
		KEY key;
		VALUE value;
	};
public:
	CGrowableMap(int nBlockSize = 10) 
	{ 
		m_pHashTable = NULL;
		m_nHashTableSize = START_SIZE; 
		m_nCount = 0;
		m_pFreeList = NULL;
		m_pBlocks = NULL;
		m_nBlockSize = nBlockSize;
	}


	BOOL Lookup(ARG_KEY key, VALUE& rValue) const
	{
		ASSERT_VALID(this);

		UINT nHash;
		CAssoc* pAssoc = GetAssocAt(key, nHash);
		if (pAssoc == NULL)
			return FALSE;  // not in map

		rValue = pAssoc->value;
		return TRUE;
	}

	VALUE& operator[](ARG_KEY key)
	{
		ASSERT_VALID(this);

		UINT nHash;
		CAssoc* pAssoc;
		if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
		{
			if (m_pHashTable == NULL)
				InitHashTable(m_nHashTableSize);
			else if (m_nCount > signed(m_nHashTableSize * 2))
			{
				CAssoc** pHashTable = new CAssoc* [m_nHashTableSize * 2];
				memset(pHashTable+m_nHashTableSize, 0, sizeof(CAssoc*) * m_nHashTableSize);
				memcpy(pHashTable, m_pHashTable, sizeof(CAssoc*) * m_nHashTableSize);
				delete m_pHashTable;
				m_pHashTable = pHashTable;
				m_nHashTableSize *= 2;

				nHash = HashKey_(key) % 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
	}

	void SetAt(ARG_KEY key, ARG_VALUE newValue)
		{ (*this)[key] = newValue; }

	void RemoveAll() 
	{ 
		ASSERT_VALID(this);

		if (m_pHashTable != NULL)
		{
			// destroy elements (values and keys)
			for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
			{
				CAssoc* pAssoc;
				for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
				  pAssoc = pAssoc->pNext)
				{
					pAssoc->CAssoc::~CAssoc();
					//DestructElements<VALUE>(&pAssoc->value, 1);
					//DestructElements<KEY>(&pAssoc->key, 1);
				}
			}
		}

		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;

		m_nCount = 0;
		m_pFreeList = NULL;
		m_pBlocks->FreeDataChain();
		m_pBlocks = NULL;

		m_nHashTableSize = START_SIZE; 
	}

	int GetCount() const { return m_nCount; }

	BOOL IsEmpty() const { return m_nCount == 0; }

	POSITION GetStartPosition() const
	{ return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }

	void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const
	{
		ASSERT_VALID(this);
		ASSERT(m_pHashTable != NULL);  // never call on empty map

		CAssoc* pAssocRet = (CAssoc*)rNextPosition;
		ASSERT(pAssocRet != NULL);

		if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
		{
			// find the first association
			for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
				if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
					break;
			ASSERT(pAssocRet != NULL);  // must find something
		}

		// find next association
		ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
		CAssoc* pAssocNext;
		if ((pAssocNext = pAssocRet->pNext) == NULL)
		{
			// go to next bucket
			for (UINT nBucket = pAssocRet->nHashValue + 1;
			  nBucket < m_nHashTableSize; nBucket++)
				if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
					break;
		}

		rNextPosition = (POSITION) pAssocNext;

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

	void InitHashTable(UINT nHashSize, BOOL bAllocNow = TRUE)
	//
	// Used to force allocation of a hash table or to override the default
	//   hash table size of (which is fairly small)
	{
		ASSERT_VALID(this);
		ASSERT(m_nCount == 0);
		ASSERT(nHashSize > 0);

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

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

// Implementation
protected:
	CAssoc** m_pHashTable;
	UINT m_nHashTableSize;
	int m_nCount;
	CAssoc* m_pFreeList;
	struct CPlex* m_pBlocks;
	int m_nBlockSize;

	static UINT HashKey_(ARG_KEY key) 
	{
		return (HashKey/*<ARG_KEY>*/(key) * 2654435761UL) >> 11;
	}

	CAssoc* GetAssocAt(ARG_KEY key, UINT& nHash) const
	// find association (or return NULL)
	{
		UINT nHashKey = HashKey_(key);
		nHash = nHashKey % m_nHashTableSize;

		if (m_pHashTable == NULL)
			return NULL;

		// see if it exists
		for (CAssoc* pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
		{
			if (CompareElements(&pAssoc->key, &key))
				return pAssoc;
		}

		UINT nHashTableSize = m_nHashTableSize;
		UINT nOldHash = nHash;
		while(nHashTableSize > START_SIZE)
		{
			nHashTableSize /= 2;
			if(nOldHash >= nHashTableSize)
			{
				nOldHash = nHashKey % nHashTableSize;
				CAssoc* pAssoc;
				for(CAssoc** ppAssoc = m_pHashTable + nOldHash
				; (pAssoc = *ppAssoc) != NULL
				; ppAssoc = &(pAssoc->pNext))
				{
					if (CompareElements(&pAssoc->key, &key))
					{
						pAssoc->nHashValue = nHash;
						*ppAssoc = pAssoc->pNext;
						pAssoc->pNext = m_pHashTable[nHash];
						m_pHashTable[nHash] = pAssoc;
						return pAssoc;
					}
				}
			}
		}
		ASSERT(START_SIZE == nHashTableSize);

		return NULL;
	}

	CAssoc* NewAssoc()
	{
		if (m_pFreeList == NULL)
		{
			// add another block
			CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CAssoc));
			// chain them into free list
			CAssoc* pAssoc = (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 != NULL);  // we must have something

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

//	void FreeAssoc(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();
//	}

public:
	~CGrowableMap()
	{
		RemoveAll();
		ASSERT(m_nCount == 0);
	}
};


#endif //GrowableMap_h_