BUG=379656
[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, 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 }
28 void 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 }
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)(FX_UINTPTR)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_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 }
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_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 }
159 FX_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 }
177 void 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 }
187 CFX_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 }
198 void 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 }
216 CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr()
217 {
218     RemoveAll();
219     ASSERT(m_nCount == 0);
220 }
221 void 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 }
246 FX_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 }
269 void*& 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 }
285 CFX_MapByteStringToPtr::CAssoc*
286 CFX_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 }
306 void 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 }
317 CFX_MapByteStringToPtr::CAssoc*
318 CFX_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 }
332 FX_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 }
342 void 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 }
359 inline 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 }
369 FX_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 }
387 struct _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 };
394 static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact)
395 {
396     if (pCompact->m_CompactLen == 0xff) {
397         FX_Allocator_Free(pAllocator, pCompact->m_pBuffer);
398     }
399 }
400 static 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 }
413 static 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 }
428 static 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
440 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr(IFX_Allocator* pAllocator)
441     : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator)
442 {
443 }
444 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()
445 {
446     RemoveAll();
447 }
448 void 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 }
457 FX_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 }
468 void 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 }
489 FX_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 }
510 FX_BOOL _CMapLookupCallback(void* param, void* pData)
511 {
512     return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength());
513 }
514 FX_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 }
523 void 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 }
550 void 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 }
557 void 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 }
572 int 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 }
584 extern "C" {
585     static int _CompareDWord(const void* p1, const void* p2)
586     {
587         return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);
588     }
589 };
590 struct _DWordPair {
591     FX_DWORD key;
592     FX_DWORD value;
593 };
594 FX_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 }
604 FX_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 }
612 void 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 }
628 void 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 }
651 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by)
652 {
653     m_Buffer.EstimateSize(size, grow_by);
654 }