Export of internal Abseil changes.

--
4eacae3ff1b14b1d309e8092185bc10e8a6203cf by Derek Mauro <dmauro@google.com>:

Release SwissTable - a fast, efficient, cache-friendly hash table.

https://www.youtube.com/watch?v=ncHmEUmJZf4

PiperOrigin-RevId: 214816527

--
df8c3dfab3cfb2f4365909a84d0683b193cfbb11 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 214785288

--
1eabd5266bbcebc33eecc91e5309b751856a75c8 by Abseil Team <absl-team@google.com>:

Internal change

PiperOrigin-RevId: 214722931

--
2ebbfac950f83146b46253038e7dd7dcde9f2951 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 214701684
GitOrigin-RevId: 4eacae3ff1b14b1d309e8092185bc10e8a6203cf
Change-Id: I9ba64e395b22ad7863213d157b8019b082adc19d

1 files changed, 404 insertions, 0 deletions

diff --git a/absl/container/internal/unordered_map_constructor_test.h b/absl/container/internal/unordered_map_constructor_test.h
new file mode 100644
index 000000000000..2ffb646cb264
--- /dev/null
+++ b/absl/container/internal/unordered_map_constructor_test.h
@@ -0,0 +1,404 @@
+// 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_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
+#define ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
+
+#include <algorithm>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/container/internal/hash_generator_testing.h"
+#include "absl/container/internal/hash_policy_testing.h"
+
+namespace absl {
+namespace container_internal {
+
+template <class UnordMap>
+class ConstructorTest : public ::testing::Test {};
+
+TYPED_TEST_CASE_P(ConstructorTest);
+
+TYPED_TEST_P(ConstructorTest, NoArgs) {
+  TypeParam m;
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+}
+
+TYPED_TEST_P(ConstructorTest, BucketCount) {
+  TypeParam m(123);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+  EXPECT_GE(m.bucket_count(), 123);
+}
+
+TYPED_TEST_P(ConstructorTest, BucketCountHash) {
+  using H = typename TypeParam::hasher;
+  H hasher;
+  TypeParam m(123, hasher);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+  EXPECT_GE(m.bucket_count(), 123);
+}
+
+TYPED_TEST_P(ConstructorTest, BucketCountHashEqual) {
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  H hasher;
+  E equal;
+  TypeParam m(123, hasher, equal);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.key_eq(), equal);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+  EXPECT_GE(m.bucket_count(), 123);
+}
+
+TYPED_TEST_P(ConstructorTest, BucketCountHashEqualAlloc) {
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  TypeParam m(123, hasher, equal, alloc);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.key_eq(), equal);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+  EXPECT_GE(m.bucket_count(), 123);
+}
+
+TYPED_TEST_P(ConstructorTest, BucketCountAlloc) {
+#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
+  using A = typename TypeParam::allocator_type;
+  A alloc(0);
+  TypeParam m(123, alloc);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+  EXPECT_GE(m.bucket_count(), 123);
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, BucketCountHashAlloc) {
+#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
+  using H = typename TypeParam::hasher;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  A alloc(0);
+  TypeParam m(123, hasher, alloc);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+  EXPECT_GE(m.bucket_count(), 123);
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, BucketAlloc) {
+#if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS
+  using A = typename TypeParam::allocator_type;
+  A alloc(0);
+  TypeParam m(alloc);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_TRUE(m.empty());
+  EXPECT_THAT(m, ::testing::UnorderedElementsAre());
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.key_eq(), equal);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_GE(m.bucket_count(), 123);
+}
+
+TYPED_TEST_P(ConstructorTest, InputIteratorBucketAlloc) {
+#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using A = typename TypeParam::allocator_type;
+  A alloc(0);
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end(), 123, alloc);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_GE(m.bucket_count(), 123);
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashAlloc) {
+#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  A alloc(0);
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end(), 123, hasher, alloc);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_GE(m.bucket_count(), 123);
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, CopyConstructor) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  TypeParam m(123, hasher, equal, alloc);
+  for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
+  TypeParam n(m);
+  EXPECT_EQ(m.hash_function(), n.hash_function());
+  EXPECT_EQ(m.key_eq(), n.key_eq());
+  EXPECT_EQ(m.get_allocator(), n.get_allocator());
+  EXPECT_EQ(m, n);
+}
+
+TYPED_TEST_P(ConstructorTest, CopyConstructorAlloc) {
+#if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  TypeParam m(123, hasher, equal, alloc);
+  for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
+  TypeParam n(m, A(11));
+  EXPECT_EQ(m.hash_function(), n.hash_function());
+  EXPECT_EQ(m.key_eq(), n.key_eq());
+  EXPECT_NE(m.get_allocator(), n.get_allocator());
+  EXPECT_EQ(m, n);
+#endif
+}
+
+// TODO(alkis): Test non-propagating allocators on copy constructors.
+
+TYPED_TEST_P(ConstructorTest, MoveConstructor) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  TypeParam m(123, hasher, equal, alloc);
+  for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
+  TypeParam t(m);
+  TypeParam n(std::move(t));
+  EXPECT_EQ(m.hash_function(), n.hash_function());
+  EXPECT_EQ(m.key_eq(), n.key_eq());
+  EXPECT_EQ(m.get_allocator(), n.get_allocator());
+  EXPECT_EQ(m, n);
+}
+
+TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) {
+#if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  TypeParam m(123, hasher, equal, alloc);
+  for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
+  TypeParam t(m);
+  TypeParam n(std::move(t), A(1));
+  EXPECT_EQ(m.hash_function(), n.hash_function());
+  EXPECT_EQ(m.key_eq(), n.key_eq());
+  EXPECT_NE(m.get_allocator(), n.get_allocator());
+  EXPECT_EQ(m, n);
+#endif
+}
+
+// TODO(alkis): Test non-propagating allocators on move constructors.
+
+TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  hash_internal::Generator<T> gen;
+  std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  TypeParam m(values, 123, hasher, equal, alloc);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.key_eq(), equal);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_GE(m.bucket_count(), 123);
+}
+
+TYPED_TEST_P(ConstructorTest, InitializerListBucketAlloc) {
+#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using A = typename TypeParam::allocator_type;
+  hash_internal::Generator<T> gen;
+  std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
+  A alloc(0);
+  TypeParam m(values, 123, alloc);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_GE(m.bucket_count(), 123);
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, InitializerListBucketHashAlloc) {
+#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  A alloc(0);
+  hash_internal::Generator<T> gen;
+  std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
+  TypeParam m(values, 123, hasher, alloc);
+  EXPECT_EQ(m.hash_function(), hasher);
+  EXPECT_EQ(m.get_allocator(), alloc);
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_GE(m.bucket_count(), 123);
+#endif
+}
+
+TYPED_TEST_P(ConstructorTest, Assignment) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  hash_internal::Generator<T> gen;
+  TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc);
+  TypeParam n;
+  n = m;
+  EXPECT_EQ(m.hash_function(), n.hash_function());
+  EXPECT_EQ(m.key_eq(), n.key_eq());
+  EXPECT_EQ(m, n);
+}
+
+// TODO(alkis): Test [non-]propagating allocators on move/copy assignments
+// (it depends on traits).
+
+TYPED_TEST_P(ConstructorTest, MoveAssignment) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  using H = typename TypeParam::hasher;
+  using E = typename TypeParam::key_equal;
+  using A = typename TypeParam::allocator_type;
+  H hasher;
+  E equal;
+  A alloc(0);
+  hash_internal::Generator<T> gen;
+  TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc);
+  TypeParam t(m);
+  TypeParam n;
+  n = std::move(t);
+  EXPECT_EQ(m.hash_function(), n.hash_function());
+  EXPECT_EQ(m.key_eq(), n.key_eq());
+  EXPECT_EQ(m, n);
+}
+
+TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  hash_internal::Generator<T> gen;
+  std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
+  TypeParam m;
+  m = values;
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+}
+
+TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  hash_internal::Generator<T> gen;
+  TypeParam m({gen(), gen(), gen()});
+  TypeParam n({gen()});
+  n = m;
+  EXPECT_EQ(m, n);
+}
+
+TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  hash_internal::Generator<T> gen;
+  TypeParam m({gen(), gen(), gen()});
+  TypeParam t(m);
+  TypeParam n({gen()});
+  n = std::move(t);
+  EXPECT_EQ(m, n);
+}
+
+TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  hash_internal::Generator<T> gen;
+  std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
+  TypeParam m;
+  m = values;
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+}
+
+TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  hash_internal::Generator<T> gen;
+  std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
+  TypeParam m(values);
+  m = *&m;  // Avoid -Wself-assign
+  EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
+}
+
+// We cannot test self move as standard states that it leaves standard
+// containers in unspecified state (and in practice in causes memory-leak
+// according to heap-checker!).
+
+REGISTER_TYPED_TEST_CASE_P(
+    ConstructorTest, NoArgs, BucketCount, BucketCountHash, BucketCountHashEqual,
+    BucketCountHashEqualAlloc, BucketCountAlloc, BucketCountHashAlloc,
+    BucketAlloc, InputIteratorBucketHashEqualAlloc, InputIteratorBucketAlloc,
+    InputIteratorBucketHashAlloc, CopyConstructor, CopyConstructorAlloc,
+    MoveConstructor, MoveConstructorAlloc, InitializerListBucketHashEqualAlloc,
+    InitializerListBucketAlloc, InitializerListBucketHashAlloc, Assignment,
+    MoveAssignment, AssignmentFromInitializerList,
+    AssignmentOverwritesExisting, MoveAssignmentOverwritesExisting,
+    AssignmentFromInitializerListOverwritesExisting, AssignmentOnSelf);
+
+}  // namespace container_internal
+}  // namespace absl
+#endif  // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_CONSTRUCTOR_TEST_H_