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