diff options
Diffstat (limited to 'core/src/fxcrt/fx_basic_maps.cpp')
| -rw-r--r-- | core/src/fxcrt/fx_basic_maps.cpp | 654 |
1 files changed, 654 insertions, 0 deletions
diff --git a/core/src/fxcrt/fx_basic_maps.cpp b/core/src/fxcrt/fx_basic_maps.cpp new file mode 100644 index 0000000000..cb397ee8bd --- /dev/null +++ b/core/src/fxcrt/fx_basic_maps.cpp @@ -0,0 +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);
+}
|