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"
8CFX_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}
21CFX_BasicArray::~CFX_BasicArray()
22{
23    FX_Allocator_Free(m_pAllocator, m_pData);
24}
25FX_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}
77FX_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}
86FX_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}
94FX_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}
114FX_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}
126FX_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}
140const 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}
147CFX_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}
157void 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}
164CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray()
165{
166    RemoveAll();
167}
168static 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}
182void 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}
192void* 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}
267void** 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}
288void* 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}
297void* 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}
318void* 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}
326void* 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}
337void 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}
366