497 lines
16 KiB
C++
497 lines
16 KiB
C++
// 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
|
|
//
|
|
// https://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 PHMAP_PRIV_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
|
|
#define PHMAP_PRIV_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
|
|
|
|
#include <algorithm>
|
|
#include <vector>
|
|
#include <unordered_map>
|
|
|
|
#ifdef _MSC_VER
|
|
#pragma warning(push, 0)
|
|
#endif
|
|
|
|
#include "gmock/gmock.h"
|
|
#include "gtest/gtest.h"
|
|
#include "hash_generator_testing.h"
|
|
#include "hash_policy_testing.h"
|
|
|
|
#ifdef _MSC_VER
|
|
#pragma warning(pop)
|
|
#endif
|
|
|
|
namespace phmap {
|
|
namespace priv {
|
|
|
|
template <class UnordMap>
|
|
class ConstructorTest : public ::testing::Test {};
|
|
|
|
TYPED_TEST_SUITE_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);
|
|
}
|
|
|
|
template <typename T>
|
|
struct is_std_unordered_map : std::false_type {};
|
|
|
|
template <typename... T>
|
|
struct is_std_unordered_map<std::unordered_map<T...>> : std::true_type {};
|
|
|
|
#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
|
|
using has_cxx14_std_apis = std::true_type;
|
|
#else
|
|
using has_cxx14_std_apis = std::false_type;
|
|
#endif
|
|
|
|
template <typename T>
|
|
using expect_cxx14_apis =
|
|
phmap::disjunction<phmap::negation<is_std_unordered_map<T>>,
|
|
has_cxx14_std_apis>;
|
|
|
|
template <typename TypeParam>
|
|
void BucketCountAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void BucketCountAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, BucketCountAlloc) {
|
|
BucketCountAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void BucketCountHashAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void BucketCountHashAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, BucketCountHashAlloc) {
|
|
BucketCountHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
|
|
}
|
|
|
|
#if PHMAP_UNORDERED_SUPPORTS_ALLOC_CTORS
|
|
using has_alloc_std_constructors = std::true_type;
|
|
#else
|
|
using has_alloc_std_constructors = std::false_type;
|
|
#endif
|
|
|
|
template <typename T>
|
|
using expect_alloc_constructors =
|
|
phmap::disjunction<phmap::negation<is_std_unordered_map<T>>,
|
|
has_alloc_std_constructors>;
|
|
|
|
template <typename TypeParam>
|
|
void AllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void AllocTest(std::true_type) {
|
|
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());
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, Alloc) {
|
|
AllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
|
|
}
|
|
|
|
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);
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void InputIteratorBucketAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void InputIteratorBucketAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, InputIteratorBucketAlloc) {
|
|
InputIteratorBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void InputIteratorBucketHashAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void InputIteratorBucketHashAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashAlloc) {
|
|
InputIteratorBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
|
|
}
|
|
|
|
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);
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void CopyConstructorAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void CopyConstructorAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, CopyConstructorAlloc) {
|
|
CopyConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
|
|
}
|
|
|
|
// 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);
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void MoveConstructorAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void MoveConstructorAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) {
|
|
MoveConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
|
|
}
|
|
|
|
// 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);
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void InitializerListBucketAllocTest(std::false_type) {}
|
|
|
|
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;
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, InitializerListBucketAlloc) {
|
|
InitializerListBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
|
|
}
|
|
|
|
template <typename TypeParam>
|
|
void InitializerListBucketHashAllocTest(std::false_type) {}
|
|
|
|
template <typename TypeParam>
|
|
void InitializerListBucketHashAllocTest(std::true_type) {
|
|
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);
|
|
}
|
|
|
|
TYPED_TEST_P(ConstructorTest, InitializerListBucketHashAlloc) {
|
|
InitializerListBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
|
|
}
|
|
|
|
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_SUITE_P(
|
|
ConstructorTest, NoArgs, BucketCount, BucketCountHash, BucketCountHashEqual,
|
|
BucketCountHashEqualAlloc, BucketCountAlloc, BucketCountHashAlloc, Alloc,
|
|
InputIteratorBucketHashEqualAlloc, InputIteratorBucketAlloc,
|
|
InputIteratorBucketHashAlloc, CopyConstructor, CopyConstructorAlloc,
|
|
MoveConstructor, MoveConstructorAlloc, InitializerListBucketHashEqualAlloc,
|
|
InitializerListBucketAlloc, InitializerListBucketHashAlloc, Assignment,
|
|
MoveAssignment, AssignmentFromInitializerList, AssignmentOverwritesExisting,
|
|
MoveAssignmentOverwritesExisting,
|
|
AssignmentFromInitializerListOverwritesExisting, AssignmentOnSelf);
|
|
|
|
} // namespace priv
|
|
} // namespace phmap
|
|
|
|
#endif // PHMAP_PRIV_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
|