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 "core/include/fxcrt/fx_basic.h"
8 #include "plex.h"
9
10 namespace {
11
12 const uint8_t kFreeLength = 0xfe;
13 const uint8_t kHasAllocatedBufferLength = 0xff;
14
15 } // namespace
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 ASSERT(m_nBlockSize > 0);
25 }
RemoveAll()26 void CFX_MapPtrToPtr::RemoveAll() {
27 FX_Free(m_pHashTable);
28 m_pHashTable = NULL;
29 m_nCount = 0;
30 m_pFreeList = NULL;
31 m_pBlocks->FreeDataChain();
32 m_pBlocks = NULL;
33 }
~CFX_MapPtrToPtr()34 CFX_MapPtrToPtr::~CFX_MapPtrToPtr() {
35 RemoveAll();
36 ASSERT(m_nCount == 0);
37 }
HashKey(void * key) const38 FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const {
39 return ((FX_DWORD)(uintptr_t)key) >> 4;
40 }
GetNextAssoc(FX_POSITION & rNextPosition,void * & rKey,void * & rValue) const41 void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition,
42 void*& rKey,
43 void*& rValue) const {
44 ASSERT(m_pHashTable);
45 CAssoc* pAssocRet = (CAssoc*)rNextPosition;
46 ASSERT(pAssocRet);
47 if (pAssocRet == (CAssoc*)-1) {
48 for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++) {
49 if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
50 break;
51 }
52 ASSERT(pAssocRet);
53 }
54 CAssoc* pAssocNext;
55 if ((pAssocNext = pAssocRet->pNext) == NULL) {
56 for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1;
57 nBucket < m_nHashTableSize; nBucket++) {
58 if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
59 break;
60 }
61 }
62 }
63 rNextPosition = (FX_POSITION)pAssocNext;
64 rKey = pAssocRet->key;
65 rValue = pAssocRet->value;
66 }
Lookup(void * key,void * & rValue) const67 FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const {
68 FX_DWORD nHash;
69 CAssoc* pAssoc = GetAssocAt(key, nHash);
70 if (!pAssoc) {
71 return FALSE;
72 }
73 rValue = pAssoc->value;
74 return TRUE;
75 }
GetValueAt(void * key) const76 void* CFX_MapPtrToPtr::GetValueAt(void* key) const {
77 FX_DWORD nHash;
78 CAssoc* pAssoc = GetAssocAt(key, nHash);
79 if (!pAssoc) {
80 return NULL;
81 }
82 return pAssoc->value;
83 }
operator [](void * key)84 void*& CFX_MapPtrToPtr::operator[](void* key) {
85 FX_DWORD nHash;
86 CAssoc* pAssoc;
87 if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {
88 if (!m_pHashTable) {
89 InitHashTable(m_nHashTableSize);
90 }
91 pAssoc = NewAssoc();
92 pAssoc->key = key;
93 pAssoc->pNext = m_pHashTable[nHash];
94 m_pHashTable[nHash] = pAssoc;
95 }
96 return pAssoc->value;
97 }
GetAssocAt(void * key,FX_DWORD & nHash) const98 CFX_MapPtrToPtr::CAssoc* CFX_MapPtrToPtr::GetAssocAt(void* key,
99 FX_DWORD& nHash) const {
100 nHash = HashKey(key) % m_nHashTableSize;
101 if (!m_pHashTable) {
102 return NULL;
103 }
104 CAssoc* pAssoc;
105 for (pAssoc = m_pHashTable[nHash]; pAssoc; pAssoc = pAssoc->pNext) {
106 if (pAssoc->key == key)
107 return pAssoc;
108 }
109 return NULL;
110 }
NewAssoc()111 CFX_MapPtrToPtr::CAssoc* CFX_MapPtrToPtr::NewAssoc() {
112 if (!m_pFreeList) {
113 CFX_Plex* newBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize,
114 sizeof(CFX_MapPtrToPtr::CAssoc));
115 CFX_MapPtrToPtr::CAssoc* pAssoc =
116 (CFX_MapPtrToPtr::CAssoc*)newBlock->data();
117 pAssoc += m_nBlockSize - 1;
118 for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {
119 pAssoc->pNext = m_pFreeList;
120 m_pFreeList = pAssoc;
121 }
122 }
123 CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList;
124 m_pFreeList = m_pFreeList->pNext;
125 m_nCount++;
126 ASSERT(m_nCount > 0);
127 pAssoc->key = 0;
128 pAssoc->value = 0;
129 return pAssoc;
130 }
InitHashTable(FX_DWORD nHashSize,FX_BOOL bAllocNow)131 void CFX_MapPtrToPtr::InitHashTable(FX_DWORD nHashSize, FX_BOOL bAllocNow) {
132 ASSERT(m_nCount == 0);
133 ASSERT(nHashSize > 0);
134 FX_Free(m_pHashTable);
135 m_pHashTable = NULL;
136 if (bAllocNow) {
137 m_pHashTable = FX_Alloc(CAssoc*, nHashSize);
138 }
139 m_nHashTableSize = nHashSize;
140 }
RemoveKey(void * key)141 FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key) {
142 if (!m_pHashTable) {
143 return FALSE;
144 }
145 CAssoc** ppAssocPrev;
146 ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
147 CAssoc* pAssoc;
148 for (pAssoc = *ppAssocPrev; pAssoc; pAssoc = pAssoc->pNext) {
149 if (pAssoc->key == key) {
150 *ppAssocPrev = pAssoc->pNext;
151 FreeAssoc(pAssoc);
152 return TRUE;
153 }
154 ppAssocPrev = &pAssoc->pNext;
155 }
156 return FALSE;
157 }
FreeAssoc(CFX_MapPtrToPtr::CAssoc * pAssoc)158 void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) {
159 pAssoc->pNext = m_pFreeList;
160 m_pFreeList = pAssoc;
161 m_nCount--;
162 ASSERT(m_nCount >= 0);
163 if (m_nCount == 0) {
164 RemoveAll();
165 }
166 }
167 struct _CompactString {
168 uint8_t m_CompactLen;
169 uint8_t m_LenHigh;
170 uint8_t m_LenLow;
171 uint8_t m_Unused;
172 uint8_t* m_pBuffer;
173 };
_CompactStringRelease(_CompactString * pCompact)174 static void _CompactStringRelease(_CompactString* pCompact) {
175 if (pCompact->m_CompactLen == kHasAllocatedBufferLength) {
176 FX_Free(pCompact->m_pBuffer);
177 }
178 }
_CompactStringSame(_CompactString * pCompact,const uint8_t * pStr,int len)179 static FX_BOOL _CompactStringSame(_CompactString* pCompact,
180 const uint8_t* pStr,
181 int len) {
182 if (len < sizeof(_CompactString)) {
183 if (pCompact->m_CompactLen != len) {
184 return FALSE;
185 }
186 return FXSYS_memcmp(&pCompact->m_LenHigh, pStr, len) == 0;
187 }
188 if (pCompact->m_CompactLen != kHasAllocatedBufferLength ||
189 pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) {
190 return FALSE;
191 }
192 return FXSYS_memcmp(pCompact->m_pBuffer, pStr, len) == 0;
193 }
_CompactStringStore(_CompactString * pCompact,const uint8_t * pStr,int len)194 static void _CompactStringStore(_CompactString* pCompact,
195 const uint8_t* pStr,
196 int len) {
197 if (len < (int)sizeof(_CompactString)) {
198 pCompact->m_CompactLen = (uint8_t)len;
199 FXSYS_memcpy(&pCompact->m_LenHigh, pStr, len);
200 return;
201 }
202 pCompact->m_CompactLen = kHasAllocatedBufferLength;
203 pCompact->m_LenHigh = len / 256;
204 pCompact->m_LenLow = len % 256;
205 pCompact->m_pBuffer = FX_Alloc(uint8_t, len);
206 FXSYS_memcpy(pCompact->m_pBuffer, pStr, len);
207 }
_CompactStringGet(_CompactString * pCompact)208 static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact) {
209 if (pCompact->m_CompactLen == kHasAllocatedBufferLength) {
210 return CFX_ByteStringC(pCompact->m_pBuffer,
211 pCompact->m_LenHigh * 256 + pCompact->m_LenLow);
212 }
213 if (pCompact->m_CompactLen == kFreeLength) {
214 return CFX_ByteStringC();
215 }
216 return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen);
217 }
218 #define CMAP_ALLOC_STEP 8
219 #define CMAP_INDEX_SIZE 8
CFX_CMapByteStringToPtr()220 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr()
221 : m_Buffer(sizeof(_CompactString) + sizeof(void*),
222 CMAP_ALLOC_STEP,
223 CMAP_INDEX_SIZE) {}
~CFX_CMapByteStringToPtr()224 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr() {
225 RemoveAll();
226 }
RemoveAll()227 void CFX_CMapByteStringToPtr::RemoveAll() {
228 int size = m_Buffer.GetSize();
229 for (int i = 0; i < size; i++) {
230 _CompactStringRelease((_CompactString*)m_Buffer.GetAt(i));
231 }
232 m_Buffer.RemoveAll();
233 }
GetStartPosition() const234 FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const {
235 int size = m_Buffer.GetSize();
236 for (int i = 0; i < size; i++) {
237 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
238 if (pKey->m_CompactLen != kFreeLength) {
239 return (FX_POSITION)(uintptr_t)(i + 1);
240 }
241 }
242 return NULL;
243 }
GetNextAssoc(FX_POSITION & rNextPosition,CFX_ByteString & rKey,void * & rValue) const244 void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition,
245 CFX_ByteString& rKey,
246 void*& rValue) const {
247 if (!rNextPosition) {
248 return;
249 }
250 int index = (int)(uintptr_t)rNextPosition - 1;
251 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
252 rKey = _CompactStringGet(pKey);
253 rValue = *(void**)(pKey + 1);
254 index++;
255 int size = m_Buffer.GetSize();
256 while (index < size) {
257 pKey = (_CompactString*)m_Buffer.GetAt(index);
258 if (pKey->m_CompactLen != kFreeLength) {
259 rNextPosition = (FX_POSITION)(uintptr_t)(index + 1);
260 return;
261 }
262 index++;
263 }
264 rNextPosition = NULL;
265 }
GetNextValue(FX_POSITION & rNextPosition) const266 void* CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const {
267 if (!rNextPosition) {
268 return NULL;
269 }
270 int index = (int)(uintptr_t)rNextPosition - 1;
271 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
272 void* rValue = *(void**)(pKey + 1);
273 index++;
274 int size = m_Buffer.GetSize();
275 while (index < size) {
276 pKey = (_CompactString*)m_Buffer.GetAt(index);
277 if (pKey->m_CompactLen != kFreeLength) {
278 rNextPosition = (FX_POSITION)(uintptr_t)(index + 1);
279 return rValue;
280 }
281 index++;
282 }
283 rNextPosition = NULL;
284 return rValue;
285 }
_CMapLookupCallback(void * param,void * pData)286 FX_BOOL _CMapLookupCallback(void* param, void* pData) {
287 return !_CompactStringSame((_CompactString*)pData,
288 ((CFX_ByteStringC*)param)->GetPtr(),
289 ((CFX_ByteStringC*)param)->GetLength());
290 }
Lookup(const CFX_ByteStringC & key,void * & rValue) const291 FX_BOOL CFX_CMapByteStringToPtr::Lookup(const CFX_ByteStringC& key,
292 void*& rValue) const {
293 void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key);
294 if (!p) {
295 return FALSE;
296 }
297 rValue = *(void**)((_CompactString*)p + 1);
298 return TRUE;
299 }
SetAt(const CFX_ByteStringC & key,void * value)300 void CFX_CMapByteStringToPtr::SetAt(const CFX_ByteStringC& key, void* value) {
301 ASSERT(value);
302 int key_len = key.GetLength();
303 int size = m_Buffer.GetSize();
304 for (int index = 0; index < size; index++) {
305 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
306 if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) {
307 continue;
308 }
309 *(void**)(pKey + 1) = value;
310 return;
311 }
312 for (int index = 0; index < size; index++) {
313 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
314 if (pKey->m_CompactLen != kFreeLength) {
315 continue;
316 }
317 _CompactStringStore(pKey, key.GetPtr(), key_len);
318 *(void**)(pKey + 1) = value;
319 return;
320 }
321 _CompactString* pKey = (_CompactString*)m_Buffer.Add();
322 _CompactStringStore(pKey, key.GetPtr(), key_len);
323 *(void**)(pKey + 1) = value;
324 }
AddValue(const CFX_ByteStringC & key,void * value)325 void CFX_CMapByteStringToPtr::AddValue(const CFX_ByteStringC& key,
326 void* value) {
327 ASSERT(value);
328 _CompactString* pKey = (_CompactString*)m_Buffer.Add();
329 _CompactStringStore(pKey, key.GetPtr(), key.GetLength());
330 *(void**)(pKey + 1) = value;
331 }
RemoveKey(const CFX_ByteStringC & key)332 void CFX_CMapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) {
333 int key_len = key.GetLength();
334 int size = m_Buffer.GetSize();
335 for (int index = 0; index < size; index++) {
336 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
337 if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) {
338 continue;
339 }
340 _CompactStringRelease(pKey);
341 pKey->m_CompactLen = kFreeLength;
342 return;
343 }
344 }
GetCount() const345 int CFX_CMapByteStringToPtr::GetCount() const {
346 int count = 0;
347 int size = m_Buffer.GetSize();
348 for (int i = 0; i < size; i++) {
349 _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
350 if (pKey->m_CompactLen != kFreeLength) {
351 count++;
352 }
353 }
354 return count;
355 }
356