EnTT 3.12.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
27namespace internal {
28
29template<typename Container, std::size_t Size>
30class storage_iterator final {
31 friend storage_iterator<const Container, Size>;
32
33 using container_type = std::remove_const_t<Container>;
34 using alloc_traits = std::allocator_traits<typename container_type::allocator_type>;
35
36 using iterator_traits = std::iterator_traits<std::conditional_t<
37 std::is_const_v<Container>,
38 typename alloc_traits::template rebind_traits<typename std::pointer_traits<typename container_type::value_type>::element_type>::const_pointer,
39 typename alloc_traits::template rebind_traits<typename std::pointer_traits<typename container_type::value_type>::element_type>::pointer>>;
40
41public:
42 using value_type = typename iterator_traits::value_type;
43 using pointer = typename iterator_traits::pointer;
44 using reference = typename iterator_traits::reference;
45 using difference_type = typename iterator_traits::difference_type;
46 using iterator_category = std::random_access_iterator_tag;
47
48 constexpr storage_iterator() noexcept = default;
49
50 constexpr storage_iterator(Container *ref, const difference_type idx) noexcept
51 : payload{ref},
52 offset{idx} {}
53
54 template<bool Const = std::is_const_v<Container>, typename = std::enable_if_t<Const>>
55 constexpr storage_iterator(const storage_iterator<std::remove_const_t<Container>, Size> &other) noexcept
56 : storage_iterator{other.payload, other.offset} {}
57
58 constexpr storage_iterator &operator++() noexcept {
59 return --offset, *this;
60 }
61
62 constexpr storage_iterator operator++(int) noexcept {
63 storage_iterator orig = *this;
64 return ++(*this), orig;
65 }
66
67 constexpr storage_iterator &operator--() noexcept {
68 return ++offset, *this;
69 }
70
71 constexpr storage_iterator operator--(int) noexcept {
72 storage_iterator orig = *this;
73 return operator--(), orig;
74 }
75
76 constexpr storage_iterator &operator+=(const difference_type value) noexcept {
77 offset -= value;
78 return *this;
79 }
80
81 constexpr storage_iterator operator+(const difference_type value) const noexcept {
82 storage_iterator copy = *this;
83 return (copy += value);
84 }
85
86 constexpr storage_iterator &operator-=(const difference_type value) noexcept {
87 return (*this += -value);
88 }
89
90 constexpr storage_iterator operator-(const difference_type value) const noexcept {
91 return (*this + -value);
92 }
93
94 [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept {
95 const auto pos = index() - value;
96 return (*payload)[pos / Size][fast_mod(pos, Size)];
97 }
98
99 [[nodiscard]] constexpr pointer operator->() const noexcept {
100 const auto pos = index();
101 return (*payload)[pos / Size] + fast_mod(pos, Size);
102 }
103
104 [[nodiscard]] constexpr reference operator*() const noexcept {
105 return *operator->();
106 }
107
108 [[nodiscard]] constexpr difference_type index() const noexcept {
109 return offset - 1;
110 }
111
112private:
113 Container *payload;
114 difference_type offset;
115};
116
117template<typename Lhs, typename Rhs, std::size_t Size>
118[[nodiscard]] constexpr std::ptrdiff_t operator-(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
119 return rhs.index() - lhs.index();
120}
121
122template<typename Lhs, typename Rhs, std::size_t Size>
123[[nodiscard]] constexpr bool operator==(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
124 return lhs.index() == rhs.index();
125}
126
127template<typename Lhs, typename Rhs, std::size_t Size>
128[[nodiscard]] constexpr bool operator!=(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
129 return !(lhs == rhs);
130}
131
132template<typename Lhs, typename Rhs, std::size_t Size>
133[[nodiscard]] constexpr bool operator<(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
134 return lhs.index() > rhs.index();
135}
136
137template<typename Lhs, typename Rhs, std::size_t Size>
138[[nodiscard]] constexpr bool operator>(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
139 return rhs < lhs;
140}
141
142template<typename Lhs, typename Rhs, std::size_t Size>
143[[nodiscard]] constexpr bool operator<=(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
144 return !(lhs > rhs);
145}
146
147template<typename Lhs, typename Rhs, std::size_t Size>
148[[nodiscard]] constexpr bool operator>=(const storage_iterator<Lhs, Size> &lhs, const storage_iterator<Rhs, Size> &rhs) noexcept {
149 return !(lhs < rhs);
150}
151
152template<typename It, typename... Other>
153class extended_storage_iterator final {
154 template<typename Iter, typename... Args>
155 friend class extended_storage_iterator;
156
157public:
158 using iterator_type = It;
159 using difference_type = std::ptrdiff_t;
160 using value_type = decltype(std::tuple_cat(std::make_tuple(*std::declval<It>()), std::forward_as_tuple(*std::declval<Other>()...)));
161 using pointer = input_iterator_pointer<value_type>;
162 using reference = value_type;
163 using iterator_category = std::input_iterator_tag;
164
165 constexpr extended_storage_iterator()
166 : it{} {}
167
168 constexpr extended_storage_iterator(It base, Other... other)
169 : it{base, other...} {}
170
171 template<typename... Args, typename = std::enable_if_t<(!std::is_same_v<Other, Args> && ...) && (std::is_constructible_v<Other, Args> && ...)>>
172 constexpr extended_storage_iterator(const extended_storage_iterator<It, Args...> &other)
173 : it{other.it} {}
174
175 constexpr extended_storage_iterator &operator++() noexcept {
176 return ++std::get<It>(it), (++std::get<Other>(it), ...), *this;
177 }
178
179 constexpr extended_storage_iterator operator++(int) noexcept {
180 extended_storage_iterator orig = *this;
181 return ++(*this), orig;
182 }
183
184 [[nodiscard]] constexpr pointer operator->() const noexcept {
185 return operator*();
186 }
187
188 [[nodiscard]] constexpr reference operator*() const noexcept {
189 return {*std::get<It>(it), *std::get<Other>(it)...};
190 }
191
192 [[nodiscard]] constexpr iterator_type base() const noexcept {
193 return std::get<It>(it);
194 }
195
196 template<typename... Lhs, typename... Rhs>
197 friend constexpr bool operator==(const extended_storage_iterator<Lhs...> &, const extended_storage_iterator<Rhs...> &) noexcept;
198
199private:
200 std::tuple<It, Other...> it;
201};
202
203template<typename... Lhs, typename... Rhs>
204[[nodiscard]] constexpr bool operator==(const extended_storage_iterator<Lhs...> &lhs, const extended_storage_iterator<Rhs...> &rhs) noexcept {
205 return std::get<0>(lhs.it) == std::get<0>(rhs.it);
206}
207
208template<typename... Lhs, typename... Rhs>
209[[nodiscard]] constexpr bool operator!=(const extended_storage_iterator<Lhs...> &lhs, const extended_storage_iterator<Rhs...> &rhs) noexcept {
210 return !(lhs == rhs);
211}
212
213} // namespace internal
214
235template<typename Type, typename Entity, typename Allocator, typename>
236class basic_storage: public basic_sparse_set<Entity, typename std::allocator_traits<Allocator>::template rebind_alloc<Entity>> {
237 using alloc_traits = std::allocator_traits<Allocator>;
238 static_assert(std::is_same_v<typename alloc_traits::value_type, Type>, "Invalid value type");
239 using container_type = std::vector<typename alloc_traits::pointer, typename alloc_traits::template rebind_alloc<typename alloc_traits::pointer>>;
241 using underlying_iterator = typename underlying_type::basic_iterator;
242
243 static constexpr bool is_pinned_type_v = !(std::is_move_constructible_v<Type> && std::is_move_assignable_v<Type>);
244
245 [[nodiscard]] auto &element_at(const std::size_t pos) const {
246 return payload[pos / traits_type::page_size][fast_mod(pos, traits_type::page_size)];
247 }
248
249 auto assure_at_least(const std::size_t pos) {
250 const auto idx = pos / traits_type::page_size;
251
252 if(!(idx < payload.size())) {
253 auto curr = payload.size();
254 allocator_type allocator{get_allocator()};
255 payload.resize(idx + 1u, nullptr);
256
257 ENTT_TRY {
258 for(const auto last = payload.size(); curr < last; ++curr) {
259 payload[curr] = alloc_traits::allocate(allocator, traits_type::page_size);
260 }
261 }
262 ENTT_CATCH {
263 payload.resize(curr);
264 ENTT_THROW;
265 }
266 }
267
268 return payload[idx] + fast_mod(pos, traits_type::page_size);
269 }
270
271 template<typename... Args>
272 auto emplace_element(const Entity entt, const bool force_back, Args &&...args) {
273 const auto it = base_type::try_emplace(entt, force_back);
274
275 ENTT_TRY {
276 auto elem = assure_at_least(static_cast<size_type>(it.index()));
277 entt::uninitialized_construct_using_allocator(to_address(elem), get_allocator(), std::forward<Args>(args)...);
278 }
279 ENTT_CATCH {
280 base_type::pop(it, it + 1u);
281 ENTT_THROW;
282 }
283
284 return it;
285 }
286
287 void shrink_to_size(const std::size_t sz) {
288 const auto from = (sz + traits_type::page_size - 1u) / traits_type::page_size;
289 allocator_type allocator{get_allocator()};
290
291 for(auto pos = sz, length = base_type::size(); pos < length; ++pos) {
292 if constexpr(traits_type::in_place_delete) {
293 if(base_type::at(pos) != tombstone) {
294 alloc_traits::destroy(allocator, std::addressof(element_at(pos)));
295 }
296 } else {
297 alloc_traits::destroy(allocator, std::addressof(element_at(pos)));
298 }
299 }
300
301 for(auto pos = from, last = payload.size(); pos < last; ++pos) {
302 alloc_traits::deallocate(allocator, payload[pos], traits_type::page_size);
303 }
304
305 payload.resize(from);
306 }
307
308private:
309 const void *get_at(const std::size_t pos) const final {
310 return std::addressof(element_at(pos));
311 }
312
313 void swap_or_move([[maybe_unused]] const std::size_t from, [[maybe_unused]] const std::size_t to) override {
314 // use a runtime value to avoid compile-time suppression that drives the code coverage tool crazy
315 ENTT_ASSERT((from + 1u) && !is_pinned_type_v, "Pinned type");
316
317 if constexpr(!is_pinned_type_v) {
318 auto &elem = element_at(from);
319
320 if constexpr(traits_type::in_place_delete) {
321 if(base_type::operator[](to) == tombstone) {
322 allocator_type allocator{get_allocator()};
323 entt::uninitialized_construct_using_allocator(to_address(assure_at_least(to)), allocator, std::move(elem));
324 alloc_traits::destroy(allocator, std::addressof(elem));
325 return;
326 }
327 }
328
329 using std::swap;
330 swap(elem, element_at(to));
331 }
332 }
333
334protected:
340 void pop(underlying_iterator first, underlying_iterator last) override {
341 for(allocator_type allocator{get_allocator()}; first != last; ++first) {
342 // cannot use first.index() because it would break with cross iterators
343 auto &elem = element_at(base_type::index(*first));
344
345 if constexpr(traits_type::in_place_delete) {
347 alloc_traits::destroy(allocator, std::addressof(elem));
348 } else {
349 auto &other = element_at(base_type::size() - 1u);
350 // destroying on exit allows reentrant destructors
351 [[maybe_unused]] auto unused = std::exchange(elem, std::move(other));
352 alloc_traits::destroy(allocator, std::addressof(other));
354 }
355 }
356 }
357
359 void pop_all() override {
360 allocator_type allocator{get_allocator()};
361
362 for(auto first = base_type::begin(); !(first.index() < 0); ++first) {
363 if constexpr(traits_type::in_place_delete) {
364 if(*first != tombstone) {
366 alloc_traits::destroy(allocator, std::addressof(element_at(static_cast<size_type>(first.index()))));
367 }
368 } else {
370 alloc_traits::destroy(allocator, std::addressof(element_at(static_cast<size_type>(first.index()))));
371 }
372 }
373 }
374
382 underlying_iterator try_emplace([[maybe_unused]] const Entity entt, [[maybe_unused]] const bool force_back, const void *value) override {
383 if(value) {
384 if constexpr(std::is_copy_constructible_v<value_type>) {
385 return emplace_element(entt, force_back, *static_cast<const value_type *>(value));
386 } else {
387 return base_type::end();
388 }
389 } else {
390 if constexpr(std::is_default_constructible_v<value_type>) {
391 return emplace_element(entt, force_back);
392 } else {
393 return base_type::end();
394 }
395 }
396 }
397
398public:
402 using value_type = Type;
406 using entity_type = Entity;
408 using size_type = std::size_t;
410 using allocator_type = Allocator;
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>;
431
435
440 explicit basic_storage(const allocator_type &allocator)
441 : base_type{type_id<value_type>(), deletion_policy{traits_type::in_place_delete}, allocator},
442 payload{allocator} {}
443
448 basic_storage(basic_storage &&other) noexcept
449 : base_type{std::move(other)},
450 payload{std::move(other.payload)} {}
451
457 basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
458 : base_type{std::move(other), allocator},
459 payload{std::move(other.payload), allocator} {
460 ENTT_ASSERT(alloc_traits::is_always_equal::value || payload.get_allocator() == other.payload.get_allocator(), "Copying a storage is not allowed");
461 }
462
464 ~basic_storage() override {
465 shrink_to_size(0u);
466 }
467
474 ENTT_ASSERT(alloc_traits::is_always_equal::value || payload.get_allocator() == other.payload.get_allocator(), "Copying a storage is not allowed");
475
476 shrink_to_size(0u);
477 base_type::operator=(std::move(other));
478 payload = std::move(other.payload);
479 return *this;
480 }
481
486 void swap(basic_storage &other) {
487 using std::swap;
488 base_type::swap(other);
489 swap(payload, other.payload);
490 }
491
496 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
497 return payload.get_allocator();
498 }
499
508 void reserve(const size_type cap) override {
509 if(cap != 0u) {
511 assure_at_least(cap - 1u);
512 }
513 }
514
520 [[nodiscard]] size_type capacity() const noexcept override {
521 return payload.size() * traits_type::page_size;
522 }
523
525 void shrink_to_fit() override {
527 shrink_to_size(base_type::size());
528 }
529
534 [[nodiscard]] const_pointer raw() const noexcept {
535 return payload.data();
536 }
537
539 [[nodiscard]] pointer raw() noexcept {
540 return payload.data();
541 }
542
550 [[nodiscard]] const_iterator cbegin() const noexcept {
551 const auto pos = static_cast<typename iterator::difference_type>(base_type::size());
552 return const_iterator{&payload, pos};
553 }
554
556 [[nodiscard]] const_iterator begin() const noexcept {
557 return cbegin();
558 }
559
561 [[nodiscard]] iterator begin() noexcept {
562 const auto pos = static_cast<typename iterator::difference_type>(base_type::size());
563 return iterator{&payload, pos};
564 }
565
571 [[nodiscard]] const_iterator cend() const noexcept {
572 return const_iterator{&payload, {}};
573 }
574
576 [[nodiscard]] const_iterator end() const noexcept {
577 return cend();
578 }
579
581 [[nodiscard]] iterator end() noexcept {
582 return iterator{&payload, {}};
583 }
584
592 [[nodiscard]] const_reverse_iterator crbegin() const noexcept {
593 return std::make_reverse_iterator(cend());
594 }
595
597 [[nodiscard]] const_reverse_iterator rbegin() const noexcept {
598 return crbegin();
599 }
600
602 [[nodiscard]] reverse_iterator rbegin() noexcept {
603 return std::make_reverse_iterator(end());
604 }
605
611 [[nodiscard]] const_reverse_iterator crend() const noexcept {
612 return std::make_reverse_iterator(cbegin());
613 }
614
616 [[nodiscard]] const_reverse_iterator rend() const noexcept {
617 return crend();
618 }
619
621 [[nodiscard]] reverse_iterator rend() noexcept {
622 return std::make_reverse_iterator(begin());
623 }
624
635 [[nodiscard]] const value_type &get(const entity_type entt) const noexcept {
636 return element_at(base_type::index(entt));
637 }
638
640 [[nodiscard]] value_type &get(const entity_type entt) noexcept {
641 return const_cast<value_type &>(std::as_const(*this).get(entt));
642 }
643
649 [[nodiscard]] std::tuple<const value_type &> get_as_tuple(const entity_type entt) const noexcept {
650 return std::forward_as_tuple(get(entt));
651 }
652
654 [[nodiscard]] std::tuple<value_type &> get_as_tuple(const entity_type entt) noexcept {
655 return std::forward_as_tuple(get(entt));
656 }
657
670 template<typename... Args>
671 value_type &emplace(const entity_type entt, Args &&...args) {
672 if constexpr(std::is_aggregate_v<value_type> && (sizeof...(Args) != 0u || !std::is_default_constructible_v<value_type>)) {
673 const auto it = emplace_element(entt, false, Type{std::forward<Args>(args)...});
674 return element_at(static_cast<size_type>(it.index()));
675 } else {
676 const auto it = emplace_element(entt, false, std::forward<Args>(args)...);
677 return element_at(static_cast<size_type>(it.index()));
678 }
679 }
680
688 template<typename... Func>
689 value_type &patch(const entity_type entt, Func &&...func) {
690 const auto idx = base_type::index(entt);
691 auto &elem = element_at(idx);
692 (std::forward<Func>(func)(elem), ...);
693 return elem;
694 }
695
710 template<typename It>
711 iterator insert(It first, It last, const value_type &value = {}) {
712 for(; first != last; ++first) {
713 emplace_element(*first, true, value);
714 }
715
716 return begin();
717 }
718
732 template<typename EIt, typename CIt, typename = std::enable_if_t<std::is_same_v<typename std::iterator_traits<CIt>::value_type, value_type>>>
733 iterator insert(EIt first, EIt last, CIt from) {
734 for(; first != last; ++first, ++from) {
735 emplace_element(*first, true, *from);
736 }
737
738 return begin();
739 }
740
749 [[nodiscard]] iterable each() noexcept {
750 return {internal::extended_storage_iterator{base_type::begin(), begin()}, internal::extended_storage_iterator{base_type::end(), end()}};
751 }
752
754 [[nodiscard]] const_iterable each() const noexcept {
755 return {internal::extended_storage_iterator{base_type::cbegin(), cbegin()}, internal::extended_storage_iterator{base_type::cend(), cend()}};
756 }
757
765 [[nodiscard]] reverse_iterable reach() noexcept {
766 return {internal::extended_storage_iterator{base_type::rbegin(), rbegin()}, internal::extended_storage_iterator{base_type::rend(), rend()}};
767 }
768
770 [[nodiscard]] const_reverse_iterable reach() const noexcept {
771 return {internal::extended_storage_iterator{base_type::crbegin(), crbegin()}, internal::extended_storage_iterator{base_type::crend(), crend()}};
772 }
773
774private:
775 container_type payload;
776};
777
779template<typename Type, typename Entity, typename Allocator>
780class basic_storage<Type, Entity, Allocator, std::enable_if_t<component_traits<Type>::page_size == 0u>>
781 : public basic_sparse_set<Entity, typename std::allocator_traits<Allocator>::template rebind_alloc<Entity>> {
782 using alloc_traits = std::allocator_traits<Allocator>;
783 static_assert(std::is_same_v<typename alloc_traits::value_type, Type>, "Invalid value type");
784
785public:
789 using value_type = Type;
793 using entity_type = Entity;
795 using size_type = std::size_t;
797 using allocator_type = Allocator;
806
810
815 explicit basic_storage(const allocator_type &allocator)
816 : base_type{type_id<value_type>(), deletion_policy{traits_type::in_place_delete}, allocator} {}
817
822 basic_storage(basic_storage &&other) noexcept = default;
823
829 basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
830 : base_type{std::move(other), allocator} {}
831
837 basic_storage &operator=(basic_storage &&other) noexcept = default;
838
843 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
845 }
846
856 void get([[maybe_unused]] const entity_type entt) const noexcept {
857 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
858 }
859
870 [[nodiscard]] std::tuple<> get_as_tuple([[maybe_unused]] const entity_type entt) const noexcept {
871 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
872 return std::tuple{};
873 }
874
885 template<typename... Args>
886 void emplace(const entity_type entt, Args &&...) {
888 }
889
896 template<typename... Func>
897 void patch([[maybe_unused]] const entity_type entt, Func &&...func) {
898 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
899 (std::forward<Func>(func)(), ...);
900 }
901
909 template<typename It, typename... Args>
910 void insert(It first, It last, Args &&...) {
911 for(; first != last; ++first) {
912 base_type::try_emplace(*first, true);
913 }
914 }
915
923 [[nodiscard]] iterable each() noexcept {
924 return {internal::extended_storage_iterator{base_type::begin()}, internal::extended_storage_iterator{base_type::end()}};
925 }
926
928 [[nodiscard]] const_iterable each() const noexcept {
929 return {internal::extended_storage_iterator{base_type::cbegin()}, internal::extended_storage_iterator{base_type::cend()}};
930 }
931
939 [[nodiscard]] reverse_iterable reach() noexcept {
940 return {internal::extended_storage_iterator{base_type::rbegin()}, internal::extended_storage_iterator{base_type::rend()}};
941 }
942
944 [[nodiscard]] const_reverse_iterable reach() const noexcept {
945 return {internal::extended_storage_iterator{base_type::crbegin()}, internal::extended_storage_iterator{base_type::crend()}};
946 }
947};
948
954template<typename Entity, typename Allocator>
955class basic_storage<Entity, Entity, Allocator>
956 : public basic_sparse_set<Entity, Allocator> {
957 using alloc_traits = std::allocator_traits<Allocator>;
958 static_assert(std::is_same_v<typename alloc_traits::value_type, Entity>, "Invalid value type");
960 using underlying_iterator = typename underlying_type::basic_iterator;
962
963 auto entity_at(const std::size_t pos) const noexcept {
964 ENTT_ASSERT(pos < local_traits_type::to_entity(null), "Invalid element");
965 return local_traits_type::combine(static_cast<typename local_traits_type::entity_type>(pos), {});
966 }
967
968private:
969 void swap_or_move([[maybe_unused]] const std::size_t lhs, [[maybe_unused]] const std::size_t rhs) override {
970 ENTT_ASSERT(((lhs < length) + (rhs < length)) != 1u, "Cross swapping is not supported");
971 }
972
973protected:
979 void pop(underlying_iterator first, underlying_iterator last) override {
980 for(; first != last; ++first) {
981 if(const auto pos = base_type::index(*first); pos < length) {
982 base_type::bump(local_traits_type::next(*first));
983
984 if(pos != --length) {
985 base_type::swap_at(pos, length);
986 }
987 }
988 }
989 }
990
992 void pop_all() override {
993 length = 0u;
995 }
996
1002 underlying_iterator try_emplace(const Entity hint, const bool, const void *) override {
1003 return base_type::find(emplace(hint));
1004 }
1005
1006public:
1010 using value_type = Entity;
1014 using entity_type = Entity;
1016 using size_type = std::size_t;
1018 using allocator_type = Allocator;
1027
1031 }
1032
1037 explicit basic_storage(const allocator_type &allocator)
1039 length{} {}
1040
1046 : base_type{std::move(other)},
1047 length{std::exchange(other.length, size_type{})} {}
1048
1054 basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
1055 : base_type{std::move(other), allocator},
1056 length{std::exchange(other.length, size_type{})} {}
1057
1064 base_type::operator=(std::move(other));
1065 length = std::exchange(other.length, size_type{});
1066 return *this;
1067 }
1068
1078 void get([[maybe_unused]] const entity_type entt) const noexcept {
1079 ENTT_ASSERT(base_type::index(entt) < length, "The requested entity is not a live one");
1080 }
1081
1092 [[nodiscard]] std::tuple<> get_as_tuple([[maybe_unused]] const entity_type entt) const noexcept {
1093 ENTT_ASSERT(base_type::index(entt) < length, "The requested entity is not a live one");
1094 return std::tuple{};
1095 }
1096
1101 void swap(basic_storage &other) {
1102 using std::swap;
1103 base_type::swap(other);
1104 swap(length, other.length);
1105 }
1106
1112 if(length == base_type::size()) {
1113 return *base_type::try_emplace(entity_at(length++), true);
1114 }
1115
1116 return base_type::operator[](length++);
1117 }
1118
1129 if(hint == null || hint == tombstone) {
1130 return emplace();
1131 } else if(const auto curr = local_traits_type::construct(local_traits_type::to_entity(hint), base_type::current(hint)); curr == tombstone) {
1132 const auto pos = static_cast<size_type>(local_traits_type::to_entity(hint));
1133
1134 while(!(pos < base_type::size())) {
1135 base_type::try_emplace(entity_at(base_type::size()), true);
1136 }
1137
1138 base_type::swap_at(pos, length++);
1139 } else if(const auto idx = base_type::index(curr); idx < length) {
1140 return emplace();
1141 } else {
1142 base_type::swap_at(idx, length++);
1143 }
1144
1145 base_type::bump(hint);
1146
1147 return hint;
1148 }
1149
1156 template<typename... Func>
1157 void patch([[maybe_unused]] const entity_type entt, Func &&...func) {
1158 ENTT_ASSERT(base_type::contains(entt), "Storage does not contain entity");
1159 (std::forward<Func>(func)(), ...);
1160 }
1161
1168 template<typename It>
1169 void insert(It first, It last) {
1170 for(const auto sz = base_type::size(); first != last && length != sz; ++first, ++length) {
1171 *first = base_type::operator[](length);
1172 }
1173
1174 for(; first != last; ++first) {
1175 *first = *base_type::try_emplace(entity_at(length++), true);
1176 }
1177 }
1178
1186 template<typename It>
1187 size_type pack(It first, It last) {
1188 size_type len = length;
1189
1190 for(; first != last; ++first, --len) {
1191 const auto pos = base_type::index(*first);
1192 ENTT_ASSERT(pos < length, "Invalid element");
1193 base_type::swap_at(pos, static_cast<size_type>(len - 1u));
1194 }
1195
1196 return (length - len);
1197 }
1198
1203 [[nodiscard]] size_type in_use() const noexcept {
1204 return length;
1205 }
1206
1211 void in_use(const size_type len) noexcept {
1212 ENTT_ASSERT(!(len > base_type::size()), "Invalid length");
1213 length = len;
1214 }
1215
1223 [[nodiscard]] iterable each() noexcept {
1224 return {internal::extended_storage_iterator{base_type::end() - length}, internal::extended_storage_iterator{base_type::end()}};
1225 }
1226
1228 [[nodiscard]] const_iterable each() const noexcept {
1229 return {internal::extended_storage_iterator{base_type::cend() - length}, internal::extended_storage_iterator{base_type::cend()}};
1230 }
1231
1239 [[nodiscard]] reverse_iterable reach() noexcept {
1240 return {internal::extended_storage_iterator{base_type::rbegin()}, internal::extended_storage_iterator{base_type::rbegin() + length}};
1241 }
1242
1244 [[nodiscard]] const_reverse_iterable reach() const noexcept {
1245 return {internal::extended_storage_iterator{base_type::crbegin()}, internal::extended_storage_iterator{base_type::crbegin() + length}};
1246 }
1247
1248private:
1249 size_type length;
1250};
1251
1252} // namespace entt
1253
1254#endif
typename Traits::entity_type entity_type
Underlying entity type.
Definition: entity.hpp:84
Basic sparse set implementation.
Definition: sparse_set.hpp:166
void swap(basic_sparse_set &other)
Exchanges the contents with those of a given sparse set.
Definition: sparse_set.hpp:435
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
Definition: sparse_set.hpp:552
virtual basic_iterator try_emplace(const Entity entt, const bool force_back, const void *=nullptr)
Assigns an entity to a sparse set.
Definition: sparse_set.hpp:314
virtual void pop_all()
Erases all entities of a sparse set.
Definition: sparse_set.hpp:292
void swap_and_pop(const basic_iterator it)
Erases an entity from a sparse set.
Definition: sparse_set.hpp:250
iterator end() const noexcept
Returns an iterator to the end.
Definition: sparse_set.hpp:561
const_reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition: sparse_set.hpp:579
reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
Definition: sparse_set.hpp:593
basic_sparse_set & operator=(basic_sparse_set &&other) noexcept
Move assignment operator.
Definition: sparse_set.hpp:419
virtual void reserve(const size_type cap)
Increases the capacity of a sparse set.
Definition: sparse_set.hpp:468
size_type size() const noexcept
Returns the number of elements in a sparse set.
Definition: sparse_set.hpp:510
version_type bump(const entity_type entt)
Bump the version number of an entity.
Definition: sparse_set.hpp:737
virtual void shrink_to_fit()
Requests the removal of unused capacity.
Definition: sparse_set.hpp:482
virtual void pop(basic_iterator first, basic_iterator last)
Erases entities from a sparse set.
Definition: sparse_set.hpp:279
version_type current(const entity_type entt) const noexcept
Returns the contained version for an identifier.
Definition: sparse_set.hpp:630
bool contains(const entity_type entt) const noexcept
Checks if a sparse set contains an entity.
Definition: sparse_set.hpp:617
const_iterator cend() const noexcept
Returns an iterator to the end.
Definition: sparse_set.hpp:566
void in_place_pop(const basic_iterator it)
Erases an entity from a sparse set.
Definition: sparse_set.hpp:267
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the end.
Definition: sparse_set.hpp:598
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition: sparse_set.hpp:448
const void * value(const entity_type entt) const noexcept
Returns the element assigned to an entity, if any.
Definition: sparse_set.hpp:680
entity_type operator[](const size_type pos) const noexcept
Returns the entity at specified location, without bounds checking.
Definition: sparse_set.hpp:665
internal::sparse_set_iterator< packed_container_type > basic_iterator
Random access iterator type.
Definition: sparse_set.hpp:228
entity_type at(const size_type pos) const noexcept
Returns the entity at specified location, with bounds checking.
Definition: sparse_set.hpp:656
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition: sparse_set.hpp:584
size_type index(const entity_type entt) const noexcept
Returns the position of an entity in a sparse set.
Definition: sparse_set.hpp:646
void swap_at(const std::size_t lhs, const std::size_t rhs)
Swaps two items at specific locations.
Definition: sparse_set.hpp:235
const_iterator begin() const noexcept
Returns an iterator to the beginning.
Definition: sparse_set.hpp:546
iterator find(const entity_type entt) const noexcept
Finds an entity.
Definition: sparse_set.hpp:608
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition: storage.hpp:1244
std::size_t size_type
Unsigned integer type.
Definition: storage.hpp:1016
void swap(basic_storage &other)
Exchanges the contents with those of a given storage.
Definition: storage.hpp:1101
Entity value_type
Type of the objects assigned to entities.
Definition: storage.hpp:1010
void get(const entity_type entt) const noexcept
Returns the object assigned to an entity, that is void.
Definition: storage.hpp:1078
void insert(It first, It last)
Assigns each element in a range an identifier.
Definition: storage.hpp:1169
Entity entity_type
Underlying entity identifier.
Definition: storage.hpp:1014
basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
Allocator-extended move constructor.
Definition: storage.hpp:1054
void pop_all() override
Erases all entities of a sparse set.
Definition: storage.hpp:992
entity_type emplace(const entity_type hint)
Creates a new identifier or recycles a destroyed one.
Definition: storage.hpp:1128
underlying_iterator try_emplace(const Entity hint, const bool, const void *) override
Assigns an entity to a storage.
Definition: storage.hpp:1002
basic_storage & operator=(basic_storage &&other) noexcept
Move assignment operator.
Definition: storage.hpp:1063
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition: storage.hpp:1239
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition: storage.hpp:1228
void pop(underlying_iterator first, underlying_iterator last) override
Erases entities from a storage.
Definition: storage.hpp:979
basic_storage(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition: storage.hpp:1037
void in_use(const size_type len) noexcept
Sets the number of elements considered still in use.
Definition: storage.hpp:1211
basic_storage(basic_storage &&other) noexcept
Move constructor.
Definition: storage.hpp:1045
entity_type emplace()
Creates a new identifier or recycles a destroyed one.
Definition: storage.hpp:1111
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition: storage.hpp:1223
size_type pack(It first, It last)
Makes all elements in a range contiguous.
Definition: storage.hpp:1187
void patch(const entity_type entt, Func &&...func)
Updates a given identifier.
Definition: storage.hpp:1157
size_type in_use() const noexcept
Returns the number of elements considered still in use.
Definition: storage.hpp:1203
std::tuple get_as_tuple(const entity_type entt) const noexcept
Returns an empty tuple.
Definition: storage.hpp:1092
void emplace(const entity_type entt, Args &&...)
Assigns an entity to a storage and constructs its object.
Definition: storage.hpp:886
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition: storage.hpp:939
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition: storage.hpp:843
void get(const entity_type entt) const noexcept
Returns the object assigned to an entity, that is void.
Definition: storage.hpp:856
basic_storage(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition: storage.hpp:815
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition: storage.hpp:928
void patch(const entity_type entt, Func &&...func)
Updates the instance assigned to a given entity in-place.
Definition: storage.hpp:897
basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
Allocator-extended move constructor.
Definition: storage.hpp:829
std::tuple get_as_tuple(const entity_type entt) const noexcept
Returns an empty tuple.
Definition: storage.hpp:870
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition: storage.hpp:923
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:944
Basic storage implementation.
Definition: storage.hpp:236
iterator end() noexcept
Returns an iterator to the end.
Definition: storage.hpp:581
~basic_storage() override
Default destructor.
Definition: storage.hpp:464
basic_storage()
Default constructor.
Definition: storage.hpp:433
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:733
const_reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition: storage.hpp:597
const_iterator end() const noexcept
Returns an iterator to the end.
Definition: storage.hpp:576
const_pointer raw() const noexcept
Direct access to the array of objects.
Definition: storage.hpp:534
void pop_all() override
Erases all entities of a storage.
Definition: storage.hpp:359
basic_storage(basic_storage &&other) noexcept
Move constructor.
Definition: storage.hpp:448
const value_type & get(const entity_type entt) const noexcept
Returns the object assigned to an entity.
Definition: storage.hpp:635
const_iterator cend() const noexcept
Returns an iterator to the end.
Definition: storage.hpp:571
size_type capacity() const noexcept override
Returns the number of elements that a storage has currently allocated space for.
Definition: storage.hpp:520
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition: storage.hpp:496
typename alloc_traits::template rebind_traits< typename alloc_traits::const_pointer >::const_pointer const_pointer
Constant pointer type to contained elements.
Definition: storage.hpp:414
const_iterable each() const noexcept
Returns an iterable object to use to visit a storage.
Definition: storage.hpp:754
reverse_iterator rbegin() noexcept
Returns a reverse iterator to the beginning.
Definition: storage.hpp:602
internal::storage_iterator< container_type, traits_type::page_size > iterator
Random access iterator type.
Definition: storage.hpp:416
Type value_type
Type of the objects assigned to entities.
Definition: storage.hpp:402
const_iterator begin() const noexcept
Returns an iterator to the beginning.
Definition: storage.hpp:556
reverse_iterator rend() noexcept
Returns a reverse iterator to the end.
Definition: storage.hpp:621
basic_storage & operator=(basic_storage &&other) noexcept
Move assignment operator.
Definition: storage.hpp:473
Entity entity_type
Underlying entity identifier.
Definition: storage.hpp:406
const_reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
Definition: storage.hpp:616
underlying_iterator try_emplace(const Entity entt, const bool force_back, const void *value) override
Assigns an entity to a storage.
Definition: storage.hpp:382
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
Definition: storage.hpp:550
std::reverse_iterator< const_iterator > const_reverse_iterator
Constant reverse iterator type.
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:689
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator type.
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:711
void pop(underlying_iterator first, underlying_iterator last) override
Erases entities from a storage.
Definition: storage.hpp:340
typename container_type::pointer pointer
Pointer type to contained elements.
Definition: storage.hpp:412
reverse_iterable reach() noexcept
Returns a reverse iterable object to use to visit a storage.
Definition: storage.hpp:765
pointer raw() noexcept
Direct access to the array of objects.
Definition: storage.hpp:539
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:654
value_type & get(const entity_type entt) noexcept
Returns the object assigned to an entity.
Definition: storage.hpp:640
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the end.
Definition: storage.hpp:611
const_reverse_iterable reach() const noexcept
Returns a reverse iterable object to use to visit a storage.
Definition: storage.hpp:770
iterable each() noexcept
Returns an iterable object to use to visit a storage.
Definition: storage.hpp:749
void reserve(const size_type cap) override
Increases the capacity of a storage.
Definition: storage.hpp:508
basic_storage(const allocator_type &allocator)
Constructs an empty storage with a given allocator.
Definition: storage.hpp:440
value_type & emplace(const entity_type entt, Args &&...args)
Assigns an entity to a storage and constructs its object.
Definition: storage.hpp:671
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:649
void shrink_to_fit() override
Requests the removal of unused capacity.
Definition: storage.hpp:525
void swap(basic_storage &other)
Exchanges the contents with those of a given storage.
Definition: storage.hpp:486
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition: storage.hpp:592
internal::storage_iterator< const container_type, traits_type::page_size > const_iterator
Constant random access iterator type.
Definition: storage.hpp:418
basic_storage(basic_storage &&other, const allocator_type &allocator) noexcept
Allocator-extended move constructor.
Definition: storage.hpp:457
iterator begin() noexcept
Returns an iterator to the beginning.
Definition: storage.hpp:561
Allocator allocator_type
Allocator type.
Definition: storage.hpp:410
EnTT default namespace.
Definition: dense_map.hpp:21
constexpr null_t null
Compile-time constant for null entities.
Definition: entity.hpp:366
constexpr tombstone_t tombstone
Compile-time constant for tombstone entities.
Definition: entity.hpp:375
constexpr Type * uninitialized_construct_using_allocator(Type *value, const Allocator &allocator, Args &&...args)
Uses-allocator construction utility (waiting for C++20).
Definition: memory.hpp:283
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:45
constexpr get_t< Type... > get
Variable template for lists of observed components.
Definition: fwd.hpp:132
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_and_pop
Swap-and-pop 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.
Definition: type_info.hpp:257
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:57
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:50
static constexpr std::size_t page_size
Page size, default is ENTT_PACKED_PAGE for non-empty types.
Definition: component.hpp:59
static constexpr bool in_place_delete
Pointer stability, default is false.
Definition: component.hpp:57
Entity traits.
Definition: entity.hpp:165
Utility class to create an iterable object from a pair of iterators.
Definition: iterator.hpp:141