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