| #ifndef _DEPOOLARRAY_HPP |
| #define _DEPOOLARRAY_HPP |
| /*------------------------------------------------------------------------- |
| * drawElements C++ Base Library |
| * ----------------------------- |
| * |
| * Copyright 2014 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| * |
| *//*! |
| * \file |
| * \brief Array template backed by memory pool. |
| *//*--------------------------------------------------------------------*/ |
| |
| #include "deDefs.hpp" |
| #include "deMemPool.hpp" |
| #include "deInt32.h" |
| |
| #include <iterator> |
| |
| namespace de |
| { |
| |
| //! Self-test for PoolArray |
| void PoolArray_selfTest (void); |
| |
| template<typename T, deUint32 Alignment> |
| class PoolArrayConstIterator; |
| |
| template<typename T, deUint32 Alignment> |
| class PoolArrayIterator; |
| |
| /*--------------------------------------------------------------------*//*! |
| * \brief Array template backed by memory pool |
| * |
| * \note Memory in PoolArray is not contiguous so pointer arithmetic |
| * to access next element(s) doesn't work. |
| * \todo [2013-02-11 pyry] Make elements per page template argument. |
| *//*--------------------------------------------------------------------*/ |
| template<typename T, deUint32 Alignment = (sizeof(T) > sizeof(void*) ? (deUint32)sizeof(void*) : (deUint32)sizeof(T))> |
| class PoolArray |
| { |
| public: |
| typedef PoolArrayIterator<T, Alignment> Iterator; |
| typedef PoolArrayConstIterator<T, Alignment> ConstIterator; |
| |
| typedef Iterator iterator; |
| typedef ConstIterator const_iterator; |
| |
| explicit PoolArray (MemPool* pool); |
| PoolArray (MemPool* pool, const PoolArray<T, Alignment>& other); |
| ~PoolArray (void); |
| |
| void clear (void); |
| |
| void reserve (deUintptr capacity); |
| void resize (deUintptr size); |
| void resize (deUintptr size, const T& value); |
| |
| deUintptr size (void) const { return m_numElements; } |
| bool empty (void) const { return m_numElements == 0;} |
| |
| void pushBack (const T& value); |
| T popBack (void); |
| |
| const T& at (deIntptr ndx) const { return *getPtr(ndx); } |
| T& at (deIntptr ndx) { return *getPtr(ndx); } |
| |
| const T& operator[] (deIntptr ndx) const { return at(ndx); } |
| T& operator[] (deIntptr ndx) { return at(ndx); } |
| |
| Iterator begin (void) { return Iterator(this, 0); } |
| Iterator end (void) { return Iterator(this, (deIntptr)m_numElements); } |
| |
| ConstIterator begin (void) const { return ConstIterator(this, 0); } |
| ConstIterator end (void) const { return ConstIterator(this, (deIntptr)m_numElements); } |
| |
| const T& front (void) const { return at(0); } |
| T& front (void) { return at(0); } |
| |
| const T& back (void) const { return at(m_numElements-1); } |
| T& back (void) { return at(m_numElements-1); } |
| |
| private: |
| enum |
| { |
| ELEMENTS_PER_PAGE_LOG2 = 4 //!< 16 elements per page. |
| }; |
| |
| PoolArray (const PoolArray<T, Alignment>& other); // \note Default copy ctor is not allowed, use PoolArray(pool, copy) instead. |
| |
| T* getPtr (deIntptr ndx) const; |
| |
| MemPool* m_pool; |
| |
| deUintptr m_numElements; //!< Number of elements in the array. |
| deUintptr m_capacity; //!< Number of allocated elements in the array. |
| |
| deUintptr m_pageTableCapacity; //!< Size of the page table. |
| void** m_pageTable; //!< Pointer to the page table. |
| }; |
| |
| template<typename T, deUint32 Alignment> |
| class PoolArrayIteratorBase |
| { |
| public: |
| PoolArrayIteratorBase (deUintptr ndx) : m_ndx(ndx) {} |
| ~PoolArrayIteratorBase (void) {} |
| |
| deIntptr getNdx (void) const throw() { return m_ndx; } |
| |
| protected: |
| deIntptr m_ndx; |
| }; |
| |
| template<typename T, deUint32 Alignment> |
| class PoolArrayConstIterator : public PoolArrayIteratorBase<T, Alignment> |
| { |
| public: |
| PoolArrayConstIterator (void); |
| PoolArrayConstIterator (const PoolArray<T, Alignment>* array, deIntptr ndx); |
| PoolArrayConstIterator (const PoolArrayIterator<T, Alignment>& iterator); |
| ~PoolArrayConstIterator (void); |
| |
| // \note Default assignment and copy-constructor are auto-generated. |
| |
| const PoolArray<T, Alignment>* getArray (void) const throw() { return m_array; } |
| |
| // De-reference operators. |
| const T* operator-> (void) const throw() { return &(*m_array)[this->m_ndx]; } |
| const T& operator* (void) const throw() { return (*m_array)[this->m_ndx]; } |
| const T& operator[] (deUintptr offs) const throw() { return (*m_array)[this->m_ndx+offs]; } |
| |
| // Pre-increment and decrement. |
| PoolArrayConstIterator<T, Alignment>& operator++ (void) { this->m_ndx += 1; return *this; } |
| PoolArrayConstIterator<T, Alignment>& operator-- (void) { this->m_ndx -= 1; return *this; } |
| |
| // Post-increment and decrement. |
| PoolArrayConstIterator<T, Alignment> operator++ (int) { PoolArrayConstIterator<T, Alignment> copy(*this); this->m_ndx +=1; return copy; } |
| PoolArrayConstIterator<T, Alignment> operator-- (int) { PoolArrayConstIterator<T, Alignment> copy(*this); this->m_ndx -=1; return copy; } |
| |
| // Compound assignment. |
| PoolArrayConstIterator<T, Alignment>& operator+= (deIntptr offs) { this->m_ndx += offs; return *this; } |
| PoolArrayConstIterator<T, Alignment>& operator-= (deIntptr offs) { this->m_ndx -= offs; return *this; } |
| |
| // Assignment from non-const. |
| PoolArrayConstIterator<T, Alignment>& operator= (const PoolArrayIterator<T, Alignment>& iter); |
| |
| private: |
| const PoolArray<T, Alignment>* m_array; |
| }; |
| |
| template<typename T, deUint32 Alignment> |
| class PoolArrayIterator : public PoolArrayIteratorBase<T, Alignment> |
| { |
| public: |
| PoolArrayIterator (void); |
| PoolArrayIterator (PoolArray<T, Alignment>* array, deIntptr ndx); |
| ~PoolArrayIterator (void); |
| |
| // \note Default assignment and copy-constructor are auto-generated. |
| |
| PoolArray<T, Alignment>* getArray (void) const throw() { return m_array; } |
| |
| // De-reference operators. |
| T* operator-> (void) const throw() { return &(*m_array)[this->m_ndx]; } |
| T& operator* (void) const throw() { return (*m_array)[this->m_ndx]; } |
| T& operator[] (deUintptr offs) const throw() { return (*m_array)[this->m_ndx+offs]; } |
| |
| // Pre-increment and decrement. |
| PoolArrayIterator<T, Alignment>& operator++ (void) { this->m_ndx += 1; return *this; } |
| PoolArrayIterator<T, Alignment>& operator-- (void) { this->m_ndx -= 1; return *this; } |
| |
| // Post-increment and decrement. |
| PoolArrayIterator<T, Alignment> operator++ (int) { PoolArrayIterator<T, Alignment> copy(*this); this->m_ndx +=1; return copy; } |
| PoolArrayIterator<T, Alignment> operator-- (int) { PoolArrayIterator<T, Alignment> copy(*this); this->m_ndx -=1; return copy; } |
| |
| // Compound assignment. |
| PoolArrayIterator<T, Alignment>& operator+= (deIntptr offs) { this->m_ndx += offs; return *this; } |
| PoolArrayIterator<T, Alignment>& operator-= (deIntptr offs) { this->m_ndx -= offs; return *this; } |
| |
| private: |
| PoolArray<T, Alignment>* m_array; |
| }; |
| |
| // Initializer helper for array. |
| template<typename T> |
| struct PoolArrayElement |
| { |
| static void constructDefault (void* ptr) { new (ptr) T(); } //!< Called for non-initialized memory. |
| static void constructCopy (void* ptr, const T& val) { new (ptr) T(val); } //!< Called for non-initialized memory when initial value is provided. |
| static void destruct (T* ptr) { ptr->~T(); } //!< Called when element is destructed. |
| }; |
| |
| // Specialization for basic types. |
| #define DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(TYPE) \ |
| template<> struct PoolArrayElement<TYPE> { \ |
| static void constructDefault (void*) {} \ |
| static void constructCopy (void* ptr, TYPE val) { *(TYPE*)ptr = val; } \ |
| static void destruct (TYPE*) {} \ |
| } |
| |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint8); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint16); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint32); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint64); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt8); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt16); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt32); |
| DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt64); |
| |
| // PoolArray<T> implementation. |
| |
| template<typename T, deUint32 Alignment> |
| PoolArray<T, Alignment>::PoolArray (MemPool* pool) |
| : m_pool (pool) |
| , m_numElements (0) |
| , m_capacity (0) |
| , m_pageTableCapacity (0) |
| , m_pageTable (0) |
| { |
| DE_ASSERT(deIsPowerOfTwo32(Alignment)); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| PoolArray<T, Alignment>::~PoolArray (void) |
| { |
| // Clear resets values to T() |
| clear(); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline void PoolArray<T, Alignment>::clear (void) |
| { |
| resize(0); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline void PoolArray<T, Alignment>::resize (deUintptr newSize) |
| { |
| if (newSize < m_numElements) |
| { |
| // Destruct elements that are no longer active. |
| for (deUintptr ndx = newSize; ndx < m_numElements; ndx++) |
| PoolArrayElement<T>::destruct(getPtr(ndx)); |
| |
| m_numElements = newSize; |
| } |
| else if (newSize > m_numElements) |
| { |
| deUintptr prevSize = m_numElements; |
| |
| reserve(newSize); |
| m_numElements = newSize; |
| |
| // Fill new elements with default values |
| for (deUintptr ndx = prevSize; ndx < m_numElements; ndx++) |
| PoolArrayElement<T>::constructDefault(getPtr(ndx)); |
| } |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline void PoolArray<T, Alignment>::resize (deUintptr newSize, const T& value) |
| { |
| if (newSize < m_numElements) |
| resize(newSize); // value is not used |
| else if (newSize > m_numElements) |
| { |
| deUintptr prevSize = m_numElements; |
| |
| reserve(newSize); |
| m_numElements = newSize; |
| |
| // Fill new elements with copies of value |
| for (deUintptr ndx = prevSize; ndx < m_numElements; ndx++) |
| PoolArrayElement<T>::constructCopy(getPtr(ndx), value); |
| } |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline void PoolArray<T, Alignment>::reserve (deUintptr capacity) |
| { |
| if (capacity >= m_capacity) |
| { |
| void* oldPageTable = DE_NULL; |
| deUintptr oldPageTableSize = 0; |
| |
| deUintptr newCapacity = (deUintptr)deAlignPtr((void*)capacity, 1 << ELEMENTS_PER_PAGE_LOG2); |
| deUintptr reqPageTableCapacity = newCapacity >> ELEMENTS_PER_PAGE_LOG2; |
| |
| if (m_pageTableCapacity < reqPageTableCapacity) |
| { |
| deUintptr newPageTableCapacity = max(2*m_pageTableCapacity, reqPageTableCapacity); |
| void** newPageTable = (void**)m_pool->alloc(newPageTableCapacity * sizeof(void*)); |
| deUintptr i; |
| |
| for (i = 0; i < m_pageTableCapacity; i++) |
| newPageTable[i] = m_pageTable[i]; |
| |
| for (; i < newPageTableCapacity; i++) |
| newPageTable[i] = DE_NULL; |
| |
| // Grab information about old page table for recycling purposes. |
| oldPageTable = m_pageTable; |
| oldPageTableSize = m_pageTableCapacity * sizeof(T*); |
| |
| m_pageTable = newPageTable; |
| m_pageTableCapacity = newPageTableCapacity; |
| } |
| |
| // Allocate new pages. |
| { |
| deUintptr elementSize = (deUintptr)deAlignPtr((void*)(deUintptr)sizeof(T), Alignment); |
| deUintptr pageAllocSize = elementSize << ELEMENTS_PER_PAGE_LOG2; |
| deUintptr pageTableNdx = m_capacity >> ELEMENTS_PER_PAGE_LOG2; |
| |
| // Allocate new pages from recycled old page table. |
| for (;;) |
| { |
| void* newPage = deAlignPtr(oldPageTable, Alignment); |
| deUintptr alignPadding = (deUintptr)newPage - (deUintptr)oldPageTable; |
| |
| if (oldPageTableSize < pageAllocSize+alignPadding) |
| break; // No free space for alloc + alignment. |
| |
| DE_ASSERT(m_pageTableCapacity > pageTableNdx); |
| DE_ASSERT(!m_pageTable[pageTableNdx]); |
| m_pageTable[pageTableNdx++] = newPage; |
| |
| oldPageTable = (void*)((deUint8*)newPage + pageAllocSize); |
| oldPageTableSize -= pageAllocSize+alignPadding; |
| } |
| |
| // Allocate the rest of the needed pages from the pool. |
| for (; pageTableNdx < reqPageTableCapacity; pageTableNdx++) |
| { |
| DE_ASSERT(!m_pageTable[pageTableNdx]); |
| m_pageTable[pageTableNdx] = m_pool->alignedAlloc(pageAllocSize, Alignment); |
| } |
| |
| m_capacity = pageTableNdx << ELEMENTS_PER_PAGE_LOG2; |
| DE_ASSERT(m_capacity >= newCapacity); |
| } |
| } |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline void PoolArray<T, Alignment>::pushBack (const T& value) |
| { |
| resize(size()+1); |
| at(size()-1) = value; |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline T PoolArray<T, Alignment>::popBack (void) |
| { |
| T val = at(size()-1); |
| resize(size()-1); |
| return val; |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline T* PoolArray<T, Alignment>::getPtr (deIntptr ndx) const |
| { |
| DE_ASSERT(inBounds<deIntptr>(ndx, 0, (deIntptr)m_numElements)); |
| deUintptr pageNdx = ((deUintptr)ndx >> ELEMENTS_PER_PAGE_LOG2); |
| deUintptr subNdx = (deUintptr)ndx & ((1 << ELEMENTS_PER_PAGE_LOG2) - 1); |
| deUintptr elemSize = (deUintptr)deAlignPtr((void*)(deUintptr)sizeof(T), Alignment); |
| T* ptr = (T*)((deUint8*)m_pageTable[pageNdx] + (subNdx*elemSize)); |
| DE_ASSERT(deIsAlignedPtr(ptr, Alignment)); |
| return ptr; |
| } |
| |
| // PoolArrayIteratorBase implementation |
| |
| template<typename T, deUint32 Alignment> |
| inline bool operator== (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b) |
| { |
| // \todo [2013-02-08 pyry] Compare array ptr. |
| return a.getNdx() == b.getNdx(); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline bool operator!= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b) |
| { |
| // \todo [2013-02-08 pyry] Compare array ptr. |
| return a.getNdx() != b.getNdx(); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline bool operator< (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b) |
| { |
| return a.getNdx() < b.getNdx(); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline bool operator> (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b) |
| { |
| return a.getNdx() > b.getNdx(); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline bool operator<= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b) |
| { |
| return a.getNdx() <= b.getNdx(); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline bool operator>= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b) |
| { |
| return a.getNdx() >= b.getNdx(); |
| } |
| |
| // PoolArrayConstIterator<T> implementation |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (void) |
| : PoolArrayIteratorBase<T, Alignment> (0) |
| , m_array (DE_NULL) |
| { |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (const PoolArray<T, Alignment>* array, deIntptr ndx) |
| : PoolArrayIteratorBase<T, Alignment> (ndx) |
| , m_array (array) |
| { |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (const PoolArrayIterator<T, Alignment>& iter) |
| : PoolArrayIteratorBase<T, Alignment> (iter) |
| , m_array (iter.getArray()) |
| { |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayConstIterator<T, Alignment>::~PoolArrayConstIterator (void) |
| { |
| } |
| |
| // Arithmetic operators. |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayConstIterator<T, Alignment> operator+ (const PoolArrayConstIterator<T, Alignment>& iter, deIntptr offs) |
| { |
| return PoolArrayConstIterator<T, Alignment>(iter->getArray(), iter->getNdx()+offs); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayConstIterator<T, Alignment> operator+ (deUintptr offs, const PoolArrayConstIterator<T, Alignment>& iter) |
| { |
| return PoolArrayConstIterator<T, Alignment>(iter->getArray(), iter->getNdx()+offs); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| PoolArrayConstIterator<T, Alignment> operator- (const PoolArrayConstIterator<T, Alignment>& iter, deIntptr offs) |
| { |
| return PoolArrayConstIterator<T, Alignment>(iter.getArray(), iter.getNdx()-offs); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| deIntptr operator- (const PoolArrayConstIterator<T, Alignment>& iter, const PoolArrayConstIterator<T, Alignment>& other) |
| { |
| return iter.getNdx()-other.getNdx(); |
| } |
| |
| // PoolArrayIterator<T> implementation. |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayIterator<T, Alignment>::PoolArrayIterator (void) |
| : PoolArrayIteratorBase<T, Alignment> (0) |
| , m_array (DE_NULL) |
| { |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayIterator<T, Alignment>::PoolArrayIterator (PoolArray<T, Alignment>* array, deIntptr ndx) |
| : PoolArrayIteratorBase<T, Alignment> (ndx) |
| , m_array (array) |
| { |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayIterator<T, Alignment>::~PoolArrayIterator (void) |
| { |
| } |
| |
| // Arithmetic operators. |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayIterator<T, Alignment> operator+ (const PoolArrayIterator<T, Alignment>& iter, deIntptr offs) |
| { |
| return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()+offs); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| inline PoolArrayIterator<T, Alignment> operator+ (deUintptr offs, const PoolArrayIterator<T, Alignment>& iter) |
| { |
| return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()+offs); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| PoolArrayIterator<T, Alignment> operator- (const PoolArrayIterator<T, Alignment>& iter, deIntptr offs) |
| { |
| return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()-offs); |
| } |
| |
| template<typename T, deUint32 Alignment> |
| deIntptr operator- (const PoolArrayIterator<T, Alignment>& iter, const PoolArrayIterator<T, Alignment>& other) |
| { |
| return iter.getNdx()-other.getNdx(); |
| } |
| |
| } // de |
| |
| // std::iterator_traits specializations |
| namespace std |
| { |
| |
| template<typename T, deUint32 Alignment> |
| struct iterator_traits<de::PoolArrayConstIterator<T, Alignment> > |
| { |
| typedef deIntptr difference_type; |
| typedef T value_type; |
| typedef const T* pointer; |
| typedef const T& reference; |
| typedef random_access_iterator_tag iterator_category; |
| }; |
| |
| template<typename T, deUint32 Alignment> |
| struct iterator_traits<de::PoolArrayIterator<T, Alignment> > |
| { |
| typedef deIntptr difference_type; |
| typedef T value_type; |
| typedef T* pointer; |
| typedef T& reference; |
| typedef random_access_iterator_tag iterator_category; |
| }; |
| |
| } // std |
| |
| #endif // _DEPOOLARRAY_HPP |