archetype.h

#pragma once
#include "gaia/config/config.h"
 
#include <cinttypes>
#include <cstdint>
 
#include "gaia/cnt/darray.h"
// #include "gaia/cnt/dbitset.h"
#include "gaia/core/hashing_policy.h"
#include "gaia/core/utility.h"
#include "gaia/ecs/api.h"
#include "gaia/ecs/archetype_common.h"
#include "gaia/ecs/archetype_graph.h"
#include "gaia/ecs/chunk.h"
#include "gaia/ecs/chunk_allocator.h"
#include "gaia/ecs/chunk_header.h"
#include "gaia/ecs/component.h"
#include "gaia/ecs/component_cache.h"
#include "gaia/ecs/id.h"
#include "gaia/ecs/query_mask.h"
#include "gaia/mem/mem_alloc.h"
#include "gaia/ser/ser_binary.h"
 
namespace gaia {
  namespace ecs {
    class World;
    class Archetype;
    struct EntityContainer;
 
    namespace detail {
      GAIA_NODISCARD inline bool cmp_comps(EntitySpan comps, EntitySpan compsOther) {
        const auto s0 = comps.size();
        const auto s1 = compsOther.size();
 
        // Size has to match
        if (s0 != s1)
          return false;
 
        // Elements have to match
        GAIA_FOR(s0) {
          if (comps[i] != compsOther[i])
            return false;
        }
 
        return true;
      }
    } // namespace detail
 
    struct ArchetypeChunkPair {
      Archetype* pArchetype;
      Chunk* pChunk;
 
      GAIA_NODISCARD bool operator==(const ArchetypeChunkPair& other) const {
        return pArchetype == other.pArchetype && pChunk == other.pChunk;
      }
    };
 
    class ArchetypeBase {
    protected:
      ArchetypeId m_archetypeId = ArchetypeIdBad;
 
    public:
      GAIA_NODISCARD ArchetypeId id() const {
        return m_archetypeId;
      }
    };
 
    class ArchetypeLookupChecker: public ArchetypeBase {
      friend class Archetype;
 
      EntitySpan m_comps;
 
    public:
      ArchetypeLookupChecker(EntitySpan comps): m_comps(comps) {}
 
      GAIA_NODISCARD bool cmp_comps(const ArchetypeLookupChecker& other) const {
        return detail::cmp_comps(m_comps, other.m_comps);
      }
    };
 
    class GAIA_API Archetype final: public ArchetypeBase {
    public:
      using LookupHash = core::direct_hash_key<uint64_t>;
 
      static constexpr uint16_t ARCHETYPE_LIFESPAN_BITS = 7;
      static_assert(ARCHETYPE_LIFESPAN_BITS >= ChunkHeader::CHUNK_LIFESPAN_BITS);
      static constexpr uint16_t MAX_ARCHETYPE_LIFESPAN = (1 << ARCHETYPE_LIFESPAN_BITS) - 1;
 
      struct Properties {
        uint16_t capacity;
        ChunkDataOffset chunkDataBytes;
        uint8_t genEntities;
        uint8_t cntEntities;
      };
 
    private:
      struct ShapeData {
        ArchetypeIdLookupKey::LookupHash archetypeIdHash;
        LookupHash hashLookup = {0};
        QueryMask queryMask{};
        Properties properties{};
        ChunkDataOffsets dataOffsets{};
        Entity ids[ChunkHeader::MAX_COMPONENTS];
        Component comps[ChunkHeader::MAX_COMPONENTS];
        ChunkDataOffset compOffs[ChunkHeader::MAX_COMPONENTS];
      };
 
      struct StorageData {
        cnt::darray<Chunk*> chunks;
        uint32_t firstFreeChunkIdx = 0;
      };
 
      struct RuntimeData {
        uint32_t listIdx = BadIndex;
        uint8_t observedTermCnt = 0;
 
        uint32_t deleteReq : 1;
        uint32_t dead : 1;
        uint32_t lifespanCountdownMax : ARCHETYPE_LIFESPAN_BITS;
        uint32_t lifespanCountdown : ARCHETYPE_LIFESPAN_BITS;
 
        RuntimeData(): deleteReq(0), dead(0), lifespanCountdownMax(1), lifespanCountdown(0) {}
      };
 
      struct EdgeData {
        ArchetypeGraph graph;
      };
 
      struct PairIndexData {
        struct PairCountBucket {
          EntityId id = IdentifierIdBad;
          uint8_t start = 0;
          uint8_t count = 0;
        };
 
        uint8_t pairIndexBuffer[ChunkHeader::MAX_COMPONENTS];
        uint8_t pairsAsIndexBuffer[ChunkHeader::MAX_COMPONENTS];
        uint8_t pairRelIndexBuffer[ChunkHeader::MAX_COMPONENTS];
        uint8_t pairTgtIndexBuffer[ChunkHeader::MAX_COMPONENTS];
        PairCountBucket pairRelCountBuffer[ChunkHeader::MAX_COMPONENTS];
        PairCountBucket pairTgtCountBuffer[ChunkHeader::MAX_COMPONENTS];
        uint8_t pairCnt = 0;
        uint8_t pairCntIs = 0;
        uint8_t pairRelCountCnt = 0;
        uint8_t pairTgtCountCnt = 0;
 
        static PairIndexData* create(EntitySpan ids) {
          auto* pPairIndex = mem::AllocHelper::alloc<PairIndexData>("ArchetypePairIndex");
          (void)new (pPairIndex) PairIndexData();
 
          uint8_t pairRelIndexCnt = 0;
          uint8_t pairTgtIndexCnt = 0;
 
          GAIA_FOR(ids.size()) {
            if (!ids[i].pair())
              continue;
 
            pPairIndex->pairIndexBuffer[pPairIndex->pairCnt] = (uint8_t)i;
            ++pPairIndex->pairCnt;
            append_pair_index_bucket(
                pPairIndex->pairRelCountBuffer, pPairIndex->pairRelCountCnt, pPairIndex->pairRelIndexBuffer,
                pairRelIndexCnt, (EntityId)ids[i].id(), (uint8_t)i);
            append_pair_index_bucket(
                pPairIndex->pairTgtCountBuffer, pPairIndex->pairTgtCountCnt, pPairIndex->pairTgtIndexBuffer,
                pairTgtIndexCnt, (EntityId)ids[i].gen(), (uint8_t)i);
 
            if (ids[i].id() == Is.id())
              pPairIndex->pairsAsIndexBuffer[pPairIndex->pairCntIs++] = (uint8_t)i;
          }
 
          if (pPairIndex->pairCnt == 0) {
            destroy(pPairIndex);
            return nullptr;
          }
 
          return pPairIndex;
        }
 
        static void destroy(PairIndexData* pPairIndex) {
          if (pPairIndex == nullptr)
            return;
 
          pPairIndex->~PairIndexData();
          mem::AllocHelper::free("ArchetypePairIndex", pPairIndex);
        }
 
        static PairCountBucket&
        ensure_pair_index_bucket(PairCountBucket* pBuckets, uint8_t& bucketCnt, EntityId id, uint8_t start) {
          GAIA_FOR(bucketCnt) {
            if (pBuckets[i].id == id)
              return pBuckets[i];
          }
 
          GAIA_ASSERT(bucketCnt < ChunkHeader::MAX_COMPONENTS);
          auto& bucket = pBuckets[bucketCnt++];
          bucket.id = id;
          bucket.start = start;
          bucket.count = 0;
          return bucket;
        }
 
        static void append_pair_index_bucket(
            PairCountBucket* pBuckets, uint8_t& bucketCnt, uint8_t* pIndexBuffer, uint8_t& indexCnt, EntityId id,
            uint8_t idsIdx) {
          auto& bucket = ensure_pair_index_bucket(pBuckets, bucketCnt, id, indexCnt);
          GAIA_ASSERT(indexCnt < ChunkHeader::MAX_COMPONENTS);
          pIndexBuffer[indexCnt++] = idsIdx;
          ++bucket.count;
        }
 
        static uint32_t pair_count_from_buckets(const PairCountBucket* pBuckets, uint8_t bucketCnt, EntityId id) {
          GAIA_FOR(bucketCnt) {
            if (pBuckets[i].id == id)
              return pBuckets[i].count;
          }
 
          return 0;
        }
 
        GAIA_NODISCARD static std::span<const uint8_t> pair_indices_from_buckets(
            const PairCountBucket* pBuckets, uint8_t bucketCnt, const uint8_t* pIndexBuffer, EntityId id) {
          GAIA_FOR(bucketCnt) {
            if (pBuckets[i].id != id)
              continue;
 
            return {pIndexBuffer + pBuckets[i].start, pBuckets[i].count};
          }
 
          return {};
        }
 
        GAIA_NODISCARD uint32_t pair_matches(EntitySpan ids, Entity pair) const {
          GAIA_ASSERT(pair.pair());
 
          if (pair == Pair(All, All))
            return pairCnt;
 
          if (pair.id() == All.id())
            return pair_count_from_buckets(pairTgtCountBuffer, pairTgtCountCnt, (EntityId)pair.gen());
 
          if (pair.gen() == All.id())
            return pair_count_from_buckets(pairRelCountBuffer, pairRelCountCnt, (EntityId)pair.id());
 
          return core::has_if(
                     ids,
                     [pair](Entity entity) {
                       return entity == pair;
                     })
                     ? 1u
                     : 0u;
        }
 
        GAIA_NODISCARD Entity entity_from_pairs_as_idx(EntitySpan ids, uint32_t idx) const {
          const auto idsIdx = pairsAsIndexBuffer[idx];
          return ids[idsIdx];
        }
 
        GAIA_NODISCARD std::span<const uint8_t> pair_indices() const {
          return {&pairIndexBuffer[0], pairCnt};
        }
 
        GAIA_NODISCARD std::span<const uint8_t> pair_rel_indices(Entity relation) const {
          return pair_indices_from_buckets(
              pairRelCountBuffer, pairRelCountCnt, pairRelIndexBuffer, (EntityId)relation.id());
        }
 
        GAIA_NODISCARD std::span<const uint8_t> pair_tgt_indices(Entity target) const {
          return pair_indices_from_buckets(
              pairTgtCountBuffer, pairTgtCountCnt, pairTgtIndexBuffer, (EntityId)target.id());
        }
      };
 
      const World& m_world;
      const ComponentCache& m_cc;
      uint32_t& m_worldVersion;
 
      ShapeData m_shape{};
      StorageData m_storage{};
      // cnt::dbitset m_disabledMask;
      EdgeData m_edges{};
      RuntimeData m_runtime{};
      PairIndexData* m_pPairIndex = nullptr;
 
      Archetype(const World& world, const ComponentCache& cc, uint32_t& worldVersion):
          m_world(world), m_cc(cc), m_worldVersion(worldVersion) //
      {}
 
      ~Archetype() {
        // Delete all archetype chunks
        for (auto* pChunk: m_storage.chunks)
          Chunk::free(pChunk);
        PairIndexData::destroy(m_pPairIndex);
      }
 
      void update_data_offsets(uintptr_t memoryAddress) {
        uintptr_t offset = 0;
 
        // Versions
        // We expect versions to fit in the first 256 bytes.
        // With 32 components per archetype this gives us some headroom.
        {
          offset += mem::padding<alignof(ComponentVersion)>(memoryAddress);
 
          const auto cnt = comps_view().size() + 1; // + 1 for entities
          GAIA_ASSERT(offset < 256);
          m_shape.dataOffsets.firstByte_Versions = (ChunkDataVersionOffset)offset;
          offset += sizeof(ComponentVersion) * cnt;
        }
 
        // Entity ids
        {
          offset += mem::padding<alignof(Entity)>(offset);
 
          const auto cnt = comps_view().size();
          if (cnt != 0) {
            m_shape.dataOffsets.firstByte_CompEntities = (ChunkDataOffset)offset;
 
            // Storage-wise, treat the component array as it it were MAX_COMPONENTS long.
            offset += sizeof(Entity) * ChunkHeader::MAX_COMPONENTS;
          }
        }
 
        // Component records
        {
          offset += mem::padding<alignof(ComponentRecord)>(offset);
 
          const auto cnt = comps_view().size();
          if (cnt != 0) {
 
            m_shape.dataOffsets.firstByte_Records = (ChunkDataOffset)offset;
 
            // Storage-wise, treat the component array as it it were MAX_COMPONENTS long.
            offset += sizeof(ComponentRecord) * cnt;
          }
        }
 
        // First entity offset
        {
          offset += mem::padding<alignof(Entity)>(offset);
          m_shape.dataOffsets.firstByte_EntityData = (ChunkDataOffset)offset;
        }
      }
 
      static bool est_max_entities_per_chunk(
          const ComponentCache& cc, uint32_t offs, ComponentSpan comps, uint32_t cap, uint32_t maxDataOffset) {
        for (const auto comp: comps) {
          if (!component_has_inline_data(comp))
            continue;
 
          const auto& desc = cc.get(comp.id());
 
          // If we're beyond what the chunk could take, subtract one entity
          offs = desc.calc_new_mem_offset(offs, cap);
          if (offs >= maxDataOffset)
            return false;
        }
 
        return true;
      }
 
      static void reg_components(
          Archetype& arch, EntitySpan ids, ComponentSpan comps, uint8_t from, uint8_t to, uint32_t& currOff,
          uint32_t count) {
        auto& ofs = arch.m_shape.compOffs;
 
        // Set component ids
        GAIA_FOR2(from, to) arch.m_shape.ids[i] = ids[i];
 
        // Calculate offsets and assign them indices according to our mappings
        GAIA_FOR2(from, to) {
          const auto comp = comps[i];
          const auto compIdx = i;
 
          if (!component_has_inline_data(comp)) {
            ofs[compIdx] = {};
          } else {
            const auto alig = comp.alig();
            currOff = mem::align(currOff, alig);
            ofs[compIdx] = (ChunkDataOffset)currOff;
 
            // Make sure the following component list is properly aligned
            currOff += comp.size() * count;
          }
        }
      }
 
    public:
      Archetype(Archetype&&) = delete;
      Archetype(const Archetype&) = delete;
      Archetype& operator=(Archetype&&) = delete;
      Archetype& operator=(const Archetype&) = delete;
 
      void save(ser::serializer& s) {
        s.save(m_storage.firstFreeChunkIdx);
        s.save(m_runtime.listIdx);
 
        s.save((uint32_t)m_storage.chunks.size());
        for (auto* pChunk: m_storage.chunks) {
          s.save(pChunk->idx());
          pChunk->save(s);
        }
      }
 
      void load(ser::serializer& s) {
        s.load(m_storage.firstFreeChunkIdx);
        s.load(m_runtime.listIdx);
 
        uint32_t chunkCnt = 0;
        s.load(chunkCnt);
        m_storage.chunks.resize(chunkCnt, nullptr);
 
        GAIA_FOR(chunkCnt) {
          uint32_t chunkIdx = 0;
          s.load(chunkIdx);
 
          auto* pChunk = m_storage.chunks[chunkIdx];
          // If the chunk doesn't exist it means it's not a part of the initial setup.
          if (pChunk == nullptr) {
            pChunk = Chunk::create(
                m_world, m_cc, chunkIdx, //
                m_shape.properties.capacity, m_shape.properties.cntEntities, //
                m_shape.properties.genEntities, m_shape.properties.chunkDataBytes, //
                m_worldVersion, m_shape.dataOffsets, m_shape.ids, m_shape.comps, m_shape.compOffs);
            m_storage.chunks[chunkIdx] = pChunk;
          }
 
          pChunk->set_idx(chunkIdx);
          pChunk->load(s);
        }
      }
 
      void list_idx(uint32_t idx) {
        m_runtime.listIdx = idx;
      }
 
      uint32_t list_idx() const {
        return m_runtime.listIdx;
      }
 
      GAIA_NODISCARD bool cmp_comps(const ArchetypeLookupChecker& other) const {
        return detail::cmp_comps(ids_view(), other.m_comps);
      }
 
      GAIA_NODISCARD static Archetype*
      create(const World& world, ArchetypeId archetypeId, uint32_t& worldVersion, EntitySpan ids) {
        const auto& cc = comp_cache(world);
 
        auto* newArch = mem::AllocHelper::alloc<Archetype>("Archetype");
        (void)new (newArch) Archetype(world, cc, worldVersion);
 
        newArch->m_archetypeId = archetypeId;
        newArch->m_shape.archetypeIdHash = ArchetypeIdLookupKey::calc(archetypeId);
 
        // Calculate component mask. This will be used to early exit matching archetypes in simple queries.
        // TODO: Performance could be improved if we're an archetype comming from one already known.
        //       We could simply take the predecessor's mask and update it with the new ids.
        newArch->m_shape.queryMask = build_entity_mask({ids.data(), ids.size()});
 
        const auto cnt = (uint32_t)ids.size();
        newArch->m_shape.properties.cntEntities = (uint8_t)ids.size();
 
        auto as_comp = [&](Entity entity) {
          const auto* pDesc = cc.find(entity);
          return pDesc == nullptr //
                     ? Component(IdentifierIdBad, 0, 0, 0, DataStorageType::Table) //
                     : pDesc->comp;
        };
 
        // Prepare m_comps array
        auto comps = std::span(&newArch->m_shape.comps[0], cnt);
        GAIA_FOR(cnt) {
          if (ids[i].pair()) {
            // When using pairs we need to decode the storage type from them.
            // This is what pair<Rel, Tgt>::type actually does to determine what type to use at compile-time.
            Entity pairEntities[] = {entity_from_id(world, ids[i].id()), entity_from_id(world, ids[i].gen())};
            Component pairComponents[] = {as_comp(pairEntities[0]), as_comp(pairEntities[1])};
            const uint32_t idx = (pairComponents[0].size() != 0U || pairComponents[1].size() == 0U) ? 0 : 1;
            comps[i] = pairComponents[idx];
          } else {
            comps[i] = as_comp(ids[i]);
          }
        }
 
        // Calculate offsets
        static auto ChunkDataAreaOffset = Chunk::chunk_data_area_offset();
        newArch->update_data_offsets(
            // This is not a real memory address.
            // Chunk memory is organized as header+data. The offsets we calculate here belong to
            // the data area.
            // Every allocated chunk is going to have the same relative offset from the header part
            // which is why providing a fictional relative offset is enough.
            ChunkDataAreaOffset);
        const auto& offs = newArch->m_shape.dataOffsets;
        newArch->m_pPairIndex = PairIndexData::create(ids);
 
        // Find the index of the last generic component in both arrays
        const auto entsCnt = (uint32_t)ids.size();
        uint32_t entsGeneric = entsCnt;
        if (entsCnt > 0) {
          for (auto i = entsCnt - 1; i != (uint32_t)-1; --i) {
            if (ids[i].kind() != EntityKind::EK_Uni)
              break;
            --entsGeneric;
          }
        }
 
        uint32_t genCompsSize = 0;
        uint32_t uniCompsSize = 0;
        GAIA_FOR(entsGeneric) genCompsSize += newArch->m_shape.comps[i].size();
        GAIA_FOR2(entsGeneric, cnt) uniCompsSize += newArch->m_shape.comps[i].size();
 
        auto compute_max_entities_for_chunk = [&](uint32_t maxEntities, uint32_t dataLimit) -> uint32_t {
          uint32_t low = 1;
          uint32_t high = maxEntities;
          uint32_t best = 1;
 
          // Helper to test if a given entity count fits in the chunk
          auto try_fit = [&](uint32_t count) -> bool {
            const uint32_t currOff = offs.firstByte_EntityData + (count * sizeof(Entity));
 
            if (!est_max_entities_per_chunk(cc, currOff, comps.subspan(0, entsGeneric), count, dataLimit))
              return false;
            if (!est_max_entities_per_chunk(cc, currOff, comps.subspan(entsGeneric), 1, dataLimit))
              return false;
 
            return true;
          };
 
          // Binary search for the lookup
          while (low <= high) {
            uint32_t mid = (low + high) / 2;
            if (try_fit(mid)) {
              best = mid;
              low = mid + 1;
            } else {
              high = mid - 1;
            }
          }
 
          return best;
        };
 
        // Calculate the number of entities per chunks precisely so we can fit as many of them into chunk as possible.
        // There are multiple chunk size we can pick from. We start at the smallest one, and try do upsize if we can't
        // fit at least MinEntitiesPerChunk.
        constexpr uint32_t MinEntitiesPerChunk = 384;
        uint32_t maxGenItemsInArchetype = 0;
 
        // Always go big for the root archetype so we can fit as many entities as possible into it
        if (archetypeId == 0) {
          const uint32_t size2 = Chunk::chunk_data_bytes(mem_block_size(2));
          maxGenItemsInArchetype =
              (size2 - offs.firstByte_EntityData - uniCompsSize - 1) / (genCompsSize + (uint32_t)sizeof(Entity));
          maxGenItemsInArchetype = compute_max_entities_for_chunk(maxGenItemsInArchetype, size2);
          if (maxGenItemsInArchetype > ChunkHeader::MAX_CHUNK_ENTITIES)
            maxGenItemsInArchetype = ChunkHeader::MAX_CHUNK_ENTITIES;
        } else {
          // Theoretical maximum number of components we can fit into one chunk.
          // This can be further reduced due to alignment and padding.
          const uint32_t size0 = Chunk::chunk_data_bytes(mem_block_size(0));
          maxGenItemsInArchetype =
              (size0 - offs.firstByte_EntityData - uniCompsSize - 1) / (genCompsSize + (uint32_t)sizeof(Entity));
          maxGenItemsInArchetype = compute_max_entities_for_chunk(maxGenItemsInArchetype, size0);
 
          // If we can't fit MinEntitiesPerChunk, go with a larger one
          if (maxGenItemsInArchetype < MinEntitiesPerChunk) {
            const uint32_t size1 = Chunk::chunk_data_bytes(mem_block_size(1));
            maxGenItemsInArchetype =
                (size1 - offs.firstByte_EntityData - uniCompsSize - 1) / (genCompsSize + (uint32_t)sizeof(Entity));
            maxGenItemsInArchetype = compute_max_entities_for_chunk(maxGenItemsInArchetype, size1);
          }
 
          // If we still can't fit MinEntitiesPerChunk, go with the largest one
          if (maxGenItemsInArchetype < MinEntitiesPerChunk) {
            const uint32_t size2 = Chunk::chunk_data_bytes(mem_block_size(2));
            maxGenItemsInArchetype =
                (size2 - offs.firstByte_EntityData - uniCompsSize - 1) / (genCompsSize + (uint32_t)sizeof(Entity));
            maxGenItemsInArchetype = compute_max_entities_for_chunk(maxGenItemsInArchetype, size2);
 
            // NOTE: No we only check against MAX_CHUNK_ENTITIES for the largest size chunk because
            //       MAX_CHUNK_ENTITIES is calculated relative to its size. Therefore, smaller chunks
            //       can't possibly fit more.
            if (maxGenItemsInArchetype > ChunkHeader::MAX_CHUNK_ENTITIES)
              maxGenItemsInArchetype = ChunkHeader::MAX_CHUNK_ENTITIES;
          }
        }
 
        // Update the offsets according to the recalculated maxGenItemsInArchetype
        auto currOff = offs.firstByte_EntityData + ((uint32_t)sizeof(Entity) * maxGenItemsInArchetype);
        reg_components(*newArch, ids, comps, (uint8_t)0, (uint8_t)entsGeneric, currOff, maxGenItemsInArchetype);
        reg_components(*newArch, ids, comps, (uint8_t)entsGeneric, (uint8_t)ids.size(), currOff, 1);
 
        newArch->m_shape.properties.capacity = (uint16_t)maxGenItemsInArchetype;
        newArch->m_shape.properties.chunkDataBytes = (ChunkDataOffset)currOff;
        newArch->m_shape.properties.genEntities = (uint8_t)entsGeneric;
 
        return newArch;
      }
 
      void static destroy(Archetype* pArchetype) {
        GAIA_ASSERT(pArchetype != nullptr);
        pArchetype->~Archetype();
        mem::AllocHelper::free("Archetype", pArchetype);
      }
 
      QueryMask queryMask() const {
        return m_shape.queryMask;
      }
 
      ArchetypeIdLookupKey::LookupHash id_hash() const {
        return m_shape.archetypeIdHash;
      }
 
      void set_hashes(LookupHash hashLookup) {
        m_shape.hashLookup = hashLookup;
      }
 
      void enable_entity(Chunk* pChunk, uint16_t row, bool enableEntity, EntityContainers& recs) {
        pChunk->enable_entity(row, enableEntity, recs);
        // m_disabledMask.set(pChunk->idx(), enableEntity ? true : pChunk->has_disabled_entities());
      }
 
      void del(Chunk* pChunk) {
        // Make sure there are any chunks to delete
        GAIA_ASSERT(!m_storage.chunks.empty());
 
        const auto chunkIndex = pChunk->idx();
 
        // Make sure the chunk is a part of the chunk array
        GAIA_ASSERT(chunkIndex == core::get_index(m_storage.chunks, pChunk));
 
        // Remove the chunk from the chunk array. We are swapping this chunk's entry
        // with the last one in the array. Therefore, we first update the last item's
        // index with the current chunk's index and then do the swapping.
        m_storage.chunks.back()->set_idx(chunkIndex);
        core::swap_erase(m_storage.chunks, chunkIndex);
 
        // Delete the chunk now. Otherwise, if the chunk happened to be the last
        // one we would end up overriding released memory.
        Chunk::free(pChunk);
      }
 
      GAIA_NODISCARD Chunk* foc_free_chunk() {
        const auto chunkCnt = m_storage.chunks.size();
 
        if (chunkCnt > 0) {
          for (uint32_t i = m_storage.firstFreeChunkIdx; i < m_storage.chunks.size(); ++i) {
            auto* pChunk = m_storage.chunks[i];
            GAIA_ASSERT(pChunk != nullptr);
            const auto entityCnt = pChunk->size();
            if (entityCnt < pChunk->capacity()) {
              m_storage.firstFreeChunkIdx = i;
              return pChunk;
            }
          }
        }
 
        // Make sure not too many chunks are allocated
        GAIA_ASSERT(chunkCnt < UINT32_MAX);
 
        // No free space found anywhere. Let's create a new chunk.
        auto* pChunk = Chunk::create(
            m_world, m_cc, chunkCnt, //
            m_shape.properties.capacity, m_shape.properties.cntEntities, //
            m_shape.properties.genEntities, m_shape.properties.chunkDataBytes, //
            m_worldVersion, m_shape.dataOffsets, m_shape.ids, m_shape.comps, m_shape.compOffs);
 
        m_storage.firstFreeChunkIdx = m_storage.chunks.size();
        m_storage.chunks.push_back(pChunk);
        return pChunk;
      }
 
      void try_update_free_chunk_idx() {
        // This is expected to be called only if there are any chunks
        GAIA_ASSERT(!m_storage.chunks.empty());
 
        auto* pChunk = m_storage.chunks[m_storage.firstFreeChunkIdx];
        if (pChunk->size() >= pChunk->capacity())
          ++m_storage.firstFreeChunkIdx;
      }
 
      void try_update_free_chunk_idx(Chunk& chunkThatRemovedEntity) {
        // This is expected to be called only if there are any chunks
        GAIA_ASSERT(!m_storage.chunks.empty());
 
        if (chunkThatRemovedEntity.idx() == m_storage.firstFreeChunkIdx)
          return;
 
        if (chunkThatRemovedEntity.idx() < m_storage.firstFreeChunkIdx) {
          m_storage.firstFreeChunkIdx = chunkThatRemovedEntity.idx();
          return;
        }
 
        auto* pChunk = m_storage.chunks[m_storage.firstFreeChunkIdx];
        if (pChunk->size() >= pChunk->capacity())
          ++m_storage.firstFreeChunkIdx;
      }
 
      void remove_entity_raw(Chunk& chunk, uint16_t row, EntityContainers& recs) {
        chunk.remove_entity(row, recs);
        try_update_free_chunk_idx(chunk);
      }
 
      void remove_entity(Chunk& chunk, uint16_t row, EntityContainers& recs) {
        remove_entity_raw(chunk, row, recs);
        chunk.update_versions();
      }
 
      GAIA_NODISCARD const Properties& props() const {
        return m_shape.properties;
      }
 
      GAIA_NODISCARD const cnt::darray<Chunk*>& chunks() const {
        return m_storage.chunks;
      }
 
      GAIA_NODISCARD LookupHash lookup_hash() const {
        return m_shape.hashLookup;
      }
 
      GAIA_NODISCARD EntitySpan ids_view() const {
        return {&m_shape.ids[0], m_shape.properties.cntEntities};
      }
 
      GAIA_NODISCARD ComponentSpan comps_view() const {
        return {&m_shape.comps[0], m_shape.properties.cntEntities};
      }
 
      GAIA_NODISCARD ChunkDataOffsetSpan comp_offs_view() const {
        return {&m_shape.compOffs[0], m_shape.properties.cntEntities};
      }
 
      GAIA_NODISCARD uint32_t pairs() const {
        return m_pPairIndex != nullptr ? m_pPairIndex->pairCnt : 0;
      }
 
      GAIA_NODISCARD uint32_t pairs_is() const {
        return m_pPairIndex != nullptr ? m_pPairIndex->pairCntIs : 0;
      }
 
      GAIA_NODISCARD uint32_t pair_matches(Entity pair) const {
        return m_pPairIndex != nullptr ? m_pPairIndex->pair_matches(ids_view(), pair) : 0;
      }
 
      GAIA_NODISCARD Entity entity_from_pairs_as_idx(uint32_t idx) const {
        GAIA_ASSERT(m_pPairIndex != nullptr);
        return m_pPairIndex->entity_from_pairs_as_idx(ids_view(), idx);
      }
 
      GAIA_NODISCARD std::span<const uint8_t> pair_indices() const {
        return m_pPairIndex != nullptr ? m_pPairIndex->pair_indices() : std::span<const uint8_t>{};
      }
 
      GAIA_NODISCARD std::span<const uint8_t> pair_rel_indices(Entity relation) const {
        return m_pPairIndex != nullptr ? m_pPairIndex->pair_rel_indices(relation) : std::span<const uint8_t>{};
      }
 
      GAIA_NODISCARD std::span<const uint8_t> pair_tgt_indices(Entity target) const {
        return m_pPairIndex != nullptr ? m_pPairIndex->pair_tgt_indices(target) : std::span<const uint8_t>{};
      }
 
      GAIA_NODISCARD bool has(Entity entity) const {
        return core::has_if(ids_view(), [&](Entity e) {
          return e == entity;
        });
      }
 
      void observed_terms_inc() {
        GAIA_ASSERT(m_runtime.observedTermCnt < m_shape.properties.cntEntities);
        ++m_runtime.observedTermCnt;
      }
 
      void observed_terms_dec() {
        GAIA_ASSERT(m_runtime.observedTermCnt > 0);
        --m_runtime.observedTermCnt;
      }
 
      GAIA_NODISCARD bool has_observed_terms() const {
        return m_runtime.observedTermCnt != 0;
      }
 
      template <typename T>
      GAIA_NODISCARD bool has() const {
        if constexpr (is_pair<T>::value) {
          const auto rel = m_cc.get<typename T::rel>().entity;
          const auto tgt = m_cc.get<typename T::tgt>().entity;
          return has((Entity)Pair(rel, tgt));
        } else {
          const auto* pComp = m_cc.find<T>();
          return pComp != nullptr && has(pComp->entity);
        }
      }
 
      //----------------------------------------------------------------------
 
      template <bool Enabled>
      Entity get_flat_entity(size_t flatIdx) const {
        size_t offset = 0;
        for (const auto* pChunk: chunks()) {
          if (pChunk->empty())
            continue;
 
          uint32_t cnt = 0;
          if constexpr (Enabled) {
            cnt = pChunk->size_enabled();
          } else {
            cnt = pChunk->size_disabled();
          }
 
          if (flatIdx < offset + cnt) {
            if constexpr (Enabled) {
              const auto idx = (uint32_t)(flatIdx - offset) + pChunk->size_disabled();
              return pChunk->entity_view()[idx];
            } else {
              const auto idx = (uint32_t)(flatIdx - offset);
              return pChunk->entity_view()[idx];
            }
          }
 
          offset += cnt;
        }
 
        GAIA_ASSERT(false);
        return EntityBad;
      }
 
      template <bool Enabled>
      const void* get_flat_comp_ptr(uint32_t compIdx, size_t flatIdx, Entity& outEntity) const {
        size_t offset = 0;
        for (const auto* pChunk: chunks()) {
          if (pChunk->empty())
            continue;
 
          uint32_t cnt = 0;
          if constexpr (Enabled) {
            cnt = pChunk->size_enabled();
          } else {
            cnt = pChunk->size_disabled();
          }
 
          if (flatIdx < offset + cnt) {
            if constexpr (Enabled) {
              const auto idx = (uint32_t)(flatIdx - offset) + pChunk->size_disabled();
              const auto* pData = pChunk->comp_ptr(compIdx, idx);
              outEntity = pChunk->entity_view()[idx];
              return pData;
            } else {
              const auto idx = (uint32_t)(flatIdx - offset);
              const auto* pData = pChunk->comp_ptr(compIdx, idx);
              outEntity = pChunk->entity_view()[idx];
              return pData;
            }
          }
 
          offset += cnt;
        }
 
        GAIA_ASSERT(false);
        return nullptr;
      }
 
      template <bool Enabled>
      void sort_entities_inter(size_t low, size_t high, TSortByFunc func) {
        if (low >= high)
          return;
 
        Entity pivotEntity = get_flat_entity<Enabled>(high);
 
        size_t i = low;
        for (size_t j = low; j < high; ++j) {
          Entity jEntity = get_flat_entity<Enabled>(j);
          if (func(m_world, &jEntity, &pivotEntity) < 0) {
            if (i != j) {
              Entity iEntity = get_flat_entity<Enabled>(i);
              Chunk::swap_chunk_entities(const_cast<World&>(m_world), iEntity, jEntity);
            }
            ++i;
          }
        }
 
        {
          Entity iEntity = get_flat_entity<Enabled>(i);
          Chunk::swap_chunk_entities(const_cast<World&>(m_world), iEntity, pivotEntity);
        }
 
        if (i > 0)
          sort_entities_inter<Enabled>(low, i - 1, func);
        sort_entities_inter<Enabled>(i + 1, high, func);
      }
 
      template <bool Enabled>
      void sort_entities_inter(
          const ComponentCacheItem* pItem, uint32_t compIdx, size_t low, size_t high, TSortByFunc func) {
        if (low >= high)
          return;
 
        Entity pivotEntity;
        const void* pPivotData = get_flat_comp_ptr<Enabled>(compIdx, high, pivotEntity);
 
        size_t i = low;
        for (size_t j = low; j < high; ++j) {
          Entity jEntity;
          const void* jData = get_flat_comp_ptr<Enabled>(compIdx, j, jEntity);
          if (func(m_world, jData, pPivotData) < 0) {
            if (i != j) {
              Entity iEntity;
              (void)get_flat_comp_ptr<Enabled>(compIdx, i, iEntity);
              Chunk::swap_chunk_entities(const_cast<World&>(m_world), iEntity, jEntity);
            }
            ++i;
          }
        }
 
        {
          Entity iEntity;
          (void)get_flat_comp_ptr<Enabled>(compIdx, i, iEntity);
          Chunk::swap_chunk_entities(const_cast<World&>(m_world), iEntity, pivotEntity);
        }
 
        if (i > 0)
          sort_entities_inter<Enabled>(pItem, compIdx, low, i - 1, func);
        sort_entities_inter<Enabled>(pItem, compIdx, i + 1, high, func);
      }
 
      void sort_entities(Entity entity, TSortByFunc func) {
        // TODO: We currently have to calculate the number of entities in the archetype from chunks.
        //       Additionally, to get the right index we need to loop through chunks again because
        //       the entities are not spread evenly among chunks (we can't just divide the index by
        //       the number of chunks and module with the same number to get the index inside a chunk).
        //       This is not optimal, and makes sorting more expensive.
 
        if (entity == EntityBad) {
          {
            uint32_t entities = 0;
            for (const auto* pChunk: m_storage.chunks)
              entities += pChunk->size_enabled();
            if (entities != 0)
              sort_entities_inter<true>(0, entities - 1, func);
          }
          {
            uint32_t entities = 0;
            for (const auto* pChunk: m_storage.chunks)
              entities += pChunk->size_disabled();
            if (entities != 0)
              sort_entities_inter<false>(0, entities - 1, func);
          }
        } else {
          const auto* pItem = m_cc.find(entity);
          GAIA_ASSERT(pItem != nullptr && "Trying to sort by a component that has not been registered");
          if (pItem == nullptr)
            return;
 
          const auto compIdx = chunks()[0]->comp_idx(entity);
          {
            uint32_t entities = 0;
            for (const auto* pChunk: m_storage.chunks)
              entities += pChunk->size_enabled();
            if (entities != 0)
              sort_entities_inter<true>(pItem, compIdx, 0, entities - 1, func);
          }
          {
            uint32_t entities = 0;
            for (const auto* pChunk: m_storage.chunks)
              entities += pChunk->size_disabled();
            if (entities != 0)
              sort_entities_inter<false>(pItem, compIdx, 0, entities - 1, func);
          }
        }
      }
 
      //----------------------------------------------------------------------
 
      void build_graph_edges(Archetype* pArchetypeRight, Entity entity) {
        // Loops can't happen
        GAIA_ASSERT(pArchetypeRight != this);
 
        m_edges.graph.add_edge_right(entity, pArchetypeRight->id(), pArchetypeRight->id_hash());
        pArchetypeRight->build_graph_edges_left(this, entity);
      }
 
      void build_graph_edges_left(Archetype* pArchetypeLeft, Entity entity) {
        // Loops can't happen
        GAIA_ASSERT(pArchetypeLeft != this);
 
        m_edges.graph.add_edge_left(entity, pArchetypeLeft->id(), pArchetypeLeft->id_hash());
      }
 
      void del_graph_edges(Archetype* pArchetypeRight, Entity entity) {
        // Loops can't happen
        GAIA_ASSERT(pArchetypeRight != this);
 
        m_edges.graph.del_edge_right(entity);
        pArchetypeRight->del_graph_edges_left(this, entity);
      }
 
      void del_graph_edges_left([[maybe_unused]] Archetype* pArchetypeLeft, Entity entity) {
        // Loops can't happen
        GAIA_ASSERT(pArchetypeLeft != this);
 
        m_edges.graph.del_edge_left(entity);
      }
 
      void del_graph_edge_right_local(Entity entity) {
        m_edges.graph.del_edge_right(entity);
      }
 
      void del_graph_edge_left_local(Entity entity) {
        m_edges.graph.del_edge_left(entity);
      }
 
      GAIA_NODISCARD ArchetypeGraphEdge find_edge_right(Entity entity) const {
        return m_edges.graph.find_edge_right(entity);
      }
 
      GAIA_NODISCARD ArchetypeGraphEdge find_edge_left(Entity entity) const {
        return m_edges.graph.find_edge_left(entity);
      }
 
      GAIA_NODISCARD auto& right_edges() {
        return m_edges.graph.right_edges();
      }
 
      GAIA_NODISCARD const auto& right_edges() const {
        return m_edges.graph.right_edges();
      }
 
      GAIA_NODISCARD auto& left_edges() {
        return m_edges.graph.left_edges();
      }
 
      GAIA_NODISCARD const auto& left_edges() const {
        return m_edges.graph.left_edges();
      }
 
      GAIA_NODISCARD bool empty() const {
        return m_storage.chunks.empty();
      }
 
      void req_del() {
        m_runtime.deleteReq = 1;
      }
 
      GAIA_NODISCARD bool is_req_del() const {
        return m_runtime.deleteReq;
      }
 
      void set_max_lifespan(uint32_t lifespan) {
        GAIA_ASSERT(lifespan <= MAX_ARCHETYPE_LIFESPAN);
 
        m_runtime.lifespanCountdownMax = lifespan;
      }
 
      GAIA_NODISCARD uint32_t max_lifespan() const {
        return m_runtime.lifespanCountdownMax;
      }
 
      GAIA_NODISCARD bool dying() const {
        return m_runtime.lifespanCountdown > 0;
      }
 
      void die() {
        m_runtime.dead = 1;
      }
 
      GAIA_NODISCARD bool dead() const {
        return m_runtime.dead == 1;
      }
 
      void start_dying() {
        GAIA_ASSERT(!dead());
        m_runtime.lifespanCountdown = m_runtime.lifespanCountdownMax;
      }
 
      void revive() {
        GAIA_ASSERT(!dead());
        m_runtime.lifespanCountdown = 0;
        m_runtime.deleteReq = 0;
      }
 
      GAIA_NODISCARD bool progress_death() {
        GAIA_ASSERT(dying());
        GAIA_ASSERT(m_runtime.lifespanCountdownMax > 0);
        --m_runtime.lifespanCountdown;
        return dying();
      }
 
      GAIA_NODISCARD bool ready_to_die() const {
        return m_runtime.lifespanCountdownMax > 0 && !dying() && empty();
      }
 
      static void diag_entity(const World& world, Entity entity) {
        if (entity.entity()) {
          const auto name = entity_name(world, entity);
          GAIA_LOG_N(
              "    ent [%u:%u] %.*s [%s]", entity.id(), entity.gen(), (int)name.size(), name.empty() ? "" : name.data(),
              EntityKindString[entity.kind()]);
        } else if (entity.pair()) {
          const auto rel = entity_name(world, entity.id());
          const auto tgt = entity_name(world, entity.gen());
          GAIA_LOG_N(
              "    pair [%u:%u] %.*s -> %.*s", entity.id(), entity.gen(), (int)rel.size(),
              rel.empty() ? "" : rel.data(), (int)tgt.size(), tgt.empty() ? "" : tgt.data());
        } else {
          const auto& cc = comp_cache(world);
          const auto& desc = cc.get(entity);
          GAIA_LOG_N(
              "    hash:%016" PRIx64 ", size:%3u B, align:%3u B, [%u:%u] %s [%s]", desc.hashLookup.hash,
              desc.comp.size(), desc.comp.alig(), desc.entity.id(), desc.entity.gen(), desc.name.str(),
              EntityKindString[entity.kind()]);
        }
      }
 
      static void diag_basic_info(const World& world, const Archetype& archetype) {
        auto ids = archetype.ids_view();
        auto comps = archetype.comps_view();
 
        // Calculate the number of entities in archetype
        uint32_t entCnt = 0;
        uint32_t entCntDisabled = 0;
        for (const auto* chunk: archetype.m_storage.chunks) {
          entCnt += chunk->size();
          entCntDisabled += chunk->size_disabled();
        }
 
        // Calculate the number of components
        uint32_t genCompsSize = 0;
        uint32_t uniCompsSize = 0;
        {
          const auto& p = archetype.props();
          GAIA_FOR(p.genEntities) genCompsSize += comps[i].size();
          GAIA_FOR2(p.genEntities, comps.size()) uniCompsSize += comps[i].size();
        }
 
        const auto chunkBytes = Chunk::chunk_total_bytes(archetype.props().chunkDataBytes);
        const auto sizeType = mem_block_size_type(chunkBytes);
        const auto allocSize = mem_block_size(sizeType) / 1024;
 
        GAIA_LOG_N(
            "aid:%u, "
            "hash:%016" PRIx64 ", "
            "chunks:%u (%uK), data:%u/%u/%u B, "
            "entities:%u/%u/%u",
            archetype.id(), archetype.lookup_hash().hash, (uint32_t)archetype.chunks().size(), allocSize, genCompsSize,
            uniCompsSize, archetype.props().chunkDataBytes, entCnt, entCntDisabled, archetype.props().capacity);
 
        if (!ids.empty()) {
          GAIA_LOG_N("  Components - count:%u", (uint32_t)ids.size());
          for (const auto ent: ids)
            diag_entity(world, ent);
        }
      }
 
      static void diag_graph_info(const World& world, const Archetype& archetype) {
        archetype.m_edges.graph.diag(world);
      }
 
      static void diag_chunk_info(const Archetype& archetype) {
        const auto& chunks = archetype.m_storage.chunks;
        if (chunks.empty())
          return;
 
        GAIA_LOG_N("  Chunks");
        for (const auto* pChunk: chunks)
          pChunk->diag();
      }
 
      static void diag_entity_info(const World& world, const Archetype& archetype) {
        const auto& chunks = archetype.m_storage.chunks;
        if (chunks.empty())
          return;
 
        GAIA_LOG_N("  Entities");
        bool noEntities = true;
        for (const auto* pChunk: chunks) {
          if (pChunk->empty())
            continue;
          noEntities = false;
 
          auto ev = pChunk->entity_view();
          for (auto entity: ev)
            diag_entity(world, entity);
        }
        if (noEntities)
          GAIA_LOG_N("    N/A");
      }
 
      static void diag(const World& world, const Archetype& archetype) {
        diag_basic_info(world, archetype);
        diag_graph_info(world, archetype);
        diag_chunk_info(archetype);
        diag_entity_info(world, archetype);
      }
    };
 
    class GAIA_API ArchetypeLookupKey final {
      Archetype::LookupHash m_hash;
      const ArchetypeBase* m_pArchetypeBase;
 
    public:
      static constexpr bool IsDirectHashKey = true;
 
      ArchetypeLookupKey(): m_hash({0}), m_pArchetypeBase(nullptr) {}
      explicit ArchetypeLookupKey(Archetype::LookupHash hash, const ArchetypeBase* pArchetypeBase):
          m_hash(hash), m_pArchetypeBase(pArchetypeBase) {}
 
      GAIA_NODISCARD size_t hash() const {
        return (size_t)m_hash.hash;
      }
 
      GAIA_NODISCARD Archetype* archetype() const {
        return (Archetype*)m_pArchetypeBase;
      }
 
      GAIA_NODISCARD bool operator==(const ArchetypeLookupKey& other) const {
        // Hash doesn't match we don't have a match.
        // Hash collisions are expected to be very unlikely so optimize for this case.
        if GAIA_LIKELY (m_hash != other.m_hash)
          return false;
 
        const auto id = m_pArchetypeBase->id();
        if (id == ArchetypeIdBad) {
          const auto* pArchetype = (const Archetype*)other.m_pArchetypeBase;
          const auto* pArchetypeLookupChecker = (const ArchetypeLookupChecker*)m_pArchetypeBase;
          return pArchetype->cmp_comps(*pArchetypeLookupChecker);
        }
 
        // Real ArchetypeID is given. Compare the pointers.
        // Normally we'd compare archetype IDs but because we do not allow archetype copies and all archetypes are
        // unique it's guaranteed that if pointers are the same we have a match.
        // This also saves a pointer indirection because we do not access the memory the pointer points to.
        return m_pArchetypeBase == other.m_pArchetypeBase;
      }
    };
 
    using ArchetypeMapByHash = cnt::map<ArchetypeLookupKey, Archetype*>;
  } // namespace ecs
} // namespace gaia