EnTT  3.10.0
organizer.hpp
1 #ifndef ENTT_ENTITY_ORGANIZER_HPP
2 #define ENTT_ENTITY_ORGANIZER_HPP
3 
4 #include <algorithm>
5 #include <cstddef>
6 #include <type_traits>
7 #include <utility>
8 #include <vector>
9 #include "../container/dense_map.hpp"
10 #include "../core/type_info.hpp"
11 #include "../core/type_traits.hpp"
12 #include "../core/utility.hpp"
13 #include "fwd.hpp"
14 #include "helper.hpp"
15 
16 namespace entt {
17 
23 namespace internal {
24 
25 template<typename>
26 struct is_view: std::false_type {};
27 
28 template<typename Entity, typename... Component, typename... Exclude>
29 struct is_view<basic_view<Entity, get_t<Component...>, exclude_t<Exclude...>>>: std::true_type {};
30 
31 template<typename Type>
32 inline constexpr bool is_view_v = is_view<Type>::value;
33 
34 template<typename Type, typename Override>
35 struct unpack_type {
36  using ro = std::conditional_t<
37  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>>),
38  type_list<std::remove_const_t<Type>>,
39  type_list<>>;
40 
41  using rw = std::conditional_t<
42  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>>),
43  type_list<Type>,
44  type_list<>>;
45 };
46 
47 template<typename Entity, typename... Override>
48 struct unpack_type<basic_registry<Entity>, type_list<Override...>> {
49  using ro = type_list<>;
50  using rw = type_list<>;
51 };
52 
53 template<typename Entity, typename... Override>
54 struct unpack_type<const basic_registry<Entity>, type_list<Override...>>
55  : unpack_type<basic_registry<Entity>, type_list<Override...>> {};
56 
57 template<typename Entity, typename... Component, typename... Exclude, typename... Override>
58 struct unpack_type<basic_view<Entity, get_t<Component...>, exclude_t<Exclude...>>, type_list<Override...>> {
59  using ro = type_list_cat_t<type_list<Exclude...>, typename unpack_type<Component, type_list<Override...>>::ro...>;
60  using rw = type_list_cat_t<typename unpack_type<Component, type_list<Override...>>::rw...>;
61 };
62 
63 template<typename Entity, typename... Component, typename... Exclude, typename... Override>
64 struct unpack_type<const basic_view<Entity, get_t<Component...>, exclude_t<Exclude...>>, type_list<Override...>>
65  : unpack_type<basic_view<Entity, get_t<Component...>, exclude_t<Exclude...>>, type_list<Override...>> {};
66 
67 template<typename, typename>
68 struct resource_traits;
69 
70 template<typename... Args, typename... Req>
71 struct resource_traits<type_list<Args...>, type_list<Req...>> {
72  using args = type_list<std::remove_const_t<Args>...>;
73  using ro = type_list_cat_t<typename unpack_type<Args, type_list<Req...>>::ro..., typename unpack_type<Req, type_list<>>::ro...>;
74  using rw = type_list_cat_t<typename unpack_type<Args, type_list<Req...>>::rw..., typename unpack_type<Req, type_list<>>::rw...>;
75 };
76 
77 template<typename... Req, typename Ret, typename... Args>
78 resource_traits<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> free_function_to_resource_traits(Ret (*)(Args...));
79 
80 template<typename... Req, typename Ret, typename Type, typename... Args>
81 resource_traits<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> constrained_function_to_resource_traits(Ret (*)(Type &, Args...));
82 
83 template<typename... Req, typename Ret, typename Class, typename... Args>
84 resource_traits<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> constrained_function_to_resource_traits(Ret (Class::*)(Args...));
85 
86 template<typename... Req, typename Ret, typename Class, typename... Args>
87 resource_traits<type_list<std::remove_reference_t<Args>...>, type_list<Req...>> constrained_function_to_resource_traits(Ret (Class::*)(Args...) const);
88 
89 } // namespace internal
90 
107 template<typename Entity>
108 class basic_organizer final {
109  using callback_type = void(const void *, basic_registry<Entity> &);
110  using prepare_type = void(basic_registry<Entity> &);
111  using dependency_type = std::size_t(const bool, const type_info **, const std::size_t);
112 
113  struct vertex_data final {
114  std::size_t ro_count{};
115  std::size_t rw_count{};
116  const char *name{};
117  const void *payload{};
118  callback_type *callback{};
119  dependency_type *dependency;
120  prepare_type *prepare{};
121  const type_info *info{};
122  };
123 
124  template<typename Type>
125  [[nodiscard]] static decltype(auto) extract(basic_registry<Entity> &reg) {
126  if constexpr(std::is_same_v<Type, basic_registry<Entity>>) {
127  return reg;
128  } else if constexpr(internal::is_view_v<Type>) {
129  return as_view{reg};
130  } else {
131  return reg.ctx().template emplace<std::remove_reference_t<Type>>();
132  }
133  }
134 
135  template<typename... Args>
136  [[nodiscard]] static auto to_args(basic_registry<Entity> &reg, type_list<Args...>) {
137  return std::tuple<decltype(extract<Args>(reg))...>(extract<Args>(reg)...);
138  }
139 
140  template<typename... Type>
141  static std::size_t fill_dependencies(type_list<Type...>, [[maybe_unused]] const type_info **buffer, [[maybe_unused]] const std::size_t count) {
142  if constexpr(sizeof...(Type) == 0u) {
143  return {};
144  } else {
145  const type_info *info[sizeof...(Type)]{&type_id<Type>()...};
146  const auto length = (std::min)(count, sizeof...(Type));
147  std::copy_n(info, length, buffer);
148  return length;
149  }
150  }
151 
152  template<typename... RO, typename... RW>
153  void track_dependencies(std::size_t index, const bool requires_registry, type_list<RO...>, type_list<RW...>) {
154  dependencies[type_hash<basic_registry<Entity>>::value()].emplace_back(index, requires_registry || (sizeof...(RO) + sizeof...(RW) == 0u));
155  (dependencies[type_hash<RO>::value()].emplace_back(index, false), ...);
156  (dependencies[type_hash<RW>::value()].emplace_back(index, true), ...);
157  }
158 
159  [[nodiscard]] std::vector<bool> adjacency_matrix() {
160  const auto length = vertices.size();
161  std::vector<bool> edges(length * length, false);
162 
163  // creates the adjacency matrix
164  for(const auto &deps: dependencies) {
165  const auto last = deps.second.cend();
166  auto it = deps.second.cbegin();
167 
168  while(it != last) {
169  if(it->second) {
170  // rw item
171  if(auto curr = it++; it != last) {
172  if(it->second) {
173  edges[curr->first * length + it->first] = true;
174  } else {
175  if(const auto next = std::find_if(it, last, [](const auto &elem) { return elem.second; }); next != last) {
176  for(; it != next; ++it) {
177  edges[curr->first * length + it->first] = true;
178  edges[it->first * length + next->first] = true;
179  }
180  } else {
181  for(; it != next; ++it) {
182  edges[curr->first * length + it->first] = true;
183  }
184  }
185  }
186  }
187  } else {
188  // ro item, possibly only on first iteration
189  if(const auto next = std::find_if(it, last, [](const auto &elem) { return elem.second; }); next != last) {
190  for(; it != next; ++it) {
191  edges[it->first * length + next->first] = true;
192  }
193  } else {
194  it = last;
195  }
196  }
197  }
198  }
199 
200  // computes the transitive closure
201  for(std::size_t vk{}; vk < length; ++vk) {
202  for(std::size_t vi{}; vi < length; ++vi) {
203  for(std::size_t vj{}; vj < length; ++vj) {
204  edges[vi * length + vj] = edges[vi * length + vj] || (edges[vi * length + vk] && edges[vk * length + vj]);
205  }
206  }
207  }
208 
209  // applies the transitive reduction
210  for(std::size_t vert{}; vert < length; ++vert) {
211  edges[vert * length + vert] = false;
212  }
213 
214  for(std::size_t vj{}; vj < length; ++vj) {
215  for(std::size_t vi{}; vi < length; ++vi) {
216  if(edges[vi * length + vj]) {
217  for(std::size_t vk{}; vk < length; ++vk) {
218  if(edges[vj * length + vk]) {
219  edges[vi * length + vk] = false;
220  }
221  }
222  }
223  }
224  }
225 
226  return edges;
227  }
228 
229 public:
231  using entity_type = Entity;
233  using size_type = std::size_t;
235  using function_type = callback_type;
236 
238  struct vertex {
245  vertex(const bool vtype, vertex_data data, std::vector<std::size_t> edges)
246  : is_top_level{vtype},
247  node{std::move(data)},
248  reachable{std::move(edges)} {}
249 
257  size_type ro_dependency(const type_info **buffer, const std::size_t length) const ENTT_NOEXCEPT {
258  return node.dependency(false, buffer, length);
259  }
260 
268  size_type rw_dependency(const type_info **buffer, const std::size_t length) const ENTT_NOEXCEPT {
269  return node.dependency(true, buffer, length);
270  }
271 
276  size_type ro_count() const ENTT_NOEXCEPT {
277  return node.ro_count;
278  }
279 
284  size_type rw_count() const ENTT_NOEXCEPT {
285  return node.rw_count;
286  }
287 
292  bool top_level() const ENTT_NOEXCEPT {
293  return is_top_level;
294  }
295 
300  const type_info &info() const ENTT_NOEXCEPT {
301  return *node.info;
302  }
303 
308  const char *name() const ENTT_NOEXCEPT {
309  return node.name;
310  }
311 
316  function_type *callback() const ENTT_NOEXCEPT {
317  return node.callback;
318  }
319 
324  const void *data() const ENTT_NOEXCEPT {
325  return node.payload;
326  }
327 
332  const std::vector<std::size_t> &children() const ENTT_NOEXCEPT {
333  return reachable;
334  }
335 
342  node.prepare ? node.prepare(reg) : void();
343  }
344 
345  private:
346  bool is_top_level;
347  vertex_data node;
348  std::vector<std::size_t> reachable;
349  };
350 
357  template<auto Candidate, typename... Req>
358  void emplace(const char *name = nullptr) {
359  using resource_type = decltype(internal::free_function_to_resource_traits<Req...>(Candidate));
360  constexpr auto requires_registry = type_list_contains_v<typename resource_type::args, basic_registry<entity_type>>;
361 
362  callback_type *callback = +[](const void *, basic_registry<entity_type> &reg) {
363  std::apply(Candidate, to_args(reg, typename resource_type::args{}));
364  };
365 
366  vertex_data vdata{
367  resource_type::ro::size,
368  resource_type::rw::size,
369  name,
370  nullptr,
371  callback,
372  +[](const bool rw, const 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); },
373  +[](basic_registry<entity_type> &reg) { void(to_args(reg, typename resource_type::args{})); },
374  &type_id<std::integral_constant<decltype(Candidate), Candidate>>()};
375 
376  track_dependencies(vertices.size(), requires_registry, typename resource_type::ro{}, typename resource_type::rw{});
377  vertices.push_back(std::move(vdata));
378  }
379 
389  template<auto Candidate, typename... Req, typename Type>
390  void emplace(Type &value_or_instance, const char *name = nullptr) {
391  using resource_type = decltype(internal::constrained_function_to_resource_traits<Req...>(Candidate));
392  constexpr auto requires_registry = type_list_contains_v<typename resource_type::args, basic_registry<entity_type>>;
393 
394  callback_type *callback = +[](const void *payload, basic_registry<entity_type> &reg) {
395  Type *curr = static_cast<Type *>(const_cast<constness_as_t<void, Type> *>(payload));
396  std::apply(Candidate, std::tuple_cat(std::forward_as_tuple(*curr), to_args(reg, typename resource_type::args{})));
397  };
398 
399  vertex_data vdata{
400  resource_type::ro::size,
401  resource_type::rw::size,
402  name,
403  &value_or_instance,
404  callback,
405  +[](const bool rw, const 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); },
406  +[](basic_registry<entity_type> &reg) { void(to_args(reg, typename resource_type::args{})); },
407  &type_id<std::integral_constant<decltype(Candidate), Candidate>>()};
408 
409  track_dependencies(vertices.size(), requires_registry, typename resource_type::ro{}, typename resource_type::rw{});
410  vertices.push_back(std::move(vdata));
411  }
412 
421  template<typename... Req>
422  void emplace(function_type *func, const void *payload = nullptr, const char *name = nullptr) {
423  using resource_type = internal::resource_traits<type_list<>, type_list<Req...>>;
424  track_dependencies(vertices.size(), true, typename resource_type::ro{}, typename resource_type::rw{});
425 
426  vertex_data vdata{
427  resource_type::ro::size,
428  resource_type::rw::size,
429  name,
430  payload,
431  func,
432  +[](const bool rw, const 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); },
433  nullptr,
434  &type_id<void>()};
435 
436  vertices.push_back(std::move(vdata));
437  }
438 
443  std::vector<vertex> graph() {
444  const auto edges = adjacency_matrix();
445 
446  // creates the adjacency list
447  std::vector<vertex> adjacency_list{};
448  adjacency_list.reserve(vertices.size());
449 
450  for(std::size_t col{}, length = vertices.size(); col < length; ++col) {
451  std::vector<std::size_t> reachable{};
452  const auto row = col * length;
453  bool is_top_level = true;
454 
455  for(std::size_t next{}; next < length; ++next) {
456  if(edges[row + next]) {
457  reachable.push_back(next);
458  }
459  }
460 
461  for(std::size_t next{}; next < length && is_top_level; ++next) {
462  is_top_level = !edges[next * length + col];
463  }
464 
465  adjacency_list.emplace_back(is_top_level, vertices[col], std::move(reachable));
466  }
467 
468  return adjacency_list;
469  }
470 
472  void clear() {
473  dependencies.clear();
474  vertices.clear();
475  }
476 
477 private:
479  std::vector<vertex_data> vertices;
480 };
481 
482 } // namespace entt
483 
484 #endif
Utility class for creating a static task graph.
Definition: organizer.hpp:108
Entity entity_type
Underlying entity identifier.
Definition: organizer.hpp:231
callback_type function_type
Raw task function type.
Definition: organizer.hpp:235
void emplace(const char *name=nullptr)
Adds a free function to the task list.
Definition: organizer.hpp:358
std::vector< vertex > graph()
Generates a task graph for the current content.
Definition: organizer.hpp:443
void clear()
Erases all elements from a container.
Definition: organizer.hpp:472
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:422
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:390
std::size_t size_type
Unsigned integer type.
Definition: organizer.hpp:233
Fast and reliable entity-component system.
Definition: registry.hpp:221
context & ctx()
Returns the context object, that is, a general purpose container.
Definition: registry.hpp:1476
Associative container for key-value pairs with unique keys.
Definition: dense_map.hpp:265
EnTT default namespace.
Definition: dense_map.hpp:22
basic_view(Storage &...storage) -> basic_view< std::common_type_t< typename Storage::entity_type... >, get_t< constness_as_t< typename Storage::value_type, Storage >... >, exclude_t<>>
Deduction guide.
const type_info & type_id()
Returns the type info object associated to a given type.
Definition: type_info.hpp:257
typename type_list_cat< List... >::type type_list_cat_t
Helper type.
typename constness_as< To, From >::type constness_as_t
Alias template to facilitate the transcription of the constness.
Converts a registry to a view.
Definition: helper.hpp:19
Vertex type of a task graph defined as an adjacency list.
Definition: organizer.hpp:238
size_type rw_count() const
Returns the number of writable resources of a vertex.
Definition: organizer.hpp:284
bool top_level() const
Checks if a vertex is also a top-level one.
Definition: organizer.hpp:292
size_type rw_dependency(const type_info **buffer, const std::size_t length) const
Fills a buffer with the type info objects for the read-only resources of a vertex.
Definition: organizer.hpp:268
size_type ro_count() const
Returns the number of read-only resources of a vertex.
Definition: organizer.hpp:276
size_type ro_dependency(const type_info **buffer, const std::size_t length) const
Fills a buffer with the type info objects for the writable resources of a vertex.
Definition: organizer.hpp:257
const void * data() const
Returns the payload associated with a vertex, if any.
Definition: organizer.hpp:324
const std::vector< std::size_t > & children() const
Returns the list of nodes reachable from a given vertex.
Definition: organizer.hpp:332
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:341
vertex(const bool vtype, vertex_data data, std::vector< std::size_t > edges)
Constructs a vertex of the task graph.
Definition: organizer.hpp:245
const char * name() const
Returns a user defined name associated with a vertex, if any.
Definition: organizer.hpp:308
const type_info & info() const
Returns a type info object associated with a vertex.
Definition: organizer.hpp:300
function_type * callback() const
Returns the function associated with a vertex.
Definition: organizer.hpp:316
Identity function object (waiting for C++20).
Definition: utility.hpp:10
Type hash.
Definition: type_info.hpp:100
static constexpr id_type value()
Returns the numeric representation of a given type.
Definition: type_info.hpp:109
Implementation specific information about a type.
Definition: type_info.hpp:141
A class to use to push around lists of types, nothing more.