OLD | NEW |
1 // Copyright 2014 PDFium Authors. All rights reserved. | 1 // Copyright 2014 PDFium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com | 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com |
6 | 6 |
7 #include "core/fxcrt/include/fx_basic.h" | 7 #include "core/fxcrt/include/fx_basic.h" |
8 #include "third_party/base/numerics/safe_math.h" | 8 #include "third_party/base/numerics/safe_math.h" |
9 | 9 |
10 CFX_BasicArray::CFX_BasicArray(int unit_size) | 10 CFX_BasicArray::CFX_BasicArray(int unit_size) |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
127 FXSYS_memcpy(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, | 127 FXSYS_memcpy(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, |
128 pNewArray->m_nSize * m_nUnitSize); | 128 pNewArray->m_nSize * m_nUnitSize); |
129 return TRUE; | 129 return TRUE; |
130 } | 130 } |
131 const void* CFX_BasicArray::GetDataPtr(int index) const { | 131 const void* CFX_BasicArray::GetDataPtr(int index) const { |
132 if (index < 0 || index >= m_nSize || !m_pData) { | 132 if (index < 0 || index >= m_nSize || !m_pData) { |
133 return NULL; | 133 return NULL; |
134 } | 134 } |
135 return m_pData + index * m_nUnitSize; | 135 return m_pData + index * m_nUnitSize; |
136 } | 136 } |
137 #ifdef PDF_ENABLE_XFA | |
138 CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, | |
139 int segment_units, | |
140 int index_size) | |
141 : m_UnitSize(unit_size), | |
142 m_SegmentSize(segment_units), | |
143 m_IndexSize(index_size), | |
144 m_IndexDepth(0), | |
145 m_DataSize(0), | |
146 m_pIndex(NULL) {} | |
147 void CFX_BaseSegmentedArray::SetUnitSize(int unit_size, | |
148 int segment_units, | |
149 int index_size) { | |
150 ASSERT(m_DataSize == 0); | |
151 m_UnitSize = unit_size; | |
152 m_SegmentSize = segment_units; | |
153 m_IndexSize = index_size; | |
154 } | |
155 CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray() { | |
156 RemoveAll(); | |
157 } | |
158 static void _ClearIndex(int level, int size, void** pIndex) { | |
159 if (level == 0) { | |
160 FX_Free(pIndex); | |
161 return; | |
162 } | |
163 for (int i = 0; i < size; ++i) { | |
164 if (pIndex[i]) | |
165 _ClearIndex(level - 1, size, (void**)pIndex[i]); | |
166 } | |
167 FX_Free(pIndex); | |
168 } | |
169 void CFX_BaseSegmentedArray::RemoveAll() { | |
170 if (!m_pIndex) { | |
171 return; | |
172 } | |
173 _ClearIndex(m_IndexDepth, m_IndexSize, (void**)m_pIndex); | |
174 m_pIndex = NULL; | |
175 m_IndexDepth = 0; | |
176 m_DataSize = 0; | |
177 } | |
178 void* CFX_BaseSegmentedArray::Add() { | |
179 if (m_DataSize % m_SegmentSize) { | |
180 return GetAt(m_DataSize++); | |
181 } | |
182 void* pSegment = FX_Alloc2D(uint8_t, m_UnitSize, m_SegmentSize); | |
183 if (!m_pIndex) { | |
184 m_pIndex = pSegment; | |
185 m_DataSize++; | |
186 return pSegment; | |
187 } | |
188 if (m_IndexDepth == 0) { | |
189 void** pIndex = FX_Alloc(void*, m_IndexSize); | |
190 pIndex[0] = m_pIndex; | |
191 pIndex[1] = pSegment; | |
192 m_pIndex = pIndex; | |
193 m_DataSize++; | |
194 m_IndexDepth++; | |
195 return pSegment; | |
196 } | |
197 int seg_index = m_DataSize / m_SegmentSize; | |
198 if (seg_index % m_IndexSize) { | |
199 void** pIndex = GetIndex(seg_index); | |
200 pIndex[seg_index % m_IndexSize] = pSegment; | |
201 m_DataSize++; | |
202 return pSegment; | |
203 } | |
204 int tree_size = 1; | |
205 int i; | |
206 for (i = 0; i < m_IndexDepth; i++) { | |
207 tree_size *= m_IndexSize; | |
208 } | |
209 if (m_DataSize == tree_size * m_SegmentSize) { | |
210 void** pIndex = FX_Alloc(void*, m_IndexSize); | |
211 pIndex[0] = m_pIndex; | |
212 m_pIndex = pIndex; | |
213 m_IndexDepth++; | |
214 } else { | |
215 tree_size /= m_IndexSize; | |
216 } | |
217 void** pSpot = (void**)m_pIndex; | |
218 for (i = 1; i < m_IndexDepth; i++) { | |
219 if (!pSpot[seg_index / tree_size]) { | |
220 pSpot[seg_index / tree_size] = FX_Alloc(void*, m_IndexSize); | |
221 } | |
222 pSpot = (void**)pSpot[seg_index / tree_size]; | |
223 seg_index = seg_index % tree_size; | |
224 tree_size /= m_IndexSize; | |
225 } | |
226 if (i < m_IndexDepth) { | |
227 FX_Free(pSegment); | |
228 RemoveAll(); | |
229 return NULL; | |
230 } | |
231 pSpot[seg_index % m_IndexSize] = pSegment; | |
232 m_DataSize++; | |
233 return pSegment; | |
234 } | |
235 void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const { | |
236 ASSERT(m_IndexDepth != 0); | |
237 if (m_IndexDepth == 1) { | |
238 return (void**)m_pIndex; | |
239 } | |
240 if (m_IndexDepth == 2) { | |
241 return (void**)((void**)m_pIndex)[seg_index / m_IndexSize]; | |
242 } | |
243 int tree_size = 1; | |
244 int i; | |
245 for (i = 1; i < m_IndexDepth; i++) { | |
246 tree_size *= m_IndexSize; | |
247 } | |
248 void** pSpot = (void**)m_pIndex; | |
249 for (i = 1; i < m_IndexDepth; i++) { | |
250 pSpot = (void**)pSpot[seg_index / tree_size]; | |
251 seg_index = seg_index % tree_size; | |
252 tree_size /= m_IndexSize; | |
253 } | |
254 return pSpot; | |
255 } | |
256 void* CFX_BaseSegmentedArray::IterateSegment(const uint8_t* pSegment, | |
257 int count, | |
258 FX_BOOL (*callback)(void* param, | |
259 void* pData), | |
260 void* param) const { | |
261 for (int i = 0; i < count; i++) { | |
262 if (!callback(param, (void*)(pSegment + i * m_UnitSize))) { | |
263 return (void*)(pSegment + i * m_UnitSize); | |
264 } | |
265 } | |
266 return NULL; | |
267 } | |
268 void* CFX_BaseSegmentedArray::IterateIndex(int level, | |
269 int& start, | |
270 void** pIndex, | |
271 FX_BOOL (*callback)(void* param, | |
272 void* pData), | |
273 void* param) const { | |
274 if (level == 0) { | |
275 int count = m_DataSize - start; | |
276 if (count > m_SegmentSize) { | |
277 count = m_SegmentSize; | |
278 } | |
279 start += count; | |
280 return IterateSegment((const uint8_t*)pIndex, count, callback, param); | |
281 } | |
282 for (int i = 0; i < m_IndexSize; i++) { | |
283 if (!pIndex[i]) { | |
284 continue; | |
285 } | |
286 void* p = | |
287 IterateIndex(level - 1, start, (void**)pIndex[i], callback, param); | |
288 if (p) { | |
289 return p; | |
290 } | |
291 } | |
292 return NULL; | |
293 } | |
294 void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, | |
295 void* pData), | |
296 void* param) const { | |
297 if (!m_pIndex) { | |
298 return NULL; | |
299 } | |
300 int start = 0; | |
301 return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param); | |
302 } | |
303 void* CFX_BaseSegmentedArray::GetAt(int index) const { | |
304 if (index < 0 || index >= m_DataSize) { | |
305 return NULL; | |
306 } | |
307 if (m_IndexDepth == 0) { | |
308 return (uint8_t*)m_pIndex + m_UnitSize * index; | |
309 } | |
310 int seg_index = index / m_SegmentSize; | |
311 return (uint8_t*)GetIndex(seg_index)[seg_index % m_IndexSize] + | |
312 (index % m_SegmentSize) * m_UnitSize; | |
313 } | |
314 void CFX_BaseSegmentedArray::Delete(int index, int count) { | |
315 if (index < 0 || count < 1 || index + count > m_DataSize) { | |
316 return; | |
317 } | |
318 int i; | |
319 for (i = index; i < m_DataSize - count; i++) { | |
320 uint8_t* pSrc = (uint8_t*)GetAt(i + count); | |
321 uint8_t* pDest = (uint8_t*)GetAt(i); | |
322 for (int j = 0; j < m_UnitSize; j++) { | |
323 pDest[j] = pSrc[j]; | |
324 } | |
325 } | |
326 int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize; | |
327 int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize; | |
328 if (new_segs < old_segs) { | |
329 if (m_IndexDepth) { | |
330 for (i = new_segs; i < old_segs; i++) { | |
331 void** pIndex = GetIndex(i); | |
332 FX_Free(pIndex[i % m_IndexSize]); | |
333 pIndex[i % m_IndexSize] = NULL; | |
334 } | |
335 } else { | |
336 FX_Free(m_pIndex); | |
337 m_pIndex = NULL; | |
338 } | |
339 } | |
340 m_DataSize -= count; | |
341 } | |
342 #endif // PDF_ENABLE_XFA | |
OLD | NEW |