chromium/third_party/abseil-cpp/absl/container/internal/layout.h

// Copyright 2018 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//                           MOTIVATION AND TUTORIAL
//
// If you want to put in a single heap allocation N doubles followed by M ints,
// it's easy if N and M are known at compile time.
//
//   struct S {
//     double a[N];
//     int b[M];
//   };
//
//   S* p = new S;
//
// But what if N and M are known only in run time? Class template Layout to the
// rescue! It's a portable generalization of the technique known as struct hack.
//
//   // This object will tell us everything we need to know about the memory
//   // layout of double[N] followed by int[M]. It's structurally identical to
//   // size_t[2] that stores N and M. It's very cheap to create.
//   const Layout<double, int> layout(N, M);
//
//   // Allocate enough memory for both arrays. `AllocSize()` tells us how much
//   // memory is needed. We are free to use any allocation function we want as
//   // long as it returns aligned memory.
//   std::unique_ptr<unsigned char[]> p(new unsigned char[layout.AllocSize()]);
//
//   // Obtain the pointer to the array of doubles.
//   // Equivalent to `reinterpret_cast<double*>(p.get())`.
//   //
//   // We could have written layout.Pointer<0>(p) instead. If all the types are
//   // unique you can use either form, but if some types are repeated you must
//   // use the index form.
//   double* a = layout.Pointer<double>(p.get());
//
//   // Obtain the pointer to the array of ints.
//   // Equivalent to `reinterpret_cast<int*>(p.get() + N * 8)`.
//   int* b = layout.Pointer<int>(p);
//
// If we are unable to specify sizes of all fields, we can pass as many sizes as
// we can to `Partial()`. In return, it'll allow us to access the fields whose
// locations and sizes can be computed from the provided information.
// `Partial()` comes in handy when the array sizes are embedded into the
// allocation.
//
//   // size_t[0] containing N, size_t[1] containing M, double[N], int[M].
//   using L = Layout<size_t, size_t, double, int>;
//
//   unsigned char* Allocate(size_t n, size_t m) {
//     const L layout(1, 1, n, m);
//     unsigned char* p = new unsigned char[layout.AllocSize()];
//     *layout.Pointer<0>(p) = n;
//     *layout.Pointer<1>(p) = m;
//     return p;
//   }
//
//   void Use(unsigned char* p) {
//     // First, extract N and M.
//     // Specify that the first array has only one element. Using `prefix` we
//     // can access the first two arrays but not more.
//     constexpr auto prefix = L::Partial(1);
//     size_t n = *prefix.Pointer<0>(p);
//     size_t m = *prefix.Pointer<1>(p);
//
//     // Now we can get pointers to the payload.
//     const L layout(1, 1, n, m);
//     double* a = layout.Pointer<double>(p);
//     int* b = layout.Pointer<int>(p);
//   }
//
// The layout we used above combines fixed-size with dynamically-sized fields.
// This is quite common. Layout is optimized for this use case and attempts to
// generate optimal code. To help the compiler do that in more cases, you can
// specify the fixed sizes using `WithStaticSizes`. This ensures that all
// computations that can be performed at compile time are indeed performed at
// compile time. Note that sometimes the `template` keyword is needed. E.g.:
//
//   using SL = L::template WithStaticSizes<1, 1>;
//
//   void Use(unsigned char* p) {
//     // First, extract N and M.
//     // Using `prefix` we can access the first three arrays but not more.
//     //
//     // More details: The first element always has offset 0. `SL`
//     // has offsets for the second and third array based on sizes of
//     // the first and second array, specified via `WithStaticSizes`.
//     constexpr auto prefix = SL::Partial();
//     size_t n = *prefix.Pointer<0>(p);
//     size_t m = *prefix.Pointer<1>(p);
//
//     // Now we can get a pointer to the final payload.
//     const SL layout(n, m);
//     double* a = layout.Pointer<double>(p);
//     int* b = layout.Pointer<int>(p);
//   }
//
// Efficiency tip: The order of fields matters. In `Layout<T1, ..., TN>` try to
// ensure that `alignof(T1) >= ... >= alignof(TN)`. This way you'll have no
// padding in between arrays.
//
// You can manually override the alignment of an array by wrapping the type in
// `Aligned<T, N>`. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
// and behavior as `Layout<..., T, ...>` except that the first element of the
// array of `T` is aligned to `N` (the rest of the elements follow without
// padding). `N` cannot be less than `alignof(T)`.
//
// `AllocSize()` and `Pointer()` are the most basic methods for dealing with
// memory layouts. Check out the reference or code below to discover more.
//
//                            EXAMPLE
//
//   // Immutable move-only string with sizeof equal to sizeof(void*). The
//   // string size and the characters are kept in the same heap allocation.
//   class CompactString {
//    public:
//     CompactString(const char* s = "") {
//       const size_t size = strlen(s);
//       // size_t[1] followed by char[size + 1].
//       const L layout(size + 1);
//       p_.reset(new unsigned char[layout.AllocSize()]);
//       // If running under ASAN, mark the padding bytes, if any, to catch
//       // memory errors.
//       layout.PoisonPadding(p_.get());
//       // Store the size in the allocation.
//       *layout.Pointer<size_t>(p_.get()) = size;
//       // Store the characters in the allocation.
//       memcpy(layout.Pointer<char>(p_.get()), s, size + 1);
//     }
//
//     size_t size() const {
//       // Equivalent to reinterpret_cast<size_t&>(*p).
//       return *L::Partial().Pointer<size_t>(p_.get());
//     }
//
//     const char* c_str() const {
//       // Equivalent to reinterpret_cast<char*>(p.get() + sizeof(size_t)).
//       return L::Partial().Pointer<char>(p_.get());
//     }
//
//    private:
//     // Our heap allocation contains a single size_t followed by an array of
//     // chars.
//     using L = Layout<size_t, char>::WithStaticSizes<1>;
//     std::unique_ptr<unsigned char[]> p_;
//   };
//
//   int main() {
//     CompactString s = "hello";
//     assert(s.size() == 5);
//     assert(strcmp(s.c_str(), "hello") == 0);
//   }
//
//                               DOCUMENTATION
//
// The interface exported by this file consists of:
// - class `Layout<>` and its public members.
// - The public members of classes `internal_layout::LayoutWithStaticSizes<>`
//   and `internal_layout::LayoutImpl<>`. Those classes aren't intended to be
//   used directly, and their name and template parameter list are internal
//   implementation details, but the classes themselves provide most of the
//   functionality in this file. See comments on their members for detailed
//   documentation.
//
// `Layout<T1,... Tn>::Partial(count1,..., countm)` (where `m` <= `n`) returns a
// `LayoutImpl<>` object. `Layout<T1,..., Tn> layout(count1,..., countn)`
// creates a `Layout` object, which exposes the same functionality by inheriting
// from `LayoutImpl<>`.

#ifndef ABSL_CONTAINER_INTERNAL_LAYOUT_H_
#define ABSL_CONTAINER_INTERNAL_LAYOUT_H_

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

#include <array>
#include <string>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <utility>

#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/debugging/internal/demangle.h"
#include "absl/meta/type_traits.h"
#include "absl/strings/str_cat.h"
#include "absl/types/span.h"
#include "absl/utility/utility.h"

#ifdef ABSL_HAVE_ADDRESS_SANITIZER
#include <sanitizer/asan_interface.h>
#endif

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace container_internal {

// A type wrapper that instructs `Layout` to use the specific alignment for the
// array. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
// and behavior as `Layout<..., T, ...>` except that the first element of the
// array of `T` is aligned to `N` (the rest of the elements follow without
// padding).
//
// Requires: `N >= alignof(T)` and `N` is a power of 2.
template <class T, size_t N>
struct Aligned;

namespace internal_layout {

template <class T>
struct NotAligned { … };

NotAligned<const Aligned<T, N>>;

IntToSize;

template <class T>
struct Type : NotAligned<T> { … };

Type<Aligned<T, N>>;

template <class T>
struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> { … };

SizeOf<Aligned<T, N>>;

// Note: workaround for https://gcc.gnu.org/PR88115
template <class T>
struct AlignOf : NotAligned<T> { … };

AlignOf<Aligned<T, N>>;

// Does `Ts...` contain `T`?
Contains;

CopyConst;

// Note: We're not qualifying this with absl:: because it doesn't compile under
// MSVC.
SliceType;

// This namespace contains no types. It prevents functions defined in it from
// being found by ADL.
namespace adl_barrier {

template <class Needle, class... Ts>
constexpr size_t Find(Needle, Needle, Ts...) { … }

template <class Needle, class T, class... Ts>
constexpr size_t Find(Needle, T, Ts...) { … }

constexpr bool IsPow2(size_t n) { … }

// Returns `q * m` for the smallest `q` such that `q * m >= n`.
// Requires: `m` is a power of two. It's enforced by IsLegalElementType below.
constexpr size_t Align(size_t n, size_t m) { … }

constexpr size_t Min(size_t a, size_t b) { … }

constexpr size_t Max(size_t a) { … }

template <class... Ts>
constexpr size_t Max(size_t a, size_t b, Ts... rest) { … }

template <class T>
std::string TypeName() { … }

}  // namespace adl_barrier

EnableIf;

// Can `T` be a template argument of `Layout`?
IsLegalElementType;

template <class Elements, class StaticSizeSeq, class RuntimeSizeSeq,
          class SizeSeq, class OffsetSeq>
class LayoutImpl;

// Public base class of `Layout` and the result type of `Layout::Partial()`.
//
// `Elements...` contains all template arguments of `Layout` that created this
// instance.
//
// `StaticSizeSeq...` is an index_sequence containing the sizes specified at
// compile-time.
//
// `RuntimeSizeSeq...` is `[0, NumRuntimeSizes)`, where `NumRuntimeSizes` is the
// number of arguments passed to `Layout::Partial()` or `Layout::Layout()`.
//
// `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is `NumRuntimeSizes` plus
// the number of sizes in `StaticSizeSeq`.
//
// `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is
// `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we
// can compute offsets).
LayoutImpl<std::tuple<Elements...>, absl::index_sequence<StaticSizeSeq...>, absl::index_sequence<RuntimeSizeSeq...>, absl::index_sequence<SizeSeq...>, absl::index_sequence<OffsetSeq...>>;

// Defining a constexpr static class member variable is redundant and deprecated
// in C++17, but required in C++14.
template <class... Elements, size_t... StaticSizeSeq, size_t... RuntimeSizeSeq,
          size_t... SizeSeq, size_t... OffsetSeq>
constexpr std::array<size_t, sizeof...(StaticSizeSeq)> LayoutImpl<
    std::tuple<Elements...>, absl::index_sequence<StaticSizeSeq...>,
    absl::index_sequence<RuntimeSizeSeq...>, absl::index_sequence<SizeSeq...>,
    absl::index_sequence<OffsetSeq...>>::kStaticSizes;

LayoutType;

template <class StaticSizeSeq, class... Ts>
class LayoutWithStaticSizes
    : public LayoutType<StaticSizeSeq,
                        sizeof...(Ts) - adl_barrier::Min(sizeof...(Ts),
                                                         StaticSizeSeq::size()),
                        Ts...> { … };

}  // namespace internal_layout

// Descriptor of arrays of various types and sizes laid out in memory one after
// another. See the top of the file for documentation.
//
// Check out the public API of internal_layout::LayoutWithStaticSizes and
// internal_layout::LayoutImpl above. Those types are internal to the library
// but their methods are public, and they are inherited by `Layout`.
template <class... Ts>
class Layout : public internal_layout::LayoutWithStaticSizes<
                   absl::make_index_sequence<0>, Ts...> { … };

}  // namespace container_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_CONTAINER_INTERNAL_LAYOUT_H_