| #pragma once |
| |
| #ifndef TCG_POOL_H |
| #define TCG_POOL_H |
| |
| |
| #include "assert.h" |
| |
| #include <vector> |
| #include <algorithm> |
| #include <functional> |
| |
| |
| |
| |
| |
| #ifndef TCG_RVALUES_SUPPORT |
| #include <boost/config.hpp> |
| |
| #ifdef BOOST_NO_RVALUE_REFERENCES |
| #define TCG_RVALUES_SUPPORT 0 |
| #else |
| #define TCG_RVALUES_SUPPORT 1 |
| #endif |
| #endif |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| namespace tcg { |
| |
| |
| |
| |
| |
| template <typename T = size_t, typename Cont = std::vector<T>> |
| class indices_pool { |
| public: |
| typedef T value_type; |
| typedef Cont container_type; |
| |
| private: |
| T m_start; |
| T m_size; |
| Cont m_releasedIndices; |
| |
| public: |
| indices_pool(value_type start = 0) : m_start(start), m_size(0) {} |
| ~indices_pool() {} |
| |
| template <typename iter> |
| indices_pool(value_type size, iter releasedBegin, iter releasedEnd, |
| value_type start = 0) |
| : m_start(start) |
| , m_size(size) |
| , m_releasedIndices(releasedBegin, releasedEnd) { |
| std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(), |
| std::greater<T>()); |
| } |
| |
| template <typename iter> |
| indices_pool(iter acquiredBegin, iter acquiredEnd, value_type start = 0) |
| : m_start(start) { |
| if (acquiredBegin == acquiredEnd) |
| m_size = 0; |
| else { |
| |
| std::vector<T> acquired(acquiredBegin, acquiredEnd); |
| |
| std::sort(acquired.begin(), acquired.end()); |
| assert(acquired.front() >= m_start); |
| |
| |
| m_size = acquired.back() - m_start + 1; |
| |
| assert(m_size >= (T)acquired.size()); |
| m_releasedIndices.reserve(m_size - acquired.size()); |
| |
| T curIdx = m_start; |
| |
| typename std::vector<T>::iterator at, aEnd(acquired.end()); |
| for (at = acquired.begin(); at != aEnd; ++at, ++curIdx) |
| for (; curIdx != *at; ++curIdx) m_releasedIndices.push_back(curIdx); |
| |
| std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(), |
| std::greater<T>()); |
| } |
| } |
| |
| value_type size() const { return m_size; } |
| value_type releasedSize() const { return m_releasedIndices.size(); } |
| value_type acquiredSize() const { return size() - releasedSize(); } |
| |
| const container_type &releasedIndices() const { return m_releasedIndices; } |
| |
| value_type acquire() { |
| if (!m_releasedIndices.empty()) { |
| value_type idx = m_releasedIndices.front(); |
| |
| pop_heap(m_releasedIndices.begin(), m_releasedIndices.end(), |
| std::greater<T>()); |
| m_releasedIndices.pop_back(); |
| |
| return idx; |
| } |
| |
| return m_start + m_size++; |
| } |
| |
| void release(value_type idx) { |
| m_releasedIndices.push_back(idx); |
| push_heap(m_releasedIndices.begin(), m_releasedIndices.end(), |
| std::greater<T>()); |
| } |
| |
| void clear() { |
| m_size = 0; |
| m_releasedIndices.clear(); |
| } |
| |
| |
| void squeeze() { |
| if (m_releasedIndices.empty()) return; |
| |
| std::sort_heap(m_releasedIndices.begin(), m_releasedIndices.end(), |
| std::greater<T>()); |
| |
| |
| T lastIndex = m_start + m_size - 1; |
| |
| typename Cont::iterator ut, uEnd(m_releasedIndices.end()); |
| for (ut = m_releasedIndices.begin(); ut != uEnd && *ut == lastIndex; ++ut) |
| --lastIndex, --m_size; |
| |
| if (ut != m_releasedIndices.begin()) m_releasedIndices.swap(Cont(ut, uEnd)); |
| |
| std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(), |
| std::greater<T>()); |
| } |
| |
| #if (TCG_RVALUES_SUPPORT > 0) |
| |
| indices_pool(const indices_pool &other) |
| : m_start(other.m_start) |
| , m_size(other.m_size) |
| , m_releasedIndices(other.m_releasedIndices) {} |
| |
| indices_pool &operator=(const indices_pool &other) { |
| m_start = other.m_start, m_size = other.m_size, |
| m_releasedIndices = other.m_releasedIndices; |
| return *this; |
| } |
| |
| indices_pool(indices_pool &&other) |
| : m_start(other.m_start) |
| , m_size(other.m_size) |
| , m_releasedIndices( |
| std::forward<container_type &&>(other.m_releasedIndices)) {} |
| |
| indices_pool &operator=(indices_pool &&other) { |
| m_start = other.m_start, m_size = other.m_size; |
| m_releasedIndices = |
| std::forward<container_type &&>(other.m_releasedIndices); |
| return *this; |
| } |
| |
| #endif |
| }; |
| |
| |
| |
| template <typename T, typename Cont = std::vector<T>> |
| class pool { |
| public: |
| typedef T value_type; |
| typedef Cont container_type; |
| typedef size_t size_type; |
| |
| private: |
| Cont m_objects; |
| tcg::indices_pool<size_t> m_indices; |
| |
| public: |
| pool() {} |
| ~pool() {} |
| |
| const tcg::indices_pool<size_t> &indices() const { return m_indices; } |
| |
| size_type size() const { |
| assert(m_indices.size() <= m_objects.size()); |
| return m_objects.size(); |
| } |
| size_type releasedSize() const { |
| return m_objects.size() - m_indices.acquiredSize(); |
| } |
| size_type acquiredSize() const { return m_indices.acquiredSize(); } |
| |
| const value_type &operator[](size_type idx) const { return m_objects[idx]; } |
| value_type &operator[](size_type idx) { return m_objects[idx]; } |
| |
| size_type acquire() { |
| size_t result = m_indices.acquire(); |
| if (result >= m_objects.size()) { |
| assert(result == m_objects.size()); |
| m_objects.push_back(T()); |
| } |
| |
| return result; |
| } |
| |
| void release(size_type idx) { m_indices.release(idx); } |
| |
| void releaseAll() { m_indices.clear(); } |
| void clear() { |
| releaseAll(); |
| m_objects.clear(); |
| } |
| |
| |
| void squeeze() { |
| m_indices.squeeze(); |
| m_objects.resize(m_indices.size()); |
| } |
| }; |
| |
| } |
| |
| #endif |