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 "../../include/fxcrt/fx_ext.h" 8#include "plex.h" 9static void ConstructElement(CFX_ByteString* pNewData) 10{ 11 new (pNewData) CFX_ByteString(); 12} 13static void DestructElement(CFX_ByteString* pOldData) 14{ 15 pOldData->~CFX_ByteString(); 16} 17CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize, IFX_Allocator* pAllocator) 18 : m_pAllocator(pAllocator) 19 , m_pHashTable(NULL) 20 , m_nHashTableSize(17) 21 , m_nCount(0) 22 , m_pFreeList(NULL) 23 , m_pBlocks(NULL) 24 , m_nBlockSize(nBlockSize) 25{ 26 ASSERT(m_nBlockSize > 0); 27} 28void CFX_MapPtrToPtr::RemoveAll() 29{ 30 if (m_pHashTable) { 31 FX_Allocator_Free(m_pAllocator, m_pHashTable); 32 m_pHashTable = NULL; 33 } 34 m_nCount = 0; 35 m_pFreeList = NULL; 36 m_pBlocks->FreeDataChain(m_pAllocator); 37 m_pBlocks = NULL; 38} 39CFX_MapPtrToPtr::~CFX_MapPtrToPtr() 40{ 41 RemoveAll(); 42 ASSERT(m_nCount == 0); 43} 44FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const 45{ 46 return ((FX_DWORD)(FX_UINTPTR)key) >> 4; 47} 48void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition, void*& rKey, void*& rValue) const 49{ 50 ASSERT(m_pHashTable != NULL); 51 CAssoc* pAssocRet = (CAssoc*)rNextPosition; 52 ASSERT(pAssocRet != NULL); 53 if (pAssocRet == (CAssoc*) - 1) { 54 for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) 55 if ((pAssocRet = m_pHashTable[nBucket]) != NULL) { 56 break; 57 } 58 ASSERT(pAssocRet != NULL); 59 } 60 CAssoc* pAssocNext; 61 if ((pAssocNext = pAssocRet->pNext) == NULL) { 62 for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1; nBucket < m_nHashTableSize; nBucket ++) { 63 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { 64 break; 65 } 66 } 67 } 68 rNextPosition = (FX_POSITION) pAssocNext; 69 rKey = pAssocRet->key; 70 rValue = pAssocRet->value; 71} 72FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const 73{ 74 FX_DWORD nHash; 75 CAssoc* pAssoc = GetAssocAt(key, nHash); 76 if (pAssoc == NULL) { 77 return FALSE; 78 } 79 rValue = pAssoc->value; 80 return TRUE; 81} 82void* CFX_MapPtrToPtr::GetValueAt(void* key) const 83{ 84 FX_DWORD nHash; 85 CAssoc* pAssoc = GetAssocAt(key, nHash); 86 if (pAssoc == NULL) { 87 return NULL; 88 } 89 return pAssoc->value; 90} 91void*& CFX_MapPtrToPtr::operator[](void* key) 92{ 93 FX_DWORD nHash; 94 CAssoc* pAssoc; 95 if ((pAssoc = GetAssocAt(key, nHash)) == NULL) { 96 if (m_pHashTable == NULL) { 97 InitHashTable(m_nHashTableSize); 98 } 99 pAssoc = NewAssoc(); 100 pAssoc->key = key; 101 pAssoc->pNext = m_pHashTable[nHash]; 102 m_pHashTable[nHash] = pAssoc; 103 } 104 return pAssoc->value; 105} 106CFX_MapPtrToPtr::CAssoc* 107CFX_MapPtrToPtr::GetAssocAt(void* key, FX_DWORD& nHash) const 108{ 109 nHash = HashKey(key) % m_nHashTableSize; 110 if (m_pHashTable == NULL) { 111 return NULL; 112 } 113 CAssoc* pAssoc; 114 for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { 115 if (pAssoc->key == key) { 116 return pAssoc; 117 } 118 } 119 return NULL; 120} 121CFX_MapPtrToPtr::CAssoc* 122CFX_MapPtrToPtr::NewAssoc() 123{ 124 if (m_pFreeList == NULL) { 125 CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapPtrToPtr::CAssoc)); 126 CFX_MapPtrToPtr::CAssoc* pAssoc = (CFX_MapPtrToPtr::CAssoc*)newBlock->data(); 127 pAssoc += m_nBlockSize - 1; 128 for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) { 129 pAssoc->pNext = m_pFreeList; 130 m_pFreeList = pAssoc; 131 } 132 } 133 ASSERT(m_pFreeList != NULL); 134 CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList; 135 m_pFreeList = m_pFreeList->pNext; 136 m_nCount++; 137 ASSERT(m_nCount > 0); 138 pAssoc->key = 0; 139 pAssoc->value = 0; 140 return pAssoc; 141} 142void CFX_MapPtrToPtr::InitHashTable( 143 FX_DWORD nHashSize, FX_BOOL bAllocNow) 144{ 145 ASSERT(m_nCount == 0); 146 ASSERT(nHashSize > 0); 147 if (m_pHashTable != NULL) { 148 FX_Allocator_Free(m_pAllocator, m_pHashTable); 149 m_pHashTable = NULL; 150 } 151 if (bAllocNow) { 152 m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize); 153 if (m_pHashTable) { 154 FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize); 155 } 156 } 157 m_nHashTableSize = nHashSize; 158} 159FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key) 160{ 161 if (m_pHashTable == NULL) { 162 return FALSE; 163 } 164 CAssoc** ppAssocPrev; 165 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; 166 CAssoc* pAssoc; 167 for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { 168 if (pAssoc->key == key) { 169 *ppAssocPrev = pAssoc->pNext; 170 FreeAssoc(pAssoc); 171 return TRUE; 172 } 173 ppAssocPrev = &pAssoc->pNext; 174 } 175 return FALSE; 176} 177void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) 178{ 179 pAssoc->pNext = m_pFreeList; 180 m_pFreeList = pAssoc; 181 m_nCount--; 182 ASSERT(m_nCount >= 0); 183 if (m_nCount == 0) { 184 RemoveAll(); 185 } 186} 187CFX_MapByteStringToPtr::CFX_MapByteStringToPtr(int nBlockSize, IFX_Allocator* pAllocator) 188 : m_pAllocator(pAllocator) 189 , m_pHashTable(NULL) 190 , m_nHashTableSize(17) 191 , m_nCount(0) 192 , m_pFreeList(NULL) 193 , m_pBlocks(NULL) 194 , m_nBlockSize(nBlockSize) 195{ 196 ASSERT(m_nBlockSize > 0); 197} 198void CFX_MapByteStringToPtr::RemoveAll() 199{ 200 if (m_pHashTable != NULL) { 201 for (FX_DWORD nHash = 0; nHash < m_nHashTableSize; nHash++) { 202 CAssoc* pAssoc; 203 for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; 204 pAssoc = pAssoc->pNext) { 205 DestructElement(&pAssoc->key); 206 } 207 } 208 FX_Allocator_Free(m_pAllocator, m_pHashTable); 209 m_pHashTable = NULL; 210 } 211 m_nCount = 0; 212 m_pFreeList = NULL; 213 m_pBlocks->FreeDataChain(m_pAllocator); 214 m_pBlocks = NULL; 215} 216CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr() 217{ 218 RemoveAll(); 219 ASSERT(m_nCount == 0); 220} 221void CFX_MapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, 222 CFX_ByteString& rKey, void*& rValue) const 223{ 224 ASSERT(m_pHashTable != NULL); 225 CAssoc* pAssocRet = (CAssoc*)rNextPosition; 226 ASSERT(pAssocRet != NULL); 227 if (pAssocRet == (CAssoc*) - 1) { 228 for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) 229 if ((pAssocRet = m_pHashTable[nBucket]) != NULL) { 230 break; 231 } 232 ASSERT(pAssocRet != NULL); 233 } 234 CAssoc* pAssocNext; 235 if ((pAssocNext = pAssocRet->pNext) == NULL) { 236 for (FX_DWORD nBucket = pAssocRet->nHashValue + 1; 237 nBucket < m_nHashTableSize; nBucket++) 238 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { 239 break; 240 } 241 } 242 rNextPosition = (FX_POSITION) pAssocNext; 243 rKey = pAssocRet->key; 244 rValue = pAssocRet->value; 245} 246FX_LPVOID CFX_MapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const 247{ 248 ASSERT(m_pHashTable != NULL); 249 CAssoc* pAssocRet = (CAssoc*)rNextPosition; 250 ASSERT(pAssocRet != NULL); 251 if (pAssocRet == (CAssoc*) - 1) { 252 for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) 253 if ((pAssocRet = m_pHashTable[nBucket]) != NULL) { 254 break; 255 } 256 ASSERT(pAssocRet != NULL); 257 } 258 CAssoc* pAssocNext; 259 if ((pAssocNext = pAssocRet->pNext) == NULL) { 260 for (FX_DWORD nBucket = pAssocRet->nHashValue + 1; 261 nBucket < m_nHashTableSize; nBucket++) 262 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) { 263 break; 264 } 265 } 266 rNextPosition = (FX_POSITION) pAssocNext; 267 return pAssocRet->value; 268} 269void*& CFX_MapByteStringToPtr::operator[](FX_BSTR key) 270{ 271 FX_DWORD nHash; 272 CAssoc* pAssoc; 273 if ((pAssoc = GetAssocAt(key, nHash)) == NULL) { 274 if (m_pHashTable == NULL) { 275 InitHashTable(m_nHashTableSize); 276 } 277 pAssoc = NewAssoc(); 278 pAssoc->nHashValue = nHash; 279 pAssoc->key = key; 280 pAssoc->pNext = m_pHashTable[nHash]; 281 m_pHashTable[nHash] = pAssoc; 282 } 283 return pAssoc->value; 284} 285CFX_MapByteStringToPtr::CAssoc* 286CFX_MapByteStringToPtr::NewAssoc() 287{ 288 if (m_pFreeList == NULL) { 289 CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapByteStringToPtr::CAssoc)); 290 CFX_MapByteStringToPtr::CAssoc* pAssoc = (CFX_MapByteStringToPtr::CAssoc*)newBlock->data(); 291 pAssoc += m_nBlockSize - 1; 292 for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) { 293 pAssoc->pNext = m_pFreeList; 294 m_pFreeList = pAssoc; 295 } 296 } 297 ASSERT(m_pFreeList != NULL); 298 CFX_MapByteStringToPtr::CAssoc* pAssoc = m_pFreeList; 299 m_pFreeList = m_pFreeList->pNext; 300 m_nCount++; 301 ASSERT(m_nCount > 0); 302 ConstructElement(&pAssoc->key); 303 pAssoc->value = 0; 304 return pAssoc; 305} 306void CFX_MapByteStringToPtr::FreeAssoc(CFX_MapByteStringToPtr::CAssoc* pAssoc) 307{ 308 DestructElement(&pAssoc->key); 309 pAssoc->pNext = m_pFreeList; 310 m_pFreeList = pAssoc; 311 m_nCount--; 312 ASSERT(m_nCount >= 0); 313 if (m_nCount == 0) { 314 RemoveAll(); 315 } 316} 317CFX_MapByteStringToPtr::CAssoc* 318CFX_MapByteStringToPtr::GetAssocAt(FX_BSTR key, FX_DWORD& nHash) const 319{ 320 nHash = HashKey(key) % m_nHashTableSize; 321 if (m_pHashTable == NULL) { 322 return NULL; 323 } 324 CAssoc* pAssoc; 325 for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { 326 if (pAssoc->key == key) { 327 return pAssoc; 328 } 329 } 330 return NULL; 331} 332FX_BOOL CFX_MapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const 333{ 334 FX_DWORD nHash; 335 CAssoc* pAssoc = GetAssocAt(key, nHash); 336 if (pAssoc == NULL) { 337 return FALSE; 338 } 339 rValue = pAssoc->value; 340 return TRUE; 341} 342void CFX_MapByteStringToPtr::InitHashTable( 343 FX_DWORD nHashSize, FX_BOOL bAllocNow) 344{ 345 ASSERT(m_nCount == 0); 346 ASSERT(nHashSize > 0); 347 if (m_pHashTable != NULL) { 348 FX_Allocator_Free(m_pAllocator, m_pHashTable); 349 m_pHashTable = NULL; 350 } 351 if (bAllocNow) { 352 m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize); 353 if (m_pHashTable) { 354 FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize); 355 } 356 } 357 m_nHashTableSize = nHashSize; 358} 359inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const 360{ 361 FX_DWORD nHash = 0; 362 int len = key.GetLength(); 363 FX_LPCBYTE buf = key; 364 for (int i = 0; i < len; i ++) { 365 nHash = (nHash << 5) + nHash + buf[i]; 366 } 367 return nHash; 368} 369FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR key) 370{ 371 if (m_pHashTable == NULL) { 372 return FALSE; 373 } 374 CAssoc** ppAssocPrev; 375 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; 376 CAssoc* pAssoc; 377 for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) { 378 if (pAssoc->key == key) { 379 *ppAssocPrev = pAssoc->pNext; 380 FreeAssoc(pAssoc); 381 return TRUE; 382 } 383 ppAssocPrev = &pAssoc->pNext; 384 } 385 return FALSE; 386} 387struct _CompactString { 388 FX_BYTE m_CompactLen; 389 FX_BYTE m_LenHigh; 390 FX_BYTE m_LenLow; 391 FX_BYTE m_Unused; 392 FX_LPBYTE m_pBuffer; 393}; 394static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact) 395{ 396 if (pCompact->m_CompactLen == 0xff) { 397 FX_Allocator_Free(pAllocator, pCompact->m_pBuffer); 398 } 399} 400static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE pStr, int len) 401{ 402 if (len < sizeof(_CompactString)) { 403 if (pCompact->m_CompactLen != len) { 404 return FALSE; 405 } 406 return FXSYS_memcmp32(&pCompact->m_LenHigh, pStr, len) == 0; 407 } 408 if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) { 409 return FALSE; 410 } 411 return FXSYS_memcmp32(pCompact->m_pBuffer, pStr, len) == 0; 412} 413static void _CompactStringStore(IFX_Allocator* pAllocator, _CompactString* pCompact, FX_LPCBYTE pStr, int len) 414{ 415 if (len < (int)sizeof(_CompactString)) { 416 pCompact->m_CompactLen = (FX_BYTE)len; 417 FXSYS_memcpy32(&pCompact->m_LenHigh, pStr, len); 418 return; 419 } 420 pCompact->m_CompactLen = 0xff; 421 pCompact->m_LenHigh = len / 256; 422 pCompact->m_LenLow = len % 256; 423 pCompact->m_pBuffer = FX_Allocator_Alloc(pAllocator, FX_BYTE, len); 424 if (pCompact->m_pBuffer) { 425 FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len); 426 } 427} 428static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact) 429{ 430 if (pCompact->m_CompactLen == 0xff) { 431 return CFX_ByteStringC(pCompact->m_pBuffer, pCompact->m_LenHigh * 256 + pCompact->m_LenLow); 432 } 433 if (pCompact->m_CompactLen == 0xfe) { 434 return CFX_ByteStringC(); 435 } 436 return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen); 437} 438#define CMAP_ALLOC_STEP 8 439#define CMAP_INDEX_SIZE 8 440CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr(IFX_Allocator* pAllocator) 441 : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator) 442{ 443} 444CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr() 445{ 446 RemoveAll(); 447} 448void CFX_CMapByteStringToPtr::RemoveAll() 449{ 450 IFX_Allocator* pAllocator = m_Buffer.m_pAllocator; 451 int size = m_Buffer.GetSize(); 452 for (int i = 0; i < size; i ++) { 453 _CompactStringRelease(pAllocator, (_CompactString*)m_Buffer.GetAt(i)); 454 } 455 m_Buffer.RemoveAll(); 456} 457FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const 458{ 459 int size = m_Buffer.GetSize(); 460 for (int i = 0; i < size; i ++) { 461 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i); 462 if (pKey->m_CompactLen != 0xfe) { 463 return (FX_POSITION)(FX_UINTPTR)(i + 1); 464 } 465 } 466 return NULL; 467} 468void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const 469{ 470 if (rNextPosition == NULL) { 471 return; 472 } 473 int index = (int)(FX_UINTPTR)rNextPosition - 1; 474 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 475 rKey = _CompactStringGet(pKey); 476 rValue = *(void**)(pKey + 1); 477 index ++; 478 int size = m_Buffer.GetSize(); 479 while (index < size) { 480 pKey = (_CompactString*)m_Buffer.GetAt(index); 481 if (pKey->m_CompactLen != 0xfe) { 482 rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1); 483 return; 484 } 485 index ++; 486 } 487 rNextPosition = NULL; 488} 489FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const 490{ 491 if (rNextPosition == NULL) { 492 return NULL; 493 } 494 int index = (int)(FX_UINTPTR)rNextPosition - 1; 495 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 496 FX_LPVOID rValue = *(void**)(pKey + 1); 497 index ++; 498 int size = m_Buffer.GetSize(); 499 while (index < size) { 500 pKey = (_CompactString*)m_Buffer.GetAt(index); 501 if (pKey->m_CompactLen != 0xfe) { 502 rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1); 503 return rValue; 504 } 505 index ++; 506 } 507 rNextPosition = NULL; 508 return rValue; 509} 510FX_BOOL _CMapLookupCallback(void* param, void* pData) 511{ 512 return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength()); 513} 514FX_BOOL CFX_CMapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const 515{ 516 void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key); 517 if (!p) { 518 return FALSE; 519 } 520 rValue = *(void**)((_CompactString*)p + 1); 521 return TRUE; 522} 523void CFX_CMapByteStringToPtr::SetAt(FX_BSTR key, void* value) 524{ 525 ASSERT(value != NULL); 526 int index, key_len = key.GetLength(); 527 int size = m_Buffer.GetSize(); 528 for (index = 0; index < size; index ++) { 529 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 530 if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) { 531 continue; 532 } 533 *(void**)(pKey + 1) = value; 534 return; 535 } 536 IFX_Allocator* pAllocator = m_Buffer.m_pAllocator; 537 for (index = 0; index < size; index ++) { 538 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 539 if (pKey->m_CompactLen) { 540 continue; 541 } 542 _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len); 543 *(void**)(pKey + 1) = value; 544 return; 545 } 546 _CompactString* pKey = (_CompactString*)m_Buffer.Add(); 547 _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len); 548 *(void**)(pKey + 1) = value; 549} 550void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value) 551{ 552 ASSERT(value != NULL); 553 _CompactString* pKey = (_CompactString*)m_Buffer.Add(); 554 _CompactStringStore(m_Buffer.m_pAllocator, pKey, (FX_LPCBYTE)key, key.GetLength()); 555 *(void**)(pKey + 1) = value; 556} 557void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key) 558{ 559 int key_len = key.GetLength(); 560 IFX_Allocator* pAllocator = m_Buffer.m_pAllocator; 561 int size = m_Buffer.GetSize(); 562 for (int index = 0; index < size; index ++) { 563 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index); 564 if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) { 565 continue; 566 } 567 _CompactStringRelease(pAllocator, pKey); 568 pKey->m_CompactLen = 0xfe; 569 return; 570 } 571} 572int CFX_CMapByteStringToPtr::GetCount() const 573{ 574 int count = 0; 575 int size = m_Buffer.GetSize(); 576 for (int i = 0; i < size; i ++) { 577 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i); 578 if (pKey->m_CompactLen != 0xfe) { 579 count ++; 580 } 581 } 582 return count; 583} 584extern "C" { 585 static int _CompareDWord(const void* p1, const void* p2) 586 { 587 return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2); 588 } 589}; 590struct _DWordPair { 591 FX_DWORD key; 592 FX_DWORD value; 593}; 594FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const 595{ 596 FX_LPVOID pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize() / sizeof(_DWordPair), 597 sizeof(_DWordPair), _CompareDWord); 598 if (pResult == NULL) { 599 return FALSE; 600 } 601 value = ((FX_DWORD*)pResult)[1]; 602 return TRUE; 603} 604FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const 605{ 606 FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); 607 if (count == 0) { 608 return NULL; 609 } 610 return (FX_POSITION)1; 611} 612void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const 613{ 614 if (pos == 0) { 615 return; 616 } 617 FX_DWORD index = ((FX_DWORD)(FX_UINTPTR)pos) - 1; 618 FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); 619 _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); 620 key = buf[index].key; 621 value = buf[index].value; 622 if (index == count - 1) { 623 pos = 0; 624 } else { 625 pos = (FX_POSITION)((FX_UINTPTR)pos + 1); 626 } 627} 628void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value) 629{ 630 FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); 631 _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); 632 _DWordPair pair = {key, value}; 633 if (count == 0 || key > buf[count - 1].key) { 634 m_Buffer.AppendBlock(&pair, sizeof(_DWordPair)); 635 return; 636 } 637 int low = 0, high = count - 1; 638 while (low <= high) { 639 int mid = (low + high) / 2; 640 if (buf[mid].key < key) { 641 low = mid + 1; 642 } else if (buf[mid].key > key) { 643 high = mid - 1; 644 } else { 645 buf[mid].value = value; 646 return; 647 } 648 } 649 m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair)); 650} 651void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) 652{ 653 m_Buffer.EstimateSize(size, grow_by); 654} 655