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