| OLD | NEW |
| 1 // Copyright 2014 PDFium Authors. All rights reserved. | 1 // Copyright 2014 PDFium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com | 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com |
| 6 | 6 |
| 7 #include "../../include/fxcrt/fx_basic.h" | 7 #include "../../include/fxcrt/fx_basic.h" |
| 8 #include "plex.h" | 8 #include "plex.h" |
| 9 | 9 |
| 10 static void ConstructElement(CFX_ByteString* pNewData) | 10 static void ConstructElement(CFX_ByteString* pNewData) |
| (...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 62 for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1
; nBucket < m_nHashTableSize; nBucket ++) { | 62 for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1
; nBucket < m_nHashTableSize; nBucket ++) { |
| 63 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { | 63 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { |
| 64 break; | 64 break; |
| 65 } | 65 } |
| 66 } | 66 } |
| 67 } | 67 } |
| 68 rNextPosition = (FX_POSITION) pAssocNext; | 68 rNextPosition = (FX_POSITION) pAssocNext; |
| 69 rKey = pAssocRet->key; | 69 rKey = pAssocRet->key; |
| 70 rValue = pAssocRet->value; | 70 rValue = pAssocRet->value; |
| 71 } | 71 } |
| 72 FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const | 72 bool CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const |
| 73 { | 73 { |
| 74 FX_DWORD nHash; | 74 FX_DWORD nHash; |
| 75 CAssoc* pAssoc = GetAssocAt(key, nHash); | 75 CAssoc* pAssoc = GetAssocAt(key, nHash); |
| 76 if (pAssoc == NULL) { | 76 if (pAssoc == NULL) { |
| 77 return FALSE; | 77 return false; |
| 78 } | 78 } |
| 79 rValue = pAssoc->value; | 79 rValue = pAssoc->value; |
| 80 return TRUE; | 80 return true; |
| 81 } | 81 } |
| 82 void* CFX_MapPtrToPtr::GetValueAt(void* key) const | 82 void* CFX_MapPtrToPtr::GetValueAt(void* key) const |
| 83 { | 83 { |
| 84 FX_DWORD nHash; | 84 FX_DWORD nHash; |
| 85 CAssoc* pAssoc = GetAssocAt(key, nHash); | 85 CAssoc* pAssoc = GetAssocAt(key, nHash); |
| 86 if (pAssoc == NULL) { | 86 if (pAssoc == NULL) { |
| 87 return NULL; | 87 return NULL; |
| 88 } | 88 } |
| 89 return pAssoc->value; | 89 return pAssoc->value; |
| 90 } | 90 } |
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 133 ASSERT(m_pFreeList != NULL); | 133 ASSERT(m_pFreeList != NULL); |
| 134 CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList; | 134 CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList; |
| 135 m_pFreeList = m_pFreeList->pNext; | 135 m_pFreeList = m_pFreeList->pNext; |
| 136 m_nCount++; | 136 m_nCount++; |
| 137 ASSERT(m_nCount > 0); | 137 ASSERT(m_nCount > 0); |
| 138 pAssoc->key = 0; | 138 pAssoc->key = 0; |
| 139 pAssoc->value = 0; | 139 pAssoc->value = 0; |
| 140 return pAssoc; | 140 return pAssoc; |
| 141 } | 141 } |
| 142 void CFX_MapPtrToPtr::InitHashTable( | 142 void CFX_MapPtrToPtr::InitHashTable( |
| 143 FX_DWORD nHashSize, FX_BOOL bAllocNow) | 143 FX_DWORD nHashSize, bool bAllocNow) |
| 144 { | 144 { |
| 145 ASSERT(m_nCount == 0); | 145 ASSERT(m_nCount == 0); |
| 146 ASSERT(nHashSize > 0); | 146 ASSERT(nHashSize > 0); |
| 147 if (m_pHashTable != NULL) { | 147 if (m_pHashTable != NULL) { |
| 148 FX_Free(m_pHashTable); | 148 FX_Free(m_pHashTable); |
| 149 m_pHashTable = NULL; | 149 m_pHashTable = NULL; |
| 150 } | 150 } |
| 151 if (bAllocNow) { | 151 if (bAllocNow) { |
| 152 m_pHashTable = FX_Alloc(CAssoc*, nHashSize); | 152 m_pHashTable = FX_Alloc(CAssoc*, nHashSize); |
| 153 } | 153 } |
| 154 m_nHashTableSize = nHashSize; | 154 m_nHashTableSize = nHashSize; |
| 155 } | 155 } |
| 156 FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key) | 156 bool CFX_MapPtrToPtr::RemoveKey(void* key) |
| 157 { | 157 { |
| 158 if (m_pHashTable == NULL) { | 158 if (m_pHashTable == NULL) { |
| 159 return FALSE; | 159 return false; |
| 160 } | 160 } |
| 161 CAssoc** ppAssocPrev; | 161 CAssoc** ppAssocPrev; |
| 162 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; | 162 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; |
| 163 CAssoc* pAssoc; | 163 CAssoc* pAssoc; |
| 164 for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { | 164 for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| 165 if (pAssoc->key == key) { | 165 if (pAssoc->key == key) { |
| 166 *ppAssocPrev = pAssoc->pNext; | 166 *ppAssocPrev = pAssoc->pNext; |
| 167 FreeAssoc(pAssoc); | 167 FreeAssoc(pAssoc); |
| 168 return TRUE; | 168 return true; |
| 169 } | 169 } |
| 170 ppAssocPrev = &pAssoc->pNext; | 170 ppAssocPrev = &pAssoc->pNext; |
| 171 } | 171 } |
| 172 return FALSE; | 172 return false; |
| 173 } | 173 } |
| 174 void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) | 174 void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) |
| 175 { | 175 { |
| 176 pAssoc->pNext = m_pFreeList; | 176 pAssoc->pNext = m_pFreeList; |
| 177 m_pFreeList = pAssoc; | 177 m_pFreeList = pAssoc; |
| 178 m_nCount--; | 178 m_nCount--; |
| 179 ASSERT(m_nCount >= 0); | 179 ASSERT(m_nCount >= 0); |
| 180 if (m_nCount == 0) { | 180 if (m_nCount == 0) { |
| 181 RemoveAll(); | 181 RemoveAll(); |
| 182 } | 182 } |
| (...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 318 return NULL; | 318 return NULL; |
| 319 } | 319 } |
| 320 CAssoc* pAssoc; | 320 CAssoc* pAssoc; |
| 321 for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { | 321 for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| 322 if (pAssoc->key == key) { | 322 if (pAssoc->key == key) { |
| 323 return pAssoc; | 323 return pAssoc; |
| 324 } | 324 } |
| 325 } | 325 } |
| 326 return NULL; | 326 return NULL; |
| 327 } | 327 } |
| 328 FX_BOOL CFX_MapByteStringToPtr::Lookup(const CFX_ByteStringC& key, void*& rValue
) const | 328 bool CFX_MapByteStringToPtr::Lookup(const CFX_ByteStringC& key, void*& rValue) c
onst |
| 329 { | 329 { |
| 330 FX_DWORD nHash; | 330 FX_DWORD nHash; |
| 331 CAssoc* pAssoc = GetAssocAt(key, nHash); | 331 CAssoc* pAssoc = GetAssocAt(key, nHash); |
| 332 if (pAssoc == NULL) { | 332 if (pAssoc == NULL) { |
| 333 return FALSE; | 333 return false; |
| 334 } | 334 } |
| 335 rValue = pAssoc->value; | 335 rValue = pAssoc->value; |
| 336 return TRUE; | 336 return true; |
| 337 } | 337 } |
| 338 void CFX_MapByteStringToPtr::InitHashTable( | 338 void CFX_MapByteStringToPtr::InitHashTable( |
| 339 FX_DWORD nHashSize, FX_BOOL bAllocNow) | 339 FX_DWORD nHashSize, bool bAllocNow) |
| 340 { | 340 { |
| 341 ASSERT(m_nCount == 0); | 341 ASSERT(m_nCount == 0); |
| 342 ASSERT(nHashSize > 0); | 342 ASSERT(nHashSize > 0); |
| 343 if (m_pHashTable != NULL) { | 343 if (m_pHashTable != NULL) { |
| 344 FX_Free(m_pHashTable); | 344 FX_Free(m_pHashTable); |
| 345 m_pHashTable = NULL; | 345 m_pHashTable = NULL; |
| 346 } | 346 } |
| 347 if (bAllocNow) { | 347 if (bAllocNow) { |
| 348 m_pHashTable = FX_Alloc(CAssoc*, nHashSize); | 348 m_pHashTable = FX_Alloc(CAssoc*, nHashSize); |
| 349 } | 349 } |
| 350 m_nHashTableSize = nHashSize; | 350 m_nHashTableSize = nHashSize; |
| 351 } | 351 } |
| 352 inline FX_DWORD CFX_MapByteStringToPtr::HashKey(const CFX_ByteStringC& key) cons
t | 352 inline FX_DWORD CFX_MapByteStringToPtr::HashKey(const CFX_ByteStringC& key) cons
t |
| 353 { | 353 { |
| 354 FX_DWORD nHash = 0; | 354 FX_DWORD nHash = 0; |
| 355 int len = key.GetLength(); | 355 int len = key.GetLength(); |
| 356 const uint8_t* buf = key.GetPtr(); | 356 const uint8_t* buf = key.GetPtr(); |
| 357 for (int i = 0; i < len; i ++) { | 357 for (int i = 0; i < len; i ++) { |
| 358 nHash = (nHash << 5) + nHash + buf[i]; | 358 nHash = (nHash << 5) + nHash + buf[i]; |
| 359 } | 359 } |
| 360 return nHash; | 360 return nHash; |
| 361 } | 361 } |
| 362 FX_BOOL CFX_MapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) | 362 bool CFX_MapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) |
| 363 { | 363 { |
| 364 if (m_pHashTable == NULL) { | 364 if (m_pHashTable == NULL) { |
| 365 return FALSE; | 365 return false; |
| 366 } | 366 } |
| 367 CAssoc** ppAssocPrev; | 367 CAssoc** ppAssocPrev; |
| 368 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; | 368 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; |
| 369 CAssoc* pAssoc; | 369 CAssoc* pAssoc; |
| 370 for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { | 370 for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { |
| 371 if (pAssoc->key == key) { | 371 if (pAssoc->key == key) { |
| 372 *ppAssocPrev = pAssoc->pNext; | 372 *ppAssocPrev = pAssoc->pNext; |
| 373 FreeAssoc(pAssoc); | 373 FreeAssoc(pAssoc); |
| 374 return TRUE; | 374 return true; |
| 375 } | 375 } |
| 376 ppAssocPrev = &pAssoc->pNext; | 376 ppAssocPrev = &pAssoc->pNext; |
| 377 } | 377 } |
| 378 return FALSE; | 378 return false; |
| 379 } | 379 } |
| 380 struct _CompactString { | 380 struct _CompactString { |
| 381 uint8_t m_CompactLen; | 381 uint8_t m_CompactLen; |
| 382 uint8_t m_LenHigh; | 382 uint8_t m_LenHigh; |
| 383 uint8_t m_LenLow; | 383 uint8_t m_LenLow; |
| 384 uint8_t m_Unused; | 384 uint8_t m_Unused; |
| 385 uint8_t* m_pBuffer; | 385 uint8_t* m_pBuffer; |
| 386 }; | 386 }; |
| 387 static void _CompactStringRelease(_CompactString* pCompact) | 387 static void _CompactStringRelease(_CompactString* pCompact) |
| 388 { | 388 { |
| 389 if (pCompact->m_CompactLen == 0xff) { | 389 if (pCompact->m_CompactLen == 0xff) { |
| 390 FX_Free(pCompact->m_pBuffer); | 390 FX_Free(pCompact->m_pBuffer); |
| 391 } | 391 } |
| 392 } | 392 } |
| 393 static FX_BOOL _CompactStringSame(_CompactString* pCompact, const uint8_t* pStr,
int len) | 393 static bool _CompactStringSame(_CompactString* pCompact, const uint8_t* pStr, in
t len) |
| 394 { | 394 { |
| 395 if (len < sizeof(_CompactString)) { | 395 if (len < sizeof(_CompactString)) { |
| 396 if (pCompact->m_CompactLen != len) { | 396 if (pCompact->m_CompactLen != len) { |
| 397 return FALSE; | 397 return false; |
| 398 } | 398 } |
| 399 return FXSYS_memcmp(&pCompact->m_LenHigh, pStr, len) == 0; | 399 return FXSYS_memcmp(&pCompact->m_LenHigh, pStr, len) == 0; |
| 400 } | 400 } |
| 401 if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->
m_LenLow != len) { | 401 if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->
m_LenLow != len) { |
| 402 return FALSE; | 402 return false; |
| 403 } | 403 } |
| 404 return FXSYS_memcmp(pCompact->m_pBuffer, pStr, len) == 0; | 404 return FXSYS_memcmp(pCompact->m_pBuffer, pStr, len) == 0; |
| 405 } | 405 } |
| 406 static void _CompactStringStore(_CompactString* pCompact, const uint8_t* pStr, i
nt len) | 406 static void _CompactStringStore(_CompactString* pCompact, const uint8_t* pStr, i
nt len) |
| 407 { | 407 { |
| 408 if (len < (int)sizeof(_CompactString)) { | 408 if (len < (int)sizeof(_CompactString)) { |
| 409 pCompact->m_CompactLen = (uint8_t)len; | 409 pCompact->m_CompactLen = (uint8_t)len; |
| 410 FXSYS_memcpy(&pCompact->m_LenHigh, pStr, len); | 410 FXSYS_memcpy(&pCompact->m_LenHigh, pStr, len); |
| 411 return; | 411 return; |
| 412 } | 412 } |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 490 pKey = (_CompactString*)m_Buffer.GetAt(index); | 490 pKey = (_CompactString*)m_Buffer.GetAt(index); |
| 491 if (pKey->m_CompactLen != 0xfe) { | 491 if (pKey->m_CompactLen != 0xfe) { |
| 492 rNextPosition = (FX_POSITION)(uintptr_t)(index + 1); | 492 rNextPosition = (FX_POSITION)(uintptr_t)(index + 1); |
| 493 return rValue; | 493 return rValue; |
| 494 } | 494 } |
| 495 index ++; | 495 index ++; |
| 496 } | 496 } |
| 497 rNextPosition = NULL; | 497 rNextPosition = NULL; |
| 498 return rValue; | 498 return rValue; |
| 499 } | 499 } |
| 500 FX_BOOL _CMapLookupCallback(void* param, void* pData) | 500 bool _CMapLookupCallback(void* param, void* pData) |
| 501 { | 501 { |
| 502 return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)
->GetPtr(), ((CFX_ByteStringC*)param)->GetLength()); | 502 return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)
->GetPtr(), ((CFX_ByteStringC*)param)->GetLength()); |
| 503 } | 503 } |
| 504 FX_BOOL CFX_CMapByteStringToPtr::Lookup(const CFX_ByteStringC& key, void*& rValu
e) const | 504 bool CFX_CMapByteStringToPtr::Lookup(const CFX_ByteStringC& key, void*& rValue)
const |
| 505 { | 505 { |
| 506 void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key); | 506 void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key); |
| 507 if (!p) { | 507 if (!p) { |
| 508 return FALSE; | 508 return false; |
| 509 } | 509 } |
| 510 rValue = *(void**)((_CompactString*)p + 1); | 510 rValue = *(void**)((_CompactString*)p + 1); |
| 511 return TRUE; | 511 return true; |
| 512 } | 512 } |
| 513 void CFX_CMapByteStringToPtr::SetAt(const CFX_ByteStringC& key, void* value) | 513 void CFX_CMapByteStringToPtr::SetAt(const CFX_ByteStringC& key, void* value) |
| 514 { | 514 { |
| 515 ASSERT(value != NULL); | 515 ASSERT(value != NULL); |
| 516 int index, key_len = key.GetLength(); | 516 int index, key_len = key.GetLength(); |
| 517 int size = m_Buffer.GetSize(); | 517 int size = m_Buffer.GetSize(); |
| 518 for (index = 0; index < size; index ++) { | 518 for (index = 0; index < size; index ++) { |
| 519 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); | 519 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); |
| 520 if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) { | 520 if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) { |
| 521 continue; | 521 continue; |
| (...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 572 extern "C" { | 572 extern "C" { |
| 573 static int _CompareDWord(const void* p1, const void* p2) | 573 static int _CompareDWord(const void* p1, const void* p2) |
| 574 { | 574 { |
| 575 return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2); | 575 return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2); |
| 576 } | 576 } |
| 577 }; | 577 }; |
| 578 struct _DWordPair { | 578 struct _DWordPair { |
| 579 FX_DWORD key; | 579 FX_DWORD key; |
| 580 FX_DWORD value; | 580 FX_DWORD value; |
| 581 }; | 581 }; |
| 582 FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const | 582 bool CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const |
| 583 { | 583 { |
| 584 void* pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize()
/ sizeof(_DWordPair), | 584 void* pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize()
/ sizeof(_DWordPair), |
| 585 sizeof(_DWordPair), _CompareDWord); | 585 sizeof(_DWordPair), _CompareDWord); |
| 586 if (pResult == NULL) { | 586 if (pResult == NULL) { |
| 587 return FALSE; | 587 return false; |
| 588 } | 588 } |
| 589 value = ((FX_DWORD*)pResult)[1]; | 589 value = ((FX_DWORD*)pResult)[1]; |
| 590 return TRUE; | 590 return true; |
| 591 } | 591 } |
| 592 FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const | 592 FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const |
| 593 { | 593 { |
| 594 FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); | 594 FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); |
| 595 if (count == 0) { | 595 if (count == 0) { |
| 596 return NULL; | 596 return NULL; |
| 597 } | 597 } |
| 598 return (FX_POSITION)1; | 598 return (FX_POSITION)1; |
| 599 } | 599 } |
| 600 void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWOR
D& value) const | 600 void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWOR
D& value) const |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 633 buf[mid].value = value; | 633 buf[mid].value = value; |
| 634 return; | 634 return; |
| 635 } | 635 } |
| 636 } | 636 } |
| 637 m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair)); | 637 m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair)); |
| 638 } | 638 } |
| 639 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) | 639 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) |
| 640 { | 640 { |
| 641 m_Buffer.EstimateSize(size, grow_by); | 641 m_Buffer.EstimateSize(size, grow_by); |
| 642 } | 642 } |
| OLD | NEW |