1/**************************************************************************/
2/* local_vector.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef LOCAL_VECTOR_H
32#define LOCAL_VECTOR_H
33
34#include "core/error/error_macros.h"
35#include "core/os/memory.h"
36#include "core/templates/sort_array.h"
37#include "core/templates/vector.h"
38
39#include <initializer_list>
40#include <type_traits>
41
42// If tight, it grows strictly as much as needed.
43// Otherwise, it grows exponentially (the default and what you want in most cases).
44template <class T, class U = uint32_t, bool force_trivial = false, bool tight = false>
45class LocalVector {
46private:
47 U count = 0;
48 U capacity = 0;
49 T *data = nullptr;
50
51public:
52 T *ptr() {
53 return data;
54 }
55
56 const T *ptr() const {
57 return data;
58 }
59
60 _FORCE_INLINE_ void push_back(T p_elem) {
61 if (unlikely(count == capacity)) {
62 capacity = tight ? (capacity + 1) : MAX((U)1, capacity << 1);
63 data = (T *)memrealloc(data, capacity * sizeof(T));
64 CRASH_COND_MSG(!data, "Out of memory");
65 }
66
67 if constexpr (!std::is_trivially_constructible<T>::value && !force_trivial) {
68 memnew_placement(&data[count++], T(p_elem));
69 } else {
70 data[count++] = p_elem;
71 }
72 }
73
74 void remove_at(U p_index) {
75 ERR_FAIL_UNSIGNED_INDEX(p_index, count);
76 count--;
77 for (U i = p_index; i < count; i++) {
78 data[i] = data[i + 1];
79 }
80 if constexpr (!std::is_trivially_destructible<T>::value && !force_trivial) {
81 data[count].~T();
82 }
83 }
84
85 /// Removes the item copying the last value into the position of the one to
86 /// remove. It's generally faster than `remove_at`.
87 void remove_at_unordered(U p_index) {
88 ERR_FAIL_INDEX(p_index, count);
89 count--;
90 if (count > p_index) {
91 data[p_index] = data[count];
92 }
93 if constexpr (!std::is_trivially_destructible<T>::value && !force_trivial) {
94 data[count].~T();
95 }
96 }
97
98 _FORCE_INLINE_ bool erase(const T &p_val) {
99 int64_t idx = find(p_val);
100 if (idx >= 0) {
101 remove_at(idx);
102 return true;
103 }
104 return false;
105 }
106
107 void invert() {
108 for (U i = 0; i < count / 2; i++) {
109 SWAP(data[i], data[count - i - 1]);
110 }
111 }
112
113 _FORCE_INLINE_ void clear() { resize(0); }
114 _FORCE_INLINE_ void reset() {
115 clear();
116 if (data) {
117 memfree(data);
118 data = nullptr;
119 capacity = 0;
120 }
121 }
122 _FORCE_INLINE_ bool is_empty() const { return count == 0; }
123 _FORCE_INLINE_ U get_capacity() const { return capacity; }
124 _FORCE_INLINE_ void reserve(U p_size) {
125 p_size = tight ? p_size : nearest_power_of_2_templated(p_size);
126 if (p_size > capacity) {
127 capacity = p_size;
128 data = (T *)memrealloc(data, capacity * sizeof(T));
129 CRASH_COND_MSG(!data, "Out of memory");
130 }
131 }
132
133 _FORCE_INLINE_ U size() const { return count; }
134 void resize(U p_size) {
135 if (p_size < count) {
136 if constexpr (!std::is_trivially_destructible<T>::value && !force_trivial) {
137 for (U i = p_size; i < count; i++) {
138 data[i].~T();
139 }
140 }
141 count = p_size;
142 } else if (p_size > count) {
143 if (unlikely(p_size > capacity)) {
144 capacity = tight ? p_size : nearest_power_of_2_templated(p_size);
145 data = (T *)memrealloc(data, capacity * sizeof(T));
146 CRASH_COND_MSG(!data, "Out of memory");
147 }
148 if constexpr (!std::is_trivially_constructible<T>::value && !force_trivial) {
149 for (U i = count; i < p_size; i++) {
150 memnew_placement(&data[i], T);
151 }
152 }
153 count = p_size;
154 }
155 }
156 _FORCE_INLINE_ const T &operator[](U p_index) const {
157 CRASH_BAD_UNSIGNED_INDEX(p_index, count);
158 return data[p_index];
159 }
160 _FORCE_INLINE_ T &operator[](U p_index) {
161 CRASH_BAD_UNSIGNED_INDEX(p_index, count);
162 return data[p_index];
163 }
164
165 struct Iterator {
166 _FORCE_INLINE_ T &operator*() const {
167 return *elem_ptr;
168 }
169 _FORCE_INLINE_ T *operator->() const { return elem_ptr; }
170 _FORCE_INLINE_ Iterator &operator++() {
171 elem_ptr++;
172 return *this;
173 }
174 _FORCE_INLINE_ Iterator &operator--() {
175 elem_ptr--;
176 return *this;
177 }
178
179 _FORCE_INLINE_ bool operator==(const Iterator &b) const { return elem_ptr == b.elem_ptr; }
180 _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return elem_ptr != b.elem_ptr; }
181
182 Iterator(T *p_ptr) { elem_ptr = p_ptr; }
183 Iterator() {}
184 Iterator(const Iterator &p_it) { elem_ptr = p_it.elem_ptr; }
185
186 private:
187 T *elem_ptr = nullptr;
188 };
189
190 struct ConstIterator {
191 _FORCE_INLINE_ const T &operator*() const {
192 return *elem_ptr;
193 }
194 _FORCE_INLINE_ const T *operator->() const { return elem_ptr; }
195 _FORCE_INLINE_ ConstIterator &operator++() {
196 elem_ptr++;
197 return *this;
198 }
199 _FORCE_INLINE_ ConstIterator &operator--() {
200 elem_ptr--;
201 return *this;
202 }
203
204 _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return elem_ptr == b.elem_ptr; }
205 _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return elem_ptr != b.elem_ptr; }
206
207 ConstIterator(const T *p_ptr) { elem_ptr = p_ptr; }
208 ConstIterator() {}
209 ConstIterator(const ConstIterator &p_it) { elem_ptr = p_it.elem_ptr; }
210
211 private:
212 const T *elem_ptr = nullptr;
213 };
214
215 _FORCE_INLINE_ Iterator begin() {
216 return Iterator(data);
217 }
218 _FORCE_INLINE_ Iterator end() {
219 return Iterator(data + size());
220 }
221
222 _FORCE_INLINE_ ConstIterator begin() const {
223 return ConstIterator(ptr());
224 }
225 _FORCE_INLINE_ ConstIterator end() const {
226 return ConstIterator(ptr() + size());
227 }
228
229 void insert(U p_pos, T p_val) {
230 ERR_FAIL_UNSIGNED_INDEX(p_pos, count + 1);
231 if (p_pos == count) {
232 push_back(p_val);
233 } else {
234 resize(count + 1);
235 for (U i = count - 1; i > p_pos; i--) {
236 data[i] = data[i - 1];
237 }
238 data[p_pos] = p_val;
239 }
240 }
241
242 int64_t find(const T &p_val, U p_from = 0) const {
243 for (U i = p_from; i < count; i++) {
244 if (data[i] == p_val) {
245 return int64_t(i);
246 }
247 }
248 return -1;
249 }
250
251 template <class C>
252 void sort_custom() {
253 U len = count;
254 if (len == 0) {
255 return;
256 }
257
258 SortArray<T, C> sorter;
259 sorter.sort(data, len);
260 }
261
262 void sort() {
263 sort_custom<_DefaultComparator<T>>();
264 }
265
266 void ordered_insert(T p_val) {
267 U i;
268 for (i = 0; i < count; i++) {
269 if (p_val < data[i]) {
270 break;
271 }
272 }
273 insert(i, p_val);
274 }
275
276 operator Vector<T>() const {
277 Vector<T> ret;
278 ret.resize(size());
279 T *w = ret.ptrw();
280 memcpy(w, data, sizeof(T) * count);
281 return ret;
282 }
283
284 Vector<uint8_t> to_byte_array() const { //useful to pass stuff to gpu or variant
285 Vector<uint8_t> ret;
286 ret.resize(count * sizeof(T));
287 uint8_t *w = ret.ptrw();
288 memcpy(w, data, sizeof(T) * count);
289 return ret;
290 }
291
292 _FORCE_INLINE_ LocalVector() {}
293 _FORCE_INLINE_ LocalVector(std::initializer_list<T> p_init) {
294 reserve(p_init.size());
295 for (const T &element : p_init) {
296 push_back(element);
297 }
298 }
299 _FORCE_INLINE_ LocalVector(const LocalVector &p_from) {
300 resize(p_from.size());
301 for (U i = 0; i < p_from.count; i++) {
302 data[i] = p_from.data[i];
303 }
304 }
305 inline void operator=(const LocalVector &p_from) {
306 resize(p_from.size());
307 for (U i = 0; i < p_from.count; i++) {
308 data[i] = p_from.data[i];
309 }
310 }
311 inline void operator=(const Vector<T> &p_from) {
312 resize(p_from.size());
313 for (U i = 0; i < count; i++) {
314 data[i] = p_from[i];
315 }
316 }
317
318 _FORCE_INLINE_ ~LocalVector() {
319 if (data) {
320 reset();
321 }
322 }
323};
324
325template <class T, class U = uint32_t, bool force_trivial = false>
326using TightLocalVector = LocalVector<T, U, force_trivial, true>;
327
328#endif // LOCAL_VECTOR_H
329