layout.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 // MOTIVATION AND TUTORIAL
16 //
17 // If you want to put in a single heap allocation N doubles followed by M ints,
18 // it's easy if N and M are known at compile time.
19 //
20 // struct S {
21 // double a[N];
22 // int b[M];
23 // };
24 //
25 // S* p = new S;
26 //
27 // But what if N and M are known only in run time? Class template Layout to the
28 // rescue! It's a portable generalization of the technique known as struct hack.
29 //
30 // // This object will tell us everything we need to know about the memory
31 // // layout of double[N] followed by int[M]. It's structurally identical to
32 // // size_t[2] that stores N and M. It's very cheap to create.
33 // const Layout<double, int> layout(N, M);
34 //
35 // // Allocate enough memory for both arrays. `AllocSize()` tells us how much
36 // // memory is needed. We are free to use any allocation function we want as
37 // // long as it returns aligned memory.
38 // std::unique_ptr<unsigned char[]> p(new unsigned char[layout.AllocSize()]);
39 //
40 // // Obtain the pointer to the array of doubles.
41 // // Equivalent to `reinterpret_cast<double*>(p.get())`.
42 // //
43 // // We could have written layout.Pointer<0>(p) instead. If all the types are
44 // // unique you can use either form, but if some types are repeated you must
45 // // use the index form.
46 // double* a = layout.Pointer<double>(p.get());
47 //
48 // // Obtain the pointer to the array of ints.
49 // // Equivalent to `reinterpret_cast<int*>(p.get() + N * 8)`.
50 // int* b = layout.Pointer<int>(p);
51 //
52 // If we are unable to specify sizes of all fields, we can pass as many sizes as
53 // we can to `Partial()`. In return, it'll allow us to access the fields whose
54 // locations and sizes can be computed from the provided information.
55 // `Partial()` comes in handy when the array sizes are embedded into the
56 // allocation.
57 //
58 // // size_t[1] containing N, size_t[1] containing M, double[N], int[M].
59 // using L = Layout<size_t, size_t, double, int>;
60 //
61 // unsigned char* Allocate(size_t n, size_t m) {
62 // const L layout(1, 1, n, m);
63 // unsigned char* p = new unsigned char[layout.AllocSize()];
64 // *layout.Pointer<0>(p) = n;
65 // *layout.Pointer<1>(p) = m;
66 // return p;
67 // }
68 //
69 // void Use(unsigned char* p) {
70 // // First, extract N and M.
71 // // Specify that the first array has only one element. Using `prefix` we
72 // // can access the first two arrays but not more.
73 // constexpr auto prefix = L::Partial(1);
74 // size_t n = *prefix.Pointer<0>(p);
75 // size_t m = *prefix.Pointer<1>(p);
76 //
77 // // Now we can get pointers to the payload.
78 // const L layout(1, 1, n, m);
79 // double* a = layout.Pointer<double>(p);
80 // int* b = layout.Pointer<int>(p);
81 // }
82 //
83 // The layout we used above combines fixed-size with dynamically-sized fields.
84 // This is quite common. Layout is optimized for this use case and generates
85 // optimal code. All computations that can be performed at compile time are
86 // indeed performed at compile time.
87 //
88 // Efficiency tip: The order of fields matters. In `Layout<T1, ..., TN>` try to
89 // ensure that `alignof(T1) >= ... >= alignof(TN)`. This way you'll have no
90 // padding in between arrays.
91 //
92 // You can manually override the alignment of an array by wrapping the type in
93 // `Aligned<T, N>`. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
94 // and behavior as `Layout<..., T, ...>` except that the first element of the
95 // array of `T` is aligned to `N` (the rest of the elements follow without
96 // padding). `N` cannot be less than `alignof(T)`.
97 //
98 // `AllocSize()` and `Pointer()` are the most basic methods for dealing with
99 // memory layouts. Check out the reference or code below to discover more.
100 //
101 // EXAMPLE
102 //
103 // // Immutable move-only string with sizeof equal to sizeof(void*). The
104 // // string size and the characters are kept in the same heap allocation.
105 // class CompactString {
106 // public:
107 // CompactString(const char* s = "") {
108 // const size_t size = strlen(s);
109 // // size_t[1] followed by char[size + 1].
110 // const L layout(1, size + 1);
111 // p_.reset(new unsigned char[layout.AllocSize()]);
112 // // If running under ASAN, mark the padding bytes, if any, to catch
113 // // memory errors.
114 // layout.PoisonPadding(p_.get());
115 // // Store the size in the allocation.
116 // *layout.Pointer<size_t>(p_.get()) = size;
117 // // Store the characters in the allocation.
118 // memcpy(layout.Pointer<char>(p_.get()), s, size + 1);
119 // }
120 //
121 // size_t size() const {
122 // // Equivalent to reinterpret_cast<size_t&>(*p).
123 // return *L::Partial().Pointer<size_t>(p_.get());
124 // }
125 //
126 // const char* c_str() const {
127 // // Equivalent to reinterpret_cast<char*>(p.get() + sizeof(size_t)).
128 // // The argument in Partial(1) specifies that we have size_t[1] in front
129 // // of the characters.
130 // return L::Partial(1).Pointer<char>(p_.get());
131 // }
132 //
133 // private:
134 // // Our heap allocation contains a size_t followed by an array of chars.
135 // using L = Layout<size_t, char>;
136 // std::unique_ptr<unsigned char[]> p_;
137 // };
138 //
139 // int main() {
140 // CompactString s = "hello";
141 // assert(s.size() == 5);
142 // assert(strcmp(s.c_str(), "hello") == 0);
143 // }
144 //
145 // DOCUMENTATION
146 //
147 // The interface exported by this file consists of:
148 // - class `Layout<>` and its public members.
149 // - The public members of class `internal_layout::LayoutImpl<>`. That class
150 // isn't intended to be used directly, and its name and template parameter
151 // list are internal implementation details, but the class itself provides
152 // most of the functionality in this file. See comments on its members for
153 // detailed documentation.
154 //
155 // `Layout<T1,... Tn>::Partial(count1,..., countm)` (where `m` <= `n`) returns a
156 // `LayoutImpl<>` object. `Layout<T1,..., Tn> layout(count1,..., countn)`
157 // creates a `Layout` object, which exposes the same functionality by inheriting
158 // from `LayoutImpl<>`.
159 
160 #ifndef ABSL_CONTAINER_INTERNAL_LAYOUT_H_
161 #define ABSL_CONTAINER_INTERNAL_LAYOUT_H_
162 
163 #include <assert.h>
164 #include <stddef.h>
165 #include <stdint.h>
166 #include <ostream>
167 #include <string>
168 #include <tuple>
169 #include <type_traits>
170 #include <typeinfo>
171 #include <utility>
172 
173 #ifdef ADDRESS_SANITIZER
174 #include <sanitizer/asan_interface.h>
175 #endif
176 
177 #include "absl/meta/type_traits.h"
178 #include "absl/strings/str_cat.h"
179 #include "absl/types/span.h"
180 #include "absl/utility/utility.h"
181 
182 #if defined(__GXX_RTTI)
183 #define ABSL_INTERNAL_HAS_CXA_DEMANGLE
184 #endif
185 
186 #ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE
187 #include <cxxabi.h>
188 #endif
189 
190 namespace absl {
191 namespace container_internal {
192 
193 // A type wrapper that instructs `Layout` to use the specific alignment for the
194 // array. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
195 // and behavior as `Layout<..., T, ...>` except that the first element of the
196 // array of `T` is aligned to `N` (the rest of the elements follow without
197 // padding).
198 //
199 // Requires: `N >= alignof(T)` and `N` is a power of 2.
200 template <class T, size_t N>
201 struct Aligned;
202 
203 namespace internal_layout {
204 
205 template <class T>
206 struct NotAligned {};
207 
208 template <class T, size_t N>
209 struct NotAligned<const Aligned<T, N>> {
210  static_assert(sizeof(T) == 0, "Aligned<T, N> cannot be const-qualified");
211 };
212 
213 template <size_t>
214 using IntToSize = size_t;
215 
216 template <class>
217 using TypeToSize = size_t;
218 
219 template <class T>
220 struct Type : NotAligned<T> {
221  using type = T;
222 };
223 
224 template <class T, size_t N>
225 struct Type<Aligned<T, N>> {
226  using type = T;
227 };
228 
229 template <class T>
230 struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {};
231 
232 template <class T, size_t N>
233 struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {};
234 
235 // Note: workaround for https://gcc.gnu.org/PR88115
236 template <class T>
237 struct AlignOf : NotAligned<T> {
238  static constexpr size_t value = alignof(T);
239 };
240 
241 template <class T, size_t N>
242 struct AlignOf<Aligned<T, N>> {
243  static_assert(N % alignof(T) == 0,
244  "Custom alignment can't be lower than the type's alignment");
245  static constexpr size_t value = N;
246 };
247 
248 // Does `Ts...` contain `T`?
249 template <class T, class... Ts>
251 
252 template <class From, class To>
253 using CopyConst =
254  typename std::conditional<std::is_const<From>::value, const To, To>::type;
255 
256 // Note: We're not qualifying this with absl:: because it doesn't compile under
257 // MSVC.
258 template <class T>
260 
261 // This namespace contains no types. It prevents functions defined in it from
262 // being found by ADL.
263 namespace adl_barrier {
264 
265 template <class Needle, class... Ts>
266 constexpr size_t Find(Needle, Needle, Ts...) {
267  static_assert(!Contains<Needle, Ts...>(), "Duplicate element type");
268  return 0;
269 }
270 
271 template <class Needle, class T, class... Ts>
272 constexpr size_t Find(Needle, T, Ts...) {
273  return adl_barrier::Find(Needle(), Ts()...) + 1;
274 }
275 
276 constexpr bool IsPow2(size_t n) { return !(n & (n - 1)); }
277 
278 // Returns `q * m` for the smallest `q` such that `q * m >= n`.
279 // Requires: `m` is a power of two. It's enforced by IsLegalElementType below.
280 constexpr size_t Align(size_t n, size_t m) { return (n + m - 1) & ~(m - 1); }
281 
282 constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; }
283 
284 constexpr size_t Max(size_t a) { return a; }
285 
286 template <class... Ts>
287 constexpr size_t Max(size_t a, size_t b, Ts... rest) {
288  return adl_barrier::Max(b < a ? a : b, rest...);
289 }
290 
291 template <class T>
292 std::string TypeName() {
293  std::string out;
294  int status = 0;
295  char* demangled = nullptr;
296 #ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE
297  demangled = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, &status);
298 #endif
299  if (status == 0 && demangled != nullptr) { // Demangling succeeded.
300  absl::StrAppend(&out, "<", demangled, ">");
301  free(demangled);
302  } else {
303 #if defined(__GXX_RTTI) || defined(_CPPRTTI)
304  absl::StrAppend(&out, "<", typeid(T).name(), ">");
305 #endif
306  }
307  return out;
308 }
309 
310 } // namespace adl_barrier
311 
312 template <bool C>
313 using EnableIf = typename std::enable_if<C, int>::type;
314 
315 // Can `T` be a template argument of `Layout`?
316 template <class T>
317 using IsLegalElementType = std::integral_constant<
319  !std::is_reference<typename Type<T>::type>::value &&
320  !std::is_volatile<typename Type<T>::type>::value &&
322 
323 template <class Elements, class SizeSeq, class OffsetSeq>
325 
326 // Public base class of `Layout` and the result type of `Layout::Partial()`.
327 //
328 // `Elements...` contains all template arguments of `Layout` that created this
329 // instance.
330 //
331 // `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is the number of arguments
332 // passed to `Layout::Partial()` or `Layout::Layout()`.
333 //
334 // `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is
335 // `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we
336 // can compute offsets).
337 template <class... Elements, size_t... SizeSeq, size_t... OffsetSeq>
338 class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>,
339  absl::index_sequence<OffsetSeq...>> {
340  private:
341  static_assert(sizeof...(Elements) > 0, "At least one field is required");
343  "Invalid element type (see IsLegalElementType)");
344 
345  enum {
346  NumTypes = sizeof...(Elements),
347  NumSizes = sizeof...(SizeSeq),
348  NumOffsets = sizeof...(OffsetSeq),
349  };
350 
351  // These are guaranteed by `Layout`.
352  static_assert(NumOffsets == adl_barrier::Min(NumTypes, NumSizes + 1),
353  "Internal error");
354  static_assert(NumTypes > 0, "Internal error");
355 
356  // Returns the index of `T` in `Elements...`. Results in a compilation error
357  // if `Elements...` doesn't contain exactly one instance of `T`.
358  template <class T>
359  static constexpr size_t ElementIndex() {
360  static_assert(Contains<Type<T>, Type<typename Type<Elements>::type>...>(),
361  "Type not found");
362  return adl_barrier::Find(Type<T>(),
363  Type<typename Type<Elements>::type>()...);
364  }
365 
366  template <size_t N>
367  using ElementAlignment =
368  AlignOf<typename std::tuple_element<N, std::tuple<Elements...>>::type>;
369 
370  public:
371  // Element types of all arrays packed in a tuple.
372  using ElementTypes = std::tuple<typename Type<Elements>::type...>;
373 
374  // Element type of the Nth array.
375  template <size_t N>
376  using ElementType = typename std::tuple_element<N, ElementTypes>::type;
377 
378  constexpr explicit LayoutImpl(IntToSize<SizeSeq>... sizes)
379  : size_{sizes...} {}
380 
381  // Alignment of the layout, equal to the strictest alignment of all elements.
382  // All pointers passed to the methods of layout must be aligned to this value.
383  static constexpr size_t Alignment() {
385  }
386 
387  // Offset in bytes of the Nth array.
388  //
389  // // int[3], 4 bytes of padding, double[4].
390  // Layout<int, double> x(3, 4);
391  // assert(x.Offset<0>() == 0); // The ints starts from 0.
392  // assert(x.Offset<1>() == 16); // The doubles starts from 16.
393  //
394  // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
395  template <size_t N, EnableIf<N == 0> = 0>
396  constexpr size_t Offset() const {
397  return 0;
398  }
399 
400  template <size_t N, EnableIf<N != 0> = 0>
401  constexpr size_t Offset() const {
402  static_assert(N < NumOffsets, "Index out of bounds");
403  return adl_barrier::Align(
404  Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1],
406  }
407 
408  // Offset in bytes of the array with the specified element type. There must
409  // be exactly one such array and its zero-based index must be at most
410  // `NumSizes`.
411  //
412  // // int[3], 4 bytes of padding, double[4].
413  // Layout<int, double> x(3, 4);
414  // assert(x.Offset<int>() == 0); // The ints starts from 0.
415  // assert(x.Offset<double>() == 16); // The doubles starts from 16.
416  template <class T>
417  constexpr size_t Offset() const {
418  return Offset<ElementIndex<T>()>();
419  }
420 
421  // Offsets in bytes of all arrays for which the offsets are known.
422  constexpr std::array<size_t, NumOffsets> Offsets() const {
423  return {{Offset<OffsetSeq>()...}};
424  }
425 
426  // The number of elements in the Nth array. This is the Nth argument of
427  // `Layout::Partial()` or `Layout::Layout()` (zero-based).
428  //
429  // // int[3], 4 bytes of padding, double[4].
430  // Layout<int, double> x(3, 4);
431  // assert(x.Size<0>() == 3);
432  // assert(x.Size<1>() == 4);
433  //
434  // Requires: `N < NumSizes`.
435  template <size_t N>
436  constexpr size_t Size() const {
437  static_assert(N < NumSizes, "Index out of bounds");
438  return size_[N];
439  }
440 
441  // The number of elements in the array with the specified element type.
442  // There must be exactly one such array and its zero-based index must be
443  // at most `NumSizes`.
444  //
445  // // int[3], 4 bytes of padding, double[4].
446  // Layout<int, double> x(3, 4);
447  // assert(x.Size<int>() == 3);
448  // assert(x.Size<double>() == 4);
449  template <class T>
450  constexpr size_t Size() const {
451  return Size<ElementIndex<T>()>();
452  }
453 
454  // The number of elements of all arrays for which they are known.
455  constexpr std::array<size_t, NumSizes> Sizes() const {
456  return {{Size<SizeSeq>()...}};
457  }
458 
459  // Pointer to the beginning of the Nth array.
460  //
461  // `Char` must be `[const] [signed|unsigned] char`.
462  //
463  // // int[3], 4 bytes of padding, double[4].
464  // Layout<int, double> x(3, 4);
465  // unsigned char* p = new unsigned char[x.AllocSize()];
466  // int* ints = x.Pointer<0>(p);
467  // double* doubles = x.Pointer<1>(p);
468  //
469  // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
470  // Requires: `p` is aligned to `Alignment()`.
471  template <size_t N, class Char>
473  using C = typename std::remove_const<Char>::type;
474  static_assert(
475  std::is_same<C, char>() || std::is_same<C, unsigned char>() ||
476  std::is_same<C, signed char>(),
477  "The argument must be a pointer to [const] [signed|unsigned] char");
478  constexpr size_t alignment = Alignment();
479  (void)alignment;
480  assert(reinterpret_cast<uintptr_t>(p) % alignment == 0);
481  return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>());
482  }
483 
484  // Pointer to the beginning of the array with the specified element type.
485  // There must be exactly one such array and its zero-based index must be at
486  // most `NumSizes`.
487  //
488  // `Char` must be `[const] [signed|unsigned] char`.
489  //
490  // // int[3], 4 bytes of padding, double[4].
491  // Layout<int, double> x(3, 4);
492  // unsigned char* p = new unsigned char[x.AllocSize()];
493  // int* ints = x.Pointer<int>(p);
494  // double* doubles = x.Pointer<double>(p);
495  //
496  // Requires: `p` is aligned to `Alignment()`.
497  template <class T, class Char>
498  CopyConst<Char, T>* Pointer(Char* p) const {
499  return Pointer<ElementIndex<T>()>(p);
500  }
501 
502  // Pointers to all arrays for which pointers are known.
503  //
504  // `Char` must be `[const] [signed|unsigned] char`.
505  //
506  // // int[3], 4 bytes of padding, double[4].
507  // Layout<int, double> x(3, 4);
508  // unsigned char* p = new unsigned char[x.AllocSize()];
509  //
510  // int* ints;
511  // double* doubles;
512  // std::tie(ints, doubles) = x.Pointers(p);
513  //
514  // Requires: `p` is aligned to `Alignment()`.
515  //
516  // Note: We're not using ElementType alias here because it does not compile
517  // under MSVC.
518  template <class Char>
519  std::tuple<CopyConst<
520  Char, typename std::tuple_element<OffsetSeq, ElementTypes>::type>*...>
521  Pointers(Char* p) const {
522  return std::tuple<CopyConst<Char, ElementType<OffsetSeq>>*...>(
523  Pointer<OffsetSeq>(p)...);
524  }
525 
526  // The Nth array.
527  //
528  // `Char` must be `[const] [signed|unsigned] char`.
529  //
530  // // int[3], 4 bytes of padding, double[4].
531  // Layout<int, double> x(3, 4);
532  // unsigned char* p = new unsigned char[x.AllocSize()];
533  // Span<int> ints = x.Slice<0>(p);
534  // Span<double> doubles = x.Slice<1>(p);
535  //
536  // Requires: `N < NumSizes`.
537  // Requires: `p` is aligned to `Alignment()`.
538  template <size_t N, class Char>
540  return SliceType<CopyConst<Char, ElementType<N>>>(Pointer<N>(p), Size<N>());
541  }
542 
543  // The array with the specified element type. There must be exactly one
544  // such array and its zero-based index must be less than `NumSizes`.
545  //
546  // `Char` must be `[const] [signed|unsigned] char`.
547  //
548  // // int[3], 4 bytes of padding, double[4].
549  // Layout<int, double> x(3, 4);
550  // unsigned char* p = new unsigned char[x.AllocSize()];
551  // Span<int> ints = x.Slice<int>(p);
552  // Span<double> doubles = x.Slice<double>(p);
553  //
554  // Requires: `p` is aligned to `Alignment()`.
555  template <class T, class Char>
557  return Slice<ElementIndex<T>()>(p);
558  }
559 
560  // All arrays with known sizes.
561  //
562  // `Char` must be `[const] [signed|unsigned] char`.
563  //
564  // // int[3], 4 bytes of padding, double[4].
565  // Layout<int, double> x(3, 4);
566  // unsigned char* p = new unsigned char[x.AllocSize()];
567  //
568  // Span<int> ints;
569  // Span<double> doubles;
570  // std::tie(ints, doubles) = x.Slices(p);
571  //
572  // Requires: `p` is aligned to `Alignment()`.
573  //
574  // Note: We're not using ElementType alias here because it does not compile
575  // under MSVC.
576  template <class Char>
577  std::tuple<SliceType<CopyConst<
578  Char, typename std::tuple_element<SizeSeq, ElementTypes>::type>>...>
579  Slices(Char* p) const {
580  // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63875 (fixed
581  // in 6.1).
582  (void)p;
583  return std::tuple<SliceType<CopyConst<Char, ElementType<SizeSeq>>>...>(
584  Slice<SizeSeq>(p)...);
585  }
586 
587  // The size of the allocation that fits all arrays.
588  //
589  // // int[3], 4 bytes of padding, double[4].
590  // Layout<int, double> x(3, 4);
591  // unsigned char* p = new unsigned char[x.AllocSize()]; // 48 bytes
592  //
593  // Requires: `NumSizes == sizeof...(Ts)`.
594  constexpr size_t AllocSize() const {
595  static_assert(NumTypes == NumSizes, "You must specify sizes of all fields");
596  return Offset<NumTypes - 1>() +
597  SizeOf<ElementType<NumTypes - 1>>() * size_[NumTypes - 1];
598  }
599 
600  // If built with --config=asan, poisons padding bytes (if any) in the
601  // allocation. The pointer must point to a memory block at least
602  // `AllocSize()` bytes in length.
603  //
604  // `Char` must be `[const] [signed|unsigned] char`.
605  //
606  // Requires: `p` is aligned to `Alignment()`.
607  template <class Char, size_t N = NumOffsets - 1, EnableIf<N == 0> = 0>
608  void PoisonPadding(const Char* p) const {
609  Pointer<0>(p); // verify the requirements on `Char` and `p`
610  }
611 
612  template <class Char, size_t N = NumOffsets - 1, EnableIf<N != 0> = 0>
613  void PoisonPadding(const Char* p) const {
614  static_assert(N < NumOffsets, "Index out of bounds");
615  (void)p;
616 #ifdef ADDRESS_SANITIZER
617  PoisonPadding<Char, N - 1>(p);
618  // The `if` is an optimization. It doesn't affect the observable behaviour.
620  size_t start =
621  Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1];
622  ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start);
623  }
624 #endif
625  }
626 
627  // Human-readable description of the memory layout. Useful for debugging.
628  // Slow.
629  //
630  // // char[5], 3 bytes of padding, int[3], 4 bytes of padding, followed
631  // // by an unknown number of doubles.
632  // auto x = Layout<char, int, double>::Partial(5, 3);
633  // assert(x.DebugString() ==
634  // "@0<char>(1)[5]; @8<int>(4)[3]; @24<double>(8)");
635  //
636  // Each field is in the following format: @offset<type>(sizeof)[size] (<type>
637  // may be missing depending on the target platform). For example,
638  // @8<int>(4)[3] means that at offset 8 we have an array of ints, where each
639  // int is 4 bytes, and we have 3 of those ints. The size of the last field may
640  // be missing (as in the example above). Only fields with known offsets are
641  // described. Type names may differ across platforms: one compiler might
642  // produce "unsigned*" where another produces "unsigned int *".
643  std::string DebugString() const {
644  const auto offsets = Offsets();
645  const size_t sizes[] = {SizeOf<ElementType<OffsetSeq>>()...};
646  const std::string types[] = {
647  adl_barrier::TypeName<ElementType<OffsetSeq>>()...};
648  std::string res = absl::StrCat("@0", types[0], "(", sizes[0], ")");
649  for (size_t i = 0; i != NumOffsets - 1; ++i) {
650  absl::StrAppend(&res, "[", size_[i], "]; @", offsets[i + 1], types[i + 1],
651  "(", sizes[i + 1], ")");
652  }
653  // NumSizes is a constant that may be zero. Some compilers cannot see that
654  // inside the if statement "size_[NumSizes - 1]" must be valid.
655  int last = static_cast<int>(NumSizes) - 1;
656  if (NumTypes == NumSizes && last >= 0) {
657  absl::StrAppend(&res, "[", size_[last], "]");
658  }
659  return res;
660  }
661 
662  private:
663  // Arguments of `Layout::Partial()` or `Layout::Layout()`.
664  size_t size_[NumSizes > 0 ? NumSizes : 1];
665 };
666 
667 template <size_t NumSizes, class... Ts>
668 using LayoutType = LayoutImpl<
669  std::tuple<Ts...>, absl::make_index_sequence<NumSizes>,
670  absl::make_index_sequence<adl_barrier::Min(sizeof...(Ts), NumSizes + 1)>>;
671 
672 } // namespace internal_layout
673 
674 // Descriptor of arrays of various types and sizes laid out in memory one after
675 // another. See the top of the file for documentation.
676 //
677 // Check out the public API of internal_layout::LayoutImpl above. The type is
678 // internal to the library but its methods are public, and they are inherited
679 // by `Layout`.
680 template <class... Ts>
681 class Layout : public internal_layout::LayoutType<sizeof...(Ts), Ts...> {
682  public:
683  static_assert(sizeof...(Ts) > 0, "At least one field is required");
684  static_assert(
686  "Invalid element type (see IsLegalElementType)");
687 
688  // The result type of `Partial()` with `NumSizes` arguments.
689  template <size_t NumSizes>
690  using PartialType = internal_layout::LayoutType<NumSizes, Ts...>;
691 
692  // `Layout` knows the element types of the arrays we want to lay out in
693  // memory but not the number of elements in each array.
694  // `Partial(size1, ..., sizeN)` allows us to specify the latter. The
695  // resulting immutable object can be used to obtain pointers to the
696  // individual arrays.
697  //
698  // It's allowed to pass fewer array sizes than the number of arrays. E.g.,
699  // if all you need is to the offset of the second array, you only need to
700  // pass one argument -- the number of elements in the first array.
701  //
702  // // int[3] followed by 4 bytes of padding and an unknown number of
703  // // doubles.
704  // auto x = Layout<int, double>::Partial(3);
705  // // doubles start at byte 16.
706  // assert(x.Offset<1>() == 16);
707  //
708  // If you know the number of elements in all arrays, you can still call
709  // `Partial()` but it's more convenient to use the constructor of `Layout`.
710  //
711  // Layout<int, double> x(3, 5);
712  //
713  // Note: The sizes of the arrays must be specified in number of elements,
714  // not in bytes.
715  //
716  // Requires: `sizeof...(Sizes) <= sizeof...(Ts)`.
717  // Requires: all arguments are convertible to `size_t`.
718  template <class... Sizes>
719  static constexpr PartialType<sizeof...(Sizes)> Partial(Sizes&&... sizes) {
720  static_assert(sizeof...(Sizes) <= sizeof...(Ts), "");
721  return PartialType<sizeof...(Sizes)>(absl::forward<Sizes>(sizes)...);
722  }
723 
724  // Creates a layout with the sizes of all arrays specified. If you know
725  // only the sizes of the first N arrays (where N can be zero), you can use
726  // `Partial()` defined above. The constructor is essentially equivalent to
727  // calling `Partial()` and passing in all array sizes; the constructor is
728  // provided as a convenient abbreviation.
729  //
730  // Note: The sizes of the arrays must be specified in number of elements,
731  // not in bytes.
732  constexpr explicit Layout(internal_layout::TypeToSize<Ts>... sizes)
733  : internal_layout::LayoutType<sizeof...(Ts), Ts...>(sizes...) {}
734 };
735 
736 } // namespace container_internal
737 } // namespace absl
738 
739 #endif // ABSL_CONTAINER_INTERNAL_LAYOUT_H_
constexpr size_t Find(Needle, Needle, Ts...)
Definition: layout.h:266
void StrAppend(std::string *dest, const AlphaNum &a)
Definition: str_cat.cc:193
constexpr size_t Min(size_t a, size_t b)
Definition: layout.h:282
std::tuple< CopyConst< Char, typename std::tuple_element< OffsetSeq, ElementTypes >::type > *... > Pointers(Char *p) const
Definition: layout.h:521
std::string StrCat(const AlphaNum &a, const AlphaNum &b)
Definition: str_cat.cc:98
std::integral_constant< bool,!std::is_reference< T >::value &&!std::is_volatile< T >::value &&!std::is_reference< typename Type< T >::type >::value &&!std::is_volatile< typename Type< T >::type >::value &&adl_barrier::IsPow2(AlignOf< T >::value)> IsLegalElementType
Definition: layout.h:321
make_integer_sequence< size_t, N > make_index_sequence
Definition: utility.h:148
Definition: algorithm.h:29
constexpr size_t Align(size_t n, size_t m)
Definition: layout.h:280
size_t value
constexpr Layout(internal_layout::TypeToSize< Ts >...sizes)
Definition: layout.h:732
std::tuple< SliceType< CopyConst< Char, typename std::tuple_element< SizeSeq, ElementTypes >::type > >... > Slices(Char *p) const
Definition: layout.h:579
constexpr size_t Max(size_t a, size_t b, Ts...rest)
Definition: layout.h:287
char name[1]
Definition: mutex.cc:296
constexpr size_t Find(Needle, T, Ts...)
Definition: layout.h:272
static constexpr PartialType< sizeof...(Sizes)> Partial(Sizes &&...sizes)
Definition: layout.h:719
int size_
Definition: arg.cc:107
uint64_t b
Definition: layout_test.cc:50
typename std::enable_if< C, int >::type EnableIf
Definition: layout.h:313
char * out
Definition: mutex.h:1013
typename std::conditional< std::is_const< From >::value, const To, To >::type CopyConst
Definition: layout.h:254
#define C(x)
Definition: city_test.cc:47


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:36