*miscHEADmaster

3 files changed, 725 insertions, 0 deletions

diff --git a/Source/modules/asura-base/Utilities/LinkedList.cpp b/Source/modules/asura-base/Utilities/LinkedList.cpp
deleted file mode 100644
index e69de29..0000000
--- a/Source/modules/asura-base/Utilities/LinkedList.cpp
+++ /dev/null
diff --git a/Source/modules/asura-base/Utilities/LinkedList.h b/Source/modules/asura-base/Utilities/LinkedList.h
index e69de29..5a7dc74 100644
--- a/Source/modules/asura-base/Utilities/LinkedList.h
+++ b/Source/modules/asura-base/Utilities/LinkedList.h
@@ -0,0 +1,388 @@
+#ifndef _ASURA_LINKED_LIST_H_
+#define _ASURA_LINKED_LIST_H_
+
+#include "../Type.h"
+#include <string.h>
+
+#if !ASURA_RELEASE
+#define LINKED_LIST_ASSERT(x) Assert(x)
+#else
+#define LINKED_LIST_ASSERT(x)
+#endif
+
+class ListElement
+{
+public:
+	inline ListElement();
+	inline ~ListElement() { RemoveFromList(); }
+
+	inline bool IsInList() const;
+	inline bool RemoveFromList();
+	inline void InsertInList(ListElement* pos);
+
+	// Check against List::end(), not NULL
+	ListElement* GetPrev() const { return m_Prev; }
+	ListElement* GetNext() const { return m_Next; }
+
+private:
+	// Non copyable
+	ListElement(const ListElement&);
+	ListElement& operator=(const ListElement&);
+
+	ListElement* m_Prev;
+	ListElement* m_Next;
+
+	template <class T> friend class List;
+	inline void ValidateLinks() const;
+
+#if !ASURA_RELEASE
+	// Iterator debugging only
+	template <class T> friend class ListIterator;
+	template <class T> friend class ListConstIterator;
+	void SetList(void* l) { m_List = l; }
+	void* m_List;
+#else	
+	void SetList(void*) {}
+#endif
+};
+
+template <class T>
+class ListNode : public ListElement
+{
+public:
+	ListNode(T* data = NULL) : m_Data(data) {}
+	T& operator*() const { return *m_Data; }
+	T* operator->() const { return m_Data; }
+	T* GetData() const { return m_Data; }
+	void SetData(T* data) { m_Data = data; }
+
+	// We know the type of prev and next element
+	ListNode* GetPrev() const { return static_cast<ListNode*>(ListElement::GetPrev()); }
+	ListNode* GetNext() const { return static_cast<ListNode*>(ListElement::GetNext()); }
+
+private:
+	T * m_Data;
+};
+
+template <class T>
+class ListIterator
+{
+public:
+	ListIterator(T* node = NULL) : m_Node(node) {}
+
+	// Pre- and post-increment operator
+	ListIterator& operator++() { m_Node = m_Node->GetNext(); return *this; }
+	ListIterator  operator++(int) { ListIterator ret(*this); ++(*this); return ret; }
+
+	// Pre- and post-decrement operator
+	ListIterator& operator--() { m_Node = m_Node->GetPrev(); return *this; }
+	ListIterator  operator--(int) { ListIterator ret(*this); --(*this); return ret; }
+
+	T& operator*() const { return static_cast<T&>(*m_Node); }
+	T* operator->() const { return static_cast<T*>(m_Node); }
+
+	friend bool operator !=(const ListIterator& x, const ListIterator& y) { return x.m_Node != y.m_Node; }
+	friend bool operator ==(const ListIterator& x, const ListIterator& y) { return x.m_Node == y.m_Node; }
+
+private:
+	template <class S> friend class List;
+	ListIterator(ListElement* node) : m_Node(node) {}
+	ListElement* m_Node;
+};
+
+
+template <class T>
+class ListConstIterator
+{
+public:
+	ListConstIterator(const T* node = NULL) : m_Node(node) {}
+
+	// Pre- and post-increment operator
+	ListConstIterator& operator++() { m_Node = m_Node->GetNext(); return *this; }
+	ListConstIterator  operator++(int) { ListConstIterator ret(*this); ++(*this); return ret; }
+
+	// Pre- and post-decrement operator
+	ListConstIterator& operator--() { m_Node = m_Node->GetPrev(); return *this; }
+	ListConstIterator  operator--(int) { ListConstIterator ret(*this); --(*this); return ret; }
+
+	const T& operator*() const { return static_cast<const T&>(*m_Node); }
+	const T* operator->() const { return static_cast<const T*>(m_Node); }
+
+	friend bool operator !=(const ListConstIterator& x, const ListConstIterator& y) { return x.m_Node != y.m_Node; }
+	friend bool operator ==(const ListConstIterator& x, const ListConstIterator& y) { return x.m_Node == y.m_Node; }
+
+private:
+	template <class S> friend class List;
+	ListConstIterator(const ListElement* node) : m_Node(node) {}
+	const ListElement* m_Node;
+};
+
+template <class T>
+class List
+{
+public:
+	typedef ListConstIterator<T> const_iterator;
+	typedef ListIterator<T> iterator;
+	typedef T value_type;
+
+	inline  List();
+	inline  ~List();
+
+	void	push_back(T& node) { node.InsertInList(&m_Root); }
+	void	push_front(T& node) { node.InsertInList(m_Root.m_Next); }
+	void	insert(iterator pos, T& node) { node.InsertInList(&(*pos)); }
+	void	erase(iterator pos) { pos->RemoveFromList(); }
+
+	void    pop_back() { if (m_Root.m_Prev != &m_Root) m_Root.m_Prev->RemoveFromList(); }
+	void    pop_front() { if (m_Root.m_Next != &m_Root) m_Root.m_Next->RemoveFromList(); }
+
+	iterator       begin() { return iterator(m_Root.m_Next); }
+	iterator       end() { return iterator(&m_Root); }
+
+	const_iterator begin() const { return const_iterator(m_Root.m_Next); }
+	const_iterator end() const { return const_iterator(&m_Root); }
+
+	T&             front() { LINKED_LIST_ASSERT(!empty()); return static_cast<T&>(*m_Root.m_Next); }
+	T&             back() { LINKED_LIST_ASSERT(!empty()); return static_cast<T&>(*m_Root.m_Prev); }
+
+	const T&       front() const { LINKED_LIST_ASSERT(!empty()); return static_cast<const T&>(*m_Root.m_Next); }
+	const T&       back() const { LINKED_LIST_ASSERT(!empty()); return static_cast<const T&>(*m_Root.m_Prev); }
+
+	bool           empty() const { return begin() == end(); }
+
+	size_t         size_slow() const;
+	inline void    clear();
+	inline void    swap(List& other);
+
+	// Insert list into list (removes elements from source)
+	inline void    insert(iterator pos, List& src);
+	inline void    append(List& src);
+
+private:
+	ListElement m_Root;
+};
+
+
+template <class T>
+List<T>::List()
+{
+	m_Root.m_Prev = &m_Root;
+	m_Root.m_Next = &m_Root;
+	m_Root.SetList(this);
+}
+
+template <class T>
+List<T>::~List()
+{
+	clear();
+}
+
+template <class T>
+size_t List<T>::size_slow() const
+{
+	size_t size = 0;
+	ListElement* node = m_Root.m_Next;
+	while (node != &m_Root)
+	{
+		node = node->m_Next;
+		size++;
+	}
+	return size;
+}
+
+template <class T>
+void List<T>::clear()
+{
+	ListElement* node = m_Root.m_Next;
+	while (node != &m_Root)
+	{
+		ListElement* next = node->m_Next;
+		node->m_Prev = NULL;
+		node->m_Next = NULL;
+		node->SetList(NULL);
+		node = next;
+	}
+	m_Root.m_Next = &m_Root;
+	m_Root.m_Prev = &m_Root;
+}
+
+template <class T>
+void List<T>::swap(List<T>& other)
+{
+	LINKED_LIST_ASSERT(this != &other);
+
+	std::swap(other.m_Root.m_Prev, m_Root.m_Prev);
+	std::swap(other.m_Root.m_Next, m_Root.m_Next);
+
+	if (other.m_Root.m_Prev == &m_Root)
+		other.m_Root.m_Prev = &other.m_Root;
+	if (m_Root.m_Prev == &other.m_Root)
+		m_Root.m_Prev = &m_Root;
+	if (other.m_Root.m_Next == &m_Root)
+		other.m_Root.m_Next = &other.m_Root;
+	if (m_Root.m_Next == &other.m_Root)
+		m_Root.m_Next = &m_Root;
+
+	other.m_Root.m_Prev->m_Next = &other.m_Root;
+	other.m_Root.m_Next->m_Prev = &other.m_Root;
+
+	m_Root.m_Prev->m_Next = &m_Root;
+	m_Root.m_Next->m_Prev = &m_Root;
+
+#if !ASURA_RELEASE
+	iterator my_it, my_end = end();
+	for (my_it = begin(); my_it != my_end; ++my_it)
+		my_it->m_List = this;
+	iterator other_it, other_end = other.end();
+	for (other_it = other.begin(); other_it != other_end; ++other_it)
+		other_it->m_List = &other;
+#endif
+}
+
+template <class T>
+void List<T>::insert(iterator pos, List<T>& src)
+{
+	LINKED_LIST_ASSERT(this != &src);
+	if (src.empty())
+		return;
+
+#if !ASURA_RELEASE
+	iterator src_it, src_end = src.end();
+	for (src_it = src.begin(); src_it != src_end; ++src_it)
+		src_it->m_List = this;
+#endif
+	// Insert source before pos
+	ListElement* a = pos.m_Node->m_Prev;
+	ListElement* b = pos.m_Node;
+	a->m_Next = src.m_Root.m_Next;
+	b->m_Prev = src.m_Root.m_Prev;
+	a->m_Next->m_Prev = a;
+	b->m_Prev->m_Next = b;
+	// Clear source list
+	src.m_Root.m_Next = &src.m_Root;
+	src.m_Root.m_Prev = &src.m_Root;
+}
+
+template <class T>
+void List<T>::append(List& src)
+{
+	insert(end(), src);
+}
+
+ListElement::ListElement()
+{
+	m_Prev = NULL;
+	m_Next = NULL;
+	SetList(NULL);
+}
+
+bool ListElement::IsInList() const
+{
+	return m_Prev != NULL;
+}
+
+bool ListElement::RemoveFromList()
+{
+	if (!IsInList())
+		return false;
+
+#if !ASURA_RELEASE
+	ValidateLinks();
+#endif	
+	m_Prev->m_Next = m_Next;
+	m_Next->m_Prev = m_Prev;
+	m_Prev = NULL;
+	m_Next = NULL;
+	return true;
+}
+
+void ListElement::InsertInList(ListElement* pos)
+{
+	if (this == pos)
+		return;
+
+	if (IsInList())
+		RemoveFromList();
+
+#if !ASURA_RELEASE
+	m_List = pos->m_List;
+	pos->m_Prev->ValidateLinks();
+	pos->ValidateLinks();
+#endif
+	m_Prev = pos->m_Prev;
+	m_Next = pos;
+	m_Prev->m_Next = this;
+	m_Next->m_Prev = this;
+#if !ASURA_RELEASE
+	ValidateLinks();
+#endif
+	return;
+}
+
+void ListElement::ValidateLinks() const
+{
+#if !ASURA_RELEASE
+	LINKED_LIST_ASSERT(m_Prev != NULL && m_Next != NULL);
+	LINKED_LIST_ASSERT(m_Prev->m_Next == this && m_Next->m_Prev == this);
+	LINKED_LIST_ASSERT(m_Prev->m_List == m_List && m_Next->m_List == m_List);
+#endif
+}
+
+/// Allows for iterating a linked list, even if you add / remove any node during traversal.
+template<class T>
+class SafeIterator
+{
+public:
+	SafeIterator(T& list)
+		: m_SourceList(list)
+	{
+		m_CurrentNode = NULL;
+		m_ExecuteList.swap(m_SourceList);
+	}
+
+	~SafeIterator()
+	{
+		// Call Complete if you abort the iteration!
+		LINKED_LIST_ASSERT(m_ExecuteList.empty());
+	}
+
+	// You must call complete if you are in some way aborting list iteration.
+	// If you dont call Complete, the source list will lose nodes that have not yet been iterated permanently.
+	// 
+	/// SafeIterator<Behaviour*> i(myList);
+	/// i =0;
+	/// while(i.GetNext() && ++i != 3)
+	///   (**i).Update();
+	/// i.Complete();
+	void Complete()
+	{
+		m_SourceList.append(m_ExecuteList);
+	}
+
+	typename T::value_type* Next()
+	{
+		if (!m_ExecuteList.empty())
+		{
+			typename T::iterator it = m_ExecuteList.begin();
+			m_CurrentNode = &*it;
+			m_ExecuteList.erase(it);
+			m_SourceList.push_back(*m_CurrentNode);
+		}
+		else
+		{
+			m_CurrentNode = NULL;
+		}
+		return m_CurrentNode;
+	}
+
+	typename T::value_type& operator *() const { return *m_CurrentNode; }
+	typename T::value_type* operator ->() const { return m_CurrentNode; }
+
+private:
+	T m_ExecuteList;
+	T& m_SourceList;
+	typename T::value_type* m_CurrentNode;
+};
+
+
+#endif
diff --git a/Source/modules/asura-base/Utilities/dynamic_array.h b/Source/modules/asura-base/Utilities/dynamic_array.h
new file mode 100644
index 0000000..36885f0
--- /dev/null
+++ b/Source/modules/asura-base/Utilities/dynamic_array.h
@@ -0,0 +1,337 @@
+#pragma once
+
+#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;
+};