pool_type.hpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef POOL_TYPE_HPP
#define POOL_TYPE_HPP
 
#include "enum_type.hpp"
 
enum PoolType {
  PT_NONE    = 0x00, 
  PT_NORMAL  = 0x01, 
  PT_NCLIENT = 0x02, 
  PT_NADMIN  = 0x04, 
  PT_DATA    = 0x08, 
  PT_ALL     = 0x0F, 
};
DECLARE_ENUM_AS_BIT_SET(PoolType)
 
typedef std::vector<struct PoolBase *> PoolVector; 
 
struct PoolBase {
  const PoolType type; 
 
  static PoolVector *GetPools()
  {
    static PoolVector *pools = new PoolVector();
    return pools;
  }
 
  static void Clean(PoolType);
 
  PoolBase(PoolType pt) : type(pt)
  {
    PoolBase::GetPools()->push_back(this);
  }
 
  virtual ~PoolBase();
 
  virtual void CleanPool() = 0;
 
private:
  PoolBase(const PoolBase &other);
};
 
template <class Titem, typename Tindex, size_t Tgrowth_step, size_t Tmax_size, PoolType Tpool_type = PT_NORMAL, bool Tcache = false, bool Tzero = true>
struct Pool : PoolBase {
  /* Ensure the highest possible index, i.e. Tmax_size -1, is within the bounds of Tindex. */
  static_assert(Tmax_size - 1 <= MAX_UVALUE(Tindex));
 
  static constexpr size_t MAX_SIZE = Tmax_size; 
 
  using BitmapStorage = size_t;
  static constexpr size_t BITMAP_SIZE = std::numeric_limits<BitmapStorage>::digits;
 
  const char * const name; 
 
  size_t size;         
  size_t first_free;   
  size_t first_unused; 
  size_t items;        
#ifdef WITH_ASSERT
  size_t checked;      
#endif /* WITH_ASSERT */
  bool cleaning;       
 
  Titem **data;        
  std::vector<BitmapStorage> used_bitmap; 
 
  Pool(const char *name);
  void CleanPool() override;
 
  inline Titem *Get(size_t index)
  {
    assert(index < this->first_unused);
    return this->data[index];
  }
 
  inline bool IsValidID(size_t index)
  {
    return index < this->first_unused && this->Get(index) != nullptr;
  }
 
  inline bool CanAllocate(size_t n = 1)
  {
    bool ret = this->items <= Tmax_size - n;
#ifdef WITH_ASSERT
    this->checked = ret ? n : 0;
#endif /* WITH_ASSERT */
    return ret;
  }
 
  template <class T>
  struct PoolIterator {
    typedef T value_type;
    typedef T *pointer;
    typedef T &reference;
    typedef size_t difference_type;
    typedef std::forward_iterator_tag iterator_category;
 
    explicit PoolIterator(size_t index) : index(index)
    {
      this->ValidateIndex();
    };
 
    bool operator==(const PoolIterator &other) const { return this->index == other.index; }
    bool operator!=(const PoolIterator &other) const { return !(*this == other); }
    T * operator*() const { return T::Get(this->index); }
    PoolIterator & operator++() { this->index++; this->ValidateIndex(); return *this; }
 
  private:
    size_t index;
    void ValidateIndex()
    {
      while (this->index < T::GetPoolSize() && !(T::IsValidID(this->index))) this->index++;
      if (this->index >= T::GetPoolSize()) this->index = T::Pool::MAX_SIZE;
    }
  };
 
  /*
   * Iterable ensemble of all valid T
   * @tparam T Type of the class/struct that is going to be iterated
   */
  template <class T>
  struct IterateWrapper {
    size_t from;
    IterateWrapper(size_t from = 0) : from(from) {}
    PoolIterator<T> begin() { return PoolIterator<T>(this->from); }
    PoolIterator<T> end() { return PoolIterator<T>(T::Pool::MAX_SIZE); }
    bool empty() { return this->begin() == this->end(); }
  };
 
  template <class T, class F>
  struct PoolIteratorFiltered {
    typedef T value_type;
    typedef T *pointer;
    typedef T &reference;
    typedef size_t difference_type;
    typedef std::forward_iterator_tag iterator_category;
 
    explicit PoolIteratorFiltered(size_t index, F filter) : index(index), filter(filter)
    {
      this->ValidateIndex();
    };
 
    bool operator==(const PoolIteratorFiltered &other) const { return this->index == other.index; }
    bool operator!=(const PoolIteratorFiltered &other) const { return !(*this == other); }
    T * operator*() const { return T::Get(this->index); }
    PoolIteratorFiltered & operator++() { this->index++; this->ValidateIndex(); return *this; }
 
  private:
    size_t index;
    F filter;
    void ValidateIndex()
    {
      while (this->index < T::GetPoolSize() && !(T::IsValidID(this->index) && this->filter(this->index))) this->index++;
      if (this->index >= T::GetPoolSize()) this->index = T::Pool::MAX_SIZE;
    }
  };
 
  /*
   * Iterable ensemble of all valid T
   * @tparam T Type of the class/struct that is going to be iterated
   */
  template <class T, class F>
  struct IterateWrapperFiltered {
    size_t from;
    F filter;
    IterateWrapperFiltered(size_t from, F filter) : from(from), filter(filter) {}
    PoolIteratorFiltered<T, F> begin() { return PoolIteratorFiltered<T, F>(this->from, this->filter); }
    PoolIteratorFiltered<T, F> end() { return PoolIteratorFiltered<T, F>(T::Pool::MAX_SIZE, this->filter); }
    bool empty() { return this->begin() == this->end(); }
  };
 
  template <struct Pool<Titem, Tindex, Tgrowth_step, Tmax_size, Tpool_type, Tcache, Tzero> *Tpool>
  struct PoolItem {
    Tindex index; 
 
    typedef struct Pool<Titem, Tindex, Tgrowth_step, Tmax_size, Tpool_type, Tcache, Tzero> Pool;
 
    inline void *operator new(size_t size)
    {
      return Tpool->GetNew(size);
    }
 
    inline void operator delete(void *p)
    {
      if (p == nullptr) return;
      Titem *pn = static_cast<Titem *>(p);
      assert(pn == Tpool->Get(pn->index));
      Tpool->FreeItem(pn->index);
    }
 
    inline void *operator new(size_t size, size_t index)
    {
      return Tpool->GetNew(size, index);
    }
 
    inline void *operator new(size_t, void *ptr)
    {
      for (size_t i = 0; i < Tpool->first_unused; i++) {
        /* Don't allow creating new objects over existing.
         * Even if we called the destructor and reused this memory,
         * we don't know whether 'size' and size of currently allocated
         * memory are the same (because of possible inheritance).
         * Use { size_t index = item->index; delete item; new (index) item; }
         * instead to make sure destructor is called and no memory leaks. */
        assert(ptr != Tpool->data[i]);
      }
      return ptr;
    }
 
 
    static inline bool CanAllocateItem(size_t n = 1)
    {
      return Tpool->CanAllocate(n);
    }
 
    static inline bool CleaningPool()
    {
      return Tpool->cleaning;
    }
 
    static inline bool IsValidID(size_t index)
    {
      return Tpool->IsValidID(index);
    }
 
    static inline Titem *Get(size_t index)
    {
      return Tpool->Get(index);
    }
 
    static inline Titem *GetIfValid(size_t index)
    {
      return index < Tpool->first_unused ? Tpool->Get(index) : nullptr;
    }
 
    static inline size_t GetPoolSize()
    {
      return Tpool->first_unused;
    }
 
    static inline size_t GetNumItems()
    {
      return Tpool->items;
    }
 
    static inline void PostDestructor([[maybe_unused]] size_t index) { }
 
    static Pool::IterateWrapper<Titem> Iterate(size_t from = 0) { return Pool::IterateWrapper<Titem>(from); }
  };
 
private:
  static const size_t NO_FREE_ITEM = MAX_UVALUE(size_t); 
 
  struct AllocCache {
    AllocCache *next;
  };
 
  AllocCache *alloc_cache;
 
  void *AllocateItem(size_t size, size_t index);
  void ResizeFor(size_t index);
  size_t FindFirstFree();
 
  void *GetNew(size_t size);
  void *GetNew(size_t size, size_t index);
 
  void FreeItem(size_t index);
};
 
#endif /* POOL_TYPE_HPP */