Reduce unnecessary COW on Vector by make writing explicit

This commit makes operator[] on Vector const and adds a write proxy to it.  From
now on writes to Vectors need to happen through the .write proxy. So for
instance:

Vector<int> vec;
vec.push_back(10);
std::cout << vec[0] << std::endl;
vec.write[0] = 20;

Failing to use the .write proxy will cause a compilation error.

In addition COWable datatypes can now embed a CowData pointer to their data.
This means that String, CharString, and VMap no longer use or derive from
Vector.

_ALWAYS_INLINE_ and _FORCE_INLINE_ are now equivalent for debug and non-debug
builds. This is a lot faster for Vector in the editor and while running tests.
The reason why this difference used to exist is because force-inlined methods
used to give a bad debugging experience. After extensive testing with modern
compilers this is no longer the case.

1 files changed, 59 insertions, 323 deletions

diff --git a/core/vector.h b/core/vector.h
index c026448ddd..7e3da34be0 100644
--- a/core/vector.h
+++ b/core/vector.h
@@ -36,131 +36,69 @@
  * @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
-
-	_FORCE_INLINE_ uint32_t *_get_refcount() const {
-
-		if (!_ptr)
-			return NULL;
+class VectorWriteProxy {
+	friend class Vector<T>;
+	Vector<T> &_parent;
 
-		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 {
+	_FORCE_INLINE_ VectorWriteProxy(Vector<T> &parent) :
+			_parent(parent){};
+	VectorWriteProxy(const VectorWriteProxy<T> &p_other);
 
-		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());
-
-		// no cow needed, since it's reading
-		return _get_data()[p_index];
-	}
+	_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(); }
 
-	Error insert(int p_pos, const T &p_val);
+	_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); }
 
 	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);
 	}
@@ -172,7 +110,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;
@@ -181,235 +119,42 @@ public:
 		insert(i, p_val);
 	}
 
-	void operator=(const Vector &p_from);
-	Vector(const Vector &p_from);
-
-	_FORCE_INLINE_ Vector();
-	_FORCE_INLINE_ ~Vector();
-};
+	int find(const T &p_val, int p_from = 0) const {
+		int ret = -1;
+		if (p_from < 0 || size() == 0)
+			return ret;
 
-template <class T>
-void Vector<T>::_unref(void *p_data) {
+		for (int i = p_from; i < size(); i++) {
 
-	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();
-
-	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() :
+			write(VectorWriteProxy<T>(*this)) {}
+	_FORCE_INLINE_ Vector(const Vector &p_from) :
+			write(VectorWriteProxy<T>(*this)) { _cowdata._ref(p_from._cowdata); }
+	inline Vector &operator=(const Vector &p_from) {
+		_cowdata._ref(p_from._cowdata);
+		return *this;
 	}
-
-	return OK;
-}
+};
 
 template <class T>
 void Vector<T>::invert() {
 
 	for (int i = 0; i < size() / 2; i++) {
-
-		SWAP(operator[](i), operator[](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);
-}
-
-template <class T>
-bool Vector<T>::push_back(const T &p_elem) {
-
-	Error err = resize(size() + 1);
-	ERR_FAIL_COND_V(err, true)
-	set(size() - 1, 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;
+		T *p = ptrw();
+		SWAP(p[i], p[size() - i - 1]);
 	}
 }
 
 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>
 void Vector<T>::append_array(const Vector<T> &p_other) {
 	const int ds = p_other.size();
 	if (ds == 0)
@@ -417,26 +162,17 @@ void Vector<T>::append_array(const Vector<T> &p_other) {
 	const int bs = size();
 	resize(bs + ds);
 	for (int i = 0; i < ds; ++i)
-		operator[](bs + i) = p_other[i];
-}
-
-template <class T>
-Vector<T>::Vector(const Vector &p_from) {
-
-	_ptr = NULL;
-	_copy_from(p_from);
+		ptrw()[bs + i] = p_other[i];
 }
 
 template <class T>
-Vector<T>::Vector() {
-
-	_ptr = NULL;
-}
+bool Vector<T>::push_back(const T &p_elem) {
 
-template <class T>
-Vector<T>::~Vector() {
+	Error err = resize(size() + 1);
+	ERR_FAIL_COND_V(err, true)
+	set(size() - 1, p_elem);
 
-	_unref(_ptr);
+	return false;
 }
 
 #endif