diff options
Diffstat (limited to 'core/vector.h')
| -rw-r--r-- | core/vector.h | 378 |
1 files changed, 66 insertions, 312 deletions
diff --git a/core/vector.h b/core/vector.h index f586471e27..52e8758f9b 100644 --- a/core/vector.h +++ b/core/vector.h @@ -36,129 +36,68 @@ * @author Juan Linietsky * Vector container. Regular Vector Container. Use with care and for smaller arrays when possible. Use PoolVector for large arrays. */ +#include "cowdata.h" #include "error_macros.h" #include "os/memory.h" -#include "safe_refcount.h" #include "sort.h" template <class T> -class Vector { - - mutable T *_ptr; - - // internal helpers +class VectorWriteProxy { + friend class Vector<T>; + CowData<T> *_parent; - _FORCE_INLINE_ uint32_t *_get_refcount() const { + _FORCE_INLINE_ VectorWriteProxy(CowData<T> *parent) : + _parent(parent){}; - 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)); - } +public: + _FORCE_INLINE_ T &operator[](int p_index) { + CRASH_BAD_INDEX(p_index, _parent->size()); - _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 + return _parent->ptrw()[p_index]; } +}; - void _unref(void *p_data); +template <class T> +class Vector { + friend class VectorWriteProxy<T>; - void _copy_from(const Vector &p_from); - void _copy_on_write(); + CowData<T> *_cowdata; public: - _FORCE_INLINE_ T *ptrw() { - if (!_ptr) return NULL; - _copy_on_write(); - return (T *)_get_data(); - } - _FORCE_INLINE_ const T *ptr() const { - if (!_ptr) return NULL; - return _get_data(); - } - - _FORCE_INLINE_ void clear() { resize(0); } + VectorWriteProxy<T> write; - _FORCE_INLINE_ int size() const { - uint32_t *size = (uint32_t *)_get_size(); - if (size) - return *size; - else - return 0; - } - _FORCE_INLINE_ bool empty() const { return _ptr == 0; } - Error resize(int p_size); bool push_back(const T &p_elem); - void remove(int p_index); + void remove(int p_index) { _cowdata->remove(p_index); } void erase(const T &p_val) { int idx = find(p_val); if (idx >= 0) remove(idx); }; void invert(); - template <class T_val> - int find(const T_val &p_val, int p_from = 0) const; - - void set(int p_index, const T &p_elem); - T get(int p_index) const; - - inline T &operator[](int p_index) { - - CRASH_BAD_INDEX(p_index, size()); - - _copy_on_write(); // wants to write, so copy on write. - - return _get_data()[p_index]; - } - - inline const T &operator[](int p_index) const { - - CRASH_BAD_INDEX(p_index, size()); + _FORCE_INLINE_ T *ptrw() { return _cowdata->ptrw(); } + _FORCE_INLINE_ const T *ptr() const { return _cowdata->ptr(); } + _FORCE_INLINE_ void clear() { resize(0); } + _FORCE_INLINE_ bool empty() const { return _cowdata->empty(); } - // no cow needed, since it's reading - return _get_data()[p_index]; - } + _FORCE_INLINE_ T get(int p_index) { return _cowdata->get(p_index); } + _FORCE_INLINE_ const T get(int p_index) const { return _cowdata->get(p_index); } + _FORCE_INLINE_ void set(int p_index, const T &p_elem) { _cowdata->set(p_index, p_elem); } + _FORCE_INLINE_ int size() const { return _cowdata->size(); } + Error resize(int p_size) { return _cowdata->resize(p_size); } + _FORCE_INLINE_ const T &operator[](int p_index) const { return _cowdata->get(p_index); } + Error insert(int p_pos, const T &p_val) { return _cowdata->insert(p_pos, p_val); } - Error insert(int p_pos, const T &p_val); + void append_array(const Vector<T> &p_other); template <class C> void sort_custom() { - int len = size(); + int len = _cowdata->size(); if (len == 0) return; - T *data = &operator[](0); + + T *data = ptrw(); SortArray<T, C> sorter; sorter.sort(data, len); } @@ -170,7 +109,7 @@ public: void ordered_insert(const T &p_val) { int i; - for (i = 0; i < size(); i++) { + for (i = 0; i < _cowdata->size(); i++) { if (p_val < operator[](i)) { break; @@ -179,173 +118,56 @@ public: insert(i, p_val); } - void operator=(const Vector &p_from); - Vector(const Vector &p_from); + int find(const T &p_val, int p_from = 0) const { + int ret = -1; + if (p_from < 0 || size() == 0) + return ret; - _FORCE_INLINE_ Vector(); - _FORCE_INLINE_ ~Vector(); -}; - -template <class T> -void Vector<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 Vector<T>::_copy_on_write() { - - if (!_ptr) - return; - - uint32_t *refc = _get_refcount(); + for (int i = p_from; i < size(); i++) { - if (*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> -template <class T_val> -int Vector<T>::find(const T_val &p_val, int p_from) const { - - int ret = -1; - if (p_from < 0 || size() == 0) - return ret; - - for (int i = p_from; i < size(); i++) { - - if (operator[](i) == p_val) { - ret = i; - break; + if (ptr()[i] == p_val) { + ret = i; + break; + }; }; - }; - return ret; -} - -template <class T> -Error Vector<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; + return ret; } - // 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; + _FORCE_INLINE_ Vector() : + _cowdata(new CowData<T>()), + write(VectorWriteProxy<T>(_cowdata)) {} + _FORCE_INLINE_ Vector(const Vector &p_from) : + _cowdata(new CowData<T>()), + write(VectorWriteProxy<T>(_cowdata)) { _cowdata->_ref(p_from._cowdata); } + inline Vector &operator=(const Vector &p_from) { + _cowdata->_ref(p_from._cowdata); + return *this; } - return OK; -} + _FORCE_INLINE_ ~Vector() { + delete _cowdata; + } +}; template <class T> void Vector<T>::invert() { for (int i = 0; i < size() / 2; i++) { - - SWAP(operator[](i), operator[](size() - i - 1)); + T *p = ptrw(); + SWAP(p[i], p[size() - i - 1]); } } template <class T> -void Vector<T>::set(int p_index, const T &p_elem) { - - operator[](p_index) = p_elem; -} - -template <class T> -T Vector<T>::get(int p_index) const { - - return operator[](p_index); +void Vector<T>::append_array(const Vector<T> &p_other) { + const int ds = p_other.size(); + if (ds == 0) + return; + const int bs = size(); + resize(bs + ds); + for (int i = 0; i < ds; ++i) + ptrw()[bs + i] = p_other[i]; } template <class T> @@ -358,72 +180,4 @@ bool Vector<T>::push_back(const T &p_elem) { return false; } -template <class T> -void Vector<T>::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); -}; - -template <class T> -void Vector<T>::_copy_from(const Vector &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> -void Vector<T>::operator=(const Vector &p_from) { - - _copy_from(p_from); -} - -template <class T> -Error Vector<T>::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; -} - -template <class T> -Vector<T>::Vector(const Vector &p_from) { - - _ptr = NULL; - _copy_from(p_from); -} - -template <class T> -Vector<T>::Vector() { - - _ptr = NULL; -} - -template <class T> -Vector<T>::~Vector() { - - _unref(_ptr); -} - #endif |