diff options
author | 2021-04-27 09:11:54 -0700 | |
---|---|---|
committer | 2021-04-27 16:35:21 +0000 | |
commit | a5167f986b82e9a7535ee710e87e53cf4c8ef2a8 (patch) | |
tree | 05455a5490740b560cdd69550bd2844ecacd2ee2 /absl/container | |
parent | d96e287417766deddbff2d01b96321288c59491e (diff) |
Export of internal Abseil changes
--
f6fbb03bff276e72123e8590519079e87732ae62 by Abseil Team <absl-team@google.com>:
Replace static absl::Mutex with SpinLock in absl::Cords
to avoid static initializers by absl::Mutex destructors
PiperOrigin-RevId: 370694199
--
654b7d9edfdc24f226990b2b46cbf91451a1d92a by Martijn Vels <mvels@google.com>:
Implement global data for CordzInfo in an ODR hardened way
This change puts the global data into a global list structure, and stores a reference to the global list in the handle itself. This hardens the implementation against ODR violations where info pointers are crossing dynamic library boundaries which are privately loaded.
PiperOrigin-RevId: 370673045
--
712dba768e66ee2ba85d6010829c617cd2af6ba7 by Martijn Vels <mvels@google.com>:
Intrument Cord::operator= for Cordz
PiperOrigin-RevId: 370659149
--
c0b347a2289e151b72680269332e264b8fa989c0 by Matt Kulukundis <kfm@google.com>:
Fix test guards for ABSL_ATTRIBUTE_RETURNS_NONNULL
PiperOrigin-RevId: 370594807
--
c2bedaa3472ef223f907de2604f9b9b58852ec5f by Martijn Vels <mvels@google.com>:
Add new Cordz instrumentation on GetAppendRegion.
PiperOrigin-RevId: 370587761
--
84fbfcc852697d509f6094482b86e84743a6b331 by Martijn Vels <mvels@google.com>:
Add instrumentation on Cord::Apppend(string_view)
PiperOrigin-RevId: 370576590
--
9e077390b8ca2239e1cb7bfbe1d5a04f2fc11d30 by Abseil Team <absl-team@google.com>:
Google-internal changes only.
PiperOrigin-RevId: 370558424
--
fb53c149eb2364ea34e3a67235f873866618b8ac by Matt Kulukundis <kfm@google.com>:
Update config.h macros with a few useful helpers to simplify version checking
PiperOrigin-RevId: 370557684
--
abf8142e99b9ff7e15f6528a357f1005461950b0 by Martijn Vels <mvels@google.com>:
clang-format cord
PiperOrigin-RevId: 370549371
--
e555985eabe63fcf0e980e9c433dd84caffec191 by Martijn Vels <mvels@google.com>:
Add MaybeUntrackCord() function
This function is near identical to the old UntrackCord() but allows info to be null, moving the cord.is_profiled() branch into CordzInfo.
PiperOrigin-RevId: 370528447
--
3883538efe4601f7864bda70a50d868bb383c63b by Derek Mauro <dmauro@google.com>:
Internal change
PiperOrigin-RevId: 370503186
--
a9514b65542fde1bc73584e6f3c1c4b3a05f215f by Derek Mauro <dmauro@google.com>:
Add -Winvalid-constexpr to warning options for LLVM
PiperOrigin-RevId: 370455171
--
d8a3966de2cf15a2dc28e17e49a3d27d205eca92 by Martijn Vels <mvels@google.com>:
Add naive UniqueGenerator<T, kMaxValues, ...> to avoid flakes from dup random values.
PiperOrigin-RevId: 370179772
--
46d0caa1a12b68a5998d4f919e20f0f83b9286f8 by Martijn Vels <mvels@google.com>:
Add new Cordz instrumentation on PrependTree.
PiperOrigin-RevId: 370138969
GitOrigin-RevId: f6fbb03bff276e72123e8590519079e87732ae62
Change-Id: Ifa4c00a5c7b01198ee367a3253bea6b66612135e
Diffstat (limited to 'absl/container')
-rw-r--r-- | absl/container/internal/hash_generator_testing.h | 21 | ||||
-rw-r--r-- | absl/container/internal/unordered_map_constructor_test.h | 38 |
2 files changed, 42 insertions, 17 deletions
diff --git a/absl/container/internal/hash_generator_testing.h b/absl/container/internal/hash_generator_testing.h index 6869fe45..f1f555a5 100644 --- a/absl/container/internal/hash_generator_testing.h +++ b/absl/container/internal/hash_generator_testing.h @@ -21,11 +21,13 @@ #include <stdint.h> #include <algorithm> +#include <cassert> #include <iosfwd> #include <random> #include <tuple> #include <type_traits> #include <utility> +#include <vector> #include "absl/container/internal/hash_policy_testing.h" #include "absl/memory/memory.h" @@ -153,6 +155,25 @@ using GeneratedType = decltype( typename Container::value_type, typename Container::key_type>::type>&>()()); +// Naive wrapper that performs a linear search of previous values. +// Beware this is O(SQR), which is reasonable for smaller kMaxValues. +template <class T, size_t kMaxValues = 64, class E = void> +struct UniqueGenerator { + Generator<T, E> gen; + std::vector<T> values; + + T operator()() { + assert(values.size() < kMaxValues); + for (;;) { + T value = gen(); + if (std::find(values.begin(), values.end(), value) == values.end()) { + values.push_back(value); + return value; + } + } + } +}; + } // namespace hash_internal } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/unordered_map_constructor_test.h b/absl/container/internal/unordered_map_constructor_test.h index 3f90ad7c..c1d20f3c 100644 --- a/absl/container/internal/unordered_map_constructor_test.h +++ b/absl/container/internal/unordered_map_constructor_test.h @@ -179,7 +179,7 @@ TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) { A alloc(0); std::vector<T> values; std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + hash_internal::UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.key_eq(), equal); @@ -198,7 +198,7 @@ void InputIteratorBucketAllocTest(std::true_type) { A alloc(0); std::vector<T> values; std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + hash_internal::UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, alloc); EXPECT_EQ(m.get_allocator(), alloc); EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); @@ -221,7 +221,7 @@ void InputIteratorBucketHashAllocTest(std::true_type) { A alloc(0); std::vector<T> values; std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + hash_internal::UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.get_allocator(), alloc); @@ -241,8 +241,9 @@ TYPED_TEST_P(ConstructorTest, CopyConstructor) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam n(m); EXPECT_EQ(m.hash_function(), n.hash_function()); EXPECT_EQ(m.key_eq(), n.key_eq()); @@ -262,8 +263,9 @@ void CopyConstructorAllocTest(std::true_type) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam n(m, A(11)); EXPECT_EQ(m.hash_function(), n.hash_function()); EXPECT_EQ(m.key_eq(), n.key_eq()); @@ -285,8 +287,9 @@ TYPED_TEST_P(ConstructorTest, MoveConstructor) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam t(m); TypeParam n(std::move(t)); EXPECT_EQ(m.hash_function(), n.hash_function()); @@ -307,8 +310,9 @@ void MoveConstructorAllocTest(std::true_type) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam t(m); TypeParam n(std::move(t), A(1)); EXPECT_EQ(m.hash_function(), n.hash_function()); @@ -325,7 +329,7 @@ TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) { TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; @@ -348,7 +352,7 @@ template <typename TypeParam> void InitializerListBucketAllocTest(std::true_type) { using T = hash_internal::GeneratedType<TypeParam>; using A = typename TypeParam::allocator_type; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; A alloc(0); TypeParam m(values, 123, alloc); @@ -371,7 +375,7 @@ void InitializerListBucketHashAllocTest(std::true_type) { using A = typename TypeParam::allocator_type; H hasher; A alloc(0); - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values, 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); @@ -392,7 +396,7 @@ TYPED_TEST_P(ConstructorTest, Assignment) { H hasher; E equal; A alloc(0); - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam n; n = m; @@ -412,7 +416,7 @@ TYPED_TEST_P(ConstructorTest, MoveAssignment) { H hasher; E equal; A alloc(0); - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam t(m); TypeParam n; @@ -424,7 +428,7 @@ TYPED_TEST_P(ConstructorTest, MoveAssignment) { TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -433,7 +437,7 @@ TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) { TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam n({gen()}); n = m; @@ -442,7 +446,7 @@ TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) { TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam t(m); TypeParam n({gen()}); @@ -452,7 +456,7 @@ TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) { TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -461,7 +465,7 @@ TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) { TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values); m = *&m; // Avoid -Wself-assign |