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