* [PATCH] gdbsupport: upgrade unordered_dense to v4.9.2
@ 2026-08-18 16:31 Simon Marchi
2026-08-19 5:54 ` Tom de Vries
0 siblings, 1 reply; 3+ messages in thread
From: Simon Marchi @ 2026-08-18 16:31 UTC (permalink / raw)
To: gdb-patches; +Cc: Simon Marchi
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 <martin.ankerl@gmail.com>
+// Copyright (c) 2022 Martin Leitner-Ankerl <martin.ankerl@gmail.com>
//
// 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 <martin.ankerl@gmail.com>
+// Copyright (c) 2022 Martin Leitner-Ankerl <martin.ankerl@gmail.com>
//
// 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
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [PATCH] gdbsupport: upgrade unordered_dense to v4.9.2
2026-08-18 16:31 [PATCH] gdbsupport: upgrade unordered_dense to v4.9.2 Simon Marchi
@ 2026-08-19 5:54 ` Tom de Vries
2026-08-19 12:38 ` Simon Marchi
0 siblings, 1 reply; 3+ messages in thread
From: Tom de Vries @ 2026-08-19 5:54 UTC (permalink / raw)
To: Simon Marchi, gdb-patches
On 8/18/26 6:31 PM, Simon Marchi wrote:
Hi Simon,
thanks for taking care of this.
> Ppotentially interesting new features:
Typo.
I also noticed the 2022-2024 -> 2022 change. I went to look for the
source of that, but the commit changing that doesn't explicitly mention
it, it just says "bump version to 4.8.1".
Anyway, I verified that the version in this patch is indeed v4.9.2.
Acked-By: Tom de Vries <tdevries@suse.de>
Thanks,
- Tom
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] gdbsupport: upgrade unordered_dense to v4.9.2
2026-08-19 5:54 ` Tom de Vries
@ 2026-08-19 12:38 ` Simon Marchi
0 siblings, 0 replies; 3+ messages in thread
From: Simon Marchi @ 2026-08-19 12:38 UTC (permalink / raw)
To: Tom de Vries, gdb-patches
On 8/19/26 1:54 AM, Tom de Vries wrote:
> On 8/18/26 6:31 PM, Simon Marchi wrote:
>
> Hi Simon,
>
> thanks for taking care of this.
>
>> Ppotentially interesting new features:
>
> Typo.
>
> I also noticed the 2022-2024 -> 2022 change. I went to look for the source of that, but the commit changing that doesn't explicitly mention it, it just says "bump version to 4.8.1".
Huh yeah, strange. In any case, we're just copying the files as-is.
> Anyway, I verified that the version in this patch is indeed v4.9.2.
>
> Acked-By: Tom de Vries <tdevries@suse.de>
Thanks, I'll push to master, since I think it's relatively low risk.
And if it introduces any problem, it likely won't be found by review
but by testing.
Simon
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-08-19 12:38 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-08-18 16:31 [PATCH] gdbsupport: upgrade unordered_dense to v4.9.2 Simon Marchi
2026-08-19 5:54 ` Tom de Vries
2026-08-19 12:38 ` Simon Marchi
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox