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