From 2125e6444a9de9e41f21ecdc674dd7d8759c149d Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 1 Aug 2018 04:34:12 -0700 Subject: Export of internal Abseil changes. -- ac7508120c60dfe689c40929e416b6a486f83ee3 by Gennadiy Rozental : Internal change PiperOrigin-RevId: 206912089 -- bd709faba88565367b6d337466e6456481b5f3e8 by Matt Calabrese : Implement `std::experimental::is_detected` in type_traits internals and move `is_detected_convertible` from variant's internals to type_traits internals. This is in preparation of creating workarounds for broken standard traits. PiperOrigin-RevId: 206825598 -- 0dbddea569370eb9b6348cee172d1874f9046eb4 by Jorg Brown : Support users who turn on floating-point conversion warnings PiperOrigin-RevId: 206813209 -- 30991f757c8f0100584619d8a9c41897d029f112 by Jorg Brown : Speed up the absl::Seconds() function for floating-point values, roughly by 4.5x, since we can take advantage of the fact that we're just taking a floating-point number and splitting it into its integral and fractional parts. PiperOrigin-RevId: 206806270 -- 6883837176838aa5a517e7a8cb4c99afd24c0d12 by Jon Cohen : Remove the DISABLE_INSTALL from absl_container. It doesn't do anything. PiperOrigin-RevId: 206802544 -- 92ab14fed06e6dd1f01a0284bd7f95d3e2c0c3d8 by Jon Cohen : Internal change PiperOrigin-RevId: 206776244 -- 17b76c7f364ac562d9e0faeca0320f63aa3fdb85 by Jorg Brown : Fix absl/strings:numbers_test flakiness due to exceeding the 1-minute timeout PiperOrigin-RevId: 206763175 -- 6637843f2e198b8efd90e5577fbc86bdea43b2cc by Abseil Team : Adds templated allocator to absl::FixedArray with corresponding tests PiperOrigin-RevId: 206354178 -- bced22f81add828c9b4c60eb45554d36c22e2f96 by Abseil Team : Adds templated allocator to absl::FixedArray with corresponding tests PiperOrigin-RevId: 206347377 -- 75be14a71d2d5e335812d5b7670120271fb5bd79 by Abseil Team : Internal change. PiperOrigin-RevId: 206326935 -- 6929e43f4c7898b1f51e441911a19092a06fbf97 by Abseil Team : Adds templated allocator to absl::FixedArray with corresponding tests PiperOrigin-RevId: 206326368 -- 55ae34b75ff029eb267f9519e577bab8a575b487 by Abseil Team : Internal change. PiperOrigin-RevId: 206233448 -- 6950a8ccddf35d451eec2d02cd28a797c8b7cf6a by Matt Kulukundis : Internal change PiperOrigin-RevId: 206035613 GitOrigin-RevId: ac7508120c60dfe689c40929e416b6a486f83ee3 Change-Id: I675605abbedab6b3ac9aa82195cbd059ff7c82b1 --- absl/container/fixed_array.h | 154 ++++++++++++++++++++++++++----------------- 1 file changed, 94 insertions(+), 60 deletions(-) (limited to 'absl/container/fixed_array.h') diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h index 62600df0..f480047a 100644 --- a/absl/container/fixed_array.h +++ b/absl/container/fixed_array.h @@ -47,6 +47,7 @@ #include "absl/base/macros.h" #include "absl/base/optimization.h" #include "absl/base/port.h" +#include "absl/container/internal/compressed_tuple.h" #include "absl/memory/memory.h" namespace absl { @@ -76,73 +77,99 @@ constexpr static auto kFixedArrayUseDefault = static_cast(-1); // heap allocation, it will do so with global `::operator new[]()` and // `::operator delete[]()`, even if T provides class-scope overrides for these // operators. -template +template > class FixedArray { static_assert(!std::is_array::value || std::extent::value > 0, "Arrays with unknown bounds cannot be used with FixedArray."); + static constexpr size_t kInlineBytesDefault = 256; + using AllocatorTraits = std::allocator_traits; // std::iterator_traits isn't guaranteed to be SFINAE-friendly until C++17, // but this seems to be mostly pedantic. template using EnableIfForwardIterator = absl::enable_if_t::iterator_category, std::forward_iterator_tag>::value>; + static constexpr bool NoexceptCopyable() { + return std::is_nothrow_copy_constructible::value && + absl::allocator_is_nothrow::value; + } + static constexpr bool NoexceptMovable() { + return std::is_nothrow_move_constructible::value && + absl::allocator_is_nothrow::value; + } + static constexpr bool DefaultConstructorIsNonTrivial() { + return !absl::is_trivially_default_constructible::value; + } public: - using value_type = T; - using iterator = T*; - using const_iterator = const T*; + using allocator_type = typename AllocatorTraits::allocator_type; + using value_type = typename allocator_type::value_type; + using pointer = typename allocator_type::pointer; + using const_pointer = typename allocator_type::const_pointer; + using reference = typename allocator_type::reference; + using const_reference = typename allocator_type::const_reference; + using size_type = typename allocator_type::size_type; + using difference_type = typename allocator_type::difference_type; + using iterator = pointer; + using const_iterator = const_pointer; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; - using reference = T&; - using const_reference = const T&; - using pointer = T*; - using const_pointer = const T*; - using difference_type = ptrdiff_t; - using size_type = size_t; static constexpr size_type inline_elements = - inlined == kFixedArrayUseDefault - ? kInlineBytesDefault / sizeof(value_type) - : inlined; + (N == kFixedArrayUseDefault ? kInlineBytesDefault / sizeof(value_type) + : static_cast(N)); - FixedArray(const FixedArray& other) - : FixedArray(other.begin(), other.end()) {} + FixedArray( + const FixedArray& other, + const allocator_type& a = allocator_type()) noexcept(NoexceptCopyable()) + : FixedArray(other.begin(), other.end(), a) {} - FixedArray(FixedArray&& other) noexcept( - absl::conjunction>, - std::is_nothrow_move_constructible>::value) + FixedArray( + FixedArray&& other, + const allocator_type& a = allocator_type()) noexcept(NoexceptMovable()) : FixedArray(std::make_move_iterator(other.begin()), - std::make_move_iterator(other.end())) {} + std::make_move_iterator(other.end()), a) {} // Creates an array object that can store `n` elements. // Note that trivially constructible elements will be uninitialized. - explicit FixedArray(size_type n) : storage_(n) { - absl::memory_internal::uninitialized_default_construct_n(storage_.begin(), - size()); + explicit FixedArray(size_type n, const allocator_type& a = allocator_type()) + : storage_(n, a) { + if (DefaultConstructorIsNonTrivial()) { + memory_internal::ConstructStorage(storage_.alloc(), storage_.begin(), + storage_.end()); + } } // Creates an array initialized with `n` copies of `val`. - FixedArray(size_type n, const value_type& val) : storage_(n) { - std::uninitialized_fill_n(data(), size(), val); + FixedArray(size_type n, const value_type& val, + const allocator_type& a = allocator_type()) + : storage_(n, a) { + memory_internal::ConstructStorage(storage_.alloc(), storage_.begin(), + storage_.end(), val); } + // Creates an array initialized with the size and contents of `init_list`. + FixedArray(std::initializer_list init_list, + const allocator_type& a = allocator_type()) + : FixedArray(init_list.begin(), init_list.end(), a) {} + // Creates an array initialized with the elements from the input // range. The array's size will always be `std::distance(first, last)`. // REQUIRES: Iterator must be a forward_iterator or better. template * = nullptr> - FixedArray(Iterator first, Iterator last) - : storage_(std::distance(first, last)) { - std::uninitialized_copy(first, last, data()); + FixedArray(Iterator first, Iterator last, + const allocator_type& a = allocator_type()) + : storage_(std::distance(first, last), a) { + memory_internal::CopyToStorageFromRange(storage_.alloc(), storage_.begin(), + first, last); } - FixedArray(std::initializer_list init_list) - : FixedArray(init_list.begin(), init_list.end()) {} - ~FixedArray() noexcept { - for (const StorageElement& cur : storage_) { - cur.~StorageElement(); + for (auto* cur = storage_.begin(); cur != storage_.end(); ++cur) { + AllocatorTraits::destroy(*storage_.alloc(), cur); } } @@ -332,7 +359,6 @@ class FixedArray { friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) { return !(lhs < rhs); } - private: // StorageElement // @@ -364,6 +390,8 @@ class FixedArray { using StorageElement = absl::conditional_t::value, StorageElementWrapper, value_type>; + using StorageElementBuffer = + absl::aligned_storage_t; static pointer AsValueType(pointer ptr) { return ptr; } static pointer AsValueType(StorageElementWrapper* ptr) { @@ -374,9 +402,6 @@ class FixedArray { static_assert(alignof(StorageElement) == alignof(value_type), ""); struct NonEmptyInlinedStorage { - using StorageElementBuffer = - absl::aligned_storage_t; StorageElement* data() { return reinterpret_cast(inlined_storage_.data()); } @@ -386,8 +411,8 @@ class FixedArray { void* RedzoneEnd() { return &redzone_end_ + 1; } #endif // ADDRESS_SANITIZER - void AnnotateConstruct(size_t); - void AnnotateDestruct(size_t); + void AnnotateConstruct(size_type); + void AnnotateDestruct(size_type); ADDRESS_SANITIZER_REDZONE(redzone_begin_); std::array inlined_storage_; @@ -396,8 +421,8 @@ class FixedArray { struct EmptyInlinedStorage { StorageElement* data() { return nullptr; } - void AnnotateConstruct(size_t) {} - void AnnotateDestruct(size_t) {} + void AnnotateConstruct(size_type) {} + void AnnotateDestruct(size_type) {} }; using InlinedStorage = @@ -414,48 +439,57 @@ class FixedArray { // class Storage : public InlinedStorage { public: - explicit Storage(size_type n) : data_(CreateStorage(n)), size_(n) {} + Storage(size_type n, const allocator_type& a) + : size_alloc_(n, a), data_(InitializeData()) {} + ~Storage() noexcept { if (UsingInlinedStorage(size())) { - this->AnnotateDestruct(size()); + InlinedStorage::AnnotateDestruct(size()); } else { - std::allocator().deallocate(begin(), size()); + AllocatorTraits::deallocate(*alloc(), AsValueType(begin()), size()); } } - size_type size() const { return size_; } + size_type size() const { return size_alloc_.template get<0>(); } StorageElement* begin() const { return data_; } StorageElement* end() const { return begin() + size(); } + allocator_type* alloc() { + return std::addressof(size_alloc_.template get<1>()); + } private: static bool UsingInlinedStorage(size_type n) { return n <= inline_elements; } - StorageElement* CreateStorage(size_type n) { - if (UsingInlinedStorage(n)) { - this->AnnotateConstruct(n); + StorageElement* InitializeData() { + if (UsingInlinedStorage(size())) { + InlinedStorage::AnnotateConstruct(size()); return InlinedStorage::data(); } else { - return std::allocator().allocate(n); + return reinterpret_cast( + AllocatorTraits::allocate(*alloc(), size())); } } - StorageElement* const data_; - const size_type size_; + // `CompressedTuple` takes advantage of EBCO for stateless `allocator_type`s + container_internal::CompressedTuple size_alloc_; + StorageElement* data_; }; - const Storage storage_; + Storage storage_; }; -template -constexpr size_t FixedArray::inline_elements; +template +constexpr size_t FixedArray::kInlineBytesDefault; -template -constexpr size_t FixedArray::kInlineBytesDefault; +template +constexpr typename FixedArray::size_type + FixedArray::inline_elements; -template -void FixedArray::NonEmptyInlinedStorage::AnnotateConstruct(size_t n) { +template +void FixedArray::NonEmptyInlinedStorage::AnnotateConstruct( + typename FixedArray::size_type n) { #ifdef ADDRESS_SANITIZER if (!n) return; ANNOTATE_CONTIGUOUS_CONTAINER(data(), RedzoneEnd(), RedzoneEnd(), data() + n); @@ -464,8 +498,9 @@ void FixedArray::NonEmptyInlinedStorage::AnnotateConstruct(size_t n) { static_cast(n); // Mark used when not in asan mode } -template -void FixedArray::NonEmptyInlinedStorage::AnnotateDestruct(size_t n) { +template +void FixedArray::NonEmptyInlinedStorage::AnnotateDestruct( + typename FixedArray::size_type n) { #ifdef ADDRESS_SANITIZER if (!n) return; ANNOTATE_CONTIGUOUS_CONTAINER(data(), RedzoneEnd(), data() + n, RedzoneEnd()); @@ -473,6 +508,5 @@ void FixedArray::NonEmptyInlinedStorage::AnnotateDestruct(size_t n) { #endif // ADDRESS_SANITIZER static_cast(n); // Mark used when not in asan mode } - } // namespace absl #endif // ABSL_CONTAINER_FIXED_ARRAY_H_ -- cgit v1.2.3