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