archetype.hpp

Go to the documentation of this file.

#pragma once
 
#include <co_ecs/chunk.hpp>
#include <co_ecs/component.hpp>
#include <co_ecs/detail/hash_map.hpp>
#include <co_ecs/entity.hpp>
#include <co_ecs/entity_location.hpp>
 
#include <bit>
 
namespace co_ecs {
 
class archetype {
public:
    using chunks_storage_t = std::vector<chunk>;
 
    archetype() = default;
 
    explicit archetype(component_meta_set components) : _components(std::move(components)) {
        _max_size = get_max_size(_components);
        init_blocks(_components);
        _chunks.emplace_back(_blocks, _max_size);
    }
 
    [[nodiscard]] auto components() const noexcept -> const component_meta_set& {
        return _components;
    }
 
    [[nodiscard]] auto chunks() noexcept -> chunks_storage_t& {
        return _chunks;
    }
 
    [[nodiscard]] auto chunks() const noexcept -> const chunks_storage_t& {
        return _chunks;
    }
 
    template<component... Components>
    auto emplace(entity ent, Components&&... components) -> entity_location {
        auto& free_chunk = ensure_free_chunk();
        auto entry_index = free_chunk.size();
        auto chunk_index = _chunks.size() - 1;
        free_chunk.emplace_back(ent, std::forward<Components>(components)...);
        return entity_location{
            this,
            chunk_index,
            entry_index,
        };
    }
 
    auto swap_erase(const entity_location& location) noexcept -> std::optional<entity> {
        auto& chunk = get_chunk(location);
        auto& last_chunk = _chunks.back();
        auto maybe_ent = chunk.swap_erase(location.entry_index, last_chunk);
        if (last_chunk.empty() && _chunks.size() > 1) {
            _chunks.pop_back();
        }
        return maybe_ent;
    }
 
    auto move(const entity_location& location, archetype& other) -> std::pair<entity_location, std::optional<entity>> {
        auto& free_chunk = other.ensure_free_chunk();
        auto& chunk = get_chunk(location);
 
        assert((location.entry_index < chunk.size()) && "Entity location index exceeds chunk size");
 
        auto entry_index = chunk.move(location.entry_index, free_chunk);
        auto moved = swap_erase(location);
        auto new_location = entity_location{
            &other,
            other._chunks.size() - 1,
            entry_index,
        };
 
        return std::make_pair(new_location, moved);
    }
 
    auto copy(const entity_location& location, archetype& other) -> entity_location {
        auto& free_chunk = other.ensure_free_chunk();
        auto& chunk = get_chunk(location);
 
        assert((location.entry_index < chunk.size()) && "Entity location index exceeds chunk size");
 
        auto entry_index = chunk.copy(location.entry_index, free_chunk);
        auto new_location = entity_location{
            &other,
            other._chunks.size() - 1,
            entry_index,
        };
 
        return new_location;
    }
 
    void visit(const entity_location& location, auto&& func) {
        get_chunk(location).visit(location.entry_index, std::forward<decltype(func)>(func));
    }
 
    void visit(const entity_location& location, auto&& func) const {
        get_chunk(location).visit(location.entry_index, std::forward<decltype(func)>(func));
    }
 
    template<component C>
    auto get(entity_location location) -> C& {
        return read_impl<C&>(*this, location);
    }
 
    template<component C>
    auto get(entity_location location) const -> const C& {
        return read_impl<const C&>(*this, location);
    }
 
    template<component C>
    [[nodiscard]] auto contains() const noexcept -> bool {
        return components().contains<C>();
    }
 
private:
    void init_blocks(const component_meta_set& components_meta) {
        // make space for entity
        auto offset = add_block(0, component_meta::of<entity>());
 
        // space for all components
        for (const auto& meta : components_meta) {
            offset = add_block(offset, meta);
        }
    }
 
    auto add_block(std::size_t offset, const component_meta& meta) -> std::size_t {
        const std::size_t size_in_bytes = _max_size * meta.type->size;
        const std::size_t align = meta.type->align;
 
        _blocks.emplace(meta.id, offset, meta);
 
        offset += detail::mod_2n(offset, align) + size_in_bytes;
 
        return offset;
    }
 
    // Calculates the maximum size of individual components this chunk buffer can hold
    static auto get_max_size(auto&& components_meta) -> std::size_t {
        // Calculate size of the following structure:
        //
        // struct {
        //     component_a_t a;
        //     component_b_t b;
        //     component_c_t c;
        //     ...
        // };
        //
        auto aligned_size = aligned_components_size(components_meta);
 
        // handle subtraction overflow - chunk size is insufficient to hold at least one such entity
        if (aligned_size > chunk::chunk_bytes) [[unlikely]] {
            throw insufficient_chunk_size{ aligned_size, chunk::chunk_bytes };
        }
 
        // Remaining size for packed components
        auto remaining_space = chunk::chunk_bytes - aligned_size;
 
        // Calculate how much components we can pack into remaining space
        auto remaining_elements_count = remaining_space / packed_components_size(components_meta);
 
        // The maximum amount of entities we can hold is grater by 1 for which we calculated aligned_size
        return remaining_elements_count + 1;
    }
 
    // Calculate size of packed structure of components
    static auto packed_components_size(auto&& components_meta) noexcept -> std::size_t {
        return std::accumulate(components_meta.begin(),
            components_meta.end(),
            component_meta::of<entity>().type->size,
            [](const auto& res, const auto& meta) { return res + meta.type->size; });
    }
 
    // Calculate size of properly aligned structure of components
    static auto aligned_components_size(auto&& components_meta) noexcept -> std::size_t {
        auto begin = chunk::alloc_alignment;
        auto end = begin;
 
        // Add single component element size accounting for its alignment
        auto add_elements = [&end](const component_meta& meta) {
            end += detail::mod_2n(std::bit_cast<std::size_t>(end), meta.type->align);
            end += meta.type->size;
        };
 
        add_elements(component_meta::of<entity>());
        for (const auto& meta : components_meta) {
            add_elements(meta);
        }
 
        return end - begin;
    }
 
    template<component_reference ComponentRef>
    static auto read_impl(auto&& self, entity_location location) -> ComponentRef {
        auto& chunk = self.get_chunk(location);
        assert((location.entry_index < chunk.size()) && "Entity location index exceeds chunk size");
        return *component_fetch::fetch_pointer<ComponentRef>(chunk, location.entry_index);
    }
 
    static auto get_chunk_impl(auto&& self, entity_location location) noexcept -> decltype(auto) {
        assert((location.archetype == std::addressof(self))
               && "Location archetype pointer does not point to this archetype");
        assert((location.chunk_index < self._chunks.size()) && "Location chunk index exceeds the chunks vector size");
        return self._chunks[location.chunk_index];
    }
 
    auto get_chunk(entity_location location) noexcept -> chunk& {
        return get_chunk_impl(*this, location);
    }
 
    auto get_chunk(entity_location location) const noexcept -> const chunk& {
        return get_chunk_impl(*this, location);
    }
 
    auto ensure_free_chunk() -> chunk& {
        auto& chunk = _chunks.back();
        if (!chunk.full()) {
            return chunk;
        }
        _chunks.emplace_back(_blocks, _max_size);
        return _chunks.back();
    }
 
private:
    std::size_t _max_size{};
    blocks_type _blocks{};
    component_meta_set _components{};
    chunks_storage_t _chunks{};
};
 
class archetypes {
public:
    using storage_type = detail::hash_map<component_set, std::unique_ptr<archetype>, component_set_hasher>;
    using iterator = storage_type::iterator;
    using const_iterator = storage_type::const_iterator;
    using value_type = storage_type::value_type;
    using key_type = storage_type::key_type;
    using mapped_type = storage_type::mapped_type;
 
public:
    auto ensure_archetype(const component_meta_set& components) -> archetype* {
        auto& archetype = _archetypes[components.ids()];
        if (!archetype) {
            archetype = create_archetype(components);
        }
        assert((archetype->components().ids() == components.ids())
               && "Archetype components do not match the search request");
        return archetype.get();
    }
 
    template<component... Components>
    auto ensure_archetype() -> archetype* {
        _search_component_set.clear();
        (..., _search_component_set.insert<Components>());
 
        auto& archetype = _archetypes[_search_component_set];
        if (!archetype) {
            archetype = create_archetype(component_meta_set::create<Components...>());
        }
        assert((archetype->components().ids() == _search_component_set)
               && "Archetype components do not match the search request");
        return archetype.get();
    }
 
    template<component... Components>
    auto ensure_archetype_added(const archetype* anchor_archetype) -> archetype* {
        _search_component_set = anchor_archetype->components().ids();
        (..., _search_component_set.insert<Components>());
 
        auto& archetype = _archetypes[_search_component_set];
        if (!archetype) {
            archetype = create_archetype_added<Components...>(anchor_archetype);
        }
        assert((archetype->components().ids() == _search_component_set)
               && "Archetype components do not match the search request");
        return archetype.get();
    }
 
    template<component... Components>
    auto ensure_archetype_removed(const archetype* anchor_archetype) -> archetype* {
        _search_component_set = anchor_archetype->components().ids();
        (..., _search_component_set.erase<Components>());
 
        auto& archetype = _archetypes[_search_component_set];
        if (!archetype) {
            archetype = create_archetype_removed<Components...>(anchor_archetype);
        }
        assert((archetype->components().ids() == _search_component_set)
               && "Archetype components do not match the search request");
        return archetype.get();
    }
 
    auto begin() noexcept -> iterator {
        return _archetypes.begin();
    }
 
    auto end() noexcept -> iterator {
        return _archetypes.end();
    }
 
    [[nodiscard]] auto begin() const noexcept -> const_iterator {
        return _archetypes.begin();
    }
 
    [[nodiscard]] auto end() const noexcept -> const_iterator {
        return _archetypes.end();
    }
 
    [[nodiscard]] auto size() const noexcept -> std::size_t {
        return _archetypes.size();
    }
 
private:
    static auto create_archetype(auto&& components) -> std::unique_ptr<archetype> {
        return std::make_unique<archetype>(std::forward<decltype(components)>(components));
    }
 
    template<component... Components>
    static auto create_archetype_added(const archetype* anchor_archetype) -> std::unique_ptr<archetype> {
        auto components_meta = anchor_archetype->components();
        (..., components_meta.insert<Components>());
        return std::make_unique<archetype>(std::move(components_meta));
    }
 
    template<component... Components>
    static auto create_archetype_removed(const archetype* anchor_archetype) -> std::unique_ptr<archetype> {
        auto components_meta = anchor_archetype->components();
        (..., components_meta.erase<Components>());
        return std::make_unique<archetype>(std::move(components_meta));
    }
 
    // Member component set is here to speed up archetype lookup.
    // If we create component_set every time we need to search for an archetype
    // that requires memory allocation for underlying data structure of the component_set.
    // The downside is that we need to NOT FORGET to clean the _search_component_set before use.
    // The other solution may require a custom allocator but create way more problems when I tried it.
    // In-ability to simply find() in the hash map due to a type mismatch is one of them.
    component_set _search_component_set{};
 
    storage_type _archetypes{};
};
 
} // namespace co_ecs