raw_hash_set_allocator_test.cc
Go to the documentation of this file.
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 "absl/container/internal/raw_hash_set.h"
20 #include "absl/container/internal/tracked.h"
21 
22 namespace absl {
23 namespace container_internal {
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  if (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 
133  template <class allocator_type, class... Args>
134  static void construct(allocator_type* alloc, slot_type* slot,
135  Args&&... args) {
136  std::allocator_traits<allocator_type>::construct(
137  *alloc, slot, std::forward<Args>(args)...);
138  }
139 
140  template <class allocator_type>
141  static void destroy(allocator_type* alloc, slot_type* slot) {
142  std::allocator_traits<allocator_type>::destroy(*alloc, slot);
143  }
144 
145  template <class allocator_type>
146  static void transfer(allocator_type* alloc, slot_type* new_slot,
147  slot_type* old_slot) {
148  construct(alloc, new_slot, std::move(*old_slot));
149  destroy(alloc, old_slot);
150  }
151 
152  template <class F>
153  static auto apply(F&& f, int32_t v) -> decltype(std::forward<F>(f)(v, v)) {
154  return std::forward<F>(f)(v, v);
155  }
156 
157  template <class F>
158  static auto apply(F&& f, const slot_type& v)
159  -> decltype(std::forward<F>(f)(v.val(), v)) {
160  return std::forward<F>(f)(v.val(), v);
161  }
162 
163  template <class F>
164  static auto apply(F&& f, slot_type&& v)
165  -> decltype(std::forward<F>(f)(v.val(), std::move(v))) {
166  return std::forward<F>(f)(v.val(), std::move(v));
167  }
168 
169  static slot_type& element(slot_type* slot) { return *slot; }
170 };
171 
172 template <int Spec>
173 struct PropagateTest : public ::testing::Test {
174  using Alloc = CheckedAlloc<Tracked<int32_t>, Spec>;
175 
176  using Table = raw_hash_set<Policy, Identity, std::equal_to<int32_t>, Alloc>;
177 
178  PropagateTest() {
179  EXPECT_EQ(a1, t1.get_allocator());
180  EXPECT_NE(a2, t1.get_allocator());
181  }
182 
183  Alloc a1 = Alloc(1);
184  Table t1 = Table(0, a1);
185  Alloc a2 = Alloc(2);
186 };
187 
188 using PropagateOnAll =
189  PropagateTest<kPropagateOnCopy | kPropagateOnMove | kPropagateOnSwap>;
190 using NoPropagateOnCopy = PropagateTest<kPropagateOnMove | kPropagateOnSwap>;
191 using NoPropagateOnMove = PropagateTest<kPropagateOnCopy | kPropagateOnSwap>;
192 
193 TEST_F(PropagateOnAll, Empty) { EXPECT_EQ(0, a1.num_allocs()); }
194 
195 TEST_F(PropagateOnAll, InsertAllocates) {
196  auto it = t1.insert(0).first;
197  EXPECT_EQ(1, a1.num_allocs());
198  EXPECT_EQ(0, it->num_moves());
199  EXPECT_EQ(0, it->num_copies());
200 }
201 
202 TEST_F(PropagateOnAll, InsertDecomposes) {
203  auto it = t1.insert(0).first;
204  EXPECT_EQ(1, a1.num_allocs());
205  EXPECT_EQ(0, it->num_moves());
206  EXPECT_EQ(0, it->num_copies());
207 
208  EXPECT_FALSE(t1.insert(0).second);
209  EXPECT_EQ(1, a1.num_allocs());
210  EXPECT_EQ(0, it->num_moves());
211  EXPECT_EQ(0, it->num_copies());
212 }
213 
214 TEST_F(PropagateOnAll, RehashMoves) {
215  auto it = t1.insert(0).first;
216  EXPECT_EQ(0, it->num_moves());
217  t1.rehash(2 * t1.capacity());
218  EXPECT_EQ(2, a1.num_allocs());
219  it = t1.find(0);
220  EXPECT_EQ(1, it->num_moves());
221  EXPECT_EQ(0, it->num_copies());
222 }
223 
224 TEST_F(PropagateOnAll, CopyConstructor) {
225  auto it = t1.insert(0).first;
226  Table u(t1);
227  EXPECT_EQ(2, a1.num_allocs());
228  EXPECT_EQ(0, it->num_moves());
229  EXPECT_EQ(1, it->num_copies());
230 }
231 
232 TEST_F(NoPropagateOnCopy, CopyConstructor) {
233  auto it = t1.insert(0).first;
234  Table u(t1);
235  EXPECT_EQ(1, a1.num_allocs());
236  EXPECT_EQ(1, u.get_allocator().num_allocs());
237  EXPECT_EQ(0, it->num_moves());
238  EXPECT_EQ(1, it->num_copies());
239 }
240 
241 TEST_F(PropagateOnAll, CopyConstructorWithSameAlloc) {
242  auto it = t1.insert(0).first;
243  Table u(t1, a1);
244  EXPECT_EQ(2, a1.num_allocs());
245  EXPECT_EQ(0, it->num_moves());
246  EXPECT_EQ(1, it->num_copies());
247 }
248 
249 TEST_F(NoPropagateOnCopy, CopyConstructorWithSameAlloc) {
250  auto it = t1.insert(0).first;
251  Table u(t1, a1);
252  EXPECT_EQ(2, a1.num_allocs());
253  EXPECT_EQ(0, it->num_moves());
254  EXPECT_EQ(1, it->num_copies());
255 }
256 
257 TEST_F(PropagateOnAll, CopyConstructorWithDifferentAlloc) {
258  auto it = t1.insert(0).first;
259  Table u(t1, a2);
260  EXPECT_EQ(a2, u.get_allocator());
261  EXPECT_EQ(1, a1.num_allocs());
262  EXPECT_EQ(1, a2.num_allocs());
263  EXPECT_EQ(0, it->num_moves());
264  EXPECT_EQ(1, it->num_copies());
265 }
266 
267 TEST_F(NoPropagateOnCopy, CopyConstructorWithDifferentAlloc) {
268  auto it = t1.insert(0).first;
269  Table u(t1, a2);
270  EXPECT_EQ(a2, u.get_allocator());
271  EXPECT_EQ(1, a1.num_allocs());
272  EXPECT_EQ(1, a2.num_allocs());
273  EXPECT_EQ(0, it->num_moves());
274  EXPECT_EQ(1, it->num_copies());
275 }
276 
277 TEST_F(PropagateOnAll, MoveConstructor) {
278  auto it = t1.insert(0).first;
279  Table u(std::move(t1));
280  EXPECT_EQ(1, a1.num_allocs());
281  EXPECT_EQ(0, it->num_moves());
282  EXPECT_EQ(0, it->num_copies());
283 }
284 
285 TEST_F(NoPropagateOnMove, MoveConstructor) {
286  auto it = t1.insert(0).first;
287  Table u(std::move(t1));
288  EXPECT_EQ(1, a1.num_allocs());
289  EXPECT_EQ(0, it->num_moves());
290  EXPECT_EQ(0, it->num_copies());
291 }
292 
293 TEST_F(PropagateOnAll, MoveConstructorWithSameAlloc) {
294  auto it = t1.insert(0).first;
295  Table u(std::move(t1), a1);
296  EXPECT_EQ(1, a1.num_allocs());
297  EXPECT_EQ(0, it->num_moves());
298  EXPECT_EQ(0, it->num_copies());
299 }
300 
301 TEST_F(NoPropagateOnMove, MoveConstructorWithSameAlloc) {
302  auto it = t1.insert(0).first;
303  Table u(std::move(t1), a1);
304  EXPECT_EQ(1, a1.num_allocs());
305  EXPECT_EQ(0, it->num_moves());
306  EXPECT_EQ(0, it->num_copies());
307 }
308 
309 TEST_F(PropagateOnAll, MoveConstructorWithDifferentAlloc) {
310  auto it = t1.insert(0).first;
311  Table u(std::move(t1), a2);
312  it = u.find(0);
313  EXPECT_EQ(a2, u.get_allocator());
314  EXPECT_EQ(1, a1.num_allocs());
315  EXPECT_EQ(1, a2.num_allocs());
316  EXPECT_EQ(1, it->num_moves());
317  EXPECT_EQ(0, it->num_copies());
318 }
319 
320 TEST_F(NoPropagateOnMove, MoveConstructorWithDifferentAlloc) {
321  auto it = t1.insert(0).first;
322  Table u(std::move(t1), a2);
323  it = u.find(0);
324  EXPECT_EQ(a2, u.get_allocator());
325  EXPECT_EQ(1, a1.num_allocs());
326  EXPECT_EQ(1, a2.num_allocs());
327  EXPECT_EQ(1, it->num_moves());
328  EXPECT_EQ(0, it->num_copies());
329 }
330 
331 TEST_F(PropagateOnAll, CopyAssignmentWithSameAlloc) {
332  auto it = t1.insert(0).first;
333  Table u(0, a1);
334  u = t1;
335  EXPECT_EQ(2, a1.num_allocs());
336  EXPECT_EQ(0, it->num_moves());
337  EXPECT_EQ(1, it->num_copies());
338 }
339 
340 TEST_F(NoPropagateOnCopy, CopyAssignmentWithSameAlloc) {
341  auto it = t1.insert(0).first;
342  Table u(0, a1);
343  u = t1;
344  EXPECT_EQ(2, a1.num_allocs());
345  EXPECT_EQ(0, it->num_moves());
346  EXPECT_EQ(1, it->num_copies());
347 }
348 
349 TEST_F(PropagateOnAll, CopyAssignmentWithDifferentAlloc) {
350  auto it = t1.insert(0).first;
351  Table u(0, a2);
352  u = t1;
353  EXPECT_EQ(a1, u.get_allocator());
354  EXPECT_EQ(2, a1.num_allocs());
355  EXPECT_EQ(0, a2.num_allocs());
356  EXPECT_EQ(0, it->num_moves());
357  EXPECT_EQ(1, it->num_copies());
358 }
359 
360 TEST_F(NoPropagateOnCopy, CopyAssignmentWithDifferentAlloc) {
361  auto it = t1.insert(0).first;
362  Table u(0, a2);
363  u = t1;
364  EXPECT_EQ(a2, u.get_allocator());
365  EXPECT_EQ(1, a1.num_allocs());
366  EXPECT_EQ(1, a2.num_allocs());
367  EXPECT_EQ(0, it->num_moves());
368  EXPECT_EQ(1, it->num_copies());
369 }
370 
371 TEST_F(PropagateOnAll, MoveAssignmentWithSameAlloc) {
372  auto it = t1.insert(0).first;
373  Table u(0, a1);
374  u = std::move(t1);
375  EXPECT_EQ(a1, u.get_allocator());
376  EXPECT_EQ(1, a1.num_allocs());
377  EXPECT_EQ(0, it->num_moves());
378  EXPECT_EQ(0, it->num_copies());
379 }
380 
381 TEST_F(NoPropagateOnMove, MoveAssignmentWithSameAlloc) {
382  auto it = t1.insert(0).first;
383  Table u(0, a1);
384  u = std::move(t1);
385  EXPECT_EQ(a1, u.get_allocator());
386  EXPECT_EQ(1, a1.num_allocs());
387  EXPECT_EQ(0, it->num_moves());
388  EXPECT_EQ(0, it->num_copies());
389 }
390 
391 TEST_F(PropagateOnAll, MoveAssignmentWithDifferentAlloc) {
392  auto it = t1.insert(0).first;
393  Table u(0, a2);
394  u = std::move(t1);
395  EXPECT_EQ(a1, u.get_allocator());
396  EXPECT_EQ(1, a1.num_allocs());
397  EXPECT_EQ(0, a2.num_allocs());
398  EXPECT_EQ(0, it->num_moves());
399  EXPECT_EQ(0, it->num_copies());
400 }
401 
402 TEST_F(NoPropagateOnMove, MoveAssignmentWithDifferentAlloc) {
403  auto it = t1.insert(0).first;
404  Table u(0, a2);
405  u = std::move(t1);
406  it = u.find(0);
407  EXPECT_EQ(a2, u.get_allocator());
408  EXPECT_EQ(1, a1.num_allocs());
409  EXPECT_EQ(1, a2.num_allocs());
410  EXPECT_EQ(1, it->num_moves());
411  EXPECT_EQ(0, it->num_copies());
412 }
413 
414 TEST_F(PropagateOnAll, Swap) {
415  auto it = t1.insert(0).first;
416  Table u(0, a2);
417  u.swap(t1);
418  EXPECT_EQ(a1, u.get_allocator());
419  EXPECT_EQ(a2, t1.get_allocator());
420  EXPECT_EQ(1, a1.num_allocs());
421  EXPECT_EQ(0, a2.num_allocs());
422  EXPECT_EQ(0, it->num_moves());
423  EXPECT_EQ(0, it->num_copies());
424 }
425 
426 } // namespace
427 } // namespace container_internal
428 } // namespace absl
v
int v
Definition: variant_test.cc:81
element
static std::function< Slot &(Slot *)> element
Definition: hash_policy_traits_test.cc:43
absl::operator<<
std::ostream & operator<<(std::ostream &os, absl::LogSeverity s)
Definition: log_severity.cc:21
owned
std::set< void * > owned
Definition: raw_hash_set_allocator_test.cc:34
id_
size_t id_
Definition: raw_hash_set_allocator_test.cc:119
absl::compare_internal::value_type
int8_t value_type
Definition: compare.h:44
absl
Definition: algorithm.h:29
a1
Alloc a1
Definition: raw_hash_set_allocator_test.cc:183
raw_hash_set.h
destroy
static std::function< void(void *, Slot *)> destroy
Definition: hash_policy_traits_test.cc:41
absl::operator==
bool operator==(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
Definition: inlined_vector.h:1226
absl::swap_internal::Swap
void Swap(T &lhs, T &rhs) noexcept(IsNothrowSwappable< T >::value)
Definition: type_traits.h:673
ptr
char * ptr
Definition: low_level_alloc_test.cc:38
absl::operator!=
bool operator!=(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
Definition: inlined_vector.h:1239
absl::synchronization_internal::TEST_F
TEST_F(GraphCyclesTest, NoCycle)
Definition: graphcycles_test.cc:405
absl::swap
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
Definition: inlined_vector.h:1217
transfer
static std::function< void(void *, Slot *, Slot *)> transfer
Definition: hash_policy_traits_test.cc:57
construct
static std::function< void(void *, Slot *, Slot)> construct
Definition: hash_policy_traits_test.cc:40
absl::apply
auto apply(Functor &&functor, Tuple &&t) -> decltype(utility_internal::apply_helper(absl::forward< Functor >(functor), absl::forward< Tuple >(t), absl::make_index_sequence< std::tuple_size< typename std::remove_reference< Tuple >::type >::value >
Definition: utility.h:287
o
UnboundConversion o
Definition: parser_test.cc:86
a2
Alloc a2
Definition: raw_hash_set_allocator_test.cc:185
t1
Table t1
Definition: raw_hash_set_allocator_test.cc:184
num_allocs
size_t num_allocs
Definition: raw_hash_set_allocator_test.cc:33
state_
std::shared_ptr< AllocState > state_
Definition: raw_hash_set_allocator_test.cc:121
b
uint64_t b
Definition: layout_test.cc:50
alloc
std::allocator< int > alloc
Definition: hash_policy_traits_test.cc:86
absl::move
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
a
int a
Definition: hash_policy_traits_test.cc:87
n
int n
Definition: node_hash_policy_test.cc:48
absl::container_internal::@120::AllocSpec
AllocSpec
Definition: raw_hash_set_allocator_test.cc:26

abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:57