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/container/dense_map.hpp | 1043 ----------------------------- 1 file changed, 1043 deletions(-) delete mode 100644 deps/include/entt/container/dense_map.hpp (limited to 'deps/include/entt/container/dense_map.hpp') diff --git a/deps/include/entt/container/dense_map.hpp b/deps/include/entt/container/dense_map.hpp deleted file mode 100644 index 4674761..0000000 --- a/deps/include/entt/container/dense_map.hpp +++ /dev/null @@ -1,1043 +0,0 @@ -#ifndef ENTT_CONTAINER_DENSE_MAP_HPP -#define ENTT_CONTAINER_DENSE_MAP_HPP - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "../config/config.h" -#include "../core/compressed_pair.hpp" -#include "../core/iterator.hpp" -#include "../core/memory.hpp" -#include "../core/bit.hpp" -#include "../core/type_traits.hpp" -#include "fwd.hpp" - -namespace entt { - -/*! @cond TURN_OFF_DOXYGEN */ -namespace internal { - -template -struct dense_map_node final { - using value_type = std::pair; - - template - dense_map_node(const std::size_t pos, Args &&...args) - : next{pos}, - element{std::forward(args)...} {} - - template - dense_map_node(std::allocator_arg_t, const Allocator &allocator, const std::size_t pos, Args &&...args) - : next{pos}, - element{entt::make_obj_using_allocator(allocator, std::forward(args)...)} {} - - template - dense_map_node(std::allocator_arg_t, const Allocator &allocator, const dense_map_node &other) - : next{other.next}, - element{entt::make_obj_using_allocator(allocator, other.element)} {} - - template - dense_map_node(std::allocator_arg_t, const Allocator &allocator, dense_map_node &&other) - : next{other.next}, - element{entt::make_obj_using_allocator(allocator, std::move(other.element))} {} - - std::size_t next; - value_type element; -}; - -template -class dense_map_iterator final { - template - friend class dense_map_iterator; - - using first_type = decltype(std::as_const(std::declval()->element.first)); - using second_type = decltype((std::declval()->element.second)); - -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::random_access_iterator_tag; - - constexpr dense_map_iterator() noexcept - : it{} {} - - constexpr dense_map_iterator(const It iter) noexcept - : it{iter} {} - - template && std::is_constructible_v>> - constexpr dense_map_iterator(const dense_map_iterator &other) noexcept - : it{other.it} {} - - constexpr dense_map_iterator &operator++() noexcept { - return ++it, *this; - } - - constexpr dense_map_iterator operator++(int) noexcept { - dense_map_iterator orig = *this; - return ++(*this), orig; - } - - constexpr dense_map_iterator &operator--() noexcept { - return --it, *this; - } - - constexpr dense_map_iterator operator--(int) noexcept { - dense_map_iterator orig = *this; - return operator--(), orig; - } - - constexpr dense_map_iterator &operator+=(const difference_type value) noexcept { - it += value; - return *this; - } - - constexpr dense_map_iterator operator+(const difference_type value) const noexcept { - dense_map_iterator copy = *this; - return (copy += value); - } - - constexpr dense_map_iterator &operator-=(const difference_type value) noexcept { - return (*this += -value); - } - - constexpr dense_map_iterator operator-(const difference_type value) const noexcept { - return (*this + -value); - } - - [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept { - return {it[value].element.first, it[value].element.second}; - } - - [[nodiscard]] constexpr pointer operator->() const noexcept { - return operator*(); - } - - [[nodiscard]] constexpr reference operator*() const noexcept { - return operator[](0); - } - - template - friend constexpr std::ptrdiff_t operator-(const dense_map_iterator &, const dense_map_iterator &) noexcept; - - template - friend constexpr bool operator==(const dense_map_iterator &, const dense_map_iterator &) noexcept; - - template - friend constexpr bool operator<(const dense_map_iterator &, const dense_map_iterator &) noexcept; - -private: - It it; -}; - -template -[[nodiscard]] constexpr std::ptrdiff_t operator-(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return lhs.it - rhs.it; -} - -template -[[nodiscard]] constexpr bool operator==(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return lhs.it == rhs.it; -} - -template -[[nodiscard]] constexpr bool operator!=(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return !(lhs == rhs); -} - -template -[[nodiscard]] constexpr bool operator<(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return lhs.it < rhs.it; -} - -template -[[nodiscard]] constexpr bool operator>(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return rhs < lhs; -} - -template -[[nodiscard]] constexpr bool operator<=(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return !(lhs > rhs); -} - -template -[[nodiscard]] constexpr bool operator>=(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { - return !(lhs < rhs); -} - -template -class dense_map_local_iterator final { - template - friend class dense_map_local_iterator; - - using first_type = decltype(std::as_const(std::declval()->element.first)); - using second_type = decltype((std::declval()->element.second)); - -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 dense_map_local_iterator() noexcept - : it{}, - offset{} {} - - constexpr dense_map_local_iterator(It iter, const std::size_t pos) noexcept - : it{iter}, - offset{pos} {} - - template && std::is_constructible_v>> - constexpr dense_map_local_iterator(const dense_map_local_iterator &other) noexcept - : it{other.it}, - offset{other.offset} {} - - constexpr dense_map_local_iterator &operator++() noexcept { - return offset = it[offset].next, *this; - } - - constexpr dense_map_local_iterator operator++(int) noexcept { - dense_map_local_iterator orig = *this; - return ++(*this), orig; - } - - [[nodiscard]] constexpr pointer operator->() const noexcept { - return operator*(); - } - - [[nodiscard]] constexpr reference operator*() const noexcept { - return {it[offset].element.first, it[offset].element.second}; - } - - [[nodiscard]] constexpr std::size_t index() const noexcept { - return offset; - } - -private: - It it; - std::size_t offset; -}; - -template -[[nodiscard]] constexpr bool operator==(const dense_map_local_iterator &lhs, const dense_map_local_iterator &rhs) noexcept { - return lhs.index() == rhs.index(); -} - -template -[[nodiscard]] constexpr bool operator!=(const dense_map_local_iterator &lhs, const dense_map_local_iterator &rhs) noexcept { - return !(lhs == rhs); -} - -} // namespace internal -/*! @endcond */ - -/** - * @brief Associative container for key-value pairs with unique keys. - * - * Internally, elements are organized into buckets. Which bucket an element is - * placed into depends entirely on the hash of its key. Keys with the same hash - * code appear in the same bucket. - * - * @tparam Key Key type of the associative container. - * @tparam Type Mapped type of the associative container. - * @tparam Hash Type of function to use to hash the keys. - * @tparam KeyEqual Type of function to use to compare the keys for equality. - * @tparam Allocator Type of allocator used to manage memory and elements. - */ -template -class dense_map { - static constexpr float default_threshold = 0.875f; - static constexpr std::size_t minimum_capacity = 8u; - - using node_type = internal::dense_map_node; - using alloc_traits = std::allocator_traits; - static_assert(std::is_same_v>, "Invalid value type"); - using sparse_container_type = std::vector>; - using packed_container_type = std::vector>; - - template - [[nodiscard]] std::size_t key_to_bucket(const Other &key) const noexcept { - return fast_mod(static_cast(sparse.second()(key)), bucket_count()); - } - - template - [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) { - for(auto it = begin(bucket), last = end(bucket); it != last; ++it) { - if(packed.second()(it->first, key)) { - return begin() + static_cast(it.index()); - } - } - - return end(); - } - - template - [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) const { - for(auto it = cbegin(bucket), last = cend(bucket); it != last; ++it) { - if(packed.second()(it->first, key)) { - return cbegin() + static_cast(it.index()); - } - } - - return cend(); - } - - template - [[nodiscard]] auto insert_or_do_nothing(Other &&key, Args &&...args) { - const auto index = key_to_bucket(key); - - if(auto it = constrained_find(key, index); it != end()) { - return std::make_pair(it, false); - } - - packed.first().emplace_back(sparse.first()[index], std::piecewise_construct, std::forward_as_tuple(std::forward(key)), std::forward_as_tuple(std::forward(args)...)); - sparse.first()[index] = packed.first().size() - 1u; - rehash_if_required(); - - return std::make_pair(--end(), true); - } - - template - [[nodiscard]] auto insert_or_overwrite(Other &&key, Arg &&value) { - const auto index = key_to_bucket(key); - - if(auto it = constrained_find(key, index); it != end()) { - it->second = std::forward(value); - return std::make_pair(it, false); - } - - packed.first().emplace_back(sparse.first()[index], std::forward(key), std::forward(value)); - sparse.first()[index] = packed.first().size() - 1u; - rehash_if_required(); - - return std::make_pair(--end(), true); - } - - void move_and_pop(const std::size_t pos) { - if(const auto last = size() - 1u; pos != last) { - size_type *curr = &sparse.first()[key_to_bucket(packed.first().back().element.first)]; - packed.first()[pos] = std::move(packed.first().back()); - for(; *curr != last; curr = &packed.first()[*curr].next) {} - *curr = pos; - } - - packed.first().pop_back(); - } - - void rehash_if_required() { - if(size() > (bucket_count() * max_load_factor())) { - rehash(bucket_count() * 2u); - } - } - -public: - /*! @brief Allocator type. */ - using allocator_type = Allocator; - /*! @brief Key type of the container. */ - using key_type = Key; - /*! @brief Mapped type of the container. */ - using mapped_type = Type; - /*! @brief Key-value type of the container. */ - using value_type = std::pair; - /*! @brief Unsigned integer type. */ - using size_type = std::size_t; - /*! @brief Type of function to use to hash the keys. */ - using hasher = Hash; - /*! @brief Type of function to use to compare the keys for equality. */ - using key_equal = KeyEqual; - /*! @brief Input iterator type. */ - using iterator = internal::dense_map_iterator; - /*! @brief Constant input iterator type. */ - using const_iterator = internal::dense_map_iterator; - /*! @brief Input iterator type. */ - using local_iterator = internal::dense_map_local_iterator; - /*! @brief Constant input iterator type. */ - using const_local_iterator = internal::dense_map_local_iterator; - - /*! @brief Default constructor. */ - dense_map() - : dense_map{minimum_capacity} {} - - /** - * @brief Constructs an empty container with a given allocator. - * @param allocator The allocator to use. - */ - explicit dense_map(const allocator_type &allocator) - : dense_map{minimum_capacity, hasher{}, key_equal{}, allocator} {} - - /** - * @brief Constructs an empty container with a given allocator and user - * supplied minimal number of buckets. - * @param cnt Minimal number of buckets. - * @param allocator The allocator to use. - */ - dense_map(const size_type cnt, const allocator_type &allocator) - : dense_map{cnt, hasher{}, key_equal{}, allocator} {} - - /** - * @brief Constructs an empty container with a given allocator, hash - * function and user supplied minimal number of buckets. - * @param cnt Minimal number of buckets. - * @param hash Hash function to use. - * @param allocator The allocator to use. - */ - dense_map(const size_type cnt, const hasher &hash, const allocator_type &allocator) - : dense_map{cnt, hash, key_equal{}, allocator} {} - - /** - * @brief Constructs an empty container with a given allocator, hash - * function, compare function and user supplied minimal number of buckets. - * @param cnt Minimal number of buckets. - * @param hash Hash function to use. - * @param equal Compare function to use. - * @param allocator The allocator to use. - */ - explicit dense_map(const size_type cnt, const hasher &hash = hasher{}, const key_equal &equal = key_equal{}, const allocator_type &allocator = allocator_type{}) - : sparse{allocator, hash}, - packed{allocator, equal} { - rehash(cnt); - } - - /*! @brief Default copy constructor. */ - dense_map(const dense_map &) = default; - - /** - * @brief Allocator-extended copy constructor. - * @param other The instance to copy from. - * @param allocator The allocator to use. - */ - dense_map(const dense_map &other, const allocator_type &allocator) - : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())}, - packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())}, - threshold{other.threshold} {} - - /*! @brief Default move constructor. */ - dense_map(dense_map &&) noexcept(std::is_nothrow_move_constructible_v> && std::is_nothrow_move_constructible_v>) = default; - - /** - * @brief Allocator-extended move constructor. - * @param other The instance to move from. - * @param allocator The allocator to use. - */ - dense_map(dense_map &&other, const allocator_type &allocator) - : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))}, - packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))}, - threshold{other.threshold} {} - - /*! @brief Default destructor. */ - ~dense_map() noexcept = default; - - /** - * @brief Default copy assignment operator. - * @return This container. - */ - dense_map &operator=(const dense_map &) = default; - - /** - * @brief Default move assignment operator. - * @return This container. - */ - dense_map &operator=(dense_map &&) noexcept(std::is_nothrow_move_assignable_v> && std::is_nothrow_move_assignable_v>) = default; - - /** - * @brief Returns the associated allocator. - * @return The associated allocator. - */ - [[nodiscard]] constexpr allocator_type get_allocator() const noexcept { - return sparse.first().get_allocator(); - } - - /** - * @brief Returns an iterator to the beginning. - * - * If the array is empty, the returned iterator will be equal to `end()`. - * - * @return An iterator to the first instance of the internal array. - */ - [[nodiscard]] const_iterator cbegin() const noexcept { - return packed.first().begin(); - } - - /*! @copydoc cbegin */ - [[nodiscard]] const_iterator begin() const noexcept { - return cbegin(); - } - - /*! @copydoc begin */ - [[nodiscard]] iterator begin() noexcept { - return packed.first().begin(); - } - - /** - * @brief Returns an iterator to the end. - * @return An iterator to the element following the last instance of the - * internal array. - */ - [[nodiscard]] const_iterator cend() const noexcept { - return packed.first().end(); - } - - /*! @copydoc cend */ - [[nodiscard]] const_iterator end() const noexcept { - return cend(); - } - - /*! @copydoc end */ - [[nodiscard]] iterator end() noexcept { - return packed.first().end(); - } - - /** - * @brief Checks whether a container is empty. - * @return True if the container is empty, false otherwise. - */ - [[nodiscard]] bool empty() const noexcept { - return packed.first().empty(); - } - - /** - * @brief Returns the number of elements in a container. - * @return Number of elements in a container. - */ - [[nodiscard]] size_type size() const noexcept { - return packed.first().size(); - } - - /** - * @brief Returns the maximum possible number of elements. - * @return Maximum possible number of elements. - */ - [[nodiscard]] size_type max_size() const noexcept { - return packed.first().max_size(); - } - - /*! @brief Clears the container. */ - void clear() noexcept { - sparse.first().clear(); - packed.first().clear(); - rehash(0u); - } - - /** - * @brief Inserts an element into the container, if the key does not exist. - * @param value A key-value pair eventually convertible to the value type. - * @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 value_type &value) { - return insert_or_do_nothing(value.first, value.second); - } - - /*! @copydoc insert */ - std::pair insert(value_type &&value) { - return insert_or_do_nothing(std::move(value.first), std::move(value.second)); - } - - /** - * @copydoc insert - * @tparam Arg Type of the key-value pair to insert into the container. - */ - template - std::enable_if_t, std::pair> - insert(Arg &&value) { - return insert_or_do_nothing(std::forward(value).first, std::forward(value).second); - } - - /** - * @brief Inserts elements into the container, if their keys do not exist. - * @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. - */ - template - void insert(It first, It last) { - for(; first != last; ++first) { - insert(*first); - } - } - - /** - * @brief Inserts an element into the container or assigns to the current - * element if the key already exists. - * @tparam Arg Type of the value to insert or assign. - * @param key A key used both to look up and to insert if not found. - * @param value A value to insert or assign. - * @return A pair consisting of an iterator to the element and a bool - * denoting whether the insertion took place. - */ - template - std::pair insert_or_assign(const key_type &key, Arg &&value) { - return insert_or_overwrite(key, std::forward(value)); - } - - /*! @copydoc insert_or_assign */ - template - std::pair insert_or_assign(key_type &&key, Arg &&value) { - return insert_or_overwrite(std::move(key), std::forward(value)); - } - - /** - * @brief Constructs an element in-place, if the key does not exist. - * - * The element is also constructed when the container already has the key, - * in which case the newly constructed object is destroyed immediately. - * - * @tparam Args Types of arguments to forward to the constructor of the - * element. - * @param args Arguments to forward to the constructor of the element. - * @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. - */ - template - std::pair emplace([[maybe_unused]] Args &&...args) { - if constexpr(sizeof...(Args) == 0u) { - return insert_or_do_nothing(key_type{}); - } else if constexpr(sizeof...(Args) == 1u) { - return insert_or_do_nothing(std::forward(args).first..., std::forward(args).second...); - } else if constexpr(sizeof...(Args) == 2u) { - return insert_or_do_nothing(std::forward(args)...); - } else { - auto &node = packed.first().emplace_back(packed.first().size(), std::forward(args)...); - const auto index = key_to_bucket(node.element.first); - - if(auto it = constrained_find(node.element.first, index); it != end()) { - packed.first().pop_back(); - return std::make_pair(it, false); - } - - std::swap(node.next, sparse.first()[index]); - rehash_if_required(); - - return std::make_pair(--end(), true); - } - } - - /** - * @brief Inserts in-place if the key does not exist, does nothing if the - * key exists. - * @tparam Args Types of arguments to forward to the constructor of the - * element. - * @param key A key used both to look up and to insert if not found. - * @param args Arguments to forward to the constructor of the element. - * @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. - */ - template - std::pair try_emplace(const key_type &key, Args &&...args) { - return insert_or_do_nothing(key, std::forward(args)...); - } - - /*! @copydoc try_emplace */ - template - std::pair try_emplace(key_type &&key, Args &&...args) { - return insert_or_do_nothing(std::move(key), std::forward(args)...); - } - - /** - * @brief Removes an element from a given position. - * @param pos An iterator to the element to remove. - * @return An iterator following the removed element. - */ - iterator erase(const_iterator pos) { - const auto diff = pos - cbegin(); - erase(pos->first); - return begin() + diff; - } - - /** - * @brief Removes the given elements from a container. - * @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 An iterator following the last removed element. - */ - iterator erase(const_iterator first, const_iterator last) { - const auto dist = first - cbegin(); - - for(auto from = last - cbegin(); from != dist; --from) { - erase(packed.first()[from - 1u].element.first); - } - - return (begin() + dist); - } - - /** - * @brief Removes the element associated with a given key. - * @param key A key value of an element to remove. - * @return Number of elements removed (either 0 or 1). - */ - size_type erase(const key_type &key) { - for(size_type *curr = &sparse.first()[key_to_bucket(key)]; *curr != (std::numeric_limits::max)(); curr = &packed.first()[*curr].next) { - if(packed.second()(packed.first()[*curr].element.first, key)) { - const auto index = *curr; - *curr = packed.first()[*curr].next; - move_and_pop(index); - return 1u; - } - } - - return 0u; - } - - /** - * @brief Exchanges the contents with those of a given container. - * @param other Container to exchange the content with. - */ - void swap(dense_map &other) { - using std::swap; - swap(sparse, other.sparse); - swap(packed, other.packed); - swap(threshold, other.threshold); - } - - /** - * @brief Accesses a given element with bounds checking. - * @param key A key of an element to find. - * @return A reference to the mapped value of the requested element. - */ - [[nodiscard]] mapped_type &at(const key_type &key) { - auto it = find(key); - ENTT_ASSERT(it != end(), "Invalid key"); - return it->second; - } - - /*! @copydoc at */ - [[nodiscard]] const mapped_type &at(const key_type &key) const { - auto it = find(key); - ENTT_ASSERT(it != cend(), "Invalid key"); - return it->second; - } - - /** - * @brief Accesses or inserts a given element. - * @param key A key of an element to find or insert. - * @return A reference to the mapped value of the requested element. - */ - [[nodiscard]] mapped_type &operator[](const key_type &key) { - return insert_or_do_nothing(key).first->second; - } - - /** - * @brief Accesses or inserts a given element. - * @param key A key of an element to find or insert. - * @return A reference to the mapped value of the requested element. - */ - [[nodiscard]] mapped_type &operator[](key_type &&key) { - return insert_or_do_nothing(std::move(key)).first->second; - } - - /** - * @brief Returns the number of elements matching a key (either 1 or 0). - * @param key Key value of an element to search for. - * @return Number of elements matching the key (either 1 or 0). - */ - [[nodiscard]] size_type count(const key_type &key) const { - return find(key) != end(); - } - - /** - * @brief Returns the number of elements matching a key (either 1 or 0). - * @tparam Other Type of the key value of an element to search for. - * @param key Key value of an element to search for. - * @return Number of elements matching the key (either 1 or 0). - */ - template - [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> - count(const Other &key) const { - return find(key) != end(); - } - - /** - * @brief Finds an element with a given key. - * @param key Key value of an element to search for. - * @return An iterator to an element with the given key. If no such element - * is found, a past-the-end iterator is returned. - */ - [[nodiscard]] iterator find(const key_type &key) { - return constrained_find(key, key_to_bucket(key)); - } - - /*! @copydoc find */ - [[nodiscard]] const_iterator find(const key_type &key) const { - return constrained_find(key, key_to_bucket(key)); - } - - /** - * @brief Finds an element with a key that compares _equivalent_ to a given - * key. - * @tparam Other Type of the key value of an element to search for. - * @param key Key value of an element to search for. - * @return An iterator to an element with the given key. If no such element - * is found, a past-the-end iterator is returned. - */ - template - [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> - find(const Other &key) { - return constrained_find(key, key_to_bucket(key)); - } - - /*! @copydoc find */ - template - [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> - find(const Other &key) const { - return constrained_find(key, key_to_bucket(key)); - } - - /** - * @brief Returns a range containing all elements with a given key. - * @param key Key value of an element to search for. - * @return A pair of iterators pointing to the first element and past the - * last element of the range. - */ - [[nodiscard]] std::pair equal_range(const key_type &key) { - const auto it = find(key); - return {it, it + !(it == end())}; - } - - /*! @copydoc equal_range */ - [[nodiscard]] std::pair equal_range(const key_type &key) const { - const auto it = find(key); - return {it, it + !(it == cend())}; - } - - /** - * @brief Returns a range containing all elements that compare _equivalent_ - * to a given key. - * @tparam Other Type of an element to search for. - * @param key Key value of an element to search for. - * @return A pair of iterators pointing to the first element and past the - * last element of the range. - */ - template - [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t>> - equal_range(const Other &key) { - const auto it = find(key); - return {it, it + !(it == end())}; - } - - /*! @copydoc equal_range */ - template - [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t>> - equal_range(const Other &key) const { - const auto it = find(key); - return {it, it + !(it == cend())}; - } - - /** - * @brief Checks if the container contains an element with a given key. - * @param key Key value of an element to search for. - * @return True if there is such an element, false otherwise. - */ - [[nodiscard]] bool contains(const key_type &key) const { - return (find(key) != cend()); - } - - /** - * @brief Checks if the container contains an element with a key that - * compares _equivalent_ to a given value. - * @tparam Other Type of the key value of an element to search for. - * @param key Key value of an element to search for. - * @return True if there is such an element, false otherwise. - */ - template - [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> - contains(const Other &key) const { - return (find(key) != cend()); - } - - /** - * @brief Returns an iterator to the beginning of a given bucket. - * @param index An index of a bucket to access. - * @return An iterator to the beginning of the given bucket. - */ - [[nodiscard]] const_local_iterator cbegin(const size_type index) const { - return {packed.first().begin(), sparse.first()[index]}; - } - - /** - * @brief Returns an iterator to the beginning of a given bucket. - * @param index An index of a bucket to access. - * @return An iterator to the beginning of the given bucket. - */ - [[nodiscard]] const_local_iterator begin(const size_type index) const { - return cbegin(index); - } - - /** - * @brief Returns an iterator to the beginning of a given bucket. - * @param index An index of a bucket to access. - * @return An iterator to the beginning of the given bucket. - */ - [[nodiscard]] local_iterator begin(const size_type index) { - return {packed.first().begin(), sparse.first()[index]}; - } - - /** - * @brief Returns an iterator to the end of a given bucket. - * @param index An index of a bucket to access. - * @return An iterator to the end of the given bucket. - */ - [[nodiscard]] const_local_iterator cend([[maybe_unused]] const size_type index) const { - return {packed.first().begin(), (std::numeric_limits::max)()}; - } - - /** - * @brief Returns an iterator to the end of a given bucket. - * @param index An index of a bucket to access. - * @return An iterator to the end of the given bucket. - */ - [[nodiscard]] const_local_iterator end(const size_type index) const { - return cend(index); - } - - /** - * @brief Returns an iterator to the end of a given bucket. - * @param index An index of a bucket to access. - * @return An iterator to the end of the given bucket. - */ - [[nodiscard]] local_iterator end([[maybe_unused]] const size_type index) { - return {packed.first().begin(), (std::numeric_limits::max)()}; - } - - /** - * @brief Returns the number of buckets. - * @return The number of buckets. - */ - [[nodiscard]] size_type bucket_count() const { - return sparse.first().size(); - } - - /** - * @brief Returns the maximum number of buckets. - * @return The maximum number of buckets. - */ - [[nodiscard]] size_type max_bucket_count() const { - return sparse.first().max_size(); - } - - /** - * @brief Returns the number of elements in a given bucket. - * @param index The index of the bucket to examine. - * @return The number of elements in the given bucket. - */ - [[nodiscard]] size_type bucket_size(const size_type index) const { - return static_cast(std::distance(begin(index), end(index))); - } - - /** - * @brief Returns the bucket for a given key. - * @param key The value of the key to examine. - * @return The bucket for the given key. - */ - [[nodiscard]] size_type bucket(const key_type &key) const { - return key_to_bucket(key); - } - - /** - * @brief Returns the average number of elements per bucket. - * @return The average number of elements per bucket. - */ - [[nodiscard]] float load_factor() const { - return size() / static_cast(bucket_count()); - } - - /** - * @brief Returns the maximum average number of elements per bucket. - * @return The maximum average number of elements per bucket. - */ - [[nodiscard]] float max_load_factor() const { - return threshold; - } - - /** - * @brief Sets the desired maximum average number of elements per bucket. - * @param value A desired maximum average number of elements per bucket. - */ - void max_load_factor(const float value) { - ENTT_ASSERT(value > 0.f, "Invalid load factor"); - threshold = value; - rehash(0u); - } - - /** - * @brief Reserves at least the specified number of buckets and regenerates - * the hash table. - * @param cnt New number of buckets. - */ - void rehash(const size_type cnt) { - auto value = cnt > minimum_capacity ? cnt : minimum_capacity; - const auto cap = static_cast(size() / max_load_factor()); - value = value > cap ? value : cap; - - if(const auto sz = next_power_of_two(value); sz != bucket_count()) { - sparse.first().resize(sz); - - for(auto &&elem: sparse.first()) { - elem = (std::numeric_limits::max)(); - } - - for(size_type pos{}, last = size(); pos < last; ++pos) { - const auto index = key_to_bucket(packed.first()[pos].element.first); - packed.first()[pos].next = std::exchange(sparse.first()[index], pos); - } - } - } - - /** - * @brief Reserves space for at least the specified number of elements and - * regenerates the hash table. - * @param cnt New number of elements. - */ - void reserve(const size_type cnt) { - packed.first().reserve(cnt); - rehash(static_cast(std::ceil(cnt / max_load_factor()))); - } - - /** - * @brief Returns the function used to hash the keys. - * @return The function used to hash the keys. - */ - [[nodiscard]] hasher hash_function() const { - return sparse.second(); - } - - /** - * @brief Returns the function used to compare keys for equality. - * @return The function used to compare keys for equality. - */ - [[nodiscard]] key_equal key_eq() const { - return packed.second(); - } - -private: - compressed_pair sparse; - compressed_pair packed; - float threshold{default_threshold}; -}; - -} // namespace entt - -/*! @cond TURN_OFF_DOXYGEN */ -namespace std { - -template -struct uses_allocator, Allocator> - : std::true_type {}; - -} // namespace std -/*! @endcond */ - -#endif -- cgit