diff options
Diffstat (limited to 'Source/modules/asura-base/Utilities')
| -rw-r--r-- | Source/modules/asura-base/Utilities/LinkedList.cpp | 0 | ||||
| -rw-r--r-- | Source/modules/asura-base/Utilities/LinkedList.h | 388 | ||||
| -rw-r--r-- | Source/modules/asura-base/Utilities/dynamic_array.h | 337 |
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; +}; |