EnTT 3.15.0
Loading...
Searching...
No Matches
storage.hpp
1#ifndef ENTT_ENTITY_STORAGE_HPP
2#define ENTT_ENTITY_STORAGE_HPP
3
4#include <cstddef>
5#include <iterator>
6#include <memory>
7#include <tuple>
8#include <type_traits>
9#include <utility>
10#include <vector>
11#include "../config/config.h"
12#include "../core/bit.hpp"
13#include "../core/iterator.hpp"
14#include "../core/memory.hpp"
15#include "../core/type_info.hpp"
16#include "component.hpp"
17#include "entity.hpp"
18#include "fwd.hpp"
19#include "sparse_set.hpp"
20
21namespace entt {
22
24namespace internal {
25
26template<typename Container, auto Page>
27class storage_iterator final {
28 friend storage_iterator<const Container, Page>;
29
30 using container_type = std::remove_const_t<Container>;
31 using alloc_traits = std::allocator_traits<typename container_type::allocator_type>;
32
33 using iterator_traits = std::iterator_traits<std::conditional_t<
34 std::is_const_v<Container>,
35 typename alloc_traits::template rebind_traits<typename std::pointer_traits<typename container_type::value_type>::element_type>::const_pointer,
36 typename alloc_traits::template rebind_traits<typename std::pointer_traits<typename container_type::value_type>::element_type>::pointer>>;
37
38public:
39 using value_type = typename iterator_traits::value_type;
40 using pointer = typename iterator_traits::pointer;
41 using reference = typename iterator_traits::reference;
42 using difference_type = typename iterator_traits::difference_type;
43 using iterator_category = std::random_access_iterator_tag;
44
45 constexpr storage_iterator() noexcept = default;
46
47 constexpr storage_iterator(Container *ref, const difference_type idx) noexcept
48 : payload{ref},
49 offset{idx} {}
50
51 template<bool Const = std::is_const_v<Container>, typename = std::enable_if_t<Const>>
52 constexpr storage_iterator(const storage_iterator<std::remove_const_t<Container>, Page> &other) noexcept
53 : storage_iterator{other.payload, other.offset} {}
54
55 constexpr storage_iterator &operator++() noexcept {
56 return --offset, *this;
57 }
58
59 constexpr storage_iterator operator++(int) noexcept {
60 const storage_iterator orig = *this;
61 return ++(*this), orig;
62 }
63
64 constexpr storage_iterator &operator--() noexcept {
65 return ++offset, *this;
66 }
67
68 constexpr storage_iterator operator--(int) noexcept {
69 const storage_iterator orig = *this;
70 return operator--(), orig;
71 }
72
73 constexpr storage_iterator &operator+=(const difference_type value) noexcept {
74 offset -= value;
75 return *this;
76 }
77
78 constexpr storage_iterator operator+(const difference_type value) const noexcept {
79 storage_iterator copy = *this;
80 return (copy += value);
81 }
82
83 constexpr storage_iterator &operator-=(const difference_type value) noexcept {
84 return (*this += -value);
85 }
86
87 constexpr storage_iterator operator-(const difference_type value) const noexcept {
88 return (*this + -value);
89 }
90
91 [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept {
92 const auto pos = static_cast<typename Container::size_type>(index() - value);
93 return (*payload)[pos / Page][fast_mod(static_cast<std::size_t>(pos), Page)];
94 }
95
96 [[nodiscard]] constexpr pointer operator->() const noexcept {
97 return std::addressof(operator[](0));
98 }
99
100 [[nodiscard]] constexpr reference operator*() const noexcept {
101 return operator[](0);
102 }
103
104 [[nodiscard]] constexpr difference_type index() const noexcept {
105 return offset - 1;
106 }
107
108private:
109 Container *payload;
110 difference_type offset;
111};
112
113template<typename Lhs, typename Rhs, auto Page>
114[[nodiscard]] constexpr std::ptrdiff_t operator-(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
115 return rhs.index() - lhs.index();
116}
117
118template<typename Lhs, typename Rhs, auto Page>
119[[nodiscard]] constexpr bool operator==(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
120 return lhs.index() == rhs.index();
121}
122
123template<typename Lhs, typename Rhs, auto Page>
124[[nodiscard]] constexpr bool operator!=(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
125 return !(lhs == rhs);
126}
127
128template<typename Lhs, typename Rhs, auto Page>
129[[nodiscard]] constexpr bool operator<(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
130 return lhs.index() > rhs.index();
131}
132
133template<typename Lhs, typename Rhs, auto Page>
134[[nodiscard]] constexpr bool operator>(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
135 return rhs < lhs;
136}
137
138template<typename Lhs, typename Rhs, auto Page>
139[[nodiscard]] constexpr bool operator<=(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
140 return !(lhs > rhs);
141}
142
143template<typename Lhs, typename Rhs, auto Page>
144[[nodiscard]] constexpr bool operator>=(const storage_iterator<Lhs, Page> &lhs, const storage_iterator<Rhs, Page> &rhs) noexcept {
145 return !(lhs < rhs);
146}
147
148template<typename It, typename... Other>
149class extended_storage_iterator final {
150 template<typename Iter, typename... Args>
151 friend class extended_storage_iterator;
152
153public:
154 using iterator_type = It;
155 using value_type = decltype(std::tuple_cat(std::make_tuple(*std::declval<It>()), std::forward_as_tuple(*std::declval<Other>()...)));
156 using pointer = input_iterator_pointer<value_type>;
157 using reference = value_type;
158 using difference_type = std::ptrdiff_t;
159 using iterator_category = std::input_iterator_tag;
160 using iterator_concept = std::forward_iterator_tag;
161
162 constexpr extended_storage_iterator()
163 : it{} {}
164
165 constexpr extended_storage_iterator(iterator_type base, Other... other)
166 : it{base, other...} {}
167
168 template<typename... Args, typename = std::enable_if_t<(!std::is_same_v<Other, Args> && ...) && (std::is_constructible_v<Other, Args> && ...)>>
169 constexpr extended_storage_iterator(const extended_storage_iterator<It, Args...> &other)
170 : it{other.it} {}
171
172 constexpr extended_storage_iterator &operator++() noexcept {
173 return ++std::get<It>(it), (++std::get<Other>(it), ...), *this;
174 }
175
176 constexpr extended_storage_iterator operator++(int) noexcept {
177 const extended_storage_iterator orig = *this;
178 return ++(*this), orig;
179 }
180
181 [[nodiscard]] constexpr pointer operator->() const noexcept {
182 return operator*();
183 }
184
185 [[nodiscard]] constexpr reference operator*() const noexcept {
186 return {*std::get<It>(it), *std::get<Other>(it)...};
187 }
188
189 [[nodiscard]] constexpr iterator_type base() const noexcept {
190 return std::get<It>(it);
191 }
192
193 template<typename... Lhs, typename... Rhs>
194 friend constexpr bool operator==(const extended_storage_iterator<Lhs...> &, const extended_storage_iterator<Rhs...> &) noexcept;
195
196private:
197 std::tuple<It, Other...> it;
198};
199
200template<typename... Lhs, typename... Rhs>
201[[nodiscard]] constexpr bool operator==(const extended_storage_iterator<Lhs...> &lhs, const extended_storage_iterator<Rhs...> &rhs) noexcept {
202 return std::get<0>(lhs.it) == std::get<0>(rhs.it);
203}
204
205template<typename... Lhs, typename... Rhs>
206[[nodiscard]] constexpr bool operator!=(const extended_storage_iterator<Lhs...> &lhs, const extended_storage_iterator<Rhs...> &rhs) noexcept {
207 return !(lhs == rhs);
208}
209
210} // namespace internal
212
228template<typename Type, typename Entity, typename Allocator, typename>
229class basic_storage: public basic_sparse_set<Entity, typename std::allocator_traits<Allocator>::template rebind_alloc<Entity>> {
230 using alloc_traits = std::allocator_traits<Allocator>;
231 static_assert(std::is_same_v<typename alloc_traits::value_type, Type>, "Invalid value type");
232 using container_type = std::vector<typename alloc_traits::pointer, typename alloc_traits::template rebind_alloc<typename alloc_traits::pointer>>;
234 using underlying_iterator = typename underlying_type::basic_iterator;
235 using traits_type = component_traits<Type, Entity>;
236
237 [[nodiscard]] auto &element_at(const std::size_t pos) const {
238 return payload[pos / traits_type::page_size][fast_mod(pos, traits_type::page_size)];
239 }
240
241 auto assure_at_least(const std::size_t pos) {
242 const auto idx = pos / traits_type::page_size;
243
244 if(!(idx < payload.size())) {
245 auto curr = payload.size();
246 allocator_type allocator{get_allocator()};
247 payload.resize(idx + 1u, nullptr);
248
249 ENTT_TRY {
250 for(const auto last = payload.size(); curr < last; ++curr) {
251 payload[curr] = alloc_traits::allocate(allocator, traits_type::page_size);
252 }
253 }
254 ENTT_CATCH {
255 payload.resize(curr);
256 ENTT_THROW;
257 }
258 }
259
260 return payload[idx] + fast_mod(pos, traits_type::page_size);
261 }
262
263 template<typename... Args>
264 auto emplace_element(const Entity entt, const bool force_back, Args &&...args) {
265 const auto it = base_type::try_emplace(entt, force_back);
266
267 ENTT_TRY {
268 auto *elem = to_address(assure_at_least(static_cast<size_type>(it.index())));
269 entt::uninitialized_construct_using_allocator(elem, get_allocator(), std::forward<Args>(args)...);
270 }
271 ENTT_CATCH {
272 base_type::pop(it, it + 1u);
273 ENTT_THROW;
274 }
275
276 return it;
277 }
278
279 void shrink_to_size(const std::size_t sz) {
280 const auto from = (sz + traits_type::page_size - 1u) / traits_type::page_size;
281 allocator_type allocator{get_allocator()};
282
283 for(auto pos = sz, length = base_type::size(); pos < length; ++pos) {
284 if constexpr(traits_type::in_place_delete) {
285 if(base_type::data()[pos] != tombstone) {
286 alloc_traits::destroy(allocator, std::addressof(element_at(pos)));
287 }
288 } else {
289 alloc_traits::destroy(allocator, std::addressof(element_at(pos)));
290 }
291 }
292
293 for(auto pos = from, last = payload.size(); pos < last; ++pos) {
294 alloc_traits::deallocate(allocator, payload[pos], traits_type::page_size);
295 }
296
297 payload.resize(from);
298 payload.shrink_to_fit();
299 }
300
301 void swap_at(const std::size_t lhs, const std::size_t rhs) {
302 using std::swap;
303 swap(element_at(lhs), element_at(rhs));
304 }
305
306 void move_to(const std::size_t lhs, const std::size_t rhs) {
307 auto &elem = element_at(lhs);
308 allocator_type allocator{get_allocator()};
309 entt::uninitialized_construct_using_allocator(to_address(assure_at_least(rhs)), allocator, std::move(elem));
310 alloc_traits::destroy(allocator, std::addressof(elem));
311 }
312
313private:
314 [[nodiscard]] const void *get_at(const std::size_t pos) const final {
315 return std::addressof(element_at(pos));
316 }
317
318 void swap_or_move([[maybe_unused]] const std::size_t from, [[maybe_unused]] const std::size_t to) override {
319 static constexpr bool is_pinned_type = !(std::is_move_constructible_v<Type> && std::is_move_assignable_v<Type>);
320 // use a runtime value to avoid compile-time suppression that drives the code coverage tool crazy
321 ENTT_ASSERT((from + 1u) && !is_pinned_type, "Pinned type");
322
323 if constexpr(!is_pinned_type) {
324 if constexpr(traits_type::in_place_delete) {
325 (base_type::operator[](to) == tombstone) ? move_to(from, to) : swap_at(from, to);
326 } else {
327 swap_at(from, to);
328 }
329 }
330 }
331
332protected:
338 void pop(underlying_iterator first, underlying_iterator last) override {
339 for(allocator_type allocator{get_allocator()}; first != last; ++first) {
340 // cannot use first.index() because it would break with cross iterators
341 auto &elem = element_at(base_type::index(*first));
342
343 if constexpr(traits_type::in_place_delete) {
345 alloc_traits::destroy(allocator, std::addressof(elem));
346 } else {
347 auto &other = element_at(base_type::size() - 1u);
348 // destroying on exit allows reentrant destructors
349 [[maybe_unused]] auto unused = std::exchange(elem, std::move(other));
350 alloc_traits::destroy(allocator, std::addressof(other));
352 }
353 }
354 }
355
357 void pop_all() override {
358 allocator_type allocator{get_allocator()};
359
360 for(auto first = base_type::begin(); !(first.index() < 0); ++first) {
361 if constexpr(traits_type::in_place_delete) {
362 if(*first != tombstone) {
364 alloc_traits::destroy(allocator, std::addressof(element_at(static_cast<size_type>(first.index()))));
365 }
366 } else {
368 alloc_traits::destroy(allocator, std::addressof(element_at(static_cast<size_type>(first.index()))));
369 }
370 }
371 }
372
380 underlying_iterator try_emplace([[maybe_unused]] const Entity entt, [[maybe_unused]] const bool force_back, const void *value) override {
381 if(value != nullptr) {
382 if constexpr(std::is_copy_constructible_v<element_type>) {
383 return emplace_element(entt, force_back, *static_cast<const element_type *>(value));
384 } else {
385 return base_type::end();
386 }
387 } else {
388 if constexpr(std::is_default_constructible_v<element_type>) {
389 return emplace_element(entt, force_back);
390 } else {
391 return base_type::end();
392 }
393 }
394 }
395
396public:
398 using allocator_type = Allocator;
400 using base_type = underlying_type;
402 using element_type = Type;
406 using entity_type = Entity;
408 using size_type = std::size_t;
410 using difference_type = std::ptrdiff_t;
412 using pointer = typename container_type::pointer;
414 using const_pointer = typename alloc_traits::template rebind_traits<typename alloc_traits::const_pointer>::const_pointer;
416 using iterator = internal::storage_iterator<container_type, traits_type::page_size>;
418 using const_iterator = internal::storage_iterator<const container_type, traits_type::page_size>;
420 using reverse_iterator = std::reverse_iterator<iterator>;
422 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
433
437
442 explicit basic_storage(const allocator_type &allocator)
444 payload{allocator} {}
445
447 basic_storage(const basic_storage &) = delete;
448
453 // NOLINTBEGIN(bugprone-use-after-move)
454 basic_storage(basic_storage &&other) noexcept
455 : base_type{std::move(other)},
456 payload{std::move(other.payload)} {}
457 // NOLINTEND(bugprone-use-after-move)
458
464 // NOLINTBEGIN(bugprone-use-after-move)
465 basic_storage(basic_storage &&other, const allocator_type &allocator)
466 : base_type{std::move(other), allocator},
467 payload{std::move(other.payload), allocator} {
468 ENTT_ASSERT(alloc_traits::is_always_equal::value || get_allocator() == other.get_allocator(), "Copying a storage is not allowed");
469 }
470 // NOLINTEND(bugprone-use-after-move)
471
473 // NOLINTNEXTLINE(bugprone-exception-escape)
474 ~basic_storage() override {
475 shrink_to_size(0u);
476 }
477
483
490 ENTT_ASSERT(alloc_traits::is_always_equal::value || get_allocator() == other.get_allocator(), "Copying a storage is not allowed");
491 swap(other);
492 return *this;
493 }
494
499 void swap(basic_storage &other) noexcept {
500 using std::swap;
501 swap(payload, other.payload);
502 base_type::swap(other);
503 }
504
509 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
510 return payload.get_allocator();
511 }
512
521 void reserve(const size_type cap) override {
522 if(cap != 0u) {
524 assure_at_least(cap - 1u);
525 }
526 }
527
533 [[nodiscard]] size_type capacity() const noexcept override {
534 return payload.size() * traits_type::page_size;
535 }
536
538 void shrink_to_fit() override {
540 shrink_to_size(base_type::size());
541 }
542
547 [[nodiscard]] const_pointer raw() const noexcept {
548 return payload.data();
549 }
550
552 [[nodiscard]] pointer raw() noexcept {
553 return payload.data();
554 }
555
563 [[nodiscard]] const_iterator cbegin() const noexcept {
564 const auto pos = static_cast<difference_type>(base_type::size());
565 return const_iterator{&payload, pos};
566 }
567
569 [[nodiscard]] const_iterator begin() const noexcept {
570 return cbegin();
571 }
572
574 [[nodiscard]] iterator begin() noexcept {
575 const auto pos = static_cast<difference_type>(base_type::size());
576 return iterator{&payload, pos};
577 }
578
584 [[nodiscard]] const_iterator cend() const noexcept {
585 return const_iterator{&payload, {}};
586 }
587
589 [[nodiscard]] const_iterator end() const noexcept {
590 return cend();
591 }
592
594 [[nodiscard]] iterator end() noexcept {
595 return iterator{&payload, {}};
596 }
597
605 [[nodiscard]] const_reverse_iterator crbegin() const noexcept {
606 return std::make_reverse_iterator(cend());
607 }
608
610 [[nodiscard]] const_reverse_iterator rbegin() const noexcept {
611 return crbegin();
612 }
613
615 [[nodiscard]] reverse_iterator rbegin() noexcept {
616 return std::make_reverse_iterator(end());
617 }
618
624 [[nodiscard]] const_reverse_iterator crend() const noexcept {
625 return std::make_reverse_iterator(cbegin());
626 }
627
629 [[nodiscard]] const_reverse_iterator rend() const noexcept {
630 return crend();
631 }
632
634 [[nodiscard]] reverse_iterator rend() noexcept {
635 return std::make_reverse_iterator(begin());
636 }
637
648 [[nodiscard]] const value_type &get(const entity_type entt) const noexcept {
649 return element_at(base_type::index(entt));
650 }
651
653 [[nodiscard]] value_type &get(const entity_type entt) noexcept {
654 return const_cast<value_type &>(std::as_const(*this).get(entt));
655 }
656
662 [[nodiscard]] std::tuple<const value_type &> get_as_tuple(const entity_type entt) const noexcept {
663 return std::forward_as_tuple(get(entt));
664 }
665
667 [[nodiscard]] std::tuple<value_type &> get_as_tuple(const entity_type entt) noexcept {
668 return std::forward_as_tuple(get(entt));
669 }
670
683 template<typename... Args>
684 value_type &emplace(const entity_type entt, Args &&...args) {
685 if constexpr(std::is_aggregate_v<value_type> && (sizeof...(Args) != 0u || !std::is_default_constructible_v<value_type>)) {
686 const auto it = emplace_element(entt, false, Type{std::forward<Args>(args)...});
687 return element_at(static_cast<size_type>(it.index()));
688 } else {
689 const auto it = emplace_element(entt, false, std::forward<Args>(args)...);
690 return element_at(static_cast<size_type>(it.index()));
691 }
692 }
693
701 template<typename... Func>
702 value_type &patch(const entity_type entt, Func &&...func) {
703 const auto idx = base_type::index(entt);
704 auto &elem = element_at(idx);
705 (std::forward<Func>(func)(elem), ...);
706 return elem;
707 }
708
723 template<typename It>
724 iterator insert(It first, It last, const value_type &value = {}) {
725 for(; first != last; ++first) {
726 emplace_element(*first, true, value);
727 }
728
729 return begin();
730 }
731
745 template<typename EIt, typename CIt, typename = std::enable_if_t<std::is_same_v<typename std::iterator_traits<CIt>::value_type, value_type>>>
746 iterator insert(EIt first, EIt last, CIt from) {
747 for(; first != last; ++first, ++from) {
748 emplace_element(*first, true, *from);
749 }
750
751 return begin();
752 }
753
762 [[nodiscard]] iterable each() noexcept {
763 return iterable{{base_type::begin(), begin()}, {base_type::end(), end()}};
764 }
765
767 [[nodiscard]] const_iterable each() const noexcept {
769 }
770
778 [[nodiscard]] reverse_iterable reach() noexcept {
780 }
781
783 [[nodiscard]] const_reverse_iterable reach() const noexcept {
785 }
786
787private:
788 container_type payload;
789};
790
792template<typename Type, typename Entity, typename Allocator>
793class basic_storage<Type, Entity, Allocator, std::enable_if_t<component_traits<Type, Entity>::page_size == 0u>>
794 : public basic_sparse_set<Entity, typename std::allocator_traits<Allocator>::template rebind_alloc<Entity>> {
795 using alloc_traits = std::allocator_traits<Allocator>;
796 static_assert(std::is_same_v<typename alloc_traits::value_type, Type>, "Invalid value type");
797 using traits_type = component_traits<Type, Entity>;
798
799public:
801 using allocator_type = Allocator;
805 using element_type = Type;
807 using value_type = void;
809 using entity_type = Entity;
811 using size_type = std::size_t;
813 using difference_type = std::ptrdiff_t;
824
828
833 explicit basic_storage(const allocator_type &allocator)
834 : base_type{type_id<element_type>(), storage_policy, allocator} {}
835
837 basic_storage(const basic_storage &) = delete;
838
843 basic_storage(basic_storage &&other) noexcept = default;
844
850 basic_storage(basic_storage &&other, const allocator_type &allocator)
851 : base_type{std::move(other), allocator} {}
852
854 ~basic_storage() override = default;
855
861
867 basic_storage &operator=(basic_storage &&other) noexcept = default;
868
873 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
874 // std::allocator<void> has no cross constructors (waiting for C++20)
875 if constexpr(std::is_void_v<element_type> && !std::is_constructible_v<allocator_type, typename base_type::allocator_type>) {
876 return allocator_type{};
877 } else {
879 }
880 }
881
891 void get([[maybe_unused]] const entity_type entt) const noexcept {
892 ENTT_ASSERT(base_type::contains(entt), "Invalid entity");
893 }
894
900 [[nodiscard]] std::tuple<> get_as_tuple([[maybe_unused]] const entity_type entt) const noexcept {
901 ENTT_ASSERT(base_type::contains(entt), "Invalid entity");
902 return std::tuple{};
903 }
904
915 template<typename... Args>
916 // NOLINTNEXTLINE(cppcoreguidelines-missing-std-forward)
917 void emplace(const entity_type entt, Args &&...) {
919 }
920
927 template<typename... Func>
928 void patch([[maybe_unused]] const entity_type entt, Func &&...func) {
929 ENTT_ASSERT(base_type::contains(entt), "Invalid entity");
930 (std::forward<Func>(func)(), ...);
931 }
932
940 template<typename It, typename... Args>
941 // NOLINTNEXTLINE(cppcoreguidelines-missing-std-forward)
942 void insert(It first, It last, Args &&...) {
943 for(; first != last; ++first) {
944 base_type::try_emplace(*first, true);
945 }
946 }
947
955 [[nodiscard]] iterable each() noexcept {
957 }
958
960 [[nodiscard]] const_iterable each() const noexcept {
962 }
963
971 [[nodiscard]] reverse_iterable reach() noexcept {
973 }
974
976 [[nodiscard]] const_reverse_iterable reach() const noexcept {
978 }
979};
980
986template<typename Entity, typename Allocator>
987class basic_storage<Entity, Entity, Allocator>
988 : public basic_sparse_set<Entity, Allocator> {
989 using alloc_traits = std::allocator_traits<Allocator>;
990 static_assert(std::is_same_v<typename alloc_traits::value_type, Entity>, "Invalid value type");
991 using underlying_iterator = typename basic_sparse_set<Entity, Allocator>::basic_iterator;
992 using traits_type = entt_traits<Entity>;
993
994 auto from_placeholder() noexcept {
995 const auto entt = traits_type::combine(static_cast<typename traits_type::entity_type>(placeholder), {});
996 ENTT_ASSERT(entt != null, "No more entities available");
997 placeholder += static_cast<size_type>(entt != null);
998 return entt;
999 }
1000
1001 auto next() noexcept {
1002 entity_type entt = from_placeholder();
1003
1005 entt = from_placeholder();
1006 }
1007
1008 return entt;
1009 }
1010
1011protected:
1013 void pop_all() override {
1015 placeholder = {};
1016 }
1017
1023 underlying_iterator try_emplace(const Entity hint, const bool, const void *) override {
1024 return base_type::find(generate(hint));
1025 }
1026
1027public:
1029 using allocator_type = Allocator;
1033 using element_type = Entity;
1035 using value_type = void;
1037 using entity_type = Entity;
1039 using size_type = std::size_t;
1041 using difference_type = std::ptrdiff_t;
1052
1057
1062 explicit basic_storage(const allocator_type &allocator)
1063 : base_type{type_id<void>(), storage_policy, allocator} {}
1064
1066 basic_storage(const basic_storage &) = delete;
1067
1072 // NOLINTBEGIN(bugprone-use-after-move)
1074 : base_type{std::move(other)},
1075 placeholder{other.placeholder} {}
1076 // NOLINTEND(bugprone-use-after-move)
1077
1083 // NOLINTBEGIN(bugprone-use-after-move)
1084 basic_storage(basic_storage &&other, const allocator_type &allocator)
1085 : base_type{std::move(other), allocator},
1086 placeholder{other.placeholder} {}
1087 // NOLINTEND(bugprone-use-after-move)
1088
1090 ~basic_storage() override = default;
1091
1097
1104 placeholder = other.placeholder;
1105 base_type::operator=(std::move(other));
1106 return *this;
1107 }
1108
1118 void get([[maybe_unused]] const entity_type entt) const noexcept {
1119 ENTT_ASSERT(base_type::index(entt) < base_type::free_list(), "The requested entity is not a live one");
1120 }
1121
1127 [[nodiscard]] std::tuple<> get_as_tuple([[maybe_unused]] const entity_type entt) const noexcept {
1128 ENTT_ASSERT(base_type::index(entt) < base_type::free_list(), "The requested entity is not a live one");
1129 return std::tuple{};
1130 }
1131
1137 const auto len = base_type::free_list();
1138 const auto entt = (len == base_type::size()) ? next() : base_type::data()[len];
1139 return *base_type::try_emplace(entt, true);
1140 }
1141
1152 if(hint != null && hint != tombstone) {
1153 if(const auto curr = traits_type::construct(traits_type::to_entity(hint), base_type::current(hint)); curr == tombstone || !(base_type::index(curr) < base_type::free_list())) {
1154 return *base_type::try_emplace(hint, true);
1155 }
1156 }
1157
1158 return generate();
1159 }
1160
1167 template<typename It>
1168 void generate(It first, It last) {
1169 for(const auto sz = base_type::size(); first != last && base_type::free_list() != sz; ++first) {
1171 }
1172
1173 for(; first != last; ++first) {
1174 *first = *base_type::try_emplace(next(), true);
1175 }
1176 }
1177
1182 [[deprecated("use ::generate() instead")]] entity_type emplace() {
1183 return generate();
1184 }
1185
1195 [[deprecated("use ::generate(hint) instead")]] entity_type emplace(const entity_type hint) {
1196 return generate(hint);
1197 }
1198
1205 template<typename... Func>
1206 void patch([[maybe_unused]] const entity_type entt, Func &&...func) {
1207 ENTT_ASSERT(base_type::index(entt) < base_type::free_list(), "The requested entity is not a live one");
1208 (std::forward<Func>(func)(), ...);
1209 }
1210
1217 template<typename It>
1218 [[deprecated("use ::generate(first, last) instead")]] void insert(It first, It last) {
1219 generate(std::move(first), std::move(last));
1220 }
1221
1229 [[nodiscard]] iterable each() noexcept {
1230 return std::as_const(*this).each();
1231 }
1232
1234 [[nodiscard]] const_iterable each() const noexcept {
1235 const auto it = base_type::cend();
1236 const auto offset = static_cast<difference_type>(base_type::free_list());
1237 return const_iterable{it - offset, it};
1238 }
1239
1247 [[nodiscard]] reverse_iterable reach() noexcept {
1248 return std::as_const(*this).reach();
1249 }
1250
1252 [[nodiscard]] const_reverse_iterable reach() const noexcept {
1253 const auto it = base_type::crbegin();
1254 const auto offset = static_cast<difference_type>(base_type::free_list());
1255 return const_reverse_iterable{it, it + offset};
1256 }
1257
1265 void start_from(const entity_type hint) {
1266 placeholder = static_cast<size_type>(traits_type::to_entity(hint));
1267 }
1268
1269private:
1270 size_type placeholder{};
1271};
1272
1273} // namespace entt
1274
1275#endif
typename Traits::entity_type entity_type
Underlying entity type.
Definition entity.hpp:71
static constexpr value_type construct(const entity_type entity, const version_type version) noexcept
Constructs an identifier from its parts.
Definition entity.hpp:131
static constexpr entity_type to_entity(const value_type value) noexcept
Returns the entity part once converted to the underlying type.
Definition entity.hpp:94
static constexpr value_type combine(const entity_type lhs, const entity_type rhs) noexcept
Combines two identifiers in a single one.
Definition entity.hpp:149
static constexpr version_type to_version(const value_type value) noexcept
Returns the version part once converted to the underlying type.
Definition entity.hpp:103
virtual basic_iterator try_emplace(const Entity entt, const bool force_back, const void *=nullptr)
version_type current(const entity_type entt) const noexcept
Returns the contained version for an identifier.
size_type free_list() const noexcept
Returns data on the free list whose meaning depends on the mode.
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:1252
std::size_t size_type
Unsigned integer type.
Definition storage.hpp:1039
iterable_adaptor< internal::extended_storage_iterator< typename base_type::reverse_iterator > > reverse_iterable
Extended reverse iterable storage proxy.
Definition storage.hpp:1047
static constexpr deletion_policy storage_policy
Storage deletion policy.
Definition storage.hpp:1051
void get(const entity_type entt) const noexcept
Returns the object assigned to an entity, that is void.
Definition storage.hpp:1118
void value_type
Type of the objects assigned to entities.
Definition storage.hpp:1035
entity_type generate(const entity_type hint)
Creates a new identifier or recycles a destroyed one.
Definition storage.hpp:1151
iterable_adaptor< internal::extended_storage_iterator< typename base_type::const_iterator > > const_iterable
Constant extended iterable storage proxy.
Definition storage.hpp:1045
void insert(It first, It last)
Assigns each element in a range an identifier.
Definition storage.hpp:1218
Entity entity_type
Underlying entity identifier.
Definition storage.hpp:1037
void pop_all() override
Erases all entities of a storage.
Definition storage.hpp:1013
entity_type emplace(const entity_type hint)
Creates a new identifier or recycles a destroyed one.
Definition storage.hpp:1195
~basic_storage() override=default
Default destructor.
underlying_iterator try_emplace(const Entity hint, const bool, const void *) override
Assigns an entity to a storage.
Definition storage.hpp:1023
basic_storage & operator=(basic_storage &&other) noexcept
Move assignment operator.
Definition storage.hpp:1103
entity_type generate()
Creates a new identifier or recycles a destroyed one.
Definition storage.hpp:1136
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:1247
basic_storage(basic_storage &&other, const allocator_type &allocator)
Allocator-extended move constructor.
Definition storage.hpp:1084
std::ptrdiff_t difference_type
Signed integer type.
Definition storage.hpp:1041
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:1234
basic_storage(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition storage.hpp:1062
void generate(It first, It last)
Assigns each element in a range an identifier.
Definition storage.hpp:1168
iterable_adaptor< internal::extended_storage_iterator< typename base_type::const_reverse_iterator > > const_reverse_iterable
Constant extended reverse iterable storage proxy.
Definition storage.hpp:1049
iterable_adaptor< internal::extended_storage_iterator< typename base_type::iterator > > iterable
Extended iterable storage proxy.
Definition storage.hpp:1043
basic_sparse_set< Entity, Allocator > base_type
Base type.
Definition storage.hpp:1031
basic_storage(basic_storage &&other) noexcept
Move constructor.
Definition storage.hpp:1073
entity_type emplace()
Creates a new identifier or recycles a destroyed one.
Definition storage.hpp:1182
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:1229
basic_storage(const basic_storage &)=delete
Default copy constructor, deleted on purpose.
void patch(const entity_type entt, Func &&...func)
Updates a given identifier.
Definition storage.hpp:1206
void start_from(const entity_type hint)
Sets the starting identifier for generation.
Definition storage.hpp:1265
basic_storage & operator=(const basic_storage &)=delete
Default copy assignment operator, deleted on purpose.
std::tuple get_as_tuple(const entity_type entt) const noexcept
Returns an empty tuple.
Definition storage.hpp:1127
basic_storage & operator=(const basic_storage &)=delete
Default copy assignment operator, deleted on purpose.
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition storage.hpp:873
basic_sparse_set< Entity, typename alloc_traits::template rebind_alloc< Entity > > base_type
Base type.
Definition storage.hpp:803
std::tuple get_as_tuple(const entity_type entt) const noexcept
Returns an empty tuple.
Definition storage.hpp:900
void patch(const entity_type entt, Func &&...func)
Updates the instance assigned to a given entity in-place.
Definition storage.hpp:928
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:971
basic_storage(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition storage.hpp:833
basic_storage(basic_storage &&other, const allocator_type &allocator)
Allocator-extended move constructor.
Definition storage.hpp:850
iterable_adaptor< internal::extended_storage_iterator< typename base_type::iterator > > iterable
Extended iterable storage proxy.
Definition storage.hpp:815
iterable_adaptor< internal::extended_storage_iterator< typename base_type::reverse_iterator > > reverse_iterable
Extended reverse iterable storage proxy.
Definition storage.hpp:819
iterable_adaptor< internal::extended_storage_iterator< typename base_type::const_iterator > > const_iterable
Constant extended iterable storage proxy.
Definition storage.hpp:817
basic_storage(const basic_storage &)=delete
Default copy constructor, deleted on purpose.
void get(const entity_type entt) const noexcept
Returns the object assigned to an entity, that is void.
Definition storage.hpp:891
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:960
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:976
basic_storage & operator=(basic_storage &&other) noexcept=default
Move assignment operator.
iterable_adaptor< internal::extended_storage_iterator< typename base_type::const_reverse_iterator > > const_reverse_iterable
Constant extended reverse iterable storage proxy.
Definition storage.hpp:821
void emplace(const entity_type entt, Args &&...)
Assigns an entity to a storage and constructs its object.
Definition storage.hpp:917
iterator end() noexcept
Returns an iterator to the end.
Definition storage.hpp:594
~basic_storage() override
Default destructor.
Definition storage.hpp:474
basic_storage()
Default constructor.
Definition storage.hpp:435
iterator insert(EIt first, EIt last, CIt from)
Assigns one or more entities to a storage and constructs their objects from a given range.
Definition storage.hpp:746
const_reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition storage.hpp:610
const_iterator end() const noexcept
Returns an iterator to the end.
Definition storage.hpp:589
const_pointer raw() const noexcept
Direct access to the array of objects.
Definition storage.hpp:547
void pop_all() override
Erases all entities of a storage.
Definition storage.hpp:357
basic_storage(basic_storage &&other) noexcept
Move constructor.
Definition storage.hpp:454
const value_type & get(const entity_type entt) const noexcept
Returns the object assigned to an entity.
Definition storage.hpp:648
const_iterator cend() const noexcept
Returns an iterator to the end.
Definition storage.hpp:584
size_type capacity() const noexcept override
Returns the number of elements that a storage has currently allocated space for.
Definition storage.hpp:533
iterable_adaptor< internal::extended_storage_iterator< typename base_type::const_reverse_iterator, const_reverse_iterator > > const_reverse_iterable
Definition storage.hpp:430
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition storage.hpp:509
typename alloc_traits::template rebind_traits< typename alloc_traits::const_pointer >::const_pointer const_pointer
Definition storage.hpp:414
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:767
void swap(basic_storage &other) noexcept
Exchanges the contents with those of a given storage.
Definition storage.hpp:499
reverse_iterator rbegin() noexcept
Returns a reverse iterator to the beginning.
Definition storage.hpp:615
internal::storage_iterator< container_type, traits_type::page_size > iterator
Definition storage.hpp:416
const_iterator begin() const noexcept
Returns an iterator to the beginning.
Definition storage.hpp:569
underlying_type base_type
Definition storage.hpp:400
reverse_iterator rend() noexcept
Returns a reverse iterator to the end.
Definition storage.hpp:634
basic_storage & operator=(basic_storage &&other) noexcept
Move assignment operator.
Definition storage.hpp:489
const_reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
Definition storage.hpp:629
underlying_iterator try_emplace(const Entity entt, const bool force_back, const void *value) override
Assigns an entity to a storage.
Definition storage.hpp:380
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
Definition storage.hpp:563
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition storage.hpp:422
value_type & patch(const entity_type entt, Func &&...func)
Updates the instance assigned to a given entity in-place.
Definition storage.hpp:702
std::reverse_iterator< iterator > reverse_iterator
Definition storage.hpp:420
std::size_t size_type
Unsigned integer type.
Definition storage.hpp:408
iterator insert(It first, It last, const value_type &value={})
Assigns one or more entities to a storage and constructs their objects from a given instance.
Definition storage.hpp:724
void pop(underlying_iterator first, underlying_iterator last) override
Erases entities from a storage.
Definition storage.hpp:338
typename container_type::pointer pointer
Definition storage.hpp:412
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:778
iterable_adaptor< internal::extended_storage_iterator< typename base_type::reverse_iterator, reverse_iterator > > reverse_iterable
Definition storage.hpp:428
iterable_adaptor< internal::extended_storage_iterator< typename base_type::iterator, iterator > > iterable
Definition storage.hpp:424
pointer raw() noexcept
Direct access to the array of objects.
Definition storage.hpp:552
std::tuple< value_type & > get_as_tuple(const entity_type entt) noexcept
Returns the object assigned to an entity as a tuple.
Definition storage.hpp:667
std::ptrdiff_t difference_type
Definition storage.hpp:410
value_type & get(const entity_type entt) noexcept
Returns the object assigned to an entity.
Definition storage.hpp:653
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the end.
Definition storage.hpp:624
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:783
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:762
basic_storage & operator=(const basic_storage &)=delete
Default copy assignment operator, deleted on purpose.
void reserve(const size_type cap) override
Increases the capacity of a storage.
Definition storage.hpp:521
basic_storage(const allocator_type &allocator)
Constructs an empty storage with a given allocator.
Definition storage.hpp:442
value_type & emplace(const entity_type entt, Args &&...args)
Assigns an entity to a storage and constructs its object.
Definition storage.hpp:684
std::tuple< const value_type & > get_as_tuple(const entity_type entt) const noexcept
Returns the object assigned to an entity as a tuple.
Definition storage.hpp:662
void shrink_to_fit() override
Requests the removal of unused capacity.
Definition storage.hpp:538
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition storage.hpp:605
internal::storage_iterator< const container_type, traits_type::page_size > const_iterator
Definition storage.hpp:418
basic_storage(basic_storage &&other, const allocator_type &allocator)
Allocator-extended move constructor.
Definition storage.hpp:465
iterable_adaptor< internal::extended_storage_iterator< typename base_type::const_iterator, const_iterator > > const_iterable
Definition storage.hpp:426
basic_storage(const basic_storage &)=delete
Default copy constructor, deleted on purpose.
iterator begin() noexcept
Returns an iterator to the beginning.
Definition storage.hpp:574
static constexpr deletion_policy storage_policy
Definition storage.hpp:432
Allocator allocator_type
Allocator type.
Definition storage.hpp:398
EnTT default namespace.
Definition dense_map.hpp:22
constexpr std::enable_if_t< std::is_unsigned_v< Type >, Type > fast_mod(const Type value, const std::size_t mod) noexcept
Fast module utility function (powers of two only).
Definition bit.hpp:63
constexpr null_t null
Compile-time constant for null entities.
Definition entity.hpp:375
constexpr tombstone_t tombstone
Compile-time constant for tombstone entities.
Definition entity.hpp:384
constexpr Type * uninitialized_construct_using_allocator(Type *value, const Allocator &allocator, Args &&...args)
Uses-allocator construction utility (waiting for C++20).
Definition memory.hpp:238
constexpr get_t< Type... > get
Variable template for lists of observed elements.
Definition fwd.hpp:167
constexpr bool operator<=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator<(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr type_list< Type..., Other... > operator+(type_list< Type... >, type_list< Other... >)
Concatenates multiple type lists.
deletion_policy
Storage deletion policy.
Definition fwd.hpp:17
@ swap_only
Swap-only deletion policy.
Definition fwd.hpp:23
constexpr bool operator!=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator>=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
const type_info & type_id() noexcept
Returns the type info object associated to a given type.
@ ref
Aliasing mode, the object points to a non-const element.
Definition fwd.hpp:19
constexpr bool operator>(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr auto to_address(Type &&ptr) noexcept
Unwraps fancy pointers, does nothing otherwise (waiting for C++20).
Definition memory.hpp:20
constexpr bool operator==(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
Common way to access various properties of components.
Definition component.hpp:43
static constexpr bool in_place_delete
Definition component.hpp:52
static constexpr std::size_t page_size
Definition component.hpp:54
Entity traits.
Definition entity.hpp:163
Utility class to create an iterable object from a pair of iterators.
Definition iterator.hpp:141