1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/container/internal/container_memory.h"
16
17 #include <cstddef>
18 #include <cstdint>
19 #include <memory>
20 #include <tuple>
21 #include <type_traits>
22 #include <typeindex>
23 #include <typeinfo>
24 #include <utility>
25
26 #include "gmock/gmock.h"
27 #include "gtest/gtest.h"
28 #include "absl/base/no_destructor.h"
29 #include "absl/container/internal/test_instance_tracker.h"
30 #include "absl/meta/type_traits.h"
31 #include "absl/strings/string_view.h"
32
33 namespace absl {
34 ABSL_NAMESPACE_BEGIN
35 namespace container_internal {
36 namespace {
37
38 using ::absl::test_internal::CopyableMovableInstance;
39 using ::absl::test_internal::InstanceTracker;
40 using ::testing::_;
41 using ::testing::ElementsAre;
42 using ::testing::Gt;
43 using ::testing::Pair;
44
TEST(Memory,AlignmentLargerThanBase)45 TEST(Memory, AlignmentLargerThanBase) {
46 std::allocator<int8_t> alloc;
47 void* mem = Allocate<2>(&alloc, 3);
48 EXPECT_EQ(0, reinterpret_cast<uintptr_t>(mem) % 2);
49 memcpy(mem, "abc", 3);
50 Deallocate<2>(&alloc, mem, 3);
51 }
52
TEST(Memory,AlignmentSmallerThanBase)53 TEST(Memory, AlignmentSmallerThanBase) {
54 std::allocator<int64_t> alloc;
55 void* mem = Allocate<2>(&alloc, 3);
56 EXPECT_EQ(0, reinterpret_cast<uintptr_t>(mem) % 2);
57 memcpy(mem, "abc", 3);
58 Deallocate<2>(&alloc, mem, 3);
59 }
60
AllocationMap()61 std::map<std::type_index, int>& AllocationMap() {
62 static absl::NoDestructor<std::map<std::type_index, int>> map;
63 return *map;
64 }
65
66 template <typename T>
67 struct TypeCountingAllocator {
68 TypeCountingAllocator() = default;
69 template <typename U>
TypeCountingAllocatorabsl::container_internal::__anon76d253f30111::TypeCountingAllocator70 TypeCountingAllocator(const TypeCountingAllocator<U>&) {} // NOLINT
71
72 using value_type = T;
73
allocateabsl::container_internal::__anon76d253f30111::TypeCountingAllocator74 T* allocate(size_t n, const void* = nullptr) {
75 AllocationMap()[typeid(T)] += n;
76 return std::allocator<T>().allocate(n);
77 }
deallocateabsl::container_internal::__anon76d253f30111::TypeCountingAllocator78 void deallocate(T* p, std::size_t n) {
79 AllocationMap()[typeid(T)] -= n;
80 return std::allocator<T>().deallocate(p, n);
81 }
82 };
83
TEST(Memory,AllocateDeallocateMatchType)84 TEST(Memory, AllocateDeallocateMatchType) {
85 TypeCountingAllocator<int> alloc;
86 void* mem = Allocate<1>(&alloc, 1);
87 // Verify that it was allocated
88 EXPECT_THAT(AllocationMap(), ElementsAre(Pair(_, Gt(0))));
89 Deallocate<1>(&alloc, mem, 1);
90 // Verify that the deallocation matched.
91 EXPECT_THAT(AllocationMap(), ElementsAre(Pair(_, 0)));
92 }
93
94 class Fixture : public ::testing::Test {
95 using Alloc = std::allocator<std::string>;
96
97 public:
Fixture()98 Fixture() { ptr_ = std::allocator_traits<Alloc>::allocate(*alloc(), 1); }
~Fixture()99 ~Fixture() override {
100 std::allocator_traits<Alloc>::destroy(*alloc(), ptr_);
101 std::allocator_traits<Alloc>::deallocate(*alloc(), ptr_, 1);
102 }
ptr()103 std::string* ptr() { return ptr_; }
alloc()104 Alloc* alloc() { return &alloc_; }
105
106 private:
107 Alloc alloc_;
108 std::string* ptr_;
109 };
110
TEST_F(Fixture,ConstructNoArgs)111 TEST_F(Fixture, ConstructNoArgs) {
112 ConstructFromTuple(alloc(), ptr(), std::forward_as_tuple());
113 EXPECT_EQ(*ptr(), "");
114 }
115
TEST_F(Fixture,ConstructOneArg)116 TEST_F(Fixture, ConstructOneArg) {
117 ConstructFromTuple(alloc(), ptr(), std::forward_as_tuple("abcde"));
118 EXPECT_EQ(*ptr(), "abcde");
119 }
120
TEST_F(Fixture,ConstructTwoArg)121 TEST_F(Fixture, ConstructTwoArg) {
122 ConstructFromTuple(alloc(), ptr(), std::forward_as_tuple(5, 'a'));
123 EXPECT_EQ(*ptr(), "aaaaa");
124 }
125
TEST(PairArgs,NoArgs)126 TEST(PairArgs, NoArgs) {
127 EXPECT_THAT(PairArgs(),
128 Pair(std::forward_as_tuple(), std::forward_as_tuple()));
129 }
130
TEST(PairArgs,TwoArgs)131 TEST(PairArgs, TwoArgs) {
132 EXPECT_EQ(
133 std::make_pair(std::forward_as_tuple(1), std::forward_as_tuple('A')),
134 PairArgs(1, 'A'));
135 }
136
TEST(PairArgs,Pair)137 TEST(PairArgs, Pair) {
138 EXPECT_EQ(
139 std::make_pair(std::forward_as_tuple(1), std::forward_as_tuple('A')),
140 PairArgs(std::make_pair(1, 'A')));
141 }
142
TEST(PairArgs,Piecewise)143 TEST(PairArgs, Piecewise) {
144 EXPECT_EQ(
145 std::make_pair(std::forward_as_tuple(1), std::forward_as_tuple('A')),
146 PairArgs(std::piecewise_construct, std::forward_as_tuple(1),
147 std::forward_as_tuple('A')));
148 }
149
TEST(WithConstructed,Simple)150 TEST(WithConstructed, Simple) {
151 EXPECT_EQ(1, WithConstructed<absl::string_view>(
152 std::make_tuple(std::string("a")),
153 [](absl::string_view str) { return str.size(); }));
154 }
155
156 template <class F, class Arg>
DecomposeValue(std::declval<F> (),std::declval<Arg> ())157 decltype(DecomposeValue(std::declval<F>(), std::declval<Arg>()))
158 DecomposeValueImpl(int, F&& f, Arg&& arg) {
159 return DecomposeValue(std::forward<F>(f), std::forward<Arg>(arg));
160 }
161
162 template <class F, class Arg>
DecomposeValueImpl(char,F && f,Arg && arg)163 const char* DecomposeValueImpl(char, F&& f, Arg&& arg) {
164 return "not decomposable";
165 }
166
167 template <class F, class Arg>
168 decltype(DecomposeValueImpl(0, std::declval<F>(), std::declval<Arg>()))
TryDecomposeValue(F && f,Arg && arg)169 TryDecomposeValue(F&& f, Arg&& arg) {
170 return DecomposeValueImpl(0, std::forward<F>(f), std::forward<Arg>(arg));
171 }
172
TEST(DecomposeValue,Decomposable)173 TEST(DecomposeValue, Decomposable) {
174 auto f = [](const int& x, int&& y) { // NOLINT
175 EXPECT_EQ(&x, &y);
176 EXPECT_EQ(42, x);
177 return 'A';
178 };
179 EXPECT_EQ('A', TryDecomposeValue(f, 42));
180 }
181
TEST(DecomposeValue,NotDecomposable)182 TEST(DecomposeValue, NotDecomposable) {
183 auto f = [](void*) {
184 ADD_FAILURE() << "Must not be called";
185 return 'A';
186 };
187 EXPECT_STREQ("not decomposable", TryDecomposeValue(f, 42));
188 }
189
190 template <class F, class... Args>
DecomposePair(std::declval<F> (),std::declval<Args> ()...)191 decltype(DecomposePair(std::declval<F>(), std::declval<Args>()...))
192 DecomposePairImpl(int, F&& f, Args&&... args) {
193 return DecomposePair(std::forward<F>(f), std::forward<Args>(args)...);
194 }
195
196 template <class F, class... Args>
DecomposePairImpl(char,F && f,Args &&...args)197 const char* DecomposePairImpl(char, F&& f, Args&&... args) {
198 return "not decomposable";
199 }
200
201 template <class F, class... Args>
202 decltype(DecomposePairImpl(0, std::declval<F>(), std::declval<Args>()...))
TryDecomposePair(F && f,Args &&...args)203 TryDecomposePair(F&& f, Args&&... args) {
204 return DecomposePairImpl(0, std::forward<F>(f), std::forward<Args>(args)...);
205 }
206
TEST(DecomposePair,Decomposable)207 TEST(DecomposePair, Decomposable) {
208 auto f = [](const int& x, // NOLINT
209 std::piecewise_construct_t, std::tuple<int&&> k,
210 std::tuple<double>&& v) {
211 EXPECT_EQ(&x, &std::get<0>(k));
212 EXPECT_EQ(42, x);
213 EXPECT_EQ(0.5, std::get<0>(v));
214 return 'A';
215 };
216 EXPECT_EQ('A', TryDecomposePair(f, 42, 0.5));
217 EXPECT_EQ('A', TryDecomposePair(f, std::make_pair(42, 0.5)));
218 EXPECT_EQ('A', TryDecomposePair(f, std::piecewise_construct,
219 std::make_tuple(42), std::make_tuple(0.5)));
220 }
221
TEST(DecomposePair,NotDecomposable)222 TEST(DecomposePair, NotDecomposable) {
223 auto f = [](...) {
224 ADD_FAILURE() << "Must not be called";
225 return 'A';
226 };
227 EXPECT_STREQ("not decomposable", TryDecomposePair(f));
228 EXPECT_STREQ("not decomposable",
229 TryDecomposePair(f, std::piecewise_construct, std::make_tuple(),
230 std::make_tuple(0.5)));
231 }
232
TEST(MapSlotPolicy,ConstKeyAndValue)233 TEST(MapSlotPolicy, ConstKeyAndValue) {
234 using slot_policy = map_slot_policy<const CopyableMovableInstance,
235 const CopyableMovableInstance>;
236 using slot_type = typename slot_policy::slot_type;
237
238 union Slots {
239 Slots() {}
240 ~Slots() {}
241 slot_type slots[100];
242 } slots;
243
244 std::allocator<
245 std::pair<const CopyableMovableInstance, const CopyableMovableInstance>>
246 alloc;
247 InstanceTracker tracker;
248 slot_policy::construct(&alloc, &slots.slots[0], CopyableMovableInstance(1),
249 CopyableMovableInstance(1));
250 for (int i = 0; i < 99; ++i) {
251 slot_policy::transfer(&alloc, &slots.slots[i + 1], &slots.slots[i]);
252 }
253 slot_policy::destroy(&alloc, &slots.slots[99]);
254
255 EXPECT_EQ(tracker.copies(), 0);
256 }
257
TEST(MapSlotPolicy,TransferReturnsTrue)258 TEST(MapSlotPolicy, TransferReturnsTrue) {
259 {
260 using slot_policy = map_slot_policy<int, float>;
261 EXPECT_TRUE(
262 (std::is_same<decltype(slot_policy::transfer<std::allocator<char>>(
263 nullptr, nullptr, nullptr)),
264 std::true_type>::value));
265 }
266 {
267 struct NonRelocatable {
268 NonRelocatable() = default;
269 NonRelocatable(NonRelocatable&&) {}
270 NonRelocatable& operator=(NonRelocatable&&) { return *this; }
271 void* self = nullptr;
272 };
273
274 EXPECT_FALSE(absl::is_trivially_relocatable<NonRelocatable>::value);
275 using slot_policy = map_slot_policy<int, NonRelocatable>;
276 EXPECT_TRUE(
277 (std::is_same<decltype(slot_policy::transfer<std::allocator<char>>(
278 nullptr, nullptr, nullptr)),
279 std::false_type>::value));
280 }
281 }
282
TEST(MapSlotPolicy,DestroyReturnsTrue)283 TEST(MapSlotPolicy, DestroyReturnsTrue) {
284 {
285 using slot_policy = map_slot_policy<int, float>;
286 EXPECT_TRUE(
287 (std::is_same<decltype(slot_policy::destroy<std::allocator<char>>(
288 nullptr, nullptr)),
289 std::true_type>::value));
290 }
291 {
292 EXPECT_FALSE(std::is_trivially_destructible<std::unique_ptr<int>>::value);
293 using slot_policy = map_slot_policy<int, std::unique_ptr<int>>;
294 EXPECT_TRUE(
295 (std::is_same<decltype(slot_policy::destroy<std::allocator<char>>(
296 nullptr, nullptr)),
297 std::false_type>::value));
298 }
299 }
300
TEST(ApplyTest,TypeErasedApplyToSlotFn)301 TEST(ApplyTest, TypeErasedApplyToSlotFn) {
302 size_t x = 7;
303 auto fn = [](size_t v) { return v * 2; };
304 EXPECT_EQ((TypeErasedApplyToSlotFn<decltype(fn), size_t>(&fn, &x)), 14);
305 }
306
TEST(ApplyTest,TypeErasedDerefAndApplyToSlotFn)307 TEST(ApplyTest, TypeErasedDerefAndApplyToSlotFn) {
308 size_t x = 7;
309 auto fn = [](size_t v) { return v * 2; };
310 size_t* x_ptr = &x;
311 EXPECT_EQ(
312 (TypeErasedDerefAndApplyToSlotFn<decltype(fn), size_t>(&fn, &x_ptr)), 14);
313 }
314
315 } // namespace
316 } // namespace container_internal
317 ABSL_NAMESPACE_END
318 } // namespace absl
319