diff options
Diffstat (limited to 'core/src/fxcrt/fx_basic_maps.cpp')
| -rw-r--r-- | core/src/fxcrt/fx_basic_maps.cpp | 1308 |
1 files changed, 654 insertions, 654 deletions
diff --git a/core/src/fxcrt/fx_basic_maps.cpp b/core/src/fxcrt/fx_basic_maps.cpp index cb397ee8bd..a0b1788a82 100644 --- a/core/src/fxcrt/fx_basic_maps.cpp +++ b/core/src/fxcrt/fx_basic_maps.cpp @@ -1,654 +1,654 @@ -// 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, IFX_Allocator* pAllocator)
- : m_pAllocator(pAllocator)
- , 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_Allocator_Free(m_pAllocator, m_pHashTable);
- m_pHashTable = NULL;
- }
- m_nCount = 0;
- m_pFreeList = NULL;
- m_pBlocks->FreeDataChain(m_pAllocator);
- m_pBlocks = NULL;
-}
-CFX_MapPtrToPtr::~CFX_MapPtrToPtr()
-{
- RemoveAll();
- ASSERT(m_nCount == 0);
-}
-FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const
-{
- return ((FX_DWORD)(FX_UINTPTR)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_pAllocator, 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_Allocator_Free(m_pAllocator, m_pHashTable);
- m_pHashTable = NULL;
- }
- if (bAllocNow) {
- m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);
- if (m_pHashTable) {
- FXSYS_memset32(m_pHashTable, 0, sizeof(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, IFX_Allocator* pAllocator)
- : m_pAllocator(pAllocator)
- , 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_Allocator_Free(m_pAllocator, m_pHashTable);
- m_pHashTable = NULL;
- }
- m_nCount = 0;
- m_pFreeList = NULL;
- m_pBlocks->FreeDataChain(m_pAllocator);
- 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;
-}
-FX_LPVOID 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[](FX_BSTR 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_pAllocator, 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(FX_BSTR 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(FX_BSTR 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_Allocator_Free(m_pAllocator, m_pHashTable);
- m_pHashTable = NULL;
- }
- if (bAllocNow) {
- m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);
- if (m_pHashTable) {
- FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
- }
- }
- m_nHashTableSize = nHashSize;
-}
-inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const
-{
- FX_DWORD nHash = 0;
- int len = key.GetLength();
- FX_LPCBYTE buf = key;
- for (int i = 0; i < len; i ++) {
- nHash = (nHash << 5) + nHash + buf[i];
- }
- return nHash;
-}
-FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR 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 {
- FX_BYTE m_CompactLen;
- FX_BYTE m_LenHigh;
- FX_BYTE m_LenLow;
- FX_BYTE m_Unused;
- FX_LPBYTE m_pBuffer;
-};
-static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact)
-{
- if (pCompact->m_CompactLen == 0xff) {
- FX_Allocator_Free(pAllocator, pCompact->m_pBuffer);
- }
-}
-static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE 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(IFX_Allocator* pAllocator, _CompactString* pCompact, FX_LPCBYTE pStr, int len)
-{
- if (len < (int)sizeof(_CompactString)) {
- pCompact->m_CompactLen = (FX_BYTE)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_Allocator_Alloc(pAllocator, FX_BYTE, len);
- if (pCompact->m_pBuffer) {
- 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(IFX_Allocator* pAllocator)
- : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator)
-{
-}
-CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()
-{
- RemoveAll();
-}
-void CFX_CMapByteStringToPtr::RemoveAll()
-{
- IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;
- int size = m_Buffer.GetSize();
- for (int i = 0; i < size; i ++) {
- _CompactStringRelease(pAllocator, (_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)(FX_UINTPTR)(i + 1);
- }
- }
- return NULL;
-}
-void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const
-{
- if (rNextPosition == NULL) {
- return;
- }
- int index = (int)(FX_UINTPTR)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)(FX_UINTPTR)(index + 1);
- return;
- }
- index ++;
- }
- rNextPosition = NULL;
-}
-FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const
-{
- if (rNextPosition == NULL) {
- return NULL;
- }
- int index = (int)(FX_UINTPTR)rNextPosition - 1;
- _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
- FX_LPVOID 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)(FX_UINTPTR)(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(FX_BSTR 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(FX_BSTR 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, (FX_LPCBYTE)key, key_len)) {
- continue;
- }
- *(void**)(pKey + 1) = value;
- return;
- }
- IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;
- for (index = 0; index < size; index ++) {
- _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
- if (pKey->m_CompactLen) {
- continue;
- }
- _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);
- *(void**)(pKey + 1) = value;
- return;
- }
- _CompactString* pKey = (_CompactString*)m_Buffer.Add();
- _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);
- *(void**)(pKey + 1) = value;
-}
-void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value)
-{
- ASSERT(value != NULL);
- _CompactString* pKey = (_CompactString*)m_Buffer.Add();
- _CompactStringStore(m_Buffer.m_pAllocator, pKey, (FX_LPCBYTE)key, key.GetLength());
- *(void**)(pKey + 1) = value;
-}
-void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key)
-{
- int key_len = key.GetLength();
- IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;
- int size = m_Buffer.GetSize();
- for (int index = 0; index < size; index ++) {
- _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
- if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {
- continue;
- }
- _CompactStringRelease(pAllocator, 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
-{
- FX_LPVOID 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)(FX_UINTPTR)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)((FX_UINTPTR)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);
-}
+// 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, IFX_Allocator* pAllocator) + : m_pAllocator(pAllocator) + , 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_Allocator_Free(m_pAllocator, m_pHashTable); + m_pHashTable = NULL; + } + m_nCount = 0; + m_pFreeList = NULL; + m_pBlocks->FreeDataChain(m_pAllocator); + m_pBlocks = NULL; +} +CFX_MapPtrToPtr::~CFX_MapPtrToPtr() +{ + RemoveAll(); + ASSERT(m_nCount == 0); +} +FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const +{ + return ((FX_DWORD)(FX_UINTPTR)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_pAllocator, 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_Allocator_Free(m_pAllocator, m_pHashTable); + m_pHashTable = NULL; + } + if (bAllocNow) { + m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize); + if (m_pHashTable) { + FXSYS_memset32(m_pHashTable, 0, sizeof(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, IFX_Allocator* pAllocator) + : m_pAllocator(pAllocator) + , 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_Allocator_Free(m_pAllocator, m_pHashTable); + m_pHashTable = NULL; + } + m_nCount = 0; + m_pFreeList = NULL; + m_pBlocks->FreeDataChain(m_pAllocator); + 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; +} +FX_LPVOID 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[](FX_BSTR 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_pAllocator, 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(FX_BSTR 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(FX_BSTR 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_Allocator_Free(m_pAllocator, m_pHashTable); + m_pHashTable = NULL; + } + if (bAllocNow) { + m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize); + if (m_pHashTable) { + FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize); + } + } + m_nHashTableSize = nHashSize; +} +inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const +{ + FX_DWORD nHash = 0; + int len = key.GetLength(); + FX_LPCBYTE buf = key; + for (int i = 0; i < len; i ++) { + nHash = (nHash << 5) + nHash + buf[i]; + } + return nHash; +} +FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR 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 { + FX_BYTE m_CompactLen; + FX_BYTE m_LenHigh; + FX_BYTE m_LenLow; + FX_BYTE m_Unused; + FX_LPBYTE m_pBuffer; +}; +static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact) +{ + if (pCompact->m_CompactLen == 0xff) { + FX_Allocator_Free(pAllocator, pCompact->m_pBuffer); + } +} +static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE 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(IFX_Allocator* pAllocator, _CompactString* pCompact, FX_LPCBYTE pStr, int len) +{ + if (len < (int)sizeof(_CompactString)) { + pCompact->m_CompactLen = (FX_BYTE)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_Allocator_Alloc(pAllocator, FX_BYTE, len); + if (pCompact->m_pBuffer) { + 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(IFX_Allocator* pAllocator) + : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator) +{ +} +CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr() +{ + RemoveAll(); +} +void CFX_CMapByteStringToPtr::RemoveAll() +{ + IFX_Allocator* pAllocator = m_Buffer.m_pAllocator; + int size = m_Buffer.GetSize(); + for (int i = 0; i < size; i ++) { + _CompactStringRelease(pAllocator, (_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)(FX_UINTPTR)(i + 1); + } + } + return NULL; +} +void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const +{ + if (rNextPosition == NULL) { + return; + } + int index = (int)(FX_UINTPTR)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)(FX_UINTPTR)(index + 1); + return; + } + index ++; + } + rNextPosition = NULL; +} +FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const +{ + if (rNextPosition == NULL) { + return NULL; + } + int index = (int)(FX_UINTPTR)rNextPosition - 1; + _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); + FX_LPVOID 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)(FX_UINTPTR)(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(FX_BSTR 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(FX_BSTR 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, (FX_LPCBYTE)key, key_len)) { + continue; + } + *(void**)(pKey + 1) = value; + return; + } + IFX_Allocator* pAllocator = m_Buffer.m_pAllocator; + for (index = 0; index < size; index ++) { + _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); + if (pKey->m_CompactLen) { + continue; + } + _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len); + *(void**)(pKey + 1) = value; + return; + } + _CompactString* pKey = (_CompactString*)m_Buffer.Add(); + _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len); + *(void**)(pKey + 1) = value; +} +void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value) +{ + ASSERT(value != NULL); + _CompactString* pKey = (_CompactString*)m_Buffer.Add(); + _CompactStringStore(m_Buffer.m_pAllocator, pKey, (FX_LPCBYTE)key, key.GetLength()); + *(void**)(pKey + 1) = value; +} +void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key) +{ + int key_len = key.GetLength(); + IFX_Allocator* pAllocator = m_Buffer.m_pAllocator; + int size = m_Buffer.GetSize(); + for (int index = 0; index < size; index ++) { + _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); + if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) { + continue; + } + _CompactStringRelease(pAllocator, 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 +{ + FX_LPVOID 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)(FX_UINTPTR)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)((FX_UINTPTR)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); +} |