diff options
Diffstat (limited to 'utils/sapi51/include/spcollec.h')
| -rw-r--r-- | utils/sapi51/include/spcollec.h | 1432 |
1 files changed, 1432 insertions, 0 deletions
diff --git a/utils/sapi51/include/spcollec.h b/utils/sapi51/include/spcollec.h new file mode 100644 index 0000000..faee643 --- /dev/null +++ b/utils/sapi51/include/spcollec.h @@ -0,0 +1,1432 @@ +/***************************************************************************** +* SPCollec.h * +*------------* +* This header file contains the SAPI5 collection class templates. These +* are a modified version of the MFC template classes without the dependencies. +*----------------------------------------------------------------------------- +* Copyright (c) Microsoft Corporation. All rights reserved. +*****************************************************************************/ +#ifndef SPCollec_h +#define SPCollec_h + +#ifndef _INC_LIMITS +#include <limits.h> +#endif + +#ifndef _INC_STRING +#include <string.h> +#endif + +#ifndef _INC_STDLIB +#include <stdlib.h> +#endif + +#ifndef _WIN32_WCE +#ifndef _INC_SEARCH +#include <search.h> +#endif +#endif + +///////////////////////////////////////////////////////////////////////////// +#define SPASSERT_VALID( a ) // This doesn't do anything right now + +typedef void* SPLISTPOS; +typedef DWORD SPLISTHANDLE; + +#define SP_BEFORE_START_POSITION ((void*)-1L) + +inline BOOL SPIsValidAddress(const void* lp, UINT nBytes, BOOL bReadWrite) +{ + // simple version using Win-32 APIs for pointer validation. + return (lp != NULL && !IsBadReadPtr(lp, nBytes) && + (!bReadWrite || !IsBadWritePtr((LPVOID)lp, nBytes))); +} + +///////////////////////////////////////////////////////////////////////////// +// global helpers (can be overridden) +template<class TYPE> +inline HRESULT SPConstructElements(TYPE* pElements, int nCount) +{ + HRESULT hr = S_OK; + SPDBG_ASSERT( nCount == 0 || + SPIsValidAddress( pElements, nCount * sizeof(TYPE), TRUE ) ); + + // default is bit-wise zero initialization + memset((void*)pElements, 0, nCount * sizeof(TYPE)); + return hr; +} + +template<class TYPE> +inline void SPDestructElements(TYPE* pElements, int nCount) +{ + SPDBG_ASSERT( ( nCount == 0 || + SPIsValidAddress( pElements, nCount * sizeof(TYPE), TRUE ) ) ); + pElements; // not used + nCount; // not used + + // default does nothing +} + +template<class TYPE> +inline HRESULT SPCopyElements(TYPE* pDest, const TYPE* pSrc, int nCount) +{ + HRESULT hr = S_OK; + SPDBG_ASSERT( ( nCount == 0 || + SPIsValidAddress( pDest, nCount * sizeof(TYPE), TRUE )) ); + SPDBG_ASSERT( ( nCount == 0 || + SPIsValidAddress( pSrc, nCount * sizeof(TYPE), FALSE )) ); + + // default is bit-wise copy + memcpy(pDest, pSrc, nCount * sizeof(TYPE)); + return hr; +} + +template<class TYPE, class ARG_TYPE> +BOOL SPCompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2) +{ + SPDBG_ASSERT( SPIsValidAddress( pElement1, sizeof(TYPE), FALSE ) ); + SPDBG_ASSERT( SPIsValidAddress( pElement2, sizeof(ARG_TYPE), FALSE ) ); + return *pElement1 == *pElement2; +} + +template<class ARG_KEY> +inline UINT SPHashKey(ARG_KEY key) +{ + // default identity hash - works for most primitive values + return ((UINT)(void*)(DWORD)key) >> 4; +} + +///////////////////////////////////////////////////////////////////////////// +// CSPPlex + +struct CSPPlex // warning variable length structure +{ + CSPPlex* pNext; + UINT nMax; + UINT nCur; + /* BYTE data[maxNum*elementSize]; */ + void* data() { return this+1; } + + static CSPPlex* PASCAL Create( CSPPlex*& pHead, UINT nMax, UINT cbElement ) + { + CSPPlex* p = (CSPPlex*) new BYTE[sizeof(CSPPlex) + nMax * cbElement]; + SPDBG_ASSERT(p); + p->nMax = nMax; + p->nCur = 0; + p->pNext = pHead; + pHead = p; // change head (adds in reverse order for simplicity) + return p; + } + + void FreeDataChain() + { + CSPPlex* p = this; + while (p != NULL) + { + BYTE* bytes = (BYTE*) p; + CSPPlex* pNext = p->pNext; + delete[] bytes; + p = pNext; + } + } +}; + + +///////////////////////////////////////////////////////////////////////////// +// CSPArray<TYPE, ARG_TYPE> + +template<class TYPE, class ARG_TYPE> +class CSPArray +{ +public: +// Construction + CSPArray(); + +// Attributes + int GetSize() const; + int GetUpperBound() const; + HRESULT SetSize(int nNewSize, int nGrowBy = -1); + +// Operations + // Clean up + void FreeExtra(); + void RemoveAll(); + + // Accessing elements + TYPE GetAt(int nIndex) const; + void SetAt(int nIndex, ARG_TYPE newElement); + TYPE& ElementAt(int nIndex); + + // Direct Access to the element data (may return NULL) + const TYPE* GetData() const; + TYPE* GetData(); + + // Potentially growing the array + HRESULT SetAtGrow(int nIndex, ARG_TYPE newElement); + int Add(ARG_TYPE newElement); + int Append(const CSPArray& src); + HRESULT Copy(const CSPArray& src); + + // overloaded operator helpers + TYPE operator[](int nIndex) const; + TYPE& operator[](int nIndex); + + // Operations that move elements around + HRESULT InsertAt(int nIndex, ARG_TYPE newElement, int nCount = 1); + void RemoveAt(int nIndex, int nCount = 1); + HRESULT InsertAt(int nStartIndex, CSPArray* pNewArray); + void Sort(int (__cdecl *compare )(const void *elem1, const void *elem2 )); + +// Implementation +protected: + TYPE* m_pData; // the actual array of data + int m_nSize; // # of elements (upperBound - 1) + int m_nMaxSize; // max allocated + int m_nGrowBy; // grow amount + +public: + ~CSPArray(); +#ifdef _DEBUG +// void Dump(CDumpContext&) const; + void AssertValid() const; +#endif +}; + +///////////////////////////////////////////////////////////////////////////// +// CSPArray<TYPE, ARG_TYPE> inline functions + +template<class TYPE, class ARG_TYPE> +inline int CSPArray<TYPE, ARG_TYPE>::GetSize() const + { return m_nSize; } +template<class TYPE, class ARG_TYPE> +inline int CSPArray<TYPE, ARG_TYPE>::GetUpperBound() const + { return m_nSize-1; } +template<class TYPE, class ARG_TYPE> +inline void CSPArray<TYPE, ARG_TYPE>::RemoveAll() + { SetSize(0, -1); } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPArray<TYPE, ARG_TYPE>::GetAt(int nIndex) const + { SPDBG_ASSERT( (nIndex >= 0 && nIndex < m_nSize) ); + return m_pData[nIndex]; } +template<class TYPE, class ARG_TYPE> +inline void CSPArray<TYPE, ARG_TYPE>::SetAt(int nIndex, ARG_TYPE newElement) + { SPDBG_ASSERT( (nIndex >= 0 && nIndex < m_nSize) ); + m_pData[nIndex] = newElement; } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPArray<TYPE, ARG_TYPE>::ElementAt(int nIndex) + { SPDBG_ASSERT( (nIndex >= 0 && nIndex < m_nSize) ); + return m_pData[nIndex]; } +template<class TYPE, class ARG_TYPE> +inline const TYPE* CSPArray<TYPE, ARG_TYPE>::GetData() const + { return (const TYPE*)m_pData; } +template<class TYPE, class ARG_TYPE> +inline TYPE* CSPArray<TYPE, ARG_TYPE>::GetData() + { return (TYPE*)m_pData; } +template<class TYPE, class ARG_TYPE> +inline int CSPArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement) + { int nIndex = m_nSize; + SetAtGrow(nIndex, newElement); + return nIndex; } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPArray<TYPE, ARG_TYPE>::operator[](int nIndex) const + { return GetAt(nIndex); } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPArray<TYPE, ARG_TYPE>::operator[](int nIndex) + { return ElementAt(nIndex); } + +///////////////////////////////////////////////////////////////////////////// +// CSPArray<TYPE, ARG_TYPE> out-of-line functions + +template<class TYPE, class ARG_TYPE> +CSPArray<TYPE, ARG_TYPE>::CSPArray() +{ + m_pData = NULL; + m_nSize = m_nMaxSize = m_nGrowBy = 0; +} + +template<class TYPE, class ARG_TYPE> +CSPArray<TYPE, ARG_TYPE>::~CSPArray() +{ + SPASSERT_VALID( this ); + + if (m_pData != NULL) + { + SPDestructElements(m_pData, m_nSize); + delete[] (BYTE*)m_pData; + } +} + +template<class TYPE, class ARG_TYPE> +HRESULT CSPArray<TYPE, ARG_TYPE>::SetSize(int nNewSize, int nGrowBy) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( nNewSize >= 0 ); + HRESULT hr = S_OK; + + if (nGrowBy != -1) + m_nGrowBy = nGrowBy; // set new size + + if (nNewSize == 0) + { + // shrink to nothing + if (m_pData != NULL) + { + SPDestructElements(m_pData, m_nSize); + delete[] (BYTE*)m_pData; + m_pData = NULL; + } + m_nSize = m_nMaxSize = 0; + } + else if (m_pData == NULL) + { + // create one with exact size +#ifdef SIZE_T_MAX + SPDBG_ASSERT( nNewSize <= SIZE_T_MAX/sizeof(TYPE) ); // no overflow +#endif + m_pData = (TYPE*) new BYTE[nNewSize * sizeof(TYPE)]; + if( m_pData ) + { + hr = SPConstructElements(m_pData, nNewSize); + if( SUCCEEDED( hr ) ) + { + m_nSize = m_nMaxSize = nNewSize; + } + else + { + delete[] (BYTE*)m_pData; + m_pData = NULL; + } + } + else + { + hr = E_OUTOFMEMORY; + } + } + else if (nNewSize <= m_nMaxSize) + { + // it fits + if (nNewSize > m_nSize) + { + // initialize the new elements + hr = SPConstructElements(&m_pData[m_nSize], nNewSize-m_nSize); + } + else if (m_nSize > nNewSize) + { + // destroy the old elements + SPDestructElements(&m_pData[nNewSize], m_nSize-nNewSize); + } + + if( SUCCEEDED( hr ) ) + { + m_nSize = nNewSize; + } + } + else + { + // otherwise, grow array + int nGrowBy = m_nGrowBy; + if (nGrowBy == 0) + { + // heuristically determe growth when nGrowBy == 0 + // (this avoids heap fragmentation in many situations) + nGrowBy = min(1024, max(4, m_nSize / 8)); + } + int nNewMax; + if (nNewSize < m_nMaxSize + nGrowBy) + nNewMax = m_nMaxSize + nGrowBy; // granularity + else + nNewMax = nNewSize; // no slush + + SPDBG_ASSERT( nNewMax >= m_nMaxSize ); // no wrap around +#ifdef SIZE_T_MAX + SPDBG_ASSERT( nNewMax <= SIZE_T_MAX/sizeof(TYPE) ); // no overflow +#endif + TYPE* pNewData = (TYPE*) new BYTE[nNewMax * sizeof(TYPE)]; + + if( pNewData ) + { + // copy new data from old + memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE)); + + // construct remaining elements + SPDBG_ASSERT( nNewSize > m_nSize ); + hr = SPConstructElements(&pNewData[m_nSize], nNewSize-m_nSize); + + // get rid of old stuff (note: no destructors called) + delete[] (BYTE*)m_pData; + m_pData = pNewData; + m_nSize = nNewSize; + m_nMaxSize = nNewMax; + } + else + { + hr = E_OUTOFMEMORY; + } + } + return hr; +} + +template<class TYPE, class ARG_TYPE> +int CSPArray<TYPE, ARG_TYPE>::Append(const CSPArray& src) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( this != &src ); // cannot append to itself + + int nOldSize = m_nSize; + HRESULT hr = SetSize(m_nSize + src.m_nSize); + if( SUCCEEDED( hr ) ) + { + hr = SPCopyElements(m_pData + nOldSize, src.m_pData, src.m_nSize); + } + return ( SUCCEEDED( hr ) )?(nOldSize):(-1); +} + +template<class TYPE, class ARG_TYPE> +HRESULT CSPArray<TYPE, ARG_TYPE>::Copy(const CSPArray& src) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( this != &src ); // cannot copy to itself + + HRESULT hr = SetSize(src.m_nSize); + if( SUCCEEDED( hr ) ) + { + hr = SPCopyElements(m_pData, src.m_pData, src.m_nSize); + } + return hr; +} + +template<class TYPE, class ARG_TYPE> +void CSPArray<TYPE, ARG_TYPE>::FreeExtra() +{ + SPASSERT_VALID( this ); + + if (m_nSize != m_nMaxSize) + { + // shrink to desired size +#ifdef SIZE_T_MAX + SPDBG_ASSERT( m_nSize <= SIZE_T_MAX/sizeof(TYPE)); // no overflow +#endif + TYPE* pNewData = NULL; + if (m_nSize != 0) + { + pNewData = (TYPE*) new BYTE[m_nSize * sizeof(TYPE)]; + SPDBG_ASSERT(pNewData); + // copy new data from old + memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE)); + } + + // get rid of old stuff (note: no destructors called) + delete[] (BYTE*)m_pData; + m_pData = pNewData; + m_nMaxSize = m_nSize; + } +} + +template<class TYPE, class ARG_TYPE> +HRESULT CSPArray<TYPE, ARG_TYPE>::SetAtGrow(int nIndex, ARG_TYPE newElement) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( nIndex >= 0 ); + HRESULT hr = S_OK; + + if (nIndex >= m_nSize) + { + hr = SetSize(nIndex+1, -1); + } + + if( SUCCEEDED( hr ) ) + { + m_pData[nIndex] = newElement; + } + return hr; +} + +template<class TYPE, class ARG_TYPE> +HRESULT CSPArray<TYPE, ARG_TYPE>::InsertAt(int nIndex, ARG_TYPE newElement, int nCount /*=1*/) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( nIndex >= 0 ); // will expand to meet need + SPDBG_ASSERT( nCount > 0 ); // zero or negative size not allowed + HRESULT hr = S_OK; + + if (nIndex >= m_nSize) + { + // adding after the end of the array + hr = SetSize(nIndex + nCount, -1); // grow so nIndex is valid + } + else + { + // inserting in the middle of the array + int nOldSize = m_nSize; + hr = SetSize(m_nSize + nCount, -1); // grow it to new size + if( SUCCEEDED( hr ) ) + { + // shift old data up to fill gap + memmove(&m_pData[nIndex+nCount], &m_pData[nIndex], + (nOldSize-nIndex) * sizeof(TYPE)); + + // re-init slots we copied from + hr = SPConstructElements(&m_pData[nIndex], nCount); + } + } + + // insert new value in the gap + if( SUCCEEDED( hr ) ) + { + SPDBG_ASSERT( nIndex + nCount <= m_nSize ); + while (nCount--) + m_pData[nIndex++] = newElement; + } + return hr; +} + +template<class TYPE, class ARG_TYPE> +void CSPArray<TYPE, ARG_TYPE>::RemoveAt(int nIndex, int nCount) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( nIndex >= 0 ); + SPDBG_ASSERT( nCount >= 0 ); + SPDBG_ASSERT( nIndex + nCount <= m_nSize ); + + // just remove a range + int nMoveCount = m_nSize - (nIndex + nCount); + SPDestructElements(&m_pData[nIndex], nCount); + if (nMoveCount) + memcpy(&m_pData[nIndex], &m_pData[nIndex + nCount], + nMoveCount * sizeof(TYPE)); + m_nSize -= nCount; +} + +template<class TYPE, class ARG_TYPE> +HRESULT CSPArray<TYPE, ARG_TYPE>::InsertAt(int nStartIndex, CSPArray* pNewArray) +{ + SPASSERT_VALID( this ); + SPASSERT_VALID( pNewArray ); + SPDBG_ASSERT( nStartIndex >= 0 ); + HRESULT hr = S_OK; + + if (pNewArray->GetSize() > 0) + { + hr = InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize()); + for (int i = 0; SUCCEEDED( hr )&& (i < pNewArray->GetSize()); i++) + { + SetAt(nStartIndex + i, pNewArray->GetAt(i)); + } + } + return hr; +} + +template<class TYPE, class ARG_TYPE> +void CSPArray<TYPE, ARG_TYPE>::Sort(int (__cdecl *compare )(const void *elem1, const void *elem2 )) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( m_pData != NULL ); + + qsort( m_pData, m_nSize, sizeof(TYPE), compare ); +} + +#ifdef _DEBUG +template<class TYPE, class ARG_TYPE> +void CSPArray<TYPE, ARG_TYPE>::AssertValid() const +{ + if (m_pData == NULL) + { + SPDBG_ASSERT( m_nSize == 0 ); + SPDBG_ASSERT( m_nMaxSize == 0 ); + } + else + { + SPDBG_ASSERT( m_nSize >= 0 ); + SPDBG_ASSERT( m_nMaxSize >= 0 ); + SPDBG_ASSERT( m_nSize <= m_nMaxSize ); + SPDBG_ASSERT( SPIsValidAddress(m_pData, m_nMaxSize * sizeof(TYPE), TRUE ) ); + } +} +#endif //_DEBUG + +///////////////////////////////////////////////////////////////////////////// +// CSPList<TYPE, ARG_TYPE> + +template<class TYPE, class ARG_TYPE> +class CSPList +{ +protected: + struct CNode + { + CNode* pNext; + CNode* pPrev; + TYPE data; + }; +public: + +// Construction + CSPList(int nBlockSize = 10); + +// Attributes (head and tail) + // count of elements + int GetCount() const; + BOOL IsEmpty() const; + + // peek at head or tail + TYPE& GetHead(); + TYPE GetHead() const; + TYPE& GetTail(); + TYPE GetTail() const; + +// Operations + // get head or tail (and remove it) - don't call on empty list ! + TYPE RemoveHead(); + TYPE RemoveTail(); + + // add before head or after tail + SPLISTPOS AddHead(ARG_TYPE newElement); + SPLISTPOS AddTail(ARG_TYPE newElement); + + // add another list of elements before head or after tail + void AddHead(CSPList* pNewList); + void AddTail(CSPList* pNewList); + + // remove all elements + void RemoveAll(); + + // iteration + SPLISTPOS GetHeadPosition() const; + SPLISTPOS GetTailPosition() const; + TYPE& GetNext(SPLISTPOS& rPosition); // return *Position++ + TYPE GetNext(SPLISTPOS& rPosition) const; // return *Position++ + TYPE& GetPrev(SPLISTPOS& rPosition); // return *Position-- + TYPE GetPrev(SPLISTPOS& rPosition) const; // return *Position-- + + // getting/modifying an element at a given position + TYPE& GetAt(SPLISTPOS position); + TYPE GetAt(SPLISTPOS position) const; + void SetAt(SPLISTPOS pos, ARG_TYPE newElement); + void RemoveAt(SPLISTPOS position); + + // inserting before or after a given position + SPLISTPOS InsertBefore(SPLISTPOS position, ARG_TYPE newElement); + SPLISTPOS InsertAfter(SPLISTPOS position, ARG_TYPE newElement); + + // helper functions (note: O(n) speed) + SPLISTPOS Find(ARG_TYPE searchValue, SPLISTPOS startAfter = NULL) const; + // defaults to starting at the HEAD, return NULL if not found + SPLISTPOS FindIndex(int nIndex) const; + // get the 'nIndex'th element (may return NULL) + +// Implementation +protected: + CNode* m_pNodeHead; + CNode* m_pNodeTail; + int m_nCount; + CNode* m_pNodeFree; + struct CSPPlex* m_pBlocks; + int m_nBlockSize; + + CNode* NewNode(CNode*, CNode*); + void FreeNode(CNode*); + +public: + ~CSPList(); +#ifdef _DEBUG + void AssertValid() const; +#endif +}; + +///////////////////////////////////////////////////////////////////////////// +// CSPList<TYPE, ARG_TYPE> inline functions + +template<class TYPE, class ARG_TYPE> +inline int CSPList<TYPE, ARG_TYPE>::GetCount() const + { return m_nCount; } +template<class TYPE, class ARG_TYPE> +inline BOOL CSPList<TYPE, ARG_TYPE>::IsEmpty() const + { return m_nCount == 0; } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPList<TYPE, ARG_TYPE>::GetHead() + { SPDBG_ASSERT( m_pNodeHead != NULL ); + return m_pNodeHead->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPList<TYPE, ARG_TYPE>::GetHead() const + { SPDBG_ASSERT( m_pNodeHead != NULL ); + return m_pNodeHead->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPList<TYPE, ARG_TYPE>::GetTail() + { SPDBG_ASSERT( m_pNodeTail != NULL ); + return m_pNodeTail->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPList<TYPE, ARG_TYPE>::GetTail() const + { SPDBG_ASSERT( m_pNodeTail != NULL ); + return m_pNodeTail->data; } +template<class TYPE, class ARG_TYPE> +inline SPLISTPOS CSPList<TYPE, ARG_TYPE>::GetHeadPosition() const + { return (SPLISTPOS) m_pNodeHead; } +template<class TYPE, class ARG_TYPE> +inline SPLISTPOS CSPList<TYPE, ARG_TYPE>::GetTailPosition() const + { return (SPLISTPOS) m_pNodeTail; } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPList<TYPE, ARG_TYPE>::GetNext(SPLISTPOS& rPosition) // return *Position++ + { CNode* pNode = (CNode*) rPosition; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + rPosition = (SPLISTPOS) pNode->pNext; + return pNode->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPList<TYPE, ARG_TYPE>::GetNext(SPLISTPOS& rPosition) const // return *Position++ + { CNode* pNode = (CNode*) rPosition; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + rPosition = (SPLISTPOS) pNode->pNext; + return pNode->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPList<TYPE, ARG_TYPE>::GetPrev(SPLISTPOS& rPosition) // return *Position-- + { CNode* pNode = (CNode*) rPosition; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + rPosition = (SPLISTPOS) pNode->pPrev; + return pNode->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPList<TYPE, ARG_TYPE>::GetPrev(SPLISTPOS& rPosition) const // return *Position-- + { CNode* pNode = (CNode*) rPosition; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + rPosition = (SPLISTPOS) pNode->pPrev; + return pNode->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE& CSPList<TYPE, ARG_TYPE>::GetAt(SPLISTPOS position) + { CNode* pNode = (CNode*) position; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + return pNode->data; } +template<class TYPE, class ARG_TYPE> +inline TYPE CSPList<TYPE, ARG_TYPE>::GetAt(SPLISTPOS position) const + { CNode* pNode = (CNode*) position; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + return pNode->data; } +template<class TYPE, class ARG_TYPE> +inline void CSPList<TYPE, ARG_TYPE>::SetAt(SPLISTPOS pos, ARG_TYPE newElement) + { CNode* pNode = (CNode*) pos; + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + pNode->data = newElement; } + +///////////////////////////////////////////////////////////////////////////// +// CSPList<TYPE, ARG_TYPE> out-of-line functions + +template<class TYPE, class ARG_TYPE> +CSPList<TYPE, ARG_TYPE>::CSPList( int nBlockSize ) +{ + SPDBG_ASSERT( nBlockSize > 0 ); + + m_nCount = 0; + m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL; + m_pBlocks = NULL; + m_nBlockSize = nBlockSize; +} + +template<class TYPE, class ARG_TYPE> +void CSPList<TYPE, ARG_TYPE>::RemoveAll() +{ + SPASSERT_VALID( this ); + + // destroy elements + CNode* pNode; + for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext) + SPDestructElements(&pNode->data, 1); + + m_nCount = 0; + m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL; + m_pBlocks->FreeDataChain(); + m_pBlocks = NULL; +} + +template<class TYPE, class ARG_TYPE> +CSPList<TYPE, ARG_TYPE>::~CSPList() +{ + RemoveAll(); + SPDBG_ASSERT( m_nCount == 0 ); +} + +///////////////////////////////////////////////////////////////////////////// +// Node helpers +// +// Implementation note: CNode's are stored in CSPPlex blocks and +// chained together. Free blocks are maintained in a singly linked list +// using the 'pNext' member of CNode with 'm_pNodeFree' as the head. +// Used blocks are maintained in a doubly linked list using both 'pNext' +// and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail' +// as the head/tail. +// +// We never free a CSPPlex block unless the List is destroyed or RemoveAll() +// is used - so the total number of CSPPlex blocks may grow large depending +// on the maximum past size of the list. +// + +template<class TYPE, class ARG_TYPE> +CSPList<TYPE, ARG_TYPE>::CNode* +CSPList<TYPE, ARG_TYPE>::NewNode(CSPList::CNode* pPrev, CSPList::CNode* pNext) +{ + if (m_pNodeFree == NULL) + { + // add another block + CSPPlex* pNewBlock = CSPPlex::Create(m_pBlocks, m_nBlockSize,sizeof(CNode)); + + // chain them into free list + CNode* pNode = (CNode*) pNewBlock->data(); + // free in reverse order to make it easier to debug + pNode += m_nBlockSize - 1; + for (int i = m_nBlockSize-1; i >= 0; i--, pNode--) + { + pNode->pNext = m_pNodeFree; + m_pNodeFree = pNode; + } + } + + CSPList::CNode* pNode = m_pNodeFree; + if( pNode ) + { + if( SUCCEEDED( SPConstructElements(&pNode->data, 1) ) ) + { + m_pNodeFree = m_pNodeFree->pNext; + pNode->pPrev = pPrev; + pNode->pNext = pNext; + m_nCount++; + SPDBG_ASSERT( m_nCount > 0 ); // make sure we don't overflow + } + } + return pNode; +} + +template<class TYPE, class ARG_TYPE> +void CSPList<TYPE, ARG_TYPE>::FreeNode(CSPList::CNode* pNode) +{ + SPDestructElements(&pNode->data, 1); + pNode->pNext = m_pNodeFree; + m_pNodeFree = pNode; + m_nCount--; + SPDBG_ASSERT( m_nCount >= 0 ); // make sure we don't underflow +} + +template<class TYPE, class ARG_TYPE> +SPLISTPOS CSPList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement) +{ + SPASSERT_VALID( this ); + + CNode* pNewNode = NewNode(NULL, m_pNodeHead); + if( pNewNode ) + { + pNewNode->data = newElement; + if (m_pNodeHead != NULL) + m_pNodeHead->pPrev = pNewNode; + else + m_pNodeTail = pNewNode; + m_pNodeHead = pNewNode; + } + return (SPLISTPOS) pNewNode; +} + +template<class TYPE, class ARG_TYPE> +SPLISTPOS CSPList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement) +{ + SPASSERT_VALID( this ); + + CNode* pNewNode = NewNode(m_pNodeTail, NULL); + if( pNewNode ) + { + pNewNode->data = newElement; + if (m_pNodeTail != NULL) + m_pNodeTail->pNext = pNewNode; + else + m_pNodeHead = pNewNode; + m_pNodeTail = pNewNode; + } + return (SPLISTPOS) pNewNode; +} + +template<class TYPE, class ARG_TYPE> +void CSPList<TYPE, ARG_TYPE>::AddHead(CSPList* pNewList) +{ + SPASSERT_VALID( this ); + SPASSERT_VALID( pNewList ); + + // add a list of same elements to head (maintain order) + SPLISTPOS pos = pNewList->GetTailPosition(); + while (pos != NULL) + AddHead(pNewList->GetPrev(pos)); +} + +template<class TYPE, class ARG_TYPE> +void CSPList<TYPE, ARG_TYPE>::AddTail(CSPList* pNewList) +{ + SPASSERT_VALID( this ); + SPASSERT_VALID( pNewList ); + + // add a list of same elements + SPLISTPOS pos = pNewList->GetHeadPosition(); + while (pos != NULL) + AddTail(pNewList->GetNext(pos)); +} + +template<class TYPE, class ARG_TYPE> +TYPE CSPList<TYPE, ARG_TYPE>::RemoveHead() +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( m_pNodeHead != NULL ); // don't call on empty list !!! + SPDBG_ASSERT( SPIsValidAddress(m_pNodeHead, sizeof(CNode), TRUE ) ); + + CNode* pOldNode = m_pNodeHead; + TYPE returnValue = pOldNode->data; + + m_pNodeHead = pOldNode->pNext; + if (m_pNodeHead != NULL) + m_pNodeHead->pPrev = NULL; + else + m_pNodeTail = NULL; + FreeNode(pOldNode); + return returnValue; +} + +template<class TYPE, class ARG_TYPE> +TYPE CSPList<TYPE, ARG_TYPE>::RemoveTail() +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( m_pNodeTail != NULL ); // don't call on empty list !!! + SPDBG_ASSERT( SPIsValidAddress(m_pNodeTail, sizeof(CNode), TRUE ) ); + + CNode* pOldNode = m_pNodeTail; + TYPE returnValue = pOldNode->data; + + m_pNodeTail = pOldNode->pPrev; + if (m_pNodeTail != NULL) + m_pNodeTail->pNext = NULL; + else + m_pNodeHead = NULL; + FreeNode(pOldNode); + return returnValue; +} + +template<class TYPE, class ARG_TYPE> +SPLISTPOS CSPList<TYPE, ARG_TYPE>::InsertBefore(SPLISTPOS position, ARG_TYPE newElement) +{ + SPASSERT_VALID( this ); + + if (position == NULL) + return AddHead(newElement); // insert before nothing -> head of the list + + // Insert it before position + CNode* pOldNode = (CNode*) position; + CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode); + if( pNewNode ) + { + pNewNode->data = newElement; + + if (pOldNode->pPrev != NULL) + { + SPDBG_ASSERT( SPIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) ); + pOldNode->pPrev->pNext = pNewNode; + } + else + { + SPDBG_ASSERT( pOldNode == m_pNodeHead ); + m_pNodeHead = pNewNode; + } + pOldNode->pPrev = pNewNode; + } + return (SPLISTPOS) pNewNode; +} + +template<class TYPE, class ARG_TYPE> +SPLISTPOS CSPList<TYPE, ARG_TYPE>::InsertAfter(SPLISTPOS position, ARG_TYPE newElement) +{ + SPASSERT_VALID( this ); + + if (position == NULL) + return AddTail(newElement); // insert after nothing -> tail of the list + + // Insert it before position + CNode* pOldNode = (CNode*) position; + SPDBG_ASSERT( SPIsValidAddress(pOldNode, sizeof(CNode), TRUE )); + CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext); + if( pNewNode ) + { + pNewNode->data = newElement; + + if (pOldNode->pNext != NULL) + { + SPDBG_ASSERT( SPIsValidAddress(pOldNode->pNext, sizeof(CNode), TRUE )); + pOldNode->pNext->pPrev = pNewNode; + } + else + { + SPDBG_ASSERT( pOldNode == m_pNodeTail ); + m_pNodeTail = pNewNode; + } + pOldNode->pNext = pNewNode; + } + return (SPLISTPOS) pNewNode; +} + +template<class TYPE, class ARG_TYPE> +void CSPList<TYPE, ARG_TYPE>::RemoveAt(SPLISTPOS position) +{ + SPASSERT_VALID( this ); + + CNode* pOldNode = (CNode*) position; + SPDBG_ASSERT( SPIsValidAddress(pOldNode, sizeof(CNode), TRUE ) ); + + // remove pOldNode from list + if (pOldNode == m_pNodeHead) + { + m_pNodeHead = pOldNode->pNext; + } + else + { + SPDBG_ASSERT( SPIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) ); + pOldNode->pPrev->pNext = pOldNode->pNext; + } + if (pOldNode == m_pNodeTail) + { + m_pNodeTail = pOldNode->pPrev; + } + else + { + SPDBG_ASSERT( SPIsValidAddress(pOldNode->pNext, sizeof(CNode), TRUE ) ); + pOldNode->pNext->pPrev = pOldNode->pPrev; + } + FreeNode(pOldNode); +} + +template<class TYPE, class ARG_TYPE> +SPLISTPOS CSPList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( nIndex >= 0 ); + + if (nIndex >= m_nCount) + return NULL; // went too far + + CNode* pNode = m_pNodeHead; + while (nIndex--) + { + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE )); + pNode = pNode->pNext; + } + return (SPLISTPOS) pNode; +} + +template<class TYPE, class ARG_TYPE> +SPLISTPOS CSPList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, SPLISTPOS startAfter) const +{ + SPASSERT_VALID( this ); + + CNode* pNode = (CNode*) startAfter; + if (pNode == NULL) + { + pNode = m_pNodeHead; // start at head + } + else + { + SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) ); + pNode = pNode->pNext; // start after the one specified + } + + for (; pNode != NULL; pNode = pNode->pNext) + if (SPCompareElements(&pNode->data, &searchValue)) + return (SPLISTPOS)pNode; + return NULL; +} + +#ifdef _DEBUG +template<class TYPE, class ARG_TYPE> +void CSPList<TYPE, ARG_TYPE>::AssertValid() const +{ + if (m_nCount == 0) + { + // empty list + SPDBG_ASSERT( m_pNodeHead == NULL ); + SPDBG_ASSERT( m_pNodeTail == NULL ); + } + else + { + // non-empty list + SPDBG_ASSERT( SPIsValidAddress(m_pNodeHead, sizeof(CNode), TRUE )); + SPDBG_ASSERT( SPIsValidAddress(m_pNodeTail, sizeof(CNode), TRUE )); + } +} +#endif //_DEBUG + +///////////////////////////////////////////////////////////////////////////// +// CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE> + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +class CSPMap +{ +protected: + // Association + struct CAssoc + { + CAssoc* pNext; + UINT nHashValue; // needed for efficient iteration + KEY key; + VALUE value; + }; +public: +// Construction + CSPMap( int nBlockSize = 10 ); + +// Attributes + // number of elements + int GetCount() const; + BOOL IsEmpty() const; + + // Lookup + BOOL 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 + BOOL RemoveKey(ARG_KEY key); + void RemoveAll(); + + // iterating all (key, value) pairs + SPLISTPOS GetStartPosition() const; + void GetNextAssoc(SPLISTPOS& rNextPosition, KEY& rKey, VALUE& rValue) const; + + // advanced features for derived classes + UINT GetHashTableSize() const; + HRESULT InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE); + +// Implementation +protected: + CAssoc** m_pHashTable; + UINT m_nHashTableSize; + int m_nCount; + CAssoc* m_pFreeList; + struct CSPPlex* m_pBlocks; + int m_nBlockSize; + + CAssoc* NewAssoc(); + void FreeAssoc(CAssoc*); + CAssoc* GetAssocAt(ARG_KEY, UINT&) const; + +public: + ~CSPMap(); +#ifdef _DEBUG +// void Dump(CDumpContext&) const; + void AssertValid() const; +#endif +}; + +///////////////////////////////////////////////////////////////////////////// +// CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE> inline functions + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +inline int CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const + { return m_nCount; } +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +inline BOOL CSPMap<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 CSPMap<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 SPLISTPOS CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const + { return (m_nCount == 0) ? NULL : SP_BEFORE_START_POSITION; } +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +inline UINT CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetHashTableSize() const + { return m_nHashTableSize; } + +///////////////////////////////////////////////////////////////////////////// +// CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE> out-of-line functions + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CSPMap( int nBlockSize ) +{ + SPDBG_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, class VALUE, class ARG_VALUE> +HRESULT CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::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) +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( m_nCount == 0 ); + SPDBG_ASSERT( nHashSize > 0 ); + HRESULT hr = S_OK; + + if (m_pHashTable != NULL) + { + // free hash table + delete[] m_pHashTable; + m_pHashTable = NULL; + } + + if (bAllocNow) + { + m_pHashTable = new CAssoc* [nHashSize]; + if( m_pHashTable ) + { + memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize); + } + else + { + hr = E_OUTOFMEMORY; + } + } + + m_nHashTableSize = ( SUCCEEDED( hr ) )?(nHashSize):(0); + return hr; +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +void CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll() +{ + SPASSERT_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) + { + SPDestructElements(&pAssoc->value, 1); + SPDestructElements(&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, class VALUE, class ARG_VALUE> +CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CSPMap() +{ + RemoveAll(); + SPDBG_ASSERT( m_nCount == 0 ); +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc* +CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc() +{ + if (m_pFreeList == NULL) + { + // add another block + CSPPlex* newBlock = CSPPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CSPMap::CAssoc)); + + if( newBlock ) + { + // chain them into free list + CSPMap::CAssoc* pAssoc = (CSPMap::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; + } + } + } + + CSPMap::CAssoc* pAssoc = m_pFreeList; + if( pAssoc ) + { + if( SUCCEEDED( SPConstructElements(&pAssoc->key, 1 ) ) ) + { + if( SUCCEEDED( SPConstructElements(&pAssoc->value, 1 ) ) ) + { + m_pFreeList = m_pFreeList->pNext; + m_nCount++; + SPDBG_ASSERT( m_nCount > 0 ); // make sure we don't overflow + } + else + { + SPDestructElements( &pAssoc->key, 1 ); + } + } + else + { + pAssoc = NULL; + } + } + return pAssoc; +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +void CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CSPMap::CAssoc* pAssoc) +{ + SPDestructElements(&pAssoc->value, 1); + SPDestructElements(&pAssoc->key, 1); + pAssoc->pNext = m_pFreeList; + m_pFreeList = pAssoc; + m_nCount--; + SPDBG_ASSERT( m_nCount >= 0 ); // make sure we don't underflow +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc* +CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const +// find association (or return NULL) +{ + nHash = SPHashKey(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 (SPCompareElements(&pAssoc->key, &key)) + return pAssoc; + } + return NULL; +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +BOOL CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const +{ + SPASSERT_VALID( this ); + + UINT nHash; + CAssoc* pAssoc = GetAssocAt(key, nHash); + if (pAssoc == NULL) + return FALSE; // not in map + + rValue = pAssoc->value; + return TRUE; +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +VALUE& CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key) +{ + SPASSERT_VALID( this ); + HRESULT hr = S_OK; + static const CAssoc ErrAssoc = 0; + + UINT nHash; + CAssoc* pAssoc; + if ((pAssoc = GetAssocAt(key, nHash)) == NULL) + { + if( m_pHashTable == NULL ) + { + hr = InitHashTable(m_nHashTableSize); + } + + if( SUCCEEDED( hr ) ) + { + // it doesn't exist, add a new Association + pAssoc = NewAssoc(); + if( pAssoc ) + { + 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; + } + else + { + pAssoc = &ErrAssoc; + } + } + } + return pAssoc->value; // return new reference +} + +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +BOOL CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key) +// remove key - return TRUE if removed +{ + SPASSERT_VALID( this ); + + if (m_pHashTable == NULL) + return FALSE; // nothing in the table + + CAssoc** ppAssocPrev; + ppAssocPrev = &m_pHashTable[SPHashKey(key) % m_nHashTableSize]; + + CAssoc* pAssoc; + for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) + { + if (SPCompareElements(&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, class VALUE, class ARG_VALUE> +void CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(SPLISTPOS& rNextPosition, + KEY& rKey, VALUE& rValue) const +{ + SPASSERT_VALID( this ); + SPDBG_ASSERT( m_pHashTable != NULL ); // never call on empty map + + CAssoc* pAssocRet = (CAssoc*)rNextPosition; + SPDBG_ASSERT( pAssocRet != NULL ); + + if (pAssocRet == (CAssoc*) SP_BEFORE_START_POSITION) + { + // find the first association + for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++) + if ((pAssocRet = m_pHashTable[nBucket]) != NULL) + break; + SPDBG_ASSERT( pAssocRet != NULL ); // must find something + } + + // find next association + SPDBG_ASSERT( SPIsValidAddress(pAssocRet, sizeof(CAssoc), TRUE )); + 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 = (SPLISTPOS) pAssocNext; + + // fill in return data + rKey = pAssocRet->key; + rValue = pAssocRet->value; +} + +#ifdef _DEBUG +template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> +void CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const +{ + SPDBG_ASSERT( m_nHashTableSize > 0 ); + SPDBG_ASSERT( (m_nCount == 0 || m_pHashTable != NULL) ); + // non-empty map should have hash table +} +#endif //_DEBUG + +#endif //--- This must be the last line in the file |