EnTT 3.13.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/iterator.hpp"
13#include "../core/memory.hpp"
14#include "../core/type_info.hpp"
15#include "component.hpp"
16#include "entity.hpp"
17#include "fwd.hpp"
18#include "sparse_set.hpp"
19
20namespace entt {
21
23namespace internal {
24
25template<typename Container, std::size_t Size>
26class storage_iterator final {
27 friend storage_iterator<const Container, Size>;
28
29 using container_type = std::remove_const_t<Container>;
30 using alloc_traits = std::allocator_traits<typename container_type::allocator_type>;
31
32 using iterator_traits = std::iterator_traits<std::conditional_t<
33 std::is_const_v<Container>,
34 typename alloc_traits::template rebind_traits<typename std::pointer_traits<typename container_type::value_type>::element_type>::const_pointer,
35 typename alloc_traits::template rebind_traits<typename std::pointer_traits<typename container_type::value_type>::element_type>::pointer>>;
36
37public:
38 using value_type = typename iterator_traits::value_type;
39 using pointer = typename iterator_traits::pointer;
40 using reference = typename iterator_traits::reference;
41 using difference_type = typename iterator_traits::difference_type;
42 using iterator_category = std::random_access_iterator_tag;
43
44 constexpr storage_iterator() noexcept = default;
45
46 constexpr storage_iterator(Container *ref, const difference_type idx) noexcept
47 : payload{ref},
48 offset{idx} {}
49
50 template<bool Const = std::is_const_v<Container>, typename = std::enable_if_t<Const>>
51 constexpr storage_iterator(const storage_iterator<std::remove_const_t<Container>, Size> &other) noexcept
52 : storage_iterator{other.payload, other.offset} {}
53
54 constexpr storage_iterator &operator++() noexcept {
55 return --offset, *this;
56 }
57
58 constexpr storage_iterator operator++(int) noexcept {
59 storage_iterator orig = *this;
60 return ++(*this), orig;
61 }
62
63 constexpr storage_iterator &operator--() noexcept {
64 return ++offset, *this;
65 }
66
67 constexpr storage_iterator operator--(int) noexcept {
68 storage_iterator orig = *this;
69 return operator--(), orig;
70 }
71
72 constexpr storage_iterator &operator+=(const difference_type value) noexcept {
73 offset -= value;
74 return *this;
75 }
76
77 constexpr storage_iterator operator+(const difference_type value) const noexcept {
78 storage_iterator copy = *this;
79 return (copy += value);
80 }
81
82 constexpr storage_iterator &operator-=(const difference_type value) noexcept {
83 return (*this += -value);
84 }
85
86 constexpr storage_iterator operator-(const difference_type value) const noexcept {
87 return (*this + -value);
88 }
89
90 [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept {
91 const auto pos = index() - value;
92 return (*payload)[pos / Size][fast_mod(pos, Size)];
93 }
94
95 [[nodiscard]] constexpr pointer operator->() const noexcept {
96 const auto pos = index();
97 return (*payload)[pos / Size] + fast_mod(pos, Size);
98 }
99
100 [[nodiscard]] constexpr reference operator*() const noexcept {
101 return *operator->();
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, std::size_t Size>
114[[nodiscard]] constexpr std::ptrdiff_t operator-(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
115 return rhs.index() - lhs.index();
116}
117
118template<typename Lhs, typename Rhs, std::size_t Size>
119[[nodiscard]] constexpr bool operator==(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
120 return lhs.index() == rhs.index();
121}
122
123template<typename Lhs, typename Rhs, std::size_t Size>
124[[nodiscard]] constexpr bool operator!=(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
125 return !(lhs == rhs);
126}
127
128template<typename Lhs, typename Rhs, std::size_t Size>
129[[nodiscard]] constexpr bool operator<(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
130 return lhs.index() > rhs.index();
131}
132
133template<typename Lhs, typename Rhs, std::size_t Size>
134[[nodiscard]] constexpr bool operator>(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
135 return rhs < lhs;
136}
137
138template<typename Lhs, typename Rhs, std::size_t Size>
139[[nodiscard]] constexpr bool operator<=(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
140 return !(lhs > rhs);
141}
142
143template<typename Lhs, typename Rhs, std::size_t Size>
144[[nodiscard]] constexpr bool operator>=(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &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 difference_type = std::ptrdiff_t;
156 using value_type = decltype(std::tuple_cat(std::make_tuple(*std::declval<It>()), std::forward_as_tuple(*std::declval<Other>()...)));
157 using pointer = input_iterator_pointer<value_type>;
158 using reference = value_type;
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 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
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
236 [[nodiscard]] auto &element_at(const std::size_t pos) const {
237 return payload[pos / traits_type::page_size][fast_mod(pos, traits_type::page_size)];
238 }
239
240 auto assure_at_least(const std::size_t pos) {
241 const auto idx = pos / traits_type::page_size;
242
243 if(!(idx < payload.size())) {
244 auto curr = payload.size();
245 allocator_type allocator{get_allocator()};
246 payload.resize(idx + 1u, nullptr);
247
248 ENTT_TRY {
249 for(const auto last = payload.size(); curr < last; ++curr) {
250 payload[curr] = alloc_traits::allocate(allocator, traits_type::page_size);
251 }
252 }
253 ENTT_CATCH {
254 payload.resize(curr);
255 ENTT_THROW;
256 }
257 }
258
259 return payload[idx] + fast_mod(pos, traits_type::page_size);
260 }
261
262 template<typename... Args>
263 auto emplace_element(const Entity entt, const bool force_back, Args &&...args) {
264 const auto it = base_type::try_emplace(entt, force_back);
265
266 ENTT_TRY {
267 auto elem = assure_at_least(static_cast<size_type>(it.index()));
268 entt::uninitialized_construct_using_allocator(to_address(elem), get_allocator(), std::forward<Args>(args)...);
269 }
270 ENTT_CATCH {
271 base_type::pop(it, it + 1u);
272 ENTT_THROW;
273 }
274
275 return it;
276 }
277
278 void shrink_to_size(const std::size_t sz) {
279 const auto from = (sz + traits_type::page_size - 1u) / traits_type::page_size;
280 allocator_type allocator{get_allocator()};
281
282 for(auto pos = sz, length = base_type::size(); pos < length; ++pos) {
283 if constexpr(traits_type::in_place_delete) {
284 if(base_type::data()[pos] != tombstone) {
285 alloc_traits::destroy(allocator, std::addressof(element_at(pos)));
286 }
287 } else {
288 alloc_traits::destroy(allocator, std::addressof(element_at(pos)));
289 }
290 }
291
292 for(auto pos = from, last = payload.size(); pos < last; ++pos) {
293 alloc_traits::deallocate(allocator, payload[pos], traits_type::page_size);
294 }
295
296 payload.resize(from);
297 }
298
299private:
300 const void *get_at(const std::size_t pos) const final {
301 return std::addressof(element_at(pos));
302 }
303
304 void swap_or_move([[maybe_unused]] const std::size_t from, [[maybe_unused]] const std::size_t to) override {
305 static constexpr bool is_pinned_type_v = !(std::is_move_constructible_v<Type> && std::is_move_assignable_v<Type>);
306 // use a runtime value to avoid compile-time suppression that drives the code coverage tool crazy
307 ENTT_ASSERT((from + 1u) && !is_pinned_type_v, "Pinned type");
308
309 if constexpr(!is_pinned_type_v) {
310 auto &elem = element_at(from);
311
312 if constexpr(traits_type::in_place_delete) {
313 if(base_type::operator[](to) == tombstone) {
314 allocator_type allocator{get_allocator()};
315 entt::uninitialized_construct_using_allocator(to_address(assure_at_least(to)), allocator, std::move(elem));
316 alloc_traits::destroy(allocator, std::addressof(elem));
317 return;
318 }
319 }
320
321 using std::swap;
322 swap(elem, element_at(to));
323 }
324 }
325
326protected:
332 void pop(underlying_iterator first, underlying_iterator last) override {
333 for(allocator_type allocator{get_allocator()}; first != last; ++first) {
334 // cannot use first.index() because it would break with cross iterators
335 auto &elem = element_at(base_type::index(*first));
336
337 if constexpr(traits_type::in_place_delete) {
339 alloc_traits::destroy(allocator, std::addressof(elem));
340 } else {
341 auto &other = element_at(base_type::size() - 1u);
342 // destroying on exit allows reentrant destructors
343 [[maybe_unused]] auto unused = std::exchange(elem, std::move(other));
344 alloc_traits::destroy(allocator, std::addressof(other));
346 }
347 }
348 }
349
351 void pop_all() override {
352 allocator_type allocator{get_allocator()};
353
354 for(auto first = base_type::begin(); !(first.index() < 0); ++first) {
355 if constexpr(traits_type::in_place_delete) {
356 if(*first != tombstone) {
358 alloc_traits::destroy(allocator, std::addressof(element_at(static_cast<size_type>(first.index()))));
359 }
360 } else {
362 alloc_traits::destroy(allocator, std::addressof(element_at(static_cast<size_type>(first.index()))));
363 }
364 }
365 }
366
374 underlying_iterator try_emplace([[maybe_unused]] const Entity entt, [[maybe_unused]] const bool force_back, const void *value) override {
375 if(value) {
376 if constexpr(std::is_copy_constructible_v<value_type>) {
377 return emplace_element(entt, force_back, *static_cast<const value_type *>(value));
378 } else {
379 return base_type::end();
380 }
381 } else {
382 if constexpr(std::is_default_constructible_v<value_type>) {
383 return emplace_element(entt, force_back);
384 } else {
385 return base_type::end();
386 }
387 }
388 }
389
390public:
394 using value_type = Type;
398 using entity_type = Entity;
400 using size_type = std::size_t;
402 using allocator_type = Allocator;
404 using pointer = typename container_type::pointer;
406 using const_pointer = typename alloc_traits::template rebind_traits<typename alloc_traits::const_pointer>::const_pointer;
408 using iterator = internal::storage_iterator<container_type, traits_type::page_size>;
410 using const_iterator = internal::storage_iterator<const container_type, traits_type::page_size>;
412 using reverse_iterator = std::reverse_iterator<iterator>;
414 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
423
427
432 explicit basic_storage(const allocator_type &allocator)
433 : base_type{type_id<value_type>(), deletion_policy{traits_type::in_place_delete}, allocator},
434 payload{allocator} {}
435
440 basic_storage(basic_storage &&other) noexcept
441 : base_type{std::move(other)},
442 payload{std::move(other.payload)} {}
443
449 basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
450 : base_type{std::move(other), allocator},
451 payload{std::move(other.payload), allocator} {
452 ENTT_ASSERT(alloc_traits::is_always_equal::value || payload.get_allocator() == other.payload.get_allocator(), "Copying a storage is not allowed");
453 }
454
456 ~basic_storage() override {
457 shrink_to_size(0u);
458 }
459
466 ENTT_ASSERT(alloc_traits::is_always_equal::value || payload.get_allocator() == other.payload.get_allocator(), "Copying a storage is not allowed");
467
468 shrink_to_size(0u);
469 base_type::operator=(std::move(other));
470 payload = std::move(other.payload);
471 return *this;
472 }
473
478 void swap(basic_storage &other) {
479 using std::swap;
480 base_type::swap(other);
481 swap(payload, other.payload);
482 }
483
488 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
489 return payload.get_allocator();
490 }
491
500 void reserve(const size_type cap) override {
501 if(cap != 0u) {
503 assure_at_least(cap - 1u);
504 }
505 }
506
512 [[nodiscard]] size_type capacity() const noexcept override {
513 return payload.size() * traits_type::page_size;
514 }
515
517 void shrink_to_fit() override {
519 shrink_to_size(base_type::size());
520 }
521
526 [[nodiscard]] const_pointer raw() const noexcept {
527 return payload.data();
528 }
529
531 [[nodiscard]] pointer raw() noexcept {
532 return payload.data();
533 }
534
542 [[nodiscard]] const_iterator cbegin() const noexcept {
543 const auto pos = static_cast<typename iterator::difference_type>(base_type::size());
544 return const_iterator{&payload, pos};
545 }
546
548 [[nodiscard]] const_iterator begin() const noexcept {
549 return cbegin();
550 }
551
553 [[nodiscard]] iterator begin() noexcept {
554 const auto pos = static_cast<typename iterator::difference_type>(base_type::size());
555 return iterator{&payload, pos};
556 }
557
563 [[nodiscard]] const_iterator cend() const noexcept {
564 return const_iterator{&payload, {}};
565 }
566
568 [[nodiscard]] const_iterator end() const noexcept {
569 return cend();
570 }
571
573 [[nodiscard]] iterator end() noexcept {
574 return iterator{&payload, {}};
575 }
576
584 [[nodiscard]] const_reverse_iterator crbegin() const noexcept {
585 return std::make_reverse_iterator(cend());
586 }
587
589 [[nodiscard]] const_reverse_iterator rbegin() const noexcept {
590 return crbegin();
591 }
592
594 [[nodiscard]] reverse_iterator rbegin() noexcept {
595 return std::make_reverse_iterator(end());
596 }
597
603 [[nodiscard]] const_reverse_iterator crend() const noexcept {
604 return std::make_reverse_iterator(cbegin());
605 }
606
608 [[nodiscard]] const_reverse_iterator rend() const noexcept {
609 return crend();
610 }
611
613 [[nodiscard]] reverse_iterator rend() noexcept {
614 return std::make_reverse_iterator(begin());
615 }
616
627 [[nodiscard]] const value_type &get(const entity_type entt) const noexcept {
628 return element_at(base_type::index(entt));
629 }
630
632 [[nodiscard]] value_type &get(const entity_type entt) noexcept {
633 return const_cast<value_type &>(std::as_const(*this).get(entt));
634 }
635
641 [[nodiscard]] std::tuple<const value_type &> get_as_tuple(const entity_type entt) const noexcept {
642 return std::forward_as_tuple(get(entt));
643 }
644
646 [[nodiscard]] std::tuple<value_type &> get_as_tuple(const entity_type entt) noexcept {
647 return std::forward_as_tuple(get(entt));
648 }
649
662 template<typename... Args>
663 value_type &emplace(const entity_type entt, Args &&...args) {
664 if constexpr(std::is_aggregate_v<value_type> && (sizeof...(Args) != 0u || !std::is_default_constructible_v<value_type>)) {
665 const auto it = emplace_element(entt, false, Type{std::forward<Args>(args)...});
666 return element_at(static_cast<size_type>(it.index()));
667 } else {
668 const auto it = emplace_element(entt, false, std::forward<Args>(args)...);
669 return element_at(static_cast<size_type>(it.index()));
670 }
671 }
672
680 template<typename... Func>
681 value_type &patch(const entity_type entt, Func &&...func) {
682 const auto idx = base_type::index(entt);
683 auto &elem = element_at(idx);
684 (std::forward<Func>(func)(elem), ...);
685 return elem;
686 }
687
702 template<typename It>
703 iterator insert(It first, It last, const value_type &value = {}) {
704 for(; first != last; ++first) {
705 emplace_element(*first, true, value);
706 }
707
708 return begin();
709 }
710
724 template<typename EIt, typename CIt, typename = std::enable_if_t<std::is_same_v<typename std::iterator_traits<CIt>::value_type, value_type>>>
725 iterator insert(EIt first, EIt last, CIt from) {
726 for(; first != last; ++first, ++from) {
727 emplace_element(*first, true, *from);
728 }
729
730 return begin();
731 }
732
741 [[nodiscard]] iterable each() noexcept {
742 return {internal::extended_storage_iterator{base_type::begin(), begin()}, internal::extended_storage_iterator{base_type::end(), end()}};
743 }
744
746 [[nodiscard]] const_iterable each() const noexcept {
747 return {internal::extended_storage_iterator{base_type::cbegin(), cbegin()}, internal::extended_storage_iterator{base_type::cend(), cend()}};
748 }
749
757 [[nodiscard]] reverse_iterable reach() noexcept {
758 return {internal::extended_storage_iterator{base_type::rbegin(), rbegin()}, internal::extended_storage_iterator{base_type::rend(), rend()}};
759 }
760
762 [[nodiscard]] const_reverse_iterable reach() const noexcept {
763 return {internal::extended_storage_iterator{base_type::crbegin(), crbegin()}, internal::extended_storage_iterator{base_type::crend(), crend()}};
764 }
765
766private:
767 container_type payload;
768};
769
771template<typename Type, typename Entity, typename Allocator>
772class basic_storage<Type, Entity, Allocator, std::enable_if_t<component_traits<Type>::page_size == 0u>>
773 : public basic_sparse_set<Entity, typename std::allocator_traits<Allocator>::template rebind_alloc<Entity>> {
774 using alloc_traits = std::allocator_traits<Allocator>;
775 static_assert(std::is_same_v<typename alloc_traits::value_type, Type>, "Invalid value type");
776
777public:
781 using value_type = Type;
785 using entity_type = Entity;
787 using size_type = std::size_t;
789 using allocator_type = Allocator;
798
802
807 explicit basic_storage(const allocator_type &allocator)
808 : base_type{type_id<value_type>(), deletion_policy{traits_type::in_place_delete}, allocator} {}
809
814 basic_storage(basic_storage &&other) noexcept = default;
815
821 basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
822 : base_type{std::move(other), allocator} {}
823
829 basic_storage &operator=(basic_storage &&other) noexcept = default;
830
835 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
836 // std::allocator<void> has no cross constructors (waiting for C++20)
837 if constexpr(std::is_void_v<value_type> && !std::is_constructible_v<allocator_type, typename base_type::allocator_type>) {
838 return allocator_type{};
839 } else {
841 }
842 }
843
853 void get([[maybe_unused]] const entity_type entt) const noexcept {
854 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
855 }
856
867 [[nodiscard]] std::tuple<> get_as_tuple([[maybe_unused]] const entity_type entt) const noexcept {
868 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
869 return std::tuple{};
870 }
871
882 template<typename... Args>
883 void emplace(const entity_type entt, Args &&...) {
885 }
886
893 template<typename... Func>
894 void patch([[maybe_unused]] const entity_type entt, Func &&...func) {
895 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
896 (std::forward<Func>(func)(), ...);
897 }
898
906 template<typename It, typename... Args>
907 void insert(It first, It last, Args &&...) {
908 for(; first != last; ++first) {
909 base_type::try_emplace(*first, true);
910 }
911 }
912
920 [[nodiscard]] iterable each() noexcept {
921 return {internal::extended_storage_iterator{base_type::begin()}, internal::extended_storage_iterator{base_type::end()}};
922 }
923
925 [[nodiscard]] const_iterable each() const noexcept {
926 return {internal::extended_storage_iterator{base_type::cbegin()}, internal::extended_storage_iterator{base_type::cend()}};
927 }
928
936 [[nodiscard]] reverse_iterable reach() noexcept {
937 return {internal::extended_storage_iterator{base_type::rbegin()}, internal::extended_storage_iterator{base_type::rend()}};
938 }
939
941 [[nodiscard]] const_reverse_iterable reach() const noexcept {
942 return {internal::extended_storage_iterator{base_type::crbegin()}, internal::extended_storage_iterator{base_type::crend()}};
943 }
944};
945
951template<typename Entity, typename Allocator>
952class basic_storage<Entity, Entity, Allocator>
953 : public basic_sparse_set<Entity, Allocator> {
954 using alloc_traits = std::allocator_traits<Allocator>;
955 static_assert(std::is_same_v<typename alloc_traits::value_type, Entity>, "Invalid value type");
957 using underlying_iterator = typename underlying_type::basic_iterator;
958
959 auto entity_at(const std::size_t pos) const noexcept {
960 ENTT_ASSERT(pos < underlying_type::traits_type::to_entity(null), "Invalid element");
961 return underlying_type::traits_type::combine(static_cast<typename underlying_type::traits_type::entity_type>(pos), {});
962 }
963
964protected:
970 underlying_iterator try_emplace(const Entity hint, const bool, const void *) override {
971 return base_type::find(emplace(hint));
972 }
973
974public:
978 using value_type = Entity;
980 using entity_type = Entity;
982 using size_type = std::size_t;
984 using allocator_type = Allocator;
993
997 }
998
1003 explicit basic_storage(const allocator_type &allocator)
1004 : base_type{type_id<void>(), deletion_policy::swap_only, allocator} {}
1005
1011 : base_type{std::move(other)} {}
1012
1018 basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
1019 : base_type{std::move(other), allocator} {}
1020
1027 base_type::operator=(std::move(other));
1028 return *this;
1029 }
1030
1040 void get([[maybe_unused]] const entity_type entt) const noexcept {
1041 ENTT_ASSERT(base_type::index(entt) < base_type::free_list(), "The requested entity is not a live one");
1042 }
1043
1054 [[nodiscard]] std::tuple<> get_as_tuple([[maybe_unused]] const entity_type entt) const noexcept {
1055 ENTT_ASSERT(base_type::index(entt) < base_type::free_list(), "The requested entity is not a live one");
1056 return std::tuple{};
1057 }
1058
1064 const auto len = base_type::free_list();
1065 const auto entt = (len == base_type::size()) ? entity_at(len) : base_type::data()[len];
1066 return *base_type::try_emplace(entt, true);
1067 }
1068
1079 if(hint == null || hint == tombstone) {
1080 return emplace();
1081 } else if(const auto curr = underlying_type::traits_type::construct(underlying_type::traits_type::to_entity(hint), base_type::current(hint)); curr == tombstone) {
1082 const auto pos = static_cast<size_type>(underlying_type::traits_type::to_entity(hint));
1083 const auto entt = *base_type::try_emplace(hint, true);
1084
1085 while(!(pos < base_type::size())) {
1086 base_type::try_emplace(entity_at(base_type::size() - 1u), false);
1087 }
1088
1089 return entt;
1090 } else if(const auto idx = base_type::index(curr); idx < base_type::free_list()) {
1091 return emplace();
1092 } else {
1093 return *base_type::try_emplace(hint, true);
1094 }
1095 }
1096
1103 template<typename... Func>
1104 void patch([[maybe_unused]] const entity_type entt, Func &&...func) {
1105 ENTT_ASSERT(base_type::index(entt) < base_type::free_list(), "The requested entity is not a live one");
1106 (std::forward<Func>(func)(), ...);
1107 }
1108
1115 template<typename It>
1116 void insert(It first, It last) {
1117 for(const auto sz = base_type::size(); first != last && base_type::free_list() != sz; ++first) {
1119 }
1120
1121 for(; first != last; ++first) {
1122 *first = *base_type::try_emplace(entity_at(base_type::free_list()), true);
1123 }
1124 }
1125
1133 template<typename It>
1134 [[deprecated("use sort_as instead")]] size_type pack(It first, It last) {
1135 base_type::sort_as(first, last);
1136 return static_cast<size_type>(std::distance(first, last));
1137 }
1138
1143 [[deprecated("use free_list() instead")]] [[nodiscard]] size_type in_use() const noexcept {
1144 return base_type::free_list();
1145 }
1146
1151 [[deprecated("use free_list(len) instead")]] void in_use(const size_type len) noexcept {
1153 }
1154
1162 [[nodiscard]] iterable each() noexcept {
1163 return {internal::extended_storage_iterator{base_type::begin(0)}, internal::extended_storage_iterator{base_type::end(0)}};
1164 }
1165
1167 [[nodiscard]] const_iterable each() const noexcept {
1168 return {internal::extended_storage_iterator{base_type::cbegin(0)}, internal::extended_storage_iterator{base_type::cend(0)}};
1169 }
1170
1178 [[nodiscard]] reverse_iterable reach() noexcept {
1179 return {internal::extended_storage_iterator{base_type::rbegin()}, internal::extended_storage_iterator{base_type::rend(0)}};
1180 }
1181
1183 [[nodiscard]] const_reverse_iterable reach() const noexcept {
1184 return {internal::extended_storage_iterator{base_type::crbegin()}, internal::extended_storage_iterator{base_type::crend(0)}};
1185 }
1186};
1187
1188} // namespace entt
1189
1190#endif
Basic sparse set implementation.
void swap(basic_sparse_set &other)
Exchanges the contents with those of a given sparse set.
iterator begin() const noexcept
Returns an iterator to the beginning.
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
virtual basic_iterator try_emplace(const Entity entt, const bool force_back, const void *=nullptr)
Assigns an entity to a sparse set.
void swap_and_pop(const basic_iterator it)
Erases an entity from a sparse set.
iterator end() const noexcept
Returns an iterator to the end.
reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
pointer data() const noexcept
Direct access to the internal packed array.
basic_sparse_set & operator=(basic_sparse_set &&other) noexcept
Move assignment operator.
virtual void reserve(const size_type cap)
Increases the capacity of a sparse set.
size_type size() const noexcept
Returns the number of elements in a sparse set.
virtual void shrink_to_fit()
Requests the removal of unused capacity.
const_iterator find(const entity_type entt) const noexcept
Finds an entity.
virtual void pop(basic_iterator first, basic_iterator last)
Erases entities from a sparse set.
version_type current(const entity_type entt) const noexcept
Returns the contained version for an identifier.
bool contains(const entity_type entt) const noexcept
Checks if a sparse set contains an entity.
const_iterator cend() const noexcept
Returns an iterator to the end.
void in_place_pop(const basic_iterator it)
Erases an entity from a sparse set.
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the end.
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
const void * value(const entity_type entt) const noexcept
Returns the element assigned to an entity, if any.
reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
size_type free_list() const noexcept
Returns the head of the free list, if any.
internal::sparse_set_iterator< packed_container_type > basic_iterator
Random access iterator type.
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the beginning.
size_type index(const entity_type entt) const noexcept
Returns the position of an entity in a sparse set.
void sort_as(It first, It last)
Sort entities according to their order in a range.
typename traits_type::value_type entity_type
Underlying entity identifier.
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:1183
std::size_t size_type
Unsigned integer type.
Definition storage.hpp:982
Entity value_type
Type of the objects assigned to entities.
Definition storage.hpp:978
void get(const entity_type entt) const noexcept
Returns the object assigned to an entity, that is void.
Definition storage.hpp:1040
void insert(It first, It last)
Assigns each element in a range an identifier.
Definition storage.hpp:1116
Entity entity_type
Underlying entity identifier.
Definition storage.hpp:980
basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
Allocator-extended move constructor.
Definition storage.hpp:1018
entity_type emplace(const entity_type hint)
Creates a new identifier or recycles a destroyed one.
Definition storage.hpp:1078
underlying_iterator try_emplace(const Entity hint, const bool, const void *) override
Assigns an entity to a storage.
Definition storage.hpp:970
basic_storage & operator=(basic_storage &&other) noexcept
Move assignment operator.
Definition storage.hpp:1026
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:1178
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:1167
basic_storage(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition storage.hpp:1003
void in_use(const size_type len) noexcept
Sets the number of elements considered still in use.
Definition storage.hpp:1151
basic_storage(basic_storage &&other) noexcept
Move constructor.
Definition storage.hpp:1010
entity_type emplace()
Creates a new identifier or recycles a destroyed one.
Definition storage.hpp:1063
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:1162
size_type pack(It first, It last)
Makes all elements in a range contiguous.
Definition storage.hpp:1134
void patch(const entity_type entt, Func &&...func)
Updates a given identifier.
Definition storage.hpp:1104
size_type in_use() const noexcept
Returns the number of elements considered still in use.
Definition storage.hpp:1143
std::tuple get_as_tuple(const entity_type entt) const noexcept
Returns an empty tuple.
Definition storage.hpp:1054
void emplace(const entity_type entt, Args &&...)
Assigns an entity to a storage and constructs its object.
Definition storage.hpp:883
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:936
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition storage.hpp:835
void get(const entity_type entt) const noexcept
Returns the object assigned to an entity, that is void.
Definition storage.hpp:853
basic_storage(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition storage.hpp:807
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:925
void patch(const entity_type entt, Func &&...func)
Updates the instance assigned to a given entity in-place.
Definition storage.hpp:894
basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
Allocator-extended move constructor.
Definition storage.hpp:821
std::tuple get_as_tuple(const entity_type entt) const noexcept
Returns an empty tuple.
Definition storage.hpp:867
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:920
basic_storage & operator=(basic_storage &&other) noexcept=default
Move assignment operator.
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:941
Basic storage implementation.
Definition storage.hpp:229
iterator end() noexcept
Returns an iterator to the end.
Definition storage.hpp:573
~basic_storage() override
Default destructor.
Definition storage.hpp:456
basic_storage()
Default constructor.
Definition storage.hpp:425
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:725
const_reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition storage.hpp:589
const_iterator end() const noexcept
Returns an iterator to the end.
Definition storage.hpp:568
const_pointer raw() const noexcept
Direct access to the array of objects.
Definition storage.hpp:526
void pop_all() override
Erases all entities of a storage.
Definition storage.hpp:351
basic_storage(basic_storage &&other) noexcept
Move constructor.
Definition storage.hpp:440
const value_type & get(const entity_type entt) const noexcept
Returns the object assigned to an entity.
Definition storage.hpp:627
const_iterator cend() const noexcept
Returns an iterator to the end.
Definition storage.hpp:563
size_type capacity() const noexcept override
Returns the number of elements that a storage has currently allocated space for.
Definition storage.hpp:512
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition storage.hpp:488
typename alloc_traits::template rebind_traits< typename alloc_traits::const_pointer >::const_pointer const_pointer
Constant pointer type to contained elements.
Definition storage.hpp:406
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:746
reverse_iterator rbegin() noexcept
Returns a reverse iterator to the beginning.
Definition storage.hpp:594
internal::storage_iterator< container_type, traits_type::page_size > iterator
Random access iterator type.
Definition storage.hpp:408
Type value_type
Type of the objects assigned to entities.
Definition storage.hpp:394
const_iterator begin() const noexcept
Returns an iterator to the beginning.
Definition storage.hpp:548
reverse_iterator rend() noexcept
Returns a reverse iterator to the end.
Definition storage.hpp:613
basic_storage & operator=(basic_storage &&other) noexcept
Move assignment operator.
Definition storage.hpp:465
Entity entity_type
Underlying entity identifier.
Definition storage.hpp:398
const_reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
Definition storage.hpp:608
underlying_iterator try_emplace(const Entity entt, const bool force_back, const void *value) override
Assigns an entity to a storage.
Definition storage.hpp:374
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
Definition storage.hpp:542
std::reverse_iterator< const_iterator > const_reverse_iterator
Constant reverse iterator type.
Definition storage.hpp:414
value_type & patch(const entity_type entt, Func &&...func)
Updates the instance assigned to a given entity in-place.
Definition storage.hpp:681
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator type.
Definition storage.hpp:412
std::size_t size_type
Unsigned integer type.
Definition storage.hpp:400
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:703
void pop(underlying_iterator first, underlying_iterator last) override
Erases entities from a storage.
Definition storage.hpp:332
typename container_type::pointer pointer
Pointer type to contained elements.
Definition storage.hpp:404
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:757
pointer raw() noexcept
Direct access to the array of objects.
Definition storage.hpp:531
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:646
value_type & get(const entity_type entt) noexcept
Returns the object assigned to an entity.
Definition storage.hpp:632
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the end.
Definition storage.hpp:603
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition storage.hpp:762
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition storage.hpp:741
void reserve(const size_type cap) override
Increases the capacity of a storage.
Definition storage.hpp:500
basic_storage(const allocator_type &allocator)
Constructs an empty storage with a given allocator.
Definition storage.hpp:432
value_type & emplace(const entity_type entt, Args &&...args)
Assigns an entity to a storage and constructs its object.
Definition storage.hpp:663
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:641
void shrink_to_fit() override
Requests the removal of unused capacity.
Definition storage.hpp:517
void swap(basic_storage &other)
Exchanges the contents with those of a given storage.
Definition storage.hpp:478
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition storage.hpp:584
internal::storage_iterator< const container_type, traits_type::page_size > const_iterator
Constant random access iterator type.
Definition storage.hpp:410
basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
Allocator-extended move constructor.
Definition storage.hpp:449
iterator begin() noexcept
Returns an iterator to the beginning.
Definition storage.hpp:553
Allocator allocator_type
Allocator type.
Definition storage.hpp:402
EnTT default namespace.
Definition dense_map.hpp:21
constexpr null_t null
Compile-time constant for null entities.
Definition entity.hpp:363
constexpr tombstone_t tombstone
Compile-time constant for tombstone entities.
Definition entity.hpp:372
constexpr Type * uninitialized_construct_using_allocator(Type *value, const Allocator &allocator, Args &&...args)
Uses-allocator construction utility (waiting for C++20).
Definition memory.hpp:277
constexpr std::size_t fast_mod(const std::size_t value, const std::size_t mod) noexcept
Fast module utility function (powers of two only).
Definition memory.hpp:47
constexpr get_t< Type... > get
Variable template for lists of observed components.
Definition fwd.hpp:157
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:16
@ swap_only
Swap-only deletion policy.
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.
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:59
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:42
static constexpr std::size_t page_size
Page size, default is ENTT_PACKED_PAGE for non-empty types.
Definition component.hpp:51
static constexpr bool in_place_delete
Pointer stability, default is false.
Definition component.hpp:49
Utility class to create an iterable object from a pair of iterators.
Definition iterator.hpp:141