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/include/fxcrt/fx_basic.h" | 7 #include "core/include/fxcrt/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 CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, | |
138 int segment_units, | |
139 int index_size) | |
140 : m_UnitSize(unit_size), | |
141 m_SegmentSize(segment_units), | |
142 m_IndexSize(index_size), | |
143 m_IndexDepth(0), | |
144 m_DataSize(0), | |
145 m_pIndex(NULL) {} | |
146 void CFX_BaseSegmentedArray::SetUnitSize(int unit_size, | |
147 int segment_units, | |
148 int index_size) { | |
149 ASSERT(m_DataSize == 0); | |
150 m_UnitSize = unit_size; | |
151 m_SegmentSize = segment_units; | |
152 m_IndexSize = index_size; | |
153 } | |
154 CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray() { | |
155 RemoveAll(); | |
156 } | |
157 static void _ClearIndex(int level, int size, void** pIndex) { | |
158 if (level == 0) { | |
159 FX_Free(pIndex); | |
160 return; | |
161 } | |
162 for (int i = 0; i < size; ++i) { | |
163 if (pIndex[i]) | |
164 _ClearIndex(level - 1, size, (void**)pIndex[i]); | |
165 } | |
166 FX_Free(pIndex); | |
167 } | |
168 void CFX_BaseSegmentedArray::RemoveAll() { | |
169 if (!m_pIndex) { | |
170 return; | |
171 } | |
172 _ClearIndex(m_IndexDepth, m_IndexSize, (void**)m_pIndex); | |
173 m_pIndex = NULL; | |
174 m_IndexDepth = 0; | |
175 m_DataSize = 0; | |
176 } | |
177 void* CFX_BaseSegmentedArray::Add() { | |
178 if (m_DataSize % m_SegmentSize) { | |
179 return GetAt(m_DataSize++); | |
180 } | |
181 void* pSegment = FX_Alloc2D(uint8_t, m_UnitSize, m_SegmentSize); | |
182 if (!m_pIndex) { | |
183 m_pIndex = pSegment; | |
184 m_DataSize++; | |
185 return pSegment; | |
186 } | |
187 if (m_IndexDepth == 0) { | |
188 void** pIndex = FX_Alloc(void*, m_IndexSize); | |
189 pIndex[0] = m_pIndex; | |
190 pIndex[1] = pSegment; | |
191 m_pIndex = pIndex; | |
192 m_DataSize++; | |
193 m_IndexDepth++; | |
194 return pSegment; | |
195 } | |
196 int seg_index = m_DataSize / m_SegmentSize; | |
197 if (seg_index % m_IndexSize) { | |
198 void** pIndex = GetIndex(seg_index); | |
199 pIndex[seg_index % m_IndexSize] = pSegment; | |
200 m_DataSize++; | |
201 return pSegment; | |
202 } | |
203 int tree_size = 1; | |
204 int i; | |
205 for (i = 0; i < m_IndexDepth; i++) { | |
206 tree_size *= m_IndexSize; | |
207 } | |
208 if (m_DataSize == tree_size * m_SegmentSize) { | |
209 void** pIndex = FX_Alloc(void*, m_IndexSize); | |
210 pIndex[0] = m_pIndex; | |
211 m_pIndex = pIndex; | |
212 m_IndexDepth++; | |
213 } else { | |
214 tree_size /= m_IndexSize; | |
215 } | |
216 void** pSpot = (void**)m_pIndex; | |
217 for (i = 1; i < m_IndexDepth; i++) { | |
218 if (!pSpot[seg_index / tree_size]) { | |
219 pSpot[seg_index / tree_size] = FX_Alloc(void*, m_IndexSize); | |
220 } | |
221 pSpot = (void**)pSpot[seg_index / tree_size]; | |
222 seg_index = seg_index % tree_size; | |
223 tree_size /= m_IndexSize; | |
224 } | |
225 if (i < m_IndexDepth) { | |
226 FX_Free(pSegment); | |
227 RemoveAll(); | |
228 return NULL; | |
229 } | |
230 pSpot[seg_index % m_IndexSize] = pSegment; | |
231 m_DataSize++; | |
232 return pSegment; | |
233 } | |
234 void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const { | |
235 ASSERT(m_IndexDepth != 0); | |
236 if (m_IndexDepth == 1) { | |
237 return (void**)m_pIndex; | |
238 } | |
239 if (m_IndexDepth == 2) { | |
240 return (void**)((void**)m_pIndex)[seg_index / m_IndexSize]; | |
241 } | |
242 int tree_size = 1; | |
243 int i; | |
244 for (i = 1; i < m_IndexDepth; i++) { | |
245 tree_size *= m_IndexSize; | |
246 } | |
247 void** pSpot = (void**)m_pIndex; | |
248 for (i = 1; i < m_IndexDepth; i++) { | |
249 pSpot = (void**)pSpot[seg_index / tree_size]; | |
250 seg_index = seg_index % tree_size; | |
251 tree_size /= m_IndexSize; | |
252 } | |
253 return pSpot; | |
254 } | |
255 void* CFX_BaseSegmentedArray::IterateSegment(const uint8_t* pSegment, | |
256 int count, | |
257 FX_BOOL (*callback)(void* param, | |
258 void* pData), | |
259 void* param) const { | |
260 for (int i = 0; i < count; i++) { | |
261 if (!callback(param, (void*)(pSegment + i * m_UnitSize))) { | |
262 return (void*)(pSegment + i * m_UnitSize); | |
263 } | |
264 } | |
265 return NULL; | |
266 } | |
267 void* CFX_BaseSegmentedArray::IterateIndex(int level, | |
268 int& start, | |
269 void** pIndex, | |
270 FX_BOOL (*callback)(void* param, | |
271 void* pData), | |
272 void* param) const { | |
273 if (level == 0) { | |
274 int count = m_DataSize - start; | |
275 if (count > m_SegmentSize) { | |
276 count = m_SegmentSize; | |
277 } | |
278 start += count; | |
279 return IterateSegment((const uint8_t*)pIndex, count, callback, param); | |
280 } | |
281 for (int i = 0; i < m_IndexSize; i++) { | |
282 if (!pIndex[i]) { | |
283 continue; | |
284 } | |
285 void* p = | |
286 IterateIndex(level - 1, start, (void**)pIndex[i], callback, param); | |
287 if (p) { | |
288 return p; | |
289 } | |
290 } | |
291 return NULL; | |
292 } | |
293 void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, | |
294 void* pData), | |
295 void* param) const { | |
296 if (!m_pIndex) { | |
297 return NULL; | |
298 } | |
299 int start = 0; | |
300 return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param); | |
301 } | |
302 void* CFX_BaseSegmentedArray::GetAt(int index) const { | |
303 if (index < 0 || index >= m_DataSize) { | |
304 return NULL; | |
305 } | |
306 if (m_IndexDepth == 0) { | |
307 return (uint8_t*)m_pIndex + m_UnitSize * index; | |
308 } | |
309 int seg_index = index / m_SegmentSize; | |
310 return (uint8_t*)GetIndex(seg_index)[seg_index % m_IndexSize] + | |
311 (index % m_SegmentSize) * m_UnitSize; | |
312 } | |
313 void CFX_BaseSegmentedArray::Delete(int index, int count) { | |
314 if (index < 0 || count < 1 || index + count > m_DataSize) { | |
315 return; | |
316 } | |
317 int i; | |
318 for (i = index; i < m_DataSize - count; i++) { | |
319 uint8_t* pSrc = (uint8_t*)GetAt(i + count); | |
320 uint8_t* pDest = (uint8_t*)GetAt(i); | |
321 for (int j = 0; j < m_UnitSize; j++) { | |
322 pDest[j] = pSrc[j]; | |
323 } | |
324 } | |
325 int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize; | |
326 int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize; | |
327 if (new_segs < old_segs) { | |
328 if (m_IndexDepth) { | |
329 for (i = new_segs; i < old_segs; i++) { | |
330 void** pIndex = GetIndex(i); | |
331 FX_Free(pIndex[i % m_IndexSize]); | |
332 pIndex[i % m_IndexSize] = NULL; | |
333 } | |
334 } else { | |
335 FX_Free(m_pIndex); | |
336 m_pIndex = NULL; | |
337 } | |
338 } | |
339 m_DataSize -= count; | |
340 } | |
OLD | NEW |