Add FX_OVERRIDE and use it for virtual functions of FX_FINAL classes.
[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_ext.h"
8 #include "plex.h"
9 static void ConstructElement(CFX_ByteString* pNewData)
10 {
11     new (pNewData) CFX_ByteString();
12 }
13 static void DestructElement(CFX_ByteString* pOldData)
14 {
15     pOldData->~CFX_ByteString();
16 }
17 CFX_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 }
27 void 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 }
38 CFX_MapPtrToPtr::~CFX_MapPtrToPtr()
39 {
40     RemoveAll();
41     ASSERT(m_nCount == 0);
42 }
43 FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const
44 {
45     return ((FX_DWORD)(FX_UINTPTR)key) >> 4;
46 }
47 void 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 }
71 FX_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 }
81 void* 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 }
90 void*& 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 }
105 CFX_MapPtrToPtr::CAssoc*
106 CFX_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 }
120 CFX_MapPtrToPtr::CAssoc*
121 CFX_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 }
141 void 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 }
155 FX_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 }
173 void 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 }
183 CFX_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 }
193 void 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 }
211 CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr()
212 {
213     RemoveAll();
214     ASSERT(m_nCount == 0);
215 }
216 void 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 }
241 FX_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 }
264 void*& 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 }
280 CFX_MapByteStringToPtr::CAssoc*
281 CFX_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 }
301 void 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 }
312 CFX_MapByteStringToPtr::CAssoc*
313 CFX_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 }
327 FX_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 }
337 void 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 }
351 inline 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;
356     for (int i = 0; i < len; i ++) {
357         nHash = (nHash << 5) + nHash + buf[i];
358     }
359     return nHash;
360 }
361 FX_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 }
379 struct _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 };
386 static void _CompactStringRelease(_CompactString* pCompact)
387 {
388     if (pCompact->m_CompactLen == 0xff) {
389         FX_Free(pCompact->m_pBuffer);
390     }
391 }
392 static 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 }
405 static 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     if (pCompact->m_pBuffer) {
417         FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len);
418     }
419 }
420 static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact)
421 {
422     if (pCompact->m_CompactLen == 0xff) {
423         return CFX_ByteStringC(pCompact->m_pBuffer, pCompact->m_LenHigh * 256 + pCompact->m_LenLow);
424     }
425     if (pCompact->m_CompactLen == 0xfe) {
426         return CFX_ByteStringC();
427     }
428     return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen);
429 }
430 #define CMAP_ALLOC_STEP         8
431 #define CMAP_INDEX_SIZE         8
432 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr()
433     : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE)
434 {
435 }
436 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()
437 {
438     RemoveAll();
439 }
440 void CFX_CMapByteStringToPtr::RemoveAll()
441 {
442     int size = m_Buffer.GetSize();
443     for (int i = 0; i < size; i++) {
444         _CompactStringRelease((_CompactString*)m_Buffer.GetAt(i));
445     }
446     m_Buffer.RemoveAll();
447 }
448 FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const
449 {
450     int size = m_Buffer.GetSize();
451     for (int i = 0; i < size; i ++) {
452         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
453         if (pKey->m_CompactLen != 0xfe) {
454             return (FX_POSITION)(FX_UINTPTR)(i + 1);
455         }
456     }
457     return NULL;
458 }
459 void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const
460 {
461     if (rNextPosition == NULL) {
462         return;
463     }
464     int index = (int)(FX_UINTPTR)rNextPosition - 1;
465     _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
466     rKey = _CompactStringGet(pKey);
467     rValue = *(void**)(pKey + 1);
468     index ++;
469     int size = m_Buffer.GetSize();
470     while (index < size) {
471         pKey = (_CompactString*)m_Buffer.GetAt(index);
472         if (pKey->m_CompactLen != 0xfe) {
473             rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);
474             return;
475         }
476         index ++;
477     }
478     rNextPosition = NULL;
479 }
480 FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const
481 {
482     if (rNextPosition == NULL) {
483         return NULL;
484     }
485     int index = (int)(FX_UINTPTR)rNextPosition - 1;
486     _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
487     FX_LPVOID rValue = *(void**)(pKey + 1);
488     index ++;
489     int size = m_Buffer.GetSize();
490     while (index < size) {
491         pKey = (_CompactString*)m_Buffer.GetAt(index);
492         if (pKey->m_CompactLen != 0xfe) {
493             rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);
494             return rValue;
495         }
496         index ++;
497     }
498     rNextPosition = NULL;
499     return rValue;
500 }
501 FX_BOOL _CMapLookupCallback(void* param, void* pData)
502 {
503     return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength());
504 }
505 FX_BOOL CFX_CMapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const
506 {
507     void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key);
508     if (!p) {
509         return FALSE;
510     }
511     rValue = *(void**)((_CompactString*)p + 1);
512     return TRUE;
513 }
514 void CFX_CMapByteStringToPtr::SetAt(FX_BSTR key, void* value)
515 {
516     ASSERT(value != NULL);
517     int index, key_len = key.GetLength();
518     int size = m_Buffer.GetSize();
519     for (index = 0; index < size; index ++) {
520         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
521         if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {
522             continue;
523         }
524         *(void**)(pKey + 1) = value;
525         return;
526     }
527     for (index = 0; index < size; index ++) {
528         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
529         if (pKey->m_CompactLen) {
530             continue;
531         }
532         _CompactStringStore(pKey, (FX_LPCBYTE)key, key_len);
533         *(void**)(pKey + 1) = value;
534         return;
535     }
536     _CompactString* pKey = (_CompactString*)m_Buffer.Add();
537     _CompactStringStore(pKey, (FX_LPCBYTE)key, key_len);
538     *(void**)(pKey + 1) = value;
539 }
540 void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value)
541 {
542     ASSERT(value != NULL);
543     _CompactString* pKey = (_CompactString*)m_Buffer.Add();
544     _CompactStringStore(pKey, (FX_LPCBYTE)key, key.GetLength());
545     *(void**)(pKey + 1) = value;
546 }
547 void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key)
548 {
549     int key_len = key.GetLength();
550     int size = m_Buffer.GetSize();
551     for (int index = 0; index < size; index++) {
552         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
553         if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {
554             continue;
555         }
556         _CompactStringRelease(pKey);
557         pKey->m_CompactLen = 0xfe;
558         return;
559     }
560 }
561 int CFX_CMapByteStringToPtr::GetCount() const
562 {
563     int count = 0;
564     int size = m_Buffer.GetSize();
565     for (int i = 0; i < size; i ++) {
566         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
567         if (pKey->m_CompactLen != 0xfe) {
568             count ++;
569         }
570     }
571     return count;
572 }
573 extern "C" {
574     static int _CompareDWord(const void* p1, const void* p2)
575     {
576         return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);
577     }
578 };
579 struct _DWordPair {
580     FX_DWORD key;
581     FX_DWORD value;
582 };
583 FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const
584 {
585     FX_LPVOID pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize() / sizeof(_DWordPair),
586                                       sizeof(_DWordPair), _CompareDWord);
587     if (pResult == NULL) {
588         return FALSE;
589     }
590     value = ((FX_DWORD*)pResult)[1];
591     return TRUE;
592 }
593 FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const
594 {
595     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
596     if (count == 0) {
597         return NULL;
598     }
599     return (FX_POSITION)1;
600 }
601 void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const
602 {
603     if (pos == 0) {
604         return;
605     }
606     FX_DWORD index = ((FX_DWORD)(FX_UINTPTR)pos) - 1;
607     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
608     _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();
609     key = buf[index].key;
610     value = buf[index].value;
611     if (index == count - 1) {
612         pos = 0;
613     } else {
614         pos = (FX_POSITION)((FX_UINTPTR)pos + 1);
615     }
616 }
617 void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value)
618 {
619     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
620     _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();
621     _DWordPair pair = {key, value};
622     if (count == 0 || key > buf[count - 1].key) {
623         m_Buffer.AppendBlock(&pair, sizeof(_DWordPair));
624         return;
625     }
626     int low = 0, high = count - 1;
627     while (low <= high) {
628         int mid = (low + high) / 2;
629         if (buf[mid].key < key) {
630             low = mid + 1;
631         } else if (buf[mid].key > key) {
632             high = mid - 1;
633         } else {
634             buf[mid].value = value;
635             return;
636         }
637     }
638     m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair));
639 }
640 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by)
641 {
642     m_Buffer.EstimateSize(size, grow_by);
643 }