From 61e5bcef2629e2d68b805a956a96fff264d4f74d Mon Sep 17 00:00:00 2001 From: untodesu Date: Sat, 28 Jun 2025 01:59:49 +0500 Subject: Restructure dependencies and update to C++20 - Nuked static_assert from almost everywhere in the project - Nuked binary dependency support. Might add one later though - Separated dependency headers into a separate include subdirectory - Grafted a thirdpartylegalnotices.txt generator from RITEG - Pushed development snapshot version to 2126 (26th week of 2025) --- deps/include/entt/graph/adjacency_matrix.hpp | 336 ------------------------- deps/include/entt/graph/dot.hpp | 58 ----- deps/include/entt/graph/flow.hpp | 351 --------------------------- deps/include/entt/graph/fwd.hpp | 27 --- 4 files changed, 772 deletions(-) delete mode 100644 deps/include/entt/graph/adjacency_matrix.hpp delete mode 100644 deps/include/entt/graph/dot.hpp delete mode 100644 deps/include/entt/graph/flow.hpp delete mode 100644 deps/include/entt/graph/fwd.hpp (limited to 'deps/include/entt/graph') diff --git a/deps/include/entt/graph/adjacency_matrix.hpp b/deps/include/entt/graph/adjacency_matrix.hpp deleted file mode 100644 index a736aeb..0000000 --- a/deps/include/entt/graph/adjacency_matrix.hpp +++ /dev/null @@ -1,336 +0,0 @@ -#ifndef ENTT_GRAPH_ADJACENCY_MATRIX_HPP -#define ENTT_GRAPH_ADJACENCY_MATRIX_HPP - -#include -#include -#include -#include -#include -#include -#include "../config/config.h" -#include "../core/iterator.hpp" -#include "fwd.hpp" - -namespace entt { - -/*! @cond TURN_OFF_DOXYGEN */ -namespace internal { - -template -class edge_iterator { - using size_type = std::size_t; - -public: - using value_type = std::pair; - using pointer = input_iterator_pointer; - using reference = value_type; - using difference_type = std::ptrdiff_t; - using iterator_category = std::input_iterator_tag; - using iterator_concept = std::forward_iterator_tag; - - constexpr edge_iterator() noexcept = default; - - // NOLINTNEXTLINE(bugprone-easily-swappable-parameters) - constexpr edge_iterator(It base, const size_type vertices, const size_type from, const size_type to, const size_type step) noexcept - : it{std::move(base)}, - vert{vertices}, - pos{from}, - last{to}, - offset{step} { - for(; pos != last && !it[pos]; pos += offset) {} - } - - constexpr edge_iterator &operator++() noexcept { - for(pos += offset; pos != last && !it[pos]; pos += offset) {} - return *this; - } - - constexpr edge_iterator operator++(int) noexcept { - edge_iterator orig = *this; - return ++(*this), orig; - } - - [[nodiscard]] constexpr reference operator*() const noexcept { - return *operator->(); - } - - [[nodiscard]] constexpr pointer operator->() const noexcept { - return std::make_pair(pos / vert, pos % vert); - } - - template - friend constexpr bool operator==(const edge_iterator &, const edge_iterator &) noexcept; - -private: - It it{}; - size_type vert{}; - size_type pos{}; - size_type last{}; - size_type offset{}; -}; - -template -[[nodiscard]] inline constexpr bool operator==(const edge_iterator &lhs, const edge_iterator &rhs) noexcept { - return lhs.pos == rhs.pos; -} - -template -[[nodiscard]] inline constexpr bool operator!=(const edge_iterator &lhs, const edge_iterator &rhs) noexcept { - return !(lhs == rhs); -} - -} // namespace internal -/*! @endcond */ - -/** - * @brief Basic implementation of a directed adjacency matrix. - * @tparam Category Either a directed or undirected category tag. - * @tparam Allocator Type of allocator used to manage memory and elements. - */ -template -class adjacency_matrix { - using alloc_traits = std::allocator_traits; - static_assert(std::is_base_of_v, "Invalid graph category"); - static_assert(std::is_same_v, "Invalid value type"); - using container_type = std::vector>; - -public: - /*! @brief Allocator type. */ - using allocator_type = Allocator; - /*! @brief Unsigned integer type. */ - using size_type = std::size_t; - /*! @brief Vertex type. */ - using vertex_type = size_type; - /*! @brief Edge type. */ - using edge_type = std::pair; - /*! @brief Vertex iterator type. */ - using vertex_iterator = iota_iterator; - /*! @brief Edge iterator type. */ - using edge_iterator = internal::edge_iterator; - /*! @brief Out-edge iterator type. */ - using out_edge_iterator = edge_iterator; - /*! @brief In-edge iterator type. */ - using in_edge_iterator = edge_iterator; - /*! @brief Graph category tag. */ - using graph_category = Category; - - /*! @brief Default constructor. */ - adjacency_matrix() noexcept(noexcept(allocator_type{})) - : adjacency_matrix{0u} { - } - - /** - * @brief Constructs an empty container with a given allocator. - * @param allocator The allocator to use. - */ - explicit adjacency_matrix(const allocator_type &allocator) noexcept - : adjacency_matrix{0u, allocator} {} - - /** - * @brief Constructs an empty container with a given allocator and user - * supplied number of vertices. - * @param vertices Number of vertices. - * @param allocator The allocator to use. - */ - adjacency_matrix(const size_type vertices, const allocator_type &allocator = allocator_type{}) - : matrix{vertices * vertices, allocator}, - vert{vertices} {} - - /*! @brief Default copy constructor. */ - adjacency_matrix(const adjacency_matrix &) = default; - - /** - * @brief Allocator-extended copy constructor. - * @param other The instance to copy from. - * @param allocator The allocator to use. - */ - adjacency_matrix(const adjacency_matrix &other, const allocator_type &allocator) - : matrix{other.matrix, allocator}, - vert{other.vert} {} - - /*! @brief Default move constructor. */ - adjacency_matrix(adjacency_matrix &&) noexcept = default; - - /** - * @brief Allocator-extended move constructor. - * @param other The instance to move from. - * @param allocator The allocator to use. - */ - adjacency_matrix(adjacency_matrix &&other, const allocator_type &allocator) - : matrix{std::move(other.matrix), allocator}, - vert{other.vert} {} - - /*! @brief Default destructor. */ - ~adjacency_matrix() noexcept = default; - - /** - * @brief Default copy assignment operator. - * @return This container. - */ - adjacency_matrix &operator=(const adjacency_matrix &) = default; - - /** - * @brief Default move assignment operator. - * @return This container. - */ - adjacency_matrix &operator=(adjacency_matrix &&) noexcept = default; - - /** - * @brief Returns the associated allocator. - * @return The associated allocator. - */ - [[nodiscard]] constexpr allocator_type get_allocator() const noexcept { - return matrix.get_allocator(); - } - - /*! @brief Clears the adjacency matrix. */ - void clear() noexcept { - matrix.clear(); - vert = {}; - } - - /** - * @brief Exchanges the contents with those of a given adjacency matrix. - * @param other Adjacency matrix to exchange the content with. - */ - void swap(adjacency_matrix &other) { - using std::swap; - swap(matrix, other.matrix); - swap(vert, other.vert); - } - - /** - * @brief Returns true if an adjacency matrix is empty, false otherwise. - * - * @warning - * Potentially expensive, try to avoid it on hot paths. - * - * @return True if the adjacency matrix is empty, false otherwise. - */ - [[nodiscard]] bool empty() const noexcept { - const auto iterable = edges(); - return (iterable.begin() == iterable.end()); - } - - /** - * @brief Returns the number of vertices. - * @return The number of vertices. - */ - [[nodiscard]] size_type size() const noexcept { - return vert; - } - - /** - * @brief Returns an iterable object to visit all vertices of a matrix. - * @return An iterable object to visit all vertices of a matrix. - */ - [[nodiscard]] iterable_adaptor vertices() const noexcept { - return {0u, vert}; - } - - /** - * @brief Returns an iterable object to visit all edges of a matrix. - * @return An iterable object to visit all edges of a matrix. - */ - [[nodiscard]] iterable_adaptor edges() const noexcept { - const auto it = matrix.cbegin(); - const auto sz = matrix.size(); - return {{it, vert, 0u, sz, 1u}, {it, vert, sz, sz, 1u}}; - } - - /** - * @brief Returns an iterable object to visit all out-edges of a vertex. - * @param vertex The vertex of which to return all out-edges. - * @return An iterable object to visit all out-edges of a vertex. - */ - [[nodiscard]] iterable_adaptor out_edges(const vertex_type vertex) const noexcept { - const auto it = matrix.cbegin(); - const auto from = vertex * vert; - const auto to = from + vert; - return {{it, vert, from, to, 1u}, {it, vert, to, to, 1u}}; - } - - /** - * @brief Returns an iterable object to visit all in-edges of a vertex. - * @param vertex The vertex of which to return all in-edges. - * @return An iterable object to visit all in-edges of a vertex. - */ - [[nodiscard]] iterable_adaptor in_edges(const vertex_type vertex) const noexcept { - const auto it = matrix.cbegin(); - const auto from = vertex; - const auto to = vert * vert + from; - return {{it, vert, from, to, vert}, {it, vert, to, to, vert}}; - } - - /** - * @brief Resizes an adjacency matrix. - * @param vertices The new number of vertices. - */ - void resize(const size_type vertices) { - adjacency_matrix other{vertices, get_allocator()}; - - for(auto [lhs, rhs]: edges()) { - other.insert(lhs, rhs); - } - - other.swap(*this); - } - - /** - * @brief Inserts an edge into the adjacency matrix, if it does not exist. - * @param lhs The left hand vertex of the edge. - * @param rhs The right hand vertex of the edge. - * @return A pair consisting of an iterator to the inserted element (or to - * the element that prevented the insertion) and a bool denoting whether the - * insertion took place. - */ - std::pair insert(const vertex_type lhs, const vertex_type rhs) { - const auto pos = lhs * vert + rhs; - - if constexpr(std::is_same_v) { - const auto rev = rhs * vert + lhs; - ENTT_ASSERT(matrix[pos] == matrix[rev], "Something went really wrong"); - matrix[rev] = 1u; - } - - const auto inserted = !std::exchange(matrix[pos], 1u); - return {edge_iterator{matrix.cbegin(), vert, pos, matrix.size(), 1u}, inserted}; - } - - /** - * @brief Removes the edge associated with a pair of given vertices. - * @param lhs The left hand vertex of the edge. - * @param rhs The right hand vertex of the edge. - * @return Number of elements removed (either 0 or 1). - */ - size_type erase(const vertex_type lhs, const vertex_type rhs) { - const auto pos = lhs * vert + rhs; - - if constexpr(std::is_same_v) { - const auto rev = rhs * vert + lhs; - ENTT_ASSERT(matrix[pos] == matrix[rev], "Something went really wrong"); - matrix[rev] = 0u; - } - - return std::exchange(matrix[pos], 0u); - } - - /** - * @brief Checks if an adjacency matrix contains a given edge. - * @param lhs The left hand vertex of the edge. - * @param rhs The right hand vertex of the edge. - * @return True if there is such an edge, false otherwise. - */ - [[nodiscard]] bool contains(const vertex_type lhs, const vertex_type rhs) const { - const auto pos = lhs * vert + rhs; - return pos < matrix.size() && matrix[pos]; - } - -private: - container_type matrix; - size_type vert; -}; - -} // namespace entt - -#endif diff --git a/deps/include/entt/graph/dot.hpp b/deps/include/entt/graph/dot.hpp deleted file mode 100644 index 4671aa8..0000000 --- a/deps/include/entt/graph/dot.hpp +++ /dev/null @@ -1,58 +0,0 @@ -#ifndef ENTT_GRAPH_DOT_HPP -#define ENTT_GRAPH_DOT_HPP - -#include -#include -#include "fwd.hpp" - -namespace entt { - -/** - * @brief Outputs a graph in dot format. - * @tparam Graph Graph type, valid as long as it exposes edges and vertices. - * @tparam Writer Vertex decorator type. - * @param out A standard output stream. - * @param graph The graph to output. - * @param writer Vertex decorator object. - */ -template -void dot(std::ostream &out, const Graph &graph, Writer writer) { - static_assert(std::is_base_of_v, "Invalid graph category"); - - if constexpr(std::is_same_v) { - out << "graph{"; - } else { - out << "digraph{"; - } - - for(auto &&vertex: graph.vertices()) { - out << vertex << "["; - writer(out, vertex); - out << "];"; - } - - for(auto [lhs, rhs]: graph.edges()) { - if constexpr(std::is_same_v) { - out << lhs << "--" << rhs << ";"; - } else { - out << lhs << "->" << rhs << ";"; - } - } - - out << "}"; -} - -/** - * @brief Outputs a graph in dot format. - * @tparam Graph Graph type, valid as long as it exposes edges and vertices. - * @param out A standard output stream. - * @param graph The graph to output. - */ -template -void dot(std::ostream &out, const Graph &graph) { - return dot(out, graph, [](auto &&...) {}); -} - -} // namespace entt - -#endif diff --git a/deps/include/entt/graph/flow.hpp b/deps/include/entt/graph/flow.hpp deleted file mode 100644 index 40cfe1c..0000000 --- a/deps/include/entt/graph/flow.hpp +++ /dev/null @@ -1,351 +0,0 @@ -#ifndef ENTT_GRAPH_FLOW_HPP -#define ENTT_GRAPH_FLOW_HPP - -#include -#include -#include -#include -#include -#include -#include -#include -#include "../config/config.h" -#include "../container/dense_map.hpp" -#include "../container/dense_set.hpp" -#include "../core/compressed_pair.hpp" -#include "../core/fwd.hpp" -#include "../core/iterator.hpp" -#include "../core/utility.hpp" -#include "adjacency_matrix.hpp" -#include "fwd.hpp" - -namespace entt { - -/** - * @brief Utility class for creating task graphs. - * @tparam Allocator Type of allocator used to manage memory and elements. - */ -template -class basic_flow { - using alloc_traits = std::allocator_traits; - static_assert(std::is_same_v, "Invalid value type"); - using task_container_type = dense_set, typename alloc_traits::template rebind_alloc>; - using ro_rw_container_type = std::vector, typename alloc_traits::template rebind_alloc>>; - using deps_container_type = dense_map, typename alloc_traits::template rebind_alloc>>; - using adjacency_matrix_type = adjacency_matrix>; - - void emplace(const id_type res, const bool is_rw) { - ENTT_ASSERT(index.first() < vertices.size(), "Invalid node"); - - if(!deps.contains(res) && sync_on != vertices.size()) { - deps[res].emplace_back(sync_on, true); - } - - deps[res].emplace_back(index.first(), is_rw); - } - - void setup_graph(adjacency_matrix_type &matrix) const { - for(const auto &elem: deps) { - const auto last = elem.second.cend(); - auto it = elem.second.cbegin(); - - while(it != last) { - if(it->second) { - // rw item - if(auto curr = it++; it != last) { - if(it->second) { - matrix.insert(curr->first, it->first); - } else if(const auto next = std::find_if(it, last, [](const auto &value) { return value.second; }); next != last) { - for(; it != next; ++it) { - matrix.insert(curr->first, it->first); - matrix.insert(it->first, next->first); - } - } else { - for(; it != next; ++it) { - matrix.insert(curr->first, it->first); - } - } - } - } else { - // ro item (first iteration only) - if(const auto next = std::find_if(it, last, [](const auto &value) { return value.second; }); next != last) { - for(; it != next; ++it) { - matrix.insert(it->first, next->first); - } - } else { - it = last; - } - } - } - } - } - - void transitive_closure(adjacency_matrix_type &matrix) const { - const auto length = matrix.size(); - - for(std::size_t vk{}; vk < length; ++vk) { - for(std::size_t vi{}; vi < length; ++vi) { - for(std::size_t vj{}; vj < length; ++vj) { - if(matrix.contains(vi, vk) && matrix.contains(vk, vj)) { - matrix.insert(vi, vj); - } - } - } - } - } - - void transitive_reduction(adjacency_matrix_type &matrix) const { - const auto length = matrix.size(); - - for(std::size_t vert{}; vert < length; ++vert) { - matrix.erase(vert, vert); - } - - for(std::size_t vj{}; vj < length; ++vj) { - for(std::size_t vi{}; vi < length; ++vi) { - if(matrix.contains(vi, vj)) { - for(std::size_t vk{}; vk < length; ++vk) { - if(matrix.contains(vj, vk)) { - matrix.erase(vi, vk); - } - } - } - } - } - } - -public: - /*! @brief Allocator type. */ - using allocator_type = Allocator; - /*! @brief Unsigned integer type. */ - using size_type = std::size_t; - /*! @brief Iterable task list. */ - using iterable = iterable_adaptor; - /*! @brief Adjacency matrix type. */ - using graph_type = adjacency_matrix_type; - - /*! @brief Default constructor. */ - basic_flow() - : basic_flow{allocator_type{}} {} - - /** - * @brief Constructs a flow builder with a given allocator. - * @param allocator The allocator to use. - */ - explicit basic_flow(const allocator_type &allocator) - : index{0u, allocator}, - vertices{allocator}, - deps{allocator} {} - - /*! @brief Default copy constructor. */ - basic_flow(const basic_flow &) = default; - - /** - * @brief Allocator-extended copy constructor. - * @param other The instance to copy from. - * @param allocator The allocator to use. - */ - basic_flow(const basic_flow &other, const allocator_type &allocator) - : index{other.index.first(), allocator}, - vertices{other.vertices, allocator}, - deps{other.deps, allocator}, - sync_on{other.sync_on} {} - - /*! @brief Default move constructor. */ - basic_flow(basic_flow &&) noexcept = default; - - /** - * @brief Allocator-extended move constructor. - * @param other The instance to move from. - * @param allocator The allocator to use. - */ - basic_flow(basic_flow &&other, const allocator_type &allocator) - : index{other.index.first(), allocator}, - vertices{std::move(other.vertices), allocator}, - deps{std::move(other.deps), allocator}, - sync_on{other.sync_on} {} - - /*! @brief Default destructor. */ - ~basic_flow() noexcept = default; - - /** - * @brief Default copy assignment operator. - * @return This flow builder. - */ - basic_flow &operator=(const basic_flow &) = default; - - /** - * @brief Default move assignment operator. - * @return This flow builder. - */ - basic_flow &operator=(basic_flow &&) noexcept = default; - - /** - * @brief Returns the associated allocator. - * @return The associated allocator. - */ - [[nodiscard]] constexpr allocator_type get_allocator() const noexcept { - return allocator_type{index.second()}; - } - - /** - * @brief Returns the identifier at specified location. - * @param pos Position of the identifier to return. - * @return The requested identifier. - */ - [[nodiscard]] id_type operator[](const size_type pos) const { - return vertices.cbegin()[pos]; - } - - /*! @brief Clears the flow builder. */ - void clear() noexcept { - index.first() = {}; - vertices.clear(); - deps.clear(); - sync_on = {}; - } - - /** - * @brief Exchanges the contents with those of a given flow builder. - * @param other Flow builder to exchange the content with. - */ - void swap(basic_flow &other) { - using std::swap; - std::swap(index, other.index); - std::swap(vertices, other.vertices); - std::swap(deps, other.deps); - std::swap(sync_on, other.sync_on); - } - - /** - * @brief Returns true if a flow builder contains no tasks, false otherwise. - * @return True if the flow builder contains no tasks, false otherwise. - */ - [[nodiscard]] bool empty() const noexcept { - return vertices.empty(); - } - - /** - * @brief Returns the number of tasks. - * @return The number of tasks. - */ - [[nodiscard]] size_type size() const noexcept { - return vertices.size(); - } - - /** - * @brief Binds a task to a flow builder. - * @param value Task identifier. - * @return This flow builder. - */ - basic_flow &bind(const id_type value) { - sync_on += (sync_on == vertices.size()); - const auto it = vertices.emplace(value).first; - index.first() = size_type(it - vertices.begin()); - return *this; - } - - /** - * @brief Turns the current task into a sync point. - * @return This flow builder. - */ - basic_flow &sync() { - ENTT_ASSERT(index.first() < vertices.size(), "Invalid node"); - sync_on = index.first(); - - for(const auto &elem: deps) { - elem.second.emplace_back(sync_on, true); - } - - return *this; - } - - /** - * @brief Assigns a resource to the current task with a given access mode. - * @param res Resource identifier. - * @param is_rw Access mode. - * @return This flow builder. - */ - basic_flow &set(const id_type res, bool is_rw = false) { - emplace(res, is_rw); - return *this; - } - - /** - * @brief Assigns a read-only resource to the current task. - * @param res Resource identifier. - * @return This flow builder. - */ - basic_flow &ro(const id_type res) { - emplace(res, false); - return *this; - } - - /** - * @brief Assigns a range of read-only resources to the current task. - * @tparam It Type of input iterator. - * @param first An iterator to the first element of the range of elements. - * @param last An iterator past the last element of the range of elements. - * @return This flow builder. - */ - template - std::enable_if_t::value_type>, id_type>, basic_flow &> - ro(It first, It last) { - for(; first != last; ++first) { - emplace(*first, false); - } - - return *this; - } - - /** - * @brief Assigns a writable resource to the current task. - * @param res Resource identifier. - * @return This flow builder. - */ - basic_flow &rw(const id_type res) { - emplace(res, true); - return *this; - } - - /** - * @brief Assigns a range of writable resources to the current task. - * @tparam It Type of input iterator. - * @param first An iterator to the first element of the range of elements. - * @param last An iterator past the last element of the range of elements. - * @return This flow builder. - */ - template - std::enable_if_t::value_type>, id_type>, basic_flow &> - rw(It first, It last) { - for(; first != last; ++first) { - emplace(*first, true); - } - - return *this; - } - - /** - * @brief Generates a task graph for the current content. - * @return The adjacency matrix of the task graph. - */ - [[nodiscard]] graph_type graph() const { - graph_type matrix{vertices.size(), get_allocator()}; - - setup_graph(matrix); - transitive_closure(matrix); - transitive_reduction(matrix); - - return matrix; - } - -private: - compressed_pair index; - task_container_type vertices; - deps_container_type deps; - size_type sync_on{}; -}; - -} // namespace entt - -#endif diff --git a/deps/include/entt/graph/fwd.hpp b/deps/include/entt/graph/fwd.hpp deleted file mode 100644 index 5da9749..0000000 --- a/deps/include/entt/graph/fwd.hpp +++ /dev/null @@ -1,27 +0,0 @@ -#ifndef ENTT_GRAPH_FWD_HPP -#define ENTT_GRAPH_FWD_HPP - -#include -#include -#include "../core/fwd.hpp" - -namespace entt { - -/*! @brief Undirected graph category tag. */ -struct directed_tag {}; - -/*! @brief Directed graph category tag. */ -struct undirected_tag: directed_tag {}; - -template> -class adjacency_matrix; - -template> -class basic_flow; - -/*! @brief Alias declaration for the most common use case. */ -using flow = basic_flow<>; - -} // namespace entt - -#endif -- cgit