layout.h
Go to the documentation of this file.
00001 // Copyright 2018 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 //
00015 //                           MOTIVATION AND TUTORIAL
00016 //
00017 // If you want to put in a single heap allocation N doubles followed by M ints,
00018 // it's easy if N and M are known at compile time.
00019 //
00020 //   struct S {
00021 //     double a[N];
00022 //     int b[M];
00023 //   };
00024 //
00025 //   S* p = new S;
00026 //
00027 // But what if N and M are known only in run time? Class template Layout to the
00028 // rescue! It's a portable generalization of the technique known as struct hack.
00029 //
00030 //   // This object will tell us everything we need to know about the memory
00031 //   // layout of double[N] followed by int[M]. It's structurally identical to
00032 //   // size_t[2] that stores N and M. It's very cheap to create.
00033 //   const Layout<double, int> layout(N, M);
00034 //
00035 //   // Allocate enough memory for both arrays. `AllocSize()` tells us how much
00036 //   // memory is needed. We are free to use any allocation function we want as
00037 //   // long as it returns aligned memory.
00038 //   std::unique_ptr<unsigned char[]> p(new unsigned char[layout.AllocSize()]);
00039 //
00040 //   // Obtain the pointer to the array of doubles.
00041 //   // Equivalent to `reinterpret_cast<double*>(p.get())`.
00042 //   //
00043 //   // We could have written layout.Pointer<0>(p) instead. If all the types are
00044 //   // unique you can use either form, but if some types are repeated you must
00045 //   // use the index form.
00046 //   double* a = layout.Pointer<double>(p.get());
00047 //
00048 //   // Obtain the pointer to the array of ints.
00049 //   // Equivalent to `reinterpret_cast<int*>(p.get() + N * 8)`.
00050 //   int* b = layout.Pointer<int>(p);
00051 //
00052 // If we are unable to specify sizes of all fields, we can pass as many sizes as
00053 // we can to `Partial()`. In return, it'll allow us to access the fields whose
00054 // locations and sizes can be computed from the provided information.
00055 // `Partial()` comes in handy when the array sizes are embedded into the
00056 // allocation.
00057 //
00058 //   // size_t[1] containing N, size_t[1] containing M, double[N], int[M].
00059 //   using L = Layout<size_t, size_t, double, int>;
00060 //
00061 //   unsigned char* Allocate(size_t n, size_t m) {
00062 //     const L layout(1, 1, n, m);
00063 //     unsigned char* p = new unsigned char[layout.AllocSize()];
00064 //     *layout.Pointer<0>(p) = n;
00065 //     *layout.Pointer<1>(p) = m;
00066 //     return p;
00067 //   }
00068 //
00069 //   void Use(unsigned char* p) {
00070 //     // First, extract N and M.
00071 //     // Specify that the first array has only one element. Using `prefix` we
00072 //     // can access the first two arrays but not more.
00073 //     constexpr auto prefix = L::Partial(1);
00074 //     size_t n = *prefix.Pointer<0>(p);
00075 //     size_t m = *prefix.Pointer<1>(p);
00076 //
00077 //     // Now we can get pointers to the payload.
00078 //     const L layout(1, 1, n, m);
00079 //     double* a = layout.Pointer<double>(p);
00080 //     int* b = layout.Pointer<int>(p);
00081 //   }
00082 //
00083 // The layout we used above combines fixed-size with dynamically-sized fields.
00084 // This is quite common. Layout is optimized for this use case and generates
00085 // optimal code. All computations that can be performed at compile time are
00086 // indeed performed at compile time.
00087 //
00088 // Efficiency tip: The order of fields matters. In `Layout<T1, ..., TN>` try to
00089 // ensure that `alignof(T1) >= ... >= alignof(TN)`. This way you'll have no
00090 // padding in between arrays.
00091 //
00092 // You can manually override the alignment of an array by wrapping the type in
00093 // `Aligned<T, N>`. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
00094 // and behavior as `Layout<..., T, ...>` except that the first element of the
00095 // array of `T` is aligned to `N` (the rest of the elements follow without
00096 // padding). `N` cannot be less than `alignof(T)`.
00097 //
00098 // `AllocSize()` and `Pointer()` are the most basic methods for dealing with
00099 // memory layouts. Check out the reference or code below to discover more.
00100 //
00101 //                            EXAMPLE
00102 //
00103 //   // Immutable move-only string with sizeof equal to sizeof(void*). The
00104 //   // string size and the characters are kept in the same heap allocation.
00105 //   class CompactString {
00106 //    public:
00107 //     CompactString(const char* s = "") {
00108 //       const size_t size = strlen(s);
00109 //       // size_t[1] followed by char[size + 1].
00110 //       const L layout(1, size + 1);
00111 //       p_.reset(new unsigned char[layout.AllocSize()]);
00112 //       // If running under ASAN, mark the padding bytes, if any, to catch
00113 //       // memory errors.
00114 //       layout.PoisonPadding(p_.get());
00115 //       // Store the size in the allocation.
00116 //       *layout.Pointer<size_t>(p_.get()) = size;
00117 //       // Store the characters in the allocation.
00118 //       memcpy(layout.Pointer<char>(p_.get()), s, size + 1);
00119 //     }
00120 //
00121 //     size_t size() const {
00122 //       // Equivalent to reinterpret_cast<size_t&>(*p).
00123 //       return *L::Partial().Pointer<size_t>(p_.get());
00124 //     }
00125 //
00126 //     const char* c_str() const {
00127 //       // Equivalent to reinterpret_cast<char*>(p.get() + sizeof(size_t)).
00128 //       // The argument in Partial(1) specifies that we have size_t[1] in front
00129 //       // of the characters.
00130 //       return L::Partial(1).Pointer<char>(p_.get());
00131 //     }
00132 //
00133 //    private:
00134 //     // Our heap allocation contains a size_t followed by an array of chars.
00135 //     using L = Layout<size_t, char>;
00136 //     std::unique_ptr<unsigned char[]> p_;
00137 //   };
00138 //
00139 //   int main() {
00140 //     CompactString s = "hello";
00141 //     assert(s.size() == 5);
00142 //     assert(strcmp(s.c_str(), "hello") == 0);
00143 //   }
00144 //
00145 //                               DOCUMENTATION
00146 //
00147 // The interface exported by this file consists of:
00148 // - class `Layout<>` and its public members.
00149 // - The public members of class `internal_layout::LayoutImpl<>`. That class
00150 //   isn't intended to be used directly, and its name and template parameter
00151 //   list are internal implementation details, but the class itself provides
00152 //   most of the functionality in this file. See comments on its members for
00153 //   detailed documentation.
00154 //
00155 // `Layout<T1,... Tn>::Partial(count1,..., countm)` (where `m` <= `n`) returns a
00156 // `LayoutImpl<>` object. `Layout<T1,..., Tn> layout(count1,..., countn)`
00157 // creates a `Layout` object, which exposes the same functionality by inheriting
00158 // from `LayoutImpl<>`.
00159 
00160 #ifndef ABSL_CONTAINER_INTERNAL_LAYOUT_H_
00161 #define ABSL_CONTAINER_INTERNAL_LAYOUT_H_
00162 
00163 #include <assert.h>
00164 #include <stddef.h>
00165 #include <stdint.h>
00166 #include <ostream>
00167 #include <string>
00168 #include <tuple>
00169 #include <type_traits>
00170 #include <typeinfo>
00171 #include <utility>
00172 
00173 #ifdef ADDRESS_SANITIZER
00174 #include <sanitizer/asan_interface.h>
00175 #endif
00176 
00177 #include "absl/meta/type_traits.h"
00178 #include "absl/strings/str_cat.h"
00179 #include "absl/types/span.h"
00180 #include "absl/utility/utility.h"
00181 
00182 #if defined(__GXX_RTTI)
00183 #define ABSL_INTERNAL_HAS_CXA_DEMANGLE
00184 #endif
00185 
00186 #ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE
00187 #include <cxxabi.h>
00188 #endif
00189 
00190 namespace absl {
00191 namespace container_internal {
00192 
00193 // A type wrapper that instructs `Layout` to use the specific alignment for the
00194 // array. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
00195 // and behavior as `Layout<..., T, ...>` except that the first element of the
00196 // array of `T` is aligned to `N` (the rest of the elements follow without
00197 // padding).
00198 //
00199 // Requires: `N >= alignof(T)` and `N` is a power of 2.
00200 template <class T, size_t N>
00201 struct Aligned;
00202 
00203 namespace internal_layout {
00204 
00205 template <class T>
00206 struct NotAligned {};
00207 
00208 template <class T, size_t N>
00209 struct NotAligned<const Aligned<T, N>> {
00210   static_assert(sizeof(T) == 0, "Aligned<T, N> cannot be const-qualified");
00211 };
00212 
00213 template <size_t>
00214 using IntToSize = size_t;
00215 
00216 template <class>
00217 using TypeToSize = size_t;
00218 
00219 template <class T>
00220 struct Type : NotAligned<T> {
00221   using type = T;
00222 };
00223 
00224 template <class T, size_t N>
00225 struct Type<Aligned<T, N>> {
00226   using type = T;
00227 };
00228 
00229 template <class T>
00230 struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {};
00231 
00232 template <class T, size_t N>
00233 struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {};
00234 
00235 // Note: workaround for https://gcc.gnu.org/PR88115
00236 template <class T>
00237 struct AlignOf : NotAligned<T> {
00238   static constexpr size_t value = alignof(T);
00239 };
00240 
00241 template <class T, size_t N>
00242 struct AlignOf<Aligned<T, N>> {
00243   static_assert(N % alignof(T) == 0,
00244                 "Custom alignment can't be lower than the type's alignment");
00245   static constexpr size_t value = N;
00246 };
00247 
00248 // Does `Ts...` contain `T`?
00249 template <class T, class... Ts>
00250 using Contains = absl::disjunction<std::is_same<T, Ts>...>;
00251 
00252 template <class From, class To>
00253 using CopyConst =
00254     typename std::conditional<std::is_const<From>::value, const To, To>::type;
00255 
00256 // Note: We're not qualifying this with absl:: because it doesn't compile under
00257 // MSVC.
00258 template <class T>
00259 using SliceType = Span<T>;
00260 
00261 // This namespace contains no types. It prevents functions defined in it from
00262 // being found by ADL.
00263 namespace adl_barrier {
00264 
00265 template <class Needle, class... Ts>
00266 constexpr size_t Find(Needle, Needle, Ts...) {
00267   static_assert(!Contains<Needle, Ts...>(), "Duplicate element type");
00268   return 0;
00269 }
00270 
00271 template <class Needle, class T, class... Ts>
00272 constexpr size_t Find(Needle, T, Ts...) {
00273   return adl_barrier::Find(Needle(), Ts()...) + 1;
00274 }
00275 
00276 constexpr bool IsPow2(size_t n) { return !(n & (n - 1)); }
00277 
00278 // Returns `q * m` for the smallest `q` such that `q * m >= n`.
00279 // Requires: `m` is a power of two. It's enforced by IsLegalElementType below.
00280 constexpr size_t Align(size_t n, size_t m) { return (n + m - 1) & ~(m - 1); }
00281 
00282 constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; }
00283 
00284 constexpr size_t Max(size_t a) { return a; }
00285 
00286 template <class... Ts>
00287 constexpr size_t Max(size_t a, size_t b, Ts... rest) {
00288   return adl_barrier::Max(b < a ? a : b, rest...);
00289 }
00290 
00291 template <class T>
00292 std::string TypeName() {
00293   std::string out;
00294   int status = 0;
00295   char* demangled = nullptr;
00296 #ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE
00297   demangled = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, &status);
00298 #endif
00299   if (status == 0 && demangled != nullptr) {  // Demangling succeeded.
00300     absl::StrAppend(&out, "<", demangled, ">");
00301     free(demangled);
00302   } else {
00303 #if defined(__GXX_RTTI) || defined(_CPPRTTI)
00304     absl::StrAppend(&out, "<", typeid(T).name(), ">");
00305 #endif
00306   }
00307   return out;
00308 }
00309 
00310 }  // namespace adl_barrier
00311 
00312 template <bool C>
00313 using EnableIf = typename std::enable_if<C, int>::type;
00314 
00315 // Can `T` be a template argument of `Layout`?
00316 template <class T>
00317 using IsLegalElementType = std::integral_constant<
00318     bool, !std::is_reference<T>::value && !std::is_volatile<T>::value &&
00319               !std::is_reference<typename Type<T>::type>::value &&
00320               !std::is_volatile<typename Type<T>::type>::value &&
00321               adl_barrier::IsPow2(AlignOf<T>::value)>;
00322 
00323 template <class Elements, class SizeSeq, class OffsetSeq>
00324 class LayoutImpl;
00325 
00326 // Public base class of `Layout` and the result type of `Layout::Partial()`.
00327 //
00328 // `Elements...` contains all template arguments of `Layout` that created this
00329 // instance.
00330 //
00331 // `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is the number of arguments
00332 // passed to `Layout::Partial()` or `Layout::Layout()`.
00333 //
00334 // `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is
00335 // `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we
00336 // can compute offsets).
00337 template <class... Elements, size_t... SizeSeq, size_t... OffsetSeq>
00338 class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>,
00339                  absl::index_sequence<OffsetSeq...>> {
00340  private:
00341   static_assert(sizeof...(Elements) > 0, "At least one field is required");
00342   static_assert(absl::conjunction<IsLegalElementType<Elements>...>::value,
00343                 "Invalid element type (see IsLegalElementType)");
00344 
00345   enum {
00346     NumTypes = sizeof...(Elements),
00347     NumSizes = sizeof...(SizeSeq),
00348     NumOffsets = sizeof...(OffsetSeq),
00349   };
00350 
00351   // These are guaranteed by `Layout`.
00352   static_assert(NumOffsets == adl_barrier::Min(NumTypes, NumSizes + 1),
00353                 "Internal error");
00354   static_assert(NumTypes > 0, "Internal error");
00355 
00356   // Returns the index of `T` in `Elements...`. Results in a compilation error
00357   // if `Elements...` doesn't contain exactly one instance of `T`.
00358   template <class T>
00359   static constexpr size_t ElementIndex() {
00360     static_assert(Contains<Type<T>, Type<typename Type<Elements>::type>...>(),
00361                   "Type not found");
00362     return adl_barrier::Find(Type<T>(),
00363                              Type<typename Type<Elements>::type>()...);
00364   }
00365 
00366   template <size_t N>
00367   using ElementAlignment =
00368       AlignOf<typename std::tuple_element<N, std::tuple<Elements...>>::type>;
00369 
00370  public:
00371   // Element types of all arrays packed in a tuple.
00372   using ElementTypes = std::tuple<typename Type<Elements>::type...>;
00373 
00374   // Element type of the Nth array.
00375   template <size_t N>
00376   using ElementType = typename std::tuple_element<N, ElementTypes>::type;
00377 
00378   constexpr explicit LayoutImpl(IntToSize<SizeSeq>... sizes)
00379       : size_{sizes...} {}
00380 
00381   // Alignment of the layout, equal to the strictest alignment of all elements.
00382   // All pointers passed to the methods of layout must be aligned to this value.
00383   static constexpr size_t Alignment() {
00384     return adl_barrier::Max(AlignOf<Elements>::value...);
00385   }
00386 
00387   // Offset in bytes of the Nth array.
00388   //
00389   //   // int[3], 4 bytes of padding, double[4].
00390   //   Layout<int, double> x(3, 4);
00391   //   assert(x.Offset<0>() == 0);   // The ints starts from 0.
00392   //   assert(x.Offset<1>() == 16);  // The doubles starts from 16.
00393   //
00394   // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
00395   template <size_t N, EnableIf<N == 0> = 0>
00396   constexpr size_t Offset() const {
00397     return 0;
00398   }
00399 
00400   template <size_t N, EnableIf<N != 0> = 0>
00401   constexpr size_t Offset() const {
00402     static_assert(N < NumOffsets, "Index out of bounds");
00403     return adl_barrier::Align(
00404         Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1],
00405         ElementAlignment<N>::value);
00406   }
00407 
00408   // Offset in bytes of the array with the specified element type. There must
00409   // be exactly one such array and its zero-based index must be at most
00410   // `NumSizes`.
00411   //
00412   //   // int[3], 4 bytes of padding, double[4].
00413   //   Layout<int, double> x(3, 4);
00414   //   assert(x.Offset<int>() == 0);      // The ints starts from 0.
00415   //   assert(x.Offset<double>() == 16);  // The doubles starts from 16.
00416   template <class T>
00417   constexpr size_t Offset() const {
00418     return Offset<ElementIndex<T>()>();
00419   }
00420 
00421   // Offsets in bytes of all arrays for which the offsets are known.
00422   constexpr std::array<size_t, NumOffsets> Offsets() const {
00423     return {{Offset<OffsetSeq>()...}};
00424   }
00425 
00426   // The number of elements in the Nth array. This is the Nth argument of
00427   // `Layout::Partial()` or `Layout::Layout()` (zero-based).
00428   //
00429   //   // int[3], 4 bytes of padding, double[4].
00430   //   Layout<int, double> x(3, 4);
00431   //   assert(x.Size<0>() == 3);
00432   //   assert(x.Size<1>() == 4);
00433   //
00434   // Requires: `N < NumSizes`.
00435   template <size_t N>
00436   constexpr size_t Size() const {
00437     static_assert(N < NumSizes, "Index out of bounds");
00438     return size_[N];
00439   }
00440 
00441   // The number of elements in the array with the specified element type.
00442   // There must be exactly one such array and its zero-based index must be
00443   // at most `NumSizes`.
00444   //
00445   //   // int[3], 4 bytes of padding, double[4].
00446   //   Layout<int, double> x(3, 4);
00447   //   assert(x.Size<int>() == 3);
00448   //   assert(x.Size<double>() == 4);
00449   template <class T>
00450   constexpr size_t Size() const {
00451     return Size<ElementIndex<T>()>();
00452   }
00453 
00454   // The number of elements of all arrays for which they are known.
00455   constexpr std::array<size_t, NumSizes> Sizes() const {
00456     return {{Size<SizeSeq>()...}};
00457   }
00458 
00459   // Pointer to the beginning of the Nth array.
00460   //
00461   // `Char` must be `[const] [signed|unsigned] char`.
00462   //
00463   //   // int[3], 4 bytes of padding, double[4].
00464   //   Layout<int, double> x(3, 4);
00465   //   unsigned char* p = new unsigned char[x.AllocSize()];
00466   //   int* ints = x.Pointer<0>(p);
00467   //   double* doubles = x.Pointer<1>(p);
00468   //
00469   // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
00470   // Requires: `p` is aligned to `Alignment()`.
00471   template <size_t N, class Char>
00472   CopyConst<Char, ElementType<N>>* Pointer(Char* p) const {
00473     using C = typename std::remove_const<Char>::type;
00474     static_assert(
00475         std::is_same<C, char>() || std::is_same<C, unsigned char>() ||
00476             std::is_same<C, signed char>(),
00477         "The argument must be a pointer to [const] [signed|unsigned] char");
00478     constexpr size_t alignment = Alignment();
00479     (void)alignment;
00480     assert(reinterpret_cast<uintptr_t>(p) % alignment == 0);
00481     return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>());
00482   }
00483 
00484   // Pointer to the beginning of the array with the specified element type.
00485   // There must be exactly one such array and its zero-based index must be at
00486   // most `NumSizes`.
00487   //
00488   // `Char` must be `[const] [signed|unsigned] char`.
00489   //
00490   //   // int[3], 4 bytes of padding, double[4].
00491   //   Layout<int, double> x(3, 4);
00492   //   unsigned char* p = new unsigned char[x.AllocSize()];
00493   //   int* ints = x.Pointer<int>(p);
00494   //   double* doubles = x.Pointer<double>(p);
00495   //
00496   // Requires: `p` is aligned to `Alignment()`.
00497   template <class T, class Char>
00498   CopyConst<Char, T>* Pointer(Char* p) const {
00499     return Pointer<ElementIndex<T>()>(p);
00500   }
00501 
00502   // Pointers to all arrays for which pointers are known.
00503   //
00504   // `Char` must be `[const] [signed|unsigned] char`.
00505   //
00506   //   // int[3], 4 bytes of padding, double[4].
00507   //   Layout<int, double> x(3, 4);
00508   //   unsigned char* p = new unsigned char[x.AllocSize()];
00509   //
00510   //   int* ints;
00511   //   double* doubles;
00512   //   std::tie(ints, doubles) = x.Pointers(p);
00513   //
00514   // Requires: `p` is aligned to `Alignment()`.
00515   //
00516   // Note: We're not using ElementType alias here because it does not compile
00517   // under MSVC.
00518   template <class Char>
00519   std::tuple<CopyConst<
00520       Char, typename std::tuple_element<OffsetSeq, ElementTypes>::type>*...>
00521   Pointers(Char* p) const {
00522     return std::tuple<CopyConst<Char, ElementType<OffsetSeq>>*...>(
00523         Pointer<OffsetSeq>(p)...);
00524   }
00525 
00526   // The Nth array.
00527   //
00528   // `Char` must be `[const] [signed|unsigned] char`.
00529   //
00530   //   // int[3], 4 bytes of padding, double[4].
00531   //   Layout<int, double> x(3, 4);
00532   //   unsigned char* p = new unsigned char[x.AllocSize()];
00533   //   Span<int> ints = x.Slice<0>(p);
00534   //   Span<double> doubles = x.Slice<1>(p);
00535   //
00536   // Requires: `N < NumSizes`.
00537   // Requires: `p` is aligned to `Alignment()`.
00538   template <size_t N, class Char>
00539   SliceType<CopyConst<Char, ElementType<N>>> Slice(Char* p) const {
00540     return SliceType<CopyConst<Char, ElementType<N>>>(Pointer<N>(p), Size<N>());
00541   }
00542 
00543   // The array with the specified element type. There must be exactly one
00544   // such array and its zero-based index must be less than `NumSizes`.
00545   //
00546   // `Char` must be `[const] [signed|unsigned] char`.
00547   //
00548   //   // int[3], 4 bytes of padding, double[4].
00549   //   Layout<int, double> x(3, 4);
00550   //   unsigned char* p = new unsigned char[x.AllocSize()];
00551   //   Span<int> ints = x.Slice<int>(p);
00552   //   Span<double> doubles = x.Slice<double>(p);
00553   //
00554   // Requires: `p` is aligned to `Alignment()`.
00555   template <class T, class Char>
00556   SliceType<CopyConst<Char, T>> Slice(Char* p) const {
00557     return Slice<ElementIndex<T>()>(p);
00558   }
00559 
00560   // All arrays with known sizes.
00561   //
00562   // `Char` must be `[const] [signed|unsigned] char`.
00563   //
00564   //   // int[3], 4 bytes of padding, double[4].
00565   //   Layout<int, double> x(3, 4);
00566   //   unsigned char* p = new unsigned char[x.AllocSize()];
00567   //
00568   //   Span<int> ints;
00569   //   Span<double> doubles;
00570   //   std::tie(ints, doubles) = x.Slices(p);
00571   //
00572   // Requires: `p` is aligned to `Alignment()`.
00573   //
00574   // Note: We're not using ElementType alias here because it does not compile
00575   // under MSVC.
00576   template <class Char>
00577   std::tuple<SliceType<CopyConst<
00578       Char, typename std::tuple_element<SizeSeq, ElementTypes>::type>>...>
00579   Slices(Char* p) const {
00580     // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63875 (fixed
00581     // in 6.1).
00582     (void)p;
00583     return std::tuple<SliceType<CopyConst<Char, ElementType<SizeSeq>>>...>(
00584         Slice<SizeSeq>(p)...);
00585   }
00586 
00587   // The size of the allocation that fits all arrays.
00588   //
00589   //   // int[3], 4 bytes of padding, double[4].
00590   //   Layout<int, double> x(3, 4);
00591   //   unsigned char* p = new unsigned char[x.AllocSize()];  // 48 bytes
00592   //
00593   // Requires: `NumSizes == sizeof...(Ts)`.
00594   constexpr size_t AllocSize() const {
00595     static_assert(NumTypes == NumSizes, "You must specify sizes of all fields");
00596     return Offset<NumTypes - 1>() +
00597            SizeOf<ElementType<NumTypes - 1>>() * size_[NumTypes - 1];
00598   }
00599 
00600   // If built with --config=asan, poisons padding bytes (if any) in the
00601   // allocation. The pointer must point to a memory block at least
00602   // `AllocSize()` bytes in length.
00603   //
00604   // `Char` must be `[const] [signed|unsigned] char`.
00605   //
00606   // Requires: `p` is aligned to `Alignment()`.
00607   template <class Char, size_t N = NumOffsets - 1, EnableIf<N == 0> = 0>
00608   void PoisonPadding(const Char* p) const {
00609     Pointer<0>(p);  // verify the requirements on `Char` and `p`
00610   }
00611 
00612   template <class Char, size_t N = NumOffsets - 1, EnableIf<N != 0> = 0>
00613   void PoisonPadding(const Char* p) const {
00614     static_assert(N < NumOffsets, "Index out of bounds");
00615     (void)p;
00616 #ifdef ADDRESS_SANITIZER
00617     PoisonPadding<Char, N - 1>(p);
00618     // The `if` is an optimization. It doesn't affect the observable behaviour.
00619     if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) {
00620       size_t start =
00621           Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1];
00622       ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start);
00623     }
00624 #endif
00625   }
00626 
00627   // Human-readable description of the memory layout. Useful for debugging.
00628   // Slow.
00629   //
00630   //   // char[5], 3 bytes of padding, int[3], 4 bytes of padding, followed
00631   //   // by an unknown number of doubles.
00632   //   auto x = Layout<char, int, double>::Partial(5, 3);
00633   //   assert(x.DebugString() ==
00634   //          "@0<char>(1)[5]; @8<int>(4)[3]; @24<double>(8)");
00635   //
00636   // Each field is in the following format: @offset<type>(sizeof)[size] (<type>
00637   // may be missing depending on the target platform). For example,
00638   // @8<int>(4)[3] means that at offset 8 we have an array of ints, where each
00639   // int is 4 bytes, and we have 3 of those ints. The size of the last field may
00640   // be missing (as in the example above). Only fields with known offsets are
00641   // described. Type names may differ across platforms: one compiler might
00642   // produce "unsigned*" where another produces "unsigned int *".
00643   std::string DebugString() const {
00644     const auto offsets = Offsets();
00645     const size_t sizes[] = {SizeOf<ElementType<OffsetSeq>>()...};
00646     const std::string types[] = {
00647         adl_barrier::TypeName<ElementType<OffsetSeq>>()...};
00648     std::string res = absl::StrCat("@0", types[0], "(", sizes[0], ")");
00649     for (size_t i = 0; i != NumOffsets - 1; ++i) {
00650       absl::StrAppend(&res, "[", size_[i], "]; @", offsets[i + 1], types[i + 1],
00651                       "(", sizes[i + 1], ")");
00652     }
00653     // NumSizes is a constant that may be zero. Some compilers cannot see that
00654     // inside the if statement "size_[NumSizes - 1]" must be valid.
00655     int last = static_cast<int>(NumSizes) - 1;
00656     if (NumTypes == NumSizes && last >= 0) {
00657       absl::StrAppend(&res, "[", size_[last], "]");
00658     }
00659     return res;
00660   }
00661 
00662  private:
00663   // Arguments of `Layout::Partial()` or `Layout::Layout()`.
00664   size_t size_[NumSizes > 0 ? NumSizes : 1];
00665 };
00666 
00667 template <size_t NumSizes, class... Ts>
00668 using LayoutType = LayoutImpl<
00669     std::tuple<Ts...>, absl::make_index_sequence<NumSizes>,
00670     absl::make_index_sequence<adl_barrier::Min(sizeof...(Ts), NumSizes + 1)>>;
00671 
00672 }  // namespace internal_layout
00673 
00674 // Descriptor of arrays of various types and sizes laid out in memory one after
00675 // another. See the top of the file for documentation.
00676 //
00677 // Check out the public API of internal_layout::LayoutImpl above. The type is
00678 // internal to the library but its methods are public, and they are inherited
00679 // by `Layout`.
00680 template <class... Ts>
00681 class Layout : public internal_layout::LayoutType<sizeof...(Ts), Ts...> {
00682  public:
00683   static_assert(sizeof...(Ts) > 0, "At least one field is required");
00684   static_assert(
00685       absl::conjunction<internal_layout::IsLegalElementType<Ts>...>::value,
00686       "Invalid element type (see IsLegalElementType)");
00687 
00688   // The result type of `Partial()` with `NumSizes` arguments.
00689   template <size_t NumSizes>
00690   using PartialType = internal_layout::LayoutType<NumSizes, Ts...>;
00691 
00692   // `Layout` knows the element types of the arrays we want to lay out in
00693   // memory but not the number of elements in each array.
00694   // `Partial(size1, ..., sizeN)` allows us to specify the latter. The
00695   // resulting immutable object can be used to obtain pointers to the
00696   // individual arrays.
00697   //
00698   // It's allowed to pass fewer array sizes than the number of arrays. E.g.,
00699   // if all you need is to the offset of the second array, you only need to
00700   // pass one argument -- the number of elements in the first array.
00701   //
00702   //   // int[3] followed by 4 bytes of padding and an unknown number of
00703   //   // doubles.
00704   //   auto x = Layout<int, double>::Partial(3);
00705   //   // doubles start at byte 16.
00706   //   assert(x.Offset<1>() == 16);
00707   //
00708   // If you know the number of elements in all arrays, you can still call
00709   // `Partial()` but it's more convenient to use the constructor of `Layout`.
00710   //
00711   //   Layout<int, double> x(3, 5);
00712   //
00713   // Note: The sizes of the arrays must be specified in number of elements,
00714   // not in bytes.
00715   //
00716   // Requires: `sizeof...(Sizes) <= sizeof...(Ts)`.
00717   // Requires: all arguments are convertible to `size_t`.
00718   template <class... Sizes>
00719   static constexpr PartialType<sizeof...(Sizes)> Partial(Sizes&&... sizes) {
00720     static_assert(sizeof...(Sizes) <= sizeof...(Ts), "");
00721     return PartialType<sizeof...(Sizes)>(absl::forward<Sizes>(sizes)...);
00722   }
00723 
00724   // Creates a layout with the sizes of all arrays specified. If you know
00725   // only the sizes of the first N arrays (where N can be zero), you can use
00726   // `Partial()` defined above. The constructor is essentially equivalent to
00727   // calling `Partial()` and passing in all array sizes; the constructor is
00728   // provided as a convenient abbreviation.
00729   //
00730   // Note: The sizes of the arrays must be specified in number of elements,
00731   // not in bytes.
00732   constexpr explicit Layout(internal_layout::TypeToSize<Ts>... sizes)
00733       : internal_layout::LayoutType<sizeof...(Ts), Ts...>(sizes...) {}
00734 };
00735 
00736 }  // namespace container_internal
00737 }  // namespace absl
00738 
00739 #endif  // ABSL_CONTAINER_INTERNAL_LAYOUT_H_


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