| // Copyright 2014 PDFium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com |
| |
| #include "../../include/fxcrt/fx_ext.h" |
| #include "plex.h" |
| static void ConstructElement(CFX_ByteString* pNewData) |
| { |
| new (pNewData) CFX_ByteString(); |
| } |
| static void DestructElement(CFX_ByteString* pOldData) |
| { |
| pOldData->~CFX_ByteString(); |
| } |
| CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize) |
| : m_pHashTable(NULL) |
| , m_nHashTableSize(17) |
| , m_nCount(0) |
| , m_pFreeList(NULL) |
| , m_pBlocks(NULL) |
| , m_nBlockSize(nBlockSize) |
| { |
| ASSERT(m_nBlockSize > 0); |
| } |
| void CFX_MapPtrToPtr::RemoveAll() |
| { |
| if (m_pHashTable) { |
| FX_Free(m_pHashTable); |
| m_pHashTable = NULL; |
| } |
| m_nCount = 0; |
| m_pFreeList = NULL; |
| m_pBlocks->FreeDataChain(); |
| m_pBlocks = NULL; |
| } |
| CFX_MapPtrToPtr::~CFX_MapPtrToPtr() |
| { |
| RemoveAll(); |
| ASSERT(m_nCount == 0); |
| } |
| FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const |
| { |
| return ((FX_DWORD)(uintptr_t)key) >> 4; |
| } |
| void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition, void*& rKey, void*& rValue) const |
| { |
| ASSERT(m_pHashTable != NULL); |
| CAssoc* pAssocRet = (CAssoc*)rNextPosition; |
| ASSERT(pAssocRet != NULL); |
| if (pAssocRet == (CAssoc*) - 1) { |
| for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) |
| if ((pAssocRet = m_pHashTable[nBucket]) != NULL) { |
| break; |
| } |
| ASSERT(pAssocRet != NULL); |
| } |
| CAssoc* pAssocNext; |
| if ((pAssocNext = pAssocRet->pNext) == NULL) { |
| for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1; nBucket < m_nHashTableSize; nBucket ++) { |
| if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { |
| break; |
| } |
| } |
| } |
| rNextPosition = (FX_POSITION) pAssocNext; |
| rKey = pAssocRet->key; |
| rValue = pAssocRet->value; |
| } |
| FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const |
| { |
| FX_DWORD nHash; |
| CAssoc* pAssoc = GetAssocAt(key, nHash); |
| if (pAssoc == NULL) { |
| return FALSE; |
| } |
| rValue = pAssoc->value; |
| return TRUE; |
| } |
| void* CFX_MapPtrToPtr::GetValueAt(void* key) const |
| { |
| FX_DWORD nHash; |
| CAssoc* pAssoc = GetAssocAt(key, nHash); |
| if (pAssoc == NULL) { |
| return NULL; |
| } |
| return pAssoc->value; |
| } |
| void*& CFX_MapPtrToPtr::operator[](void* key) |
| { |
| FX_DWORD nHash; |
| CAssoc* pAssoc; |
| if ((pAssoc = GetAssocAt(key, nHash)) == NULL) { |
| if (m_pHashTable == NULL) { |
| InitHashTable(m_nHashTableSize); |
| } |
| pAssoc = NewAssoc(); |
| pAssoc->key = key; |
| pAssoc->pNext = m_pHashTable[nHash]; |
| m_pHashTable[nHash] = pAssoc; |
| } |
| return pAssoc->value; |
| } |
| CFX_MapPtrToPtr::CAssoc* |
| CFX_MapPtrToPtr::GetAssocAt(void* key, FX_DWORD& nHash) const |
| { |
| nHash = HashKey(key) % m_nHashTableSize; |
| if (m_pHashTable == NULL) { |
| return NULL; |
| } |
| CAssoc* pAssoc; |
| for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| if (pAssoc->key == key) { |
| return pAssoc; |
| } |
| } |
| return NULL; |
| } |
| CFX_MapPtrToPtr::CAssoc* |
| CFX_MapPtrToPtr::NewAssoc() |
| { |
| if (m_pFreeList == NULL) { |
| CFX_Plex* newBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize, sizeof(CFX_MapPtrToPtr::CAssoc)); |
| CFX_MapPtrToPtr::CAssoc* pAssoc = (CFX_MapPtrToPtr::CAssoc*)newBlock->data(); |
| 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); |
| CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList; |
| m_pFreeList = m_pFreeList->pNext; |
| m_nCount++; |
| ASSERT(m_nCount > 0); |
| pAssoc->key = 0; |
| pAssoc->value = 0; |
| return pAssoc; |
| } |
| void CFX_MapPtrToPtr::InitHashTable( |
| FX_DWORD nHashSize, FX_BOOL bAllocNow) |
| { |
| ASSERT(m_nCount == 0); |
| ASSERT(nHashSize > 0); |
| if (m_pHashTable != NULL) { |
| FX_Free(m_pHashTable); |
| m_pHashTable = NULL; |
| } |
| if (bAllocNow) { |
| m_pHashTable = FX_Alloc(CAssoc*, nHashSize); |
| } |
| m_nHashTableSize = nHashSize; |
| } |
| FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key) |
| { |
| if (m_pHashTable == NULL) { |
| return FALSE; |
| } |
| CAssoc** ppAssocPrev; |
| ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; |
| CAssoc* pAssoc; |
| for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| if (pAssoc->key == key) { |
| *ppAssocPrev = pAssoc->pNext; |
| FreeAssoc(pAssoc); |
| return TRUE; |
| } |
| ppAssocPrev = &pAssoc->pNext; |
| } |
| return FALSE; |
| } |
| void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) |
| { |
| pAssoc->pNext = m_pFreeList; |
| m_pFreeList = pAssoc; |
| m_nCount--; |
| ASSERT(m_nCount >= 0); |
| if (m_nCount == 0) { |
| RemoveAll(); |
| } |
| } |
| CFX_MapByteStringToPtr::CFX_MapByteStringToPtr(int nBlockSize) |
| : m_pHashTable(NULL) |
| , m_nHashTableSize(17) |
| , m_nCount(0) |
| , m_pFreeList(NULL) |
| , m_pBlocks(NULL) |
| , m_nBlockSize(nBlockSize) |
| { |
| ASSERT(m_nBlockSize > 0); |
| } |
| void CFX_MapByteStringToPtr::RemoveAll() |
| { |
| if (m_pHashTable != NULL) { |
| for (FX_DWORD nHash = 0; nHash < m_nHashTableSize; nHash++) { |
| CAssoc* pAssoc; |
| for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; |
| pAssoc = pAssoc->pNext) { |
| DestructElement(&pAssoc->key); |
| } |
| } |
| FX_Free(m_pHashTable); |
| m_pHashTable = NULL; |
| } |
| m_nCount = 0; |
| m_pFreeList = NULL; |
| m_pBlocks->FreeDataChain(); |
| m_pBlocks = NULL; |
| } |
| CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr() |
| { |
| RemoveAll(); |
| ASSERT(m_nCount == 0); |
| } |
| void CFX_MapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, |
| CFX_ByteString& rKey, void*& rValue) const |
| { |
| ASSERT(m_pHashTable != NULL); |
| CAssoc* pAssocRet = (CAssoc*)rNextPosition; |
| ASSERT(pAssocRet != NULL); |
| if (pAssocRet == (CAssoc*) - 1) { |
| for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) |
| if ((pAssocRet = m_pHashTable[nBucket]) != NULL) { |
| break; |
| } |
| ASSERT(pAssocRet != NULL); |
| } |
| CAssoc* pAssocNext; |
| if ((pAssocNext = pAssocRet->pNext) == NULL) { |
| for (FX_DWORD nBucket = pAssocRet->nHashValue + 1; |
| nBucket < m_nHashTableSize; nBucket++) |
| if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { |
| break; |
| } |
| } |
| rNextPosition = (FX_POSITION) pAssocNext; |
| rKey = pAssocRet->key; |
| rValue = pAssocRet->value; |
| } |
| void* CFX_MapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const |
| { |
| ASSERT(m_pHashTable != NULL); |
| CAssoc* pAssocRet = (CAssoc*)rNextPosition; |
| ASSERT(pAssocRet != NULL); |
| if (pAssocRet == (CAssoc*) - 1) { |
| for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) |
| if ((pAssocRet = m_pHashTable[nBucket]) != NULL) { |
| break; |
| } |
| ASSERT(pAssocRet != NULL); |
| } |
| CAssoc* pAssocNext; |
| if ((pAssocNext = pAssocRet->pNext) == NULL) { |
| for (FX_DWORD nBucket = pAssocRet->nHashValue + 1; |
| nBucket < m_nHashTableSize; nBucket++) |
| if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { |
| break; |
| } |
| } |
| rNextPosition = (FX_POSITION) pAssocNext; |
| return pAssocRet->value; |
| } |
| void*& CFX_MapByteStringToPtr::operator[](const CFX_ByteStringC& key) |
| { |
| FX_DWORD nHash; |
| CAssoc* pAssoc; |
| if ((pAssoc = GetAssocAt(key, nHash)) == NULL) { |
| if (m_pHashTable == NULL) { |
| InitHashTable(m_nHashTableSize); |
| } |
| pAssoc = NewAssoc(); |
| pAssoc->nHashValue = nHash; |
| pAssoc->key = key; |
| pAssoc->pNext = m_pHashTable[nHash]; |
| m_pHashTable[nHash] = pAssoc; |
| } |
| return pAssoc->value; |
| } |
| CFX_MapByteStringToPtr::CAssoc* |
| CFX_MapByteStringToPtr::NewAssoc() |
| { |
| if (m_pFreeList == NULL) { |
| CFX_Plex* newBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize, sizeof(CFX_MapByteStringToPtr::CAssoc)); |
| CFX_MapByteStringToPtr::CAssoc* pAssoc = (CFX_MapByteStringToPtr::CAssoc*)newBlock->data(); |
| 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); |
| CFX_MapByteStringToPtr::CAssoc* pAssoc = m_pFreeList; |
| m_pFreeList = m_pFreeList->pNext; |
| m_nCount++; |
| ASSERT(m_nCount > 0); |
| ConstructElement(&pAssoc->key); |
| pAssoc->value = 0; |
| return pAssoc; |
| } |
| void CFX_MapByteStringToPtr::FreeAssoc(CFX_MapByteStringToPtr::CAssoc* pAssoc) |
| { |
| DestructElement(&pAssoc->key); |
| pAssoc->pNext = m_pFreeList; |
| m_pFreeList = pAssoc; |
| m_nCount--; |
| ASSERT(m_nCount >= 0); |
| if (m_nCount == 0) { |
| RemoveAll(); |
| } |
| } |
| CFX_MapByteStringToPtr::CAssoc* |
| CFX_MapByteStringToPtr::GetAssocAt(const CFX_ByteStringC& key, FX_DWORD& nHash) const |
| { |
| nHash = HashKey(key) % m_nHashTableSize; |
| if (m_pHashTable == NULL) { |
| return NULL; |
| } |
| CAssoc* pAssoc; |
| for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| if (pAssoc->key == key) { |
| return pAssoc; |
| } |
| } |
| return NULL; |
| } |
| FX_BOOL CFX_MapByteStringToPtr::Lookup(const CFX_ByteStringC& key, void*& rValue) const |
| { |
| FX_DWORD nHash; |
| CAssoc* pAssoc = GetAssocAt(key, nHash); |
| if (pAssoc == NULL) { |
| return FALSE; |
| } |
| rValue = pAssoc->value; |
| return TRUE; |
| } |
| void CFX_MapByteStringToPtr::InitHashTable( |
| FX_DWORD nHashSize, FX_BOOL bAllocNow) |
| { |
| ASSERT(m_nCount == 0); |
| ASSERT(nHashSize > 0); |
| if (m_pHashTable != NULL) { |
| FX_Free(m_pHashTable); |
| m_pHashTable = NULL; |
| } |
| if (bAllocNow) { |
| m_pHashTable = FX_Alloc(CAssoc*, nHashSize); |
| } |
| m_nHashTableSize = nHashSize; |
| } |
| inline FX_DWORD CFX_MapByteStringToPtr::HashKey(const CFX_ByteStringC& key) const |
| { |
| FX_DWORD nHash = 0; |
| int len = key.GetLength(); |
| const uint8_t* buf = key.GetPtr(); |
| for (int i = 0; i < len; i ++) { |
| nHash = (nHash << 5) + nHash + buf[i]; |
| } |
| return nHash; |
| } |
| FX_BOOL CFX_MapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) |
| { |
| if (m_pHashTable == NULL) { |
| return FALSE; |
| } |
| CAssoc** ppAssocPrev; |
| ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; |
| CAssoc* pAssoc; |
| for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| if (pAssoc->key == key) { |
| *ppAssocPrev = pAssoc->pNext; |
| FreeAssoc(pAssoc); |
| return TRUE; |
| } |
| ppAssocPrev = &pAssoc->pNext; |
| } |
| return FALSE; |
| } |
| struct _CompactString { |
| uint8_t m_CompactLen; |
| uint8_t m_LenHigh; |
| uint8_t m_LenLow; |
| uint8_t m_Unused; |
| uint8_t* m_pBuffer; |
| }; |
| static void _CompactStringRelease(_CompactString* pCompact) |
| { |
| if (pCompact->m_CompactLen == 0xff) { |
| FX_Free(pCompact->m_pBuffer); |
| } |
| } |
| static FX_BOOL _CompactStringSame(_CompactString* pCompact, const uint8_t* pStr, int len) |
| { |
| if (len < sizeof(_CompactString)) { |
| if (pCompact->m_CompactLen != len) { |
| return FALSE; |
| } |
| return FXSYS_memcmp32(&pCompact->m_LenHigh, pStr, len) == 0; |
| } |
| if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) { |
| return FALSE; |
| } |
| return FXSYS_memcmp32(pCompact->m_pBuffer, pStr, len) == 0; |
| } |
| static void _CompactStringStore(_CompactString* pCompact, const uint8_t* pStr, int len) |
| { |
| if (len < (int)sizeof(_CompactString)) { |
| pCompact->m_CompactLen = (uint8_t)len; |
| FXSYS_memcpy32(&pCompact->m_LenHigh, pStr, len); |
| return; |
| } |
| pCompact->m_CompactLen = 0xff; |
| pCompact->m_LenHigh = len / 256; |
| pCompact->m_LenLow = len % 256; |
| pCompact->m_pBuffer = FX_Alloc(uint8_t, len); |
| FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len); |
| } |
| static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact) |
| { |
| if (pCompact->m_CompactLen == 0xff) { |
| return CFX_ByteStringC(pCompact->m_pBuffer, pCompact->m_LenHigh * 256 + pCompact->m_LenLow); |
| } |
| if (pCompact->m_CompactLen == 0xfe) { |
| return CFX_ByteStringC(); |
| } |
| return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen); |
| } |
| #define CMAP_ALLOC_STEP 8 |
| #define CMAP_INDEX_SIZE 8 |
| CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr() |
| : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE) |
| { |
| } |
| CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr() |
| { |
| RemoveAll(); |
| } |
| void CFX_CMapByteStringToPtr::RemoveAll() |
| { |
| int size = m_Buffer.GetSize(); |
| for (int i = 0; i < size; i++) { |
| _CompactStringRelease((_CompactString*)m_Buffer.GetAt(i)); |
| } |
| m_Buffer.RemoveAll(); |
| } |
| FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const |
| { |
| int size = m_Buffer.GetSize(); |
| for (int i = 0; i < size; i ++) { |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i); |
| if (pKey->m_CompactLen != 0xfe) { |
| return (FX_POSITION)(uintptr_t)(i + 1); |
| } |
| } |
| return NULL; |
| } |
| void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const |
| { |
| if (rNextPosition == NULL) { |
| return; |
| } |
| int index = (int)(uintptr_t)rNextPosition - 1; |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); |
| rKey = _CompactStringGet(pKey); |
| rValue = *(void**)(pKey + 1); |
| index ++; |
| int size = m_Buffer.GetSize(); |
| while (index < size) { |
| pKey = (_CompactString*)m_Buffer.GetAt(index); |
| if (pKey->m_CompactLen != 0xfe) { |
| rNextPosition = (FX_POSITION)(uintptr_t)(index + 1); |
| return; |
| } |
| index ++; |
| } |
| rNextPosition = NULL; |
| } |
| void* CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const |
| { |
| if (rNextPosition == NULL) { |
| return NULL; |
| } |
| int index = (int)(uintptr_t)rNextPosition - 1; |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); |
| void* rValue = *(void**)(pKey + 1); |
| index ++; |
| int size = m_Buffer.GetSize(); |
| while (index < size) { |
| pKey = (_CompactString*)m_Buffer.GetAt(index); |
| if (pKey->m_CompactLen != 0xfe) { |
| rNextPosition = (FX_POSITION)(uintptr_t)(index + 1); |
| return rValue; |
| } |
| index ++; |
| } |
| rNextPosition = NULL; |
| return rValue; |
| } |
| FX_BOOL _CMapLookupCallback(void* param, void* pData) |
| { |
| return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength()); |
| } |
| FX_BOOL CFX_CMapByteStringToPtr::Lookup(const CFX_ByteStringC& key, void*& rValue) const |
| { |
| void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key); |
| if (!p) { |
| return FALSE; |
| } |
| rValue = *(void**)((_CompactString*)p + 1); |
| return TRUE; |
| } |
| void CFX_CMapByteStringToPtr::SetAt(const CFX_ByteStringC& key, void* value) |
| { |
| ASSERT(value != NULL); |
| int index, key_len = key.GetLength(); |
| int size = m_Buffer.GetSize(); |
| for (index = 0; index < size; index ++) { |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); |
| if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) { |
| continue; |
| } |
| *(void**)(pKey + 1) = value; |
| return; |
| } |
| for (index = 0; index < size; index ++) { |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); |
| if (pKey->m_CompactLen) { |
| continue; |
| } |
| _CompactStringStore(pKey, key.GetPtr(), key_len); |
| *(void**)(pKey + 1) = value; |
| return; |
| } |
| _CompactString* pKey = (_CompactString*)m_Buffer.Add(); |
| _CompactStringStore(pKey, key.GetPtr(), key_len); |
| *(void**)(pKey + 1) = value; |
| } |
| void CFX_CMapByteStringToPtr::AddValue(const CFX_ByteStringC& key, void* value) |
| { |
| ASSERT(value != NULL); |
| _CompactString* pKey = (_CompactString*)m_Buffer.Add(); |
| _CompactStringStore(pKey, key.GetPtr(), key.GetLength()); |
| *(void**)(pKey + 1) = value; |
| } |
| void CFX_CMapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) |
| { |
| int key_len = key.GetLength(); |
| int size = m_Buffer.GetSize(); |
| for (int index = 0; index < size; index++) { |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); |
| if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) { |
| continue; |
| } |
| _CompactStringRelease(pKey); |
| pKey->m_CompactLen = 0xfe; |
| return; |
| } |
| } |
| int CFX_CMapByteStringToPtr::GetCount() const |
| { |
| int count = 0; |
| int size = m_Buffer.GetSize(); |
| for (int i = 0; i < size; i ++) { |
| _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i); |
| if (pKey->m_CompactLen != 0xfe) { |
| count ++; |
| } |
| } |
| return count; |
| } |
| extern "C" { |
| static int _CompareDWord(const void* p1, const void* p2) |
| { |
| return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2); |
| } |
| }; |
| struct _DWordPair { |
| FX_DWORD key; |
| FX_DWORD value; |
| }; |
| FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const |
| { |
| void* pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize() / sizeof(_DWordPair), |
| sizeof(_DWordPair), _CompareDWord); |
| if (pResult == NULL) { |
| return FALSE; |
| } |
| value = ((FX_DWORD*)pResult)[1]; |
| return TRUE; |
| } |
| FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const |
| { |
| FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); |
| if (count == 0) { |
| return NULL; |
| } |
| return (FX_POSITION)1; |
| } |
| void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const |
| { |
| if (pos == 0) { |
| return; |
| } |
| FX_DWORD index = ((FX_DWORD)(uintptr_t)pos) - 1; |
| FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); |
| _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); |
| key = buf[index].key; |
| value = buf[index].value; |
| if (index == count - 1) { |
| pos = 0; |
| } else { |
| pos = (FX_POSITION)((uintptr_t)pos + 1); |
| } |
| } |
| void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value) |
| { |
| FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); |
| _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); |
| _DWordPair pair = {key, value}; |
| if (count == 0 || key > buf[count - 1].key) { |
| m_Buffer.AppendBlock(&pair, sizeof(_DWordPair)); |
| return; |
| } |
| int low = 0, high = count - 1; |
| while (low <= high) { |
| int mid = (low + high) / 2; |
| if (buf[mid].key < key) { |
| low = mid + 1; |
| } else if (buf[mid].key > key) { |
| high = mid - 1; |
| } else { |
| buf[mid].value = value; |
| return; |
| } |
| } |
| m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair)); |
| } |
| void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) |
| { |
| m_Buffer.EstimateSize(size, grow_by); |
| } |
