Initial commit.
[pdfium.git] / core / src / fxcrt / fx_basic_array.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_basic.h"\r
8 CFX_BasicArray::CFX_BasicArray(int unit_size, IFX_Allocator* pAllocator)\r
9     : m_pAllocator(pAllocator)\r
10     , m_pData(NULL)\r
11     , m_nSize(0)\r
12     , m_nMaxSize(0)\r
13     , m_nGrowBy(0)\r
14 {\r
15     if (unit_size < 0 || unit_size > (1 << 28)) {\r
16         m_nUnitSize = 4;\r
17     } else {\r
18         m_nUnitSize = unit_size;\r
19     }\r
20 }\r
21 CFX_BasicArray::~CFX_BasicArray()\r
22 {\r
23     FX_Allocator_Free(m_pAllocator, m_pData);\r
24 }\r
25 FX_BOOL CFX_BasicArray::SetSize(int nNewSize, int nGrowBy)\r
26 {\r
27     if (nNewSize < 0 || nNewSize > (1 << 28) / m_nUnitSize) {\r
28         m_pData = NULL;\r
29         m_nSize = m_nMaxSize = 0;\r
30         return FALSE;\r
31     }\r
32     if (nGrowBy >= 0) {\r
33         m_nGrowBy = nGrowBy;\r
34     }\r
35     if (nNewSize == 0) {\r
36         if (m_pData != NULL) {\r
37             FX_Allocator_Free(m_pAllocator, m_pData);\r
38             m_pData = NULL;\r
39         }\r
40         m_nSize = m_nMaxSize = 0;\r
41     } else if (m_pData == NULL) {\r
42         m_pData = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, nNewSize * m_nUnitSize);\r
43         if (!m_pData) {\r
44             m_nSize = m_nMaxSize = 0;\r
45             return FALSE;\r
46         }\r
47         FXSYS_memset32(m_pData, 0, nNewSize * m_nUnitSize);\r
48         m_nSize = m_nMaxSize = nNewSize;\r
49     } else if (nNewSize <= m_nMaxSize) {\r
50         if (nNewSize > m_nSize) {\r
51             FXSYS_memset32(m_pData + m_nSize * m_nUnitSize, 0, (nNewSize - m_nSize) * m_nUnitSize);\r
52         }\r
53         m_nSize = nNewSize;\r
54     } else {\r
55         int nGrowBy = m_nGrowBy;\r
56         if (nGrowBy == 0) {\r
57             nGrowBy = m_nSize / 8;\r
58             nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);\r
59         }\r
60         int nNewMax;\r
61         if (nNewSize < m_nMaxSize + nGrowBy) {\r
62             nNewMax = m_nMaxSize + nGrowBy;\r
63         } else {\r
64             nNewMax = nNewSize;\r
65         }\r
66         FX_LPBYTE pNewData = FX_Allocator_Realloc(m_pAllocator, FX_BYTE, m_pData, nNewMax * m_nUnitSize);\r
67         if (pNewData == NULL) {\r
68             return FALSE;\r
69         }\r
70         FXSYS_memset32(pNewData + m_nSize * m_nUnitSize, 0, (nNewMax - m_nSize) * m_nUnitSize);\r
71         m_pData = pNewData;\r
72         m_nSize = nNewSize;\r
73         m_nMaxSize = nNewMax;\r
74     }\r
75     return TRUE;\r
76 }\r
77 FX_BOOL CFX_BasicArray::Append(const CFX_BasicArray& src)\r
78 {\r
79     int nOldSize = m_nSize;\r
80     if (!SetSize(m_nSize + src.m_nSize, -1)) {\r
81         return FALSE;\r
82     }\r
83     FXSYS_memcpy32(m_pData + nOldSize * m_nUnitSize, src.m_pData, src.m_nSize * m_nUnitSize);\r
84     return TRUE;\r
85 }\r
86 FX_BOOL CFX_BasicArray::Copy(const CFX_BasicArray& src)\r
87 {\r
88     if (!SetSize(src.m_nSize, -1)) {\r
89         return FALSE;\r
90     }\r
91     FXSYS_memcpy32(m_pData, src.m_pData, src.m_nSize * m_nUnitSize);\r
92     return TRUE;\r
93 }\r
94 FX_LPBYTE CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount)\r
95 {\r
96     if (nIndex < 0 || nCount <= 0) {\r
97         return NULL;\r
98     }\r
99     if (nIndex >= m_nSize) {\r
100         if (!SetSize(nIndex + nCount, -1)) {\r
101             return NULL;\r
102         }\r
103     } else {\r
104         int nOldSize = m_nSize;\r
105         if (!SetSize(m_nSize + nCount, -1)) {\r
106             return NULL;\r
107         }\r
108         FXSYS_memmove32(m_pData + (nIndex + nCount)*m_nUnitSize, m_pData + nIndex * m_nUnitSize,\r
109                         (nOldSize - nIndex) * m_nUnitSize);\r
110         FXSYS_memset32(m_pData + nIndex * m_nUnitSize, 0, nCount * m_nUnitSize);\r
111     }\r
112     return m_pData + nIndex * m_nUnitSize;\r
113 }\r
114 FX_BOOL CFX_BasicArray::RemoveAt(int nIndex, int nCount)\r
115 {\r
116     if (nIndex < 0 || nCount <= 0 || m_nSize < nIndex + nCount) {\r
117         return FALSE;\r
118     }\r
119     int nMoveCount = m_nSize - (nIndex + nCount);\r
120     if (nMoveCount) {\r
121         FXSYS_memmove32(m_pData + nIndex * m_nUnitSize, m_pData + (nIndex + nCount) * m_nUnitSize, nMoveCount * m_nUnitSize);\r
122     }\r
123     m_nSize -= nCount;\r
124     return TRUE;\r
125 }\r
126 FX_BOOL CFX_BasicArray::InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray)\r
127 {\r
128     if (pNewArray == NULL) {\r
129         return FALSE;\r
130     }\r
131     if (pNewArray->m_nSize == 0) {\r
132         return TRUE;\r
133     }\r
134     if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) {\r
135         return FALSE;\r
136     }\r
137     FXSYS_memcpy32(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, pNewArray->m_nSize * m_nUnitSize);\r
138     return TRUE;\r
139 }\r
140 const void* CFX_BasicArray::GetDataPtr(int index) const\r
141 {\r
142     if (index < 0 || index >= m_nSize || m_pData == NULL) {\r
143         return NULL;\r
144     }\r
145     return m_pData + index * m_nUnitSize;\r
146 }\r
147 CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, int segment_units, int index_size, IFX_Allocator* pAllocator)\r
148     : m_pAllocator(pAllocator)\r
149     , m_UnitSize(unit_size)\r
150     , m_SegmentSize(segment_units)\r
151     , m_IndexSize(index_size)\r
152     , m_IndexDepth(0)\r
153     , m_DataSize(0)\r
154     , m_pIndex(NULL)\r
155 {\r
156 }\r
157 void CFX_BaseSegmentedArray::SetUnitSize(int unit_size, int segment_units, int index_size)\r
158 {\r
159     ASSERT(m_DataSize == 0);\r
160     m_UnitSize = unit_size;\r
161     m_SegmentSize = segment_units;\r
162     m_IndexSize = index_size;\r
163 }\r
164 CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray()\r
165 {\r
166     RemoveAll();\r
167 }\r
168 static void _ClearIndex(IFX_Allocator* pAllcator, int level, int size, void** pIndex)\r
169 {\r
170     if (level == 0) {\r
171         FX_Allocator_Free(pAllcator, pIndex);\r
172         return;\r
173     }\r
174     for (int i = 0; i < size; i ++) {\r
175         if (pIndex[i] == NULL) {\r
176             continue;\r
177         }\r
178         _ClearIndex(pAllcator, level - 1, size, (void**)pIndex[i]);\r
179     }\r
180     FX_Allocator_Free(pAllcator, pIndex);\r
181 }\r
182 void CFX_BaseSegmentedArray::RemoveAll()\r
183 {\r
184     if (m_pIndex == NULL) {\r
185         return;\r
186     }\r
187     _ClearIndex(m_pAllocator, m_IndexDepth, m_IndexSize, (void**)m_pIndex);\r
188     m_pIndex = NULL;\r
189     m_IndexDepth = 0;\r
190     m_DataSize = 0;\r
191 }\r
192 void* CFX_BaseSegmentedArray::Add()\r
193 {\r
194     if (m_DataSize % m_SegmentSize) {\r
195         return GetAt(m_DataSize ++);\r
196     }\r
197     void* pSegment = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, m_UnitSize * m_SegmentSize);\r
198     if (!pSegment) {\r
199         return NULL;\r
200     }\r
201     if (m_pIndex == NULL) {\r
202         m_pIndex = pSegment;\r
203         m_DataSize ++;\r
204         return pSegment;\r
205     }\r
206     if (m_IndexDepth == 0) {\r
207         void** pIndex = (void**)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize);\r
208         if (pIndex == NULL) {\r
209             FX_Allocator_Free(m_pAllocator, pSegment);\r
210             return NULL;\r
211         }\r
212         FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize);\r
213         pIndex[0] = m_pIndex;\r
214         pIndex[1] = pSegment;\r
215         m_pIndex = pIndex;\r
216         m_DataSize ++;\r
217         m_IndexDepth ++;\r
218         return pSegment;\r
219     }\r
220     int seg_index = m_DataSize / m_SegmentSize;\r
221     if (seg_index % m_IndexSize) {\r
222         void** pIndex = GetIndex(seg_index);\r
223         pIndex[seg_index % m_IndexSize] = pSegment;\r
224         m_DataSize ++;\r
225         return pSegment;\r
226     }\r
227     int tree_size = 1;\r
228     int i;\r
229     for (i = 0; i < m_IndexDepth; i ++) {\r
230         tree_size *= m_IndexSize;\r
231     }\r
232     if (m_DataSize == tree_size * m_SegmentSize) {\r
233         void** pIndex = (void**)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize);\r
234         if (pIndex == NULL) {\r
235             FX_Allocator_Free(m_pAllocator, pSegment);\r
236             return NULL;\r
237         }\r
238         FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize);\r
239         pIndex[0] = m_pIndex;\r
240         m_pIndex = pIndex;\r
241         m_IndexDepth ++;\r
242     } else {\r
243         tree_size /= m_IndexSize;\r
244     }\r
245     void** pSpot = (void**)m_pIndex;\r
246     for (i = 1; i < m_IndexDepth; i ++) {\r
247         if (pSpot[seg_index / tree_size] == NULL) {\r
248             pSpot[seg_index / tree_size] = (void*)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize);\r
249             if (pSpot[seg_index / tree_size] == NULL) {\r
250                 break;\r
251             }\r
252             FXSYS_memset32(pSpot[seg_index / tree_size], 0, sizeof(void*) * m_IndexSize);\r
253         }\r
254         pSpot = (void**)pSpot[seg_index / tree_size];\r
255         seg_index = seg_index % tree_size;\r
256         tree_size /= m_IndexSize;\r
257     }\r
258     if (i < m_IndexDepth) {\r
259         FX_Allocator_Free(m_pAllocator, pSegment);\r
260         RemoveAll();\r
261         return NULL;\r
262     }\r
263     pSpot[seg_index % m_IndexSize] = pSegment;\r
264     m_DataSize ++;\r
265     return pSegment;\r
266 }\r
267 void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const\r
268 {\r
269     ASSERT(m_IndexDepth != 0);\r
270     if (m_IndexDepth == 1) {\r
271         return (void**)m_pIndex;\r
272     } else if (m_IndexDepth == 2) {\r
273         return (void**)((void**)m_pIndex)[seg_index / m_IndexSize];\r
274     }\r
275     int tree_size = 1;\r
276     int i;\r
277     for (i = 1; i < m_IndexDepth; i ++) {\r
278         tree_size *= m_IndexSize;\r
279     }\r
280     void** pSpot = (void**)m_pIndex;\r
281     for (i = 1; i < m_IndexDepth; i ++) {\r
282         pSpot = (void**)pSpot[seg_index / tree_size];\r
283         seg_index = seg_index % tree_size;\r
284         tree_size /= m_IndexSize;\r
285     }\r
286     return pSpot;\r
287 }\r
288 void* CFX_BaseSegmentedArray::IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const\r
289 {\r
290     for (int i = 0; i < count; i ++) {\r
291         if (!callback(param, (void*)(pSegment + i * m_UnitSize))) {\r
292             return (void*)(pSegment + i * m_UnitSize);\r
293         }\r
294     }\r
295     return NULL;\r
296 }\r
297 void* CFX_BaseSegmentedArray::IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const\r
298 {\r
299     if (level == 0) {\r
300         int count = m_DataSize - start;\r
301         if (count > m_SegmentSize) {\r
302             count = m_SegmentSize;\r
303         }\r
304         start += count;\r
305         return IterateSegment((FX_LPCBYTE)pIndex, count, callback, param);\r
306     }\r
307     for (int i = 0; i < m_IndexSize; i ++) {\r
308         if (pIndex[i] == NULL) {\r
309             continue;\r
310         }\r
311         void* p = IterateIndex(level - 1, start, (void**)pIndex[i], callback, param);\r
312         if (p) {\r
313             return p;\r
314         }\r
315     }\r
316     return NULL;\r
317 }\r
318 void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const\r
319 {\r
320     if (m_pIndex == NULL) {\r
321         return NULL;\r
322     }\r
323     int start = 0;\r
324     return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param);\r
325 }\r
326 void* CFX_BaseSegmentedArray::GetAt(int index) const\r
327 {\r
328     if (index < 0 || index >= m_DataSize) {\r
329         return NULL;\r
330     }\r
331     if (m_IndexDepth == 0) {\r
332         return (FX_LPBYTE)m_pIndex + m_UnitSize * index;\r
333     }\r
334     int seg_index = index / m_SegmentSize;\r
335     return (FX_LPBYTE)GetIndex(seg_index)[seg_index % m_IndexSize] + (index % m_SegmentSize) * m_UnitSize;\r
336 }\r
337 void CFX_BaseSegmentedArray::Delete(int index, int count)\r
338 {\r
339     if(index < 0 || count < 1 || index + count > m_DataSize) {\r
340         return;\r
341     }\r
342     int i;\r
343     for (i = index; i < m_DataSize - count; i ++) {\r
344         FX_BYTE* pSrc = (FX_BYTE*)GetAt(i + count);\r
345         FX_BYTE* pDest = (FX_BYTE*)GetAt(i);\r
346         for (int j = 0; j < m_UnitSize; j ++) {\r
347             pDest[j] = pSrc[j];\r
348         }\r
349     }\r
350     int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize;\r
351     int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize;\r
352     if (new_segs < old_segs) {\r
353         if(m_IndexDepth) {\r
354             for (i = new_segs; i < old_segs; i ++) {\r
355                 void** pIndex = GetIndex(i);\r
356                 FX_Allocator_Free(m_pAllocator, pIndex[i % m_IndexSize]);\r
357                 pIndex[i % m_IndexSize] = NULL;\r
358             }\r
359         } else {\r
360             FX_Allocator_Free(m_pAllocator, m_pIndex);\r
361             m_pIndex = NULL;\r
362         }\r
363     }\r
364     m_DataSize -= count;\r
365 }\r