EnTT  3.6.0
organizer.hpp
1 #ifndef ENTT_ENTITY_ORGANIZER_HPP
2 #define ENTT_ENTITY_ORGANIZER_HPP
3 
4 
5 #include <cstddef>
6 #include <algorithm>
7 #include <type_traits>
8 #include <unordered_map>
9 #include <utility>
10 #include <vector>
11 #include "../core/type_info.hpp"
12 #include "../core/type_traits.hpp"
13 #include "fwd.hpp"
14 #include "helper.hpp"
15 
16 
17 namespace entt {
18 
19 
26 namespace internal {
27 
28 
29 template<typename>
30 struct is_view: std::false_type {};
31 
32 template<typename Entity, typename... Exclude, typename... Component>
33 struct is_view<basic_view<Entity, exclude_t<Exclude...>, Component...>>: std::true_type {};
34 
35 template<typename Type>
36 inline constexpr bool is_view_v = is_view<Type>::value;
37 
38 
39 template<typename Type, typename Override>
40 struct unpack_type {
41  using ro = std::conditional_t<
42  type_list_contains_v<Override, std::add_const_t<Type>> || (std::is_const_v<Type> && !type_list_contains_v<Override, std::remove_const_t<Type>>),
43  type_list<std::remove_const_t<Type>>,
44  type_list<>
45  >;
46 
47  using rw = std::conditional_t<
48  type_list_contains_v<Override, std::remove_const_t<Type>> || (!std::is_const_v<Type> && !type_list_contains_v<Override, std::add_const_t<Type>>),
49  type_list<Type>,
50  type_list<>
51  >;
52 };
53 
54 template<typename Entity, typename... Override>
55 struct unpack_type<basic_registry<Entity>, type_list<Override...>> {
56  using ro = type_list<>;
57  using rw = type_list<>;
58 };
59 
60 template<typename Entity, typename... Override>
61 struct unpack_type<const basic_registry<Entity>, type_list<Override...>>
62  : unpack_type<basic_registry<Entity>, type_list<Override...>>
63 {};
64 
65 template<typename Entity, typename... Exclude, typename... Component, typename... Override>
66 struct unpack_type<basic_view<Entity, exclude_t<Exclude...>, Component...>, type_list<Override...>> {
67  using ro = type_list_cat_t<type_list<Exclude...>, typename unpack_type<Component, type_list<Override...>>::ro...>;
68  using rw = type_list_cat_t<typename unpack_type<Component, type_list<Override...>>::rw...>;
69 };
70 
71 template<typename Entity, typename... Exclude, typename... Component, typename... Override>
72 struct unpack_type<const basic_view<Entity, exclude_t<Exclude...>, Component...>, type_list<Override...>>
73  : unpack_type<basic_view<Entity, exclude_t<Exclude...>, Component...>, type_list<Override...>>
74 {};
75 
76 
77 template<typename, typename>
78 struct resource;
79 
80 template<typename... Args, typename... Req>
81 struct resource<type_list<Args...>, type_list<Req...>> {
82  using args = type_list<std::remove_const_t<Args>...>;
83  using ro = type_list_cat_t<typename unpack_type<Args, type_list<Req...>>::ro..., typename unpack_type<Req, type_list<>>::ro...>;
84  using rw = type_list_cat_t<typename unpack_type<Args, type_list<Req...>>::rw..., typename unpack_type<Req, type_list<>>::rw...>;
85 };
86 
87 
88 template<typename... Req, typename Ret, typename... Args>
89 resource<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> free_function_to_resource(Ret(*)(Args...));
90 
91 template<typename... Req, typename Ret, typename Type, typename... Args>
92 resource<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> constrained_function_to_resource(Ret(*)(Type &, Args...));
93 
94 template<typename... Req, typename Ret, typename Class, typename... Args>
95 resource<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> constrained_function_to_resource(Ret(Class:: *)(Args...));
96 
97 template<typename... Req, typename Ret, typename Class, typename... Args>
98 resource<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> constrained_function_to_resource(Ret(Class:: *)(Args...) const);
99 
100 template<typename... Req>
101 resource<type_list<>, type_list<Req...>> to_resource();
102 
103 
104 }
105 
106 
124 template<typename Entity>
125 class basic_organizer final {
126  using callback_type = void(const void *, entt::basic_registry<Entity> &);
127  using prepare_type = void(entt::basic_registry<Entity> &);
128  using dependency_type = std::size_t(const bool, type_info *, const std::size_t);
129 
130  struct vertex_data final {
131  std::size_t ro_count{};
132  std::size_t rw_count{};
133  const char *name{};
134  const void *payload{};
135  callback_type *callback{};
136  dependency_type *dependency;
137  prepare_type *prepare{};
138  type_info info{};
139  };
140 
141  template<typename Type>
142  [[nodiscard]] static decltype(auto) extract(basic_registry<Entity> &reg) {
143  if constexpr(std::is_same_v<Type, basic_registry<Entity>>) {
144  return reg;
145  } else if constexpr(internal::is_view_v<Type>) {
146  return as_view{reg};
147  } else {
148  return reg.template ctx_or_set<std::remove_reference_t<Type>>();
149  }
150  }
151 
152  template<typename... Args>
153  [[nodiscard]] static auto to_args(basic_registry<Entity> &reg, type_list<Args...>) {
154  return std::tuple<decltype(extract<Args>(reg))...>(extract<Args>(reg)...);
155  }
156 
157  template<typename... Type>
158  static std::size_t fill_dependencies(type_list<Type...>, [[maybe_unused]] type_info *buffer, [[maybe_unused]] const std::size_t count) {
159  if constexpr(sizeof...(Type) == 0u) {
160  return {};
161  } else {
162  type_info info[sizeof...(Type)]{type_id<Type>()...};
163  const auto length = std::min(count, sizeof...(Type));
164  std::copy_n(info, length, buffer);
165  return length;
166  }
167  }
168 
169  template<typename... RO, typename... RW>
170  void track_dependencies(std::size_t index, const bool requires_registry, type_list<RO...>, type_list<RW...>) {
171  dependencies[type_hash<basic_registry<Entity>>::value()].emplace_back(index, requires_registry || (sizeof...(RO) + sizeof...(RW) == 0u));
172  (dependencies[type_hash<RO>::value()].emplace_back(index, false), ...);
173  (dependencies[type_hash<RW>::value()].emplace_back(index, true), ...);
174  }
175 
176  [[nodiscard]] std::vector<bool> adjacency_matrix() {
177  const auto length = vertices.size();
178  std::vector<bool> edges(length * length, false);
179 
180  // creates the ajacency matrix
181  for(const auto &deps: dependencies) {
182  const auto last = deps.second.cend();
183  auto it = deps.second.cbegin();
184 
185  while(it != last) {
186  if(it->second) {
187  // rw item
188  if(auto curr = it++; it != last) {
189  if(it->second) {
190  edges[curr->first * length + it->first] = true;
191  } else {
192  if(const auto next = std::find_if(it, last, [](const auto &elem) { return elem.second; }); next != last) {
193  for(; it != next; ++it) {
194  edges[curr->first * length + it->first] = true;
195  edges[it->first * length + next->first] = true;
196  }
197  } else {
198  for(; it != next; ++it) {
199  edges[curr->first * length + it->first] = true;
200  }
201  }
202  }
203  }
204  } else {
205  // ro item, possibly only on first iteration
206  if(const auto next = std::find_if(it, last, [](const auto &elem) { return elem.second; }); next != last) {
207  for(; it != next; ++it) {
208  edges[it->first * length + next->first] = true;
209  }
210  } else {
211  it = last;
212  }
213  }
214  }
215  }
216 
217  // computes the transitive closure
218  for(std::size_t vk{}; vk < length; ++vk) {
219  for(std::size_t vi{}; vi < length; ++vi) {
220  for(std::size_t vj{}; vj < length; ++vj) {
221  edges[vi * length + vj] = edges[vi * length + vj] || (edges[vi * length + vk] && edges[vk * length + vj]);
222  }
223  }
224  }
225 
226  // applies the transitive reduction
227  for(std::size_t vert{}; vert < length; ++vert) {
228  edges[vert * length + vert] = false;
229  }
230 
231  for(std::size_t vj{}; vj < length; ++vj) {
232  for(std::size_t vi{}; vi < length; ++vi) {
233  if(edges[vi * length + vj]) {
234  for(std::size_t vk{}; vk < length; ++vk) {
235  if(edges[vj * length + vk]) {
236  edges[vi * length + vk] = false;
237  }
238  }
239  }
240  }
241  }
242 
243  return edges;
244  }
245 
246 public:
248  using entity_type = Entity;
250  using size_type = std::size_t;
252  using function_type = callback_type;
253 
255  struct vertex {
262  vertex(const bool vtype, vertex_data data, std::vector<std::size_t> edges)
263  : is_top_level{vtype},
264  node{std::move(data)},
265  reachable{std::move(edges)}
266  {}
267 
275  size_type ro_dependency(type_info *buffer, const std::size_t length) const ENTT_NOEXCEPT {
276  return node.dependency(false, buffer, length);
277  }
278 
286  size_type rw_dependency(type_info *buffer, const std::size_t length) const ENTT_NOEXCEPT {
287  return node.dependency(true, buffer, length);
288  }
289 
294  size_type ro_count() const ENTT_NOEXCEPT {
295  return node.ro_count;
296  }
297 
302  size_type rw_count() const ENTT_NOEXCEPT {
303  return node.rw_count;
304  }
305 
310  bool top_level() const ENTT_NOEXCEPT {
311  return is_top_level;
312  }
313 
318  type_info info() const ENTT_NOEXCEPT {
319  return node.info;
320  }
321 
326  const char * name() const ENTT_NOEXCEPT {
327  return node.name;
328  }
329 
334  function_type * callback() const ENTT_NOEXCEPT {
335  return node.callback;
336  }
337 
342  const void * data() const ENTT_NOEXCEPT {
343  return node.payload;
344  }
345 
350  const std::vector<std::size_t> & children() const ENTT_NOEXCEPT {
351  return reachable;
352  }
353 
360  node.prepare ? node.prepare(reg) : void();
361  }
362 
363  private:
364  bool is_top_level;
365  vertex_data node;
366  std::vector<std::size_t> reachable;
367  };
368 
375  template<auto Candidate, typename... Req>
376  void emplace(const char *name = nullptr) {
377  using resource_type = decltype(internal::free_function_to_resource<Req...>(Candidate));
378  constexpr auto requires_registry = type_list_contains_v<typename resource_type::args, basic_registry<entity_type>>;
379 
380  callback_type *callback = +[](const void *, basic_registry<entity_type> &reg) {
381  std::apply(Candidate, to_args(reg, typename resource_type::args{}));
382  };
383 
384  track_dependencies(vertices.size(), requires_registry, typename resource_type::ro{}, typename resource_type::rw{});
385 
386  vertices.push_back({
387  resource_type::ro::size,
388  resource_type::rw::size,
389  name,
390  nullptr,
391  callback,
392  +[](const bool rw, type_info *buffer, const std::size_t length) { return rw ? fill_dependencies(typename resource_type::rw{}, buffer, length) : fill_dependencies(typename resource_type::ro{}, buffer, length); },
393  +[](basic_registry<entity_type> &reg) { void(to_args(reg, typename resource_type::args{})); },
394  type_id<std::integral_constant<decltype(Candidate), Candidate>>()
395  });
396  }
397 
407  template<auto Candidate, typename... Req, typename Type>
408  void emplace(Type &value_or_instance, const char *name = nullptr) {
409  using resource_type = decltype(internal::constrained_function_to_resource<Req...>(Candidate));
410  constexpr auto requires_registry = type_list_contains_v<typename resource_type::args, basic_registry<entity_type>>;
411 
412  callback_type *callback = +[](const void *payload, basic_registry<entity_type> &reg) {
413  Type *curr = static_cast<Type *>(const_cast<constness_as_t<void, Type> *>(payload));
414  std::apply(Candidate, std::tuple_cat(std::forward_as_tuple(*curr), to_args(reg, typename resource_type::args{})));
415  };
416 
417  track_dependencies(vertices.size(), requires_registry, typename resource_type::ro{}, typename resource_type::rw{});
418 
419  vertices.push_back({
420  resource_type::ro::size,
421  resource_type::rw::size,
422  name,
423  &value_or_instance,
424  callback,
425  +[](const bool rw, type_info *buffer, const std::size_t length) {
426  return rw ? fill_dependencies(typename resource_type::rw{}, buffer, length) : fill_dependencies(typename resource_type::ro{}, buffer, length);
427  },
428  +[](basic_registry<entity_type> &reg) {
429  void(to_args(reg, typename resource_type::args{}));
430  },
431  type_id<std::integral_constant<decltype(Candidate), Candidate>>()
432  });
433  }
434 
443  template<typename... Req>
444  void emplace(function_type *func, const void *payload = nullptr, const char *name = nullptr) {
445  using resource_type = internal::resource<type_list<>, type_list<Req...>>;
446  track_dependencies(vertices.size(), true, typename resource_type::ro{}, typename resource_type::rw{});
447 
448  vertices.push_back({
449  resource_type::ro::size,
450  resource_type::rw::size,
451  name,
452  payload,
453  func,
454  +[](const bool rw, type_info *buffer, const std::size_t length) {
455  return rw ? fill_dependencies(typename resource_type::rw{}, buffer, length) : fill_dependencies(typename resource_type::ro{}, buffer, length);
456  },
457  nullptr,
458  type_info{}
459  });
460  }
461 
466  std::vector<vertex> graph() {
467  const auto edges = adjacency_matrix();
468 
469  // creates the adjacency list
470  std::vector<vertex> adjacency_list{};
471  adjacency_list.reserve(vertices.size());
472 
473  for(std::size_t col{}, length = vertices.size(); col < length; ++col) {
474  std::vector<std::size_t> reachable{};
475  const auto row = col * length;
476  bool is_top_level = true;
477 
478  for(std::size_t next{}; next < length; ++next) {
479  if(edges[row + next]) {
480  reachable.push_back(next);
481  }
482  }
483 
484  for(std::size_t next{}; next < length && is_top_level; ++next) {
485  is_top_level = !edges[next * length + col];
486  }
487 
488  adjacency_list.emplace_back(is_top_level, vertices[col], std::move(reachable));
489  }
490 
491  return adjacency_list;
492  }
493 
495  void clear() {
496  dependencies.clear();
497  vertices.clear();
498  }
499 
500 private:
501  std::unordered_map<entt::id_type, std::vector<std::pair<std::size_t, bool>>> dependencies;
502  std::vector<vertex_data> vertices;
503 };
504 
505 
506 }
507 
508 
509 #endif
entt::basic_organizer::clear
void clear()
Erases all elements from a container.
Definition: organizer.hpp:495
entt::type_list
A class to use to push around lists of types, nothing more.
Definition: type_traits.hpp:127
entt::basic_organizer::function_type
callback_type function_type
Raw task function type.
Definition: organizer.hpp:252
entt::basic_organizer::vertex::data
const void * data() const noexcept
Returns the payload associated with a vertex, if any.
Definition: organizer.hpp:342
entt::basic_organizer::vertex::ro_dependency
size_type ro_dependency(type_info *buffer, const std::size_t length) const noexcept
Fills a buffer with the type info objects for the writable resources of a vertex.
Definition: organizer.hpp:275
entt::type_list_cat_t
typename type_list_cat< List... >::type type_list_cat_t
Helper type.
Definition: type_traits.hpp:225
entt::basic_organizer::vertex::callback
function_type * callback() const noexcept
Returns the function associated with a vertex.
Definition: organizer.hpp:334
entt::type_hash
Type hash.
Definition: type_info.hpp:108
entt::basic_organizer::vertex::top_level
bool top_level() const noexcept
Checks if a vertex is also a top-level one.
Definition: organizer.hpp:310
entt::basic_organizer::vertex::children
const std::vector< std::size_t > & children() const noexcept
Returns the list of nodes reachable from a given vertex.
Definition: organizer.hpp:350
entt::type_id
type_info type_id() noexcept
Returns the type info object for a given type.
Definition: type_info.hpp:239
entt::basic_organizer::emplace
void emplace(Type &value_or_instance, const char *name=nullptr)
Adds a free function with payload or a member function with an instance to the task list.
Definition: organizer.hpp:408
entt::basic_organizer::size_type
std::size_t size_type
Unsigned integer type.
Definition: organizer.hpp:250
entt::basic_organizer::vertex::ro_count
size_type ro_count() const noexcept
Returns the number of read-only resources of a vertex.
Definition: organizer.hpp:294
entt::basic_organizer::entity_type
Entity entity_type
Underlying entity identifier.
Definition: organizer.hpp:248
entt::basic_organizer::vertex::name
const char * name() const noexcept
Returns a user defined name associated with a vertex, if any.
Definition: organizer.hpp:326
entt::basic_organizer::emplace
void emplace(const char *name=nullptr)
Adds a free function to the task list.
Definition: organizer.hpp:376
entt
EnTT default namespace.
Definition: algorithm.hpp:13
entt::basic_organizer::vertex::rw_dependency
size_type rw_dependency(type_info *buffer, const std::size_t length) const noexcept
Fills a buffer with the type info objects for the read-only resources of a vertex.
Definition: organizer.hpp:286
entt::basic_organizer::vertex::vertex
vertex(const bool vtype, vertex_data data, std::vector< std::size_t > edges)
Constructs a vertex of the task graph.
Definition: organizer.hpp:262
entt::type_hash::value
static constexpr id_type value() noexcept
Returns the numeric representation of a given type.
Definition: type_info.hpp:117
entt::basic_organizer
Utility class for creating a static task graph.
Definition: organizer.hpp:125
entt::basic_organizer::vertex::rw_count
size_type rw_count() const noexcept
Returns the number of writable resources of a vertex.
Definition: organizer.hpp:302
entt::basic_organizer::emplace
void emplace(function_type *func, const void *payload=nullptr, const char *name=nullptr)
Adds an user defined function with optional payload to the task list.
Definition: organizer.hpp:444
entt::basic_organizer::graph
std::vector< vertex > graph()
Generates a task graph for the current content.
Definition: organizer.hpp:466
entt::basic_registry
Fast and reliable entity-component system.
Definition: registry.hpp:44
entt::basic_organizer::vertex::info
type_info info() const noexcept
Returns a type info object associated with a vertex.
Definition: organizer.hpp:318
entt::type_info
Implementation specific information about a type.
Definition: type_info.hpp:141
entt::basic_organizer::vertex::prepare
void prepare(basic_registry< entity_type > &reg) const
Prepares a registry and assures that all required resources are properly instantiated before using th...
Definition: organizer.hpp:359
entt::as_view
Converts a registry to a view.
Definition: helper.hpp:21
entt::basic_view
basic_view(Storage &... storage) noexcept -> basic_view< std::common_type_t< typename Storage::entity_type... >, entt::exclude_t<>, constness_as_t< typename Storage::value_type, Storage >... >
Deduction guide.
entt::constness_as_t
typename constness_as< To, From >::type constness_as_t
Alias template to facilitate the transcription of the constness.
Definition: type_traits.hpp:549
entt::basic_organizer::vertex
Vertex type of a task graph defined as an adjacency list.
Definition: organizer.hpp:255