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 
35 CORE_BEGIN_NAMESPACE()
36 using BASE_NS::pair;
37 using BASE_NS::vector;
38 
39 namespace {
GetId(const Entity & e)40 uint32_t GetId(const Entity& e)
41 {
42     return e.id & 0xFFFFFFFF;
43 }
44 
GetGeneration(const Entity & e)45 uint32_t GetGeneration(const Entity& e)
46 {
47     return (e.id >> 32L) & 0xFFFFFFFF;
48 }
49 
MakeEntityId(uint32_t g,uint32_t i)50 Entity MakeEntityId(uint32_t g, uint32_t i)
51 {
52     return { (static_cast<uint64_t>(g) << 32L) | i }; // 32: signed long
53 }
54 
55 class EntityReferenceCounter final : public IEntityReferenceCounter {
56 public:
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 
65 protected:
Ref()66     void Ref() noexcept override
67     {
68         refcnt_.fetch_add(1, std::memory_order_relaxed);
69     }
70 
Unref()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 
GetRefCount() const79     int32_t GetRefCount() const noexcept override
80     {
81         return refcnt_.load();
82     }
83 
84 private:
85     std::atomic<int32_t> refcnt_ { -1 };
86 };
87 } // namespace
88 
EntityManager()89 EntityManager::EntityManager() : EntityManager(64u) {}
90 
EntityManager(const size_t entityCount)91 EntityManager::EntityManager(const size_t entityCount)
92 {
93     entities_.reserve(entityCount);
94 }
95 
~EntityManager()96 EntityManager::~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 
Create()113 Entity 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 
CreateReferenceCounted()142 EntityReference 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 
GetReferenceCounted(const Entity entity)174 EntityReference 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 
Destroy(const Entity entity)198 void 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 
DestroyAllEntities()215 void 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 
IsAlive(const Entity entity) const230 bool 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 
GetRemovedEntities()245 vector<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 
GetGenerationCounter() const281 uint32_t EntityManager::GetGenerationCounter() const
282 {
283     return generationCounter_;
284 }
285 
GetEvents()286 vector<pair<Entity, IEntityManager::EventType>> EntityManager::GetEvents()
287 {
288     return move(eventList_);
289 }
290 
SetActive(const Entity entity,bool state)291 void 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 
UpdateDeadEntities()320 void 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 
IteratorImpl(const EntityManager & owner,size_t index,IteratorType type)337 EntityManager::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 
349 const class IEntityManager* EntityManager::IteratorImpl::GetOwner() const
350 {
351     return owner_;
352 }
353 
Compare(const Iterator::Ptr & other) const354 bool 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 
Next()363 bool 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 
Get() const382 Entity EntityManager::IteratorImpl::Get() const
383 {
384     if (index_ >= owner_->entities_.size()) {
385         return {};
386     }
387     return MakeEntityId(owner_->entities_[index_].generation, index_);
388 }
389 
MakeIterator(uint32_t index,IteratorType type) const390 IEntityManager::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 
Clone() const397 IEntityManager::Iterator::Ptr EntityManager::IteratorImpl::Clone() const
398 {
399     return owner_->MakeIterator(index_, type_);
400 }
401 
Begin(IteratorType type) const402 IEntityManager::Iterator::Ptr EntityManager::Begin(IteratorType type) const
403 {
404     return MakeIterator(0U, type);
405 }
406 
End(IteratorType type) const407 IEntityManager::Iterator::Ptr EntityManager::End(IteratorType type) const
408 {
409     return MakeIterator(static_cast<uint32_t>(entities_.size()), type);
410 }
411 
412 CORE_END_NAMESPACE()
413