A Comprehensive CE Class Library to Replace ATL and MFC

#if !defined(__KXSet_h )
#define __KXSet_h 

//
// This implmentation on a set template is just a rip off from the
// CMap template in the Microsoft Foundation Classes.  All the Value
// peocessing was removed in order to implement a hash table without
// associations, or a set.
//

struct CPlex     // warning variable length structure
{
	CPlex* pNext;
#if (_AFX_PACKING >= 8)
	DWORD dwReserved[1];    // align on 8 byte boundary
#endif
	// BYTE data[maxNum*elementSize];

	void* data() { return this+1; }

//	static CPlex* PASCAL Create(CPlex*& head, UINT nMax, UINT cbElement);
			// like 'calloc' but no zero fill
			// may throw memory exceptions
static CPlex* PASCAL CPlex::Create(CPlex*& pHead, UINT nMax, UINT cbElement)
{
	ASSERT(nMax > 0 && cbElement > 0);
	CPlex* p = (CPlex*) new BYTE[sizeof(CPlex) + nMax * cbElement];
			// may throw exception
	p->pNext = pHead;
	pHead = p;  // change head (adds in reverse order for simplicity)
	return p;
}

	void FreeDataChain()     // free this one and links
	{
		CPlex* p = this;
		while (p != NULL)
		{
			BYTE* bytes = (BYTE*) p;
			CPlex* pNext = p->pNext;
			delete[] bytes;
			p = pNext;
		}
	}
};





typedef void* POSITION;
#define BEFORE_START_POSITION ((POSITION)-1L)

/////////////////////////////////////////////////////////////////////////////
// CeSet<KEY, ARG_KEY>

template<class KEY, class ARG_KEY>
class CeSet
{
protected:
	// Association
	struct CAssoc
	{
		CAssoc* pNext;
		UINT nHashValue;  // needed for efficient iteration
		KEY key;
	};
public:
// Construction
	CeSet(int nBlockSize = 10);

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

	// Lookup
	BOOL Lookup(ARG_KEY key) const;
	BOOL operator[](ARG_KEY key) const;

// Operations
	// removing existing key
	BOOL RemoveKey(ARG_KEY key);
	void RemoveAll();

   // add a new key
   void AddKey(ARG_KEY key);
   void SetAt(ARG_KEY key);

	// iterating all keys
	POSITION GetStartPosition() const;
	void GetNextAssoc(POSITION& rNextPosition, KEY& rKey) const;

	// advanced features for derived classes
	UINT GetHashTableSize() const;
	void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);

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

	UINT HashKey(KEY key) const
	{
		// default identity hash - works for most primitive values
		return ((UINT)(void*)(DWORD)key) >> 4;
	}

	BOOL CompareElements(const KEY* pElement1, const ARG_KEY* pElement2) const
	{
		ASSERT_VALID(pElement1);
		ASSERT_VALID(pElement2);

		return *pElement1 == *pElement2;
	}

	void DestructElements(KEY* pElements, int nCount)
	{
		// call the destructor(s)
		for (; nCount--; pElements++)
			pElements->~KEY();
	}

	void ConstructElements(KEY* pElements, int nCount)
	{
		// first do byte-wise zero initialization
		memset((void*)pElements, 0, nCount * sizeof(KEY));

		// then call the constructor(s)
		//for (; nCount--; pElements++)
		//	::new ((void*)pElements); // KEY;
	}


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

public:
	~CeSet();
};

/////////////////////////////////////////////////////////////////////////////
// CeSet<KEY, ARG_KEY> inline functions

template<class KEY, class ARG_KEY>
inline int CeSet<KEY, ARG_KEY>::GetCount() const
	{ return m_nCount; }

template<class KEY, class ARG_KEY>
inline BOOL CeSet<KEY, ARG_KEY>::IsEmpty() const
	{ return m_nCount == 0; }

template<class KEY, class ARG_KEY>
inline void CeSet<KEY, ARG_KEY>::SetAt(ARG_KEY key)
	{ AddKey(key); }

template<class KEY, class ARG_KEY>
inline POSITION CeSet<KEY, ARG_KEY>::GetStartPosition() const
	{ return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }

template<class KEY, class ARG_KEY>
inline UINT CeSet<KEY, ARG_KEY>::GetHashTableSize() const
	{ return m_nHashTableSize; }

template<class KEY, class ARG_KEY>
inline BOOL CeSet<KEY, ARG_KEY>::operator[](ARG_KEY key) const
   { return Lookup(key); }

/////////////////////////////////////////////////////////////////////////////
// CeSet<KEY, ARG_KEY> out-of-line functions

template<class KEY, class ARG_KEY>
CeSet<KEY, ARG_KEY>::CeSet(int nBlockSize)
{
	ASSERT(nBlockSize > 0);

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

template<class KEY, class ARG_KEY>
void CeSet<KEY, ARG_KEY>::InitHashTable(UINT nHashSize, BOOL bAllocNow)
//
// 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;
}

template<class KEY, class ARG_KEY>
void CeSet<KEY, ARG_KEY>::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)
			{
				DestructElements(&pAssoc->key, 1);
			}
		}
	}

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

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

template<class KEY, class ARG_KEY>
CeSet<KEY, ARG_KEY>::~CeSet()
{
	RemoveAll();
	ASSERT(m_nCount == 0);
}

template<class KEY, class ARG_KEY>
CeSet<KEY, ARG_KEY>::CAssoc* CeSet<KEY, ARG_KEY>::NewAssoc()
{
	if (m_pFreeList == NULL)
	{
		// add another block
		CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CeSet::CAssoc));
		// chain them into free list
		CeSet::CAssoc* pAssoc = (CeSet::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

	CeSet::CAssoc* pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow
	ConstructElements(&pAssoc->key, 1);
	return pAssoc;
}

template<class KEY, class ARG_KEY>
void CeSet<KEY, ARG_KEY>::FreeAssoc(CeSet::CAssoc* pAssoc)
{
	DestructElements(&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>
CeSet<KEY, ARG_KEY>::CAssoc* CeSet<KEY, ARG_KEY>::GetAssocAt(ARG_KEY key, UINT& nHash) const
// find association (or return NULL)
{
	nHash = HashKey(key) % m_nHashTableSize;

	if (m_pHashTable == NULL)
		return NULL;

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

template<class KEY, class ARG_KEY>
BOOL CeSet<KEY, ARG_KEY>::Lookup(ARG_KEY key) const
{
	ASSERT_VALID(this);

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

	return TRUE;
}


template<class KEY, class ARG_KEY>
void CeSet<KEY, ARG_KEY>::AddKey(ARG_KEY key)
{
	ASSERT_VALID(this);

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

		// it doesn't exist, add a new Association
		pAssoc = NewAssoc();
		pAssoc->nHashValue = nHash;
		pAssoc->key = key;

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


template<class KEY, class ARG_KEY>
BOOL CeSet<KEY, ARG_KEY>::RemoveKey(ARG_KEY key)
// remove key - return TRUE if removed
{
	ASSERT_VALID(this);

	if (m_pHashTable == NULL)
		return FALSE;  // nothing in the table

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

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

template<class KEY, class ARG_KEY>
void CeSet<KEY, ARG_KEY>::GetNextAssoc(POSITION& rNextPosition,	KEY& rKey) 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_VALID(pAssocRet);
	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;
}

#endif