summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel10
-rw-r--r--absl/container/CMakeLists.txt12
-rw-r--r--absl/container/internal/common.h48
-rw-r--r--absl/container/internal/container_memory.h27
-rw-r--r--absl/container/internal/hashtablez_sampler.cc1
-rw-r--r--absl/container/internal/raw_hash_map.h4
-rw-r--r--absl/container/internal/raw_hash_set.h29
7 files changed, 99 insertions, 32 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 623faf45..87fc7349 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -511,11 +511,21 @@ cc_library(
)
cc_library(
+ name = "common",
+ hdrs = ["internal/common.h"],
+ copts = ABSL_DEFAULT_COPTS,
+ deps = [
+ "//absl/meta:type_traits",
+ ],
+)
+
+cc_library(
name = "raw_hash_set",
srcs = ["internal/raw_hash_set.cc"],
hdrs = ["internal/raw_hash_set.h"],
copts = ABSL_DEFAULT_COPTS,
deps = [
+ ":common",
":compressed_tuple",
":container_memory",
":hash_policy_traits",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index de9b22f7..21c9cb95 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -529,6 +529,17 @@ absl_cc_library(
absl_cc_library(
NAME
+ container_common
+ HDRS
+ "internal/commom.h"
+ COPTS
+ ${ABSL_DEFAULT_COPTS}
+ DEPS
+ absl::type_traits
+)
+
+absl_cc_library(
+ NAME
raw_hash_set
HDRS
"internal/raw_hash_set.h"
@@ -540,6 +551,7 @@ absl_cc_library(
absl::bits
absl::compressed_tuple
absl::config
+ absl::container_common
absl::container_memory
absl::core_headers
absl::endian
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
new file mode 100644
index 00000000..a6dc9103
--- /dev/null
+++ b/absl/container/internal/common.h
@@ -0,0 +1,48 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_CONTAINER_INTERNAL_CONTAINER_H_
+#define ABSL_CONTAINER_INTERNAL_CONTAINER_H_
+
+#include <type_traits>
+
+#include "absl/meta/type_traits.h"
+
+namespace absl {
+namespace container_internal {
+
+template <class, class = void>
+struct IsTransparent : std::false_type {};
+template <class T>
+struct IsTransparent<T, absl::void_t<typename T::is_transparent>>
+ : std::true_type {};
+
+template <bool is_transparent>
+struct KeyArg {
+ // Transparent. Forward `K`.
+ template <typename K, typename key_type>
+ using type = K;
+};
+
+template <>
+struct KeyArg<false> {
+ // Not transparent. Always use `key_type`.
+ template <typename K, typename key_type>
+ using type = key_type;
+};
+
+} // namespace container_internal
+} // namespace absl
+
+#endif // ABSL_CONTAINER_INTERNAL_CONTAINER_H_
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h
index 56c5d2df..35b691ce 100644
--- a/absl/container/internal/container_memory.h
+++ b/absl/container/internal/container_memory.h
@@ -286,11 +286,30 @@ struct IsLayoutCompatible {
} // namespace memory_internal
-// If kMutableKeys is false, only the value member is accessed.
+// The internal storage type for key-value containers like flat_hash_map.
//
-// If kMutableKeys is true, key is accessed through all slots while value and
-// mutable_value are accessed only via INITIALIZED slots. Slots are created and
-// destroyed via mutable_value so that the key can be moved later.
+// It is convenient for the value_type of a flat_hash_map<K, V> to be
+// pair<const K, V>; the "const K" prevents accidental modification of the key
+// when dealing with the reference returned from find() and similar methods.
+// However, this creates other problems; we want to be able to emplace(K, V)
+// efficiently with move operations, and similarly be able to move a
+// pair<K, V> in insert().
+//
+// The solution is this union, which aliases the const and non-const versions
+// of the pair. This also allows flat_hash_map<const K, V> to work, even though
+// that has the same efficiency issues with move in emplace() and insert() -
+// but people do it anyway.
+//
+// If kMutableKeys is false, only the value member can be accessed.
+//
+// If kMutableKeys is true, key can be accessed through all slots while value
+// and mutable_value must be accessed only via INITIALIZED slots. Slots are
+// created and destroyed via mutable_value so that the key can be moved later.
+//
+// Accessing one of the union fields while the other is active is safe as
+// long as they are layout-compatible, which is guaranteed by the definition of
+// kMutableKeys. For C++11, the relevant section of the standard is
+// https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
template <class K, class V>
union slot_type {
private:
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc
index e588f24c..1ba95645 100644
--- a/absl/container/internal/hashtablez_sampler.cc
+++ b/absl/container/internal/hashtablez_sampler.cc
@@ -16,6 +16,7 @@
#include <atomic>
#include <cassert>
+#include <cmath>
#include <functional>
#include <limits>
diff --git a/absl/container/internal/raw_hash_map.h b/absl/container/internal/raw_hash_map.h
index 05270ef3..e0f5c07c 100644
--- a/absl/container/internal/raw_hash_map.h
+++ b/absl/container/internal/raw_hash_map.h
@@ -39,8 +39,8 @@ class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> {
using MappedConstReference = decltype(P::value(
std::addressof(std::declval<typename raw_hash_map::const_reference>())));
- using KeyArgImpl = container_internal::KeyArg<IsTransparent<Eq>::value &&
- IsTransparent<Hash>::value>;
+ using KeyArgImpl =
+ KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
public:
using key_type = typename Policy::key_type;
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 8cdea4ec..8f2350a7 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -105,6 +105,7 @@
#include "absl/base/internal/bits.h"
#include "absl/base/internal/endian.h"
#include "absl/base/port.h"
+#include "absl/container/internal/common.h"
#include "absl/container/internal/compressed_tuple.h"
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/hash_policy_traits.h"
@@ -165,12 +166,6 @@ struct IsDecomposable<
std::declval<Ts>()...))>,
Policy, Hash, Eq, Ts...> : std::true_type {};
-template <class, class = void>
-struct IsTransparent : std::false_type {};
-template <class T>
-struct IsTransparent<T, absl::void_t<typename T::is_transparent>>
- : std::true_type {};
-
// TODO(alkis): Switch to std::is_nothrow_swappable when gcc/clang supports it.
template <class T>
constexpr bool IsNoThrowSwappable() {
@@ -605,24 +600,6 @@ struct insert_return_type {
NodeType node;
};
-// Helper trait to allow or disallow arbitrary keys when the hash and
-// eq functions are transparent.
-// It is very important that the inner template is an alias and that the type it
-// produces is not a dependent type. Otherwise, type deduction would fail.
-template <bool is_transparent>
-struct KeyArg {
- // Transparent. Forward `K`.
- template <typename K, typename key_type>
- using type = K;
-};
-
-template <>
-struct KeyArg<false> {
- // Not transparent. Always use `key_type`.
- template <typename K, typename key_type>
- using type = key_type;
-};
-
// Policy: a policy defines how to perform different operations on
// the slots of the hashtable (see hash_policy_traits.h for the full interface
// of policy).
@@ -643,8 +620,8 @@ struct KeyArg<false> {
template <class Policy, class Hash, class Eq, class Alloc>
class raw_hash_set {
using PolicyTraits = hash_policy_traits<Policy>;
- using KeyArgImpl = container_internal::KeyArg<IsTransparent<Eq>::value &&
- IsTransparent<Hash>::value>;
+ using KeyArgImpl =
+ KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
public:
using init_type = typename PolicyTraits::init_type;