diff options
Diffstat (limited to 'absl')
-rw-r--r-- | absl/algorithm/container.h | 2 | ||||
-rw-r--r-- | absl/container/BUILD.bazel | 14 | ||||
-rw-r--r-- | absl/container/CMakeLists.txt | 14 | ||||
-rw-r--r-- | absl/container/internal/node_slot_policy.h (renamed from absl/container/internal/node_hash_policy.h) | 8 | ||||
-rw-r--r-- | absl/container/internal/node_slot_policy_test.cc (renamed from absl/container/internal/node_hash_policy_test.cc) | 4 | ||||
-rw-r--r-- | absl/container/node_hash_map.h | 4 | ||||
-rw-r--r-- | absl/container/node_hash_set.h | 4 | ||||
-rw-r--r-- | absl/hash/hash_test.cc | 195 | ||||
-rw-r--r-- | absl/hash/internal/hash.h | 19 | ||||
-rw-r--r-- | absl/strings/cord.h | 5 | ||||
-rw-r--r-- | absl/strings/internal/cord_rep_flat.h | 11 |
11 files changed, 211 insertions, 69 deletions
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index c38a4a63..26b19529 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h @@ -166,7 +166,7 @@ container_algorithm_internal::ContainerDifferenceType<const C> c_distance( // c_all_of() // // Container-based version of the <algorithm> `std::all_of()` function to -// test a condition on all elements within a container. +// test if all elements within a container satisfy a condition. template <typename C, typename Pred> bool c_all_of(const C& c, Pred&& pred) { return std::all_of(container_algorithm_internal::c_begin(c), diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index ffaee19c..ea2c98b8 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -307,7 +307,7 @@ cc_library( deps = [ ":container_memory", ":hash_function_defaults", - ":node_hash_policy", + ":node_slot_policy", ":raw_hash_map", "//absl/algorithm:container", "//absl/memory", @@ -339,7 +339,7 @@ cc_library( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_function_defaults", - ":node_hash_policy", + ":node_slot_policy", ":raw_hash_set", "//absl/algorithm:container", "//absl/memory", @@ -535,21 +535,21 @@ cc_test( ) cc_library( - name = "node_hash_policy", - hdrs = ["internal/node_hash_policy.h"], + name = "node_slot_policy", + hdrs = ["internal/node_slot_policy.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = ["//absl/base:config"], ) cc_test( - name = "node_hash_policy_test", - srcs = ["internal/node_hash_policy_test.cc"], + name = "node_slot_policy_test", + srcs = ["internal/node_slot_policy_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_policy_traits", - ":node_hash_policy", + ":node_slot_policy", "@com_google_googletest//:gtest_main", ], ) diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 78584d2c..bb718cf8 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -348,7 +348,7 @@ absl_cc_library( DEPS absl::container_memory absl::hash_function_defaults - absl::node_hash_policy + absl::node_slot_policy absl::raw_hash_map absl::algorithm_container absl::memory @@ -382,7 +382,7 @@ absl_cc_library( ${ABSL_DEFAULT_COPTS} DEPS absl::hash_function_defaults - absl::node_hash_policy + absl::node_slot_policy absl::raw_hash_set absl::algorithm_container absl::memory @@ -599,9 +599,9 @@ absl_cc_library( absl_cc_library( NAME - node_hash_policy + node_slot_policy HDRS - "internal/node_hash_policy.h" + "internal/node_slot_policy.h" COPTS ${ABSL_DEFAULT_COPTS} DEPS @@ -611,14 +611,14 @@ absl_cc_library( absl_cc_test( NAME - node_hash_policy_test + node_slot_policy_test SRCS - "internal/node_hash_policy_test.cc" + "internal/node_slot_policy_test.cc" COPTS ${ABSL_TEST_COPTS} DEPS absl::hash_policy_traits - absl::node_hash_policy + absl::node_slot_policy GTest::gmock_main ) diff --git a/absl/container/internal/node_hash_policy.h b/absl/container/internal/node_slot_policy.h index 4617162f..baba5743 100644 --- a/absl/container/internal/node_hash_policy.h +++ b/absl/container/internal/node_slot_policy.h @@ -30,8 +30,8 @@ // It may also optionally define `value()` and `apply()`. For documentation on // these, see hash_policy_traits.h. -#ifndef ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ -#define ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ +#ifndef ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ +#define ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ #include <cassert> #include <cstddef> @@ -46,7 +46,7 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { template <class Reference, class Policy> -struct node_hash_policy { +struct node_slot_policy { static_assert(std::is_lvalue_reference<Reference>::value, ""); using slot_type = typename std::remove_cv< @@ -89,4 +89,4 @@ struct node_hash_policy { ABSL_NAMESPACE_END } // namespace absl -#endif // ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ +#endif // ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ diff --git a/absl/container/internal/node_hash_policy_test.cc b/absl/container/internal/node_slot_policy_test.cc index 84aabba9..51b7467b 100644 --- a/absl/container/internal/node_hash_policy_test.cc +++ b/absl/container/internal/node_slot_policy_test.cc @@ -12,7 +12,7 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include <memory> @@ -27,7 +27,7 @@ namespace { using ::testing::Pointee; -struct Policy : node_hash_policy<int&, Policy> { +struct Policy : node_slot_policy<int&, Policy> { using key_type = int; using init_type = int; diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 7a39f628..302dafa2 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h @@ -43,7 +43,7 @@ #include "absl/algorithm/container.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export #include "absl/memory/memory.h" @@ -535,7 +535,7 @@ namespace container_internal { template <class Key, class Value> class NodeHashMapPolicy - : public absl::container_internal::node_hash_policy< + : public absl::container_internal::node_slot_policy< std::pair<const Key, Value>&, NodeHashMapPolicy<Key, Value>> { using value_type = std::pair<const Key, Value>; diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 93b15f46..4247288d 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h @@ -39,7 +39,7 @@ #include "absl/algorithm/container.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export #include "absl/memory/memory.h" @@ -442,7 +442,7 @@ namespace container_internal { template <class T> struct NodeHashSetPolicy - : absl::container_internal::node_hash_policy<T&, NodeHashSetPolicy<T>> { + : absl::container_internal::node_slot_policy<T&, NodeHashSetPolicy<T>> { using key_type = T; using init_type = T; using constant_iterators = std::true_type; diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index b3ddebdd..dbfacb2d 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc @@ -14,12 +14,14 @@ #include "absl/hash/hash.h" +#include <algorithm> #include <array> #include <bitset> #include <cstring> #include <deque> #include <forward_list> #include <functional> +#include <initializer_list> #include <iterator> #include <limits> #include <list> @@ -46,6 +48,56 @@ namespace { +// Utility wrapper of T for the purposes of testing the `AbslHash` type erasure +// mechanism. `TypeErasedValue<T>` can be constructed with a `T`, and can +// be compared and hashed. However, all hashing goes through the hashing +// type-erasure framework. +template <typename T> +class TypeErasedValue { + public: + TypeErasedValue() = default; + TypeErasedValue(const TypeErasedValue&) = default; + TypeErasedValue(TypeErasedValue&&) = default; + explicit TypeErasedValue(const T& n) : n_(n) {} + + template <typename H> + friend H AbslHashValue(H hash_state, const TypeErasedValue& v) { + v.HashValue(absl::HashState::Create(&hash_state)); + return hash_state; + } + + void HashValue(absl::HashState state) const { + absl::HashState::combine(std::move(state), n_); + } + + bool operator==(const TypeErasedValue& rhs) const { return n_ == rhs.n_; } + bool operator!=(const TypeErasedValue& rhs) const { return !(*this == rhs); } + + private: + T n_; +}; + +// A TypeErasedValue refinement, for containers. It exposes the wrapped +// `value_type` and is constructible from an initializer list. +template <typename T> +class TypeErasedContainer : public TypeErasedValue<T> { + public: + using value_type = typename T::value_type; + TypeErasedContainer() = default; + TypeErasedContainer(const TypeErasedContainer&) = default; + TypeErasedContainer(TypeErasedContainer&&) = default; + explicit TypeErasedContainer(const T& n) : TypeErasedValue<T>(n) {} + TypeErasedContainer(std::initializer_list<value_type> init_list) + : TypeErasedContainer(T(init_list.begin(), init_list.end())) {} + // one-argument constructor of value type T, to appease older toolchains that + // get confused by one-element initializer lists in some contexts + explicit TypeErasedContainer(const value_type& v) + : TypeErasedContainer(T(&v, &v + 1)) {} +}; + +template <typename T> +using TypeErasedVector = TypeErasedContainer<std::vector<T>>; + using absl::Hash; using absl::hash_internal::SpyHashState; @@ -389,23 +441,60 @@ TYPED_TEST_SUITE_P(HashValueSequenceTest); TYPED_TEST_P(HashValueSequenceTest, BasicUsage) { EXPECT_TRUE((is_hashable<TypeParam>::value)); - using ValueType = typename TypeParam::value_type; - auto a = static_cast<ValueType>(0); - auto b = static_cast<ValueType>(23); - auto c = static_cast<ValueType>(42); - - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( - std::make_tuple(TypeParam(), TypeParam{}, TypeParam{a, b, c}, - TypeParam{a, b}, TypeParam{b, c}))); + using IntType = typename TypeParam::value_type; + auto a = static_cast<IntType>(0); + auto b = static_cast<IntType>(23); + auto c = static_cast<IntType>(42); + + std::vector<TypeParam> exemplars = { + TypeParam(), TypeParam(), TypeParam{a, b, c}, + TypeParam{a, c, b}, TypeParam{c, a, b}, TypeParam{a}, + TypeParam{a, a}, TypeParam{a, a, a}, TypeParam{a, a, b}, + TypeParam{a, b, a}, TypeParam{b, a, a}, TypeParam{a, b}, + TypeParam{b, c}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); } REGISTER_TYPED_TEST_CASE_P(HashValueSequenceTest, BasicUsage); using IntSequenceTypes = testing::Types<std::deque<int>, std::forward_list<int>, std::list<int>, - std::vector<int>, std::vector<bool>, std::set<int>, - std::multiset<int>>; + std::vector<int>, std::vector<bool>, TypeErasedVector<int>, + TypeErasedVector<bool>, std::set<int>, std::multiset<int>>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes); +template <typename T> +class HashValueNestedSequenceTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueNestedSequenceTest); + +TYPED_TEST_P(HashValueNestedSequenceTest, BasicUsage) { + using T = TypeParam; + using V = typename T::value_type; + std::vector<T> exemplars = { + // empty case + T{}, + // sets of empty sets + T{V{}}, T{V{}, V{}}, T{V{}, V{}, V{}}, + // multisets of different values + T{V{1}}, T{V{1, 1}, V{1, 1}}, T{V{1, 1, 1}, V{1, 1, 1}, V{1, 1, 1}}, + // various orderings of same nested sets + T{V{}, V{1, 2}}, T{V{}, V{2, 1}}, T{V{1, 2}, V{}}, T{V{2, 1}, V{}}, + // various orderings of various nested sets, case 2 + T{V{1, 2}, V{3, 4}}, T{V{1, 2}, V{4, 3}}, T{V{1, 3}, V{2, 4}}, + T{V{1, 3}, V{4, 2}}, T{V{1, 4}, V{2, 3}}, T{V{1, 4}, V{3, 2}}, + T{V{2, 3}, V{1, 4}}, T{V{2, 3}, V{4, 1}}, T{V{2, 4}, V{1, 3}}, + T{V{2, 4}, V{3, 1}}, T{V{3, 4}, V{1, 2}}, T{V{3, 4}, V{2, 1}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); +} + +REGISTER_TYPED_TEST_CASE_P(HashValueNestedSequenceTest, BasicUsage); +using NestedIntSequenceTypes = + testing::Types<std::vector<std::vector<int>>, + std::vector<TypeErasedVector<int>>, + TypeErasedVector<std::vector<int>>, + TypeErasedVector<TypeErasedVector<int>>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueNestedSequenceTest, + NestedIntSequenceTypes); + // Private type that only supports AbslHashValue to make sure our chosen hash // implementation is recursive within absl::Hash. // It uses std::abs() on the value to provide different bitwise representations @@ -564,23 +653,59 @@ TEST(HashValueTest, Variant) { #endif } -TEST(HashValueTest, Maps) { - EXPECT_TRUE((is_hashable<std::map<int, std::string>>::value)); +template <typename T> +class HashValueAssociativeMapTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueAssociativeMapTest); + +TYPED_TEST_P(HashValueAssociativeMapTest, BasicUsage) { + using M = TypeParam; + using V = typename M::value_type; + std::vector<M> exemplars{M{}, + M{V{0, "foo"}}, + M{V{1, "foo"}}, + M{V{0, "bar"}}, + M{V{1, "bar"}}, + M{V{0, "foo"}, V{42, "bar"}}, + M{V{42, "bar"}, V{0, "foo"}}, + M{V{1, "foo"}, V{42, "bar"}}, + M{V{1, "foo"}, V{43, "bar"}}, + M{V{1, "foo"}, V{43, "baz"}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); +} - using M = std::map<int, std::string>; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - M{}, M{{0, "foo"}}, M{{1, "foo"}}, M{{0, "bar"}}, M{{1, "bar"}}, - M{{0, "foo"}, {42, "bar"}}, M{{1, "foo"}, {42, "bar"}}, - M{{1, "foo"}, {43, "bar"}}, M{{1, "foo"}, {43, "baz"}}))); +REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMapTest, BasicUsage); +using AssociativeMapTypes = testing::Types<std::map<int, std::string>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMapTest, + AssociativeMapTypes); - using MM = std::multimap<int, std::string>; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - MM{}, MM{{0, "foo"}}, MM{{1, "foo"}}, MM{{0, "bar"}}, MM{{1, "bar"}}, - MM{{0, "foo"}, {0, "bar"}}, MM{{0, "bar"}, {0, "foo"}}, - MM{{0, "foo"}, {42, "bar"}}, MM{{1, "foo"}, {42, "bar"}}, - MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}}))); +template <typename T> +class HashValueAssociativeMultimapTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest); + +TYPED_TEST_P(HashValueAssociativeMultimapTest, BasicUsage) { + using MM = TypeParam; + using V = typename MM::value_type; + std::vector<MM> exemplars{MM{}, + MM{V{0, "foo"}}, + MM{V{1, "foo"}}, + MM{V{0, "bar"}}, + MM{V{1, "bar"}}, + MM{V{0, "foo"}, V{0, "bar"}}, + MM{V{0, "bar"}, V{0, "foo"}}, + MM{V{0, "foo"}, V{42, "bar"}}, + MM{V{1, "foo"}, V{42, "bar"}}, + MM{V{1, "foo"}, V{1, "foo"}, V{43, "bar"}}, + MM{V{1, "foo"}, V{43, "bar"}, V{1, "foo"}}, + MM{V{1, "foo"}, V{43, "baz"}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); } +REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMultimapTest, BasicUsage); +using AssociativeMultimapTypes = + testing::Types<std::multimap<int, std::string>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMultimapTest, + AssociativeMultimapTypes); + TEST(HashValueTest, ReferenceWrapper) { EXPECT_TRUE(is_hashable<std::reference_wrapper<Private>>::value); @@ -928,28 +1053,14 @@ TEST(HashTest, SmallValueOn64ByteBoundary) { Hash<IntAndString>()(IntAndString{0, std::string(63, '0')}); } -struct TypeErased { - size_t n; - - template <typename H> - friend H AbslHashValue(H hash_state, const TypeErased& v) { - v.HashValue(absl::HashState::Create(&hash_state)); - return hash_state; - } - - void HashValue(absl::HashState state) const { - absl::HashState::combine(std::move(state), n); - } -}; - TEST(HashTest, TypeErased) { - EXPECT_TRUE((is_hashable<TypeErased>::value)); - EXPECT_TRUE((is_hashable<std::pair<TypeErased, int>>::value)); + EXPECT_TRUE((is_hashable<TypeErasedValue<size_t>>::value)); + EXPECT_TRUE((is_hashable<std::pair<TypeErasedValue<size_t>, int>>::value)); - EXPECT_EQ(SpyHash(TypeErased{7}), SpyHash(size_t{7})); - EXPECT_NE(SpyHash(TypeErased{7}), SpyHash(size_t{13})); + EXPECT_EQ(SpyHash(TypeErasedValue<size_t>(7)), SpyHash(size_t{7})); + EXPECT_NE(SpyHash(TypeErasedValue<size_t>(7)), SpyHash(size_t{13})); - EXPECT_EQ(SpyHash(std::make_pair(TypeErased{7}, 17)), + EXPECT_EQ(SpyHash(std::make_pair(TypeErasedValue<size_t>(7), 17)), SpyHash(std::make_pair(size_t{7}, 17))); } diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index b1e33caf..97b68bad 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -502,10 +502,9 @@ AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { vector.size()); } +// AbslHashValue special cases for hashing std::vector<bool> #if defined(ABSL_IS_BIG_ENDIAN) && \ (defined(__GLIBCXX__) || defined(__GLIBCPP__)) -// AbslHashValue for hashing std::vector<bool> -// // std::hash in libstdc++ does not work correctly with vector<bool> on Big // Endian platforms therefore we need to implement a custom AbslHashValue for // it. More details on the bug: @@ -521,6 +520,22 @@ AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { } return H::combine(combiner.finalize(std::move(hash_state)), vector.size()); } +#else +// When not working around the libstdc++ bug above, we still have to contend +// with the fact that std::hash<vector<bool>> is often poor quality, hashing +// directly on the internal words and on no other state. On these platforms, +// vector<bool>{1, 1} and vector<bool>{1, 1, 0} hash to the same value. +// +// Mixing in the size (as we do in our other vector<> implementations) on top +// of the library-provided hash implementation avoids this QOI issue. +template <typename H, typename T, typename Allocator> +typename std::enable_if<is_hashable<T>::value && std::is_same<T, bool>::value, + H>::type +AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { + return H::combine(std::move(hash_state), + std::hash<std::vector<T, Allocator>>{}(vector), + vector.size()); +} #endif // ----------------------------------------------------------------------------- diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 3f0633bd..662e889a 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -855,6 +855,11 @@ class Cord { // Returns true if the Cord is being profiled by cordz. bool is_profiled() const { return data_.is_tree() && data_.is_profiled(); } + // Returns the available inlined capacity, or 0 if is_tree() == true. + size_t inline_capacity() const { + return data_.is_tree() ? 0 : kMaxInline - data_.inline_size(); + } + // Returns the profiled CordzInfo, or nullptr if not sampled. absl::cord_internal::CordzInfo* cordz_info() const { return data_.cordz_info(); diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h index 62cf5840..8c254273 100644 --- a/absl/strings/internal/cord_rep_flat.h +++ b/absl/strings/internal/cord_rep_flat.h @@ -117,6 +117,17 @@ struct CordRepFlat : public CordRep { #endif } + // Create a CordRepFlat containing `data`, with an optional additional + // extra capacity of up to `extra` bytes. Requires that `data.size()` + // is less than kMaxFlatLength. + static CordRepFlat* Create(absl::string_view data, size_t extra = 0) { + assert(data.size() <= kMaxFlatLength); + CordRepFlat* flat = New(data.size() + (std::min)(extra, kMaxFlatLength)); + memcpy(flat->Data(), data.data(), data.size()); + flat->length = data.size(); + return flat; + } + // Returns a pointer to the data inside this flat rep. char* Data() { return reinterpret_cast<char*>(storage); } const char* Data() const { return reinterpret_cast<const char*>(storage); } |