From 3f3b45cc74b0499912409f766a595945dbbfc4c5 Mon Sep 17 00:00:00 2001 From: John Abd-El-Malek Date: Fri, 23 May 2014 17:28:10 -0700 Subject: Convert all line endings to LF. --- core/src/fxcrt/fx_basic_maps.cpp | 1308 +++++++++++++++++++------------------- 1 file changed, 654 insertions(+), 654 deletions(-) (limited to 'core/src/fxcrt/fx_basic_maps.cpp') 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); +} -- cgit v1.2.3