container_memory.h
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 #ifndef ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
16 #define ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
17 
18 #ifdef ADDRESS_SANITIZER
19 #include <sanitizer/asan_interface.h>
20 #endif
21 
22 #ifdef MEMORY_SANITIZER
23 #include <sanitizer/msan_interface.h>
24 #endif
25 
26 #include <cassert>
27 #include <cstddef>
28 #include <memory>
29 #include <tuple>
30 #include <type_traits>
31 #include <utility>
32 
33 #include "absl/memory/memory.h"
34 #include "absl/utility/utility.h"
35 
36 namespace absl {
37 namespace container_internal {
38 
39 // Allocates at least n bytes aligned to the specified alignment.
40 // Alignment must be a power of 2. It must be positive.
41 //
42 // Note that many allocators don't honor alignment requirements above certain
43 // threshold (usually either alignof(std::max_align_t) or alignof(void*)).
44 // Allocate() doesn't apply alignment corrections. If the underlying allocator
45 // returns insufficiently alignment pointer, that's what you are going to get.
46 template <size_t Alignment, class Alloc>
47 void* Allocate(Alloc* alloc, size_t n) {
48  static_assert(Alignment > 0, "");
49  assert(n && "n must be positive");
50  struct alignas(Alignment) M {};
51  using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
52  using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
53  A mem_alloc(*alloc);
54  void* p = AT::allocate(mem_alloc, (n + sizeof(M) - 1) / sizeof(M));
55  assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 &&
56  "allocator does not respect alignment");
57  return p;
58 }
59 
60 // The pointer must have been previously obtained by calling
61 // Allocate<Alignment>(alloc, n).
62 template <size_t Alignment, class Alloc>
63 void Deallocate(Alloc* alloc, void* p, size_t n) {
64  static_assert(Alignment > 0, "");
65  assert(n && "n must be positive");
66  struct alignas(Alignment) M {};
67  using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
68  using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
69  A mem_alloc(*alloc);
70  AT::deallocate(mem_alloc, static_cast<M*>(p),
71  (n + sizeof(M) - 1) / sizeof(M));
72 }
73 
74 namespace memory_internal {
75 
76 // Constructs T into uninitialized storage pointed by `ptr` using the args
77 // specified in the tuple.
78 template <class Alloc, class T, class Tuple, size_t... I>
79 void ConstructFromTupleImpl(Alloc* alloc, T* ptr, Tuple&& t,
82  *alloc, ptr, std::get<I>(std::forward<Tuple>(t))...);
83 }
84 
85 template <class T, class F>
87  template <class... Args>
88  decltype(std::declval<F>()(std::declval<T>())) operator()(
89  Args&&... args) const {
90  return std::forward<F>(f)(T(std::forward<Args>(args)...));
91  }
92  F&& f;
93 };
94 
95 template <class T, class Tuple, size_t... Is, class F>
96 decltype(std::declval<F>()(std::declval<T>())) WithConstructedImpl(
97  Tuple&& t, absl::index_sequence<Is...>, F&& f) {
98  return WithConstructedImplF<T, F>{std::forward<F>(f)}(
99  std::get<Is>(std::forward<Tuple>(t))...);
100 }
101 
102 template <class T, size_t... Is>
104  -> decltype(std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...)) {
105  return std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...);
106 }
107 
108 // Returns a tuple of references to the elements of the input tuple. T must be a
109 // tuple.
110 template <class T>
111 auto TupleRef(T&& t) -> decltype(
112  TupleRefImpl(std::forward<T>(t),
114  std::tuple_size<typename std::decay<T>::type>::value>())) {
115  return TupleRefImpl(
116  std::forward<T>(t),
118  std::tuple_size<typename std::decay<T>::type>::value>());
119 }
120 
121 template <class F, class K, class V>
122 decltype(std::declval<F>()(std::declval<const K&>(), std::piecewise_construct,
123  std::declval<std::tuple<K>>(), std::declval<V>()))
124 DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
125  const auto& key = std::get<0>(p.first);
126  return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
127  std::move(p.second));
128 }
129 
130 } // namespace memory_internal
131 
132 // Constructs T into uninitialized storage pointed by `ptr` using the args
133 // specified in the tuple.
134 template <class Alloc, class T, class Tuple>
135 void ConstructFromTuple(Alloc* alloc, T* ptr, Tuple&& t) {
137  alloc, ptr, std::forward<Tuple>(t),
139  std::tuple_size<typename std::decay<Tuple>::type>::value>());
140 }
141 
142 // Constructs T using the args specified in the tuple and calls F with the
143 // constructed value.
144 template <class T, class Tuple, class F>
145 decltype(std::declval<F>()(std::declval<T>())) WithConstructed(
146  Tuple&& t, F&& f) {
147  return memory_internal::WithConstructedImpl<T>(
148  std::forward<Tuple>(t),
150  std::tuple_size<typename std::decay<Tuple>::type>::value>(),
151  std::forward<F>(f));
152 }
153 
154 // Given arguments of an std::pair's consructor, PairArgs() returns a pair of
155 // tuples with references to the passed arguments. The tuples contain
156 // constructor arguments for the first and the second elements of the pair.
157 //
158 // The following two snippets are equivalent.
159 //
160 // 1. std::pair<F, S> p(args...);
161 //
162 // 2. auto a = PairArgs(args...);
163 // std::pair<F, S> p(std::piecewise_construct,
164 // std::move(p.first), std::move(p.second));
165 inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { return {}; }
166 template <class F, class S>
167 std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
168  return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
169  std::forward_as_tuple(std::forward<S>(s))};
170 }
171 template <class F, class S>
172 std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs(
173  const std::pair<F, S>& p) {
174  return PairArgs(p.first, p.second);
175 }
176 template <class F, class S>
177 std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) {
178  return PairArgs(std::forward<F>(p.first), std::forward<S>(p.second));
179 }
180 template <class F, class S>
181 auto PairArgs(std::piecewise_construct_t, F&& f, S&& s)
182  -> decltype(std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
183  memory_internal::TupleRef(std::forward<S>(s)))) {
184  return std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
185  memory_internal::TupleRef(std::forward<S>(s)));
186 }
187 
188 // A helper function for implementing apply() in map policies.
189 template <class F, class... Args>
190 auto DecomposePair(F&& f, Args&&... args)
192  std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
194  std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
195 }
196 
197 // A helper function for implementing apply() in set policies.
198 template <class F, class Arg>
199 decltype(std::declval<F>()(std::declval<const Arg&>(), std::declval<Arg>()))
200 DecomposeValue(F&& f, Arg&& arg) {
201  const auto& key = arg;
202  return std::forward<F>(f)(key, std::forward<Arg>(arg));
203 }
204 
205 // Helper functions for asan and msan.
206 inline void SanitizerPoisonMemoryRegion(const void* m, size_t s) {
207 #ifdef ADDRESS_SANITIZER
208  ASAN_POISON_MEMORY_REGION(m, s);
209 #endif
210 #ifdef MEMORY_SANITIZER
211  __msan_poison(m, s);
212 #endif
213  (void)m;
214  (void)s;
215 }
216 
217 inline void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) {
218 #ifdef ADDRESS_SANITIZER
219  ASAN_UNPOISON_MEMORY_REGION(m, s);
220 #endif
221 #ifdef MEMORY_SANITIZER
222  __msan_unpoison(m, s);
223 #endif
224  (void)m;
225  (void)s;
226 }
227 
228 template <typename T>
229 inline void SanitizerPoisonObject(const T* object) {
230  SanitizerPoisonMemoryRegion(object, sizeof(T));
231 }
232 
233 template <typename T>
234 inline void SanitizerUnpoisonObject(const T* object) {
235  SanitizerUnpoisonMemoryRegion(object, sizeof(T));
236 }
237 
238 namespace memory_internal {
239 
240 // If Pair is a standard-layout type, OffsetOf<Pair>::kFirst and
241 // OffsetOf<Pair>::kSecond are equivalent to offsetof(Pair, first) and
242 // offsetof(Pair, second) respectively. Otherwise they are -1.
243 //
244 // The purpose of OffsetOf is to avoid calling offsetof() on non-standard-layout
245 // type, which is non-portable.
246 template <class Pair, class = std::true_type>
247 struct OffsetOf {
248  static constexpr size_t kFirst = -1;
249  static constexpr size_t kSecond = -1;
250 };
251 
252 template <class Pair>
253 struct OffsetOf<Pair, typename std::is_standard_layout<Pair>::type> {
254  static constexpr size_t kFirst = offsetof(Pair, first);
255  static constexpr size_t kSecond = offsetof(Pair, second);
256 };
257 
258 template <class K, class V>
260  private:
261  struct Pair {
262  K first;
264  };
265 
266  // Is P layout-compatible with Pair?
267  template <class P>
268  static constexpr bool LayoutCompatible() {
269  return std::is_standard_layout<P>() && sizeof(P) == sizeof(Pair) &&
270  alignof(P) == alignof(Pair) &&
275  }
276 
277  public:
278  // Whether pair<const K, V> and pair<K, V> are layout-compatible. If they are,
279  // then it is safe to store them in a union and read from either.
280  static constexpr bool value = std::is_standard_layout<K>() &&
281  std::is_standard_layout<Pair>() &&
283  LayoutCompatible<std::pair<K, V>>() &&
284  LayoutCompatible<std::pair<const K, V>>();
285 };
286 
287 } // namespace memory_internal
288 
289 // The internal storage type for key-value containers like flat_hash_map.
290 //
291 // It is convenient for the value_type of a flat_hash_map<K, V> to be
292 // pair<const K, V>; the "const K" prevents accidental modification of the key
293 // when dealing with the reference returned from find() and similar methods.
294 // However, this creates other problems; we want to be able to emplace(K, V)
295 // efficiently with move operations, and similarly be able to move a
296 // pair<K, V> in insert().
297 //
298 // The solution is this union, which aliases the const and non-const versions
299 // of the pair. This also allows flat_hash_map<const K, V> to work, even though
300 // that has the same efficiency issues with move in emplace() and insert() -
301 // but people do it anyway.
302 //
303 // If kMutableKeys is false, only the value member can be accessed.
304 //
305 // If kMutableKeys is true, key can be accessed through all slots while value
306 // and mutable_value must be accessed only via INITIALIZED slots. Slots are
307 // created and destroyed via mutable_value so that the key can be moved later.
308 //
309 // Accessing one of the union fields while the other is active is safe as
310 // long as they are layout-compatible, which is guaranteed by the definition of
311 // kMutableKeys. For C++11, the relevant section of the standard is
312 // https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
313 template <class K, class V>
316  ~map_slot_type() = delete;
317  using value_type = std::pair<const K, V>;
318  using mutable_value_type = std::pair<K, V>;
319 
322  K key;
323 };
324 
325 template <class K, class V>
328  using value_type = std::pair<const K, V>;
329  using mutable_value_type = std::pair<K, V>;
330 
331  private:
332  static void emplace(slot_type* slot) {
333  // The construction of union doesn't do anything at runtime but it allows us
334  // to access its members without violating aliasing rules.
335  new (slot) slot_type;
336  }
337  // If pair<const K, V> and pair<K, V> are layout-compatible, we can accept one
338  // or the other via slot_type. We are also free to access the key via
339  // slot_type::key in this case.
341 
342  public:
343  static value_type& element(slot_type* slot) { return slot->value; }
344  static const value_type& element(const slot_type* slot) {
345  return slot->value;
346  }
347 
348  static const K& key(const slot_type* slot) {
349  return kMutableKeys::value ? slot->key : slot->value.first;
350  }
351 
352  template <class Allocator, class... Args>
353  static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
354  emplace(slot);
355  if (kMutableKeys::value) {
357  std::forward<Args>(args)...);
358  } else {
360  std::forward<Args>(args)...);
361  }
362  }
363 
364  // Construct this slot by moving from another slot.
365  template <class Allocator>
366  static void construct(Allocator* alloc, slot_type* slot, slot_type* other) {
367  emplace(slot);
368  if (kMutableKeys::value) {
370  *alloc, &slot->mutable_value, std::move(other->mutable_value));
371  } else {
373  std::move(other->value));
374  }
375  }
376 
377  template <class Allocator>
378  static void destroy(Allocator* alloc, slot_type* slot) {
379  if (kMutableKeys::value) {
381  } else {
383  }
384  }
385 
386  template <class Allocator>
387  static void transfer(Allocator* alloc, slot_type* new_slot,
388  slot_type* old_slot) {
389  emplace(new_slot);
390  if (kMutableKeys::value) {
392  *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value));
393  } else {
395  std::move(old_slot->value));
396  }
397  destroy(alloc, old_slot);
398  }
399 
400  template <class Allocator>
401  static void swap(Allocator* alloc, slot_type* a, slot_type* b) {
402  if (kMutableKeys::value) {
403  using std::swap;
405  } else {
406  value_type tmp = std::move(a->value);
409  std::move(b->value));
412  std::move(tmp));
413  }
414  }
415 
416  template <class Allocator>
417  static void move(Allocator* alloc, slot_type* src, slot_type* dest) {
418  if (kMutableKeys::value) {
419  dest->mutable_value = std::move(src->mutable_value);
420  } else {
423  std::move(src->value));
424  }
425  }
426 
427  template <class Allocator>
428  static void move(Allocator* alloc, slot_type* first, slot_type* last,
429  slot_type* result) {
430  for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
431  move(alloc, src, dest);
432  }
433 };
434 
435 } // namespace container_internal
436 } // namespace absl
437 
438 #endif // ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
void * Allocate(Alloc *alloc, size_t n)
void ConstructFromTuple(Alloc *alloc, T *ptr, Tuple &&t)
static void move(Allocator *alloc, slot_type *src, slot_type *dest)
decltype(std::declval< F >()(std::declval< const Arg & >(), std::declval< Arg >())) DecomposeValue(F &&f, Arg &&arg)
static void destroy(Alloc &a, T *p)
Definition: memory.h:542
void ConstructFromTupleImpl(Alloc *alloc, T *ptr, Tuple &&t, absl::index_sequence< I... >)
static const value_type & element(const slot_type *slot)
make_integer_sequence< size_t, N > make_index_sequence
Definition: utility.h:148
Definition: algorithm.h:29
static std::function< void(void *, Slot *)> destroy
static void construct(Allocator *alloc, slot_type *slot, slot_type *other)
static void destroy(Allocator *alloc, slot_type *slot)
void SanitizerUnpoisonMemoryRegion(const void *m, size_t s)
char * ptr
std::pair< std::tuple<>, std::tuple<> > PairArgs()
size_t value
std::pair< std::string, std::string > pair
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
auto DecomposePair(F &&f, Args &&...args) -> decltype(memory_internal::DecomposePairImpl(std::forward< F >(f), PairArgs(std::forward< Args >(args)...)))
static void construct(Allocator *alloc, slot_type *slot, Args &&...args)
static void move(Allocator *alloc, slot_type *first, slot_type *last, slot_type *result)
void SanitizerPoisonMemoryRegion(const void *m, size_t s)
static const K & key(const slot_type *slot)
void Deallocate(Alloc *alloc, void *p, size_t n)
static value_type & element(slot_type *slot)
void SanitizerPoisonObject(const T *object)
void * arg
Definition: mutex.cc:292
auto TupleRefImpl(T &&t, absl::index_sequence< Is... >) -> decltype(std::forward_as_tuple(std::get< Is >(std::forward< T >(t))...))
static void swap(Allocator *alloc, slot_type *a, slot_type *b)
decltype(std::declval< F >()(std::declval< T >())) WithConstructed(Tuple &&t, F &&f)
auto TupleRef(T &&t) -> decltype(TupleRefImpl(std::forward< T >(t), absl::make_index_sequence< std::tuple_size< typename std::decay< T >::type >::value >()))
void SanitizerUnpoisonObject(const T *object)
uint64_t b
Definition: layout_test.cc:50
std::allocator< int > alloc
static void transfer(Allocator *alloc, slot_type *new_slot, slot_type *old_slot)
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
decltype(std::declval< F >()(std::declval< const K & >(), std::piecewise_construct, std::declval< std::tuple< K >>(), std::declval< V >())) DecomposePairImpl(F &&f, std::pair< std::tuple< K >, V > p)
static void emplace(slot_type *slot)
static void construct(Alloc &a, T *p, Args &&...args)
Definition: memory.h:534
decltype(std::declval< F >()(std::declval< T >())) WithConstructedImpl(Tuple &&t, absl::index_sequence< Is... >, F &&f)


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