summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/btree_map.h10
-rw-r--r--absl/container/btree_test.cc29
-rw-r--r--absl/container/flat_hash_map.h5
-rw-r--r--absl/container/flat_hash_map_test.cc15
-rw-r--r--absl/container/internal/btree.h7
-rw-r--r--absl/container/internal/common.h7
-rw-r--r--absl/container/internal/container_memory.h15
-rw-r--r--absl/container/internal/hash_policy_traits.h31
-rw-r--r--absl/container/node_hash_map.h5
-rw-r--r--absl/container/node_hash_map_test.cc15
10 files changed, 129 insertions, 10 deletions
diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h
index bb450ead..448ac48a 100644
--- a/absl/container/btree_map.h
+++ b/absl/container/btree_map.h
@@ -325,6 +325,11 @@ class btree_map
// does not contain an element with a matching key, this function returns an
// empty node handle.
//
+ // NOTE: when compiled in an earlier version of C++ than C++17,
+ // `node_type::key()` returns a const reference to the key instead of a
+ // mutable reference. We cannot safely return a mutable reference without
+ // std::launder (which is not available before C++17).
+ //
// NOTE: In this context, `node_type` refers to the C++17 concept of a
// move-only type that owns and provides access to the elements in associative
// containers (https://en.cppreference.com/w/cpp/container/node_handle).
@@ -652,6 +657,11 @@ class btree_multimap
// does not contain an element with a matching key, this function returns an
// empty node handle.
//
+ // NOTE: when compiled in an earlier version of C++ than C++17,
+ // `node_type::key()` returns a const reference to the key instead of a
+ // mutable reference. We cannot safely return a mutable reference without
+ // std::launder (which is not available before C++17).
+ //
// NOTE: In this context, `node_type` refers to the C++17 concept of a
// move-only type that owns and provides access to the elements in associative
// containers (https://en.cppreference.com/w/cpp/container/node_handle).
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 0c5f9368..43704206 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2551,6 +2551,35 @@ TEST(Btree, HeterogeneousInsertOrAssign) {
}
#endif
+// This test requires std::launder for mutable key access in node handles.
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+TEST(Btree, NodeHandleMutableKeyAccess) {
+ {
+ absl::btree_map<std::string, std::string> map;
+
+ map["key1"] = "mapped";
+
+ auto nh = map.extract(map.begin());
+ nh.key().resize(3);
+ map.insert(std::move(nh));
+
+ EXPECT_THAT(map, ElementsAre(Pair("key", "mapped")));
+ }
+ // Also for multimap.
+ {
+ absl::btree_multimap<std::string, std::string> map;
+
+ map.emplace("key1", "mapped");
+
+ auto nh = map.extract(map.begin());
+ nh.key().resize(3);
+ map.insert(std::move(nh));
+
+ EXPECT_THAT(map, ElementsAre(Pair("key", "mapped")));
+ }
+}
+#endif
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h
index fcb70d86..dbd37d3c 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -383,6 +383,11 @@ class flat_hash_map : public absl::container_internal::raw_hash_map<
// key value and returns a node handle owning that extracted data. If the
// `flat_hash_map` does not contain an element with a matching key, this
// function returns an empty node handle.
+ //
+ // NOTE: when compiled in an earlier version of C++ than C++17,
+ // `node_type::key()` returns a const reference to the key instead of a
+ // mutable reference. We cannot safely return a mutable reference without
+ // std::launder (which is not available before C++17).
using Base::extract;
// flat_hash_map::merge()
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc
index 2823c32b..89ec60c9 100644
--- a/absl/container/flat_hash_map_test.cc
+++ b/absl/container/flat_hash_map_test.cc
@@ -267,6 +267,21 @@ TEST(FlatHashMap, EraseIf) {
}
}
+// This test requires std::launder for mutable key access in node handles.
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+TEST(FlatHashMap, NodeHandleMutableKeyAccess) {
+ flat_hash_map<std::string, std::string> map;
+
+ map["key1"] = "mapped";
+
+ auto nh = map.extract(map.begin());
+ nh.key().resize(3);
+ map.insert(std::move(nh));
+
+ EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped")));
+}
+#endif
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 293e5771..4d405734 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -292,6 +292,11 @@ struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
}
static const Key &key(const slot_type *s) { return slot_policy::key(s); }
static const Key &key(slot_type *s) { return slot_policy::key(s); }
+ // For use in node handle.
+ static auto mutable_key(slot_type *s)
+ -> decltype(slot_policy::mutable_key(s)) {
+ return slot_policy::mutable_key(s);
+ }
static mapped_type &value(value_type *value) { return value->second; }
};
@@ -1043,7 +1048,7 @@ class btree {
#endif
}
- enum {
+ enum : uint32_t {
kNodeValues = node_type::kNodeValues,
kMinNodeValues = kNodeValues / 2,
};
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
index 8990f294..030e9d4a 100644
--- a/absl/container/internal/common.h
+++ b/absl/container/internal/common.h
@@ -146,8 +146,11 @@ class node_handle<Policy, PolicyTraits, Alloc,
constexpr node_handle() {}
- auto key() const -> decltype(PolicyTraits::key(std::declval<slot_type*>())) {
- return PolicyTraits::key(this->slot());
+ // When C++17 is available, we can use std::launder to provide mutable
+ // access to the key. Otherwise, we provide const access.
+ auto key() const
+ -> decltype(PolicyTraits::mutable_key(std::declval<slot_type*>())) {
+ return PolicyTraits::mutable_key(this->slot());
}
mapped_type& mapped() const {
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h
index c7777a93..d02c576d 100644
--- a/absl/container/internal/container_memory.h
+++ b/absl/container/internal/container_memory.h
@@ -18,6 +18,7 @@
#include <cassert>
#include <cstddef>
#include <memory>
+#include <new>
#include <tuple>
#include <type_traits>
#include <utility>
@@ -352,6 +353,20 @@ struct map_slot_policy {
return slot->value;
}
+ // When C++17 is available, we can use std::launder to provide mutable
+ // access to the key for use in node handle.
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+ static K& mutable_key(slot_type* slot) {
+ // Still check for kMutableKeys so that we can avoid calling std::launder
+ // unless necessary because it can interfere with optimizations.
+ return kMutableKeys::value ? slot->key
+ : *std::launder(const_cast<K*>(
+ std::addressof(slot->value.first)));
+ }
+#else // !(defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606)
+ static const K& mutable_key(slot_type* slot) { return key(slot); }
+#endif
+
static const K& key(const slot_type* slot) {
return kMutableKeys::value ? slot->key : slot->value.first;
}
diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h
index 3e1209c6..46c97b18 100644
--- a/absl/container/internal/hash_policy_traits.h
+++ b/absl/container/internal/hash_policy_traits.h
@@ -17,6 +17,7 @@
#include <cstddef>
#include <memory>
+#include <new>
#include <type_traits>
#include <utility>
@@ -29,15 +30,34 @@ namespace container_internal {
// Defines how slots are initialized/destroyed/moved.
template <class Policy, class = void>
struct hash_policy_traits {
+ // The type of the keys stored in the hashtable.
+ using key_type = typename Policy::key_type;
+
private:
struct ReturnKey {
- // We return `Key` here.
+ // When C++17 is available, we can use std::launder to provide mutable
+ // access to the key for use in node handle.
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+ template <class Key,
+ absl::enable_if_t<std::is_lvalue_reference<Key>::value, int> = 0>
+ static key_type& Impl(Key&& k, int) {
+ return *std::launder(
+ const_cast<key_type*>(std::addressof(std::forward<Key>(k))));
+ }
+#endif
+
+ template <class Key>
+ static Key Impl(Key&& k, char) {
+ return std::forward<Key>(k);
+ }
+
// When Key=T&, we forward the lvalue reference.
// When Key=T, we return by value to avoid a dangling reference.
// eg, for string_hash_map.
template <class Key, class... Args>
- Key operator()(Key&& k, const Args&...) const {
- return std::forward<Key>(k);
+ auto operator()(Key&& k, const Args&...) const
+ -> decltype(Impl(std::forward<Key>(k), 0)) {
+ return Impl(std::forward<Key>(k), 0);
}
};
@@ -52,9 +72,6 @@ struct hash_policy_traits {
// The actual object stored in the hash table.
using slot_type = typename Policy::slot_type;
- // The type of the keys stored in the hashtable.
- using key_type = typename Policy::key_type;
-
// The argument type for insertions into the hashtable. This is different
// from value_type for increased performance. See initializer_list constructor
// and insert() member functions for more details.
@@ -156,7 +173,7 @@ struct hash_policy_traits {
// Returns the "key" portion of the slot.
// Used for node handle manipulation.
template <class P = Policy>
- static auto key(slot_type* slot)
+ static auto mutable_key(slot_type* slot)
-> decltype(P::apply(ReturnKey(), element(slot))) {
return P::apply(ReturnKey(), element(slot));
}
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h
index 174b971e..9852ff7f 100644
--- a/absl/container/node_hash_map.h
+++ b/absl/container/node_hash_map.h
@@ -374,6 +374,11 @@ class node_hash_map
// key value and returns a node handle owning that extracted data. If the
// `node_hash_map` does not contain an element with a matching key, this
// function returns an empty node handle.
+ //
+ // NOTE: when compiled in an earlier version of C++ than C++17,
+ // `node_type::key()` returns a const reference to the key instead of a
+ // mutable reference. We cannot safely return a mutable reference without
+ // std::launder (which is not available before C++17).
using Base::extract;
// node_hash_map::merge()
diff --git a/absl/container/node_hash_map_test.cc b/absl/container/node_hash_map_test.cc
index 5d74b814..8f59a1e4 100644
--- a/absl/container/node_hash_map_test.cc
+++ b/absl/container/node_hash_map_test.cc
@@ -254,6 +254,21 @@ TEST(NodeHashMap, EraseIf) {
}
}
+// This test requires std::launder for mutable key access in node handles.
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+TEST(NodeHashMap, NodeHandleMutableKeyAccess) {
+ node_hash_map<std::string, std::string> map;
+
+ map["key1"] = "mapped";
+
+ auto nh = map.extract(map.begin());
+ nh.key().resize(3);
+ map.insert(std::move(nh));
+
+ EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped")));
+}
+#endif
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-21 16:24:19 +0000