diff options
Diffstat (limited to 'sample/d3d11/Effects11/Inc/d3dxGlobal.h')
| -rw-r--r-- | sample/d3d11/Effects11/Inc/d3dxGlobal.h | 1337 |
1 files changed, 0 insertions, 1337 deletions
diff --git a/sample/d3d11/Effects11/Inc/d3dxGlobal.h b/sample/d3d11/Effects11/Inc/d3dxGlobal.h deleted file mode 100644 index 3b5cdf8..0000000 --- a/sample/d3d11/Effects11/Inc/d3dxGlobal.h +++ /dev/null @@ -1,1337 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// Copyright (C) Microsoft Corporation. All Rights Reserved. -// -// File: D3DXGlobal.h -// Content: D3DX11 Effects helper defines and data structures -// -////////////////////////////////////////////////////////////////////////////// - -#pragma once - -#pragma warning(disable : 4100 4127 4189 4201 4245 4389 4505 4701 4706) - -namespace D3DX11Debug -{ -} - -using namespace D3DX11Debug; - -#include "d3dx11dbg.h" - -#define SAFE_RELEASE(p) { if (p) { (p)->Release(); (p) = NULL; } } -#define SAFE_ADDREF(p) { if (p) { (p)->AddRef(); } } - -#define SAFE_DELETE_ARRAY(p) { delete [](p); p = NULL; } -#define SAFE_DELETE(p) { delete (p); p = NULL; } - -#if FXDEBUG -#define __BREAK_ON_FAIL { __debugbreak(); } -#else -#define __BREAK_ON_FAIL -#endif - -#define VA(x, action) { hr = (x); if (FAILED(hr)) { action; __BREAK_ON_FAIL; return hr; } } -#define VNA(x,action) { if (!(x)) { action; __BREAK_ON_FAIL; hr = E_OUTOFMEMORY; goto lExit; } } -#define VBA(x,action) { if (!(x)) { action; __BREAK_ON_FAIL; hr = E_FAIL; goto lExit; } } -#define VHA(x,action) { hr = (x); if (FAILED(hr)) { action; __BREAK_ON_FAIL; goto lExit; } } - -#define V(x) { VA (x, 0) } -#define VN(x) { VNA(x, 0) } -#define VB(x) { VBA(x, 0) } -#define VH(x) { VHA(x, 0) } - -#define VBD(x,str) { VBA(x, DPF(1,str)) } -#define VHD(x,str) { VHA(x, DPF(1,str)) } - -#define VEASSERT(x) { hr = (x); if (FAILED(hr)) { __BREAK_ON_FAIL; D3DXASSERT(!#x); goto lExit; } } -#define VNASSERT(x) { if (!(x)) { __BREAK_ON_FAIL; D3DXASSERT(!#x); hr = E_OUTOFMEMORY; goto lExit; } } - -#define ANALYSIS_ASSUME(x) { D3DXASSERT(x); __analysis_assume(x); __assume(x); } - -#define D3DX11FLTASSIGN(a,b) { *reinterpret_cast< UINT32* >(&(a)) = *reinterpret_cast< UINT32* >(&(b)); } - -// Preferred data alignment -- must be a power of 2! -static const UINT c_DataAlignment = sizeof(UINT_PTR); - -D3DX11INLINE UINT AlignToPowerOf2(UINT Value, UINT Alignment) -{ - D3DXASSERT((Alignment & (Alignment - 1)) == 0); - // to align to 2^N, add 2^N - 1 and AND with all but lowest N bits set - ANALYSIS_ASSUME(Alignment > 0 && Value < MAXDWORD - Alignment); - return (Value + Alignment - 1) & (~(Alignment - 1)); -} - -D3DX11INLINE void * AlignToPowerOf2(void *pValue, UINT_PTR Alignment) -{ - D3DXASSERT((Alignment & (Alignment - 1)) == 0); - // to align to 2^N, add 2^N - 1 and AND with all but lowest N bits set - return (void *)(((UINT_PTR)pValue + Alignment - 1) & (~((UINT_PTR)Alignment - 1))); -} - - -// Fast memcpy -D3DX11INLINE void dwordMemcpy( __out_bcount(uByteCount) void * __restrict pDest, __in_bcount(uByteCount) CONST void * __restrict pSource, UINT uByteCount) -{ - UINT i; - D3DXASSERT(uByteCount % 4 == 0); -#ifdef _AMD64_ - const UINT qwordCount = uByteCount >> 3; - - __int64* src64 = (__int64*) pSource; - __int64* dst64 = (__int64*) pDest; - - for (i=0; i<(qwordCount & 0x3); i++) - { - *(dst64) = *(src64); - dst64++; - src64++; - } - - for (; i<qwordCount; i+= 4) - { - *(dst64 ) = *(src64 ); - *(dst64 + 1 ) = *(src64 + 1 ); - *(dst64 + 2 ) = *(src64 + 2 ); - *(dst64 + 3 ) = *(src64 + 3 ); - dst64 += 4; - src64 += 4; - } - - ANALYSIS_ASSUME( dst64 - static_cast< __int64* >(pDest) <= uByteCount - 4 ); - ANALYSIS_ASSUME( src64 - static_cast< const __int64* >(pSource) <= uByteCount - 4 ); - if( uByteCount & 0x4 ) - { - *((UINT*)dst64) = *((UINT*)src64); - } -#else - const UINT dwordCount = uByteCount >> 2; - - for (i=0; i<(dwordCount & 0x3); i++) - { -#pragma prefast(suppress: __WARNING_UNRELATED_LOOP_TERMINATION, "(dwordCount & 03) < dwordCount") - ((UINT*)pDest)[i ] = ((UINT*)pSource)[i ]; - } - for (; i<dwordCount; i+= 4) - { - ((UINT*)pDest)[i ] = ((UINT*)pSource)[i ]; - ((UINT*)pDest)[i+1] = ((UINT*)pSource)[i+1]; - ((UINT*)pDest)[i+2] = ((UINT*)pSource)[i+2]; - ((UINT*)pDest)[i+3] = ((UINT*)pSource)[i+3]; - } -#endif -} - - -namespace D3DX11Core -{ - -////////////////////////////////////////////////////////////////////////// -// CMemoryStream - A class to simplify reading binary data -////////////////////////////////////////////////////////////////////////// -class CMemoryStream -{ - BYTE *m_pData; - SIZE_T m_cbData; - SIZE_T m_readPtr; - -public: - HRESULT SetData(const void *pData, SIZE_T size); - - HRESULT Read(UINT *pUint); - HRESULT Read(void **ppData, SIZE_T size); - HRESULT Read(LPCSTR *ppString); - - HRESULT ReadAtOffset(SIZE_T offset, SIZE_T size, void **ppData); - HRESULT ReadAtOffset(SIZE_T offset, LPCSTR *ppString); - - SIZE_T GetPosition(); - HRESULT Seek(SIZE_T offset); - - CMemoryStream(); - ~CMemoryStream(); -}; - -} - -#if FXDEBUG - -namespace D3DX11Debug -{ - -// This variable indicates how many ticks to go before rolling over -// all of the timer variables in the FX system. -// It is read from the system registry in debug builds; in retail the high bit is simply tested. - -_declspec(selectany) unsigned int g_TimerRolloverCount = 0x80000000; -} - -#endif // FXDEBUG - - -////////////////////////////////////////////////////////////////////////// -// CEffectVector - A vector implementation -////////////////////////////////////////////////////////////////////////// - -template<class T> class CEffectVector -{ -protected: -#if _DEBUG - T *m_pCastData; // makes debugging easier to have a casted version of the data -#endif // _DEBUG - - BYTE *m_pData; - UINT m_MaxSize; - UINT m_CurSize; - - HRESULT Grow() - { - return Reserve(m_CurSize + 1); - } - - HRESULT Reserve(UINT DesiredSize) - { - if (DesiredSize > m_MaxSize) - { - BYTE *pNewData; - UINT newSize = max(m_MaxSize * 2, DesiredSize); - - if (newSize < 16) - newSize = 16; - - if ((newSize < m_MaxSize) || (newSize < m_CurSize) || (newSize >= UINT_MAX / sizeof(T))) - { - m_hLastError = E_OUTOFMEMORY; - return m_hLastError; - } - - pNewData = NEW BYTE[newSize * sizeof(T)]; - if (pNewData == NULL) - { - m_hLastError = E_OUTOFMEMORY; - return m_hLastError; - } - - if (m_pData) - { - memcpy(pNewData, m_pData, m_CurSize * sizeof(T)); - delete []m_pData; - } - - m_pData = pNewData; - m_MaxSize = newSize; - } -#if _DEBUG - m_pCastData = (T*) m_pData; -#endif // _DEBUG - return S_OK; - } - -public: - HRESULT m_hLastError; - - CEffectVector<T>() - { - m_hLastError = S_OK; -#if _DEBUG - m_pCastData = NULL; -#endif // _DEBUG - m_pData = NULL; - m_CurSize = m_MaxSize = 0; - } - - ~CEffectVector<T>() - { - Clear(); - } - - // cleanly swaps two vectors -- useful for when you want - // to reallocate a vector and copy data over, then swap them back - void SwapVector(CEffectVector<T> &vOther) - { - BYTE tempData[sizeof(*this)]; - - memcpy(tempData, this, sizeof(*this)); - memcpy(this, &vOther, sizeof(*this)); - memcpy(&vOther, tempData, sizeof(*this)); - } - - HRESULT CopyFrom(CEffectVector<T> &vOther) - { - HRESULT hr = S_OK; - Clear(); - VN( m_pData = NEW BYTE[vOther.m_MaxSize * sizeof(T)] ); - - m_CurSize = vOther.m_CurSize; - m_MaxSize = vOther.m_MaxSize; - m_hLastError = vOther.m_hLastError; - - UINT i; - for (i = 0; i < m_CurSize; ++ i) - { - ((T*)m_pData)[i] = ((T*)vOther.m_pData)[i]; - } - -lExit: - -#if _DEBUG - m_pCastData = (T*) m_pData; -#endif // _DEBUG - - return hr; - } - - void Clear() - { - Empty(); - SAFE_DELETE_ARRAY(m_pData); - m_MaxSize = 0; -#if _DEBUG - m_pCastData = NULL; -#endif // _DEBUG - } - - void ClearWithoutDestructor() - { - m_CurSize = 0; - m_hLastError = S_OK; - SAFE_DELETE_ARRAY(m_pData); - m_MaxSize = 0; - -#if _DEBUG - m_pCastData = NULL; -#endif // _DEBUG - } - - void Empty() - { - UINT i; - - // manually invoke destructor on all elements - for (i = 0; i < m_CurSize; ++ i) - { - ((T*)m_pData + i)->~T(); - } - m_CurSize = 0; - m_hLastError = S_OK; - } - - T* Add() - { - if (FAILED(Grow())) - return NULL; - - // placement new - return new((T*)m_pData + (m_CurSize ++)) T; - } - - T* AddRange(UINT count) - { - if (m_CurSize + count < m_CurSize) - { - m_hLastError = E_OUTOFMEMORY; - return NULL; - } - - if (FAILED(Reserve(m_CurSize + count))) - return NULL; - - T *pData = (T*)m_pData + m_CurSize; - UINT i; - for (i = 0; i < count; ++ i) - { - new(pData + i) T; - } - m_CurSize += count; - return pData; - } - - HRESULT Add(const T& var) - { - if (FAILED(Grow())) - return m_hLastError; - - memcpy((T*)m_pData + m_CurSize, &var, sizeof(T)); - m_CurSize++; - - return S_OK; - } - - HRESULT AddRange(const T *pVar, UINT count) - { - if (m_CurSize + count < m_CurSize) - { - m_hLastError = E_OUTOFMEMORY; - return m_hLastError; - } - - if (FAILED(Reserve(m_CurSize + count))) - return m_hLastError; - - memcpy((T*)m_pData + m_CurSize, pVar, count * sizeof(T)); - m_CurSize += count; - - return S_OK; - } - - HRESULT Insert(const T& var, UINT index) - { - D3DXASSERT(index < m_CurSize); - - if (FAILED(Grow())) - return m_hLastError; - - memmove((T*)m_pData + index + 1, (T*)m_pData + index, (m_CurSize - index) * sizeof(T)); - memcpy((T*)m_pData + index, &var, sizeof(T)); - m_CurSize++; - - return S_OK; - } - - HRESULT InsertRange(const T *pVar, UINT index, UINT count) - { - D3DXASSERT(index < m_CurSize); - - if (m_CurSize + count < m_CurSize) - { - m_hLastError = E_OUTOFMEMORY; - return m_hLastError; - } - - if (FAILED(Reserve(m_CurSize + count))) - return m_hLastError; - - memmove((T*)m_pData + index + count, (T*)m_pData + index, (m_CurSize - index) * sizeof(T)); - memcpy((T*)m_pData + index, pVar, count * sizeof(T)); - m_CurSize += count; - - return S_OK; - } - - inline T& operator[](UINT index) - { - D3DXASSERT(index < m_CurSize); - return ((T*)m_pData)[index]; - } - - // Deletes element at index and shifts all other values down - void Delete(UINT index) - { - D3DXASSERT(index < m_CurSize); - - -- m_CurSize; - memmove((T*)m_pData + index, (T*)m_pData + index + 1, (m_CurSize - index) * sizeof(T)); - } - - // Deletes element at index and moves the last element into its place - void QuickDelete(UINT index) - { - D3DXASSERT(index < m_CurSize); - - -- m_CurSize; - memcpy((T*)m_pData + index, (T*)m_pData + m_CurSize, sizeof(T)); - } - - inline UINT GetSize() const - { - return m_CurSize; - } - - inline T* GetData() const - { - return (T*)m_pData; - } - - UINT FindIndexOf(void *pEntry) const - { - UINT i; - - for (i = 0; i < m_CurSize; ++ i) - { - if (((T*)m_pData + i) == pEntry) - return i; - } - - return -1; - } - - void Sort(int (__cdecl *pfnCompare)(const void *pElem1, const void *pElem2)) - { - qsort(m_pData, m_CurSize, sizeof(T), pfnCompare); - } -}; - -////////////////////////////////////////////////////////////////////////// -// CEffectVectorOwner - implements a vector of ptrs to objects. The vector owns the objects. -////////////////////////////////////////////////////////////////////////// -template<class T> class CEffectVectorOwner : public CEffectVector<T*> -{ -public: - ~CEffectVectorOwner<T>() - { - Clear(); - UINT i; - - for (i=0; i<m_CurSize; i++) - SAFE_DELETE(((T**)m_pData)[i]); - - SAFE_DELETE_ARRAY(m_pData); - } - - void Clear() - { - Empty(); - SAFE_DELETE_ARRAY(m_pData); - m_MaxSize = 0; - } - - void Empty() - { - UINT i; - - // manually invoke destructor on all elements - for (i = 0; i < m_CurSize; ++ i) - { - SAFE_DELETE(((T**)m_pData)[i]); - } - m_CurSize = 0; - m_hLastError = S_OK; - } - - void Delete(UINT index) - { - D3DXASSERT(index < m_CurSize); - - SAFE_DELETE(((T**)m_pData)[index]); - - CEffectVector<T*>::Delete(index); - } -}; - - -////////////////////////////////////////////////////////////////////////// -// Checked UINT, DWORD64 -// Use CheckedNumber only with UINT and DWORD64 -////////////////////////////////////////////////////////////////////////// -template <class T, T MaxValue> class CheckedNumber -{ - T m_Value; - BOOL m_bValid; - -public: - CheckedNumber<T, MaxValue>() - { - m_Value = 0; - m_bValid = TRUE; - } - - CheckedNumber<T, MaxValue>(const T &value) - { - m_Value = value; - m_bValid = TRUE; - } - - CheckedNumber<T, MaxValue>(const CheckedNumber<T, MaxValue> &value) - { - m_bValid = value.m_bValid; - m_Value = value.m_Value; - } - - CheckedNumber<T, MaxValue> &operator+(const CheckedNumber<T, MaxValue> &other) - { - CheckedNumber<T, MaxValue> Res(*this); - return Res+=other; - } - - CheckedNumber<T, MaxValue> &operator+=(const CheckedNumber<T, MaxValue> &other) - { - if (!other.m_bValid) - { - m_bValid = FALSE; - } - else - { - m_Value += other.m_Value; - - if (m_Value < other.m_Value) - m_bValid = FALSE; - } - - return *this; - } - - CheckedNumber<T, MaxValue> &operator*(const CheckedNumber<T, MaxValue> &other) - { - CheckedNumber<T, MaxValue> Res(*this); - return Res*=other; - } - - CheckedNumber<T, MaxValue> &operator*=(const CheckedNumber<T, MaxValue> &other) - { - if (!other.m_bValid) - { - m_bValid = FALSE; - } - else - { - if (other.m_Value != 0) - { - if (m_Value > MaxValue / other.m_Value) - { - m_bValid = FALSE; - } - } - m_Value *= other.m_Value; - } - - return *this; - } - - HRESULT GetValue(T *pValue) - { - if (!m_bValid) - { - *pValue = -1; - return E_FAIL; - } - - *pValue = m_Value; - return S_OK; - } -}; - -typedef CheckedNumber<UINT, _UI32_MAX> CCheckedDword; -typedef CheckedNumber<DWORD64, _UI64_MAX> CCheckedDword64; - - -////////////////////////////////////////////////////////////////////////// -// Data Block Store - A linked list of allocations -////////////////////////////////////////////////////////////////////////// - -class CDataBlock -{ -protected: - UINT m_size; - UINT m_maxSize; - BYTE *m_pData; - CDataBlock *m_pNext; - - BOOL m_IsAligned; // Whether or not to align the data to c_DataAlignment - -public: - // AddData appends an existing use buffer to the data block - HRESULT AddData(const void *pNewData, UINT bufferSize, CDataBlock **ppBlock); - - // Allocate reserves bufferSize bytes of contiguous memory and returns a pointer to the user - void* Allocate(UINT bufferSize, CDataBlock **ppBlock); - - void EnableAlignment(); - - CDataBlock(); - ~CDataBlock(); - - friend class CDataBlockStore; -}; - - -class CDataBlockStore -{ -protected: - CDataBlock *m_pFirst; - CDataBlock *m_pLast; - UINT m_Size; - UINT m_Offset; // m_Offset gets added to offsets returned from AddData & AddString. Use this to set a global for the entire string block - BOOL m_IsAligned; // Whether or not to align the data to c_DataAlignment - -public: -#if _DEBUG - UINT m_cAllocations; -#endif - -public: - HRESULT AddString(LPCSTR pString, UINT *pOffset); // Writes a null-terminated string to buffer - HRESULT AddData(const void *pNewData, UINT bufferSize, UINT *pOffset); // Writes data block to buffer - - void* Allocate(UINT buffferSize); // Memory allocator support - UINT GetSize(); - void EnableAlignment(); - - CDataBlockStore(); - ~CDataBlockStore(); -}; - -// Custom allocator that uses CDataBlockStore -// The trick is that we never free, so we don't have to keep as much state around -// Use PRIVATENEW in CEffectLoader - -static void* __cdecl operator new(size_t s, CDataBlockStore &pAllocator) -{ - D3DXASSERT( s <= 0xffffffff ); - return pAllocator.Allocate( (UINT)s ); -} - -static void __cdecl operator delete(void* p, CDataBlockStore &pAllocator) -{ -} - - -////////////////////////////////////////////////////////////////////////// -// Hash table -////////////////////////////////////////////////////////////////////////// - -#define HASH_MIX(a,b,c) \ -{ \ - a -= b; a -= c; a ^= (c>>13); \ - b -= c; b -= a; b ^= (a<<8); \ - c -= a; c -= b; c ^= (b>>13); \ - a -= b; a -= c; a ^= (c>>12); \ - b -= c; b -= a; b ^= (a<<16); \ - c -= a; c -= b; c ^= (b>>5); \ - a -= b; a -= c; a ^= (c>>3); \ - b -= c; b -= a; b ^= (a<<10); \ - c -= a; c -= b; c ^= (b>>15); \ -} - -static UINT ComputeHash(BYTE *pb, UINT cbToHash) -{ - UINT a; - UINT b; - UINT c; - UINT cbLeft; - - cbLeft = cbToHash; - - a = b = 0x9e3779b9; // the golden ratio; an arbitrary value - c = 0; - - while (cbLeft >= 12) - { - UINT *pdw = reinterpret_cast<UINT *>(pb); - - a += pdw[0]; - b += pdw[1]; - c += pdw[2]; - - HASH_MIX(a,b,c); - pb += 12; - cbLeft -= 12; - } - - c += cbToHash; - - switch(cbLeft) // all the case statements fall through - { - case 11: c+=((UINT) pb[10] << 24); - case 10: c+=((UINT) pb[9] << 16); - case 9 : c+=((UINT) pb[8] << 8); - // the first byte of c is reserved for the length - case 8 : b+=((UINT) pb[7] << 24); - case 7 : b+=((UINT) pb[6] << 16); - case 6 : b+=((UINT) pb[5] << 8); - case 5 : b+=pb[4]; - case 4 : a+=((UINT) pb[3] << 24); - case 3 : a+=((UINT) pb[2] << 16); - case 2 : a+=((UINT) pb[1] << 8); - case 1 : a+=pb[0]; - } - - HASH_MIX(a,b,c); - - return c; -} - -static UINT ComputeHashLower(BYTE *pb, UINT cbToHash) -{ - UINT a; - UINT b; - UINT c; - UINT cbLeft; - - cbLeft = cbToHash; - - a = b = 0x9e3779b9; // the golden ratio; an arbitrary value - c = 0; - - while (cbLeft >= 12) - { - BYTE pbT[12]; - for( UINT i = 0; i < 12; i++ ) - pbT[i] = (BYTE)tolower(pb[i]); - - UINT *pdw = reinterpret_cast<UINT *>(pbT); - - a += pdw[0]; - b += pdw[1]; - c += pdw[2]; - - HASH_MIX(a,b,c); - pb += 12; - cbLeft -= 12; - } - - c += cbToHash; - - BYTE pbT[12]; - for( UINT i = 0; i < cbLeft; i++ ) - pbT[i] = (BYTE)tolower(pb[i]); - - switch(cbLeft) // all the case statements fall through - { - case 11: c+=((UINT) pbT[10] << 24); - case 10: c+=((UINT) pbT[9] << 16); - case 9 : c+=((UINT) pbT[8] << 8); - // the first byte of c is reserved for the length - case 8 : b+=((UINT) pbT[7] << 24); - case 7 : b+=((UINT) pbT[6] << 16); - case 6 : b+=((UINT) pbT[5] << 8); - case 5 : b+=pbT[4]; - case 4 : a+=((UINT) pbT[3] << 24); - case 3 : a+=((UINT) pbT[2] << 16); - case 2 : a+=((UINT) pbT[1] << 8); - case 1 : a+=pbT[0]; - } - - HASH_MIX(a,b,c); - - return c; -} - - -static UINT ComputeHash(LPCSTR pString) -{ - return ComputeHash((BYTE*) pString, (UINT)strlen(pString)); -} - - -// 1) these numbers are prime -// 2) each is slightly less than double the last -// 4) each is roughly in between two powers of 2; -// (2^n hash table sizes are VERY BAD; they effectively truncate your -// precision down to the n least significant bits of the hash) -static const UINT c_PrimeSizes[] = -{ - 11, - 23, - 53, - 97, - 193, - 389, - 769, - 1543, - 3079, - 6151, - 12289, - 24593, - 49157, - 98317, - 196613, - 393241, - 786433, - 1572869, - 3145739, - 6291469, - 12582917, - 25165843, - 50331653, - 100663319, - 201326611, - 402653189, - 805306457, - 1610612741, -}; - -static const UINT c_NumPrimes = sizeof(c_PrimeSizes) / sizeof(UINT); - -template<typename T, BOOL (*pfnIsEqual)(const T &Data1, const T &Data2)> -class CEffectHashTable -{ -protected: - - struct SHashEntry - { - UINT Hash; - T Data; - SHashEntry *pNext; - }; - - // Array of hash entries - SHashEntry **m_rgpHashEntries; - UINT m_NumHashSlots; - UINT m_NumEntries; - bool m_bOwnHashEntryArray; - -public: - class CIterator - { - friend class CEffectHashTable; - - protected: - SHashEntry **ppHashSlot; - SHashEntry *pHashEntry; - - public: - T GetData() - { - D3DXASSERT(NULL != pHashEntry); - return pHashEntry->Data; - } - - UINT GetHash() - { - D3DXASSERT(NULL != pHashEntry); - return pHashEntry->Hash; - } - }; - - CEffectHashTable() - { - m_rgpHashEntries = NULL; - m_NumHashSlots = 0; - m_NumEntries = 0; - m_bOwnHashEntryArray = false; - } - - HRESULT Initialize(CEffectHashTable *pOther) - { - HRESULT hr = S_OK; - SHashEntry **rgpNewHashEntries = NULL; - SHashEntry ***rgppListEnds = NULL; - UINT i; - UINT valuesMigrated = 0; - UINT actualSize; - - Cleanup(); - - actualSize = pOther->m_NumHashSlots; - VN( rgpNewHashEntries = NEW SHashEntry*[actualSize] ); - - ZeroMemory(rgpNewHashEntries, sizeof(SHashEntry*) * actualSize); - - // Expensive operation: rebuild the hash table - CIterator iter, nextIter; - pOther->GetFirstEntry(&iter); - while (!pOther->PastEnd(&iter)) - { - UINT index = iter.GetHash() % actualSize; - - // we need to advance to the next element - // before we seize control of this element and move - // it to the new table - nextIter = iter; - pOther->GetNextEntry(&nextIter); - - // seize this hash entry, migrate it to the new table - SHashEntry *pNewEntry; - VN( pNewEntry = NEW SHashEntry ); - - pNewEntry->pNext = rgpNewHashEntries[index]; - pNewEntry->Data = iter.pHashEntry->Data; - pNewEntry->Hash = iter.pHashEntry->Hash; - rgpNewHashEntries[index] = pNewEntry; - - iter = nextIter; - ++ valuesMigrated; - } - - D3DXASSERT(valuesMigrated == pOther->m_NumEntries); - - m_rgpHashEntries = rgpNewHashEntries; - m_NumHashSlots = actualSize; - m_NumEntries = pOther->m_NumEntries; - m_bOwnHashEntryArray = true; - rgpNewHashEntries = NULL; - -lExit: - SAFE_DELETE_ARRAY( rgpNewHashEntries ); - return hr; - } - -protected: - void CleanArray() - { - if (m_bOwnHashEntryArray) - { - SAFE_DELETE_ARRAY(m_rgpHashEntries); - m_bOwnHashEntryArray = false; - } - } - -public: - void Cleanup() - { - UINT i; - for (i = 0; i < m_NumHashSlots; ++ i) - { - SHashEntry *pCurrentEntry = m_rgpHashEntries[i]; - SHashEntry *pTempEntry; - while (NULL != pCurrentEntry) - { - pTempEntry = pCurrentEntry->pNext; - SAFE_DELETE(pCurrentEntry); - pCurrentEntry = pTempEntry; - -- m_NumEntries; - } - } - CleanArray(); - m_NumHashSlots = 0; - D3DXASSERT(m_NumEntries == 0); - } - - ~CEffectHashTable() - { - Cleanup(); - } - - static UINT GetNextHashTableSize(__in UINT DesiredSize) - { - // figure out the next logical size to use - for (UINT i = 0; i < c_NumPrimes; ++ i) - { - if (c_PrimeSizes[i] >= DesiredSize) - { - return c_PrimeSizes[i]; - } - } - - return DesiredSize; - } - - // O(n) function - // Grows to the next suitable size (based off of the prime number table) - // DesiredSize is merely a suggestion - HRESULT Grow(__in UINT DesiredSize, - __in UINT ProvidedArraySize = 0, - __in_ecount_opt(ProvidedArraySize) - void** ProvidedArray = NULL, - __in bool OwnProvidedArray = false) - { - HRESULT hr = S_OK; - SHashEntry **rgpNewHashEntries = NULL; - SHashEntry ***rgppListEnds = NULL; - UINT valuesMigrated = 0; - UINT actualSize; - - VB( DesiredSize > m_NumHashSlots ); - - actualSize = GetNextHashTableSize(DesiredSize); - - if (ProvidedArray && - ProvidedArraySize >= actualSize) - { - rgpNewHashEntries = reinterpret_cast<SHashEntry**>(ProvidedArray); - } - else - { - OwnProvidedArray = true; - - VN( rgpNewHashEntries = NEW SHashEntry*[actualSize] ); - } - - ZeroMemory(rgpNewHashEntries, sizeof(SHashEntry*) * actualSize); - - // Expensive operation: rebuild the hash table - CIterator iter, nextIter; - GetFirstEntry(&iter); - while (!PastEnd(&iter)) - { - UINT index = iter.GetHash() % actualSize; - - // we need to advance to the next element - // before we seize control of this element and move - // it to the new table - nextIter = iter; - GetNextEntry(&nextIter); - - // seize this hash entry, migrate it to the new table - iter.pHashEntry->pNext = rgpNewHashEntries[index]; - rgpNewHashEntries[index] = iter.pHashEntry; - - iter = nextIter; - ++ valuesMigrated; - } - - D3DXASSERT(valuesMigrated == m_NumEntries); - - CleanArray(); - m_rgpHashEntries = rgpNewHashEntries; - m_NumHashSlots = actualSize; - m_bOwnHashEntryArray = OwnProvidedArray; - -lExit: - return hr; - } - - HRESULT AutoGrow() - { - // arbitrary heuristic -- grow if 1:1 - if (m_NumEntries >= m_NumHashSlots) - { - // grows this hash table so that it is roughly 50% full - return Grow(m_NumEntries * 2 + 1); - } - return S_OK; - } - -#if _DEBUG - void PrintHashTableStats() - { - if (m_NumHashSlots == 0) - { - DPF(0, "Uninitialized hash table!"); - return; - } - - UINT i; - float variance = 0.0f; - float mean = (float)m_NumEntries / (float)m_NumHashSlots; - UINT unusedSlots = 0; - - DPF(0, "Hash table slots: %d, Entries in table: %d", m_NumHashSlots, m_NumEntries); - - for (i = 0; i < m_NumHashSlots; ++ i) - { - UINT entries = 0; - SHashEntry *pCurrentEntry = m_rgpHashEntries[i]; - - while (NULL != pCurrentEntry) - { - SHashEntry *pCurrentEntry2 = m_rgpHashEntries[i]; - - // check other hash entries in this slot for hash collisions or duplications - while (pCurrentEntry2 != pCurrentEntry) - { - if (pCurrentEntry->Hash == pCurrentEntry2->Hash) - { - if (pfnIsEqual(pCurrentEntry->Data, pCurrentEntry2->Data)) - { - D3DXASSERT(0); - DPF(0, "Duplicate entry (identical hash, identical data) found!"); - } - else - { - DPF(0, "Hash collision (hash: %d)", pCurrentEntry->Hash); - } - } - pCurrentEntry2 = pCurrentEntry2->pNext; - } - - pCurrentEntry = pCurrentEntry->pNext; - ++ entries; - } - - if (0 == entries) - { - ++ unusedSlots; - } - - // mean must be greater than 0 at this point - variance += (float)entries * (float)entries / mean; - } - - variance /= max(1.0f, (m_NumHashSlots - 1)); - variance -= (mean * mean); - - DPF(0, "Mean number of entries per slot: %f, Standard deviation: %f, Unused slots; %d", mean, variance, unusedSlots); - } -#endif // _DEBUG - - // S_OK if element is found, E_FAIL otherwise - HRESULT FindValueWithHash(T Data, UINT Hash, CIterator *pIterator) - { - D3DXASSERT(m_NumHashSlots > 0); - - UINT index = Hash % m_NumHashSlots; - SHashEntry *pEntry = m_rgpHashEntries[index]; - while (NULL != pEntry) - { - if (Hash == pEntry->Hash && pfnIsEqual(pEntry->Data, Data)) - { - pIterator->ppHashSlot = m_rgpHashEntries + index; - pIterator->pHashEntry = pEntry; - return S_OK; - } - pEntry = pEntry->pNext; - } - return E_FAIL; - } - - // S_OK if element is found, E_FAIL otherwise - HRESULT FindFirstMatchingValue(UINT Hash, CIterator *pIterator) - { - D3DXASSERT(m_NumHashSlots > 0); - - UINT index = Hash % m_NumHashSlots; - SHashEntry *pEntry = m_rgpHashEntries[index]; - while (NULL != pEntry) - { - if (Hash == pEntry->Hash) - { - pIterator->ppHashSlot = m_rgpHashEntries + index; - pIterator->pHashEntry = pEntry; - return S_OK; - } - pEntry = pEntry->pNext; - } - return E_FAIL; - } - - // Adds data at the specified hash slot without checking for existence - HRESULT AddValueWithHash(T Data, UINT Hash) - { - HRESULT hr = S_OK; - - D3DXASSERT(m_NumHashSlots > 0); - - SHashEntry *pHashEntry; - UINT index = Hash % m_NumHashSlots; - - VN( pHashEntry = NEW SHashEntry ); - pHashEntry->pNext = m_rgpHashEntries[index]; - pHashEntry->Data = Data; - pHashEntry->Hash = Hash; - m_rgpHashEntries[index] = pHashEntry; - - ++ m_NumEntries; - -lExit: - return hr; - } - - // Iterator code: - // - // CMyHashTable::CIterator myIt; - // for (myTable.GetFirstEntry(&myIt); !myTable.PastEnd(&myIt); myTable.GetNextEntry(&myIt) - // { myTable.GetData(&myIt); } - void GetFirstEntry(CIterator *pIterator) - { - SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots; - pIterator->ppHashSlot = m_rgpHashEntries; - while (pIterator->ppHashSlot < ppEnd) - { - if (NULL != *(pIterator->ppHashSlot)) - { - pIterator->pHashEntry = *(pIterator->ppHashSlot); - return; - } - ++ pIterator->ppHashSlot; - } - } - - BOOL PastEnd(CIterator *pIterator) - { - SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots; - D3DXASSERT(pIterator->ppHashSlot >= m_rgpHashEntries && pIterator->ppHashSlot <= ppEnd); - return (pIterator->ppHashSlot == ppEnd); - } - - void GetNextEntry(CIterator *pIterator) - { - SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots; - D3DXASSERT(pIterator->ppHashSlot >= m_rgpHashEntries && pIterator->ppHashSlot <= ppEnd); - D3DXASSERT(NULL != pIterator->pHashEntry); - - pIterator->pHashEntry = pIterator->pHashEntry->pNext; - if (NULL != pIterator->pHashEntry) - { - return; - } - - ++ pIterator->ppHashSlot; - while (pIterator->ppHashSlot < ppEnd) - { - pIterator->pHashEntry = *(pIterator->ppHashSlot); - if (NULL != pIterator->pHashEntry) - { - return; - } - ++ pIterator->ppHashSlot; - } - // hit the end of the list, ppHashSlot == ppEnd - } - - void RemoveEntry(CIterator *pIterator) - { - SHashEntry *pTemp; - SHashEntry **ppPrev; - SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots; - - D3DXASSERT(pIterator && !PastEnd(pIterator)); - ppPrev = pIterator->ppHashSlot; - pTemp = *ppPrev; - while (pTemp) - { - if (pTemp == pIterator->pHashEntry) - { - *ppPrev = pTemp->pNext; - pIterator->ppHashSlot = ppEnd; - delete pTemp; - return; - } - ppPrev = &pTemp->pNext; - pTemp = pTemp->pNext; - } - - // Should never get here - D3DXASSERT(0); - } - -}; - -// Allocates the hash slots on the regular heap (since the -// hash table can grow), but all hash entries are allocated on -// a private heap - -template<typename T, BOOL (*pfnIsEqual)(const T &Data1, const T &Data2)> -class CEffectHashTableWithPrivateHeap : public CEffectHashTable<T, pfnIsEqual> -{ -protected: - CDataBlockStore *m_pPrivateHeap; - -public: - CEffectHashTableWithPrivateHeap() - { - m_pPrivateHeap = NULL; - } - - void Cleanup() - { - CleanArray(); - m_NumHashSlots = 0; - m_NumEntries = 0; - } - - ~CEffectHashTableWithPrivateHeap() - { - Cleanup(); - } - - // Call this only once - void SetPrivateHeap(CDataBlockStore *pPrivateHeap) - { - D3DXASSERT(NULL == m_pPrivateHeap); - m_pPrivateHeap = pPrivateHeap; - } - - // Adds data at the specified hash slot without checking for existence - HRESULT AddValueWithHash(T Data, UINT Hash) - { - HRESULT hr = S_OK; - - D3DXASSERT(NULL != m_pPrivateHeap); - D3DXASSERT(m_NumHashSlots > 0); - - SHashEntry *pHashEntry; - UINT index = Hash % m_NumHashSlots; - - VN( pHashEntry = new(*m_pPrivateHeap) SHashEntry ); - pHashEntry->pNext = m_rgpHashEntries[index]; - pHashEntry->Data = Data; - pHashEntry->Hash = Hash; - m_rgpHashEntries[index] = pHashEntry; - - ++ m_NumEntries; - -lExit: - return hr; - } -}; |