Initial commit.
[pdfium.git] / core / src / fxcrt / fx_basic_maps.cpp
1 // Copyright 2014 PDFium Authors. All rights reserved.\r
2 // Use of this source code is governed by a BSD-style license that can be\r
3 // found in the LICENSE file.\r
4  \r
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
6 \r
7 #include "../../include/fxcrt/fx_ext.h"\r
8 #include "plex.h"\r
9 static void ConstructElement(CFX_ByteString* pNewData)\r
10 {\r
11     new (pNewData) CFX_ByteString();\r
12 }\r
13 static void DestructElement(CFX_ByteString* pOldData)\r
14 {\r
15     pOldData->~CFX_ByteString();\r
16 }\r
17 CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize, IFX_Allocator* pAllocator)\r
18     : m_pAllocator(pAllocator)\r
19     , m_pHashTable(NULL)\r
20     , m_nHashTableSize(17)\r
21     , m_nCount(0)\r
22     , m_pFreeList(NULL)\r
23     , m_pBlocks(NULL)\r
24     , m_nBlockSize(nBlockSize)\r
25 {\r
26     ASSERT(m_nBlockSize > 0);\r
27 }\r
28 void CFX_MapPtrToPtr::RemoveAll()\r
29 {\r
30     if (m_pHashTable) {\r
31         FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
32         m_pHashTable = NULL;\r
33     }\r
34     m_nCount = 0;\r
35     m_pFreeList = NULL;\r
36     m_pBlocks->FreeDataChain(m_pAllocator);\r
37     m_pBlocks = NULL;\r
38 }\r
39 CFX_MapPtrToPtr::~CFX_MapPtrToPtr()\r
40 {\r
41     RemoveAll();\r
42     ASSERT(m_nCount == 0);\r
43 }\r
44 FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const\r
45 {\r
46     return ((FX_DWORD)(FX_UINTPTR)key) >> 4;\r
47 }\r
48 void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition, void*& rKey, void*& rValue) const\r
49 {\r
50     ASSERT(m_pHashTable != NULL);\r
51     CAssoc* pAssocRet = (CAssoc*)rNextPosition;\r
52     ASSERT(pAssocRet != NULL);\r
53     if (pAssocRet == (CAssoc*) - 1) {\r
54         for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)\r
55             if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {\r
56                 break;\r
57             }\r
58         ASSERT(pAssocRet != NULL);\r
59     }\r
60     CAssoc* pAssocNext;\r
61     if ((pAssocNext = pAssocRet->pNext) == NULL) {\r
62         for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1; nBucket < m_nHashTableSize; nBucket ++) {\r
63             if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {\r
64                 break;\r
65             }\r
66         }\r
67     }\r
68     rNextPosition = (FX_POSITION) pAssocNext;\r
69     rKey = pAssocRet->key;\r
70     rValue = pAssocRet->value;\r
71 }\r
72 FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const\r
73 {\r
74     FX_DWORD nHash;\r
75     CAssoc* pAssoc = GetAssocAt(key, nHash);\r
76     if (pAssoc == NULL) {\r
77         return FALSE;\r
78     }\r
79     rValue = pAssoc->value;\r
80     return TRUE;\r
81 }\r
82 void* CFX_MapPtrToPtr::GetValueAt(void* key) const\r
83 {\r
84     FX_DWORD nHash;\r
85     CAssoc* pAssoc = GetAssocAt(key, nHash);\r
86     if (pAssoc == NULL) {\r
87         return NULL;\r
88     }\r
89     return pAssoc->value;\r
90 }\r
91 void*& CFX_MapPtrToPtr::operator[](void* key)\r
92 {\r
93     FX_DWORD nHash;\r
94     CAssoc* pAssoc;\r
95     if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {\r
96         if (m_pHashTable == NULL) {\r
97             InitHashTable(m_nHashTableSize);\r
98         }\r
99         pAssoc = NewAssoc();\r
100         pAssoc->key = key;\r
101         pAssoc->pNext = m_pHashTable[nHash];\r
102         m_pHashTable[nHash] = pAssoc;\r
103     }\r
104     return pAssoc->value;\r
105 }\r
106 CFX_MapPtrToPtr::CAssoc*\r
107 CFX_MapPtrToPtr::GetAssocAt(void* key, FX_DWORD& nHash) const\r
108 {\r
109     nHash = HashKey(key) % m_nHashTableSize;\r
110     if (m_pHashTable == NULL) {\r
111         return NULL;\r
112     }\r
113     CAssoc* pAssoc;\r
114     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
115         if (pAssoc->key == key) {\r
116             return pAssoc;\r
117         }\r
118     }\r
119     return NULL;\r
120 }\r
121 CFX_MapPtrToPtr::CAssoc*\r
122 CFX_MapPtrToPtr::NewAssoc()\r
123 {\r
124     if (m_pFreeList == NULL) {\r
125         CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapPtrToPtr::CAssoc));\r
126         CFX_MapPtrToPtr::CAssoc* pAssoc = (CFX_MapPtrToPtr::CAssoc*)newBlock->data();\r
127         pAssoc += m_nBlockSize - 1;\r
128         for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {\r
129             pAssoc->pNext = m_pFreeList;\r
130             m_pFreeList = pAssoc;\r
131         }\r
132     }\r
133     ASSERT(m_pFreeList != NULL);\r
134     CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList;\r
135     m_pFreeList = m_pFreeList->pNext;\r
136     m_nCount++;\r
137     ASSERT(m_nCount > 0);\r
138     pAssoc->key = 0;\r
139     pAssoc->value = 0;\r
140     return pAssoc;\r
141 }\r
142 void CFX_MapPtrToPtr::InitHashTable(\r
143     FX_DWORD nHashSize, FX_BOOL bAllocNow)\r
144 {\r
145     ASSERT(m_nCount == 0);\r
146     ASSERT(nHashSize > 0);\r
147     if (m_pHashTable != NULL) {\r
148         FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
149         m_pHashTable = NULL;\r
150     }\r
151     if (bAllocNow) {\r
152         m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);\r
153         if (m_pHashTable) {\r
154             FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);\r
155         }\r
156     }\r
157     m_nHashTableSize = nHashSize;\r
158 }\r
159 FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key)\r
160 {\r
161     if (m_pHashTable == NULL) {\r
162         return FALSE;\r
163     }\r
164     CAssoc** ppAssocPrev;\r
165     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];\r
166     CAssoc* pAssoc;\r
167     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
168         if (pAssoc->key == key) {\r
169             *ppAssocPrev = pAssoc->pNext;\r
170             FreeAssoc(pAssoc);\r
171             return TRUE;\r
172         }\r
173         ppAssocPrev = &pAssoc->pNext;\r
174     }\r
175     return FALSE;\r
176 }\r
177 void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc)\r
178 {\r
179     pAssoc->pNext = m_pFreeList;\r
180     m_pFreeList = pAssoc;\r
181     m_nCount--;\r
182     ASSERT(m_nCount >= 0);\r
183     if (m_nCount == 0) {\r
184         RemoveAll();\r
185     }\r
186 }\r
187 CFX_MapByteStringToPtr::CFX_MapByteStringToPtr(int nBlockSize, IFX_Allocator* pAllocator)\r
188     : m_pAllocator(pAllocator)\r
189     , m_pHashTable(NULL)\r
190     , m_nHashTableSize(17)\r
191     , m_nCount(0)\r
192     , m_pFreeList(NULL)\r
193     , m_pBlocks(NULL)\r
194     , m_nBlockSize(nBlockSize)\r
195 {\r
196     ASSERT(m_nBlockSize > 0);\r
197 }\r
198 void CFX_MapByteStringToPtr::RemoveAll()\r
199 {\r
200     if (m_pHashTable != NULL) {\r
201         for (FX_DWORD nHash = 0; nHash < m_nHashTableSize; nHash++) {\r
202             CAssoc* pAssoc;\r
203             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;\r
204                     pAssoc = pAssoc->pNext) {\r
205                 DestructElement(&pAssoc->key);\r
206             }\r
207         }\r
208         FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
209         m_pHashTable = NULL;\r
210     }\r
211     m_nCount = 0;\r
212     m_pFreeList = NULL;\r
213     m_pBlocks->FreeDataChain(m_pAllocator);\r
214     m_pBlocks = NULL;\r
215 }\r
216 CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr()\r
217 {\r
218     RemoveAll();\r
219     ASSERT(m_nCount == 0);\r
220 }\r
221 void CFX_MapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition,\r
222         CFX_ByteString& rKey, void*& rValue) const\r
223 {\r
224     ASSERT(m_pHashTable != NULL);\r
225     CAssoc* pAssocRet = (CAssoc*)rNextPosition;\r
226     ASSERT(pAssocRet != NULL);\r
227     if (pAssocRet == (CAssoc*) - 1) {\r
228         for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)\r
229             if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {\r
230                 break;\r
231             }\r
232         ASSERT(pAssocRet != NULL);\r
233     }\r
234     CAssoc* pAssocNext;\r
235     if ((pAssocNext = pAssocRet->pNext) == NULL) {\r
236         for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;\r
237                 nBucket < m_nHashTableSize; nBucket++)\r
238             if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {\r
239                 break;\r
240             }\r
241     }\r
242     rNextPosition = (FX_POSITION) pAssocNext;\r
243     rKey = pAssocRet->key;\r
244     rValue = pAssocRet->value;\r
245 }\r
246 FX_LPVOID CFX_MapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const\r
247 {\r
248     ASSERT(m_pHashTable != NULL);\r
249     CAssoc* pAssocRet = (CAssoc*)rNextPosition;\r
250     ASSERT(pAssocRet != NULL);\r
251     if (pAssocRet == (CAssoc*) - 1) {\r
252         for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)\r
253             if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {\r
254                 break;\r
255             }\r
256         ASSERT(pAssocRet != NULL);\r
257     }\r
258     CAssoc* pAssocNext;\r
259     if ((pAssocNext = pAssocRet->pNext) == NULL) {\r
260         for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;\r
261                 nBucket < m_nHashTableSize; nBucket++)\r
262             if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {\r
263                 break;\r
264             }\r
265     }\r
266     rNextPosition = (FX_POSITION) pAssocNext;\r
267     return pAssocRet->value;\r
268 }\r
269 void*& CFX_MapByteStringToPtr::operator[](FX_BSTR key)\r
270 {\r
271     FX_DWORD nHash;\r
272     CAssoc* pAssoc;\r
273     if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {\r
274         if (m_pHashTable == NULL) {\r
275             InitHashTable(m_nHashTableSize);\r
276         }\r
277         pAssoc = NewAssoc();\r
278         pAssoc->nHashValue = nHash;\r
279         pAssoc->key = key;\r
280         pAssoc->pNext = m_pHashTable[nHash];\r
281         m_pHashTable[nHash] = pAssoc;\r
282     }\r
283     return pAssoc->value;\r
284 }\r
285 CFX_MapByteStringToPtr::CAssoc*\r
286 CFX_MapByteStringToPtr::NewAssoc()\r
287 {\r
288     if (m_pFreeList == NULL) {\r
289         CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapByteStringToPtr::CAssoc));\r
290         CFX_MapByteStringToPtr::CAssoc* pAssoc = (CFX_MapByteStringToPtr::CAssoc*)newBlock->data();\r
291         pAssoc += m_nBlockSize - 1;\r
292         for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {\r
293             pAssoc->pNext = m_pFreeList;\r
294             m_pFreeList = pAssoc;\r
295         }\r
296     }\r
297     ASSERT(m_pFreeList != NULL);\r
298     CFX_MapByteStringToPtr::CAssoc* pAssoc = m_pFreeList;\r
299     m_pFreeList = m_pFreeList->pNext;\r
300     m_nCount++;\r
301     ASSERT(m_nCount > 0);\r
302     ConstructElement(&pAssoc->key);\r
303     pAssoc->value = 0;\r
304     return pAssoc;\r
305 }\r
306 void CFX_MapByteStringToPtr::FreeAssoc(CFX_MapByteStringToPtr::CAssoc* pAssoc)\r
307 {\r
308     DestructElement(&pAssoc->key);\r
309     pAssoc->pNext = m_pFreeList;\r
310     m_pFreeList = pAssoc;\r
311     m_nCount--;\r
312     ASSERT(m_nCount >= 0);\r
313     if (m_nCount == 0) {\r
314         RemoveAll();\r
315     }\r
316 }\r
317 CFX_MapByteStringToPtr::CAssoc*\r
318 CFX_MapByteStringToPtr::GetAssocAt(FX_BSTR key, FX_DWORD& nHash) const\r
319 {\r
320     nHash = HashKey(key) % m_nHashTableSize;\r
321     if (m_pHashTable == NULL) {\r
322         return NULL;\r
323     }\r
324     CAssoc* pAssoc;\r
325     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
326         if (pAssoc->key == key) {\r
327             return pAssoc;\r
328         }\r
329     }\r
330     return NULL;\r
331 }\r
332 FX_BOOL CFX_MapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const\r
333 {\r
334     FX_DWORD nHash;\r
335     CAssoc* pAssoc = GetAssocAt(key, nHash);\r
336     if (pAssoc == NULL) {\r
337         return FALSE;\r
338     }\r
339     rValue = pAssoc->value;\r
340     return TRUE;\r
341 }\r
342 void CFX_MapByteStringToPtr::InitHashTable(\r
343     FX_DWORD nHashSize, FX_BOOL bAllocNow)\r
344 {\r
345     ASSERT(m_nCount == 0);\r
346     ASSERT(nHashSize > 0);\r
347     if (m_pHashTable != NULL) {\r
348         FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
349         m_pHashTable = NULL;\r
350     }\r
351     if (bAllocNow) {\r
352         m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);\r
353         if (m_pHashTable) {\r
354             FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);\r
355         }\r
356     }\r
357     m_nHashTableSize = nHashSize;\r
358 }\r
359 inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const\r
360 {\r
361     FX_DWORD nHash = 0;\r
362     int len = key.GetLength();\r
363     FX_LPCBYTE buf = key;\r
364     for (int i = 0; i < len; i ++) {\r
365         nHash = (nHash << 5) + nHash + buf[i];\r
366     }\r
367     return nHash;\r
368 }\r
369 FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR key)\r
370 {\r
371     if (m_pHashTable == NULL) {\r
372         return FALSE;\r
373     }\r
374     CAssoc** ppAssocPrev;\r
375     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];\r
376     CAssoc* pAssoc;\r
377     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
378         if (pAssoc->key == key) {\r
379             *ppAssocPrev = pAssoc->pNext;\r
380             FreeAssoc(pAssoc);\r
381             return TRUE;\r
382         }\r
383         ppAssocPrev = &pAssoc->pNext;\r
384     }\r
385     return FALSE;\r
386 }\r
387 struct _CompactString {\r
388     FX_BYTE             m_CompactLen;\r
389     FX_BYTE             m_LenHigh;\r
390     FX_BYTE             m_LenLow;\r
391     FX_BYTE             m_Unused;\r
392     FX_LPBYTE   m_pBuffer;\r
393 };\r
394 static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact)\r
395 {\r
396     if (pCompact->m_CompactLen == 0xff) {\r
397         FX_Allocator_Free(pAllocator, pCompact->m_pBuffer);\r
398     }\r
399 }\r
400 static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE pStr, int len)\r
401 {\r
402     if (len < sizeof(_CompactString)) {\r
403         if (pCompact->m_CompactLen != len) {\r
404             return FALSE;\r
405         }\r
406         return FXSYS_memcmp32(&pCompact->m_LenHigh, pStr, len) == 0;\r
407     }\r
408     if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) {\r
409         return FALSE;\r
410     }\r
411     return FXSYS_memcmp32(pCompact->m_pBuffer, pStr, len) == 0;\r
412 }\r
413 static void _CompactStringStore(IFX_Allocator* pAllocator, _CompactString* pCompact, FX_LPCBYTE pStr, int len)\r
414 {\r
415     if (len < (int)sizeof(_CompactString)) {\r
416         pCompact->m_CompactLen = (FX_BYTE)len;\r
417         FXSYS_memcpy32(&pCompact->m_LenHigh, pStr, len);\r
418         return;\r
419     }\r
420     pCompact->m_CompactLen = 0xff;\r
421     pCompact->m_LenHigh = len / 256;\r
422     pCompact->m_LenLow = len % 256;\r
423     pCompact->m_pBuffer = FX_Allocator_Alloc(pAllocator, FX_BYTE, len);\r
424     if (pCompact->m_pBuffer) {\r
425         FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len);\r
426     }\r
427 }\r
428 static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact)\r
429 {\r
430     if (pCompact->m_CompactLen == 0xff) {\r
431         return CFX_ByteStringC(pCompact->m_pBuffer, pCompact->m_LenHigh * 256 + pCompact->m_LenLow);\r
432     }\r
433     if (pCompact->m_CompactLen == 0xfe) {\r
434         return CFX_ByteStringC();\r
435     }\r
436     return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen);\r
437 }\r
438 #define CMAP_ALLOC_STEP         8\r
439 #define CMAP_INDEX_SIZE         8\r
440 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr(IFX_Allocator* pAllocator)\r
441     : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator)\r
442 {\r
443 }\r
444 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()\r
445 {\r
446     RemoveAll();\r
447 }\r
448 void CFX_CMapByteStringToPtr::RemoveAll()\r
449 {\r
450     IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;\r
451     int size = m_Buffer.GetSize();\r
452     for (int i = 0; i < size; i ++) {\r
453         _CompactStringRelease(pAllocator, (_CompactString*)m_Buffer.GetAt(i));\r
454     }\r
455     m_Buffer.RemoveAll();\r
456 }\r
457 FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const\r
458 {\r
459     int size = m_Buffer.GetSize();\r
460     for (int i = 0; i < size; i ++) {\r
461         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);\r
462         if (pKey->m_CompactLen != 0xfe) {\r
463             return (FX_POSITION)(FX_UINTPTR)(i + 1);\r
464         }\r
465     }\r
466     return NULL;\r
467 }\r
468 void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const\r
469 {\r
470     if (rNextPosition == NULL) {\r
471         return;\r
472     }\r
473     int index = (int)(FX_UINTPTR)rNextPosition - 1;\r
474     _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
475     rKey = _CompactStringGet(pKey);\r
476     rValue = *(void**)(pKey + 1);\r
477     index ++;\r
478     int size = m_Buffer.GetSize();\r
479     while (index < size) {\r
480         pKey = (_CompactString*)m_Buffer.GetAt(index);\r
481         if (pKey->m_CompactLen != 0xfe) {\r
482             rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);\r
483             return;\r
484         }\r
485         index ++;\r
486     }\r
487     rNextPosition = NULL;\r
488 }\r
489 FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const\r
490 {\r
491     if (rNextPosition == NULL) {\r
492         return NULL;\r
493     }\r
494     int index = (int)(FX_UINTPTR)rNextPosition - 1;\r
495     _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
496     FX_LPVOID rValue = *(void**)(pKey + 1);\r
497     index ++;\r
498     int size = m_Buffer.GetSize();\r
499     while (index < size) {\r
500         pKey = (_CompactString*)m_Buffer.GetAt(index);\r
501         if (pKey->m_CompactLen != 0xfe) {\r
502             rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);\r
503             return rValue;\r
504         }\r
505         index ++;\r
506     }\r
507     rNextPosition = NULL;\r
508     return rValue;\r
509 }\r
510 FX_BOOL _CMapLookupCallback(void* param, void* pData)\r
511 {\r
512     return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength());\r
513 }\r
514 FX_BOOL CFX_CMapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const\r
515 {\r
516     void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key);\r
517     if (!p) {\r
518         return FALSE;\r
519     }\r
520     rValue = *(void**)((_CompactString*)p + 1);\r
521     return TRUE;\r
522 }\r
523 void CFX_CMapByteStringToPtr::SetAt(FX_BSTR key, void* value)\r
524 {\r
525     ASSERT(value != NULL);\r
526     int index, key_len = key.GetLength();\r
527     int size = m_Buffer.GetSize();\r
528     for (index = 0; index < size; index ++) {\r
529         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
530         if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {\r
531             continue;\r
532         }\r
533         *(void**)(pKey + 1) = value;\r
534         return;\r
535     }\r
536     IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;\r
537     for (index = 0; index < size; index ++) {\r
538         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
539         if (pKey->m_CompactLen) {\r
540             continue;\r
541         }\r
542         _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);\r
543         *(void**)(pKey + 1) = value;\r
544         return;\r
545     }\r
546     _CompactString* pKey = (_CompactString*)m_Buffer.Add();\r
547     _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);\r
548     *(void**)(pKey + 1) = value;\r
549 }\r
550 void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value)\r
551 {\r
552     ASSERT(value != NULL);\r
553     _CompactString* pKey = (_CompactString*)m_Buffer.Add();\r
554     _CompactStringStore(m_Buffer.m_pAllocator, pKey, (FX_LPCBYTE)key, key.GetLength());\r
555     *(void**)(pKey + 1) = value;\r
556 }\r
557 void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key)\r
558 {\r
559     int key_len = key.GetLength();\r
560     IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;\r
561     int size = m_Buffer.GetSize();\r
562     for (int index = 0; index < size; index ++) {\r
563         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
564         if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {\r
565             continue;\r
566         }\r
567         _CompactStringRelease(pAllocator, pKey);\r
568         pKey->m_CompactLen = 0xfe;\r
569         return;\r
570     }\r
571 }\r
572 int CFX_CMapByteStringToPtr::GetCount() const\r
573 {\r
574     int count = 0;\r
575     int size = m_Buffer.GetSize();\r
576     for (int i = 0; i < size; i ++) {\r
577         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);\r
578         if (pKey->m_CompactLen != 0xfe) {\r
579             count ++;\r
580         }\r
581     }\r
582     return count;\r
583 }\r
584 extern "C" {\r
585     static int _CompareDWord(const void* p1, const void* p2)\r
586     {\r
587         return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);\r
588     }\r
589 };\r
590 struct _DWordPair {\r
591     FX_DWORD key;\r
592     FX_DWORD value;\r
593 };\r
594 FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const\r
595 {\r
596     FX_LPVOID pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize() / sizeof(_DWordPair),\r
597                                       sizeof(_DWordPair), _CompareDWord);\r
598     if (pResult == NULL) {\r
599         return FALSE;\r
600     }\r
601     value = ((FX_DWORD*)pResult)[1];\r
602     return TRUE;\r
603 }\r
604 FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const\r
605 {\r
606     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);\r
607     if (count == 0) {\r
608         return NULL;\r
609     }\r
610     return (FX_POSITION)1;\r
611 }\r
612 void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const\r
613 {\r
614     if (pos == 0) {\r
615         return;\r
616     }\r
617     FX_DWORD index = ((FX_DWORD)(FX_UINTPTR)pos) - 1;\r
618     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);\r
619     _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();\r
620     key = buf[index].key;\r
621     value = buf[index].value;\r
622     if (index == count - 1) {\r
623         pos = 0;\r
624     } else {\r
625         pos = (FX_POSITION)((FX_UINTPTR)pos + 1);\r
626     }\r
627 }\r
628 void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value)\r
629 {\r
630     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);\r
631     _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();\r
632     _DWordPair pair = {key, value};\r
633     if (count == 0 || key > buf[count - 1].key) {\r
634         m_Buffer.AppendBlock(&pair, sizeof(_DWordPair));\r
635         return;\r
636     }\r
637     int low = 0, high = count - 1;\r
638     while (low <= high) {\r
639         int mid = (low + high) / 2;\r
640         if (buf[mid].key < key) {\r
641             low = mid + 1;\r
642         } else if (buf[mid].key > key) {\r
643             high = mid - 1;\r
644         } else {\r
645             buf[mid].value = value;\r
646             return;\r
647         }\r
648     }\r
649     m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair));\r
650 }\r
651 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by)\r
652 {\r
653     m_Buffer.EstimateSize(size, grow_by);\r
654 }\r