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