1/**************************************************************************/
2/* rid_owner.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 RID_OWNER_H
32#define RID_OWNER_H
33
34#include "core/os/memory.h"
35#include "core/os/spin_lock.h"
36#include "core/string/print_string.h"
37#include "core/templates/hash_set.h"
38#include "core/templates/list.h"
39#include "core/templates/oa_hash_map.h"
40#include "core/templates/rid.h"
41#include "core/templates/safe_refcount.h"
42
43#include <stdio.h>
44#include <typeinfo>
45
46class RID_AllocBase {
47 static SafeNumeric<uint64_t> base_id;
48
49protected:
50 static RID _make_from_id(uint64_t p_id) {
51 RID rid;
52 rid._id = p_id;
53 return rid;
54 }
55
56 static RID _gen_rid() {
57 return _make_from_id(_gen_id());
58 }
59
60 friend struct VariantUtilityFunctions;
61
62 static uint64_t _gen_id() {
63 return base_id.increment();
64 }
65
66public:
67 virtual ~RID_AllocBase() {}
68};
69
70template <class T, bool THREAD_SAFE = false>
71class RID_Alloc : public RID_AllocBase {
72 T **chunks = nullptr;
73 uint32_t **free_list_chunks = nullptr;
74 uint32_t **validator_chunks = nullptr;
75
76 uint32_t elements_in_chunk;
77 uint32_t max_alloc = 0;
78 uint32_t alloc_count = 0;
79
80 const char *description = nullptr;
81
82 mutable SpinLock spin_lock;
83
84 _FORCE_INLINE_ RID _allocate_rid() {
85 if (THREAD_SAFE) {
86 spin_lock.lock();
87 }
88
89 if (alloc_count == max_alloc) {
90 //allocate a new chunk
91 uint32_t chunk_count = alloc_count == 0 ? 0 : (max_alloc / elements_in_chunk);
92
93 //grow chunks
94 chunks = (T **)memrealloc(chunks, sizeof(T *) * (chunk_count + 1));
95 chunks[chunk_count] = (T *)memalloc(sizeof(T) * elements_in_chunk); //but don't initialize
96
97 //grow validators
98 validator_chunks = (uint32_t **)memrealloc(validator_chunks, sizeof(uint32_t *) * (chunk_count + 1));
99 validator_chunks[chunk_count] = (uint32_t *)memalloc(sizeof(uint32_t) * elements_in_chunk);
100 //grow free lists
101 free_list_chunks = (uint32_t **)memrealloc(free_list_chunks, sizeof(uint32_t *) * (chunk_count + 1));
102 free_list_chunks[chunk_count] = (uint32_t *)memalloc(sizeof(uint32_t) * elements_in_chunk);
103
104 //initialize
105 for (uint32_t i = 0; i < elements_in_chunk; i++) {
106 // Don't initialize chunk.
107 validator_chunks[chunk_count][i] = 0xFFFFFFFF;
108 free_list_chunks[chunk_count][i] = alloc_count + i;
109 }
110
111 max_alloc += elements_in_chunk;
112 }
113
114 uint32_t free_index = free_list_chunks[alloc_count / elements_in_chunk][alloc_count % elements_in_chunk];
115
116 uint32_t free_chunk = free_index / elements_in_chunk;
117 uint32_t free_element = free_index % elements_in_chunk;
118
119 uint32_t validator = (uint32_t)(_gen_id() & 0x7FFFFFFF);
120 CRASH_COND_MSG(validator == 0x7FFFFFFF, "Overflow in RID validator");
121 uint64_t id = validator;
122 id <<= 32;
123 id |= free_index;
124
125 validator_chunks[free_chunk][free_element] = validator;
126
127 validator_chunks[free_chunk][free_element] |= 0x80000000; //mark uninitialized bit
128
129 alloc_count++;
130
131 if (THREAD_SAFE) {
132 spin_lock.unlock();
133 }
134
135 return _make_from_id(id);
136 }
137
138public:
139 RID make_rid() {
140 RID rid = _allocate_rid();
141 initialize_rid(rid);
142 return rid;
143 }
144 RID make_rid(const T &p_value) {
145 RID rid = _allocate_rid();
146 initialize_rid(rid, p_value);
147 return rid;
148 }
149
150 //allocate but don't initialize, use initialize_rid afterwards
151 RID allocate_rid() {
152 return _allocate_rid();
153 }
154
155 _FORCE_INLINE_ T *get_or_null(const RID &p_rid, bool p_initialize = false) {
156 if (p_rid == RID()) {
157 return nullptr;
158 }
159 if (THREAD_SAFE) {
160 spin_lock.lock();
161 }
162
163 uint64_t id = p_rid.get_id();
164 uint32_t idx = uint32_t(id & 0xFFFFFFFF);
165 if (unlikely(idx >= max_alloc)) {
166 if (THREAD_SAFE) {
167 spin_lock.unlock();
168 }
169 return nullptr;
170 }
171
172 uint32_t idx_chunk = idx / elements_in_chunk;
173 uint32_t idx_element = idx % elements_in_chunk;
174
175 uint32_t validator = uint32_t(id >> 32);
176
177 if (unlikely(p_initialize)) {
178 if (unlikely(!(validator_chunks[idx_chunk][idx_element] & 0x80000000))) {
179 if (THREAD_SAFE) {
180 spin_lock.unlock();
181 }
182 ERR_FAIL_V_MSG(nullptr, "Initializing already initialized RID");
183 }
184
185 if (unlikely((validator_chunks[idx_chunk][idx_element] & 0x7FFFFFFF) != validator)) {
186 if (THREAD_SAFE) {
187 spin_lock.unlock();
188 }
189 ERR_FAIL_V_MSG(nullptr, "Attempting to initialize the wrong RID");
190 }
191
192 validator_chunks[idx_chunk][idx_element] &= 0x7FFFFFFF; //initialized
193
194 } else if (unlikely(validator_chunks[idx_chunk][idx_element] != validator)) {
195 if (THREAD_SAFE) {
196 spin_lock.unlock();
197 }
198 if ((validator_chunks[idx_chunk][idx_element] & 0x80000000) && validator_chunks[idx_chunk][idx_element] != 0xFFFFFFFF) {
199 ERR_FAIL_V_MSG(nullptr, "Attempting to use an uninitialized RID");
200 }
201 return nullptr;
202 }
203
204 T *ptr = &chunks[idx_chunk][idx_element];
205
206 if (THREAD_SAFE) {
207 spin_lock.unlock();
208 }
209
210 return ptr;
211 }
212 void initialize_rid(RID p_rid) {
213 T *mem = get_or_null(p_rid, true);
214 ERR_FAIL_NULL(mem);
215 memnew_placement(mem, T);
216 }
217 void initialize_rid(RID p_rid, const T &p_value) {
218 T *mem = get_or_null(p_rid, true);
219 ERR_FAIL_NULL(mem);
220 memnew_placement(mem, T(p_value));
221 }
222
223 _FORCE_INLINE_ bool owns(const RID &p_rid) const {
224 if (THREAD_SAFE) {
225 spin_lock.lock();
226 }
227
228 uint64_t id = p_rid.get_id();
229 uint32_t idx = uint32_t(id & 0xFFFFFFFF);
230 if (unlikely(idx >= max_alloc)) {
231 if (THREAD_SAFE) {
232 spin_lock.unlock();
233 }
234 return false;
235 }
236
237 uint32_t idx_chunk = idx / elements_in_chunk;
238 uint32_t idx_element = idx % elements_in_chunk;
239
240 uint32_t validator = uint32_t(id >> 32);
241
242 bool owned = (validator != 0x7FFFFFFF) && (validator_chunks[idx_chunk][idx_element] & 0x7FFFFFFF) == validator;
243
244 if (THREAD_SAFE) {
245 spin_lock.unlock();
246 }
247
248 return owned;
249 }
250
251 _FORCE_INLINE_ void free(const RID &p_rid) {
252 if (THREAD_SAFE) {
253 spin_lock.lock();
254 }
255
256 uint64_t id = p_rid.get_id();
257 uint32_t idx = uint32_t(id & 0xFFFFFFFF);
258 if (unlikely(idx >= max_alloc)) {
259 if (THREAD_SAFE) {
260 spin_lock.unlock();
261 }
262 ERR_FAIL();
263 }
264
265 uint32_t idx_chunk = idx / elements_in_chunk;
266 uint32_t idx_element = idx % elements_in_chunk;
267
268 uint32_t validator = uint32_t(id >> 32);
269 if (unlikely(validator_chunks[idx_chunk][idx_element] & 0x80000000)) {
270 if (THREAD_SAFE) {
271 spin_lock.unlock();
272 }
273 ERR_FAIL_MSG("Attempted to free an uninitialized or invalid RID");
274 } else if (unlikely(validator_chunks[idx_chunk][idx_element] != validator)) {
275 if (THREAD_SAFE) {
276 spin_lock.unlock();
277 }
278 ERR_FAIL();
279 }
280
281 chunks[idx_chunk][idx_element].~T();
282 validator_chunks[idx_chunk][idx_element] = 0xFFFFFFFF; // go invalid
283
284 alloc_count--;
285 free_list_chunks[alloc_count / elements_in_chunk][alloc_count % elements_in_chunk] = idx;
286
287 if (THREAD_SAFE) {
288 spin_lock.unlock();
289 }
290 }
291
292 _FORCE_INLINE_ uint32_t get_rid_count() const {
293 return alloc_count;
294 }
295 void get_owned_list(List<RID> *p_owned) const {
296 if (THREAD_SAFE) {
297 spin_lock.lock();
298 }
299 for (size_t i = 0; i < max_alloc; i++) {
300 uint64_t validator = validator_chunks[i / elements_in_chunk][i % elements_in_chunk];
301 if (validator != 0xFFFFFFFF) {
302 p_owned->push_back(_make_from_id((validator << 32) | i));
303 }
304 }
305 if (THREAD_SAFE) {
306 spin_lock.unlock();
307 }
308 }
309
310 //used for fast iteration in the elements or RIDs
311 void fill_owned_buffer(RID *p_rid_buffer) const {
312 if (THREAD_SAFE) {
313 spin_lock.lock();
314 }
315 uint32_t idx = 0;
316 for (size_t i = 0; i < max_alloc; i++) {
317 uint64_t validator = validator_chunks[i / elements_in_chunk][i % elements_in_chunk];
318 if (validator != 0xFFFFFFFF) {
319 p_rid_buffer[idx] = _make_from_id((validator << 32) | i);
320 idx++;
321 }
322 }
323 if (THREAD_SAFE) {
324 spin_lock.unlock();
325 }
326 }
327
328 void set_description(const char *p_descrption) {
329 description = p_descrption;
330 }
331
332 RID_Alloc(uint32_t p_target_chunk_byte_size = 65536) {
333 elements_in_chunk = sizeof(T) > p_target_chunk_byte_size ? 1 : (p_target_chunk_byte_size / sizeof(T));
334 }
335
336 ~RID_Alloc() {
337 if (alloc_count) {
338 print_error(vformat("ERROR: %d RID allocations of type '%s' were leaked at exit.",
339 alloc_count, description ? description : typeid(T).name()));
340
341 for (size_t i = 0; i < max_alloc; i++) {
342 uint64_t validator = validator_chunks[i / elements_in_chunk][i % elements_in_chunk];
343 if (validator & 0x80000000) {
344 continue; //uninitialized
345 }
346 if (validator != 0xFFFFFFFF) {
347 chunks[i / elements_in_chunk][i % elements_in_chunk].~T();
348 }
349 }
350 }
351
352 uint32_t chunk_count = max_alloc / elements_in_chunk;
353 for (uint32_t i = 0; i < chunk_count; i++) {
354 memfree(chunks[i]);
355 memfree(validator_chunks[i]);
356 memfree(free_list_chunks[i]);
357 }
358
359 if (chunks) {
360 memfree(chunks);
361 memfree(free_list_chunks);
362 memfree(validator_chunks);
363 }
364 }
365};
366
367template <class T, bool THREAD_SAFE = false>
368class RID_PtrOwner {
369 RID_Alloc<T *, THREAD_SAFE> alloc;
370
371public:
372 _FORCE_INLINE_ RID make_rid(T *p_ptr) {
373 return alloc.make_rid(p_ptr);
374 }
375
376 _FORCE_INLINE_ RID allocate_rid() {
377 return alloc.allocate_rid();
378 }
379
380 _FORCE_INLINE_ void initialize_rid(RID p_rid, T *p_ptr) {
381 alloc.initialize_rid(p_rid, p_ptr);
382 }
383
384 _FORCE_INLINE_ T *get_or_null(const RID &p_rid) {
385 T **ptr = alloc.get_or_null(p_rid);
386 if (unlikely(!ptr)) {
387 return nullptr;
388 }
389 return *ptr;
390 }
391
392 _FORCE_INLINE_ void replace(const RID &p_rid, T *p_new_ptr) {
393 T **ptr = alloc.get_or_null(p_rid);
394 ERR_FAIL_NULL(ptr);
395 *ptr = p_new_ptr;
396 }
397
398 _FORCE_INLINE_ bool owns(const RID &p_rid) const {
399 return alloc.owns(p_rid);
400 }
401
402 _FORCE_INLINE_ void free(const RID &p_rid) {
403 alloc.free(p_rid);
404 }
405
406 _FORCE_INLINE_ uint32_t get_rid_count() const {
407 return alloc.get_rid_count();
408 }
409
410 _FORCE_INLINE_ void get_owned_list(List<RID> *p_owned) const {
411 return alloc.get_owned_list(p_owned);
412 }
413
414 void fill_owned_buffer(RID *p_rid_buffer) const {
415 alloc.fill_owned_buffer(p_rid_buffer);
416 }
417
418 void set_description(const char *p_descrption) {
419 alloc.set_description(p_descrption);
420 }
421
422 RID_PtrOwner(uint32_t p_target_chunk_byte_size = 65536) :
423 alloc(p_target_chunk_byte_size) {}
424};
425
426template <class T, bool THREAD_SAFE = false>
427class RID_Owner {
428 RID_Alloc<T, THREAD_SAFE> alloc;
429
430public:
431 _FORCE_INLINE_ RID make_rid() {
432 return alloc.make_rid();
433 }
434 _FORCE_INLINE_ RID make_rid(const T &p_ptr) {
435 return alloc.make_rid(p_ptr);
436 }
437
438 _FORCE_INLINE_ RID allocate_rid() {
439 return alloc.allocate_rid();
440 }
441
442 _FORCE_INLINE_ void initialize_rid(RID p_rid) {
443 alloc.initialize_rid(p_rid);
444 }
445
446 _FORCE_INLINE_ void initialize_rid(RID p_rid, const T &p_ptr) {
447 alloc.initialize_rid(p_rid, p_ptr);
448 }
449
450 _FORCE_INLINE_ T *get_or_null(const RID &p_rid) {
451 return alloc.get_or_null(p_rid);
452 }
453
454 _FORCE_INLINE_ bool owns(const RID &p_rid) const {
455 return alloc.owns(p_rid);
456 }
457
458 _FORCE_INLINE_ void free(const RID &p_rid) {
459 alloc.free(p_rid);
460 }
461
462 _FORCE_INLINE_ uint32_t get_rid_count() const {
463 return alloc.get_rid_count();
464 }
465
466 _FORCE_INLINE_ void get_owned_list(List<RID> *p_owned) const {
467 return alloc.get_owned_list(p_owned);
468 }
469 void fill_owned_buffer(RID *p_rid_buffer) const {
470 alloc.fill_owned_buffer(p_rid_buffer);
471 }
472
473 void set_description(const char *p_descrption) {
474 alloc.set_description(p_descrption);
475 }
476 RID_Owner(uint32_t p_target_chunk_byte_size = 65536) :
477 alloc(p_target_chunk_byte_size) {}
478};
479
480#endif // RID_OWNER_H
481