1 /*
2  * Copyright (c) 2020 - 2024 the ThorVG project. All rights reserved.
3 
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10 
11  * The above copyright notice and this permission notice shall be included in all
12  * copies or substantial portions of the Software.
13 
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20  * SOFTWARE.
21  */
22 
23 #include "../../lv_conf_internal.h"
24 #if LV_USE_THORVG_INTERNAL
25 
26 #ifndef _TVG_ARRAY_H_
27 #define _TVG_ARRAY_H_
28 
29 #include <memory.h>
30 #include <cstdint>
31 #include <cstdlib>
32 
33 namespace tvg
34 {
35 
36 template<class T>
37 struct Array
38 {
39     T* data = nullptr;
40     uint32_t count = 0;
41     uint32_t reserved = 0;
42 
ArrayArray43     Array(){}
44 
ArrayArray45     Array(int32_t size)
46     {
47         reserve(size);
48     }
49 
ArrayArray50     Array(const Array& rhs)
51     {
52         reset();
53         *this = rhs;
54     }
55 
pushArray56     void push(T element)
57     {
58         if (count + 1 > reserved) {
59             reserved = count + (count + 2) / 2;
60             data = static_cast<T*>(realloc(data, sizeof(T) * reserved));
61         }
62         data[count++] = element;
63     }
64 
pushArray65     void push(const Array<T>& rhs)
66     {
67         if (rhs.count == 0) return;
68         grow(rhs.count);
69         memcpy(data + count, rhs.data, rhs.count * sizeof(T));
70         count += rhs.count;
71     }
72 
reserveArray73     bool reserve(uint32_t size)
74     {
75         if (size > reserved) {
76             reserved = size;
77             data = static_cast<T*>(realloc(data, sizeof(T) * reserved));
78         }
79         return true;
80     }
81 
growArray82     bool grow(uint32_t size)
83     {
84         return reserve(count + size);
85     }
86 
87     const T& operator[](size_t idx) const
88     {
89         return data[idx];
90     }
91 
92     T& operator[](size_t idx)
93     {
94         return data[idx];
95     }
96 
beginArray97     const T* begin() const
98     {
99         return data;
100     }
101 
beginArray102     T* begin()
103     {
104         return data;
105     }
106 
endArray107     T* end()
108     {
109         return data + count;
110     }
111 
endArray112     const T* end() const
113     {
114         return data + count;
115     }
116 
lastArray117     const T& last() const
118     {
119         return data[count - 1];
120     }
121 
firstArray122     const T& first() const
123     {
124         return data[0];
125     }
126 
lastArray127     T& last()
128     {
129         return data[count - 1];
130     }
131 
firstArray132     T& first()
133     {
134         return data[0];
135     }
136 
popArray137     void pop()
138     {
139         if (count > 0) --count;
140     }
141 
resetArray142     void reset()
143     {
144         free(data);
145         data = nullptr;
146         count = reserved = 0;
147     }
148 
clearArray149     void clear()
150     {
151         count = 0;
152     }
153 
emptyArray154     bool empty() const
155     {
156         return count == 0;
157     }
158 
159     template<class COMPARE>
sortArray160     void sort()
161     {
162         qsort<COMPARE>(data, 0, static_cast<int32_t>(count) - 1);
163     }
164 
165     void operator=(const Array& rhs)
166     {
167         reserve(rhs.count);
168         if (rhs.count > 0) memcpy(data, rhs.data, sizeof(T) * rhs.count);
169         count = rhs.count;
170     }
171 
~ArrayArray172     ~Array()
173     {
174         free(data);
175     }
176 
177 private:
178     template<class COMPARE>
qsortArray179     void qsort(T* arr, int32_t low, int32_t high)
180     {
181         if (low < high) {
182             int32_t i = low;
183             int32_t j = high;
184             T tmp = arr[low];
185             while (i < j) {
186                 while (i < j && !COMPARE{}(arr[j], tmp)) --j;
187                 if (i < j) {
188                     arr[i] = arr[j];
189                     ++i;
190                 }
191                 while (i < j && COMPARE{}(arr[i], tmp)) ++i;
192                 if (i < j) {
193                     arr[j] = arr[i];
194                     --j;
195                 }
196             }
197             arr[i] = tmp;
198             qsort<COMPARE>(arr, low, i - 1);
199             qsort<COMPARE>(arr, i + 1, high);
200         }
201     }
202 };
203 
204 }
205 
206 #endif //_TVG_ARRAY_H_
207 
208 #endif /* LV_USE_THORVG_INTERNAL */
209 
210