[PATCH] gdbsupport: upgrade unordered_dense to v4.9.2
Simon Marchi <[email protected]>
| Newsgroups | gmane.comp.gdb.patches |
|---|---|
| Message-ID | <[email protected]> |
Synchronize with upstream [1], tag v4.9.2 (commit aa9af528227ab).
There is one change I am particularly happy about (even though it
doesn't change anything functionally), because I did file the issue for
that:
👉 A default-constructed map allocates nothing, and copying or move-
assigning an empty one drops two further allocations.
Ppotentially interesting new features:
👉 map.hash_for(key) returns a precomputed hash that find, contains,
count, equal_range and at now accept, so it's now possible for
repeated lookups of the same key to hash it only once.
👉 hash_is_avalanching<Hash> can be used to mark a third-party
hash as high quality without editing it, or as false_type to force
mixing on a hash that overpromises. The only way to mark a hash as
avalanching before that was to define the is_avalanching type in the
hash type itself.
Behaviour changes that could affect us:
👉 The is_avalanching marker is now read as a compile-time bool, the way
Boost.Unordered reads it. "using is_avalanching = std::false_type;"
previously meant yes here and now correctly means no. "= void" still
works. Anything else is now a compile error rather than a guess.
There are some claimed performance improvements, and some bug fixes, but
nothing that I could see for things we actually use.
I did a test run on Linux, didn't spot any regression.
[1] https://github.com/martinus/unordered_dense/
Change-Id: I8b2dda1a74b59f78a7dcc9f1b1931a03e8781393
---
gdbsupport/unordered_dense/stl.h | 8 +-
gdbsupport/unordered_dense/unordered_dense.h | 1037 +++++++++++++++---
2 files changed, 873 insertions(+), 172 deletions(-)
diff --git a/gdbsupport/unordered_dense/stl.h b/gdbsupport/unordered_dense/stl.h
index 8c198773195e..2389d0c8cf0a 100644
--- a/gdbsupport/unordered_dense/stl.h
+++ b/gdbsupport/unordered_dense/stl.h
@@ -1,12 +1,12 @@
///////////////////////// ankerl::unordered_dense::{map, set} /////////////////////////
// A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion.
-// Version 4.8.0
+// Version 4.9.2
// https://github.com/martinus/unordered_dense
//
// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
// SPDX-License-Identifier: MIT
-// Copyright (c) 2022-2024 Martin Leitner-Ankerl <[email protected]>
+// Copyright (c) 2022 Martin Leitner-Ankerl <[email protected]>
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
@@ -77,7 +77,9 @@
#if defined(_MSC_VER) && defined(_M_X64)
# include <intrin.h>
-# pragma intrinsic(_umul128)
+# if !defined(_M_ARM64EC)
+# pragma intrinsic(_umul128)
+# endif
#endif
#endif
diff --git a/gdbsupport/unordered_dense/unordered_dense.h b/gdbsupport/unordered_dense/unordered_dense.h
index 56383b6ce8f7..58bb57da12ca 100644
--- a/gdbsupport/unordered_dense/unordered_dense.h
+++ b/gdbsupport/unordered_dense/unordered_dense.h
@@ -1,12 +1,12 @@
///////////////////////// ankerl::unordered_dense::{map, set} /////////////////////////
// A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion.
-// Version 4.8.0
+// Version 4.9.2
// https://github.com/martinus/unordered_dense
//
// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
// SPDX-License-Identifier: MIT
-// Copyright (c) 2022-2024 Martin Leitner-Ankerl <[email protected]>
+// Copyright (c) 2022 Martin Leitner-Ankerl <[email protected]>
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
@@ -31,8 +31,8 @@
// see https://semver.org/spec/v2.0.0.html
#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 4 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes
-#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 8 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
-#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
+#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 9 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
+#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 2 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
// API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/
@@ -70,6 +70,13 @@
# define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
#endif
+// data prefetch hint, a no-op when not supported
+#if defined(__GNUC__) || defined(__clang__)
+# define ANKERL_UNORDERED_DENSE_PREFETCH(addr) __builtin_prefetch(addr) // NOLINT(cppcoreguidelines-macro-usage)
+#else
+# define ANKERL_UNORDERED_DENSE_PREFETCH(addr) static_cast<void>(addr) // NOLINT(cppcoreguidelines-macro-usage)
+#endif
+
#if defined(__clang__) && defined(__has_attribute)
# if __has_attribute(__no_sanitize__)
# define ANKERL_UNORDERED_DENSE_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK \
@@ -212,28 +219,35 @@ inline void mum(std::uint64_t* a, std::uint64_t* b) {
static constexpr auto secret = std::array{UINT64_C(0xa0761d6478bd642f),
UINT64_C(0xe7037ed1a0b428db),
UINT64_C(0x8ebc6af09c88c6e3),
- UINT64_C(0x589965cc75374cc3)};
+ UINT64_C(0x589965cc75374cc3),
+ UINT64_C(0x2d358dccaa6c78a5),
+ UINT64_C(0x8bb84b93962eacc9),
+ UINT64_C(0x4b33a62ed433d4a3)};
- auto const* p = static_cast<uint8_t const*>(key);
+ auto const* p = static_cast<std::uint8_t const*>(key);
std::uint64_t seed = secret[0];
std::uint64_t a{};
std::uint64_t b{};
if (ANKERL_UNORDERED_DENSE_LIKELY(len <= 16))
ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
- if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 4))
+ if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 8))
ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
- a = (r4(p) << 32U) | r4(p + ((len >> 3U) << 2U));
- b = (r4(p + len - 4) << 32U) | r4(p + len - 4 - ((len >> 3U) << 2U));
+ // two (potentially overlapping) 8 byte reads cover the whole input
+ a = r8(p);
+ b = r8(p + len - 8);
}
- else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0))
+ else if (len >= 4) {
+ a = r4(p);
+ b = r4(p + len - 4);
+ } else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0))
ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
+ // b stays zero: r3 packs all len bytes it is given into a, and there are at
+ // most three of them.
a = r3(p, len);
- b = 0;
}
- else {
- a = 0;
- b = 0;
- }
+ // ... and an empty input needs no branch of its own: it hashes whatever a and b were
+ // declared with, which is the zero it has to be. Assigning it again here is what a
+ // deletion sweep of this file kept pointing at.
}
else {
std::size_t i = len;
@@ -241,14 +255,41 @@ inline void mum(std::uint64_t* a, std::uint64_t* b) {
ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
std::uint64_t see1 = seed;
std::uint64_t see2 = seed;
- do {
+ if (i > 96) {
+ // 6 independent lanes: twice the instruction level parallelism of the 48 byte loop below
+ std::uint64_t see3 = seed;
+ std::uint64_t see4 = seed;
+ std::uint64_t see5 = seed;
+ do {
+ seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
+ see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
+ see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
+ see3 = mix(r8(p + 48) ^ secret[4], r8(p + 56) ^ see3);
+ see4 = mix(r8(p + 64) ^ secret[5], r8(p + 72) ^ see4);
+ see5 = mix(r8(p + 80) ^ secret[6], r8(p + 88) ^ see5);
+ p += 96;
+ i -= 96;
+ } while (ANKERL_UNORDERED_DENSE_LIKELY(i > 96));
+ seed ^= see3 ^ see4 ^ see5;
+ }
+ while (i > 48) {
seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
p += 48;
i -= 48;
- } while (ANKERL_UNORDERED_DENSE_LIKELY(i > 48));
+ }
seed ^= see1 ^ see2;
+ while (i > 16) {
+ seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
+ i -= 16;
+ p += 16;
+ }
+
+ // the tail lane only depends on the input, not on seed, so it can execute in parallel
+ // with the lane loops above, and a single dependent mix finishes the hash
+ auto tail = mix(r8(p + i - 16) ^ secret[2], r8(p + i - 8) ^ secret[3]);
+ return mix(secret[1] ^ len, seed ^ tail);
}
while (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 16))
ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
@@ -269,6 +310,85 @@ inline void mum(std::uint64_t* a, std::uint64_t* b) {
} // namespace detail::wyhash
+namespace detail {
+
+struct nonesuch {};
+
+template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
+struct detector {
+ using value_t = std::false_type;
+ using type = Default;
+};
+
+template <class Default, template <class...> class Op, class... Args>
+struct detector<Default, std::void_t<Op<Args...>>, Op, Args...> {
+ using value_t = std::true_type;
+ using type = Op<Args...>;
+};
+
+template <template <class...> class Op, class... Args>
+using is_detected = typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
+
+template <template <class...> class Op, class... Args>
+constexpr bool is_detected_v = is_detected<Op, Args...>::value;
+
+template <typename>
+constexpr bool dependent_false = false;
+
+template <typename T>
+using detect_avalanching = typename T::is_avalanching;
+
+// The member written as a value instead of a type, which is the near miss that would otherwise
+// answer "not avalanching" and say nothing about why.
+template <typename T>
+using detect_avalanching_as_value = decltype((void)T::is_avalanching);
+
+template <typename T>
+using detect_bool_value = std::enable_if_t<std::is_convertible_v<decltype(T::value), bool>>;
+
+// What a hash's is_avalanching member means. void is this library's spelling, and Boost's original
+// one; a type carrying a compile time bool is what Boost's documentation asks for now. Saying
+// std::false_type there has to mean no rather than yes -- reading the member as a bare "it is
+// there" would take a hash that declares itself ordinary and use it unmixed, which is the one
+// answer that costs the table its distribution.
+//
+// Anything else is a mistake, and is said to be one rather than guessed at.
+template <typename Hash>
+[[nodiscard]] constexpr auto is_avalanching_member() -> bool {
+ if constexpr (!is_detected_v<detect_avalanching, Hash>) {
+ static_assert(!is_detected_v<detect_avalanching_as_value, Hash>,
+ "is_avalanching must be a type: write 'using is_avalanching = std::true_type;' "
+ "rather than 'static constexpr bool is_avalanching = true;'");
+ return false;
+ } else if constexpr (std::is_void_v<detect_avalanching<Hash>>) {
+ return true;
+ } else if constexpr (is_detected_v<detect_bool_value, detect_avalanching<Hash>>) {
+ return static_cast<bool>(detect_avalanching<Hash>::value);
+ } else {
+ static_assert(dependent_false<Hash>,
+ "is_avalanching must be void, or a type with a compile time bool value such "
+ "as std::true_type or std::false_type");
+ return false;
+ }
+}
+
+} // namespace detail
+
+// Whether a hash is high quality -- every bit of its result independently well distributed -- so
+// that a table can index with those bits as they come instead of mixing them first. The default
+// answer is the member typedef a hash can carry, `using is_avalanching = void;` or the equivalent
+// `= std::true_type`. For a hash you cannot edit, specialize this instead; `std::false_type` is
+// allowed too, and forces the mixing back on for a hash that promises more than it delivers.
+//
+// Deliberately the same name, the same two ways of answering and the same meaning as Boost's
+// boost::hash_is_avalanching, so that a hash annotated for either library is read correctly by the
+// other. See README 3.2.7.
+template <typename Hash>
+struct hash_is_avalanching : std::bool_constant<detail::is_avalanching_member<Hash>()> {};
+
+template <typename Hash>
+constexpr bool hash_is_avalanching_v = hash_is_avalanching<Hash>::value;
+
template <typename T, typename Enable = void>
struct hash {
auto operator()(T const& obj) const noexcept(noexcept(std::declval<std::hash<T>>().operator()(std::declval<T const&>())))
@@ -277,8 +397,12 @@ struct hash {
}
};
+// Asked of hash_is_avalanching rather than of std::hash<T>::is_avalanching directly, so that there
+// is one reader of the marker and not two: a std::hash spelling its marker the way Boost asks, or
+// named avalanching by a specialization because it cannot be edited, reaches the table through here
+// as well.
template <typename T>
-struct hash<T, typename std::hash<T>::is_avalanching> {
+struct hash<T, std::enable_if_t<hash_is_avalanching_v<std::hash<T>>>> {
using is_avalanching = void;
auto operator()(T const& obj) const noexcept(noexcept(std::declval<std::hash<T>>().operator()(std::declval<T const&>())))
-> std::uint64_t {
@@ -334,7 +458,7 @@ struct hash<Enum, typename std::enable_if_t<std::is_enum_v<Enum>>> {
using is_avalanching = void;
auto operator()(Enum e) const noexcept -> std::uint64_t {
using underlying = std::underlying_type_t<Enum>;
- return detail::wyhash::hash(static_cast<underlying>(e));
+ return detail::wyhash::hash(static_cast<std::uint64_t>(static_cast<underlying>(e)));
}
};
@@ -446,30 +570,8 @@ ANKERL_UNORDERED_DENSE_PACK(struct big {
namespace detail {
-struct nonesuch {};
struct default_container_t {};
-template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
-struct detector {
- using value_t = std::false_type;
- using type = Default;
-};
-
-template <class Default, template <class...> class Op, class... Args>
-struct detector<Default, std::void_t<Op<Args...>>, Op, Args...> {
- using value_t = std::true_type;
- using type = Op<Args...>;
-};
-
-template <template <class...> class Op, class... Args>
-using is_detected = typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
-
-template <template <class...> class Op, class... Args>
-constexpr bool is_detected_v = is_detected<Op, Args...>::value;
-
-template <typename T>
-using detect_avalanching = typename T::is_avalanching;
-
template <typename T>
using detect_is_transparent = typename T::is_transparent;
@@ -504,8 +606,52 @@ struct base_table_type_map {
// base type for set doesn't have mapped_type
struct base_table_type_set {};
+// A key's hash, finalized and ready for a table to index with, as produced by hash_for(). See the
+// lookup section of table for what it is for; this is spelled table::precomputed_hash.
+//
+// Templated on the hasher and nothing else, because the hasher is all a hash depends on: a map, a
+// set and a segmented_map that hash the key the same way can pass one around between them. It is a
+// type of its own rather than a plain integer so that an integer does not convert to it by
+// accident -- in particular what hash_function() returns, which is not this number.
+template <typename Hash>
+struct precomputed_hash {
+ std::uint64_t m_mixed_hash;
+};
+
} // namespace detail
+// A hash that has to be a high quality one, for a codebase where they all are meant to be and
+// forgetting to say so is the easy mistake:
+//
+// template <class Key, class T>
+// using my_map = ankerl::unordered_dense::map<Key, T, require_avalanching<my_hash<Key>>>;
+//
+// Written into the alias rather than next to the hash so that the check is part of what the map
+// is, and survives my_hash being reimplemented without its marker.
+//
+// It inherits, which is what keeps the hash's own operator() overloads and its is_transparent, and
+// costs nothing: the wrapper is the same size as the hash and compiles to the same code.
+template <typename Hash>
+struct require_avalanching : Hash {
+ static_assert(hash_is_avalanching_v<Hash>,
+ "hash is not avalanching: give it 'using is_avalanching = void;', or specialize "
+ "ankerl::unordered_dense::hash_is_avalanching for it, or stop requiring it here");
+ static_assert(!std::is_final_v<Hash>,
+ "hash is final, so it cannot be wrapped: specialize "
+ "ankerl::unordered_dense::hash_is_avalanching for it instead");
+
+ require_avalanching() = default;
+
+ // So that a stateful hash can be handed over by value as well as braced into place -- an
+ // aggregate would take require_avalanching<H>{h} but not require_avalanching<H>(h).
+ explicit require_avalanching(Hash const& hash)
+ : Hash(hash) {}
+
+ // Restated rather than inherited, because a hash named avalanching by a specialization of
+ // hash_is_avalanching has no member typedef to inherit.
+ using is_avalanching = void;
+};
+
// Very much like std::deque, but faster for indexing (in most cases). As of now this doesn't implement the full std::vector
// API, but merely what's necessary to work as an underlying container for ankerl::unordered_dense::{map, set}.
// It allocates blocks of equal size and puts them into the m_blocks vector. That means it can grow simply by adding a new
@@ -530,6 +676,16 @@ class segmented_vector {
private:
using vec_alloc = typename std::allocator_traits<Allocator>::template rebind_alloc<pointer>;
+ using vec_alloc_traits = std::allocator_traits<vec_alloc>;
+
+ // The allocator lives in m_blocks, so these are what the assignment operators below act on --
+ // and what their noexcept specifications are written over, so that the condition and the
+ // promise cannot drift apart.
+ static constexpr bool propagates_on_copy_assign = vec_alloc_traits::propagate_on_container_copy_assignment::value;
+ static constexpr bool propagates_on_move_assign = vec_alloc_traits::propagate_on_container_move_assignment::value;
+ static constexpr bool allocators_always_equal = vec_alloc_traits::is_always_equal::value;
+ static constexpr bool propagates_on_swap = vec_alloc_traits::propagate_on_container_swap::value;
+
std::vector<pointer, vec_alloc> m_blocks{};
std::size_t m_size{};
@@ -564,7 +720,11 @@ class segmented_vector {
using value_type = segmented_vector::value_type;
using reference = std::conditional_t<IsConst, value_type const&, value_type&>;
using pointer = std::conditional_t<IsConst, segmented_vector::const_pointer, segmented_vector::pointer>;
- using iterator_category = std::forward_iterator_tag;
+ // Everything a random access iterator needs is right here -- the position is an index, so jumping and
+ // subtracting are single operations. Saying "forward" instead meant std::distance walked the whole container
+ // one element at a time to compute what operator-() answers directly, and every algorithm that requires
+ // random access, std::sort over values() among them, was ill-formed over an iterator that can do the job.
+ using iterator_category = std::random_access_iterator_tag;
iter_t() noexcept = default;
@@ -611,17 +771,25 @@ class segmented_vector {
return {m_data, static_cast<std::size_t>(static_cast<difference_type>(m_idx) + diff)};
}
+ // n + it, which a random access iterator has to support just as it + n does
+ [[nodiscard]] friend constexpr auto operator+(difference_type diff, iter_t const& it) noexcept -> iter_t {
+ return it + diff;
+ }
+
+ // The cast is the one operator+() already does. Nothing instantiated these two before, because no algorithm
+ // could reach them through a forward iterator, so the implicit signed-to-unsigned conversion sat here
+ // unnoticed until clang's -Wsign-conversion saw std::sort use it.
constexpr auto operator+=(difference_type diff) noexcept -> iter_t& {
- m_idx += diff;
+ m_idx = static_cast<std::size_t>(static_cast<difference_type>(m_idx) + diff);
return *this;
}
[[nodiscard]] constexpr auto operator-(difference_type diff) const noexcept -> iter_t {
- return {m_data, static_cast<size_t>(static_cast<difference_type>(m_idx) - diff)};
+ return {m_data, static_cast<std::size_t>(static_cast<difference_type>(m_idx) - diff)};
}
constexpr auto operator-=(difference_type diff) noexcept -> iter_t& {
- m_idx -= diff;
+ m_idx = static_cast<std::size_t>(static_cast<difference_type>(m_idx) - diff);
return *this;
}
@@ -634,6 +802,10 @@ class segmented_vector {
return m_data[m_idx >> num_bits][m_idx & mask];
}
+ [[nodiscard]] constexpr auto operator[](difference_type diff) const noexcept -> reference {
+ return *(*this + diff);
+ }
+
constexpr auto operator->() const noexcept -> pointer {
return &m_data[m_idx >> num_bits][m_idx & mask];
}
@@ -672,6 +844,16 @@ class segmented_vector {
// slow path: need to allocate a new segment every once in a while
void increase_capacity() {
auto ba = Allocator(m_blocks.get_allocator());
+
+ // Room for the pointer first. push_back is the other thing here that can throw -- it
+ // reallocates -- and it used to do so with the block already allocated and owned by
+ // nobody, which leaked it. Reserving first means the only allocation still outstanding
+ // when something fails is one that has not happened yet, and the push_back below cannot
+ // fail because the capacity is already there. Grow geometrically to avoid reallocation
+ // on every new segment.
+ if (m_blocks.size() == m_blocks.capacity()) {
+ m_blocks.reserve((std::max)(std::size_t{1}, m_blocks.capacity() * 2));
+ }
pointer block = std::allocator_traits<Allocator>::allocate(ba, num_elements_in_block);
m_blocks.push_back(block);
}
@@ -703,9 +885,9 @@ class segmented_vector {
return (capacity + num_elements_in_block - 1U) / num_elements_in_block;
}
- void resize_shrink(size_t new_size) {
+ void resize_shrink(std::size_t new_size) {
if constexpr (!std::is_trivially_destructible_v<T>) {
- for (size_t ix = new_size; ix < m_size; ++ix) {
+ for (std::size_t ix = new_size; ix < m_size; ++ix) {
operator[](ix).~T();
}
}
@@ -719,9 +901,19 @@ class segmented_vector {
segmented_vector(Allocator alloc)
: m_blocks(vec_alloc(alloc)) {}
- segmented_vector(segmented_vector&& other, Allocator alloc)
- : segmented_vector(alloc) {
- *this = std::move(other);
+ // Uses alloc, unconditionally -- that is the whole point of an extended move constructor. It
+ // used to delegate to move assignment, which cannot express it: assignment has to consult
+ // propagate_on_container_move_assignment, so with a propagating allocator it adopted other's
+ // and the allocator the caller named was quietly dropped.
+ segmented_vector(segmented_vector&& other, Allocator alloc) noexcept(allocators_always_equal)
+ : m_blocks(vec_alloc(alloc)) {
+ if (allocators_always_equal || alloc == other.get_allocator()) {
+ // Nothing to move element by element, the blocks just change hands.
+ m_blocks = std::move(other.m_blocks);
+ m_size = std::exchange(other.m_size, {});
+ } else {
+ append_everything_from(std::move(other));
+ }
}
segmented_vector(segmented_vector const& other, Allocator alloc)
@@ -732,7 +924,8 @@ class segmented_vector {
segmented_vector(segmented_vector&& other) noexcept
: segmented_vector(std::move(other), other.get_allocator()) {}
- segmented_vector(segmented_vector const& other) {
+ segmented_vector(segmented_vector const& other)
+ : m_blocks(vec_alloc_traits::select_on_container_copy_construction(other.m_blocks.get_allocator())) {
append_everything_from(other);
}
@@ -741,19 +934,42 @@ class segmented_vector {
return *this;
}
clear();
+ if constexpr (propagates_on_copy_assign) {
+ if (m_blocks.get_allocator() != other.m_blocks.get_allocator()) {
+ // Everything still held has to go back through the old allocator before the new
+ // one is adopted. Copy assignment and not move: which of the two propagates is
+ // the inner vector's own pocca/pocma, and only pocca is known true here, so
+ // assigning a temporary would consult pocma and silently keep the old allocator.
+ dealloc();
+ auto const empty_with_other_allocator = std::vector<pointer, vec_alloc>(other.m_blocks.get_allocator());
+ m_blocks = empty_with_other_allocator;
+ }
+ }
append_everything_from(other);
return *this;
}
- auto operator=(segmented_vector&& other) noexcept -> segmented_vector& {
+ // Not unconditionally noexcept. When the allocator neither propagates nor compares equal --
+ // std::pmr::polymorphic_allocator, for one -- the elements are moved one at a time into memory
+ // this container allocates, so running out of it here has to be allowed to throw rather than
+ // terminate. std::vector spells the condition the same way.
+ auto operator=(segmented_vector&& other) noexcept(propagates_on_move_assign || allocators_always_equal)
+ -> segmented_vector& {
+ if (this == &other) {
+ return *this;
+ }
clear();
- dealloc();
- if (other.get_allocator() == get_allocator()) {
+ // Either the allocator comes along with the blocks or it is already the same one, and
+ // either way the blocks can be taken over; std::vector's own move assignment does the
+ // propagating in the first case.
+ if (propagates_on_move_assign || m_blocks.get_allocator() == other.m_blocks.get_allocator()) {
+ dealloc();
m_blocks = std::move(other.m_blocks);
m_size = std::exchange(other.m_size, {});
} else {
- // make sure to construct with other's allocator!
- m_blocks = std::vector<pointer, vec_alloc>(vec_alloc(other.get_allocator()));
+ // Keeps its own allocator, because nothing said to take other's -- so the blocks it
+ // already holds came from that same allocator and are reused rather than handed back
+ // and immediately asked for again.
append_everything_from(std::move(other));
}
return *this;
@@ -824,25 +1040,25 @@ class segmented_vector {
}
}
- void resize(size_t const count) {
+ void resize(std::size_t const count) {
if (count < m_size) {
resize_shrink(count);
} else if (count > m_size) {
- size_t const new_elems = count - m_size;
+ std::size_t const new_elems = count - m_size;
reserve(count);
- for (size_t ix = 0; ix < new_elems; ++ix) {
+ for (std::size_t ix = 0; ix < new_elems; ++ix) {
emplace_back();
}
}
}
- void resize(size_t const count, value_type const& value) {
+ void resize(std::size_t const count, value_type const& value) {
if (count < m_size) {
resize_shrink(count);
} else if (count > m_size) {
- size_t const new_elems = count - m_size;
+ std::size_t const new_elems = count - m_size;
reserve(count);
- for (size_t ix = 0; ix < new_elems; ++ix) {
+ for (std::size_t ix = 0; ix < new_elems; ++ix) {
emplace_back(value);
}
}
@@ -852,6 +1068,22 @@ class segmented_vector {
return allocator_type{m_blocks.get_allocator()};
}
+ // Exchanging two pointers and a size, and the inner vector's own swap exchanges the allocators
+ // exactly when propagate_on_container_swap says to -- so this answers the allocator question
+ // the way std::vector does, and a map gets the same answer whichever container backs it.
+ // Without a member swap, std::swap fell back to a move construction and two move assignments:
+ // O(n) for an operation that needs none, able to throw from inside a noexcept swap, and a
+ // different answer from the flat container for the same map.
+ void swap(segmented_vector& other) noexcept(propagates_on_swap || allocators_always_equal) {
+ using std::swap;
+ swap(m_blocks, other.m_blocks);
+ swap(m_size, other.m_size);
+ }
+
+ friend void swap(segmented_vector& a, segmented_vector& b) noexcept(noexcept(a.swap(b))) {
+ a.swap(b);
+ }
+
template <class... Args>
auto emplace_back(Args&&... args) -> reference {
if (m_size == capacity()) {
@@ -917,6 +1149,15 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
static constexpr std::uint8_t initial_shifts = 64 - 2; // 2^(64-m_shift) number of buckets
static constexpr float default_max_load_factor = 0.8F;
+ // Named, and covering both containers, so that the promise and the recovery that exists for
+ // when the promise cannot be made are spelled the same way and cannot drift apart -- the same
+ // reason segmented_vector names its propagation traits. Covering only m_values would be wrong
+ // twice over: it would leave m_buckets free to throw out of a noexcept function, and it would
+ // compile a rethrow into one, which gcc rejects outright.
+ static constexpr bool move_assign_is_nothrow =
+ std::is_nothrow_move_assignable_v<value_container_type> && std::is_nothrow_move_assignable_v<bucket_container_type> &&
+ std::is_nothrow_move_assignable_v<Hash> && std::is_nothrow_move_assignable_v<KeyEqual>;
+
public:
using key_type = Key;
using value_type = typename value_container_type::value_type;
@@ -933,6 +1174,11 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
using iterator = std::conditional_t<is_map_v<T>, typename value_container_type::iterator, const_iterator>;
using bucket_type = Bucket;
+ // What hash_for() returns; see the lookup section below. Shared by every table with this
+ // hasher, whatever else it is made of, because that is exactly the set of tables the hash is
+ // good for.
+ using precomputed_hash = detail::precomputed_hash<Hash>;
+
private:
using value_idx_type = decltype(Bucket::m_value_idx);
using dist_and_fingerprint_type = decltype(Bucket::m_dist_and_fingerprint);
@@ -940,21 +1186,33 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
static_assert(std::is_trivially_destructible_v<Bucket>, "assert there's no need to call destructor / std::destroy");
static_assert(std::is_trivially_copyable_v<Bucket>, "assert we can just memset / memcpy");
+ // m_dist_and_fingerprint packs two fields into one integer, and these are what keeps them from
+ // reaching into each other. A bucket type is something a user can supply, so this is checked
+ // here rather than assumed.
+ //
+ // The fingerprint has to stay strictly below dist_inc. A mask that overlaps it lets hash bits
+ // add to the distance a bucket claims, which silently reorders the robin hood sequence that
+ // every probe depends on -- and a mask that reaches the bit above turns a fresh bucket into one
+ // that reads as further from home than it is. Fewer fingerprint bits than dist_inc allows is
+ // merely a weaker fingerprint, so the bound is one-sided.
+ static_assert(Bucket::fingerprint_mask < Bucket::dist_inc,
+ "the fingerprint must fit strictly below dist_inc, or it changes the distance");
+ // And dist_inc has to be a single bit, because the distance is incremented by adding it: two
+ // bits set would carry into the fingerprint on the very first step away from home.
+ static_assert(0 != Bucket::dist_inc && 0 == (Bucket::dist_inc & (Bucket::dist_inc - 1)),
+ "dist_inc must be a power of two, so that adding it only touches the distance");
+
value_container_type m_values{}; // Contains all the key-value pairs in one densely stored container. No holes.
bucket_container_type m_buckets{};
std::size_t m_max_bucket_capacity = 0;
+ value_idx_type m_bucket_mask = 0; // bucket_count() - 1; works because bucket_count() is always a power of two
float m_max_load_factor = default_max_load_factor;
Hash m_hash{};
KeyEqual m_equal{};
std::uint8_t m_shifts = initial_shifts;
[[nodiscard]] auto next(value_idx_type bucket_idx) const -> value_idx_type {
- if (ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U == bucket_count()))
- ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
- return 0;
- }
-
- return static_cast<value_idx_type>(bucket_idx + 1U);
+ return static_cast<value_idx_type>((bucket_idx + 1U) & m_bucket_mask);
}
// Helper to access bucket through pointer types
@@ -978,7 +1236,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
// The goal of mixed_hash is to always produce a high quality 64bit hash.
template <typename K>
[[nodiscard]] constexpr auto mixed_hash(K const& key) const -> std::uint64_t {
- if constexpr (is_detected_v<detect_avalanching, Hash>) {
+ if constexpr (hash_is_avalanching_v<Hash>) {
// we know that the hash is good because is_avalanching.
if constexpr (sizeof(decltype(m_hash(key))) < sizeof(std::uint64_t)) {
// 32bit hash and is_avalanching => multiply with a constant to avalanche bits upwards
@@ -1023,21 +1281,26 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
void place_and_shift_up(Bucket bucket, value_idx_type place) {
+ // cache mask in a local so the bucket stores can't alias it
+ auto const mask = m_bucket_mask;
while (0 != at(m_buckets, place).m_dist_and_fingerprint) {
bucket = std::exchange(at(m_buckets, place), bucket);
bucket.m_dist_and_fingerprint = dist_inc(bucket.m_dist_and_fingerprint);
- place = next(place);
+ place = static_cast<value_idx_type>((place + 1U) & mask);
}
at(m_buckets, place) = bucket;
}
void erase_and_shift_down(value_idx_type bucket_idx) {
+ // cache mask in a local so the bucket stores can't alias it
+ auto const mask = m_bucket_mask;
+
// shift down until either empty or an element with correct spot is found
- auto next_bucket_idx = next(bucket_idx);
+ auto next_bucket_idx = static_cast<value_idx_type>((bucket_idx + 1U) & mask);
while (at(m_buckets, next_bucket_idx).m_dist_and_fingerprint >= Bucket::dist_inc * 2) {
auto& next_bucket = at(m_buckets, next_bucket_idx);
at(m_buckets, bucket_idx) = {dist_dec(next_bucket.m_dist_and_fingerprint), next_bucket.m_value_idx};
- bucket_idx = std::exchange(next_bucket_idx, next(next_bucket_idx));
+ bucket_idx = std::exchange(next_bucket_idx, static_cast<value_idx_type>((next_bucket_idx + 1U) & mask));
}
at(m_buckets, bucket_idx) = {};
}
@@ -1048,7 +1311,16 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
[[nodiscard]] constexpr auto calc_shifts_for_size(std::size_t s) const -> std::uint8_t {
auto shifts = initial_shifts;
- while (shifts > 0 && static_cast<std::size_t>(static_cast<float>(calc_num_buckets(shifts)) * max_load_factor()) < s) {
+ // Stopping once the array is as large as it may get is what keeps this from running off the
+ // end. calc_num_buckets() saturates at max_bucket_count(), so past that point the capacity
+ // being compared stops growing while the loop keeps decrementing -- and for any size above
+ // max_bucket_count() * max_load_factor() it used to walk all the way to zero. A shift of
+ // zero then asks calc_num_buckets() for `1 << 64`, which is undefined and in practice one:
+ // a table sized for billions of elements would come back with a single bucket and a mask of
+ // zero, and the next probe reads past the end of it. Reachable from rehash(), which does not
+ // allocate the values and so has nothing to fail first.
+ while (shifts > 0 && calc_num_buckets(shifts) < max_bucket_count() &&
+ static_cast<std::size_t>(static_cast<float>(calc_num_buckets(shifts)) * max_load_factor()) < s) {
--shifts;
}
return shifts;
@@ -1058,22 +1330,113 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
void copy_buckets(table const& other) {
// assumes m_values has already the correct data copied over.
if (empty()) {
- // when empty, at least allocate an initial buckets and clear them.
- allocate_buckets_from_shift();
- clear_buckets();
+ // Nothing to index, so stay in the state a default constructed table is in and let the
+ // first insert allocate. Copying an empty table therefore allocates nothing either.
+ m_shifts = initial_shifts;
} else {
- m_shifts = other.m_shifts;
- allocate_buckets_from_shift();
if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
+ allocate_buckets_from_shift(other.m_shifts);
for (auto i = 0UL; i < bucket_count(); ++i) {
at(m_buckets, i) = at(other.m_buckets, i);
}
} else {
- std::memcpy(m_buckets.data(), other.m_buckets.data(), sizeof(Bucket) * bucket_count());
+ // One pass, not two. This used to grow the array with resize(), which value
+ // initialises every bucket it adds, and then memcpy over all of it -- so every byte
+ // of the bucket array was written twice, and for a large map the wasted half is a
+ // memset of megabytes. assign() copies straight into the new storage.
+ //
+ // assign() and not m_buckets = other.m_buckets, which would consult pocca: the
+ // allocator question is answered by the caller, and this is also reached from the
+ // move assignment's differing-allocator branch, where adopting other's would be
+ // exactly wrong.
+ m_buckets.assign(other.m_buckets.begin(), other.m_buckets.end());
+ m_shifts = other.m_shifts;
+ describe_buckets(m_buckets.size());
}
}
}
+ // The part of copy assignment that can throw, kept separate so the operator can put the table
+ // back together if it does.
+ void copy_everything_from(table const& other) {
+ // The assignment below takes other's allocator (pocca), and the buckets have to follow it,
+ // or the container's two halves end up on different allocators and get_allocator() -- which
+ // reports m_values' -- stops describing the bucket array, which the "same allocator" check
+ // in the move assignment relies on it doing.
+ //
+ // Done before the copy rather than after: it is the same allocator either way, both
+ // containers are empty here so it cannot throw, and doing it first means a copy that fails
+ // part way through cannot leave the two halves disagreeing. Copy assignment and not move:
+ // move would consult pocma, a different question, and not the one answered true here.
+ if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value) {
+ // Rebound explicitly: m_values' allocator and m_buckets' are different types, and
+ // comparing them directly is ambiguous rather than merely unusual.
+ auto const wanted = typename bucket_container_type::allocator_type(other.m_values.get_allocator());
+ if (m_buckets.get_allocator() != wanted) {
+ auto const empty_with_other_allocator = bucket_container_type(wanted);
+ m_buckets = empty_with_other_allocator;
+ }
+ }
+
+ m_values = other.m_values;
+ m_max_load_factor = other.m_max_load_factor;
+ m_hash = other.m_hash;
+ m_equal = other.m_equal;
+ copy_buckets(other); // sets m_shifts on both of its branches
+ }
+
+ // The half of move assignment that can throw, so the caller can put the table back together if
+ // it does. Its twin for copies is above.
+ // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved) -- moved from member by member
+ void move_everything_from(table&& other) {
+ m_values = std::move(other.m_values);
+ other.m_values.clear();
+
+ // we can only reuse m_buckets when both maps have the same allocator!
+ if (get_allocator() == other.get_allocator()) {
+ m_buckets = std::move(other.m_buckets);
+ other.m_buckets.clear();
+ m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
+ m_bucket_mask = std::exchange(other.m_bucket_mask, 0);
+ m_shifts = std::exchange(other.m_shifts, initial_shifts);
+ m_max_load_factor = std::exchange(other.m_max_load_factor, default_max_load_factor);
+ m_hash = std::exchange(other.m_hash, {});
+ m_equal = std::exchange(other.m_equal, {});
+ // The exchanges above leave "other" exactly as a default constructed table looks, so it
+ // is already usable and does not need buckets handed back to it. It used to get a
+ // freshly allocated set here, which is an allocation -- and a way to throw -- inside an
+ // operation that is otherwise noexcept and needs neither.
+ } else {
+ // set max_load_factor *before* copying the other's buckets, so we have the same behavior
+ m_max_load_factor = other.m_max_load_factor;
+
+ // copy_buckets sets m_buckets, m_num_buckets, m_max_bucket_capacity, m_shifts
+ copy_buckets(other);
+ // clear's the other's buckets so other is now already usable.
+ other.clear_buckets();
+ m_hash = other.m_hash;
+ m_equal = other.m_equal;
+ }
+ // map "other" is now already usable, it's empty.
+ }
+
+ // Back to what a default constructed table holds. An assignment gives the buckets back before
+ // it knows whether it can build new ones, and in between the table holds values it has no way
+ // to find -- size() elements and no bucket array at all, which no operation is prepared for. If
+ // an exception leaves that window this is where it lands: assignment owes the basic guarantee,
+ // which means valid and not merely non-leaking, and with no buckets the only valid state is
+ // empty. Every step is noexcept, so the recovery cannot fail on its way out.
+ // Deliberately not deallocate_buckets(), which is otherwise the same three stores: that one
+ // also calls shrink_to_fit(), which is allowed to allocate and is not noexcept, and this runs
+ // while an exception is already in flight.
+ void reset_to_empty() noexcept {
+ m_values.clear();
+ m_buckets.clear();
+ m_max_bucket_capacity = 0;
+ m_bucket_mask = 0;
+ m_shifts = initial_shifts;
+ }
+
/**
* True when no element can be added any more without increasing the size
*/
@@ -1085,20 +1448,57 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
m_buckets.clear();
m_buckets.shrink_to_fit();
m_max_bucket_capacity = 0;
+ m_bucket_mask = 0;
}
- void allocate_buckets_from_shift() {
- auto num_buckets = calc_num_buckets(m_shifts);
+ // Takes the shift rather than reading m_shifts, so that nothing describing the bucket array is
+ // written until an array of that size exists. Callers used to assign m_shifts and then
+ // allocate, which left a gap for a failed allocation to stop in.
+ void allocate_buckets_from_shift(std::uint8_t shifts) {
+ auto num_buckets = calc_num_buckets(shifts);
if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
- if constexpr (has_reserve<bucket_container_type>) {
- m_buckets.reserve(num_buckets);
- }
- for (std::size_t i = m_buckets.size(); i < num_buckets; ++i) {
- m_buckets.emplace_back();
+ if (num_buckets < m_buckets.size()) {
+ // Shrinking, which rehash does. This used to work because the caller emptied the
+ // array first and the loop below then grew it from nothing; without that it would
+ // keep the larger size. Shrinking rather than emptying is what keeps the array and
+ // the mask agreeing at every point: it hands memory back instead of asking for it,
+ // so unlike a clear-then-regrow it has no failure to stop in.
+ m_buckets.resize(num_buckets);
+ } else {
+ if constexpr (has_reserve<bucket_container_type>) {
+ m_buckets.reserve(num_buckets);
+ }
+ // Growing in place leaves the old buckets where they are, so a failure part way
+ // through leaves an array that is merely larger than the mask below describes,
+ // which nothing reads.
+ for (std::size_t i = m_buckets.size(); i < num_buckets; ++i) {
+ m_buckets.emplace_back();
+ }
}
} else {
- m_buckets.resize(num_buckets);
+ // Built beside the old array rather than over it, so that a failure here leaves the
+ // table exactly as it was. Callers used to give the old array back first, which made
+ // this the only allocation alive -- and made a failure leave them holding values with
+ // no buckets to find them by, which is not a state anything can recover from without
+ // allocating again.
+ auto fresh = bucket_container_type(m_buckets.get_allocator());
+ fresh.resize(num_buckets);
+ m_buckets = std::move(fresh);
}
+ // All three commit here, together, and only once the array they describe exists. They have
+ // to move as one: do_find indexes its first probe with hash >> m_shifts and does not mask,
+ // so a shift that has run ahead of the array reads past the end of it, and a mask published
+ // ahead of an allocation that then failed does the same. This is the one function every
+ // bucket-allocating path goes through, which is what makes a failed growth leave the old
+ // buckets intact and consistent rather than unusable.
+ m_shifts = shifts;
+ describe_buckets(num_buckets);
+ }
+
+ // The two values derived from the bucket array's size. Only ever called once the array of that
+ // size exists; see the note above.
+ void describe_buckets(std::size_t num_buckets) {
+ m_bucket_mask = static_cast<value_idx_type>(num_buckets - 1);
if (num_buckets == max_bucket_count()) {
// reached the maximum, make sure we can use each bucket
m_max_bucket_capacity = max_bucket_count();
@@ -1107,7 +1507,29 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
}
+ // The bucket array is not allocated until the first element goes in, so that a default
+ // constructed table does not allocate. Every path that probes the buckets either returns early
+ // while the table is empty (do_find and do_find_hashed's callers, do_erase_key), or needs an
+ // iterator into m_values and so
+ // cannot be reached in this state (erase, extract, replace_key), or calls this first -- which
+ // is the three insert entry points, the only ones that reach the buckets without a prior
+ // emptiness check.
+ void allocate_buckets_if_none() {
+ if (ANKERL_UNORDERED_DENSE_UNLIKELY(0 == bucket_count()))
+ ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
+ allocate_buckets_from_shift(m_shifts);
+ clear_buckets();
+ }
+ }
+
void clear_buckets() {
+ // Reachable now that a table can have no buckets at all -- extract() clears them on the way
+ // out whether or not there are any. data() is null in that state, and memset's pointer has
+ // to be valid even for a zero length. Neither sanitizer in CI objects, so this is on the
+ // language rule rather than on a diagnostic.
+ if (0 == bucket_count()) {
+ return;
+ }
if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
for (auto&& e : m_buckets) {
std::memset(&e, 0, sizeof(e));
@@ -1119,13 +1541,17 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
void clear_and_fill_buckets_from_values() {
clear_buckets();
- for (value_idx_type value_idx = 0, end_idx = static_cast<value_idx_type>(m_values.size()); value_idx < end_idx;
- ++value_idx) {
+ // Counted in std::size_t, for the reason spelled out in replace(): max_size() is exactly
+ // what value_idx_type can hold, so a container of precisely that many has a size that is
+ // not representable in it and the cast wraps to zero. Latent here rather than live -- a
+ // table at max_size() already has the smallest shift, so rehash() and reserve() early out
+ // before reaching this -- but the rule is the same and only one place was following it.
+ for (std::size_t value_idx = 0, end_idx = m_values.size(); value_idx < end_idx; ++value_idx) {
auto const& key = get_key(m_values[value_idx]);
auto [dist_and_fingerprint, bucket] = next_while_less(key);
// we know for certain that key has not yet been inserted, so no need to check it.
- place_and_shift_up({dist_and_fingerprint, value_idx}, bucket);
+ place_and_shift_up({dist_and_fingerprint, static_cast<value_idx_type>(value_idx)}, bucket);
}
}
@@ -1135,28 +1561,37 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
m_values.pop_back();
on_error_bucket_overflow();
}
- --m_shifts;
- if constexpr (!IsSegmented || std::is_same_v<BucketContainer, default_container_t>) {
- deallocate_buckets();
+ // Both callers have already appended the new element to m_values, which is why the branch
+ // above takes it back out before reporting the overflow. A bucket array that cannot be
+ // grown is the same situation: the element is in m_values with no bucket pointing at it,
+ // and never will have one, so size() would count an element that find() cannot reach.
+ // Taking it back out is what makes a failed insert have no effect, which is what the
+ // unordered containers promise for inserting a single element.
+ if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()) {
+ try {
+ allocate_buckets_from_shift(static_cast<std::uint8_t>(m_shifts - 1));
+ } catch (...) {
+ m_values.pop_back();
+ throw;
+ }
+ } else {
+ allocate_buckets_from_shift(static_cast<std::uint8_t>(m_shifts - 1));
}
- allocate_buckets_from_shift();
clear_and_fill_buckets_from_values();
}
- template <typename Op>
- void do_erase(value_idx_type bucket_idx, Op handle_erased_value) {
- auto const value_idx_to_remove = at(m_buckets, bucket_idx).m_value_idx;
- erase_and_shift_down(bucket_idx);
- handle_erased_value(std::move(m_values[value_idx_to_remove]));
-
- // update m_values
+ // Closes the hole that the erased value left in m_values, by moving the last value into it and repointing that
+ // value's bucket. Runs after the erased value has been handed over, and has to run even when handing it over threw:
+ // by that point the bucket is already gone, so leaving the value in place would mean size() counts an element that
+ // nothing can find.
+ void finish_erase(value_idx_type value_idx_to_remove) {
if (value_idx_to_remove != m_values.size() - 1) {
// no luck, we'll have to replace the value with the last one and update the index accordingly
auto& val = m_values[value_idx_to_remove];
val = std::move(m_values.back());
// update the values_idx of the moved entry. No need to play the info game, just look until we find the values_idx
- bucket_idx = bucket_idx_from_hash(mixed_hash(get_key(val)));
+ auto bucket_idx = bucket_idx_from_hash(mixed_hash(get_key(val)));
auto const values_idx_back = static_cast<value_idx_type>(m_values.size() - 1);
while (values_idx_back != at(m_buckets, bucket_idx).m_value_idx) {
bucket_idx = next(bucket_idx);
@@ -1166,6 +1601,33 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
m_values.pop_back();
}
+ template <typename Op>
+ void do_erase(value_idx_type bucket_idx, Op handle_erased_value) {
+ auto const value_idx_to_remove = at(m_buckets, bucket_idx).m_value_idx;
+
+ // both values are needed after the shift down; start fetching them now to overlap the latencies
+ ANKERL_UNORDERED_DENSE_PREFETCH(&m_values[value_idx_to_remove]);
+ ANKERL_UNORDERED_DENSE_PREFETCH(&m_values.back());
+
+ erase_and_shift_down(bucket_idx);
+ auto&& erased_value = std::move(m_values[value_idx_to_remove]);
+
+ // erase() hands the value to a callback that cannot throw, so the branch below is not even instantiated for it.
+ // extract() moves the value out into the caller's storage, and that move is the one that can throw.
+ if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() && !noexcept(handle_erased_value(std::move(erased_value)))) {
+ try {
+ handle_erased_value(std::move(erased_value));
+ } catch (...) {
+ finish_erase(value_idx_to_remove);
+ throw;
+ }
+ } else {
+ handle_erased_value(std::move(erased_value));
+ }
+
+ finish_erase(value_idx_to_remove);
+ }
+
template <typename K, typename Op>
auto do_erase_key(K&& key, Op handle_erased_value) -> std::size_t { // NOLINT(cppcoreguidelines-missing-std-forward)
if (empty()) {
@@ -1218,6 +1680,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
template <typename K, typename... Args>
auto do_try_emplace(K&& key, Args&&... args) -> std::pair<iterator, bool> {
+ allocate_buckets_if_none();
auto hash = mixed_hash(key);
auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
auto bucket_idx = bucket_idx_from_hash(hash);
@@ -1247,7 +1710,14 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
return end();
}
- auto mh = mixed_hash(key);
+ return do_find_hashed(key, mixed_hash(key));
+ }
+
+ // Same lookup with the hashing already done. Requires the bucket array to be allocated, which
+ // !empty() implies; the callers test empty() rather than this function so that a lookup in an
+ // empty table returns without hashing anything.
+ template <typename K>
+ auto do_find_hashed(K const& key, std::uint64_t mh) -> iterator {
auto dist_and_fingerprint = dist_and_fingerprint_from_hash(mh);
auto bucket_idx = bucket_idx_from_hash(mh);
auto* bucket = &at(m_buckets, bucket_idx);
@@ -1286,6 +1756,21 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
return const_cast<table*>(this)->do_find(key); // NOLINT(cppcoreguidelines-pro-type-const-cast)
}
+ template <typename K>
+ auto do_find(K const& key, precomputed_hash ph) -> iterator {
+ if (ANKERL_UNORDERED_DENSE_UNLIKELY(empty()))
+ ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
+ return end();
+ }
+
+ return do_find_hashed(key, ph.m_mixed_hash);
+ }
+
+ template <typename K>
+ auto do_find(K const& key, precomputed_hash ph) const -> const_iterator {
+ return const_cast<table*>(this)->do_find(key, ph); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ }
+
template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
auto do_at(K const& key) -> Q& {
if (auto it = find(key); ANKERL_UNORDERED_DENSE_LIKELY(end() != it))
@@ -1300,6 +1785,20 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
return const_cast<table*>(this)->at(key); // NOLINT(cppcoreguidelines-pro-type-const-cast)
}
+ template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+ auto do_at(K const& key, precomputed_hash ph) -> Q& {
+ if (auto it = find(key, ph); ANKERL_UNORDERED_DENSE_LIKELY(end() != it))
+ ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
+ return it->second;
+ }
+ on_error_key_not_found();
+ }
+
+ template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+ auto do_at(K const& key, precomputed_hash ph) const -> Q const& {
+ return const_cast<table*>(this)->do_at(key, ph); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ }
+
public:
explicit table(std::size_t bucket_count,
Hash const& hash = Hash(),
@@ -1309,11 +1808,11 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
, m_buckets(alloc_or_container)
, m_hash(hash)
, m_equal(equal) {
+ // No bucket_count asked for means no buckets yet: the first insert allocates them. See
+ // allocate_buckets_if_none(). A default constructed table therefore costs no allocation at
+ // all, so one can sit in a scope that may never use it without paying for it.
if (0 != bucket_count) {
reserve(bucket_count);
- } else {
- allocate_buckets_from_shift();
- clear_buckets();
}
}
@@ -1348,23 +1847,60 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
table(InputIt first, InputIt last, size_type bucket_count, Hash const& hash, allocator_type const& alloc)
: table(first, last, bucket_count, hash, KeyEqual(), alloc) {}
+ // Asks the allocator whether it wants to come along, which is what allocator_traits' default
+ // does and what an allocator like std::pmr::polymorphic_allocator declines: a copy of a map
+ // living in an arena should not silently keep that arena alive and keep allocating into it.
table(table const& other)
- : table(other, other.m_values.get_allocator()) {}
+ : table(other,
+ std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.m_values.get_allocator())) {
+ }
+ // m_buckets takes the allocator too. Leaving it to its default member initialiser put the
+ // bucket array in the default resource while the values went where the caller asked, so half
+ // the container escaped the arena it was given -- and get_allocator(), which reports m_values'
+ // allocator, could not be used to reason about the buckets any more.
table(table const& other, allocator_type const& alloc)
: m_values(other.m_values, alloc)
+ , m_buckets(alloc)
, m_max_load_factor(other.m_max_load_factor)
, m_hash(other.m_hash)
, m_equal(other.m_equal) {
copy_buckets(other);
}
+ // Unconditionally noexcept, and honestly so: it hands over other's own allocator, so the
+ // assignment below always takes the branch that takes the buffers over rather than the one
+ // that moves elements into freshly allocated memory.
table(table&& other) noexcept
: table(std::move(other), other.m_values.get_allocator()) {}
- table(table&& other, allocator_type const& alloc) noexcept
- : m_values(alloc) {
- *this = std::move(other);
+ // Uses alloc, unconditionally. It used to construct empty and then move-assign, which cannot
+ // express that: assignment has to consult propagate_on_container_move_assignment, so with a
+ // propagating allocator this ended up holding other's and the allocator the caller asked for
+ // was quietly dropped -- while std::vector, given the same allocator, kept it.
+ //
+ // Not unconditionally noexcept, unlike the plain move constructor above: this is the one whose
+ // whole purpose is a *differing* allocator, so the containers below may have to move the
+ // elements one at a time, and that allocates. The specification is theirs.
+ // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved) -- moved from member by member
+ table(table&& other, allocator_type const& alloc) noexcept(
+ std::is_nothrow_constructible_v<value_container_type, value_container_type&&, allocator_type const&> &&
+ std::is_nothrow_constructible_v<bucket_container_type, bucket_container_type&&, allocator_type const&> &&
+ std::is_nothrow_move_constructible_v<Hash> && std::is_nothrow_move_constructible_v<KeyEqual>)
+ : m_values(std::move(other.m_values), alloc)
+ , m_buckets(std::move(other.m_buckets), alloc)
+ , m_max_bucket_capacity(std::exchange(other.m_max_bucket_capacity, 0))
+ , m_bucket_mask(std::exchange(other.m_bucket_mask, 0))
+ , m_max_load_factor(std::exchange(other.m_max_load_factor, default_max_load_factor))
+ , m_hash(std::move(other.m_hash))
+ , m_equal(std::move(other.m_equal))
+ , m_shifts(std::exchange(other.m_shifts, initial_shifts)) {
+ // When the allocators differ the two containers above moved element by element, so other
+ // still holds them. Either way it has to come out of this as an empty, usable table, which
+ // the exchanges above have already made the rest of it -- and an empty table needs no
+ // buckets, so this hands nothing back to it.
+ other.m_values.clear();
+ other.m_buckets.clear();
}
table(std::initializer_list<value_type> ilist,
@@ -1387,48 +1923,47 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
auto operator=(table const& other) -> table& {
if (&other != this) {
deallocate_buckets(); // deallocate before m_values is set (might have another allocator)
- m_values = other.m_values;
- m_max_load_factor = other.m_max_load_factor;
- m_hash = other.m_hash;
- m_equal = other.m_equal;
- m_shifts = initial_shifts;
- copy_buckets(other);
+
+ // Copying the values, and building the buckets for them, both allocate. Until both have
+ // happened the table holds values with no buckets to find them by; a throw in there
+ // used to leave it that way, so size() counted elements that find() could not reach and
+ // the next lookup probed a bucket array that was not there. See reset_to_empty().
+ if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()) {
+ try {
+ copy_everything_from(other);
+ } catch (...) {
+ reset_to_empty();
+ throw;
+ }
+ } else {
+ copy_everything_from(other);
+ }
}
return *this;
}
- auto operator=(table&& other) noexcept(noexcept(std::is_nothrow_move_assignable_v<value_container_type> &&
- std::is_nothrow_move_assignable_v<Hash> &&
- std::is_nothrow_move_assignable_v<KeyEqual>)) -> table& {
+ // The condition used to be wrapped in another noexcept(), which asks whether evaluating a bool expression can
+ // throw. It cannot, so the specification was noexcept(true) whatever the traits said, and a type with a throwing
+ // move assignment terminated instead of propagating.
+ auto operator=(table&& other) noexcept(move_assign_is_nothrow) -> table& {
if (&other != this) {
deallocate_buckets(); // deallocate before m_values is set (might have another allocator)
- m_values = std::move(other.m_values);
- other.m_values.clear();
- // we can only reuse m_buckets when both maps have the same allocator!
- if (get_allocator() == other.get_allocator()) {
- m_buckets = std::move(other.m_buckets);
- other.m_buckets.clear();
- m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
- m_shifts = std::exchange(other.m_shifts, initial_shifts);
- m_max_load_factor = std::exchange(other.m_max_load_factor, default_max_load_factor);
- m_hash = std::exchange(other.m_hash, {});
- m_equal = std::exchange(other.m_equal, {});
- other.allocate_buckets_from_shift();
- other.clear_buckets();
+ // Same window as the copy assignment above, and reachable for the same reason: with an
+ // allocator that neither propagates nor compares equal the move below moves the
+ // elements one at a time into memory it has to allocate. See reset_to_empty().
+ // Exactly when this operator does not promise noexcept, which is what makes the
+ // recovery reachable rather than a rethrow inside a noexcept function.
+ if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() && !move_assign_is_nothrow) {
+ try {
+ move_everything_from(std::move(other));
+ } catch (...) {
+ reset_to_empty();
+ throw;
+ }
} else {
- // set max_load_factor *before* copying the other's buckets, so we have the same
- // behavior
- m_max_load_factor = other.m_max_load_factor;
-
- // copy_buckets sets m_buckets, m_num_buckets, m_max_bucket_capacity, m_shifts
- copy_buckets(other);
- // clear's the other's buckets so other is now already usable.
- other.clear_buckets();
- m_hash = other.m_hash;
- m_equal = other.m_equal;
+ move_everything_from(std::move(other));
}
- // map "other" is now already usable, it's empty.
}
return *this;
}
@@ -1490,8 +2025,10 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
// modifiers //////////////////////////////////////////////////////////////
void clear() {
- m_values.clear();
- clear_buckets();
+ if (!empty()) {
+ m_values.clear();
+ clear_buckets();
+ }
}
auto insert(value_type const& value) -> std::pair<iterator, bool> {
@@ -1535,7 +2072,14 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
// nonstandard API: *this is emptied.
// Also see "A Standard flat_map" https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0429r9.pdf
auto extract() && -> value_container_type {
- return std::move(m_values);
+ auto values = std::move(m_values);
+
+ // Moving the values out does not empty the buckets, and they index into the container that just left. Emptying
+ // them here is what makes "*this is emptied" true: without it the table looks empty -- size() is 0, find()
+ // returns end() -- and then the next insert probes a bucket pointing at an element that is no longer there.
+ m_values.clear();
+ clear_buckets();
+ return values;
}
// nonstandard API:
@@ -1547,19 +2091,23 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
auto shifts = calc_shifts_for_size(container.size());
if (0 == bucket_count() || shifts < m_shifts || container.get_allocator() != m_values.get_allocator()) {
- m_shifts = shifts;
- deallocate_buckets();
- allocate_buckets_from_shift();
+ allocate_buckets_from_shift(shifts);
}
clear_buckets();
m_values = std::move(container);
// can't use clear_and_fill_buckets_from_values() because container elements might not be unique
- auto value_idx = value_idx_type{};
+ //
+ // Counted in std::size_t rather than in value_idx_type. max_size() is exactly the number
+ // values that type can hold, so a container of precisely that many has a size that is not
+ // representable in it: the cast wrapped to zero, the loop below never ran once, and the
+ // table came back reporting size() elements with no bucket pointing at any of them. Every
+ // index the loop produces is representable -- it is the count that is not.
+ auto value_idx = std::size_t{};
// loop until we reach the end of the container. duplicated entries will be replaced with back().
- while (value_idx != static_cast<value_idx_type>(m_values.size())) {
+ while (value_idx != m_values.size()) {
auto const& key = get_key(m_values[value_idx]);
auto hash = mixed_hash(key);
@@ -1582,12 +2130,12 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
if (key_found) {
- if (value_idx != static_cast<value_idx_type>(m_values.size() - 1)) {
+ if (value_idx != m_values.size() - 1) {
m_values[value_idx] = std::move(m_values.back());
}
m_values.pop_back();
} else {
- place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
+ place_and_shift_up({dist_and_fingerprint, static_cast<value_idx_type>(value_idx)}, bucket_idx);
++value_idx;
}
}
@@ -1640,6 +2188,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
typename KE = KeyEqual,
std::enable_if_t<!is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
auto emplace(K&& key) -> std::pair<iterator, bool> {
+ allocate_buckets_if_none();
auto hash = mixed_hash(key);
auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
auto bucket_idx = bucket_idx_from_hash(hash);
@@ -1660,6 +2209,8 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
template <class... Args>
auto emplace(Args&&... args) -> std::pair<iterator, bool> {
+ allocate_buckets_if_none();
+
// we have to instantiate the value_type to be able to access the key.
// 1. emplace_back the object so it is constructed. 2. If the key is already there, pop it later in the loop.
auto& key = get_key(m_values.emplace_back(std::forward<Args>(args)...));
@@ -1802,7 +2353,9 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
bucket_idx = next(bucket_idx);
}
- do_erase(bucket_idx, [](value_type const& /*unused*/) {
+ // The noexcept here and on the other two erase callbacks is what keeps erase() out of do_erase()'s exception
+ // guard: a call expression is noexcept only if the callee says so, an empty body is not enough.
+ do_erase(bucket_idx, [](value_type const& /*unused*/) noexcept -> void {
});
return begin() + static_cast<difference_type>(value_idx_to_remove);
}
@@ -1817,7 +2370,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
auto tmp = std::optional<value_type>{};
- do_erase(bucket_idx, [&tmp](value_type&& val) {
+ do_erase(bucket_idx, [&tmp](value_type&& val) -> void {
tmp = std::move(val);
});
return std::move(tmp).value();
@@ -1858,13 +2411,13 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
auto erase(Key const& key) -> std::size_t {
- return do_erase_key(key, [](value_type const& /*unused*/) {
+ return do_erase_key(key, [](value_type const& /*unused*/) noexcept -> void {
});
}
auto extract(Key const& key) -> std::optional<value_type> {
auto tmp = std::optional<value_type>{};
- do_erase_key(key, [&tmp](value_type&& val) {
+ do_erase_key(key, [&tmp](value_type&& val) -> void {
tmp = std::move(val);
});
return tmp;
@@ -1872,23 +2425,42 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
auto erase(K&& key) -> std::size_t {
- return do_erase_key(std::forward<K>(key), [](value_type const& /*unused*/) {
+ return do_erase_key(std::forward<K>(key), [](value_type const& /*unused*/) noexcept -> void {
});
}
template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
auto extract(K&& key) -> std::optional<value_type> {
auto tmp = std::optional<value_type>{};
- do_erase_key(std::forward<K>(key), [&tmp](value_type&& val) {
+ do_erase_key(std::forward<K>(key), [&tmp](value_type&& val) -> void {
tmp = std::move(val);
});
return tmp;
}
- void swap(table& other) noexcept(noexcept(std::is_nothrow_swappable_v<value_container_type> &&
- std::is_nothrow_swappable_v<Hash> && std::is_nothrow_swappable_v<KeyEqual>)) {
+ void swap(table& other) noexcept(std::is_nothrow_swappable_v<value_container_type> &&
+ std::is_nothrow_swappable_v<bucket_container_type> && std::is_nothrow_swappable_v<Hash> &&
+ std::is_nothrow_swappable_v<KeyEqual>) {
+ // There is no free swap() for table, so "swap(other, *this)" used to resolve to the generic std::swap: three
+ // move assignments, each of which hands the moved-from table a freshly allocated set of buckets. That is three
+ // allocations for an operation that needs none, and three ways to throw out of a noexcept function.
+ //
+ // segmented_vector has a swap of its own now, so both container choices answer the allocator
+ // question the same way; see its definition for what the generic std::swap did instead.
+ //
+ // Calling it as a member rather than unqualified is not what fixes that -- the free swap
+ // beside it is found by ADL just the same. It is so that a BucketContainer supplied from
+ // some other namespace cannot quietly fall back to the three-move std::swap: every
+ // container is required to have the member, none is required to have the free function.
+ m_values.swap(other.m_values);
+ m_buckets.swap(other.m_buckets);
using std::swap;
- swap(other, *this);
+ swap(m_max_bucket_capacity, other.m_max_bucket_capacity);
+ swap(m_bucket_mask, other.m_bucket_mask);
+ swap(m_max_load_factor, other.m_max_load_factor);
+ swap(m_hash, other.m_hash);
+ swap(m_equal, other.m_equal);
+ swap(m_shifts, other.m_shifts);
}
// lookup /////////////////////////////////////////////////////////////////
@@ -1998,6 +2570,127 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
return {it, it == end() ? end() : it + 1};
}
+ // lookup with a precomputed hash /////////////////////////////////////////
+
+ // Looking the same key up over and over -- a handful of string literals against a map parsed
+ // out of a document, say -- hashes it every time, and for a long key that hashing is most of
+ // the cost of the lookup. Hashing it once instead is what hash_for() and these overloads are
+ // for:
+ //
+ // auto const h = map.hash_for("some-long-key"); // once
+ // auto it = map.find("some-long-key", h); // as often as you like
+ //
+ // The key is still needed, because a lookup that found a bucket still has to compare keys to
+ // know it found the right one. What is saved is the hashing, not the comparison.
+ //
+ // The number a lookup wants is the one hash_for() returns, and nothing else: it is the hasher's
+ // output finalized the way a lookup finalizes it, which for most hashers is not the same number
+ // the hasher gave. An integer will not convert to a precomputed_hash, which is the mistake
+ // worth blocking; the value inside stays open, since a caller may want to keep or move one.
+ // Every table with this hasher takes it, so one hash can serve a map and a set together, and a
+ // stateless hasher makes it good for the life of the program. What it does not survive is the
+ // key changing -- pass the hash of a different key and the lookup quietly finds nothing.
+ //
+ // Only lookups take one. Insertion never will: a lookup handed the wrong hash merely misses,
+ // while an insertion handed one files the element under a probe chain it is not on, which
+ // loses it for good and lets a second copy of the same key in beside it. Erase is left out for
+ // a duller reason -- it hashes the moved element as well as the key, so precomputing the key's
+ // hash saves it only half its hashing.
+ [[nodiscard]] auto hash_for(Key const& key) const -> precomputed_hash {
+ return {mixed_hash(key)};
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ [[nodiscard]] auto hash_for(K const& key) const -> precomputed_hash {
+ return {mixed_hash(key)};
+ }
+
+ auto find(Key const& key, precomputed_hash ph) -> iterator {
+ return do_find(key, ph);
+ }
+
+ auto find(Key const& key, precomputed_hash ph) const -> const_iterator {
+ return do_find(key, ph);
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ auto find(K const& key, precomputed_hash ph) -> iterator {
+ return do_find(key, ph);
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ auto find(K const& key, precomputed_hash ph) const -> const_iterator {
+ return do_find(key, ph);
+ }
+
+ auto contains(Key const& key, precomputed_hash ph) const -> bool {
+ return find(key, ph) != end();
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ auto contains(K const& key, precomputed_hash ph) const -> bool {
+ return find(key, ph) != end();
+ }
+
+ auto count(Key const& key, precomputed_hash ph) const -> std::size_t {
+ return find(key, ph) == end() ? 0 : 1;
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ auto count(K const& key, precomputed_hash ph) const -> std::size_t {
+ return find(key, ph) == end() ? 0 : 1;
+ }
+
+ auto equal_range(Key const& key, precomputed_hash ph) -> std::pair<iterator, iterator> {
+ auto it = do_find(key, ph);
+ return {it, it == end() ? end() : it + 1};
+ }
+
+ auto equal_range(Key const& key, precomputed_hash ph) const -> std::pair<const_iterator, const_iterator> {
+ auto it = do_find(key, ph);
+ return {it, it == end() ? end() : it + 1};
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ auto equal_range(K const& key, precomputed_hash ph) -> std::pair<iterator, iterator> {
+ auto it = do_find(key, ph);
+ return {it, it == end() ? end() : it + 1};
+ }
+
+ template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+ auto equal_range(K const& key, precomputed_hash ph) const -> std::pair<const_iterator, const_iterator> {
+ auto it = do_find(key, ph);
+ return {it, it == end() ? end() : it + 1};
+ }
+
+ template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+ auto at(key_type const& key, precomputed_hash ph) -> Q& {
+ return do_at(key, ph);
+ }
+
+ template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+ auto at(key_type const& key, precomputed_hash ph) const -> Q const& {
+ return do_at(key, ph);
+ }
+
+ template <typename K,
+ typename Q = T,
+ typename H = Hash,
+ typename KE = KeyEqual,
+ std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
+ auto at(K const& key, precomputed_hash ph) -> Q& {
+ return do_at(key, ph);
+ }
+
+ template <typename K,
+ typename Q = T,
+ typename H = Hash,
+ typename KE = KeyEqual,
+ std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
+ auto at(K const& key, precomputed_hash ph) const -> Q const& {
+ return do_at(key, ph);
+ }
+
// bucket interface ///////////////////////////////////////////////////////
auto bucket_count() const noexcept -> std::size_t { // NOLINT(modernize-use-nodiscard)
@@ -2019,7 +2712,11 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
void max_load_factor(float ml) {
- m_max_load_factor = ml;
+ // A load factor above 1 is meaningful for a container that chains, and std::unordered_map takes one. Open
+ // addressing cannot use it: m_max_bucket_capacity would exceed bucket_count(), is_full() would never fire, the
+ // table would fill completely, and place_and_shift_up() would then probe forever for an empty bucket that does
+ // not exist. Exactly 1 is fine, because is_full() is checked after the value is appended.
+ m_max_load_factor = (std::min)(ml, 1.0F);
if (bucket_count() != max_bucket_count()) {
m_max_bucket_capacity = static_cast<value_idx_type>(static_cast<float>(bucket_count()) * max_load_factor());
}
@@ -2029,10 +2726,8 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
count = (std::min)(count, max_size());
auto shifts = calc_shifts_for_size((std::max)(count, size()));
if (shifts != m_shifts) {
- m_shifts = shifts;
- deallocate_buckets();
+ allocate_buckets_from_shift(shifts);
m_values.shrink_to_fit();
- allocate_buckets_from_shift();
clear_and_fill_buckets_from_values();
}
}
@@ -2045,9 +2740,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
}
auto shifts = calc_shifts_for_size((std::max)(capa, size()));
if (0 == bucket_count() || shifts < m_shifts) {
- m_shifts = shifts;
- deallocate_buckets();
- allocate_buckets_from_shift();
+ allocate_buckets_from_shift(shifts);
clear_and_fill_buckets_from_values();
}
}
@@ -2096,6 +2789,12 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
friend auto operator!=(table const& a, table const& b) -> bool {
return !(a == b);
}
+
+ // Standard containers provide this, and generic code written as "using std::swap; swap(a, b);" needs it to find
+ // the member. Without it that call lands on the generic std::swap and moves three times.
+ friend void swap(table& a, table& b) noexcept(noexcept(a.swap(b))) {
+ a.swap(b);
+ }
};
} // namespace detail
base-commit: afa6db16e6508d8ea269557085bc7c301e824382
--
2.55.0