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
190namespace absl {
191namespace 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.
200template <class T, size_t N>
201struct Aligned;
202
203namespace internal_layout {
204
205template <class T>
206struct NotAligned {};
207
208template <class T, size_t N>
209struct NotAligned<const Aligned<T, N>> {
210 static_assert(sizeof(T) == 0, "Aligned<T, N> cannot be const-qualified");
211};
212
213template <size_t>
214using IntToSize = size_t;
215
216template <class>
217using TypeToSize = size_t;
218
219template <class T>
220struct Type : NotAligned<T> {
221 using type = T;
222};
223
224template <class T, size_t N>
225struct Type<Aligned<T, N>> {
226 using type = T;
227};
228
229template <class T>
230struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {};
231
232template <class T, size_t N>
233struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {};
234
235// Note: workaround for https://gcc.gnu.org/PR88115
236template <class T>
237struct AlignOf : NotAligned<T> {
238 static constexpr size_t value = alignof(T);
239};
240
241template <class T, size_t N>
242struct 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`?
249template <class T, class... Ts>
250using Contains = absl::disjunction<std::is_same<T, Ts>...>;
251
252template <class From, class To>
253using 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.
258template <class T>
259using SliceType = Span<T>;
260
261// This namespace contains no types. It prevents functions defined in it from
262// being found by ADL.
263namespace adl_barrier {
264
265template <class Needle, class... Ts>
266constexpr size_t Find(Needle, Needle, Ts...) {
267 static_assert(!Contains<Needle, Ts...>(), "Duplicate element type");
268 return 0;
269}
270
271template <class Needle, class T, class... Ts>
272constexpr size_t Find(Needle, T, Ts...) {
273 return adl_barrier::Find(Needle(), Ts()...) + 1;
274}
275
276constexpr 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.
280constexpr size_t Align(size_t n, size_t m) { return (n + m - 1) & ~(m - 1); }
281
282constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; }
283
284constexpr size_t Max(size_t a) { return a; }
285
286template <class... Ts>
287constexpr size_t Max(size_t a, size_t b, Ts... rest) {
288 return adl_barrier::Max(b < a ? a : b, rest...);
289}
290
291template <class T>
292std::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
312template <bool C>
313using EnableIf = typename std::enable_if<C, int>::type;
314
315// Can `T` be a template argument of `Layout`?
316template <class T>
317using IsLegalElementType = std::integral_constant<
318 bool, !std::is_reference<T>::value && !std::is_volatile<T>::value &&
319 !std::is_reference<typename Type<T>::type>::value &&
320 !std::is_volatile<typename Type<T>::type>::value &&
321 adl_barrier::IsPow2(AlignOf<T>::value)>;
322
323template <class Elements, class SizeSeq, class OffsetSeq>
324class LayoutImpl;
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).
337template <class... Elements, size_t... SizeSeq, size_t... OffsetSeq>
338class 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");
342 static_assert(absl::conjunction<IsLegalElementType<Elements>...>::value,
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() {
384 return adl_barrier::Max(AlignOf<Elements>::value...);
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],
405 ElementAlignment<N>::value);
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>
472 CopyConst<Char, ElementType<N>>* Pointer(Char* p) const {
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>
539 SliceType<CopyConst<Char, ElementType<N>>> Slice(Char* p) const {
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>
556 SliceType<CopyConst<Char, T>> Slice(Char* p) const {
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.
619 if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) {
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
667template <size_t NumSizes, class... Ts>
668using 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`.
680template <class... Ts>
681class 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(
685 absl::conjunction<internal_layout::IsLegalElementType<Ts>...>::value,
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_
740