ec.cpp

#include <new>
#include <vector>

using Byte = unsigned char; 
using Type = unsigned short;
using Slot = unsigned short;
using Size = decltype(sizeof 0);

// Convieience user-defined literal to make Size (i.e size_t) literals
// e.g 0_z
constexpr Size operator""_z(unsigned long long _value) {
  return static_cast<Size>(_value);
}

struct ComponentTraits {
  // Generate unique value for T but always gives same value for same T
  template<typename T>
  static Type type() {
    static Type id{s_type++};
    return id;
  }
  static inline Type s_type;
};

struct EntityTraits {
  // Generate unique value for T but always gives same value for same T
  template<typename T>
  static Type type() {
    static Type id{s_type++};
    return id;
  }
  static inline Type s_type;
};

// Simple arbitrarily sized bitmap. Used to keep track of used objects
// in Pool below.
struct BitMap {
  using BitType = unsigned long;

  static constexpr const BitType k_bit_one{1};
  static constexpr const Size k_word_bits{8*sizeof(BitType)};
  
  BitMap(Size _bits)
    : m_data{new BitType[words(_bits)]}
    , m_bits{_bits}
  {
    for (Size i{0}; i < words(_bits); i++) {
      m_data[i] = 0;
    }
  }
  
  ~BitMap() {
    delete[] m_data;
  }
  
  void set(Size _bit) {
    m_data[index(_bit)] |= k_bit_one << offset(_bit);
  }
  
  void clear(Size _bit) {
    m_data[index(_bit)] &= ~(k_bit_one << offset(_bit));
  }
  
  bool test(Size _bit) const {
    return !!(m_data[index(_bit)] & (k_bit_one << offset(_bit)));
  }
  
  Size find_first_unset() const {
    for (Size i{0}; i < m_bits; i++) {
      if (!test(i)) {
        return i;
      }
    }
    return -1_z;
  }
  
  template<typename F>
  void each_set(F&& _function) {
    for (Size i{0}; i < m_bits; i++) {
      if (test(i)) {
        _function(i);
      }
    }
  }

private:
  static Size words(Size _bits) {
    return sizeof(BitType) * (_bits / k_word_bits + 1);
  }

  static Size index(Size _bit) {
    return _bit / k_word_bits;
  }
  
  static Size offset(Size _bit) {
    return _bit % k_word_bits;
  }
  
  BitType* m_data;
  Size m_bits;
};

// Simple object pool allocator
struct Pool {
  Pool(Size _size, Size _count)
    : m_size{_size}
    , m_data{new Byte[m_size * _count]}
    , m_bitmap{_count}
  {
  }
  
  ~Pool() {
    delete[] m_data;
  }

  Slot allocate() {
    Size bit{m_bitmap.find_first_unset()};
    m_bitmap.set(bit);
    return static_cast<Slot>(bit);
  }
  
  void deallocate(Slot _slot) {
    m_bitmap.clear(_slot);
  }
  
  void* data_at(Slot _slot) {
    return m_data + m_size * _slot;
  }
  
  const void* data_at(Slot _slot) const {
    return m_data + m_size * _slot;
  }
  
  template<typename F>
  void each(F&& _function) {
    m_bitmap.each_set([this, _function](Size _bit) {
      _function(data_at(static_cast<Slot>(_bit)));
    });
  }

private:
  Size m_size;
  Byte* m_data;
  BitMap m_bitmap;
};

struct World {
  static constexpr const Size k_max_components{65536};
  static constexpr const Size k_max_entities{65536};

  template<typename T, typename... Ts>
  T& create(Ts&&... _arguments) {
    Slot slot{create_entity<T>(_arguments...)};
    return access_entity<T>(slot);
  }
  
  template<typename T>
  void destroy(T& _entity) {
    destroy_entity<T>(_entity.m_slot);
  }
  
  ~World() {
    for (Size i{0}; i < m_component_pools.size(); i++) {
      delete m_component_pools[i];
    }
    for (Size i{0}; i < m_entity_pools.size(); i++) {
      delete m_entity_pools[i];
    }
  }
  
  template<typename T, typename F>
  void each_entity(F&& _function) {
    m_entity_pools[EntityTraits::type<T>()]->each([_function](void* _data) {
      _function(*reinterpret_cast<T*>(_data));
    });
  }
  
  template<typename T, typename F>
  void each_component(F&& _function) {
    m_component_pools[ComponentTraits::type<T>()]->each([_function](void* _data) {
      _function(*reinterpret_cast<T*>(_data));
    });
  }
  
private:
  template<typename T>
  friend struct Component;

  // entity management
  template<typename T, typename... Ts>
  Slot create_entity(Ts&&... _arguments) {
    const Type type{EntityTraits::type<T>()};
    if (type >= m_entity_pools.size()) {
      m_entity_pools.resize(type + 1);
    }
    if (!m_entity_pools[type]) {
      m_entity_pools[type] = new Pool(sizeof(T), k_max_entities);
    }
    Slot slot{allocate_entity(type)};
    T* data{new (access_entity(type, slot)) T{this, _arguments...}};
    data->m_slot = slot;
    return slot;
  }

  template<typename T>
  void destroy_entity(Slot _slot) {
    access_entity<T>(_slot).~T();
    deallocate_entity(EntityTraits::type<T>(), _slot);
  }

  Slot allocate_entity(Type _type) {
    return m_entity_pools[_type]->allocate();
  }

  void deallocate_entity(Type _type, Slot _slot) {
    m_entity_pools[_type]->deallocate(_slot);
  }

  template<typename T>
  T& access_entity(Slot _slot) {
    return *reinterpret_cast<T*>(access_entity(EntityTraits::type<T>(), _slot));
  }
  
  template<typename T>
  const T& access_entity(Slot _slot) const {
    return *reinterpret_cast<const T*>(access_entity(EntityTraits::type<T>(), _slot));
  }

  void* access_entity(Type _type, Slot _slot) {
    return m_entity_pools[_type]->data_at(_slot);
  }
  
  const void* access_entity(Type _type, Slot _slot) const {
    return m_entity_pools[_type]->data_at(_slot);
  }
  
  // component management
  template<typename T, typename... Ts>
  Slot create_component(Ts&&... _arguments) {
    const Type type{ComponentTraits::type<T>()};
    if (type >= m_component_pools.size()) {
      m_component_pools.resize(type + 1);
    }
    if (!m_component_pools[type]) {
      m_component_pools[type] = new Pool(sizeof(T), k_max_components);
    }
    Slot slot{allocate_component(type)};
    new (access_component(type, slot)) T{_arguments...};
    return slot;
  }
  
  template<typename T>
  void destroy_component(Slot _slot) {
    access_component<T>(_slot).~T();
    deallocate_component(ComponentTraits::type<T>(), _slot);
  }

  Slot allocate_component(Type _type) {
    return m_component_pools[_type]->allocate();
  }
  
  void deallocate_component(Type _type, Slot _slot) {
    m_component_pools[_type]->deallocate(_slot);
  }

  template<typename T>
  T& access_component(Slot _slot) {
    return *reinterpret_cast<T*>(access_component(ComponentTraits::type<T>(), _slot));
  }
  
  template<typename T>
  const T& access_component(Slot _slot) const {
    return *reinterpret_cast<const T*>(access_component(ComponentTraits::type<T>(), _slot));
  }

  void* access_component(Type _type, Slot _slot) {
    return m_component_pools[_type]->data_at(_slot);
  }
  
  const void* access_component(Type _type, Slot _slot) const {
    return m_component_pools[_type]->data_at(_slot);
  }
  
  std::vector<Pool*> m_component_pools;
  std::vector<Pool*> m_entity_pools;
};

// Every entity inherits from this.
struct Entity {
  Entity(World* _world)
    : m_world{_world}
  {
  }
  
  World* world() const {
    return m_world;
  }

private:
  friend struct World;

  World* m_world;
  Slot m_slot;
};

// Fields of an entity are to be wrapped in this box type. This permits
// SoA style access on entities.
template<typename T>
struct Component {
  Component() = delete;

  template<typename B, typename... Ts>
  Component(B* _base, Ts&&... _arguments)
    : m_base{find_base(_base)}
    , m_slot{world()->template create_component<T>(_arguments...)}
  {
  }
  
  ~Component() {
    world()->template destroy_component<T>(m_slot);
  }
  
  operator T&() {
    return world()->template access_component<T>(m_slot);
  }
  
  operator const T&() const {
    return world()->template access_component<T>(m_slot);
  }
  
  T& operator*() {
    return operator T&();
  }
  
  const T& operator*() const {
    return operator T&();
  }
  
  T* operator->() {
    return &operator T&();
  }
  
  const T* operator->() const {
    return &operator T&();
  }
  
  T& operator=(const T& _value) {
    operator T&() = _value;
    return *this;
  }

private:
  using Base = unsigned short;

  template<typename B>
  Base find_base(const B* _base) const {
    // This function searches for the base Entity class and encodes the
    // difference in m_base. This works only because Component objects
    // are members of the entity structure and the entity structure
    // inherits from Entity.
    //
    // This will fail in spectacular ways if the distance between the
    // base class and the Component exceeds 65536 bytes. Since components
    // are represented by a Base and Slot (2 bytes each) you'd need to
    // have an entity with 32768 Components before this happens.
    return static_cast<Base>(reinterpret_cast<const Byte*>(this) - reinterpret_cast<const Byte*>(_base));
  }

  World* world() const {
    // Reconstruct the pointer the base then get the World from it.
    return reinterpret_cast<const Entity*>(reinterpret_cast<const Byte*>(this) - m_base)->world();
  }

  Base m_base;
  Slot m_slot;
  
};


// Usage:
//
// Entites are represented by a structure that has members of type
// Component<T> and inherits from Entity.
// 
// e.g:
//   struct Player : Entity {
//     Component<std::string> name;
//   };
//
// Every entity must have a constructor which takes World*
//
// e.g:
//   Player::Player(World* world)
//
// Every component must be given `this` in its' constructor.
//
// e.g:
//   name{this}
//
//
// Any additional arguments in the constructor are the constructor
// arguments for the component data. Likewise, World::create can be
// passed arguments which become additional constructor arguments for
// the entity itself.

#include <string>
#include <iostream>

struct Player : Entity {
  Player(World* world, const std::string& initial_name={})
    : Entity{world}
    , name{this, initial_name} // Can pass constructor arguments for T here after `this`
    , score{this}
  {
    std::cout << "Player::Player" << std::endl;
  }
  
  ~Player() {
    std::cout << "Player::~Player()" << std::endl;
  }

  // Components of an entity are always the same size regardless of
  // the type here. They're always 4 bytes.
  //
  // Or in other words an entity is always 2*n_components + sizeof(Entity)
  // in size.
  Component<std::string> name;
  Component<int> score;
};

int main() {
  World w;
  
  std::cout << "sizeof Entity: " << sizeof(Entity) << std::endl;
  std::cout << "sizeof Player: " << sizeof(Player) << std::endl;
  
  Player& player1 = w.create<Player>("alpha");
  Player& player2 = w.create<Player>("omega");
  
  player1.score = 42;
  player2.score = 30;
  
  // SoA access e.g:
  //
  // You can enumerate entities like this, this is all linear in memory
  w.each_entity<Player>([](Player& _player) {
    std::cout << *_player.name << " : " << *_player.score << std::endl;
  });
  
  // You can enumerate components like this, this is all linear in memory
  w.each_component<int>([](const int& _score) {
    std::cout << _score << std::endl;
  });
  
  // Calls the destructor on all components owned by the entity,
  // releases them from the component pools to be reused and releases
  // the entity itself from the entity pool to be reused
  w.destroy(player1);
  w.destroy(player2);
}