1/**************************************************************************/
2/* cowdata.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 COWDATA_H
32#define COWDATA_H
33
34#include "core/error/error_macros.h"
35#include "core/os/memory.h"
36#include "core/templates/safe_refcount.h"
37
38#include <string.h>
39#include <type_traits>
40
41template <class T>
42class Vector;
43class String;
44class Char16String;
45class CharString;
46template <class T, class V>
47class VMap;
48
49SAFE_NUMERIC_TYPE_PUN_GUARANTEES(uint32_t)
50
51// Silence a false positive warning (see GH-52119).
52#if defined(__GNUC__) && !defined(__clang__)
53#pragma GCC diagnostic push
54#pragma GCC diagnostic ignored "-Wplacement-new"
55#endif
56
57template <class T>
58class CowData {
59 template <class TV>
60 friend class Vector;
61 friend class String;
62 friend class Char16String;
63 friend class CharString;
64 template <class TV, class VV>
65 friend class VMap;
66
67private:
68 mutable T *_ptr = nullptr;
69
70 // internal helpers
71
72 _FORCE_INLINE_ SafeNumeric<uint32_t> *_get_refcount() const {
73 if (!_ptr) {
74 return nullptr;
75 }
76
77 return reinterpret_cast<SafeNumeric<uint32_t> *>(_ptr) - 2;
78 }
79
80 _FORCE_INLINE_ uint32_t *_get_size() const {
81 if (!_ptr) {
82 return nullptr;
83 }
84
85 return reinterpret_cast<uint32_t *>(_ptr) - 1;
86 }
87
88 _FORCE_INLINE_ size_t _get_alloc_size(size_t p_elements) const {
89 return next_power_of_2(p_elements * sizeof(T));
90 }
91
92 _FORCE_INLINE_ bool _get_alloc_size_checked(size_t p_elements, size_t *out) const {
93#if defined(__GNUC__)
94 size_t o;
95 size_t p;
96 if (__builtin_mul_overflow(p_elements, sizeof(T), &o)) {
97 *out = 0;
98 return false;
99 }
100 *out = next_power_of_2(o);
101 if (__builtin_add_overflow(o, static_cast<size_t>(32), &p)) {
102 return false; // No longer allocated here.
103 }
104 return true;
105#else
106 // Speed is more important than correctness here, do the operations unchecked
107 // and hope for the best.
108 *out = _get_alloc_size(p_elements);
109 return true;
110#endif
111 }
112
113 void _unref(void *p_data);
114 void _ref(const CowData *p_from);
115 void _ref(const CowData &p_from);
116 uint32_t _copy_on_write();
117
118public:
119 void operator=(const CowData<T> &p_from) { _ref(p_from); }
120
121 _FORCE_INLINE_ T *ptrw() {
122 _copy_on_write();
123 return _ptr;
124 }
125
126 _FORCE_INLINE_ const T *ptr() const {
127 return _ptr;
128 }
129
130 _FORCE_INLINE_ int size() const {
131 uint32_t *size = (uint32_t *)_get_size();
132 if (size) {
133 return *size;
134 } else {
135 return 0;
136 }
137 }
138
139 _FORCE_INLINE_ void clear() { resize(0); }
140 _FORCE_INLINE_ bool is_empty() const { return _ptr == nullptr; }
141
142 _FORCE_INLINE_ void set(int p_index, const T &p_elem) {
143 ERR_FAIL_INDEX(p_index, size());
144 _copy_on_write();
145 _ptr[p_index] = p_elem;
146 }
147
148 _FORCE_INLINE_ T &get_m(int p_index) {
149 CRASH_BAD_INDEX(p_index, size());
150 _copy_on_write();
151 return _ptr[p_index];
152 }
153
154 _FORCE_INLINE_ const T &get(int p_index) const {
155 CRASH_BAD_INDEX(p_index, size());
156
157 return _ptr[p_index];
158 }
159
160 template <bool p_ensure_zero = false>
161 Error resize(int p_size);
162
163 _FORCE_INLINE_ void remove_at(int p_index) {
164 ERR_FAIL_INDEX(p_index, size());
165 T *p = ptrw();
166 int len = size();
167 for (int i = p_index; i < len - 1; i++) {
168 p[i] = p[i + 1];
169 }
170
171 resize(len - 1);
172 }
173
174 Error insert(int p_pos, const T &p_val) {
175 ERR_FAIL_INDEX_V(p_pos, size() + 1, ERR_INVALID_PARAMETER);
176 resize(size() + 1);
177 for (int i = (size() - 1); i > p_pos; i--) {
178 set(i, get(i - 1));
179 }
180 set(p_pos, p_val);
181
182 return OK;
183 }
184
185 int find(const T &p_val, int p_from = 0) const;
186 int rfind(const T &p_val, int p_from = -1) const;
187 int count(const T &p_val) const;
188
189 _FORCE_INLINE_ CowData() {}
190 _FORCE_INLINE_ ~CowData();
191 _FORCE_INLINE_ CowData(CowData<T> &p_from) { _ref(p_from); };
192};
193
194template <class T>
195void CowData<T>::_unref(void *p_data) {
196 if (!p_data) {
197 return;
198 }
199
200 SafeNumeric<uint32_t> *refc = _get_refcount();
201
202 if (refc->decrement() > 0) {
203 return; // still in use
204 }
205 // clean up
206
207 if (!std::is_trivially_destructible<T>::value) {
208 uint32_t *count = _get_size();
209 T *data = (T *)(count + 1);
210
211 for (uint32_t i = 0; i < *count; ++i) {
212 // call destructors
213 data[i].~T();
214 }
215 }
216
217 // free mem
218 Memory::free_static((uint8_t *)p_data, true);
219}
220
221template <class T>
222uint32_t CowData<T>::_copy_on_write() {
223 if (!_ptr) {
224 return 0;
225 }
226
227 SafeNumeric<uint32_t> *refc = _get_refcount();
228
229 uint32_t rc = refc->get();
230 if (unlikely(rc > 1)) {
231 /* in use by more than me */
232 uint32_t current_size = *_get_size();
233
234 uint32_t *mem_new = (uint32_t *)Memory::alloc_static(_get_alloc_size(current_size), true);
235
236 new (mem_new - 2) SafeNumeric<uint32_t>(1); //refcount
237 *(mem_new - 1) = current_size; //size
238
239 T *_data = (T *)(mem_new);
240
241 // initialize new elements
242 if (std::is_trivially_copyable<T>::value) {
243 memcpy(mem_new, _ptr, current_size * sizeof(T));
244
245 } else {
246 for (uint32_t i = 0; i < current_size; i++) {
247 memnew_placement(&_data[i], T(_ptr[i]));
248 }
249 }
250
251 _unref(_ptr);
252 _ptr = _data;
253
254 rc = 1;
255 }
256 return rc;
257}
258
259template <class T>
260template <bool p_ensure_zero>
261Error CowData<T>::resize(int p_size) {
262 ERR_FAIL_COND_V(p_size < 0, ERR_INVALID_PARAMETER);
263
264 int current_size = size();
265
266 if (p_size == current_size) {
267 return OK;
268 }
269
270 if (p_size == 0) {
271 // wants to clean up
272 _unref(_ptr);
273 _ptr = nullptr;
274 return OK;
275 }
276
277 // possibly changing size, copy on write
278 uint32_t rc = _copy_on_write();
279
280 size_t current_alloc_size = _get_alloc_size(current_size);
281 size_t alloc_size;
282 ERR_FAIL_COND_V(!_get_alloc_size_checked(p_size, &alloc_size), ERR_OUT_OF_MEMORY);
283
284 if (p_size > current_size) {
285 if (alloc_size != current_alloc_size) {
286 if (current_size == 0) {
287 // alloc from scratch
288 uint32_t *ptr = (uint32_t *)Memory::alloc_static(alloc_size, true);
289 ERR_FAIL_NULL_V(ptr, ERR_OUT_OF_MEMORY);
290 *(ptr - 1) = 0; //size, currently none
291 new (ptr - 2) SafeNumeric<uint32_t>(1); //refcount
292
293 _ptr = (T *)ptr;
294
295 } else {
296 uint32_t *_ptrnew = (uint32_t *)Memory::realloc_static(_ptr, alloc_size, true);
297 ERR_FAIL_NULL_V(_ptrnew, ERR_OUT_OF_MEMORY);
298 new (_ptrnew - 2) SafeNumeric<uint32_t>(rc); //refcount
299
300 _ptr = (T *)(_ptrnew);
301 }
302 }
303
304 // construct the newly created elements
305
306 if (!std::is_trivially_constructible<T>::value) {
307 for (int i = *_get_size(); i < p_size; i++) {
308 memnew_placement(&_ptr[i], T);
309 }
310 } else if (p_ensure_zero) {
311 memset((void *)(_ptr + current_size), 0, (p_size - current_size) * sizeof(T));
312 }
313
314 *_get_size() = p_size;
315
316 } else if (p_size < current_size) {
317 if (!std::is_trivially_destructible<T>::value) {
318 // deinitialize no longer needed elements
319 for (uint32_t i = p_size; i < *_get_size(); i++) {
320 T *t = &_ptr[i];
321 t->~T();
322 }
323 }
324
325 if (alloc_size != current_alloc_size) {
326 uint32_t *_ptrnew = (uint32_t *)Memory::realloc_static(_ptr, alloc_size, true);
327 ERR_FAIL_NULL_V(_ptrnew, ERR_OUT_OF_MEMORY);
328 new (_ptrnew - 2) SafeNumeric<uint32_t>(rc); //refcount
329
330 _ptr = (T *)(_ptrnew);
331 }
332
333 *_get_size() = p_size;
334 }
335
336 return OK;
337}
338
339template <class T>
340int CowData<T>::find(const T &p_val, int p_from) const {
341 int ret = -1;
342
343 if (p_from < 0 || size() == 0) {
344 return ret;
345 }
346
347 for (int i = p_from; i < size(); i++) {
348 if (get(i) == p_val) {
349 ret = i;
350 break;
351 }
352 }
353
354 return ret;
355}
356
357template <class T>
358int CowData<T>::rfind(const T &p_val, int p_from) const {
359 const int s = size();
360
361 if (p_from < 0) {
362 p_from = s + p_from;
363 }
364 if (p_from < 0 || p_from >= s) {
365 p_from = s - 1;
366 }
367
368 for (int i = p_from; i >= 0; i--) {
369 if (get(i) == p_val) {
370 return i;
371 }
372 }
373 return -1;
374}
375
376template <class T>
377int CowData<T>::count(const T &p_val) const {
378 int amount = 0;
379 for (int i = 0; i < size(); i++) {
380 if (get(i) == p_val) {
381 amount++;
382 }
383 }
384 return amount;
385}
386
387template <class T>
388void CowData<T>::_ref(const CowData *p_from) {
389 _ref(*p_from);
390}
391
392template <class T>
393void CowData<T>::_ref(const CowData &p_from) {
394 if (_ptr == p_from._ptr) {
395 return; // self assign, do nothing.
396 }
397
398 _unref(_ptr);
399 _ptr = nullptr;
400
401 if (!p_from._ptr) {
402 return; //nothing to do
403 }
404
405 if (p_from._get_refcount()->conditional_increment() > 0) { // could reference
406 _ptr = p_from._ptr;
407 }
408}
409
410template <class T>
411CowData<T>::~CowData() {
412 _unref(_ptr);
413}
414
415#if defined(__GNUC__) && !defined(__clang__)
416#pragma GCC diagnostic pop
417#endif
418
419#endif // COWDATA_H
420