diff options
Diffstat (limited to 'core/cowdata.h')
| -rw-r--r-- | core/cowdata.h | 332 |
1 files changed, 332 insertions, 0 deletions
diff --git a/core/cowdata.h b/core/cowdata.h new file mode 100644 index 0000000000..66e7d1c343 --- /dev/null +++ b/core/cowdata.h @@ -0,0 +1,332 @@ +/*************************************************************************/ +/* cowdata.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* */ +/* 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. */ +/*************************************************************************/ + +#ifndef COWDATA_H_ +#define COWDATA_H_ + +#include "os/memory.h" +#include "safe_refcount.h" + +template <class T> +class Vector; +class String; +class CharString; +template <class T, class V> +class VMap; + +template <class T> +class CowData { + template <class TV> + friend class Vector; + friend class String; + friend class CharString; + template <class TV, class VV> + friend class VMap; + +private: + mutable T *_ptr; + + // internal helpers + + _FORCE_INLINE_ uint32_t *_get_refcount() const { + + if (!_ptr) + return NULL; + + return reinterpret_cast<uint32_t *>(_ptr) - 2; + } + + _FORCE_INLINE_ uint32_t *_get_size() const { + + if (!_ptr) + return NULL; + + return reinterpret_cast<uint32_t *>(_ptr) - 1; + } + + _FORCE_INLINE_ T *_get_data() const { + + if (!_ptr) + return NULL; + return reinterpret_cast<T *>(_ptr); + } + + _FORCE_INLINE_ size_t _get_alloc_size(size_t p_elements) const { + //return nearest_power_of_2_templated(p_elements*sizeof(T)+sizeof(SafeRefCount)+sizeof(int)); + return next_power_of_2(p_elements * sizeof(T)); + } + + _FORCE_INLINE_ bool _get_alloc_size_checked(size_t p_elements, size_t *out) const { +#if defined(_add_overflow) && defined(_mul_overflow) + size_t o; + size_t p; + if (_mul_overflow(p_elements, sizeof(T), &o)) return false; + *out = next_power_of_2(o); + if (_add_overflow(o, static_cast<size_t>(32), &p)) return false; //no longer allocated here + return true; +#else + // Speed is more important than correctness here, do the operations unchecked + // and hope the best + *out = _get_alloc_size(p_elements); + return true; +#endif + } + + void _unref(void *p_data); + void _ref(const CowData &p_from); + void _copy_on_write(); + +public: + void operator=(const CowData<T> &p_from) { _ref(p_from); } + + _FORCE_INLINE_ T *ptrw() { + _copy_on_write(); + return (T *)_get_data(); + } + + _FORCE_INLINE_ const T *ptr() const { + return _get_data(); + } + + _FORCE_INLINE_ int size() const { + uint32_t *size = (uint32_t *)_get_size(); + if (size) + return *size; + else + return 0; + } + + _FORCE_INLINE_ void clear() { resize(0); } + _FORCE_INLINE_ bool empty() const { return _ptr == 0; } + + _FORCE_INLINE_ void set(int p_index, const T &p_elem) { + + CRASH_BAD_INDEX(p_index, size()); + _copy_on_write(); + _get_data()[p_index] = p_elem; + } + + _FORCE_INLINE_ T &get_m(int p_index) { + + CRASH_BAD_INDEX(p_index, size()); + _copy_on_write(); + return _get_data()[p_index]; + } + + _FORCE_INLINE_ const T &get(int p_index) const { + + CRASH_BAD_INDEX(p_index, size()); + + return _get_data()[p_index]; + } + + Error resize(int p_size); + + _FORCE_INLINE_ void remove(int p_index) { + + ERR_FAIL_INDEX(p_index, size()); + T *p = ptrw(); + int len = size(); + for (int i = p_index; i < len - 1; i++) { + + p[i] = p[i + 1]; + }; + + resize(len - 1); + }; + + Error insert(int p_pos, const T &p_val) { + + ERR_FAIL_INDEX_V(p_pos, size() + 1, ERR_INVALID_PARAMETER); + resize(size() + 1); + for (int i = (size() - 1); i > p_pos; i--) + set(i, get(i - 1)); + set(p_pos, p_val); + + return OK; + }; + + _FORCE_INLINE_ CowData(); + _FORCE_INLINE_ ~CowData(); + _FORCE_INLINE_ CowData(CowData<T> &p_from) { _ref(p_from); }; +}; + +template <class T> +void CowData<T>::_unref(void *p_data) { + + if (!p_data) + return; + + uint32_t *refc = _get_refcount(); + + if (atomic_decrement(refc) > 0) + return; // still in use + // clean up + + uint32_t *count = _get_size(); + T *data = (T *)(count + 1); + + for (uint32_t i = 0; i < *count; ++i) { + // call destructors + data[i].~T(); + } + + // free mem + Memory::free_static((uint8_t *)p_data, true); +} + +template <class T> +void CowData<T>::_copy_on_write() { + + if (!_ptr) + return; + + uint32_t *refc = _get_refcount(); + + if (unlikely(*refc > 1)) { + /* in use by more than me */ + uint32_t current_size = *_get_size(); + + uint32_t *mem_new = (uint32_t *)Memory::alloc_static(_get_alloc_size(current_size), true); + + *(mem_new - 2) = 1; //refcount + *(mem_new - 1) = current_size; //size + + T *_data = (T *)(mem_new); + + // initialize new elements + for (uint32_t i = 0; i < current_size; i++) { + + memnew_placement(&_data[i], T(_get_data()[i])); + } + + _unref(_ptr); + _ptr = _data; + } +} + +template <class T> +Error CowData<T>::resize(int p_size) { + + ERR_FAIL_COND_V(p_size < 0, ERR_INVALID_PARAMETER); + + if (p_size == size()) + return OK; + + if (p_size == 0) { + // wants to clean up + _unref(_ptr); + _ptr = NULL; + return OK; + } + + // possibly changing size, copy on write + _copy_on_write(); + + size_t alloc_size; + ERR_FAIL_COND_V(!_get_alloc_size_checked(p_size, &alloc_size), ERR_OUT_OF_MEMORY); + + if (p_size > size()) { + + if (size() == 0) { + // alloc from scratch + uint32_t *ptr = (uint32_t *)Memory::alloc_static(alloc_size, true); + ERR_FAIL_COND_V(!ptr, ERR_OUT_OF_MEMORY); + *(ptr - 1) = 0; //size, currently none + *(ptr - 2) = 1; //refcount + + _ptr = (T *)ptr; + + } else { + void *_ptrnew = (T *)Memory::realloc_static(_ptr, alloc_size, true); + ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY); + _ptr = (T *)(_ptrnew); + } + + // construct the newly created elements + T *elems = _get_data(); + + for (int i = *_get_size(); i < p_size; i++) { + + memnew_placement(&elems[i], T); + } + + *_get_size() = p_size; + + } else if (p_size < size()) { + + // deinitialize no longer needed elements + for (uint32_t i = p_size; i < *_get_size(); i++) { + + T *t = &_get_data()[i]; + t->~T(); + } + + void *_ptrnew = (T *)Memory::realloc_static(_ptr, alloc_size, true); + ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY); + + _ptr = (T *)(_ptrnew); + + *_get_size() = p_size; + } + + return OK; +} + +template <class T> +void CowData<T>::_ref(const CowData &p_from) { + + if (_ptr == p_from._ptr) + return; // self assign, do nothing. + + _unref(_ptr); + _ptr = NULL; + + if (!p_from._ptr) + return; //nothing to do + + if (atomic_conditional_increment(p_from._get_refcount()) > 0) { // could reference + _ptr = p_from._ptr; + } +} + +template <class T> +CowData<T>::CowData() { + + _ptr = NULL; +} + +template <class T> +CowData<T>::~CowData() { + + _unref(_ptr); +} + +#endif /* COW_H_ */ |