Shinya Kitaoka 810553
#pragma once
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef TCG_POOL_H
Toshihiro Shimizu 890ddd
#define TCG_POOL_H
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// STD includes
Toshihiro Shimizu 890ddd
#include "assert.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include <vector></vector>
Toshihiro Shimizu 890ddd
#include <algorithm></algorithm>
Toshihiro Shimizu 890ddd
#include <functional></functional>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Discriminate rvalues support - either use Boost's config.hpp for automatic
Shinya Kitaoka 120a6e
// lookup,
Toshihiro Shimizu 890ddd
// or deal with it manually
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef TCG_RVALUES_SUPPORT
Toshihiro Shimizu 890ddd
#include <boost config.hpp=""></boost>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef BOOST_NO_RVALUE_REFERENCES
Toshihiro Shimizu 890ddd
#define TCG_RVALUES_SUPPORT 0
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
#define TCG_RVALUES_SUPPORT 1
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*!
Toshihiro Shimizu 890ddd
  \file     pool.h
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  \brief    This file contains an implementation of the \a pool container
Shinya Kitaoka 120a6e
  concept.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  \details  A pool is a container that supports two fundamental operations,
Shinya Kitaoka 120a6e
  acquire() and
Shinya Kitaoka 120a6e
            release(), whose purpose is that of marking access operations to a
Shinya Kitaoka 120a6e
  resource
Toshihiro Shimizu 890ddd
            that should not be destroyed when the access operation ends.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
            Creation and destruction of resources can be a time-consuming task
Shinya Kitaoka 120a6e
  that could
Shinya Kitaoka 120a6e
            be avoided when it is known that resources could be reused - which
Shinya Kitaoka 120a6e
  is the very
Toshihiro Shimizu 890ddd
            reason why caching can be a useful approach to some problems.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
            The classical cache concept is nothing more than that of a standard
Shinya Kitaoka 120a6e
  associative
luz paz 6454c4
            map, tweaked to accommodate specific commodities - such as managing
Shinya Kitaoka 120a6e
  the cache
Toshihiro Shimizu 890ddd
            size.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
            However, sometimes resources could be considered to be effectively
luz paz 6454c4
  identical,
Shinya Kitaoka 120a6e
            to the point that assigning a key is merely a way to keep the
Shinya Kitaoka 120a6e
  objects
Shinya Kitaoka 120a6e
            distinct in the cache. Users are in the condition to require only
Shinya Kitaoka 120a6e
  two functions,
Toshihiro Shimizu 890ddd
            one to acquire() a resource, the other to release() it.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
            The Pool concept we are introducing satisfies the following ruleset:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
            
    Shinya Kitaoka 120a6e
                
  • The pool is a dynamical container which allocates resources by
  • Shinya Kitaoka 120a6e
      invoking the
    Toshihiro Shimizu 890ddd
                     objects' default constructor. 
    Shinya Kitaoka 120a6e
                
  • Objects in the pool are \b not destructed, except when the pool
  • Shinya Kitaoka 120a6e
      is explicitly
    Toshihiro Shimizu 890ddd
                     \a squeezed by the user.
    Shinya Kitaoka 120a6e
                
  • Keys are indices, returned by the pool with an incremental
  • Shinya Kitaoka 120a6e
      ordering. 
    Shinya Kitaoka 120a6e
                
  • An object which has been acquired cannot be acquired again
  • Shinya Kitaoka 120a6e
      until it has been
    Toshihiro Shimizu 890ddd
                     released 
    Toshihiro Shimizu 890ddd
                
    Toshihiro Shimizu 890ddd
    */
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
    namespace tcg {
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    //****************************************************************************
    Toshihiro Shimizu 890ddd
    //    TCG Indices Pool  class
    Toshihiro Shimizu 890ddd
    //****************************************************************************
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    template <typename cont="std::vector&lt;T" t="size_t," typename="">></typename>
    Shinya Kitaoka 120a6e
    class indices_pool {
    Toshihiro Shimizu 890ddd
    public:
    Shinya Kitaoka 120a6e
      typedef T value_type;
    Shinya Kitaoka 120a6e
      typedef Cont container_type;
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    private:
    Shinya Kitaoka 120a6e
      T m_start;               //!< First index to be acquired
    Shinya Kitaoka 120a6e
      T m_size;                //!< Current indices count
    Shinya Kitaoka 120a6e
      Cont m_releasedIndices;  //!< Priority queue of released indices
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    public:
    Shinya Kitaoka 120a6e
      indices_pool(value_type start = 0) : m_start(start), m_size(0) {}
    Shinya Kitaoka 120a6e
      ~indices_pool() {}
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      template <typename iter=""></typename>
    Shinya Kitaoka 120a6e
      indices_pool(value_type size, iter releasedBegin, iter releasedEnd,
    Shinya Kitaoka 120a6e
                   value_type start = 0)
    Shinya Kitaoka 120a6e
          : m_start(start)
    Shinya Kitaoka 120a6e
          , m_size(size)
    Shinya Kitaoka 120a6e
          , m_releasedIndices(releasedBegin, releasedEnd) {
    Shinya Kitaoka 120a6e
        std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(),
    Shinya Kitaoka 120a6e
                       std::greater<t>());</t>
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      template <typename iter=""></typename>
    Shinya Kitaoka 120a6e
      indices_pool(iter acquiredBegin, iter acquiredEnd, value_type start = 0)
    Shinya Kitaoka 120a6e
          : m_start(start) {
    Shinya Kitaoka 120a6e
        if (acquiredBegin == acquiredEnd)
    Shinya Kitaoka 120a6e
          m_size = 0;
    Shinya Kitaoka 120a6e
        else {
    Shinya Kitaoka 120a6e
          // Sort the acquired indices
    Shinya Kitaoka 120a6e
          std::vector<t> acquired(acquiredBegin, acquiredEnd);</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          std::sort(acquired.begin(), acquired.end());
    Shinya Kitaoka 120a6e
          assert(acquired.front() >= m_start);
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          // Scan them, adding holes in the acquired sequence to released indices
    Shinya Kitaoka 120a6e
          m_size = acquired.back() - m_start + 1;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          assert(m_size >= (T)acquired.size());
    Shinya Kitaoka 120a6e
          m_releasedIndices.reserve(m_size - acquired.size());
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          T curIdx = m_start;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          typename std::vector<t>::iterator at, aEnd(acquired.end());</t>
    Shinya Kitaoka 120a6e
          for (at = acquired.begin(); at != aEnd; ++at, ++curIdx)
    Shinya Kitaoka 120a6e
            for (; curIdx != *at; ++curIdx) m_releasedIndices.push_back(curIdx);
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(),
    Shinya Kitaoka 120a6e
                         std::greater<t>());</t>
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      value_type size() const { return m_size; }
    Shinya Kitaoka 120a6e
      value_type releasedSize() const { return m_releasedIndices.size(); }
    Shinya Kitaoka 120a6e
      value_type acquiredSize() const { return size() - releasedSize(); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      const container_type &releasedIndices() const { return m_releasedIndices; }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      value_type acquire() {
    Shinya Kitaoka 120a6e
        if (!m_releasedIndices.empty()) {
    Shinya Kitaoka 120a6e
          value_type idx = m_releasedIndices.front();
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          pop_heap(m_releasedIndices.begin(), m_releasedIndices.end(),
    Shinya Kitaoka 120a6e
                   std::greater<t>());</t>
    Shinya Kitaoka 120a6e
          m_releasedIndices.pop_back();
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          return idx;
    Shinya Kitaoka 120a6e
        }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        return m_start + m_size++;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void release(value_type idx) {
    Shinya Kitaoka 120a6e
        m_releasedIndices.push_back(idx);
    Shinya Kitaoka 120a6e
        push_heap(m_releasedIndices.begin(), m_releasedIndices.end(),
    Shinya Kitaoka 120a6e
                  std::greater<t>());</t>
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void clear() {
    Shinya Kitaoka 120a6e
        m_size = 0;
    Shinya Kitaoka 120a6e
        m_releasedIndices.clear();
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      //! Removes pool entries whose index is beyond that of the last acquired one.
    Shinya Kitaoka 120a6e
      void squeeze() {
    Shinya Kitaoka 120a6e
        if (m_releasedIndices.empty()) return;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        std::sort_heap(m_releasedIndices.begin(), m_releasedIndices.end(),
    Shinya Kitaoka 120a6e
                       std::greater<t>());  // O(n logn)</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        // Decrease the pool size as long as the back items are unused
    Shinya Kitaoka 120a6e
        T lastIndex = m_start + m_size - 1;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        typename Cont::iterator ut, uEnd(m_releasedIndices.end());
    Shinya Kitaoka 120a6e
        for (ut = m_releasedIndices.begin(); ut != uEnd && *ut == lastIndex; ++ut)
    Shinya Kitaoka 120a6e
          --lastIndex, --m_size;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        if (ut != m_releasedIndices.begin()) m_releasedIndices.swap(Cont(ut, uEnd));
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(),
    Shinya Kitaoka 120a6e
                       std::greater<t>());  // O(n)</t>
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #if (TCG_RVALUES_SUPPORT > 0)
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      indices_pool(const indices_pool &other)
    Shinya Kitaoka 120a6e
          : m_start(other.m_start)
    Shinya Kitaoka 120a6e
          , m_size(other.m_size)
    Shinya Kitaoka 120a6e
          , m_releasedIndices(other.m_releasedIndices) {}
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      indices_pool &operator=(const indices_pool &other) {
    Shinya Kitaoka 120a6e
        m_start = other.m_start, m_size = other.m_size,
    Shinya Kitaoka 120a6e
        m_releasedIndices = other.m_releasedIndices;
    Shinya Kitaoka 120a6e
        return *this;
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      indices_pool(indices_pool &&other)
    Shinya Kitaoka 120a6e
          : m_start(other.m_start)
    Shinya Kitaoka 120a6e
          , m_size(other.m_size)
    Shinya Kitaoka 120a6e
          , m_releasedIndices(
    Shinya Kitaoka 120a6e
                std::forward<container_type &&="">(other.m_releasedIndices)) {}</container_type>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      indices_pool &operator=(indices_pool &&other) {
    Shinya Kitaoka 120a6e
        m_start = other.m_start, m_size = other.m_size;
    Shinya Kitaoka 120a6e
        m_releasedIndices =
    Shinya Kitaoka 120a6e
            std::forward<container_type &&="">(other.m_releasedIndices);</container_type>
    Shinya Kitaoka 120a6e
        return *this;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #endif
    Toshihiro Shimizu 890ddd
    };
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    //----------------------------------------------------------------
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    template <typename cont="std::vector&lt;T" t,="" typename="">></typename>
    Shinya Kitaoka 120a6e
    class pool {
    Toshihiro Shimizu 890ddd
    public:
    Shinya Kitaoka 120a6e
      typedef T value_type;
    Shinya Kitaoka 120a6e
      typedef Cont container_type;
    Shinya Kitaoka 120a6e
      typedef size_t size_type;
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    private:
    Shinya Kitaoka 120a6e
      Cont m_objects;                       //!< Objects in the pool
    Shinya Kitaoka 120a6e
      tcg::indices_pool<size_t> m_indices;  //!< Indices Pool representing m_objects</size_t>
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    public:
    Shinya Kitaoka 120a6e
      pool() {}
    Shinya Kitaoka 120a6e
      ~pool() {}
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      const tcg::indices_pool<size_t> &indices() const { return m_indices; }</size_t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      size_type size() const {
    Shinya Kitaoka 120a6e
        assert(m_indices.size() <= m_objects.size());
    Shinya Kitaoka 120a6e
        return m_objects.size();
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
      size_type releasedSize() const {
    Shinya Kitaoka 120a6e
        return m_objects.size() - m_indices.acquiredSize();
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
      size_type acquiredSize() const { return m_indices.acquiredSize(); }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      const value_type &operator[](size_type idx) const { return m_objects[idx]; }
    Shinya Kitaoka 120a6e
      value_type &operator[](size_type idx) { return m_objects[idx]; }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      size_type acquire() {
    Shinya Kitaoka 120a6e
        size_t result = m_indices.acquire();
    Shinya Kitaoka 120a6e
        if (result >= m_objects.size()) {
    Shinya Kitaoka 120a6e
          assert(result == m_objects.size());
    Shinya Kitaoka 120a6e
          m_objects.push_back(T());
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
        return result;
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      void release(size_type idx) { m_indices.release(idx); }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      void releaseAll() { m_indices.clear(); }
    Shinya Kitaoka 120a6e
      void clear() {
    Shinya Kitaoka 120a6e
        releaseAll();
    Shinya Kitaoka 120a6e
        m_objects.clear();
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      //! Removes pool entries whose index is beyond that of the last acquired one.
    Shinya Kitaoka 120a6e
      void squeeze() {
    Shinya Kitaoka 120a6e
        m_indices.squeeze();
    Shinya Kitaoka 120a6e
        m_objects.resize(m_indices.size());
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    };
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
    }  // namespace tcg
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
    #endif  // TCG_POOL_H