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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

 
#ifndef POOL_TYPE_HPP
#define POOL_TYPE_HPP
 
#include "enum_type.hpp"

enum class PoolType : uint8_t {
  Normal, 
  NetworkClient, 
  NetworkAdmin, 
  Data, 
};
using PoolTypes = EnumBitSet<PoolType, uint8_t>;
static constexpr PoolTypes PT_ALL = {PoolType::Normal, PoolType::NetworkClient, PoolType::NetworkAdmin, PoolType::Data};
 
typedef std::vector<struct PoolBase *> PoolVector; 
 
template <typename Tindex>
using AllocationResult = std::pair<void *, Tindex>;
 

struct PoolIDBase {};

template <typename TBaseType, typename TTag, TBaseType TEnd, TBaseType TInvalid>
struct EMPTY_BASES PoolID : PoolIDBase {
  using BaseType = TBaseType;
 
  constexpr PoolID() = default;
  constexpr PoolID(const PoolID &) = default;
  constexpr PoolID(PoolID &&) = default;
 
  explicit constexpr PoolID(const TBaseType &value) : value(value) {}
 
  constexpr PoolID &operator =(const PoolID &rhs) { this->value = rhs.value; return *this; }
  constexpr PoolID &operator =(PoolID &&rhs) { this->value = std::move(rhs.value); return *this; }
 
  /* Only allow conversion to BaseType via method. */
  constexpr TBaseType base() const noexcept { return this->value; }
 
  static constexpr PoolID Begin() { return PoolID{}; }
  static constexpr PoolID End() { return PoolID{static_cast<TBaseType>(TEnd)}; }
  static constexpr PoolID Invalid() { return PoolID{static_cast<TBaseType>(TInvalid)}; }
 
  constexpr auto operator++() { ++this->value; return this; }
  constexpr auto operator+(const std::integral auto &val) const { return this->value + val; }
  constexpr auto operator-(const std::integral auto &val) const { return this->value - val; }
  constexpr auto operator%(const std::integral auto &val) const { return this->value % val; }
 
  constexpr bool operator==(const PoolID<TBaseType, TTag, TEnd, TInvalid> &rhs) const { return this->value == rhs.value; }
  constexpr auto operator<=>(const PoolID<TBaseType, TTag, TEnd, TInvalid> &rhs) const { return this->value <=> rhs.value; }
 
  constexpr bool operator==(const size_t &rhs) const { return this->value == rhs; }
  constexpr auto operator<=>(const size_t &rhs) const { return this->value <=> rhs; }
private:
  /* Do not explicitly initialize. */
  TBaseType value;
};
 
template <typename T> requires std::is_base_of_v<PoolIDBase, T>
constexpr auto operator+(const std::integral auto &val, const T &pool_id) { return pool_id + val; }
template <typename Te, typename Tp> requires std::is_enum_v<Te> && std::is_base_of_v<PoolIDBase, Tp>
constexpr auto operator+(const Te &val, const Tp &pool_id) { return pool_id + to_underlying(val); }

struct PoolBase {
  const PoolType type; 

  static PoolVector *GetPools()
  {
    static PoolVector *pools = new PoolVector();
    return pools;
  }
 
  static void Clean(PoolTypes);

  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, PoolType Tpool_type = PoolType::Normal, bool Tcache = false>
requires std::is_base_of_v<PoolIDBase, Tindex>
struct Pool : PoolBase {
public:
  static constexpr size_t MAX_SIZE = Tindex::End().base(); 
 
  using IndexType = Tindex;
  using BitmapStorage = size_t;
  static constexpr size_t BITMAP_SIZE = std::numeric_limits<BitmapStorage>::digits;
 
  const std::string_view name{}; 
 
  size_t first_free = 0; 
  size_t first_unused = 0; 
  size_t items = 0; 
#ifdef WITH_ASSERT
  size_t checked = 0; 
#endif /* WITH_ASSERT */
  bool cleaning = false; 
 
  std::vector<Titem *> data{}; 
  std::vector<BitmapStorage> used_bitmap{}; 
 
  Pool(std::string_view name) : PoolBase(Tpool_type), name(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 <= MAX_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; }
    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; }
    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, Tpool_type, Tcache> *Tpool>
  struct PoolItem {
    const Tindex index; 

    PoolItem(Tindex index) : index(index) {}

    typedef struct Pool<Titem, Tindex, Tgrowth_step, Tpool_type, Tcache> Pool;

    inline void *operator new(size_t) = delete;

    inline void operator delete(void *p, size_t size)
    {
      if (p == nullptr) return;
      Titem *pn = static_cast<Titem *>(p);
      assert(pn == Tpool->Get(Pool::GetRawIndex(pn->index)));
      Tpool->FreeItem(size, Pool::GetRawIndex(pn->index));
    }

    inline void *operator new(size_t size, Tindex index) = delete;

    inline void *operator new(size_t, void *ptr) = delete;
 

    template <typename T = Titem, typename... Targs>
    requires std::is_base_of_v<Titem, T>
    static inline T *Create(Targs &&... args)
    {
      auto [data, index] = Tpool->GetNew(sizeof(T));
      return ::new (data) T(index, std::forward<Targs&&>(args)...);
    }

    template <typename T = Titem, typename... Targs>
    requires std::is_base_of_v<Titem, T>
    static inline T *CreateAtIndex(Tindex index, Targs &&... args)
    {
      auto [data, _] = Tpool->GetNew(sizeof(T), index.base());
      return ::new (data) T(index, std::forward<Targs&&>(args)...);
    }


    static inline bool CanAllocateItem(size_t n = 1)
    {
      return Tpool->CanAllocate(n);
    }

    static inline bool CleaningPool()
    {
      return Tpool->cleaning;
    }

    static inline bool IsValidID(auto index)
    {
      return Tpool->IsValidID(GetRawIndex(index));
    }

    static inline Titem *Get(auto index)
    {
      return Tpool->Get(GetRawIndex(index));
    }

    static inline Titem *GetIfValid(auto index)
    {
      return GetRawIndex(index) < Tpool->first_unused ? Tpool->Get(GetRawIndex(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 = std::numeric_limits<size_t>::max(); 

  struct AllocCache {
    AllocCache *next;
  };

  AllocCache *alloc_cache = nullptr;
  std::allocator<uint8_t> allocator{};
 
  AllocationResult<Tindex> AllocateItem(size_t size, size_t index);
  void ResizeFor(size_t index);
  size_t FindFirstFree();
 
  AllocationResult<Tindex> GetNew(size_t size);
  AllocationResult<Tindex> GetNew(size_t size, size_t index);
 
  void FreeItem(size_t size, size_t index);
 
  static constexpr size_t GetRawIndex(size_t index) { return index; }
  template <typename T> requires std::is_base_of_v<PoolIDBase, T>
  static constexpr size_t GetRawIndex(const T &index) { return index.base(); }
};
 
#endif /* POOL_TYPE_HPP */