Debian Codegraph @

tests/raw_hash_set_allocator_test.cc

raw
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 <limits>
16 #include <scoped_allocator>
17
18 #include "gtest/gtest.h"
19 #include "parallel_hashmap/phmap.h"
20 #include "tracked.h"
21
22 namespace phmap {
23 namespace priv {
24 namespace {
25
26 enum AllocSpec {
27 kPropagateOnCopy = 1,
28 kPropagateOnMove = 2,
29 kPropagateOnSwap = 4,
30 };
31
32 struct AllocState {
33 size_t num_allocs = 0;
34 std::set<void*> owned;
35 };
36
37 template <class T,
38 int Spec = kPropagateOnCopy | kPropagateOnMove | kPropagateOnSwap>
39 class CheckedAlloc {
40 public:
41 template <class, int>
42 friend class CheckedAlloc;
43
44 using value_type = T;
45
46 CheckedAlloc() {}
47 explicit CheckedAlloc(size_t id) : id_(id) {}
48 CheckedAlloc(const CheckedAlloc&) = default;
49 CheckedAlloc& operator=(const CheckedAlloc&) = default;
50
51 template <class U>
52 CheckedAlloc(const CheckedAlloc<U, Spec>& that)
53 : id_(that.id_), state_(that.state_) {}
54
55 template <class U>
56 struct rebind {
57 using other = CheckedAlloc<U, Spec>;
58 };
59
60 using propagate_on_container_copy_assignment =
61 std::integral_constant<bool, (Spec & kPropagateOnCopy) != 0>;
62
63 using propagate_on_container_move_assignment =
64 std::integral_constant<bool, (Spec & kPropagateOnMove) != 0>;
65
66 using propagate_on_container_swap =
67 std::integral_constant<bool, (Spec & kPropagateOnSwap) != 0>;
68
69 CheckedAlloc select_on_container_copy_construction() const {
70 PHMAP_IF_CONSTEXPR (Spec & kPropagateOnCopy) return *this;
71 return {};
72 }
73
74 T* allocate(size_t n) {
75 T* ptr = std::allocator<T>().allocate(n);
76 track_alloc(ptr);
77 return ptr;
78 }
79 void deallocate(T* ptr, size_t n) {
80 memset(ptr, 0, n * sizeof(T)); // The freed memory must be unpoisoned.
81 track_dealloc(ptr);
82 return std::allocator<T>().deallocate(ptr, n);
83 }
84
85 friend bool operator==(const CheckedAlloc& a, const CheckedAlloc& b) {
86 return a.id_ == b.id_;
87 }
88 friend bool operator!=(const CheckedAlloc& a, const CheckedAlloc& b) {
89 return !(a == b);
90 }
91
92 size_t num_allocs() const { return state_->num_allocs; }
93
94 void swap(CheckedAlloc& that) {
95 using std::swap;
96 swap(id_, that.id_);
97 swap(state_, that.state_);
98 }
99
100 friend void swap(CheckedAlloc& a, CheckedAlloc& b) { a.swap(b); }
101
102 friend std::ostream& operator<<(std::ostream& o, const CheckedAlloc& a) {
103 return o << "alloc(" << a.id_ << ")";
104 }
105
106 private:
107 void track_alloc(void* ptr) {
108 AllocState* state = state_.get();
109 ++state->num_allocs;
110 if (!state->owned.insert(ptr).second)
111 ADD_FAILURE() << *this << " got previously allocated memory: " << ptr;
112 }
113 void track_dealloc(void* ptr) {
114 if (state_->owned.erase(ptr) != 1)
115 ADD_FAILURE() << *this
116 << " deleting memory owned by another allocator: " << ptr;
117 }
118
119 size_t id_ = std::numeric_limits<size_t>::max();
120
121 std::shared_ptr<AllocState> state_ = std::make_shared<AllocState>();
122 };
123
124 struct Identity {
125 int32_t operator()(int32_t v) const { return v; }
126 };
127
128 struct Policy {
129 using slot_type = Tracked<int32_t>;
130 using init_type = Tracked<int32_t>;
131 using key_type = int32_t;
132 using is_flat = std::false_type;
133
134 template <class allocator_type, class... Args>
135 static void construct(allocator_type* alloc, slot_type* slot,
136 Args&&... args) {
137 std::allocator_traits<allocator_type>::construct(
138 *alloc, slot, std::forward<Args>(args)...);
139 }
140
141 template <class allocator_type>
142 static void destroy(allocator_type* alloc, slot_type* slot) {
143 std::allocator_traits<allocator_type>::destroy(*alloc, slot);
144 }
145
146 template <class allocator_type>
147 static void transfer(allocator_type* alloc, slot_type* new_slot,
148 slot_type* old_slot) {
149 construct(alloc, new_slot, std::move(*old_slot));
150 destroy(alloc, old_slot);
151 }
152
153 template <class F>
154 static auto apply(F&& f, int32_t v) -> decltype(std::forward<F>(f)(v, v)) {
155 return std::forward<F>(f)(v, v);
156 }
157
158 template <class F>
159 static auto apply(F&& f, const slot_type& v)
160 -> decltype(std::forward<F>(f)(v.val(), v)) {
161 return std::forward<F>(f)(v.val(), v);
162 }
163
164 template <class F>
165 static auto apply(F&& f, slot_type&& v)
166 -> decltype(std::forward<F>(f)(v.val(), std::move(v))) {
167 return std::forward<F>(f)(v.val(), std::move(v));
168 }
169
170 static slot_type& element(slot_type* slot) { return *slot; }
171 };
172
173 template <int Spec>
174 struct PropagateTest : public ::testing::Test {
175 using Alloc = CheckedAlloc<Tracked<int32_t>, Spec>;
176
177 using Table = raw_hash_set<Policy, Identity, std::equal_to<int32_t>, Alloc>;
178
179 PropagateTest() {
180 EXPECT_EQ(a1, t1.get_allocator());
181 EXPECT_NE(a2, t1.get_allocator());
182 }
183
184 Alloc a1 = Alloc(1);
185 Table t1 = Table(0, a1);
186 Alloc a2 = Alloc(2);
187 };
188
189 using PropagateOnAll =
190 PropagateTest<kPropagateOnCopy | kPropagateOnMove | kPropagateOnSwap>;
191 using NoPropagateOnCopy = PropagateTest<kPropagateOnMove | kPropagateOnSwap>;
192 using NoPropagateOnMove = PropagateTest<kPropagateOnCopy | kPropagateOnSwap>;
193
194 TEST_F(PropagateOnAll, Empty) { EXPECT_EQ(0, a1.num_allocs()); }
195
196 TEST_F(PropagateOnAll, InsertAllocates) {
197 auto it = t1.insert(0).first;
198 EXPECT_EQ(1, a1.num_allocs());
199 EXPECT_EQ(0, it->num_moves());
200 EXPECT_EQ(0, it->num_copies());
201 }
202
203 TEST_F(PropagateOnAll, InsertDecomposes) {
204 auto it = t1.insert(0).first;
205 EXPECT_EQ(1, a1.num_allocs());
206 EXPECT_EQ(0, it->num_moves());
207 EXPECT_EQ(0, it->num_copies());
208
209 EXPECT_FALSE(t1.insert(0).second);
210 EXPECT_EQ(1, a1.num_allocs());
211 EXPECT_EQ(0, it->num_moves());
212 EXPECT_EQ(0, it->num_copies());
213 }
214
215 TEST_F(PropagateOnAll, RehashMoves) {
216 auto it = t1.insert(0).first;
217 EXPECT_EQ(0, it->num_moves());
218 t1.rehash(2 * t1.capacity());
219 EXPECT_EQ(2, a1.num_allocs());
220 it = t1.find(0);
221 EXPECT_EQ(1, it->num_moves());
222 EXPECT_EQ(0, it->num_copies());
223 }
224
225 TEST_F(PropagateOnAll, CopyConstructor) {
226 auto it = t1.insert(0).first;
227 Table u(t1);
228 EXPECT_EQ(2, a1.num_allocs());
229 EXPECT_EQ(0, it->num_moves());
230 EXPECT_EQ(1, it->num_copies());
231 }
232
233 TEST_F(NoPropagateOnCopy, CopyConstructor) {
234 auto it = t1.insert(0).first;
235 Table u(t1);
236 EXPECT_EQ(1, a1.num_allocs());
237 EXPECT_EQ(1, u.get_allocator().num_allocs());
238 EXPECT_EQ(0, it->num_moves());
239 EXPECT_EQ(1, it->num_copies());
240 }
241
242 TEST_F(PropagateOnAll, CopyConstructorWithSameAlloc) {
243 auto it = t1.insert(0).first;
244 Table u(t1, a1);
245 EXPECT_EQ(2, a1.num_allocs());
246 EXPECT_EQ(0, it->num_moves());
247 EXPECT_EQ(1, it->num_copies());
248 }
249
250 TEST_F(NoPropagateOnCopy, CopyConstructorWithSameAlloc) {
251 auto it = t1.insert(0).first;
252 Table u(t1, a1);
253 EXPECT_EQ(2, a1.num_allocs());
254 EXPECT_EQ(0, it->num_moves());
255 EXPECT_EQ(1, it->num_copies());
256 }
257
258 TEST_F(PropagateOnAll, CopyConstructorWithDifferentAlloc) {
259 auto it = t1.insert(0).first;
260 Table u(t1, a2);
261 EXPECT_EQ(a2, u.get_allocator());
262 EXPECT_EQ(1, a1.num_allocs());
263 EXPECT_EQ(1, a2.num_allocs());
264 EXPECT_EQ(0, it->num_moves());
265 EXPECT_EQ(1, it->num_copies());
266 }
267
268 TEST_F(NoPropagateOnCopy, CopyConstructorWithDifferentAlloc) {
269 auto it = t1.insert(0).first;
270 Table u(t1, a2);
271 EXPECT_EQ(a2, u.get_allocator());
272 EXPECT_EQ(1, a1.num_allocs());
273 EXPECT_EQ(1, a2.num_allocs());
274 EXPECT_EQ(0, it->num_moves());
275 EXPECT_EQ(1, it->num_copies());
276 }
277
278 TEST_F(PropagateOnAll, MoveConstructor) {
279 auto it = t1.insert(0).first;
280 Table u(std::move(t1));
281 EXPECT_EQ(1, a1.num_allocs());
282 EXPECT_EQ(0, it->num_moves());
283 EXPECT_EQ(0, it->num_copies());
284 }
285
286 TEST_F(NoPropagateOnMove, MoveConstructor) {
287 auto it = t1.insert(0).first;
288 Table u(std::move(t1));
289 EXPECT_EQ(1, a1.num_allocs());
290 EXPECT_EQ(0, it->num_moves());
291 EXPECT_EQ(0, it->num_copies());
292 }
293
294 TEST_F(PropagateOnAll, MoveConstructorWithSameAlloc) {
295 auto it = t1.insert(0).first;
296 Table u(std::move(t1), a1);
297 EXPECT_EQ(1, a1.num_allocs());
298 EXPECT_EQ(0, it->num_moves());
299 EXPECT_EQ(0, it->num_copies());
300 }
301
302 TEST_F(NoPropagateOnMove, MoveConstructorWithSameAlloc) {
303 auto it = t1.insert(0).first;
304 Table u(std::move(t1), a1);
305 EXPECT_EQ(1, a1.num_allocs());
306 EXPECT_EQ(0, it->num_moves());
307 EXPECT_EQ(0, it->num_copies());
308 }
309
310 TEST_F(PropagateOnAll, MoveConstructorWithDifferentAlloc) {
311 auto it = t1.insert(0).first;
312 Table u(std::move(t1), a2);
313 it = u.find(0);
314 EXPECT_EQ(a2, u.get_allocator());
315 EXPECT_EQ(1, a1.num_allocs());
316 EXPECT_EQ(1, a2.num_allocs());
317 EXPECT_EQ(1, it->num_moves());
318 EXPECT_EQ(0, it->num_copies());
319 }
320
321 TEST_F(NoPropagateOnMove, MoveConstructorWithDifferentAlloc) {
322 auto it = t1.insert(0).first;
323 Table u(std::move(t1), a2);
324 it = u.find(0);
325 EXPECT_EQ(a2, u.get_allocator());
326 EXPECT_EQ(1, a1.num_allocs());
327 EXPECT_EQ(1, a2.num_allocs());
328 EXPECT_EQ(1, it->num_moves());
329 EXPECT_EQ(0, it->num_copies());
330 }
331
332 TEST_F(PropagateOnAll, CopyAssignmentWithSameAlloc) {
333 auto it = t1.insert(0).first;
334 Table u(0, a1);
335 u = t1;
336 EXPECT_EQ(2, a1.num_allocs());
337 EXPECT_EQ(0, it->num_moves());
338 EXPECT_EQ(1, it->num_copies());
339 }
340
341 TEST_F(NoPropagateOnCopy, CopyAssignmentWithSameAlloc) {
342 auto it = t1.insert(0).first;
343 Table u(0, a1);
344 u = t1;
345 EXPECT_EQ(2, a1.num_allocs());
346 EXPECT_EQ(0, it->num_moves());
347 EXPECT_EQ(1, it->num_copies());
348 }
349
350 TEST_F(PropagateOnAll, CopyAssignmentWithDifferentAlloc) {
351 auto it = t1.insert(0).first;
352 Table u(0, a2);
353 u = t1;
354 EXPECT_EQ(a1, u.get_allocator());
355 EXPECT_EQ(2, a1.num_allocs());
356 EXPECT_EQ(0, a2.num_allocs());
357 EXPECT_EQ(0, it->num_moves());
358 EXPECT_EQ(1, it->num_copies());
359 }
360
361 TEST_F(NoPropagateOnCopy, CopyAssignmentWithDifferentAlloc) {
362 auto it = t1.insert(0).first;
363 Table u(0, a2);
364 u = t1;
365 EXPECT_EQ(a2, u.get_allocator());
366 EXPECT_EQ(1, a1.num_allocs());
367 EXPECT_EQ(1, a2.num_allocs());
368 EXPECT_EQ(0, it->num_moves());
369 EXPECT_EQ(1, it->num_copies());
370 }
371
372 TEST_F(PropagateOnAll, MoveAssignmentWithSameAlloc) {
373 auto it = t1.insert(0).first;
374 Table u(0, a1);
375 u = std::move(t1);
376 EXPECT_EQ(a1, u.get_allocator());
377 EXPECT_EQ(1, a1.num_allocs());
378 EXPECT_EQ(0, it->num_moves());
379 EXPECT_EQ(0, it->num_copies());
380 }
381
382 TEST_F(NoPropagateOnMove, MoveAssignmentWithSameAlloc) {
383 auto it = t1.insert(0).first;
384 Table u(0, a1);
385 u = std::move(t1);
386 EXPECT_EQ(a1, u.get_allocator());
387 EXPECT_EQ(1, a1.num_allocs());
388 EXPECT_EQ(0, it->num_moves());
389 EXPECT_EQ(0, it->num_copies());
390 }
391
392 TEST_F(PropagateOnAll, MoveAssignmentWithDifferentAlloc) {
393 auto it = t1.insert(0).first;
394 Table u(0, a2);
395 u = std::move(t1);
396 EXPECT_EQ(a1, u.get_allocator());
397 EXPECT_EQ(1, a1.num_allocs());
398 EXPECT_EQ(0, a2.num_allocs());
399 EXPECT_EQ(0, it->num_moves());
400 EXPECT_EQ(0, it->num_copies());
401 }
402
403 TEST_F(NoPropagateOnMove, MoveAssignmentWithDifferentAlloc) {
404 auto it = t1.insert(0).first;
405 Table u(0, a2);
406 u = std::move(t1);
407 it = u.find(0);
408 EXPECT_EQ(a2, u.get_allocator());
409 EXPECT_EQ(1, a1.num_allocs());
410 EXPECT_EQ(1, a2.num_allocs());
411 EXPECT_EQ(1, it->num_moves());
412 EXPECT_EQ(0, it->num_copies());
413 }
414
415 TEST_F(PropagateOnAll, Swap) {
416 auto it = t1.insert(0).first;
417 Table u(0, a2);
418 u.swap(t1);
419 EXPECT_EQ(a1, u.get_allocator());
420 EXPECT_EQ(a2, t1.get_allocator());
421 EXPECT_EQ(1, a1.num_allocs());
422 EXPECT_EQ(0, a2.num_allocs());
423 EXPECT_EQ(0, it->num_moves());
424 EXPECT_EQ(0, it->num_copies());
425 }
426
427 } // namespace
428 } // namespace priv
429 } // namespace phmap