/**************************************************************************/
/* cowdata.h */
/**************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
/* https://godotengine.org */
/**************************************************************************/
/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
/* */
/* Permission is hereby granted, free of charge, to any person obtaining */
/* a copy of this software and associated documentation files (the */
/* "Software"), to deal in the Software without restriction, including */
/* without limitation the rights to use, copy, modify, merge, publish, */
/* distribute, sublicense, and/or sell copies of the Software, and to */
/* permit persons to whom the Software is furnished to do so, subject to */
/* the following conditions: */
/* */
/* The above copyright notice and this permission notice shall be */
/* included in all copies or substantial portions of the Software. */
/* */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/**************************************************************************/
#pragma once
#include "core/error/error_macros.h"
#include "core/os/memory.h"
#include "core/string/print_string.h" // IWYU pragma: keep. `WARN_VERBOSE` macro.
#include "core/templates/safe_refcount.h"
#include "core/templates/span.h"
#include <initializer_list>
#include <type_traits>
#ifdef ASAN_ENABLED
#include <sanitizer/asan_interface.h>
#endif
static_assert(std::is_trivially_destructible_v<std::atomic<uint64_t>>);
// Silences false-positive warnings.
GODOT_GCC_WARNING_PUSH
GODOT_GCC_WARNING_IGNORE("-Wplacement-new") // Silence a false positive warning (see GH-52119).
GODOT_GCC_WARNING_IGNORE("-Wmaybe-uninitialized") // False positive raised when using constexpr.
GODOT_GCC_WARNING_IGNORE("-Warray-bounds")
GODOT_GCC_WARNING_IGNORE("-Wrestrict")
GODOT_GCC_PRAGMA(GCC diagnostic warning "-Wstringop-overflow=0") // Can't "ignore" this for some reason.
#ifdef WINDOWS_ENABLED
GODOT_GCC_PRAGMA(GCC diagnostic warning "-Wdangling-pointer=0") // Can't "ignore" this for some reason.
#endif
template <typename T>
class CowData {
public:
typedef int64_t Size;
typedef uint64_t USize;
static constexpr USize MAX_INT = INT64_MAX;
private:
// Alignment: ↓ max_align_t ↓ USize ↓ USize ↓ MAX_ALIGN
// ┌────────────────────┬──┬───────────────┬──┬─────────────┬──┬───────────...
// │ SafeNumeric<USize> │░░│ USize │░░│ USize │░░│ T[]
// │ ref. count │░░│ data capacity │░░│ data size │░░│ data
// └────────────────────┴──┴───────────────┴──┴─────────────┴──┴───────────...
// Offset: ↑ REF_COUNT_OFFSET ↑ CAPACITY_OFFSET ↑ SIZE_OFFSET ↑ DATA_OFFSET
static constexpr size_t REF_COUNT_OFFSET = 0;
static constexpr size_t CAPACITY_OFFSET = Memory::get_aligned_address(REF_COUNT_OFFSET + sizeof(SafeNumeric<USize>), alignof(USize));
static constexpr size_t SIZE_OFFSET = Memory::get_aligned_address(CAPACITY_OFFSET + sizeof(USize), alignof(USize));
static constexpr size_t DATA_OFFSET = Memory::get_aligned_address(SIZE_OFFSET + sizeof(USize), Memory::MAX_ALIGN);
mutable T *_ptr = nullptr;
// internal helpers
static constexpr _FORCE_INLINE_ USize grow_capacity(USize p_previous_capacity) {
// 1.5x the given size.
// This ratio was chosen because it is close to the ideal growth rate of the golden ratio.
// See https://archive.ph/Z2R8w for details.
return MAX((USize)2, p_previous_capacity + ((1 + p_previous_capacity) >> 1));
}
static constexpr _FORCE_INLINE_ USize next_capacity(USize p_previous_capacity, USize p_size) {
if (p_previous_capacity < p_size) {
return MAX(grow_capacity(p_previous_capacity), p_size);
}
return p_previous_capacity;
}
static constexpr _FORCE_INLINE_ USize smaller_capacity(USize p_previous_capacity, USize p_size) {
if (p_size < p_previous_capacity >> 2) {
return grow_capacity(p_size);
}
return p_previous_capacity;
}
static _FORCE_INLINE_ T *_get_data_ptr(uint8_t *p_ptr) {
return (T *)(p_ptr + DATA_OFFSET);
}
/// Note: Assumes _ptr != nullptr.
_FORCE_INLINE_ SafeNumeric<USize> *_get_refcount() const {
return (SafeNumeric<USize> *)((uint8_t *)_ptr - DATA_OFFSET + REF_COUNT_OFFSET);
}
/// Note: Assumes _ptr != nullptr.
_FORCE_INLINE_ USize *_get_size() const {
return (USize *)((uint8_t *)_ptr - DATA_OFFSET + SIZE_OFFSET);
}
/// Note: Assumes _ptr != nullptr.
_FORCE_INLINE_ USize *_get_capacity() const {
return (USize *)((uint8_t *)_ptr - DATA_OFFSET + CAPACITY_OFFSET);
}
// Decrements the reference count. Deallocates the backing buffer if needed.
// After this function, _ptr is guaranteed to be NULL.
void _unref();
void _ref(const CowData *p_from);
void _ref(const CowData &p_from);
/// Allocates a backing array of the given capacity. The reference count is initialized to 1, size to 0.
/// It is the responsibility of the caller to:
/// - Ensure _ptr == nullptr
/// - Ensure p_capacity > 0
Error _alloc_exact(USize p_capacity);
/// Re-allocates the backing array to the given capacity.
/// It is the responsibility of the caller to:
/// - Ensure we are the only owner of the backing array
/// - Ensure p_capacity > 0
Error _realloc_exact(USize p_capacity);
/// Create a new buffer and copies over elements from the old buffer.
/// Elements are inserted first from the start, then a gap is left uninitialized, and then elements are inserted from the back.
/// It is the responsibility of the caller to:
/// - Construct elements in the gap.
/// - Ensure size() >= p_size_from_start and size() >= p_size_from_back.
/// - Ensure p_capacity is enough to hold all elements.
[[nodiscard]] Error _copy_to_new_buffer_exact(USize p_capacity, USize p_size_from_start, USize p_gap, USize p_size_from_back);
/// Ensure we are the only owners of the backing buffer.
[[nodiscard]] Error _copy_on_write();
public:
void operator=(const CowData<T> &p_from) { _ref(p_from); }
void operator=(CowData<T> &&p_from) {
if (_ptr == p_from._ptr) {
return;
}
_unref();
_ptr = p_from._ptr;
p_from._ptr = nullptr;
}
_FORCE_INLINE_ T *ptrw() {
// If forking fails, we can only crash.
CRASH_COND(_copy_on_write());
return _ptr;
}
_FORCE_INLINE_ const T *ptr() const {
return _ptr;
}
_FORCE_INLINE_ Size size() const { return !_ptr ? 0 : *_get_size(); }
_FORCE_INLINE_ USize capacity() const { return !_ptr ? 0 : *_get_capacity(); }
_FORCE_INLINE_ USize refcount() const { return !_ptr ? 0 : *_get_refcount(); }
_FORCE_INLINE_ void clear() { _unref(); }
_FORCE_INLINE_ bool is_empty() const { return size() == 0; }
_FORCE_INLINE_ void set(Size p_index, const T &p_elem) {
ERR_FAIL_INDEX(p_index, size());
// TODO Returning the error would be more appropriate.
CRASH_COND(_copy_on_write());
_ptr[p_index] = p_elem;
}
_FORCE_INLINE_ T &get_m(Size p_index) {
CRASH_BAD_INDEX(p_index, size());
// If we fail to fork, all we can do is crash,
// since the caller may write incorrectly to the unforked array.
CRASH_COND(_copy_on_write());
return _ptr[p_index];
}
_FORCE_INLINE_ const T &get(Size p_index) const {
CRASH_BAD_INDEX(p_index, size());
return _ptr[p_index];
}
template <bool p_init = false>
Error resize(Size p_size);
template <bool p_exact = false>
Error reserve(USize p_min_capacity);
_FORCE_INLINE_ Error reserve_exact(USize p_capacity) {
return reserve<true>(p_capacity);
}
_FORCE_INLINE_ void remove_at(Size p_index);
Error insert(Size p_pos, T &&p_val);
Error push_back(T &&p_val);
_FORCE_INLINE_ operator Span<T>() const { return Span<T>(ptr(), size()); }
_FORCE_INLINE_ Span<T> span() const { return operator Span<T>(); }
_FORCE_INLINE_ CowData() {}
_FORCE_INLINE_ ~CowData() { _unref(); }
_FORCE_INLINE_ CowData(std::initializer_list<T> p_init);
_FORCE_INLINE_ CowData(const CowData<T> &p_from) { _ref(p_from); }
_FORCE_INLINE_ CowData(CowData<T> &&p_from) {
_ptr = p_from._ptr;
p_from._ptr = nullptr;
}
};
template <typename T>
void CowData<T>::_unref() {
if (!_ptr) {
return;
}
if (_get_refcount()->decrement() > 0) {
// Data is still in use elsewhere.
_ptr = nullptr;
return;
}
// We had the only reference; destroy the data.
// First, invalidate our own reference.
// NOTE: It is required to do so immediately because it must not be observable outside of this
// function after refcount has already been reduced to 0.
// WARNING: It must be done before calling the destructors, because one of them may otherwise
// observe it through a reference to us. In this case, it may try to access the buffer,
// which is illegal after some of the elements in it have already been destructed, and
// may lead to a segmentation fault.
USize current_size = size();
T *prev_ptr = _ptr;
_ptr = nullptr;
#ifdef ASAN_ENABLED
// Access during destruction is illegal in C++, and results in undefined behavior.
// In address sanitizer builds, we can poison ourselves (_ptr) to catch this.
__asan_poison_memory_region(this, sizeof(CowData));
#endif
destruct_arr_placement(prev_ptr, current_size);
// Free Memory.
Memory::free_static((uint8_t *)prev_ptr - DATA_OFFSET, false);
#ifdef ASAN_ENABLED
__asan_unpoison_memory_region(this, sizeof(CowData));
#elif defined(DEBUG_ENABLED)
// In a non-asan build, the best we can do is catch if elements were added during destruction.
ERR_FAIL_COND_MSG(_ptr != nullptr, "Internal bug, please report: CowData was modified during destruction.");
#endif
}
template <typename T>
void CowData<T>::remove_at(Size p_index) {
const Size prev_size = size();
ERR_FAIL_INDEX(p_index, prev_size);
if (prev_size == 1) {
// Removing the only element.
_unref();
return;
}
const USize new_size = prev_size - 1;
if (_get_refcount()->get() == 1) {
// We're the only owner; remove in-place.
// Destruct the element, then relocate the rest one down.
_ptr[p_index].~T();
memmove((void *)(_ptr + p_index), (void *)(_ptr + p_index + 1), (new_size - p_index) * sizeof(T));
// Shrink to fit if necessary.
const USize new_capacity = smaller_capacity(capacity(), new_size);
if (new_capacity < capacity()) {
Error err = _realloc_exact(new_capacity);
CRASH_COND(err);
}
*_get_size() = new_size;
} else {
// Remove by forking.
Error err = _copy_to_new_buffer_exact(smaller_capacity(capacity(), new_size), p_index, 0, new_size - p_index);
CRASH_COND(err);
}
}
template <typename T>
Error CowData<T>::insert(Size p_pos, T &&p_val) {
const Size new_size = size() + 1;
ERR_FAIL_INDEX_V(p_pos, new_size, ERR_INVALID_PARAMETER);
if (!_ptr) {
_alloc_exact(next_capacity(0, 1));
*_get_size() = 1;
} else if (_get_refcount()->get() == 1) {
if ((USize)new_size > capacity()) {
// Need to grow.
const Error error = _realloc_exact(grow_capacity(capacity()));
if (error) {
return error;
}
}
// Relocate elements one position up.
memmove((void *)(_ptr + p_pos + 1), (void *)(_ptr + p_pos), (size() - p_pos) * sizeof(T));
*_get_size() = new_size;
} else {
// Insert new element by forking.
// Use the max of capacity and new_size, to ensure we don't accidentally shrink after reserve.
const USize new_capacity = next_capacity(capacity(), new_size);
const Error error = _copy_to_new_buffer_exact(new_capacity, p_pos, 1, size() - p_pos);
if (error) {
return error;
}
}
// Create the new element at the given index.
memnew_placement(_ptr + p_pos, T(std::move(p_val)));
return OK;
}
template <typename T>
Error CowData<T>::push_back(T &&p_val) {
const Size new_size = size() + 1;
if (!_ptr) {
// Grow by allocating.
_alloc_exact(next_capacity(0, 1));
*_get_size() = 1;
} else if (_get_refcount()->get() == 1) {
// Grow in-place.
if ((USize)new_size > capacity()) {
// Need to grow.
const Error error = _realloc_exact(grow_capacity(capacity()));
if (error) {
return error;
}
}
*_get_size() = new_size;
} else {
// Grow by forking.
// Use the max of capacity and new_size, to ensure we don't accidentally shrink after reserve.
const USize new_capacity = next_capacity(capacity(), new_size);
const Error error = _copy_to_new_buffer_exact(new_capacity, size(), 1, 0);
if (error) {
return error;
}
}
// Create the new element at the given index.
memnew_placement(_ptr + new_size - 1, T(std::move(p_val)));
return OK;
}
template <typename T>
template <bool p_exact>
Error CowData<T>::reserve(USize p_min_capacity) {
USize new_capacity = p_exact ? p_min_capacity : next_capacity(capacity(), p_min_capacity);
if (new_capacity <= capacity()) {
if (p_min_capacity < (USize)size()) {
WARN_VERBOSE("reserve() called with a capacity smaller than the current size. This is likely a mistake.");
}
// No need to reserve more, we already have (at least) the right size.
return OK;
}
if (!_ptr) {
// Initial allocation.
return _alloc_exact(new_capacity);
} else if (_get_refcount()->get() == 1) {
// Grow in-place.
return _realloc_exact(new_capacity);
} else {
// Grow by forking.
return _copy_to_new_buffer_exact(new_capacity, size(), 0, 0);
}
}
template <typename T>
template <bool p_initialize>
Error CowData<T>::resize(Size p_size) {
ERR_FAIL_COND_V(p_size < 0, ERR_INVALID_PARAMETER);
const Size prev_size = size();
if (p_size == prev_size) {
// Caller wants to stay the same size, so we do nothing.
return OK;
}
if (p_size > prev_size) {
// Caller wants to grow.
if (!_ptr) {
// Grow by allocating.
const Error error = _alloc_exact(next_capacity(0, p_size));
if (error) {
return error;
}
} else if (_get_refcount()->get() == 1) {
// Grow in-place.
if ((USize)p_size > capacity()) {
const Error error = _realloc_exact(next_capacity(capacity(), p_size));
if (error) {
return error;
}
}
} else {
// Grow by forking.
const Error error = _copy_to_new_buffer_exact(next_capacity(capacity(), p_size), prev_size, 0, 0);
if (error) {
return error;
}
}
// Construct new elements.
if constexpr (p_initialize) {
memnew_arr_placement(_ptr + prev_size, p_size - prev_size);
}
*_get_size() = p_size;
return OK;
} else {
// Caller wants to shrink.
if (p_size == 0) {
_unref();
return OK;
} else if (_get_refcount()->get() == 1) {
// Shrink in-place.
destruct_arr_placement(_ptr + p_size, prev_size - p_size);
// Shrink buffer if necessary.
const USize new_capacity = smaller_capacity(capacity(), p_size);
if (new_capacity < capacity()) {
Error err = _realloc_exact(new_capacity);
CRASH_COND(err);
}
*_get_size() = p_size;
return OK;
} else {
// Shrink by forking.
const USize new_capacity = smaller_capacity(capacity(), p_size);
return _copy_to_new_buffer_exact(new_capacity, p_size, 0, 0);
}
}
}
template <typename T>
Error CowData<T>::_alloc_exact(USize p_capacity) {
DEV_ASSERT(!_ptr);
uint8_t *mem_new = (uint8_t *)Memory::alloc_static(p_capacity * sizeof(T) + DATA_OFFSET, false);
ERR_FAIL_NULL_V(mem_new, ERR_OUT_OF_MEMORY);
_ptr = _get_data_ptr(mem_new);
// If we alloc, we're guaranteed to be the only reference.
new (_get_refcount()) SafeNumeric<USize>(1);
*_get_size() = 0;
// The actual capacity is whatever we can stuff into the alloc_size.
*_get_capacity() = p_capacity;
return OK;
}
template <typename T>
Error CowData<T>::_realloc_exact(USize p_capacity) {
DEV_ASSERT(_ptr);
uint8_t *mem_new = (uint8_t *)Memory::realloc_static(((uint8_t *)_ptr) - DATA_OFFSET, p_capacity * sizeof(T) + DATA_OFFSET, false);
ERR_FAIL_NULL_V(mem_new, ERR_OUT_OF_MEMORY);
_ptr = _get_data_ptr(mem_new);
// If we realloc, we're guaranteed to be the only reference.
// So the reference was 1 and was copied to be 1 again.
DEV_ASSERT(_get_refcount()->get() == 1);
// The size was also copied from the previous allocation.
// The actual capacity is whatever we can stuff into the alloc_size.
*_get_capacity() = p_capacity;
return OK;
}
template <typename T>
Error CowData<T>::_copy_to_new_buffer_exact(USize p_capacity, USize p_size_from_start, USize p_gap, USize p_size_from_back) {
DEV_ASSERT(p_capacity >= p_size_from_start + p_size_from_back + p_gap);
DEV_ASSERT((USize)size() >= p_size_from_start && (USize)size() >= p_size_from_back);
// Create a temporary CowData to hold ownership over our _ptr.
// It will be used to copy elements from the old buffer over to our new buffer.
// At the end of the block, it will be automatically destructed by going out of scope.
const CowData prev_data;
prev_data._ptr = _ptr;
_ptr = nullptr;
const Error error = _alloc_exact(p_capacity);
if (error) {
// On failure to allocate, recover the old data and return the error.
_ptr = prev_data._ptr;
prev_data._ptr = nullptr;
return error;
}
// Copy over elements.
copy_arr_placement(_ptr, prev_data._ptr, p_size_from_start);
copy_arr_placement(
_ptr + p_size_from_start + p_gap,
prev_data._ptr + prev_data.size() - p_size_from_back,
p_size_from_back);
*_get_size() = p_size_from_start + p_gap + p_size_from_back;
return OK;
}
template <typename T>
Error CowData<T>::_copy_on_write() {
if (!_ptr || _get_refcount()->get() == 1) {
// Nothing to do.
return OK;
}
// Fork to become the only reference.
return _copy_to_new_buffer_exact(capacity(), size(), 0, 0);
}
template <typename T>
void CowData<T>::_ref(const CowData *p_from) {
_ref(*p_from);
}
template <typename T>
void CowData<T>::_ref(const CowData &p_from) {
if (_ptr == p_from._ptr) {
return; // self assign, do nothing.
}
_unref(); // Resets _ptr to nullptr.
if (!p_from._ptr) {
return; //nothing to do
}
if (p_from._get_refcount()->conditional_increment() > 0) { // could reference
_ptr = p_from._ptr;
}
}
template <typename T>
CowData<T>::CowData(std::initializer_list<T> p_init) {
CRASH_COND(_alloc_exact(p_init.size()));
copy_arr_placement(_ptr, p_init.begin(), p_init.size());
*_get_size() = p_init.size();
}
GODOT_GCC_WARNING_POP
// Zero-constructing CowData initializes _ptr to nullptr (and thus empty).
template <typename T>
struct is_zero_constructible<CowData<T>> : std::true_type {};