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 |