From 5aa5d282eac56a21e74611c1cdbaa97bb5db2dca Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Tue, 8 Feb 2022 02:05:36 +0300 Subject: chore(3p/abseil_cpp): unvendor abseil_cpp we weren't actually using these sources anymore, okay? Change-Id: If701571d9716de308d3512e1eb22c35db0877a66 Reviewed-on: https://cl.tvl.fyi/c/depot/+/5248 Tested-by: BuildkiteCI Reviewed-by: grfn Autosubmit: tazjin --- .../abseil_cpp/absl/container/internal/layout.h | 743 --------------------- 1 file changed, 743 deletions(-) delete mode 100644 third_party/abseil_cpp/absl/container/internal/layout.h (limited to 'third_party/abseil_cpp/absl/container/internal/layout.h') diff --git a/third_party/abseil_cpp/absl/container/internal/layout.h b/third_party/abseil_cpp/absl/container/internal/layout.h deleted file mode 100644 index 233678331543..000000000000 --- a/third_party/abseil_cpp/absl/container/internal/layout.h +++ /dev/null @@ -1,743 +0,0 @@ -// 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 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 p(new unsigned char[layout.AllocSize()]); -// -// // Obtain the pointer to the array of doubles. -// // Equivalent to `reinterpret_cast(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(p.get()); -// -// // Obtain the pointer to the array of ints. -// // Equivalent to `reinterpret_cast(p.get() + N * 8)`. -// int* b = layout.Pointer(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[1] containing N, size_t[1] containing M, double[N], int[M]. -// using L = Layout; -// -// 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(p); -// int* b = layout.Pointer(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 generates -// optimal code. All computations that can be performed at compile time are -// indeed performed at compile time. -// -// Efficiency tip: The order of fields matters. In `Layout` 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`. `Layout<..., Aligned, ...>` 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(1, 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(p_.get()) = size; -// // Store the characters in the allocation. -// memcpy(layout.Pointer(p_.get()), s, size + 1); -// } -// -// size_t size() const { -// // Equivalent to reinterpret_cast(*p). -// return *L::Partial().Pointer(p_.get()); -// } -// -// const char* c_str() const { -// // Equivalent to reinterpret_cast(p.get() + sizeof(size_t)). -// // The argument in Partial(1) specifies that we have size_t[1] in front -// // of the characters. -// return L::Partial(1).Pointer(p_.get()); -// } -// -// private: -// // Our heap allocation contains a size_t followed by an array of chars. -// using L = Layout; -// std::unique_ptr 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 class `internal_layout::LayoutImpl<>`. That class -// isn't intended to be used directly, and its name and template parameter -// list are internal implementation details, but the class itself provides -// most of the functionality in this file. See comments on its members for -// detailed documentation. -// -// `Layout::Partial(count1,..., countm)` (where `m` <= `n`) returns a -// `LayoutImpl<>` object. `Layout 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 -#include -#include - -#include -#include -#include -#include -#include -#include - -#include "absl/base/config.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 -#endif - -#if defined(__GXX_RTTI) -#define ABSL_INTERNAL_HAS_CXA_DEMANGLE -#endif - -#ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE -#include -#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, ...>` 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 -struct Aligned; - -namespace internal_layout { - -template -struct NotAligned {}; - -template -struct NotAligned> { - static_assert(sizeof(T) == 0, "Aligned cannot be const-qualified"); -}; - -template -using IntToSize = size_t; - -template -using TypeToSize = size_t; - -template -struct Type : NotAligned { - using type = T; -}; - -template -struct Type> { - using type = T; -}; - -template -struct SizeOf : NotAligned, std::integral_constant {}; - -template -struct SizeOf> : std::integral_constant {}; - -// Note: workaround for https://gcc.gnu.org/PR88115 -template -struct AlignOf : NotAligned { - static constexpr size_t value = alignof(T); -}; - -template -struct AlignOf> { - static_assert(N % alignof(T) == 0, - "Custom alignment can't be lower than the type's alignment"); - static constexpr size_t value = N; -}; - -// Does `Ts...` contain `T`? -template -using Contains = absl::disjunction...>; - -template -using CopyConst = - typename std::conditional::value, const To, To>::type; - -// Note: We're not qualifying this with absl:: because it doesn't compile under -// MSVC. -template -using SliceType = Span; - -// This namespace contains no types. It prevents functions defined in it from -// being found by ADL. -namespace adl_barrier { - -template -constexpr size_t Find(Needle, Needle, Ts...) { - static_assert(!Contains(), "Duplicate element type"); - return 0; -} - -template -constexpr size_t Find(Needle, T, Ts...) { - return adl_barrier::Find(Needle(), Ts()...) + 1; -} - -constexpr bool IsPow2(size_t n) { return !(n & (n - 1)); } - -// 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) { return (n + m - 1) & ~(m - 1); } - -constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; } - -constexpr size_t Max(size_t a) { return a; } - -template -constexpr size_t Max(size_t a, size_t b, Ts... rest) { - return adl_barrier::Max(b < a ? a : b, rest...); -} - -template -std::string TypeName() { - std::string out; - int status = 0; - char* demangled = nullptr; -#ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE - demangled = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, &status); -#endif - if (status == 0 && demangled != nullptr) { // Demangling succeeded. - absl::StrAppend(&out, "<", demangled, ">"); - free(demangled); - } else { -#if defined(__GXX_RTTI) || defined(_CPPRTTI) - absl::StrAppend(&out, "<", typeid(T).name(), ">"); -#endif - } - return out; -} - -} // namespace adl_barrier - -template -using EnableIf = typename std::enable_if::type; - -// Can `T` be a template argument of `Layout`? -template -using IsLegalElementType = std::integral_constant< - bool, !std::is_reference::value && !std::is_volatile::value && - !std::is_reference::type>::value && - !std::is_volatile::type>::value && - adl_barrier::IsPow2(AlignOf::value)>; - -template -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. -// -// `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is the number of arguments -// passed to `Layout::Partial()` or `Layout::Layout()`. -// -// `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is -// `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we -// can compute offsets). -template -class LayoutImpl, absl::index_sequence, - absl::index_sequence> { - private: - static_assert(sizeof...(Elements) > 0, "At least one field is required"); - static_assert(absl::conjunction...>::value, - "Invalid element type (see IsLegalElementType)"); - - enum { - NumTypes = sizeof...(Elements), - NumSizes = sizeof...(SizeSeq), - NumOffsets = sizeof...(OffsetSeq), - }; - - // These are guaranteed by `Layout`. - static_assert(NumOffsets == adl_barrier::Min(NumTypes, NumSizes + 1), - "Internal error"); - static_assert(NumTypes > 0, "Internal error"); - - // Returns the index of `T` in `Elements...`. Results in a compilation error - // if `Elements...` doesn't contain exactly one instance of `T`. - template - static constexpr size_t ElementIndex() { - static_assert(Contains, Type::type>...>(), - "Type not found"); - return adl_barrier::Find(Type(), - Type::type>()...); - } - - template - using ElementAlignment = - AlignOf>::type>; - - public: - // Element types of all arrays packed in a tuple. - using ElementTypes = std::tuple::type...>; - - // Element type of the Nth array. - template - using ElementType = typename std::tuple_element::type; - - constexpr explicit LayoutImpl(IntToSize... sizes) - : size_{sizes...} {} - - // Alignment of the layout, equal to the strictest alignment of all elements. - // All pointers passed to the methods of layout must be aligned to this value. - static constexpr size_t Alignment() { - return adl_barrier::Max(AlignOf::value...); - } - - // Offset in bytes of the Nth array. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // assert(x.Offset<0>() == 0); // The ints starts from 0. - // assert(x.Offset<1>() == 16); // The doubles starts from 16. - // - // Requires: `N <= NumSizes && N < sizeof...(Ts)`. - template = 0> - constexpr size_t Offset() const { - return 0; - } - - template = 0> - constexpr size_t Offset() const { - static_assert(N < NumOffsets, "Index out of bounds"); - return adl_barrier::Align( - Offset() + SizeOf>() * size_[N - 1], - ElementAlignment::value); - } - - // Offset in bytes of the array with the specified element type. There must - // be exactly one such array and its zero-based index must be at most - // `NumSizes`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // assert(x.Offset() == 0); // The ints starts from 0. - // assert(x.Offset() == 16); // The doubles starts from 16. - template - constexpr size_t Offset() const { - return Offset()>(); - } - - // Offsets in bytes of all arrays for which the offsets are known. - constexpr std::array Offsets() const { - return {{Offset()...}}; - } - - // The number of elements in the Nth array. This is the Nth argument of - // `Layout::Partial()` or `Layout::Layout()` (zero-based). - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // assert(x.Size<0>() == 3); - // assert(x.Size<1>() == 4); - // - // Requires: `N < NumSizes`. - template - constexpr size_t Size() const { - static_assert(N < NumSizes, "Index out of bounds"); - return size_[N]; - } - - // The number of elements in the array with the specified element type. - // There must be exactly one such array and its zero-based index must be - // at most `NumSizes`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // assert(x.Size() == 3); - // assert(x.Size() == 4); - template - constexpr size_t Size() const { - return Size()>(); - } - - // The number of elements of all arrays for which they are known. - constexpr std::array Sizes() const { - return {{Size()...}}; - } - - // Pointer to the beginning of the Nth array. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // int* ints = x.Pointer<0>(p); - // double* doubles = x.Pointer<1>(p); - // - // Requires: `N <= NumSizes && N < sizeof...(Ts)`. - // Requires: `p` is aligned to `Alignment()`. - template - CopyConst>* Pointer(Char* p) const { - using C = typename std::remove_const::type; - static_assert( - std::is_same() || std::is_same() || - std::is_same(), - "The argument must be a pointer to [const] [signed|unsigned] char"); - constexpr size_t alignment = Alignment(); - (void)alignment; - assert(reinterpret_cast(p) % alignment == 0); - return reinterpret_cast>*>(p + Offset()); - } - - // Pointer to the beginning of the array with the specified element type. - // There must be exactly one such array and its zero-based index must be at - // most `NumSizes`. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // int* ints = x.Pointer(p); - // double* doubles = x.Pointer(p); - // - // Requires: `p` is aligned to `Alignment()`. - template - CopyConst* Pointer(Char* p) const { - return Pointer()>(p); - } - - // Pointers to all arrays for which pointers are known. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // - // int* ints; - // double* doubles; - // std::tie(ints, doubles) = x.Pointers(p); - // - // Requires: `p` is aligned to `Alignment()`. - // - // Note: We're not using ElementType alias here because it does not compile - // under MSVC. - template - std::tuple::type>*...> - Pointers(Char* p) const { - return std::tuple>*...>( - Pointer(p)...); - } - - // The Nth array. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // Span ints = x.Slice<0>(p); - // Span doubles = x.Slice<1>(p); - // - // Requires: `N < NumSizes`. - // Requires: `p` is aligned to `Alignment()`. - template - SliceType>> Slice(Char* p) const { - return SliceType>>(Pointer(p), Size()); - } - - // The array with the specified element type. There must be exactly one - // such array and its zero-based index must be less than `NumSizes`. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // Span ints = x.Slice(p); - // Span doubles = x.Slice(p); - // - // Requires: `p` is aligned to `Alignment()`. - template - SliceType> Slice(Char* p) const { - return Slice()>(p); - } - - // All arrays with known sizes. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; - // - // Span ints; - // Span doubles; - // std::tie(ints, doubles) = x.Slices(p); - // - // Requires: `p` is aligned to `Alignment()`. - // - // Note: We're not using ElementType alias here because it does not compile - // under MSVC. - template - std::tuple::type>>...> - Slices(Char* p) const { - // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63875 (fixed - // in 6.1). - (void)p; - return std::tuple>>...>( - Slice(p)...); - } - - // The size of the allocation that fits all arrays. - // - // // int[3], 4 bytes of padding, double[4]. - // Layout x(3, 4); - // unsigned char* p = new unsigned char[x.AllocSize()]; // 48 bytes - // - // Requires: `NumSizes == sizeof...(Ts)`. - constexpr size_t AllocSize() const { - static_assert(NumTypes == NumSizes, "You must specify sizes of all fields"); - return Offset() + - SizeOf>() * size_[NumTypes - 1]; - } - - // If built with --config=asan, poisons padding bytes (if any) in the - // allocation. The pointer must point to a memory block at least - // `AllocSize()` bytes in length. - // - // `Char` must be `[const] [signed|unsigned] char`. - // - // Requires: `p` is aligned to `Alignment()`. - template = 0> - void PoisonPadding(const Char* p) const { - Pointer<0>(p); // verify the requirements on `Char` and `p` - } - - template = 0> - void PoisonPadding(const Char* p) const { - static_assert(N < NumOffsets, "Index out of bounds"); - (void)p; -#ifdef ABSL_HAVE_ADDRESS_SANITIZER - PoisonPadding(p); - // The `if` is an optimization. It doesn't affect the observable behaviour. - if (ElementAlignment::value % ElementAlignment::value) { - size_t start = - Offset() + SizeOf>() * size_[N - 1]; - ASAN_POISON_MEMORY_REGION(p + start, Offset() - start); - } -#endif - } - - // Human-readable description of the memory layout. Useful for debugging. - // Slow. - // - // // char[5], 3 bytes of padding, int[3], 4 bytes of padding, followed - // // by an unknown number of doubles. - // auto x = Layout::Partial(5, 3); - // assert(x.DebugString() == - // "@0(1)[5]; @8(4)[3]; @24(8)"); - // - // Each field is in the following format: @offset(sizeof)[size] ( - // may be missing depending on the target platform). For example, - // @8(4)[3] means that at offset 8 we have an array of ints, where each - // int is 4 bytes, and we have 3 of those ints. The size of the last field may - // be missing (as in the example above). Only fields with known offsets are - // described. Type names may differ across platforms: one compiler might - // produce "unsigned*" where another produces "unsigned int *". - std::string DebugString() const { - const auto offsets = Offsets(); - const size_t sizes[] = {SizeOf>()...}; - const std::string types[] = { - adl_barrier::TypeName>()...}; - std::string res = absl::StrCat("@0", types[0], "(", sizes[0], ")"); - for (size_t i = 0; i != NumOffsets - 1; ++i) { - absl::StrAppend(&res, "[", size_[i], "]; @", offsets[i + 1], types[i + 1], - "(", sizes[i + 1], ")"); - } - // NumSizes is a constant that may be zero. Some compilers cannot see that - // inside the if statement "size_[NumSizes - 1]" must be valid. - int last = static_cast(NumSizes) - 1; - if (NumTypes == NumSizes && last >= 0) { - absl::StrAppend(&res, "[", size_[last], "]"); - } - return res; - } - - private: - // Arguments of `Layout::Partial()` or `Layout::Layout()`. - size_t size_[NumSizes > 0 ? NumSizes : 1]; -}; - -template -using LayoutType = LayoutImpl< - std::tuple, absl::make_index_sequence, - absl::make_index_sequence>; - -} // 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::LayoutImpl above. The type is -// internal to the library but its methods are public, and they are inherited -// by `Layout`. -template -class Layout : public internal_layout::LayoutType { - public: - static_assert(sizeof...(Ts) > 0, "At least one field is required"); - static_assert( - absl::conjunction...>::value, - "Invalid element type (see IsLegalElementType)"); - - // The result type of `Partial()` with `NumSizes` arguments. - template - using PartialType = internal_layout::LayoutType; - - // `Layout` knows the element types of the arrays we want to lay out in - // memory but not the number of elements in each array. - // `Partial(size1, ..., sizeN)` allows us to specify the latter. The - // resulting immutable object can be used to obtain pointers to the - // individual arrays. - // - // It's allowed to pass fewer array sizes than the number of arrays. E.g., - // if all you need is to the offset of the second array, you only need to - // pass one argument -- the number of elements in the first array. - // - // // int[3] followed by 4 bytes of padding and an unknown number of - // // doubles. - // auto x = Layout::Partial(3); - // // doubles start at byte 16. - // assert(x.Offset<1>() == 16); - // - // If you know the number of elements in all arrays, you can still call - // `Partial()` but it's more convenient to use the constructor of `Layout`. - // - // Layout x(3, 5); - // - // Note: The sizes of the arrays must be specified in number of elements, - // not in bytes. - // - // Requires: `sizeof...(Sizes) <= sizeof...(Ts)`. - // Requires: all arguments are convertible to `size_t`. - template - static constexpr PartialType Partial(Sizes&&... sizes) { - static_assert(sizeof...(Sizes) <= sizeof...(Ts), ""); - return PartialType(absl::forward(sizes)...); - } - - // Creates a layout with the sizes of all arrays specified. If you know - // only the sizes of the first N arrays (where N can be zero), you can use - // `Partial()` defined above. The constructor is essentially equivalent to - // calling `Partial()` and passing in all array sizes; the constructor is - // provided as a convenient abbreviation. - // - // Note: The sizes of the arrays must be specified in number of elements, - // not in bytes. - constexpr explicit Layout(internal_layout::TypeToSize... sizes) - : internal_layout::LayoutType(sizes...) {} -}; - -} // namespace container_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_CONTAINER_INTERNAL_LAYOUT_H_ -- cgit 1.4.1