1/*
2 * Copyright (c) 2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "entity_manager.h"
17
18#include <algorithm>
19#include <atomic>
20
21#include <base/containers/generic_iterator.h>
22#include <base/containers/iterator.h>
23#include <base/containers/refcnt_ptr.h>
24#include <base/containers/type_traits.h>
25#include <base/containers/unique_ptr.h>
26#include <base/containers/unordered_map.h>
27#include <base/containers/vector.h>
28#include <base/namespace.h>
29#include <core/ecs/entity.h>
30#include <core/ecs/entity_reference.h>
31#include <core/ecs/intf_entity_manager.h>
32#include <core/log.h>
33#include <core/namespace.h>
34
35CORE_BEGIN_NAMESPACE()
36using BASE_NS::pair;
37using BASE_NS::vector;
38
39namespace {
40uint32_t GetId(const Entity& e)
41{
42    return e.id & 0xFFFFFFFF;
43}
44
45uint32_t GetGeneration(const Entity& e)
46{
47    return (e.id >> 32l) & 0xFFFFFFFF;
48}
49
50Entity MakeEntityId(uint32_t g, uint32_t i)
51{
52    return { (static_cast<uint64_t>(g) << 32l) | i };
53}
54
55class EntityReferenceCounter final : public IEntityReferenceCounter {
56public:
57    using Ptr = BASE_NS::refcnt_ptr<EntityReferenceCounter>;
58    EntityReferenceCounter() = default;
59    ~EntityReferenceCounter() override = default;
60    EntityReferenceCounter(const EntityReferenceCounter&) = delete;
61    EntityReferenceCounter& operator=(const EntityReferenceCounter&) = delete;
62    EntityReferenceCounter(EntityReferenceCounter&&) = delete;
63    EntityReferenceCounter& operator=(EntityReferenceCounter&&) = delete;
64
65protected:
66    void Ref() noexcept override
67    {
68        refcnt_.fetch_add(1, std::memory_order_relaxed);
69    }
70
71    void Unref() noexcept override
72    {
73        if (std::atomic_fetch_sub_explicit(&refcnt_, 1, std::memory_order_release) == 0) {
74            std::atomic_thread_fence(std::memory_order_acquire);
75            delete this;
76        }
77    }
78
79    int32_t GetRefCount() const noexcept override
80    {
81        return refcnt_.load();
82    }
83
84private:
85    std::atomic<int32_t> refcnt_ { -1 };
86};
87} // namespace
88
89EntityManager::EntityManager() : EntityManager(64u) {}
90
91EntityManager::EntityManager(const size_t entityCount)
92{
93    entities_.reserve(entityCount);
94}
95
96EntityManager::~EntityManager()
97{
98    // count live entities, should be zero
99    [[maybe_unused]] int32_t liveEntities = 0;
100    [[maybe_unused]] int32_t inactiveEntities = 0;
101    for (const auto& e : entities_) {
102        if (EntityState::State::ALIVE == e.state) {
103            ++liveEntities;
104        }
105        if (EntityState::State::INACTIVE == e.state) {
106            ++inactiveEntities;
107        }
108    }
109    CORE_ASSERT(inactiveEntities == 0);
110    CORE_ASSERT(liveEntities == 0);
111}
112
113Entity EntityManager::Create()
114{
115    Entity result;
116    if (freeList_.empty()) {
117        const auto generation = 1U;
118        const auto id = static_cast<uint32_t>(entities_.size());
119        entities_.push_back({ EntityState::State::ALIVE, generation, nullptr });
120        result = MakeEntityId(generation, id);
121    } else {
122        const auto id = freeList_.back();
123        freeList_.pop_back();
124        auto& slot = entities_[id];
125        // if the slot isn't free report a dead entity
126        if (slot.state != EntityState::State::FREE) {
127            const auto deadEntity = MakeEntityId(slot.generation, id);
128            removedList_.push_back(deadEntity);
129            eventList_.push_back({ deadEntity, EventType::DESTROYED });
130        }
131        slot.counter = nullptr; // NOTE: could push to a pool and recycle used often
132        ++slot.generation;
133
134        slot.state = EntityState::State::ALIVE;
135        result = MakeEntityId(slot.generation, id);
136    }
137    eventList_.push_back({ result, EventType::CREATED });
138    ++generationCounter_;
139    return result;
140}
141
142EntityReference EntityManager::CreateReferenceCounted()
143{
144    Entity result;
145    if (freeList_.empty()) {
146        const auto generation = 1U;
147        const auto id = static_cast<uint32_t>(entities_.size());
148        entities_.push_back(
149            { EntityState::State::ALIVE, generation, IEntityReferenceCounter::Ptr { new EntityReferenceCounter } });
150        result = MakeEntityId(generation, id);
151    } else {
152        const auto id = freeList_.back();
153        freeList_.pop_back();
154        auto& slot = entities_[id];
155
156        // if the slot isn't free report a dead entity
157        if (slot.state != EntityState::State::FREE) {
158            const auto deadEntity = MakeEntityId(slot.generation, id);
159            removedList_.push_back(deadEntity);
160            eventList_.push_back({ deadEntity, EventType::DESTROYED });
161        }
162        if (!slot.counter) {
163            slot.counter.reset(new EntityReferenceCounter);
164        }
165        ++slot.generation;
166        slot.state = EntityState::State::ALIVE;
167        result = MakeEntityId(slot.generation, id);
168    }
169    eventList_.push_back({ result, EventType::CREATED });
170    ++generationCounter_;
171    return EntityReference(result, entities_[GetId(result)].counter);
172}
173
174EntityReference EntityManager::GetReferenceCounted(const Entity entity)
175{
176    if (EntityUtil::IsValid(entity)) {
177        if (const uint32_t id = GetId(entity); id < entities_.size()) {
178            auto& e = entities_[id];
179            // make sure the given entity id has the same generation and that the entity isn't dead or free.
180            if ((e.generation == GetGeneration(entity)) &&
181                ((e.state == EntityState::State::ALIVE) || (e.state == EntityState::State::INACTIVE))) {
182                if (!e.counter) {
183                    // entity wasn't yet reference counted so add a counter
184                    e.counter.reset(new EntityReferenceCounter);
185                    return { entity, e.counter };
186                }
187                if (e.counter->GetRefCount() > 0) {
188                    // reference count is still valid
189                    return { entity, e.counter };
190                }
191                // reference count has expired, but we won't revive the entity.
192            }
193        }
194    }
195    return {};
196}
197
198void EntityManager::Destroy(const Entity entity)
199{
200    if (EntityUtil::IsValid(entity)) {
201        if (const uint32_t id = GetId(entity); id < entities_.size()) {
202            auto& e = entities_[id];
203            if ((e.generation == GetGeneration(entity)) &&
204                ((e.state == EntityState::State::ALIVE) || (e.state == EntityState::State::INACTIVE))) {
205                e.state = EntityState::State::DEAD;
206                e.counter = nullptr;
207                removedList_.push_back(entity);
208                eventList_.push_back({ entity, EventType::DESTROYED });
209                ++generationCounter_;
210            }
211        }
212    }
213}
214
215void EntityManager::DestroyAllEntities()
216{
217    for (uint32_t i = 0, count = static_cast<uint32_t>(entities_.size()); i < count; ++i) {
218        auto& e = entities_[i];
219        if ((EntityState::State::ALIVE == e.state) || (EntityState::State::INACTIVE == e.state)) {
220            auto entity = MakeEntityId(e.generation, i);
221            removedList_.push_back(entity);
222            eventList_.push_back({ entity, EventType::DESTROYED });
223            e.counter = nullptr;
224            e.state = EntityState::State::DEAD;
225        }
226    }
227    ++generationCounter_;
228}
229
230bool EntityManager::IsAlive(const Entity entity) const
231{
232    if (EntityUtil::IsValid(entity)) {
233        const uint32_t id = GetId(entity);
234        if (id < entities_.size()) {
235            const auto& state = entities_[id];
236            if (state.generation == GetGeneration(entity)) {
237                return (state.state == EntityState::State::ALIVE) &&
238                       (!state.counter || (state.counter->GetRefCount() > 0));
239            }
240        }
241    }
242    return false;
243}
244
245vector<Entity> EntityManager::GetRemovedEntities()
246{
247    const auto freeSize = freeList_.size();
248    for (const Entity& e : removedList_) {
249        const uint32_t id = GetId(e);
250        if (id < entities_.size()) {
251            if (entities_[id].generation == GetGeneration(e)) {
252                CORE_ASSERT(entities_[id].state == EntityState::State::DEAD);
253                if (id < entities_.size() - 1) {
254                    entities_[id].state = EntityState::State::FREE;
255                    freeList_.push_back(id);
256                } else {
257                    entities_.resize(entities_.size() - 1);
258                }
259            }
260        }
261    }
262    if (const auto finalFreeSize = freeList_.size()) {
263        // by sorting with greater and using pop_back in creation we keep entities_ filled from the beginning.
264        // could be removed not useful.
265        if (finalFreeSize != freeSize) {
266            std::sort(freeList_.begin(), freeList_.end(), std::greater {});
267        }
268        // check from the beginning that ids don't go out-of-bounds and remove problematic ones.
269        // most likely they never are so linear is better than lower_bounds.
270        auto count = 0U;
271        while ((count < finalFreeSize) && (freeList_[count] >= entities_.size())) {
272            ++count;
273        }
274        if (count) {
275            freeList_.erase(freeList_.cbegin(), freeList_.cbegin() + count);
276        }
277    }
278    return move(removedList_);
279}
280
281uint32_t EntityManager::GetGenerationCounter() const
282{
283    return generationCounter_;
284}
285
286vector<pair<Entity, IEntityManager::EventType>> EntityManager::GetEvents()
287{
288    return move(eventList_);
289}
290
291void EntityManager::SetActive(const Entity entity, bool state)
292{
293    if (EntityUtil::IsValid(entity)) {
294        EntityState::State oldState;
295        EntityState::State newState;
296        EventType event;
297        if (state) {
298            oldState = EntityState::State::INACTIVE;
299            newState = EntityState::State::ALIVE;
300            event = EventType::ACTIVATED;
301        } else {
302            oldState = EntityState::State::ALIVE;
303            newState = EntityState::State::INACTIVE;
304            event = EventType::DEACTIVATED;
305        }
306
307        uint32_t id = GetId(entity);
308        if (id < entities_.size()) {
309            if (entities_[id].generation == GetGeneration(entity)) {
310                if (entities_[id].state == oldState) {
311                    entities_[id].state = newState;
312                    eventList_.push_back({ entity, event });
313                    ++generationCounter_;
314                }
315            }
316        }
317    }
318}
319
320void EntityManager::UpdateDeadEntities()
321{
322    const auto removedCount = removedList_.size();
323    for (uint32_t id = 0, count = static_cast<uint32_t>(entities_.size()); id < count; ++id) {
324        auto& e = entities_[id];
325        if ((e.state != EntityState::State::FREE) && e.counter && (e.counter->GetRefCount() == 0)) {
326            const Entity entity = MakeEntityId(e.generation, id);
327            removedList_.push_back(entity);
328            eventList_.push_back({ entity, EventType::DESTROYED });
329            e.state = EntityState::State::DEAD;
330        }
331    }
332    if (removedCount != removedList_.size()) {
333        ++generationCounter_;
334    }
335}
336
337EntityManager::IteratorImpl::IteratorImpl(const EntityManager& owner, size_t index, IteratorType type)
338    : owner_(&owner), index_(static_cast<uint32_t>(index)), type_(type)
339{
340    const auto valid = (type == IteratorType::DEACTIVATED) ? EntityState::State::INACTIVE : EntityState::State::ALIVE;
341    if (index < owner.entities_.size()) {
342        const auto& e = owner.entities_[index];
343        if ((e.state != valid) || (e.counter && e.counter->GetRefCount() == 0)) {
344            Next();
345        }
346    }
347}
348
349const class IEntityManager* EntityManager::IteratorImpl::GetOwner() const
350{
351    return owner_;
352}
353
354bool EntityManager::IteratorImpl::Compare(const Iterator::Ptr& other) const
355{
356    if ((other == nullptr) || (other->GetOwner() != owner_)) {
357        return false;
358    }
359    auto* otheri = static_cast<const EntityManager::IteratorImpl*>(other.get());
360    return (index_ == otheri->index_) && (type_ == otheri->type_);
361}
362
363bool EntityManager::IteratorImpl::Next()
364{
365    const auto& entities = owner_->entities_;
366    if (index_ < entities.size()) {
367        const auto valid =
368            (type_ == IteratorType::DEACTIVATED) ? EntityState::State::INACTIVE : EntityState::State::ALIVE;
369
370        ++index_;
371        while (index_ < entities.size()) {
372            auto& state = entities[index_];
373            if ((state.state == valid) && ((!state.counter) || (state.counter->GetRefCount() > 0))) {
374                break;
375            }
376            ++index_;
377        }
378    }
379    return (index_ < owner_->entities_.size());
380}
381
382Entity EntityManager::IteratorImpl::Get() const
383{
384    if (index_ >= owner_->entities_.size()) {
385        return {};
386    }
387    return MakeEntityId(owner_->entities_[index_].generation, index_);
388}
389
390IEntityManager::Iterator::Ptr EntityManager::MakeIterator(uint32_t index, IteratorType type) const
391{
392    auto del = [](Iterator* it) { delete static_cast<EntityManager::IteratorImpl*>(it); };
393    auto p = new EntityManager::IteratorImpl(*this, index, type);
394    return { p, del };
395}
396
397IEntityManager::Iterator::Ptr EntityManager::IteratorImpl::Clone() const
398{
399    return owner_->MakeIterator(index_, type_);
400}
401
402IEntityManager::Iterator::Ptr EntityManager::Begin(IteratorType type) const
403{
404    return MakeIterator(0U, type);
405}
406
407IEntityManager::Iterator::Ptr EntityManager::End(IteratorType type) const
408{
409    return MakeIterator(static_cast<uint32_t>(entities_.size()), type);
410}
411
412CORE_END_NAMESPACE()
413