Pool

#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <cassert>
#include <chrono>
#include <memory>
#include <string.h>
#include <unordered_map>

using namespace std;

using Stamp = int32_t;
constexpr Stamp FreeStamp = 0;

template<typename T>
class Pool;

template<typename T>
class Handle {
private:
  friend class Pool<T>;
  int32_t mIndex { 0 };
  Stamp mStamp { FreeStamp };
  Handle(int32_t index, Stamp stamp) : mIndex(index), mStamp(stamp) { }
public:
  Handle() { }
  ~Handle() { }
};

template<typename T>
class PoolRecord final {
private:
  friend class Pool<T>;
  Stamp mStamp { FreeStamp };
public:
  T mObject;
  template<typename... Args>
  PoolRecord(int stamp, Args&&... args) : mStamp(stamp), mObject(args...) {
  }
  PoolRecord() {
  }
  ~PoolRecord() {
  }
  bool IsValid() const noexcept {
    return mStamp != FreeStamp;
  }
  const T * operator -> () const {
    return &mObject;
  }
  T * operator -> () {
    return &mObject;
  }
};

template<typename T>
class Pool final {
private:
  size_t mSpawnedCount { 0 };
  Stamp mGlobalStamp { 1 };
  PoolRecord<T> * mRecords { nullptr };
  size_t mRecordCount { 0 };
  size_t mCapacity { 0 };
public:
  Pool() {

  }
  ~Pool() {
    for (size_t i = 0; i < mRecordCount; ++i) {
      // Destruct only busy objects, not the free ones
      if (mRecords[i].mStamp != FreeStamp) {
        mRecords[i].mObject.~T();
      }
    }
    free(mRecords);
  }
  template<typename... Args>
  Handle<T> Spawn(Args&&... args) {
    // Find free object
    for (size_t i = 0; i < mRecordCount; ++i) {
      auto & rec = mRecords[i];
      if (rec.mStamp == FreeStamp) {
        rec.mStamp = mGlobalStamp++;
        // Reconstruct object via placement new
        new(&rec.mObject) T(args...);
        ++mSpawnedCount;
        return Handle<T> {static_cast<int32_t>(i), rec.mStamp};
      }
    }
    // No free objects, grow pool
    auto oldCapacity = mCapacity;
    ++mCapacity;
    // Remember old records
    auto old = mRecords;
    // Create new array with larger size
    mRecords = reinterpret_cast<PoolRecord<T>*>(malloc(sizeof(PoolRecord<T>) * mCapacity));
    for (size_t i = 0; i < mCapacity; ++i) {
      if (i == mRecordCount) {
        new(&mRecords[i]) PoolRecord<T>(mGlobalStamp++, args...);
      } else {
        new(&mRecords[i]) PoolRecord<T>(std::move(old[i]));
      }
    }
    // Remove old array of records
    for (size_t i = 0; i < oldCapacity; ++i) {
      old[i].~PoolRecord();
    }
    free(old);
    auto & rec = mRecords[mRecordCount];
    ++mSpawnedCount;
    ++mRecordCount;
    return Handle<T> {static_cast<int32_t>(mRecordCount - 1), rec.mStamp};
  }
  void Return(const Handle<T> & handle) {
    if (static_cast<size_t>(handle.mIndex) >= mRecordCount) {
      throw runtime_error("Handle has invalid index!");
    }
    auto & rec = mRecords[handle.mIndex];
    if (rec.mStamp != FreeStamp) {
      rec.mStamp = FreeStamp;
      rec.mObject.~T(); // destruct
      --mSpawnedCount;
    }
  }
  bool IsValid(const Handle<T> & handle) {
    if (static_cast<size_t>(handle.mIndex) >= mRecordCount) {
      throw runtime_error("Handle has invalid index!");
    }
    return handle.mStamp == mRecords[handle.mIndex].mStamp;
  }
  T & operator[](const Handle<T> & handle) const {
    return mRecords[handle.mIndex].mObject;
  }
  size_t GetSize() const noexcept {
    return mRecordCount;
  }
  size_t GetSpawnedCount() const noexcept {
    return mSpawnedCount;
  }
  size_t GetCapacity() const noexcept {
    return mCapacity;
  }
  PoolRecord<T> * GetRecords() noexcept {
    return mRecords;
  }
  // range-based for
  PoolRecord<T> * begin() {
    return mRecords;
  }
  PoolRecord<T> * end() {
    return mRecords + mRecordCount;
  }
  // Use this only to obtain handle by 'this' pointer inside class method
  // Do not rely on pointers to objects in pool, they can suddenly become invalid
  // this pointer can be used, because it is always valid
  Handle<T> HandleByPointer(const T * ptr) const {
    for (size_t i = 0; i < mRecordCount; ++i) {
      if (&mRecords[i].mObject == ptr) {
        return Handle<T>(static_cast<int32_t>(i), mRecords[i].mStamp);
      }
    }
    return Handle<T>();
  }
};

class PoolableNode {
public:
  string mName { "Unnamed" };
  Handle<PoolableNode> mParent;
  vector<Handle<PoolableNode>> mChildren;
  // pointer to pool always valid, since node allocated inside the pool
  Pool<PoolableNode> * mPool { nullptr };
public:
  PoolableNode() {

  }
  PoolableNode(Pool<PoolableNode> * pool) : PoolableNode() {
    mPool = pool;
    //cout << "Created!" << endl;
  }
  virtual ~PoolableNode() {
    //cout << mName << " Destroyed!" << endl;
    for (auto & child : mChildren) {
      mPool->Return(child);
    }
  }
  void SetName(const string & name) {
    mName = name;
  }
  void AttachTo(const Handle<PoolableNode> & parentHandle) {
    auto & parent = (*mPool)[parentHandle];
    mParent = parentHandle;
    parent.mChildren.push_back(mPool->HandleByPointer(this));
  }
};

class OrdinaryNode : public enable_shared_from_this<OrdinaryNode> {
private:
  string mName;
  weak_ptr<OrdinaryNode> mParent;
  vector<shared_ptr<OrdinaryNode>> mChildren;
public:
  OrdinaryNode() {

  }
  virtual ~OrdinaryNode() {

  }
  void SetName(const string & name) {
    mName = name;
  }
  void AttachTo(const shared_ptr<OrdinaryNode> & parent) {
    parent->mChildren.push_back(shared_from_this());
    mParent = parent;
  }
};

int main(int argc, char **argv) {



  // Sanity tests
  {
    /*
    Pool<PoolableNode> pool;
    vector<Handle<PoolableNode>> nodes;
    for (int i = 0; i < 100; ++i) {
    nodes.push_back(pool.Spawn(&pool));
    }
    for (auto & node : nodes) {
    pool.Return(node);
    }
    */


    Pool<PoolableNode> pool;
    auto a = pool.Spawn(&pool);
    pool[a].SetName("A");
    auto b = pool.Spawn(&pool);
    pool[b].SetName("B");
    auto c = pool.Spawn(&pool);
    pool[c].SetName("C");
    pool.Return(a);
    pool.Return(b);
    pool.Return(c);
    a = pool.Spawn(&pool);
    pool[a].SetName("A");
  }


  {
    Pool<PoolableNode> pool;

    auto handle = pool.Spawn(&pool);
    assert(pool.IsValid(handle));
    assert(pool.GetSize() == 1);

    pool.Return(handle);

    assert(!pool.IsValid(handle));
    assert(pool.GetSize() == 1);
    assert(pool.GetSpawnedCount() == 0);

    auto newHandle = pool.Spawn(&pool);
    assert(pool.IsValid(newHandle));
    assert(pool.GetSpawnedCount() == 1);
    pool.Return(newHandle);
  }


  // Performance test
  {
    constexpr int count = 10000;

    cout << "Object count: " << count << endl;

    // PoolableNode
    {
      Pool<PoolableNode> pool;

      auto lastTime = chrono::high_resolution_clock::now();
      for (int i = 0; i < count; ++i) {
        auto parent = pool.Spawn(&pool);
        pool[parent].SetName("Parent");
        auto child = pool.Spawn(&pool);
        pool[child].SetName("Child");
        pool[child].AttachTo(parent);
        pool.Return(parent);
      }

      cout << "PoolableNode: " << chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - lastTime).count() << " microseconds" << endl;
    }

    // OrdinaryNode
    {
      auto lastTime = chrono::high_resolution_clock::now();

      for (int i = 0; i < count; ++i) {
        auto parent = make_shared<OrdinaryNode>();
        parent->SetName("Parent");
        auto child = make_shared<OrdinaryNode>();
        child->SetName("Child");
        child->AttachTo(parent);
        parent.reset();
      }

      cout << "OrdinaryNode: " << chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - lastTime).count() << " microseconds" << endl;
    }
  }


  system("pause");
  return 0;
}