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