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