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"
ConstructElement(CFX_ByteString * pNewData)9 static void ConstructElement(CFX_ByteString* pNewData)
10 {
11     new (pNewData) CFX_ByteString();
12 }
DestructElement(CFX_ByteString * pOldData)13 static void DestructElement(CFX_ByteString* pOldData)
14 {
15     pOldData->~CFX_ByteString();
16 }
CFX_MapPtrToPtr(int nBlockSize)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 }
RemoveAll()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 }
~CFX_MapPtrToPtr()38 CFX_MapPtrToPtr::~CFX_MapPtrToPtr()
39 {
40     RemoveAll();
41     ASSERT(m_nCount == 0);
42 }
HashKey(void * key) const43 FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const
44 {
45     return ((FX_DWORD)(FX_UINTPTR)key) >> 4;
46 }
GetNextAssoc(FX_POSITION & rNextPosition,void * & rKey,void * & rValue) const47 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 }
Lookup(void * key,void * & rValue) const71 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 }
GetValueAt(void * key) const81 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 }
operator [](void * key)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*
GetAssocAt(void * key,FX_DWORD & nHash) const106 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*
NewAssoc()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 }
InitHashTable(FX_DWORD nHashSize,FX_BOOL bAllocNow)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 }
RemoveKey(void * key)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 }
FreeAssoc(CFX_MapPtrToPtr::CAssoc * pAssoc)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 }
CFX_MapByteStringToPtr(int nBlockSize)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 }
RemoveAll()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 }
~CFX_MapByteStringToPtr()211 CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr()
212 {
213     RemoveAll();
214     ASSERT(m_nCount == 0);
215 }
GetNextAssoc(FX_POSITION & rNextPosition,CFX_ByteString & rKey,void * & rValue) const216 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 }
GetNextValue(FX_POSITION & rNextPosition) const241 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 }
operator [](FX_BSTR key)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*
NewAssoc()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 }
FreeAssoc(CFX_MapByteStringToPtr::CAssoc * pAssoc)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*
GetAssocAt(FX_BSTR key,FX_DWORD & nHash) const313 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 }
Lookup(FX_BSTR key,void * & rValue) const327 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 }
InitHashTable(FX_DWORD nHashSize,FX_BOOL bAllocNow)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 }
HashKey(FX_BSTR key) const351 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.GetPtr();
356     for (int i = 0; i < len; i ++) {
357         nHash = (nHash << 5) + nHash + buf[i];
358     }
359     return nHash;
360 }
RemoveKey(FX_BSTR key)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 };
_CompactStringRelease(_CompactString * pCompact)386 static void _CompactStringRelease(_CompactString* pCompact)
387 {
388     if (pCompact->m_CompactLen == 0xff) {
389         FX_Free(pCompact->m_pBuffer);
390     }
391 }
_CompactStringSame(_CompactString * pCompact,FX_LPCBYTE pStr,int len)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 }
_CompactStringStore(_CompactString * pCompact,FX_LPCBYTE pStr,int len)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     FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len);
417 }
_CompactStringGet(_CompactString * pCompact)418 static 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
CFX_CMapByteStringToPtr()430 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr()
431     : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE)
432 {
433 }
~CFX_CMapByteStringToPtr()434 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()
435 {
436     RemoveAll();
437 }
RemoveAll()438 void 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 }
GetStartPosition() const446 FX_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 }
GetNextAssoc(FX_POSITION & rNextPosition,CFX_ByteString & rKey,void * & rValue) const457 void 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 }
GetNextValue(FX_POSITION & rNextPosition) const478 FX_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 }
_CMapLookupCallback(void * param,void * pData)499 FX_BOOL _CMapLookupCallback(void* param, void* pData)
500 {
501     return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength());
502 }
Lookup(FX_BSTR key,void * & rValue) const503 FX_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 }
SetAt(FX_BSTR key,void * value)512 void 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 }
AddValue(FX_BSTR key,void * value)538 void 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 }
RemoveKey(FX_BSTR key)545 void 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 }
GetCount() const559 int 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 }
571 extern "C" {
_CompareDWord(const void * p1,const void * p2)572     static int _CompareDWord(const void* p1, const void* p2)
573     {
574         return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);
575     }
576 };
577 struct _DWordPair {
578     FX_DWORD key;
579     FX_DWORD value;
580 };
Lookup(FX_DWORD key,FX_DWORD & value) const581 FX_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 }
GetStartPosition() const591 FX_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 }
GetNextAssoc(FX_POSITION & pos,FX_DWORD & key,FX_DWORD & value) const599 void 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 }
SetAt(FX_DWORD key,FX_DWORD value)615 void 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 }
EstimateSize(FX_DWORD size,FX_DWORD grow_by)638 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by)
639 {
640     m_Buffer.EstimateSize(size, grow_by);
641 }
642