Merge XFA to PDFium master at 4dc95e7 on 10/28/2014
[pdfium.git] / xfa / src / fgas / src / crt / fx_memory.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 "../fgas_base.h"\r
8 #include "fx_memory.h"\r
9 #define FX_4BYTEALIGN(size)     (((size) + 3) / 4 * 4)\r
10 IFX_MEMAllocator* FX_CreateAllocator(FX_ALLOCTYPE eType, size_t chunkSize, size_t blockSize)\r
11 {\r
12     switch (eType) {\r
13 #ifndef _FXEMB\r
14         case FX_ALLOCTYPE_Dynamic:\r
15             return FXTARGET_New CFX_DynamicStore(chunkSize);\r
16 #endif\r
17         case FX_ALLOCTYPE_Default:\r
18             return FXTARGET_New CFX_DefStore();\r
19         case FX_ALLOCTYPE_Static:\r
20             return FXTARGET_New CFX_StaticStore(chunkSize);\r
21         case FX_ALLOCTYPE_Fixed:\r
22             return FXTARGET_New CFX_FixedStore(blockSize, chunkSize);\r
23         default:\r
24             return NULL;\r
25     }\r
26 }\r
27 CFX_StaticStore::CFX_StaticStore(size_t iDefChunkSize)\r
28     : m_iAllocatedSize(0)\r
29     , m_iDefChunkSize(iDefChunkSize)\r
30     , m_pChunk(NULL)\r
31     , m_pLastChunk(NULL)\r
32 {\r
33     FXSYS_assert(m_iDefChunkSize != 0);\r
34 }\r
35 CFX_StaticStore::~CFX_StaticStore()\r
36 {\r
37     register FX_LPSTATICSTORECHUNK pChunk, pNext;\r
38     pChunk = m_pChunk;\r
39     while (pChunk != NULL) {\r
40         pNext = pChunk->pNextChunk;\r
41         FX_Free(pChunk);\r
42         pChunk = pNext;\r
43     }\r
44 }\r
45 FX_LPSTATICSTORECHUNK CFX_StaticStore::AllocChunk(size_t size)\r
46 {\r
47     FXSYS_assert(size != 0);\r
48     register FX_LPSTATICSTORECHUNK pChunk = (FX_LPSTATICSTORECHUNK)FX_Alloc(FX_BYTE, sizeof(FX_STATICSTORECHUNK) + size);\r
49     if (pChunk == NULL) {\r
50         return NULL;\r
51     }\r
52     pChunk->iChunkSize = size;\r
53     pChunk->iFreeSize = size;\r
54     pChunk->pNextChunk = NULL;\r
55     if (m_pLastChunk == NULL) {\r
56         m_pChunk = pChunk;\r
57     } else {\r
58         m_pLastChunk->pNextChunk = pChunk;\r
59     }\r
60     m_pLastChunk = pChunk;\r
61     return pChunk;\r
62 }\r
63 FX_LPSTATICSTORECHUNK CFX_StaticStore::FindChunk(size_t size)\r
64 {\r
65     FXSYS_assert(size != 0);\r
66     if (m_pLastChunk == NULL || m_pLastChunk->iFreeSize < size) {\r
67         return AllocChunk(FX_MAX(m_iDefChunkSize, size));\r
68     }\r
69     return m_pLastChunk;\r
70 }\r
71 void* CFX_StaticStore::Alloc(size_t size)\r
72 {\r
73     size = FX_4BYTEALIGN(size);\r
74     FXSYS_assert(size != 0);\r
75     register FX_LPSTATICSTORECHUNK pChunk = FindChunk(size);\r
76     FXSYS_assert(pChunk != NULL && pChunk->iFreeSize >= size);\r
77     register FX_LPBYTE p = (FX_LPBYTE)pChunk;\r
78     p += sizeof(FX_STATICSTORECHUNK) + pChunk->iChunkSize - pChunk->iFreeSize;\r
79     pChunk->iFreeSize -= size;\r
80     m_iAllocatedSize += size;\r
81     return p;\r
82 }\r
83 size_t CFX_StaticStore::SetDefChunkSize(size_t size)\r
84 {\r
85     FXSYS_assert(size != 0);\r
86     size_t v = m_iDefChunkSize;\r
87     m_iDefChunkSize = size;\r
88     return v;\r
89 }\r
90 CFX_FixedStore::CFX_FixedStore(size_t iBlockSize, size_t iBlockNumsInChunk)\r
91     : m_iBlockSize(FX_4BYTEALIGN(iBlockSize))\r
92     , m_iDefChunkSize(FX_4BYTEALIGN(iBlockNumsInChunk))\r
93     , m_pChunk(NULL)\r
94 {\r
95     FXSYS_assert(m_iBlockSize != 0 && m_iDefChunkSize != 0);\r
96 }\r
97 CFX_FixedStore::~CFX_FixedStore()\r
98 {\r
99     register FX_LPFIXEDSTORECHUNK pChunk, pNext;\r
100     pChunk = m_pChunk;\r
101     while (pChunk != NULL) {\r
102         pNext = pChunk->pNextChunk;\r
103         FX_Free(pChunk);\r
104         pChunk = pNext;\r
105     }\r
106 }\r
107 FX_LPFIXEDSTORECHUNK CFX_FixedStore::AllocChunk()\r
108 {\r
109     FX_INT32 iTotalSize = sizeof(FX_FIXEDSTORECHUNK) + m_iDefChunkSize + m_iBlockSize * m_iDefChunkSize;\r
110     register FX_LPFIXEDSTORECHUNK pChunk = (FX_LPFIXEDSTORECHUNK)FX_Alloc(FX_BYTE, iTotalSize);\r
111     if (pChunk == NULL) {\r
112         return NULL;\r
113     }\r
114     FXSYS_memset(pChunk->FirstFlag(), 0, m_iDefChunkSize);\r
115     pChunk->pNextChunk = m_pChunk;\r
116     pChunk->iChunkSize = m_iDefChunkSize;\r
117     pChunk->iFreeNum = m_iDefChunkSize;\r
118     m_pChunk = pChunk;\r
119     return pChunk;\r
120 }\r
121 void* CFX_FixedStore::Alloc(size_t size)\r
122 {\r
123     if (size > m_iBlockSize) {\r
124         return NULL;\r
125     }\r
126     register FX_LPFIXEDSTORECHUNK pChunk = m_pChunk;\r
127     while (pChunk != NULL) {\r
128         if (pChunk->iFreeNum > 0) {\r
129             break;\r
130         }\r
131         pChunk = pChunk->pNextChunk;\r
132     }\r
133     if (pChunk == NULL) {\r
134         pChunk = AllocChunk();\r
135     }\r
136     FXSYS_assert(pChunk != NULL);\r
137     register FX_LPBYTE pFlags = pChunk->FirstFlag();\r
138     register size_t i = 0;\r
139     for (; i < pChunk->iChunkSize; i ++)\r
140         if (pFlags[i] == 0) {\r
141             break;\r
142         }\r
143     FXSYS_assert(i < pChunk->iChunkSize);\r
144     pFlags[i] = 1;\r
145     pChunk->iFreeNum --;\r
146     return pChunk->FirstBlock() + i * m_iBlockSize;\r
147 }\r
148 void CFX_FixedStore::Free(void* pBlock)\r
149 {\r
150     FXSYS_assert(pBlock != NULL);\r
151     register FX_LPFIXEDSTORECHUNK pPrior, pChunk;\r
152     pPrior = NULL, pChunk = m_pChunk;\r
153     register FX_LPBYTE pStart = NULL, pEnd;\r
154     while (pChunk != NULL) {\r
155         pStart = pChunk->FirstBlock();\r
156         if (pBlock >= pStart) {\r
157             pEnd = pStart + m_iBlockSize * pChunk->iChunkSize;\r
158             if (pBlock < pEnd) {\r
159                 break;\r
160             }\r
161         }\r
162         pPrior = pChunk, pChunk = pChunk->pNextChunk;\r
163     }\r
164     FXSYS_assert(pChunk != NULL);\r
165     register size_t iPos = ((FX_LPBYTE)pBlock - pStart) / m_iBlockSize;\r
166     FXSYS_assert(iPos < pChunk->iChunkSize);\r
167     register FX_LPBYTE pFlags = pChunk->FirstFlag();\r
168     if (pFlags[iPos] == 0) {\r
169         return;\r
170     }\r
171     pFlags[iPos] = 0;\r
172     pChunk->iFreeNum ++;\r
173     if (pChunk->iFreeNum == pChunk->iChunkSize) {\r
174         if (pPrior == NULL) {\r
175             m_pChunk = pChunk->pNextChunk;\r
176         } else {\r
177             pPrior->pNextChunk = pChunk->pNextChunk;\r
178         }\r
179         FX_Free(pChunk);\r
180     }\r
181 }\r
182 size_t CFX_FixedStore::SetDefChunkSize(size_t iChunkSize)\r
183 {\r
184     FXSYS_assert(iChunkSize != 0);\r
185     size_t v = m_iDefChunkSize;\r
186     m_iDefChunkSize = FX_4BYTEALIGN(iChunkSize);\r
187     return v;\r
188 }\r
189 #ifndef _FXEMB\r
190 CFX_DynamicStore::CFX_DynamicStore(size_t iDefChunkSize)\r
191     : m_iDefChunkSize(iDefChunkSize)\r
192     , m_pChunk(NULL)\r
193 {\r
194     FXSYS_assert(m_iDefChunkSize != 0);\r
195 }\r
196 CFX_DynamicStore::~CFX_DynamicStore()\r
197 {\r
198     register FX_LPDYNAMICSTORECHUNK pChunk, pNext;\r
199     pChunk = m_pChunk;\r
200     while (pChunk != NULL) {\r
201         pNext = pChunk->pNextChunk;\r
202         FX_Free(pChunk);\r
203         pChunk = pNext;\r
204     }\r
205 }\r
206 FX_LPDYNAMICSTORECHUNK CFX_DynamicStore::AllocChunk(size_t size)\r
207 {\r
208     FXSYS_assert(size != 0);\r
209     register FX_LPDYNAMICSTORECHUNK pChunk = (FX_LPDYNAMICSTORECHUNK)FX_Alloc(FX_BYTE, sizeof(FX_DYNAMICSTORECHUNK) + sizeof(FX_DYNAMICSTOREBLOCK) * 2 + size);\r
210     if (pChunk == NULL) {\r
211         return NULL;\r
212     }\r
213     pChunk->iChunkSize = size;\r
214     pChunk->iFreeSize = size;\r
215     register FX_LPDYNAMICSTOREBLOCK pBlock = pChunk->FirstBlock();\r
216     pBlock->iBlockSize = size;\r
217     pBlock->bUsed = FALSE;\r
218     pBlock = pBlock->NextBlock();\r
219     pBlock->iBlockSize = 0;\r
220     pBlock->bUsed = TRUE;\r
221     if (m_pChunk != NULL && size >= m_iDefChunkSize) {\r
222         FX_LPDYNAMICSTORECHUNK pLast = m_pChunk;\r
223         while (pLast->pNextChunk != NULL) {\r
224             pLast = pLast->pNextChunk;\r
225         }\r
226         pLast->pNextChunk = pChunk;\r
227         pChunk->pNextChunk = NULL;\r
228     } else {\r
229         pChunk->pNextChunk = m_pChunk;\r
230         m_pChunk = pChunk;\r
231     }\r
232     return pChunk;\r
233 }\r
234 void* CFX_DynamicStore::Alloc(size_t size)\r
235 {\r
236     size = FX_4BYTEALIGN(size);\r
237     FXSYS_assert(size != 0);\r
238     register FX_LPDYNAMICSTORECHUNK pChunk = m_pChunk;\r
239     register FX_LPDYNAMICSTOREBLOCK pBlock = NULL;\r
240     while (pChunk != NULL) {\r
241         if (pChunk->iFreeSize >= size) {\r
242             pBlock = pChunk->FirstBlock();\r
243             register FX_BOOL bFind = FALSE;\r
244             while(pBlock->iBlockSize != 0) {\r
245                 if (!pBlock->bUsed && pBlock->iBlockSize >= size) {\r
246                     bFind = TRUE;\r
247                     break;\r
248                 }\r
249                 pBlock = pBlock->NextBlock();\r
250             }\r
251             if (bFind) {\r
252                 break;\r
253             }\r
254         }\r
255         pChunk = pChunk->pNextChunk;\r
256     }\r
257     if (pChunk == NULL) {\r
258         pChunk = AllocChunk(FX_MAX(m_iDefChunkSize, size));\r
259         pBlock = pChunk->FirstBlock();\r
260     }\r
261     FXSYS_assert(pChunk != NULL && pBlock != NULL);\r
262     register size_t m = size + sizeof(FX_DYNAMICSTOREBLOCK);\r
263     pBlock->bUsed = TRUE;\r
264     if (pBlock->iBlockSize > m) {\r
265         register size_t n = pBlock->iBlockSize;\r
266         pBlock->iBlockSize = size;\r
267         register FX_LPDYNAMICSTOREBLOCK pNextBlock = pBlock->NextBlock();\r
268         pNextBlock->bUsed = FALSE;\r
269         pNextBlock->iBlockSize = n - size - sizeof(FX_DYNAMICSTOREBLOCK);\r
270         pChunk->iFreeSize -= size + sizeof(FX_DYNAMICSTOREBLOCK);\r
271     } else {\r
272         pChunk->iFreeSize -= pBlock->iBlockSize;\r
273     }\r
274     return pBlock->Data();\r
275 }\r
276 void CFX_DynamicStore::Free(void* pBlock)\r
277 {\r
278     FXSYS_assert(pBlock != NULL);\r
279     register FX_LPDYNAMICSTORECHUNK pPriorChunk, pChunk;\r
280     pPriorChunk = NULL, pChunk = m_pChunk;\r
281     while (pChunk != NULL) {\r
282         if (pBlock > pChunk && pBlock <= ((FX_LPBYTE)pChunk + sizeof(FX_DYNAMICSTORECHUNK) + pChunk->iChunkSize)) {\r
283             break;\r
284         }\r
285         pPriorChunk = pChunk, pChunk = pChunk->pNextChunk;\r
286     }\r
287     FXSYS_assert(pChunk != NULL);\r
288     register FX_LPDYNAMICSTOREBLOCK pPriorBlock, pFindBlock;\r
289     pPriorBlock = NULL, pFindBlock = pChunk->FirstBlock();\r
290     while(pFindBlock->iBlockSize != 0) {\r
291         if (pBlock == (void*)pFindBlock->Data()) {\r
292             break;\r
293         }\r
294         pPriorBlock = pFindBlock;\r
295         pFindBlock = pFindBlock->NextBlock();\r
296     }\r
297     FXSYS_assert(pFindBlock->iBlockSize != 0 && pFindBlock->bUsed && pBlock == (void*)pFindBlock->Data());\r
298     pFindBlock->bUsed = FALSE;\r
299     pChunk->iFreeSize += pFindBlock->iBlockSize;\r
300     if (pPriorBlock == NULL) {\r
301         pPriorBlock = pChunk->FirstBlock();\r
302     } else if (pPriorBlock->bUsed) {\r
303         pPriorBlock = pFindBlock;\r
304     }\r
305     pFindBlock = pPriorBlock;\r
306     register size_t sizeFree = 0;\r
307     register size_t sizeBlock = 0;\r
308     while (pFindBlock->iBlockSize != 0 && !pFindBlock->bUsed) {\r
309         if (pFindBlock != pPriorBlock) {\r
310             sizeFree += sizeof(FX_DYNAMICSTOREBLOCK);\r
311             sizeBlock += sizeof(FX_DYNAMICSTOREBLOCK);\r
312         }\r
313         sizeBlock += pFindBlock->iBlockSize;\r
314         pFindBlock = pFindBlock->NextBlock();\r
315     }\r
316     pPriorBlock->iBlockSize = sizeBlock;\r
317     pChunk->iFreeSize += sizeFree;\r
318     if (pChunk->iFreeSize == pChunk->iChunkSize) {\r
319         if (pPriorChunk == NULL) {\r
320             m_pChunk = pChunk->pNextChunk;\r
321         } else {\r
322             pPriorChunk->pNextChunk = pChunk->pNextChunk;\r
323         }\r
324         FX_Free(pChunk);\r
325     }\r
326 }\r
327 size_t CFX_DynamicStore::SetDefChunkSize(size_t size)\r
328 {\r
329     FXSYS_assert(size != 0);\r
330     size_t v = m_iDefChunkSize;\r
331     m_iDefChunkSize = size;\r
332     return v;\r
333 }\r
334 #endif\r