GODOT IS OPEN SOURCE

1 files changed, 401 insertions, 0 deletions

diff --git a/core/vector.h b/core/vector.h
new file mode 100644
index 0000000000..90a9bf715b
--- /dev/null
+++ b/core/vector.h
@@ -0,0 +1,401 @@
+/*************************************************************************/
+/*  vector.h                                                             */
+/*************************************************************************/
+/*                       This file is part of:                           */
+/*                           GODOT ENGINE                                */
+/*                    http://www.godotengine.org                         */
+/*************************************************************************/
+/* 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.                */
+/*************************************************************************/
+#ifndef VECTOR_H
+#define VECTOR_H
+
+/**
+ * @class Vector
+ * @author Juan Linietsky
+ * Vector container. Regular Vector Container. Use with care and for smaller arrays when possible. Use DVector for large arrays.
+*/
+#include "os/memory.h"
+#include "error_macros.h"
+#include "safe_refcount.h"
+#include "sort.h"
+
+template<class T>
+class Vector {
+
+	mutable void* _ptr;
+ 
+ 	// internal helpers
+ 
+ 	_FORCE_INLINE_ SafeRefCount* _get_refcount() const  {
+ 	
+		if (!_ptr)
+ 			return NULL;
+ 			
+		return reinterpret_cast<SafeRefCount*>(_ptr);
+ 	}
+ 	
+	_FORCE_INLINE_ int* _get_size() const  {
+ 	
+		if (!_ptr)
+ 			return NULL;
+		return reinterpret_cast<int*>(((uint8_t*)(_ptr))+sizeof(SafeRefCount));
+ 		
+ 	}
+	_FORCE_INLINE_ T* _get_data() const {
+ 	
+		if (!_ptr)
+ 			return NULL;
+		return reinterpret_cast<T*>(((uint8_t*)(_ptr))+sizeof(SafeRefCount)+sizeof(int));
+ 		
+ 	}
+ 	
+	_FORCE_INLINE_ int _get_alloc_size(int p_elements) const {
+ 	
+ 		return  nearest_power_of_2(p_elements*sizeof(T)+sizeof(SafeRefCount)+sizeof(int));
+ 	}
+ 	
+	void _unref(void *p_data);
+	
+	void _copy_from(const Vector& p_from);
+	void _copy_on_write();
+public:
+
+
+	_FORCE_INLINE_ T *ptr() { 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); }
+	
+	_FORCE_INLINE_ int size() const {
+		
+		if (!_ptr)
+			return 0;
+		else		
+			return *reinterpret_cast<int*>(((uint8_t*)(_ptr))+sizeof(SafeRefCount));
+	}
+	_FORCE_INLINE_ bool empty() const { return _ptr == 0; }
+	Error resize(int p_size);
+	bool push_back(T p_elem);
+	
+	void remove(int 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(T_val& p_val) const;
+
+	void set(int p_index,T p_elem);
+	T get(int p_index) const;
+
+	inline T& operator[](int p_index) {
+
+		if (p_index<0 || p_index>=size()) {
+			T& aux=*((T*)0); //nullreturn
+			ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux);
+		}
+
+		_copy_on_write(); // wants to write, so copy on write.
+		
+		return _get_data()[p_index];
+	}
+
+	inline const T& operator[](int p_index) const {
+
+		if (p_index<0 || p_index>=size()) {
+			const T& aux=*((T*)0); //nullreturn
+			ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux);
+		}
+		// no cow needed, since it's reading
+		return _get_data()[p_index];
+	}
+	
+	Error insert(int p_pos,const T& p_val);
+
+	template<class C>
+	void sort_custom() {
+
+		int len = size();
+		if (len==0)
+			return;
+		T *data = &operator[](0);
+		SortArray<T,C> sorter;
+		sorter.sort(data,len);
+	}
+
+	void sort() {
+
+		sort_custom<_DefaultComparator<T> >();
+	}
+
+
+
+	void operator=(const Vector& p_from);
+	Vector(const Vector& p_from);
+
+	_FORCE_INLINE_ Vector();
+	_FORCE_INLINE_ ~Vector();
+
+};
+
+template<class T>
+void Vector<T>::_unref(void *p_data) {
+
+	if (!p_data)
+		return;
+		
+	SafeRefCount *src = reinterpret_cast<SafeRefCount*>(p_data);
+	
+	if (!src->unref())
+		return; // still in use
+	// clean up
+		
+	int *count = (int*)(src+1);
+	T *data = (T*)(count+1);
+	
+	for (int i=0;i<*count;i++) {
+		// call destructors	
+		data[i].~T();
+	}
+	
+	// free mem
+	memfree(p_data);
+
+}
+
+template<class T>
+void Vector<T>::_copy_on_write() {
+
+	if (!_ptr)
+		return;
+	
+	if (_get_refcount()->get() > 1 ) {
+		/* in use by more than me */
+		SafeRefCount *src_new=(SafeRefCount *)memalloc(_get_alloc_size(*_get_size()));
+		src_new->init();
+		int * _size = (int*)(src_new+1);
+		*_size=*_get_size();
+		
+		T*_data=(T*)(_size+1);
+		
+		// initialize new elements
+		for (int i=0;i<*_size;i++) {
+		
+			memnew_placement(&_data[i], T( _get_data()[i] ) );
+		}
+		
+		_unref(_ptr);
+		_ptr=src_new;
+	}
+
+}
+
+template<class T> template<class T_val>
+int Vector<T>::find(T_val& p_val) const {
+
+	int ret = -1;
+	if (size() == 0) 
+		return ret;
+		
+	for (int i=0; i<size(); i++) {
+	
+		if (operator[](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;
+	}
+	
+	// possibly changing size, copy on write
+	_copy_on_write();
+	
+	if (p_size>size()) {
+
+		if (size()==0) {
+			// alloc from scratch
+			_ptr = (T*)memalloc(_get_alloc_size(p_size));
+			ERR_FAIL_COND_V( !_ptr ,ERR_OUT_OF_MEMORY);
+			_get_refcount()->init(); // init refcount
+			*_get_size()=0; // init size (currently, none)
+
+		} else {
+			
+			void *_ptrnew = (T*)memrealloc(_ptr,_get_alloc_size(p_size));
+			ERR_FAIL_COND_V( !_ptrnew ,ERR_OUT_OF_MEMORY);
+			_ptr=_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 (int i=p_size;i<*_get_size();i++) {
+
+			T* t = &_get_data()[i];
+			t->~T();
+		}
+
+		void *_ptrnew = (T*)memrealloc(_ptr,_get_alloc_size(p_size));
+		ERR_FAIL_COND_V( !_ptrnew ,ERR_OUT_OF_MEMORY);
+		
+		_ptr=_ptrnew;
+		
+		*_get_size()=p_size;
+				
+	}
+
+	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,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(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());
+	for (int i=p_index; i<size()-1; i++) {
+
+		set(i, get(i+1));
+	};
+
+	resize(size()-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 (p_from._get_refcount()->ref()) // 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