1 // Copyright 2014 PDFium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6 7 #include "core/include/fxcrt/fx_basic.h" 8 #include "plex.h" 9 10 namespace { 11 12 const uint8_t kFreeLength = 0xfe; 13 const uint8_t kHasAllocatedBufferLength = 0xff; 14 15 } // namespace 16 17 CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize) 18 : m_pHashTable(NULL), 19 m_nHashTableSize(17), 20 m_nCount(0), 21 m_pFreeList(NULL), 22 m_pBlocks(NULL), 23 m_nBlockSize(nBlockSize) { 24 ASSERT(m_nBlockSize > 0); 25 } 26 void CFX_MapPtrToPtr::RemoveAll() { 27 FX_Free(m_pHashTable); 28 m_pHashTable = NULL; 29 m_nCount = 0; 30 m_pFreeList = NULL; 31 m_pBlocks->FreeDataChain(); 32 m_pBlocks = NULL; 33 } 34 CFX_MapPtrToPtr::~CFX_MapPtrToPtr() { 35 RemoveAll(); 36 ASSERT(m_nCount == 0); 37 } 38 FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const { 39 return ((FX_DWORD)(uintptr_t)key) >> 4; 40 } 41 void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition, 42 void*& rKey, 43 void*& rValue) const { 44 ASSERT(m_pHashTable); 45 CAssoc* pAssocRet = (CAssoc*)rNextPosition; 46 ASSERT(pAssocRet); 47 if (pAssocRet == (CAssoc*)-1) { 48 for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) { 49 if ((pAssocRet = m_pHashTable[nBucket]) != NULL) 50 break; 51 } 52 ASSERT(pAssocRet); 53 } 54 CAssoc* pAssocNext; 55 if ((pAssocNext = pAssocRet->pNext) == NULL) { 56 for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1; 57 nBucket < m_nHashTableSize; nBucket++) { 58 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { 59 break; 60 } 61 } 62 } 63 rNextPosition = (FX_POSITION)pAssocNext; 64 rKey = pAssocRet->key; 65 rValue = pAssocRet->value; 66 } 67 FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const { 68 FX_DWORD nHash; 69 CAssoc* pAssoc = GetAssocAt(key, nHash); 70 if (!pAssoc) { 71 return FALSE; 72 } 73 rValue = pAssoc->value; 74 return TRUE; 75 } 76 void* CFX_MapPtrToPtr::GetValueAt(void* key) const { 77 FX_DWORD nHash; 78 CAssoc* pAssoc = GetAssocAt(key, nHash); 79 if (!pAssoc) { 80 return NULL; 81 } 82 return pAssoc->value; 83 } 84 void*& CFX_MapPtrToPtr::operator[](void* key) { 85 FX_DWORD nHash; 86 CAssoc* pAssoc; 87 if ((pAssoc = GetAssocAt(key, nHash)) == NULL) { 88 if (!m_pHashTable) { 89 InitHashTable(m_nHashTableSize); 90 } 91 pAssoc = NewAssoc(); 92 pAssoc->key = key; 93 pAssoc->pNext = m_pHashTable[nHash]; 94 m_pHashTable[nHash] = pAssoc; 95 } 96 return pAssoc->value; 97 } 98 CFX_MapPtrToPtr::CAssoc* CFX_MapPtrToPtr::GetAssocAt(void* key, 99 FX_DWORD& nHash) const { 100 nHash = HashKey(key) % m_nHashTableSize; 101 if (!m_pHashTable) { 102 return NULL; 103 } 104 CAssoc* pAssoc; 105 for (pAssoc = m_pHashTable[nHash]; pAssoc; pAssoc = pAssoc->pNext) { 106 if (pAssoc->key == key) 107 return pAssoc; 108 } 109 return NULL; 110 } 111 CFX_MapPtrToPtr::CAssoc* CFX_MapPtrToPtr::NewAssoc() { 112 if (!m_pFreeList) { 113 CFX_Plex* newBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize, 114 sizeof(CFX_MapPtrToPtr::CAssoc)); 115 CFX_MapPtrToPtr::CAssoc* pAssoc = 116 (CFX_MapPtrToPtr::CAssoc*)newBlock->data(); 117 pAssoc += m_nBlockSize - 1; 118 for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) { 119 pAssoc->pNext = m_pFreeList; 120 m_pFreeList = pAssoc; 121 } 122 } 123 CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList; 124 m_pFreeList = m_pFreeList->pNext; 125 m_nCount++; 126 ASSERT(m_nCount > 0); 127 pAssoc->key = 0; 128 pAssoc->value = 0; 129 return pAssoc; 130 } 131 void CFX_MapPtrToPtr::InitHashTable(FX_DWORD nHashSize, FX_BOOL bAllocNow) { 132 ASSERT(m_nCount == 0); 133 ASSERT(nHashSize > 0); 134 FX_Free(m_pHashTable); 135 m_pHashTable = NULL; 136 if (bAllocNow) { 137 m_pHashTable = FX_Alloc(CAssoc*, nHashSize); 138 } 139 m_nHashTableSize = nHashSize; 140 } 141 FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key) { 142 if (!m_pHashTable) { 143 return FALSE; 144 } 145 CAssoc** ppAssocPrev; 146 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; 147 CAssoc* pAssoc; 148 for (pAssoc = *ppAssocPrev; pAssoc; pAssoc = pAssoc->pNext) { 149 if (pAssoc->key == key) { 150 *ppAssocPrev = pAssoc->pNext; 151 FreeAssoc(pAssoc); 152 return TRUE; 153 } 154 ppAssocPrev = &pAssoc->pNext; 155 } 156 return FALSE; 157 } 158 void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) { 159 pAssoc->pNext = m_pFreeList; 160 m_pFreeList = pAssoc; 161 m_nCount--; 162 ASSERT(m_nCount >= 0); 163 if (m_nCount == 0) { 164 RemoveAll(); 165 } 166 } 167 struct _CompactString { 168 uint8_t m_CompactLen; 169 uint8_t m_LenHigh; 170 uint8_t m_LenLow; 171 uint8_t m_Unused; 172 uint8_t* m_pBuffer; 173 }; 174 static void _CompactStringRelease(_CompactString* pCompact) { 175 if (pCompact->m_CompactLen == kHasAllocatedBufferLength) { 176 FX_Free(pCompact->m_pBuffer); 177 } 178 } 179 static FX_BOOL _CompactStringSame(_CompactString* pCompact, 180 const uint8_t* pStr, 181 int len) { 182 if (len < sizeof(_CompactString)) { 183 if (pCompact->m_CompactLen != len) { 184 return FALSE; 185 } 186 return FXSYS_memcmp(&pCompact->m_LenHigh, pStr, len) == 0; 187 } 188 if (pCompact->m_CompactLen != kHasAllocatedBufferLength || 189 pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) { 190 return FALSE; 191 } 192 return FXSYS_memcmp(pCompact->m_pBuffer, pStr, len) == 0; 193 } 194 static void _CompactStringStore(_CompactString* pCompact, 195 const uint8_t* pStr, 196 int len) { 197 if (len < (int)sizeof(_CompactString)) { 198 pCompact->m_CompactLen = (uint8_t)len; 199 FXSYS_memcpy(&pCompact->m_LenHigh, pStr, len); 200 return; 201 } 202 pCompact->m_CompactLen = kHasAllocatedBufferLength; 203 pCompact->m_LenHigh = len / 256; 204 pCompact->m_LenLow = len % 256; 205 pCompact->m_pBuffer = FX_Alloc(uint8_t, len); 206 FXSYS_memcpy(pCompact->m_pBuffer, pStr, len); 207 } 208 static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact) { 209 if (pCompact->m_CompactLen == kHasAllocatedBufferLength) { 210 return CFX_ByteStringC(pCompact->m_pBuffer, 211 pCompact->m_LenHigh * 256 + pCompact->m_LenLow); 212 } 213 if (pCompact->m_CompactLen == kFreeLength) { 214 return CFX_ByteStringC(); 215 } 216 return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen); 217 } 218 #define CMAP_ALLOC_STEP 8 219 #define CMAP_INDEX_SIZE 8 220 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr() 221 : m_Buffer(sizeof(_CompactString) + sizeof(void*), 222 CMAP_ALLOC_STEP, 223 CMAP_INDEX_SIZE) {} 224 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr() { 225 RemoveAll(); 226 } 227 void CFX_CMapByteStringToPtr::RemoveAll() { 228 int size = m_Buffer.GetSize(); 229 for (int i = 0; i < size; i++) { 230 _CompactStringRelease((_CompactString*)m_Buffer.GetAt(i)); 231 } 232 m_Buffer.RemoveAll(); 233 } 234 FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const { 235 int size = m_Buffer.GetSize(); 236 for (int i = 0; i < size; i++) { 237 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i); 238 if (pKey->m_CompactLen != kFreeLength) { 239 return (FX_POSITION)(uintptr_t)(i + 1); 240 } 241 } 242 return NULL; 243 } 244 void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, 245 CFX_ByteString& rKey, 246 void*& rValue) const { 247 if (!rNextPosition) { 248 return; 249 } 250 int index = (int)(uintptr_t)rNextPosition - 1; 251 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 252 rKey = _CompactStringGet(pKey); 253 rValue = *(void**)(pKey + 1); 254 index++; 255 int size = m_Buffer.GetSize(); 256 while (index < size) { 257 pKey = (_CompactString*)m_Buffer.GetAt(index); 258 if (pKey->m_CompactLen != kFreeLength) { 259 rNextPosition = (FX_POSITION)(uintptr_t)(index + 1); 260 return; 261 } 262 index++; 263 } 264 rNextPosition = NULL; 265 } 266 void* CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const { 267 if (!rNextPosition) { 268 return NULL; 269 } 270 int index = (int)(uintptr_t)rNextPosition - 1; 271 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 272 void* rValue = *(void**)(pKey + 1); 273 index++; 274 int size = m_Buffer.GetSize(); 275 while (index < size) { 276 pKey = (_CompactString*)m_Buffer.GetAt(index); 277 if (pKey->m_CompactLen != kFreeLength) { 278 rNextPosition = (FX_POSITION)(uintptr_t)(index + 1); 279 return rValue; 280 } 281 index++; 282 } 283 rNextPosition = NULL; 284 return rValue; 285 } 286 FX_BOOL _CMapLookupCallback(void* param, void* pData) { 287 return !_CompactStringSame((_CompactString*)pData, 288 ((CFX_ByteStringC*)param)->GetPtr(), 289 ((CFX_ByteStringC*)param)->GetLength()); 290 } 291 FX_BOOL CFX_CMapByteStringToPtr::Lookup(const CFX_ByteStringC& key, 292 void*& rValue) const { 293 void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key); 294 if (!p) { 295 return FALSE; 296 } 297 rValue = *(void**)((_CompactString*)p + 1); 298 return TRUE; 299 } 300 void CFX_CMapByteStringToPtr::SetAt(const CFX_ByteStringC& key, void* value) { 301 ASSERT(value); 302 int key_len = key.GetLength(); 303 int size = m_Buffer.GetSize(); 304 for (int index = 0; index < size; index++) { 305 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 306 if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) { 307 continue; 308 } 309 *(void**)(pKey + 1) = value; 310 return; 311 } 312 for (int index = 0; index < size; index++) { 313 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 314 if (pKey->m_CompactLen != kFreeLength) { 315 continue; 316 } 317 _CompactStringStore(pKey, key.GetPtr(), key_len); 318 *(void**)(pKey + 1) = value; 319 return; 320 } 321 _CompactString* pKey = (_CompactString*)m_Buffer.Add(); 322 _CompactStringStore(pKey, key.GetPtr(), key_len); 323 *(void**)(pKey + 1) = value; 324 } 325 void CFX_CMapByteStringToPtr::AddValue(const CFX_ByteStringC& key, 326 void* value) { 327 ASSERT(value); 328 _CompactString* pKey = (_CompactString*)m_Buffer.Add(); 329 _CompactStringStore(pKey, key.GetPtr(), key.GetLength()); 330 *(void**)(pKey + 1) = value; 331 } 332 void CFX_CMapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) { 333 int key_len = key.GetLength(); 334 int size = m_Buffer.GetSize(); 335 for (int index = 0; index < size; index++) { 336 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 337 if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) { 338 continue; 339 } 340 _CompactStringRelease(pKey); 341 pKey->m_CompactLen = kFreeLength; 342 return; 343 } 344 } 345 int CFX_CMapByteStringToPtr::GetCount() const { 346 int count = 0; 347 int size = m_Buffer.GetSize(); 348 for (int i = 0; i < size; i++) { 349 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i); 350 if (pKey->m_CompactLen != kFreeLength) { 351 count++; 352 } 353 } 354 return count; 355 } 356
