From 666fc1266bccfd8e6eaaa084e7b42580bb8eb199 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 4 Apr 2019 08:13:57 -0700 Subject: Export of internal Abseil changes. -- bc89d3221e3927d08881d75eeee0e8db862300fa by Benjamin Barenblat : Clean up C-style casts in `ABSL_ASSERT` PiperOrigin-RevId: 241932756 -- 17482daae4b3e2fc725b759586590ac466b72a1e by Jon Cohen : Move Gtest-specific CMake code to its own directory PiperOrigin-RevId: 241920192 -- 9ae52b4f665625352c0a789cff884bde492c28f5 by CJ Johnson : Moves private data methods from InlinedVector to InlinedVector Storage in anticipation of migrating the Rep union type PiperOrigin-RevId: 241794144 -- 95315bc50a61a0aae4f171b44c2312158a43e72e by Jon Cohen : Use /DNOMINMAX in Abseil tests. This offsets inlcudes of from gtest. PiperOrigin-RevId: 241790584 -- ee505c7f2ab99d29c165ea21a07190474f64053d by CJ Johnson : Adds inlined_vector_internal to the deps of inlined_vector in CMakeLists.txt PiperOrigin-RevId: 241775332 -- 94eb5165b49bab59ce7de143be38a4581d5658da by CJ Johnson : Migrates InlinedVector Storage to class Metadata for compatibility with the eventual member-wise migration to the new exception safe implementation PiperOrigin-RevId: 241633420 -- f99e172caad1ec8b35bf7bbabaf2833d55a6f055 by Abseil Team : Add MSVC specific linker flags only to MSVC builds. PiperOrigin-RevId: 241615711 -- 3ad19d2779281e945bdf56643dc5cee3f730eb4f by Abseil Team : Add a comment about per-process randomization of absl::Hash. PiperOrigin-RevId: 241583697 -- 8dfb02d725fee3528351b2da4ed32a7455f9858a by Tom Manshreck : Internal change PiperOrigin-RevId: 241564734 GitOrigin-RevId: bc89d3221e3927d08881d75eeee0e8db862300fa Change-Id: Ibad3da416d08a96ec1f8313f8b519b4270b7e01a --- CMake/CMakeLists.txt.in | 15 -- CMake/DownloadGTest.cmake | 32 --- CMake/Googletest/CMakeLists.txt.in | 15 ++ CMake/Googletest/DownloadGTest.cmake | 32 +++ CMakeLists.txt | 2 +- absl/base/macros.h | 7 +- absl/container/BUILD.bazel | 1 + absl/container/CMakeLists.txt | 2 + absl/container/inlined_vector.h | 354 ++++++++++++++--------------- absl/container/internal/inlined_vector.h | 90 +++++--- absl/copts/AbseilConfigureCopts.cmake | 2 +- absl/copts/GENERATED_AbseilCopts.cmake | 1 + absl/copts/GENERATED_copts.bzl | 1 + absl/copts/copts.py | 1 + absl/hash/hash.h | 4 + absl/types/BUILD.bazel | 1 + absl/types/CMakeLists.txt | 2 + absl/types/internal/optional.h | 364 ++++++++++++++++++++++++++++++ absl/types/optional.h | 375 ++----------------------------- 19 files changed, 681 insertions(+), 620 deletions(-) delete mode 100644 CMake/CMakeLists.txt.in delete mode 100644 CMake/DownloadGTest.cmake create mode 100644 CMake/Googletest/CMakeLists.txt.in create mode 100644 CMake/Googletest/DownloadGTest.cmake create mode 100644 absl/types/internal/optional.h diff --git a/CMake/CMakeLists.txt.in b/CMake/CMakeLists.txt.in deleted file mode 100644 index d60a33e9..00000000 --- a/CMake/CMakeLists.txt.in +++ /dev/null @@ -1,15 +0,0 @@ -cmake_minimum_required(VERSION 2.8.2) - -project(googletest-download NONE) - -include(ExternalProject) -ExternalProject_Add(googletest - GIT_REPOSITORY https://github.com/google/googletest.git - GIT_TAG master - SOURCE_DIR "${CMAKE_BINARY_DIR}/googletest-src" - BINARY_DIR "${CMAKE_BINARY_DIR}/googletest-build" - CONFIGURE_COMMAND "" - BUILD_COMMAND "" - INSTALL_COMMAND "" - TEST_COMMAND "" -) \ No newline at end of file diff --git a/CMake/DownloadGTest.cmake b/CMake/DownloadGTest.cmake deleted file mode 100644 index 3c682aef..00000000 --- a/CMake/DownloadGTest.cmake +++ /dev/null @@ -1,32 +0,0 @@ -# Downloads and unpacks googletest at configure time. Based on the instructions -# at https://github.com/google/googletest/tree/master/googletest#incorporating-into-an-existing-cmake-project - -# Download the latest googletest from Github master -configure_file( - ${CMAKE_CURRENT_LIST_DIR}/CMakeLists.txt.in - ${CMAKE_BINARY_DIR}/googletest-download/CMakeLists.txt -) - -# Configure and build the downloaded googletest source -execute_process(COMMAND ${CMAKE_COMMAND} -G "${CMAKE_GENERATOR}" . - RESULT_VARIABLE result - WORKING_DIRECTORY ${CMAKE_BINARY_DIR}/googletest-download ) -if(result) - message(FATAL_ERROR "CMake step for googletest failed: ${result}") -endif() - -execute_process(COMMAND ${CMAKE_COMMAND} --build . - RESULT_VARIABLE result - WORKING_DIRECTORY ${CMAKE_BINARY_DIR}/googletest-download) -if(result) - message(FATAL_ERROR "Build step for googletest failed: ${result}") -endif() - -# Prevent overriding the parent project's compiler/linker settings on Windows -set(gtest_force_shared_crt ON CACHE BOOL "" FORCE) - -# Add googletest directly to our build. This defines the gtest and gtest_main -# targets. -add_subdirectory(${CMAKE_BINARY_DIR}/googletest-src - ${CMAKE_BINARY_DIR}/googletest-build - EXCLUDE_FROM_ALL) diff --git a/CMake/Googletest/CMakeLists.txt.in b/CMake/Googletest/CMakeLists.txt.in new file mode 100644 index 00000000..d60a33e9 --- /dev/null +++ b/CMake/Googletest/CMakeLists.txt.in @@ -0,0 +1,15 @@ +cmake_minimum_required(VERSION 2.8.2) + +project(googletest-download NONE) + +include(ExternalProject) +ExternalProject_Add(googletest + GIT_REPOSITORY https://github.com/google/googletest.git + GIT_TAG master + SOURCE_DIR "${CMAKE_BINARY_DIR}/googletest-src" + BINARY_DIR "${CMAKE_BINARY_DIR}/googletest-build" + CONFIGURE_COMMAND "" + BUILD_COMMAND "" + INSTALL_COMMAND "" + TEST_COMMAND "" +) \ No newline at end of file diff --git a/CMake/Googletest/DownloadGTest.cmake b/CMake/Googletest/DownloadGTest.cmake new file mode 100644 index 00000000..3c682aef --- /dev/null +++ b/CMake/Googletest/DownloadGTest.cmake @@ -0,0 +1,32 @@ +# Downloads and unpacks googletest at configure time. Based on the instructions +# at https://github.com/google/googletest/tree/master/googletest#incorporating-into-an-existing-cmake-project + +# Download the latest googletest from Github master +configure_file( + ${CMAKE_CURRENT_LIST_DIR}/CMakeLists.txt.in + ${CMAKE_BINARY_DIR}/googletest-download/CMakeLists.txt +) + +# Configure and build the downloaded googletest source +execute_process(COMMAND ${CMAKE_COMMAND} -G "${CMAKE_GENERATOR}" . + RESULT_VARIABLE result + WORKING_DIRECTORY ${CMAKE_BINARY_DIR}/googletest-download ) +if(result) + message(FATAL_ERROR "CMake step for googletest failed: ${result}") +endif() + +execute_process(COMMAND ${CMAKE_COMMAND} --build . + RESULT_VARIABLE result + WORKING_DIRECTORY ${CMAKE_BINARY_DIR}/googletest-download) +if(result) + message(FATAL_ERROR "Build step for googletest failed: ${result}") +endif() + +# Prevent overriding the parent project's compiler/linker settings on Windows +set(gtest_force_shared_crt ON CACHE BOOL "" FORCE) + +# Add googletest directly to our build. This defines the gtest and gtest_main +# targets. +add_subdirectory(${CMAKE_BINARY_DIR}/googletest-src + ${CMAKE_BINARY_DIR}/googletest-build + EXCLUDE_FROM_ALL) diff --git a/CMakeLists.txt b/CMakeLists.txt index dff46f91..e7587f72 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -90,7 +90,7 @@ endif() if(BUILD_TESTING) if(${ABSL_USE_GOOGLETEST_HEAD}) - include(CMake/DownloadGTest.cmake) + include(CMake/Googletest/DownloadGTest.cmake) set(absl_gtest_src_dir ${CMAKE_BINARY_DIR}/googletest-src) set(absl_gtest_build_dir ${CMAKE_BINARY_DIR}/googletest-build) endif() diff --git a/absl/base/macros.h b/absl/base/macros.h index 5b43d7c2..ca620792 100644 --- a/absl/base/macros.h +++ b/absl/base/macros.h @@ -191,10 +191,11 @@ enum LinkerInitialized { // This macro is inspired by // https://akrzemi1.wordpress.com/2017/05/18/asserts-in-constexpr-functions/ #if defined(NDEBUG) -#define ABSL_ASSERT(expr) (false ? (void)(expr) : (void)0) +#define ABSL_ASSERT(expr) \ + (false ? static_cast(expr) : static_cast(0)) #else -#define ABSL_ASSERT(expr) \ - (ABSL_PREDICT_TRUE((expr)) ? (void)0 \ +#define ABSL_ASSERT(expr) \ + (ABSL_PREDICT_TRUE((expr)) ? static_cast(0) \ : [] { assert(false && #expr); }()) // NOLINT #endif diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 066a9886..f25a9ff9 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -123,6 +123,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":compressed_tuple", "//absl/meta:type_traits", ], ) diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 292fea2a..3c44bd0e 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -115,6 +115,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::compressed_tuple absl::type_traits PUBLIC ) @@ -129,6 +130,7 @@ absl_cc_library( DEPS absl::algorithm absl::core_headers + absl::inlined_vector_internal absl::throw_delegate absl::memory PUBLIC diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 9b699b57..c59fb938 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -70,8 +70,6 @@ class InlinedVector { N > 0, "InlinedVector cannot be instantiated with `0` inlined elements."); using Storage = inlined_vector_internal::Storage; - using Tag = typename Storage::Tag; - using AllocatorAndTag = typename Storage::AllocatorAndTag; using Allocation = typename Storage::Allocation; template @@ -162,18 +160,19 @@ class InlinedVector { // Creates a copy of an `other` inlined vector using `other`'s allocator. InlinedVector(const InlinedVector& other) - : InlinedVector(other, other.allocator()) {} + : InlinedVector(other, other.storage_.GetAllocator()) {} // Creates a copy of an `other` inlined vector using a specified allocator. InlinedVector(const InlinedVector& other, const allocator_type& alloc) : storage_(alloc) { reserve(other.size()); - if (allocated()) { - UninitializedCopy(other.begin(), other.end(), allocated_space()); - tag().set_allocated_size(other.size()); + if (storage_.GetIsAllocated()) { + UninitializedCopy(other.begin(), other.end(), + storage_.GetAllocatedData()); + storage_.SetAllocatedSize(other.size()); } else { - UninitializedCopy(other.begin(), other.end(), inlined_space()); - tag().set_inline_size(other.size()); + UninitializedCopy(other.begin(), other.end(), storage_.GetInlinedData()); + storage_.SetInlinedSize(other.size()); } } @@ -195,19 +194,20 @@ class InlinedVector { InlinedVector(InlinedVector&& other) noexcept( absl::allocator_is_nothrow::value || std::is_nothrow_move_constructible::value) - : storage_(other.allocator()) { - if (other.allocated()) { + : storage_(other.storage_.GetAllocator()) { + if (other.storage_.GetIsAllocated()) { // We can just steal the underlying buffer from the source. // That leaves the source empty, so we clear its size. - init_allocation(other.allocation()); - tag().set_allocated_size(other.size()); - other.tag() = Tag(); + storage_.InitAllocation(other.storage_.GetAllocation()); + storage_.SetAllocatedSize(other.size()); + other.storage_.SetInlinedSize(0); } else { UninitializedCopy( - std::make_move_iterator(other.inlined_space()), - std::make_move_iterator(other.inlined_space() + other.size()), - inlined_space()); - tag().set_inline_size(other.size()); + std::make_move_iterator(other.storage_.GetInlinedData()), + std::make_move_iterator(other.storage_.GetInlinedData() + + other.size()), + storage_.GetInlinedData()); + storage_.SetInlinedSize(other.size()); } } @@ -227,26 +227,27 @@ class InlinedVector { InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept( absl::allocator_is_nothrow::value) : storage_(alloc) { - if (other.allocated()) { - if (alloc == other.allocator()) { + if (other.storage_.GetIsAllocated()) { + if (alloc == other.storage_.GetAllocator()) { // We can just steal the allocation from the source. - tag() = other.tag(); - init_allocation(other.allocation()); - other.tag() = Tag(); + storage_.SetAllocatedSize(other.size()); + storage_.InitAllocation(other.storage_.GetAllocation()); + other.storage_.SetInlinedSize(0); } else { // We need to use our own allocator reserve(other.size()); UninitializedCopy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()), - allocated_space()); - tag().set_allocated_size(other.size()); + storage_.GetAllocatedData()); + storage_.SetAllocatedSize(other.size()); } } else { UninitializedCopy( - std::make_move_iterator(other.inlined_space()), - std::make_move_iterator(other.inlined_space() + other.size()), - inlined_space()); - tag().set_inline_size(other.size()); + std::make_move_iterator(other.storage_.GetInlinedData()), + std::make_move_iterator(other.storage_.GetInlinedData() + + other.size()), + storage_.GetInlinedData()); + storage_.SetInlinedSize(other.size()); } } @@ -264,7 +265,7 @@ class InlinedVector { // `InlinedVector::size()` // // Returns the number of elements in the inlined vector. - size_type size() const noexcept { return tag().size(); } + size_type size() const noexcept { return storage_.GetSize(); } // `InlinedVector::max_size()` // @@ -286,7 +287,8 @@ class InlinedVector { // will no longer be inlined and `capacity()` will equal its capacity on the // allocated heap. size_type capacity() const noexcept { - return allocated() ? allocation().capacity() : static_cast(N); + return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity() + : static_cast(N); } // `InlinedVector::data()` @@ -295,14 +297,16 @@ class InlinedVector { // used to access and modify the contained elements. // Only results within the range [`0`, `size()`) are defined. pointer data() noexcept { - return allocated() ? allocated_space() : inlined_space(); + return storage_.GetIsAllocated() ? storage_.GetAllocatedData() + : storage_.GetInlinedData(); } // Overload of `InlinedVector::data()` to return a `const_pointer` to elements // of the inlined vector. This pointer can be used to access (but not modify) // the contained elements. const_pointer data() const noexcept { - return allocated() ? allocated_space() : inlined_space(); + return storage_.GetIsAllocated() ? storage_.GetAllocatedData() + : storage_.GetInlinedData(); } // `InlinedVector::operator[]()` @@ -436,7 +440,7 @@ class InlinedVector { // `InlinedVector::get_allocator()` // // Returns a copy of the allocator of the inlined vector. - allocator_type get_allocator() const { return allocator(); } + allocator_type get_allocator() const { return storage_.GetAllocator(); } // --------------------------------------------------------------------------- // InlinedVector Member Mutators @@ -477,13 +481,13 @@ class InlinedVector { InlinedVector& operator=(InlinedVector&& other) { if (ABSL_PREDICT_FALSE(this == std::addressof(other))) return *this; - if (other.allocated()) { + if (other.storage_.GetIsAllocated()) { clear(); - tag().set_allocated_size(other.size()); - init_allocation(other.allocation()); - other.tag() = Tag(); + storage_.SetAllocatedSize(other.size()); + storage_.InitAllocation(other.storage_.GetAllocation()); + other.storage_.SetInlinedSize(0); } else { - if (allocated()) clear(); + if (storage_.GetIsAllocated()) clear(); // Both are inlined now. if (size() < other.size()) { auto mid = std::make_move_iterator(other.begin() + size()); @@ -494,7 +498,7 @@ class InlinedVector { std::make_move_iterator(other.end()), begin()); Destroy(new_end, end()); } - tag().set_inline_size(other.size()); + storage_.SetInlinedSize(other.size()); } return *this; } @@ -511,12 +515,14 @@ class InlinedVector { // Grow reserve(n); std::fill_n(begin(), size(), v); - if (allocated()) { - UninitializedFill(allocated_space() + size(), allocated_space() + n, v); - tag().set_allocated_size(n); + if (storage_.GetIsAllocated()) { + UninitializedFill(storage_.GetAllocatedData() + size(), + storage_.GetAllocatedData() + n, v); + storage_.SetAllocatedSize(n); } else { - UninitializedFill(inlined_space() + size(), inlined_space() + n, v); - tag().set_inline_size(n); + UninitializedFill(storage_.GetInlinedData() + size(), + storage_.GetInlinedData() + n, v); + storage_.SetInlinedSize(n); } } @@ -564,12 +570,14 @@ class InlinedVector { assert(capacity() >= n); // Fill new space with elements constructed in-place. - if (allocated()) { - UninitializedFill(allocated_space() + s, allocated_space() + n); - tag().set_allocated_size(n); + if (storage_.GetIsAllocated()) { + UninitializedFill(storage_.GetAllocatedData() + s, + storage_.GetAllocatedData() + n); + storage_.SetAllocatedSize(n); } else { - UninitializedFill(inlined_space() + s, inlined_space() + n); - tag().set_inline_size(n); + UninitializedFill(storage_.GetInlinedData() + s, + storage_.GetInlinedData() + n); + storage_.SetInlinedSize(n); } } @@ -586,12 +594,14 @@ class InlinedVector { assert(capacity() >= n); // Fill new space with copies of `v`. - if (allocated()) { - UninitializedFill(allocated_space() + s, allocated_space() + n, v); - tag().set_allocated_size(n); + if (storage_.GetIsAllocated()) { + UninitializedFill(storage_.GetAllocatedData() + s, + storage_.GetAllocatedData() + n, v); + storage_.SetAllocatedSize(n); } else { - UninitializedFill(inlined_space() + s, inlined_space() + n, v); - tag().set_inline_size(n); + UninitializedFill(storage_.GetInlinedData() + s, + storage_.GetInlinedData() + n, v); + storage_.SetInlinedSize(n); } } @@ -688,12 +698,12 @@ class InlinedVector { return GrowAndEmplaceBack(std::forward(args)...); } pointer space; - if (allocated()) { - tag().set_allocated_size(s + 1); - space = allocated_space(); + if (storage_.GetIsAllocated()) { + storage_.SetAllocatedSize(s + 1); + space = storage_.GetAllocatedData(); } else { - tag().set_inline_size(s + 1); - space = inlined_space(); + storage_.SetInlinedSize(s + 1); + space = storage_.GetInlinedData(); } return Construct(space + s, std::forward(args)...); } @@ -716,12 +726,13 @@ class InlinedVector { void pop_back() noexcept { assert(!empty()); size_type s = size(); - if (allocated()) { - Destroy(allocated_space() + s - 1, allocated_space() + s); - tag().set_allocated_size(s - 1); + if (storage_.GetIsAllocated()) { + Destroy(storage_.GetAllocatedData() + s - 1, + storage_.GetAllocatedData() + s); + storage_.SetAllocatedSize(s - 1); } else { - Destroy(inlined_space() + s - 1, inlined_space() + s); - tag().set_inline_size(s - 1); + Destroy(storage_.GetInlinedData() + s - 1, storage_.GetInlinedData() + s); + storage_.SetInlinedSize(s - 1); } } @@ -757,12 +768,12 @@ class InlinedVector { ptrdiff_t erase_gap = std::distance(range_start, range_end); if (erase_gap > 0) { pointer space; - if (allocated()) { - space = allocated_space(); - tag().set_allocated_size(s - erase_gap); + if (storage_.GetIsAllocated()) { + space = storage_.GetAllocatedData(); + storage_.SetAllocatedSize(s - erase_gap); } else { - space = inlined_space(); - tag().set_inline_size(s - erase_gap); + space = storage_.GetInlinedData(); + storage_.SetInlinedSize(s - erase_gap); } std::move(range_end, space + s, range_start); Destroy(space + s - erase_gap, space + s); @@ -776,13 +787,13 @@ class InlinedVector { // deallocates the heap allocation if the inlined vector was allocated. void clear() noexcept { size_type s = size(); - if (allocated()) { - Destroy(allocated_space(), allocated_space() + s); - allocation().Dealloc(allocator()); + if (storage_.GetIsAllocated()) { + Destroy(storage_.GetAllocatedData(), storage_.GetAllocatedData() + s); + storage_.GetAllocation().Dealloc(storage_.GetAllocator()); } else if (s != 0) { // do nothing for empty vectors - Destroy(inlined_space(), inlined_space() + s); + Destroy(storage_.GetInlinedData(), storage_.GetInlinedData() + s); } - tag() = Tag(); + storage_.SetInlinedSize(0); } // `InlinedVector::reserve()` @@ -814,7 +825,8 @@ class InlinedVector { // smaller heap allocation. void shrink_to_fit() { const auto s = size(); - if (ABSL_PREDICT_FALSE(!allocated() || s == capacity())) return; + if (ABSL_PREDICT_FALSE(!storage_.GetIsAllocated() || s == capacity())) + return; if (s <= N) { // Move the elements to the inlined storage. @@ -829,9 +841,9 @@ class InlinedVector { // Reallocate storage and move elements. // We can't simply use the same approach as above, because `assign()` would // call into `reserve()` internally and reserve larger capacity than we need - Allocation new_allocation(allocator(), s); - UninitializedCopy(std::make_move_iterator(allocated_space()), - std::make_move_iterator(allocated_space() + s), + Allocation new_allocation(storage_.GetAllocator(), s); + UninitializedCopy(std::make_move_iterator(storage_.GetAllocatedData()), + std::make_move_iterator(storage_.GetAllocatedData() + s), new_allocation.buffer()); ResetAllocation(new_allocation, s); } @@ -849,67 +861,24 @@ class InlinedVector { template friend H AbslHashValue(H h, const absl::InlinedVector& a); - const Tag& tag() const { return storage_.allocator_and_tag_.tag(); } - - Tag& tag() { return storage_.allocator_and_tag_.tag(); } - - Allocation& allocation() { - return reinterpret_cast( - storage_.rep_.allocation_storage.allocation); - } - - const Allocation& allocation() const { - return reinterpret_cast( - storage_.rep_.allocation_storage.allocation); - } - - void init_allocation(const Allocation& allocation) { - new (static_cast(std::addressof( - storage_.rep_.allocation_storage.allocation))) Allocation(allocation); - } - - // TODO(absl-team): investigate whether the reinterpret_cast is appropriate. - pointer inlined_space() { - return reinterpret_cast( - std::addressof(storage_.rep_.inlined_storage.inlined[0])); - } - - const_pointer inlined_space() const { - return reinterpret_cast( - std::addressof(storage_.rep_.inlined_storage.inlined[0])); - } - - pointer allocated_space() { return allocation().buffer(); } - - const_pointer allocated_space() const { return allocation().buffer(); } - - const allocator_type& allocator() const { - return storage_.allocator_and_tag_.allocator(); - } - - allocator_type& allocator() { - return storage_.allocator_and_tag_.allocator(); - } - - bool allocated() const { return tag().allocated(); } - void ResetAllocation(Allocation new_allocation, size_type new_size) { - if (allocated()) { - Destroy(allocated_space(), allocated_space() + size()); - assert(begin() == allocated_space()); - allocation().Dealloc(allocator()); - allocation() = new_allocation; + if (storage_.GetIsAllocated()) { + Destroy(storage_.GetAllocatedData(), + storage_.GetAllocatedData() + size()); + assert(begin() == storage_.GetAllocatedData()); + storage_.GetAllocation().Dealloc(storage_.GetAllocator()); + storage_.GetAllocation() = new_allocation; } else { - Destroy(inlined_space(), inlined_space() + size()); - init_allocation(new_allocation); // bug: only init once + Destroy(storage_.GetInlinedData(), storage_.GetInlinedData() + size()); + storage_.InitAllocation(new_allocation); // bug: only init once } - tag().set_allocated_size(new_size); + storage_.SetAllocatedSize(new_size); } template reference Construct(pointer p, Args&&... args) { std::allocator_traits::construct( - allocator(), p, std::forward(args)...); + storage_.GetAllocator(), p, std::forward(args)...); return *p; } @@ -926,7 +895,8 @@ class InlinedVector { // Destroy [`from`, `to`) in place. void Destroy(pointer from, pointer to) { for (pointer cur = from; cur != to; ++cur) { - std::allocator_traits::destroy(allocator(), cur); + std::allocator_traits::destroy(storage_.GetAllocator(), + cur); } #if !defined(NDEBUG) // Overwrite unused memory with `0xab` so we can catch uninitialized usage. @@ -946,7 +916,7 @@ class InlinedVector { const size_type s = size(); assert(s <= capacity()); - size_type target = (std::max)(N, s + delta); + size_type target = (std::max)(static_cast(N), s + delta); // Compute new capacity by repeatedly doubling current capacity // TODO(psrc): Check and avoid overflow? @@ -955,7 +925,7 @@ class InlinedVector { new_capacity <<= 1; } - Allocation new_allocation(allocator(), new_capacity); + Allocation new_allocation(storage_.GetAllocator(), new_capacity); UninitializedCopy(std::make_move_iterator(data()), std::make_move_iterator(data() + s), @@ -987,7 +957,7 @@ class InlinedVector { } // Move everyone into the new allocation, leaving a gap of `n` for the // requested shift. - Allocation new_allocation(allocator(), new_capacity); + Allocation new_allocation(storage_.GetAllocator(), new_capacity); size_type index = position - begin(); UninitializedCopy(std::make_move_iterator(data()), std::make_move_iterator(data() + index), @@ -1026,7 +996,7 @@ class InlinedVector { start_used = pos; start_raw = pos + new_elements_in_used_space; } - tag().add_size(n); + storage_.AddSize(n); return std::make_pair(start_used, start_raw); } @@ -1035,7 +1005,7 @@ class InlinedVector { assert(size() == capacity()); const size_type s = size(); - Allocation new_allocation(allocator(), 2 * capacity()); + Allocation new_allocation(storage_.GetAllocator(), 2 * capacity()); reference new_element = Construct(new_allocation.buffer() + s, std::forward(args)...); @@ -1049,26 +1019,30 @@ class InlinedVector { } void InitAssign(size_type n) { - if (n > N) { - Allocation new_allocation(allocator(), n); - init_allocation(new_allocation); - UninitializedFill(allocated_space(), allocated_space() + n); - tag().set_allocated_size(n); + if (n > static_cast(N)) { + Allocation new_allocation(storage_.GetAllocator(), n); + storage_.InitAllocation(new_allocation); + UninitializedFill(storage_.GetAllocatedData(), + storage_.GetAllocatedData() + n); + storage_.SetAllocatedSize(n); } else { - UninitializedFill(inlined_space(), inlined_space() + n); - tag().set_inline_size(n); + UninitializedFill(storage_.GetInlinedData(), + storage_.GetInlinedData() + n); + storage_.SetInlinedSize(n); } } void InitAssign(size_type n, const_reference v) { - if (n > N) { - Allocation new_allocation(allocator(), n); - init_allocation(new_allocation); - UninitializedFill(allocated_space(), allocated_space() + n, v); - tag().set_allocated_size(n); + if (n > static_cast(N)) { + Allocation new_allocation(storage_.GetAllocator(), n); + storage_.InitAllocation(new_allocation); + UninitializedFill(storage_.GetAllocatedData(), + storage_.GetAllocatedData() + n, v); + storage_.SetAllocatedSize(n); } else { - UninitializedFill(inlined_space(), inlined_space() + n, v); - tag().set_inline_size(n); + UninitializedFill(storage_.GetInlinedData(), + storage_.GetInlinedData() + n, v); + storage_.SetInlinedSize(n); } } @@ -1087,12 +1061,12 @@ class InlinedVector { reserve(length); iterator out = begin(); for (; out != end(); ++first, ++out) *out = *first; - if (allocated()) { + if (storage_.GetIsAllocated()) { UninitializedCopy(first, last, out); - tag().set_allocated_size(length); + storage_.SetAllocatedSize(length); } else { UninitializedCopy(first, last, out); - tag().set_inline_size(length); + storage_.SetInlinedSize(length); } } @@ -1102,12 +1076,12 @@ class InlinedVector { auto length = std::distance(first, last); reserve(size() + length); - if (allocated()) { - UninitializedCopy(first, last, allocated_space() + size()); - tag().set_allocated_size(size() + length); + if (storage_.GetIsAllocated()) { + UninitializedCopy(first, last, storage_.GetAllocatedData() + size()); + storage_.SetAllocatedSize(size() + length); } else { - UninitializedCopy(first, last, inlined_space() + size()); - tag().set_inline_size(size() + length); + UninitializedCopy(first, last, storage_.GetInlinedData() + size()); + storage_.SetInlinedSize(size() + length); } } @@ -1145,14 +1119,19 @@ class InlinedVector { void SwapImpl(InlinedVector& other) { using std::swap; // Augment ADL with `std::swap`. - if (allocated() && other.allocated()) { + bool is_allocated = storage_.GetIsAllocated(); + bool other_is_allocated = other.storage_.GetIsAllocated(); + + if (is_allocated && other_is_allocated) { // Both out of line, so just swap the tag, allocation, and allocator. - swap(tag(), other.tag()); - swap(allocation(), other.allocation()); - swap(allocator(), other.allocator()); + storage_.SwapSizeAndIsAllocated(other.storage_); + swap(storage_.GetAllocation(), other.storage_.GetAllocation()); + swap(storage_.GetAllocator(), other.storage_.GetAllocator()); + return; } - if (!allocated() && !other.allocated()) { + + if (!is_allocated && !other_is_allocated) { // Both inlined: swap up to smaller size, then move remaining elements. InlinedVector* a = this; InlinedVector* b = std::addressof(other); @@ -1164,18 +1143,21 @@ class InlinedVector { const size_type b_size = b->size(); assert(a_size >= b_size); // `a` is larger. Swap the elements up to the smaller array size. - std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size, - b->inlined_space()); + std::swap_ranges(a->storage_.GetInlinedData(), + a->storage_.GetInlinedData() + b_size, + b->storage_.GetInlinedData()); // Move the remaining elements: // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b` - b->UninitializedCopy(a->inlined_space() + b_size, - a->inlined_space() + a_size, - b->inlined_space() + b_size); - a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size); + b->UninitializedCopy(a->storage_.GetInlinedData() + b_size, + a->storage_.GetInlinedData() + a_size, + b->storage_.GetInlinedData() + b_size); + a->Destroy(a->storage_.GetInlinedData() + b_size, + a->storage_.GetInlinedData() + a_size); + + storage_.SwapSizeAndIsAllocated(other.storage_); + swap(storage_.GetAllocator(), other.storage_.GetAllocator()); - swap(a->tag(), b->tag()); - swap(a->allocator(), b->allocator()); assert(b->size() == a_size); assert(a->size() == b_size); return; @@ -1188,31 +1170,35 @@ class InlinedVector { // the tags. InlinedVector* a = this; InlinedVector* b = std::addressof(other); - if (a->allocated()) { + if (a->storage_.GetIsAllocated()) { swap(a, b); } - assert(!a->allocated()); - assert(b->allocated()); + + assert(!a->storage_.GetIsAllocated()); + assert(b->storage_.GetIsAllocated()); + const size_type a_size = a->size(); const size_type b_size = b->size(); // In an optimized build, `b_size` would be unused. static_cast(b_size); - // Made Local copies of `size()`, don't need `tag()` accurate anymore - swap(a->tag(), b->tag()); + // Made Local copies of `size()`, these can now be swapped + a->storage_.SwapSizeAndIsAllocated(b->storage_); // Copy `b_allocation` out before `b`'s union gets clobbered by // `inline_space` - Allocation b_allocation = b->allocation(); + Allocation b_allocation = b->storage_.GetAllocation(); - b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size, - b->inlined_space()); - a->Destroy(a->inlined_space(), a->inlined_space() + a_size); + b->UninitializedCopy(a->storage_.GetInlinedData(), + a->storage_.GetInlinedData() + a_size, + b->storage_.GetInlinedData()); + a->Destroy(a->storage_.GetInlinedData(), + a->storage_.GetInlinedData() + a_size); - a->allocation() = b_allocation; + a->storage_.GetAllocation() = b_allocation; - if (a->allocator() != b->allocator()) { - swap(a->allocator(), b->allocator()); + if (a->storage_.GetAllocator() != b->storage_.GetAllocator()) { + swap(a->storage_.GetAllocator(), b->storage_.GetAllocator()); } assert(b->size() == a_size); diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index 24059d94..7aa05b6a 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -18,7 +18,9 @@ #include #include #include +#include +#include "absl/container/internal/compressed_tuple.h" #include "absl/meta/type_traits.h" namespace absl { @@ -31,6 +33,8 @@ template