+Unity Runtime codeHEADmaster

1 files changed, 340 insertions, 0 deletions

diff --git a/Runtime/Utilities/dynamic_array.h b/Runtime/Utilities/dynamic_array.h
new file mode 100644
index 0000000..90573d9
--- /dev/null
+++ b/Runtime/Utilities/dynamic_array.h
@@ -0,0 +1,340 @@
+#pragma once
+
+#include "Runtime/Allocator/MemoryMacros.h"
+#include "Runtime/Utilities/StaticAssert.h"
+
+#include <memory> // std::uninitialized_fill
+
+// dynamic_array - simplified version of std::vector<T>
+//
+// features:
+//  . always uses memcpy for copying elements. Your data structures must be simple and can't have internal pointers / rely on copy constructor.
+//  . EASTL like push_back(void) implementation
+//		Existing std STL implementations implement insertion operations by copying from an element.
+//		For example, resize(size() + 1) creates a throw-away temporary object.
+//		There is no way in existing std STL implementations to add an element to a container without implicitly or
+//			explicitly providing one to copy from (aside from some existing POD optimizations).
+//		For expensive-to-construct objects this creates a potentially serious performance problem.
+//  . grows X2 on reallocation
+//  . small code footprint
+//  . clear actually deallocates memory
+//  . resize does NOT initialize members!
+//
+//	Changelog:
+//		Added pop_back()
+//		Added assign()
+//		Added clear() - frees the data, use resize(0) to clear w/o freeing
+//		zero allocation for empty array
+//
+//
+template<typename T>
+struct AlignOfType
+{
+	enum { align = ALIGN_OF(T) };
+};
+
+
+template <typename T, size_t align = AlignOfType<T>::align, MemLabelIdentifier defaultLabel = kMemDynamicArrayId>
+struct dynamic_array
+{
+public:
+	typedef 	T*									iterator;
+	typedef 	const T*							const_iterator;
+	typedef 	T									value_type;
+	typedef 	size_t								size_type;
+	typedef 	size_t								difference_type;
+	typedef 	T&									reference;
+	typedef 	const T&							const_reference;
+
+public:
+
+	dynamic_array() : m_data(NULL), m_label(defaultLabel, NULL), m_size(0), m_capacity(0)  
+	{
+		m_label = MemLabelId(defaultLabel, GET_CURRENT_ALLOC_ROOT_HEADER());
+	}
+
+	dynamic_array(MemLabelRef label) : m_data(NULL), m_label(label), m_size(0), m_capacity(0)
+	{
+	}
+
+	explicit dynamic_array (size_t size, MemLabelRef label)
+	:   m_label(label), m_size(size), m_capacity (size)
+	{
+		m_data = allocate (size);
+	}
+
+	dynamic_array (size_t size, T const& init_value, MemLabelRef label)
+	:	m_label(label), m_size (size), m_capacity (size)
+	{
+		m_data = allocate (size);
+		std::uninitialized_fill (m_data, m_data + size, init_value);
+	}
+
+	~dynamic_array()
+	{
+		if (owns_data())
+			m_data = deallocate(m_data);
+	}
+
+	dynamic_array(const dynamic_array& other) : m_capacity(0), m_size(0), m_label(other.m_label)
+	{
+		//m_label.SetRootHeader(GET_CURRENT_ALLOC_ROOT_HEADER());
+		m_data = NULL;
+		assign(other.begin(), other.end());
+	}
+
+	dynamic_array& operator=(const dynamic_array& other)
+	{
+		// should not allocate memory unless we have to
+		assign(other.begin(), other.end());
+		return *this;
+	}
+
+	void clear()
+	{
+		if (owns_data())
+			m_data = deallocate(m_data);
+		m_size = 0;
+		m_capacity = 0;
+	}
+
+	void assign(const_iterator begin, const_iterator end)
+	{
+		Assert(begin<=end);
+
+		resize_uninitialized(end-begin);
+		memcpy(m_data, begin, m_size * sizeof(T));
+	}
+
+	void erase(iterator input_begin, iterator input_end)
+	{
+		Assert(input_begin <= input_end);
+		Assert(input_begin >= begin());
+		Assert(input_end <= end());
+
+		size_t leftOverSize = end() - input_end;
+		memmove(input_begin, input_end, leftOverSize * sizeof(T));
+		m_size -= input_end - input_begin;
+	}
+
+	iterator erase(iterator position)
+	{
+		Assert(position >= begin());
+		Assert(position < end());
+
+		size_t leftOverSize = end() - position - 1;
+		memmove(position, position+1, leftOverSize * sizeof(T));
+		m_size -= 1;
+
+		return position;
+	}
+
+	iterator insert(iterator insert_before, const_iterator input_begin, const_iterator input_end)
+	{
+		Assert(input_begin <= input_end);
+		Assert(insert_before >= begin());
+		Assert(insert_before <= end());
+
+		// resize (make sure that insertBefore does not get invalid in the meantime because of a reallocation)
+		size_t insert_before_index = insert_before - begin();
+		size_t elements_to_be_moved = size() - insert_before_index;
+		resize_uninitialized((input_end - input_begin) + size());
+		insert_before = begin() + insert_before_index;
+
+		size_t insertsize = input_end - input_begin;
+		// move to the end of where the inserted data will be
+		memmove(insert_before + insertsize, insert_before, elements_to_be_moved * sizeof(T));
+		// inject input data in the hole we just created
+		memcpy(insert_before, input_begin, insertsize * sizeof(T));
+
+		return insert_before;
+	}
+
+	iterator insert(iterator insertBefore, const T& t)   { return insert(insertBefore, &t, &t + 1); }
+
+	void swap(dynamic_array& other) throw()
+	{
+		if (m_data) UNITY_TRANSFER_OWNERSHIP_TO_HEADER(m_data, m_label, other.m_label.GetRootHeader());
+		if (other.m_data) UNITY_TRANSFER_OWNERSHIP_TO_HEADER(other.m_data, other.m_label, m_label.GetRootHeader());
+		std::swap(m_data, other.m_data);
+		std::swap(m_size, other.m_size);
+		std::swap(m_capacity, other.m_capacity);
+		std::swap(m_label, other.m_label);
+	}
+
+	T& push_back()
+	{
+		if (++m_size > capacity())
+			reserve(std::max<size_t>(capacity()*2, 1));
+		return back();
+	}
+
+	void push_back(const T& t)
+	{
+		push_back() = t;
+	}
+
+	void pop_back()
+	{
+		Assert(m_size >= 1);
+		m_size--;
+	}
+
+	void resize_uninitialized(size_t size, bool double_on_resize = false)
+	{
+		m_size = size;
+		if (m_size <= capacity())
+			return;
+
+		if(double_on_resize && size < capacity()*2)
+			size = capacity()*2;
+		reserve(size);
+	}
+
+	void resize_initialized(size_t size, const T& t = T(), bool double_on_resize = false)
+	{
+		if (size > capacity())
+		{
+			size_t requested_size = size;
+			if(double_on_resize && size < capacity()*2)
+				requested_size = capacity()*2;
+			reserve(requested_size);
+		}
+
+		if (size > m_size)
+			std::uninitialized_fill (m_data + m_size, m_data + size, t);
+		m_size = size;
+	}
+
+	void reserve(size_t inCapacity)
+	{
+		if (capacity() >= inCapacity)
+			return;
+
+		if (owns_data())
+		{
+			m_capacity = inCapacity;
+			m_data = reallocate(m_data, inCapacity);
+		}
+		else
+		{
+			T* newData = allocate(inCapacity);
+			memcpy(newData, m_data, m_size * sizeof(T));
+
+			// Invalidate old non-owned data, since using the data from two places is most likely a really really bad idea.
+			#if DEBUGMODE
+			memset(m_data, 0xCD, capacity() * sizeof(T));
+			#endif
+
+			m_capacity = inCapacity; // and clear reference bit
+			m_data = newData;
+		}
+	}
+
+	void assign_external (T* begin, T* end)
+	{
+		if (owns_data())
+			m_data = deallocate(m_data);
+		m_size = m_capacity = reinterpret_cast<value_type*> (end) - reinterpret_cast<value_type*> (begin);
+		Assert(m_size < k_reference_bit);
+		m_capacity |= k_reference_bit;
+		m_data = begin;
+	}
+
+	void set_owns_data (bool ownsData)
+	{
+		if (ownsData)
+			m_capacity &= ~k_reference_bit;
+		else
+			m_capacity |= k_reference_bit;
+	}
+
+	void shrink_to_fit()
+	{
+		if (owns_data())
+		{
+			m_capacity = m_size;
+			m_data = reallocate(m_data, m_size);
+		}
+	}
+
+	const T& back() const { Assert (m_size != 0); return m_data[m_size - 1]; }
+	const T& front() const { Assert (m_size != 0); return m_data[0]; }
+	
+	T& back() { Assert (m_size != 0); return m_data[m_size - 1]; }
+	T& front() { Assert (m_size != 0); return m_data[0]; }
+	
+	T* data () { return m_data; }
+	T const* data () const { return m_data; }
+	
+	bool empty () const { return m_size == 0; }
+	size_t size() const { return m_size; }
+	size_t capacity() const { return m_capacity & ~k_reference_bit; }
+
+	T const& operator[] (size_t index) const { DebugAssert(index < m_size); return m_data[index]; }
+	T& operator[] (size_t index) { DebugAssert(index < m_size); return m_data[index]; }
+
+	T const* begin() const { return m_data; }
+	T* begin() { return m_data; }
+
+	T const* end() const { return m_data + m_size; }
+	T* end() { return m_data + m_size; }
+
+	bool owns_data() { return (m_capacity & k_reference_bit) == 0; }
+
+	bool equals(const dynamic_array& other)
+	{
+		if(m_size != other.m_size)
+			return false;
+
+		for( int i = 0; i < m_size; i++)
+		{
+			if (m_data[i] != other.m_data[i])
+				return false;
+		}
+
+		return true;
+	}
+
+	void set_memory_label (MemLabelRef label)
+	{
+		Assert(m_data == NULL);
+		m_label = label;
+	}
+	
+private:
+
+	static const size_t k_reference_bit = (size_t)1 << (sizeof (size_t) * 8 - 1);
+
+	T* allocate (size_t size)
+	{
+		// If you are getting this error then you are trying to allocate memory for an incomplete type
+		CompileTimeAssert(sizeof(T) != 0, "incomplete type");
+		CompileTimeAssert(align != 0, "incomplete type");
+
+		return static_cast<T*> (UNITY_MALLOC_ALIGNED (m_label, size * sizeof(T), align));
+	}
+
+	T* deallocate (T* data)
+	{
+		Assert(owns_data());
+		UNITY_FREE (m_label, data);
+		return NULL;
+	}
+
+	T* reallocate (T* data, size_t size)
+	{
+		// If you are getting this error then you are trying to allocate memory for an incomplete type
+		CompileTimeAssert(sizeof(T) != 0, "incomplete type");
+		CompileTimeAssert(align != 0, "incomplete type");
+
+		Assert(owns_data());
+		int alignof = static_cast<int>(align);
+		return static_cast<T*> (UNITY_REALLOC_ALIGNED(m_label, data, size * sizeof(T), alignof));
+	}
+
+	T*          m_data;
+	MemLabelId  m_label;
+	size_t      m_size;
+	size_t      m_capacity;
+};