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