diff options
author | 2019-04-04 08:13:57 -0700 | |
---|---|---|
committer | 2019-04-04 16:07:58 -0400 | |
commit | 666fc1266bccfd8e6eaaa084e7b42580bb8eb199 (patch) | |
tree | 9a9366d8846fb3905f3f224d0e90b9de9d5f730b | |
parent | 93dfcf74cb5fccae3da07897d8613ae6cab958a0 (diff) |
Export of internal Abseil changes.
--
bc89d3221e3927d08881d75eeee0e8db862300fa by Benjamin Barenblat <bbaren@google.com>:
Clean up C-style casts in `ABSL_ASSERT`
PiperOrigin-RevId: 241932756
--
17482daae4b3e2fc725b759586590ac466b72a1e by Jon Cohen <cohenjon@google.com>:
Move Gtest-specific CMake code to its own directory
PiperOrigin-RevId: 241920192
--
9ae52b4f665625352c0a789cff884bde492c28f5 by CJ Johnson <johnsoncj@google.com>:
Moves private data methods from InlinedVector to InlinedVector Storage in anticipation of migrating the Rep union type
PiperOrigin-RevId: 241794144
--
95315bc50a61a0aae4f171b44c2312158a43e72e by Jon Cohen <cohenjon@google.com>:
Use /DNOMINMAX in Abseil tests. This offsets inlcudes of <windows.h> from gtest.
PiperOrigin-RevId: 241790584
--
ee505c7f2ab99d29c165ea21a07190474f64053d by CJ Johnson <johnsoncj@google.com>:
Adds inlined_vector_internal to the deps of inlined_vector in CMakeLists.txt
PiperOrigin-RevId: 241775332
--
94eb5165b49bab59ce7de143be38a4581d5658da by CJ Johnson <johnsoncj@google.com>:
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 <absl-team@google.com>:
Add MSVC specific linker flags only to MSVC builds.
PiperOrigin-RevId: 241615711
--
3ad19d2779281e945bdf56643dc5cee3f730eb4f by Abseil Team <absl-team@google.com>:
Add a comment about per-process randomization of absl::Hash.
PiperOrigin-RevId: 241583697
--
8dfb02d725fee3528351b2da4ed32a7455f9858a by Tom Manshreck <shreck@google.com>:
Internal change
PiperOrigin-RevId: 241564734
GitOrigin-RevId: bc89d3221e3927d08881d75eeee0e8db862300fa
Change-Id: Ibad3da416d08a96ec1f8313f8b519b4270b7e01a
-rw-r--r-- | CMake/Googletest/CMakeLists.txt.in (renamed from CMake/CMakeLists.txt.in) | 0 | ||||
-rw-r--r-- | CMake/Googletest/DownloadGTest.cmake (renamed from CMake/DownloadGTest.cmake) | 0 | ||||
-rw-r--r-- | CMakeLists.txt | 2 | ||||
-rw-r--r-- | absl/base/macros.h | 7 | ||||
-rw-r--r-- | absl/container/BUILD.bazel | 1 | ||||
-rw-r--r-- | absl/container/CMakeLists.txt | 2 | ||||
-rw-r--r-- | absl/container/inlined_vector.h | 354 | ||||
-rw-r--r-- | absl/container/internal/inlined_vector.h | 90 | ||||
-rw-r--r-- | absl/copts/AbseilConfigureCopts.cmake | 2 | ||||
-rw-r--r-- | absl/copts/GENERATED_AbseilCopts.cmake | 1 | ||||
-rw-r--r-- | absl/copts/GENERATED_copts.bzl | 1 | ||||
-rw-r--r-- | absl/copts/copts.py | 1 | ||||
-rw-r--r-- | absl/hash/hash.h | 4 | ||||
-rw-r--r-- | absl/types/BUILD.bazel | 1 | ||||
-rw-r--r-- | absl/types/CMakeLists.txt | 2 | ||||
-rw-r--r-- | absl/types/internal/optional.h | 364 | ||||
-rw-r--r-- | absl/types/optional.h | 375 |
17 files changed, 634 insertions, 573 deletions
diff --git a/CMake/CMakeLists.txt.in b/CMake/Googletest/CMakeLists.txt.in index d60a33e9..d60a33e9 100644 --- a/CMake/CMakeLists.txt.in +++ b/CMake/Googletest/CMakeLists.txt.in diff --git a/CMake/DownloadGTest.cmake b/CMake/Googletest/DownloadGTest.cmake index 3c682aef..3c682aef 100644 --- a/CMake/DownloadGTest.cmake +++ b/CMake/Googletest/DownloadGTest.cmake 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<void>(expr) : static_cast<void>(0)) #else -#define ABSL_ASSERT(expr) \ - (ABSL_PREDICT_TRUE((expr)) ? (void)0 \ +#define ABSL_ASSERT(expr) \ + (ABSL_PREDICT_TRUE((expr)) ? static_cast<void>(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<InlinedVector>; - using Tag = typename Storage::Tag; - using AllocatorAndTag = typename Storage::AllocatorAndTag; using Allocation = typename Storage::Allocation; template <typename Iterator> @@ -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<allocator_type>::value || std::is_nothrow_move_constructible<value_type>::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<allocator_type>::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<size_type>(N); + return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity() + : static_cast<size_type>(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>(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>(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 <typename H, typename TheT, size_t TheN, typename TheA> friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a); - const Tag& tag() const { return storage_.allocator_and_tag_.tag(); } - - Tag& tag() { return storage_.allocator_and_tag_.tag(); } - - Allocation& allocation() { - return reinterpret_cast<Allocation&>( - storage_.rep_.allocation_storage.allocation); - } - - const Allocation& allocation() const { - return reinterpret_cast<const Allocation&>( - storage_.rep_.allocation_storage.allocation); - } - - void init_allocation(const Allocation& allocation) { - new (static_cast<void*>(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<pointer>( - std::addressof(storage_.rep_.inlined_storage.inlined[0])); - } - - const_pointer inlined_space() const { - return reinterpret_cast<const_pointer>( - 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 <typename... Args> reference Construct(pointer p, Args&&... args) { std::allocator_traits<allocator_type>::construct( - allocator(), p, std::forward<Args>(args)...); + storage_.GetAllocator(), p, std::forward<Args>(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<allocator_type>::destroy(allocator(), cur); + std::allocator_traits<allocator_type>::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<size_type>(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>(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<size_type>(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<size_type>(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<void>(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 <cstddef> #include <iterator> #include <memory> +#include <utility> +#include "absl/container/internal/compressed_tuple.h" #include "absl/meta/type_traits.h" namespace absl { @@ -31,6 +33,8 @@ template <template <typename, size_t, typename> class InlinedVector, typename T, size_t N, typename A> class Storage<InlinedVector<T, N, A>> { public: + class Allocation; // TODO(johnsoncj): Remove after migration + using allocator_type = A; using value_type = typename allocator_type::value_type; using pointer = typename allocator_type::pointer; @@ -45,38 +49,63 @@ class Storage<InlinedVector<T, N, A>> { using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; - explicit Storage(const allocator_type& a) : allocator_and_tag_(a) {} + explicit Storage(const allocator_type& alloc) + : metadata_(alloc, /* empty and inlined */ 0) {} - // TODO(johnsoncj): Make the below types and members private after migration + size_type GetSize() const { return GetSizeAndIsAllocated() >> 1; } - // Holds whether the vector is allocated or not in the lowest bit and the size - // in the high bits: - // `size_ = (size << 1) | is_allocated;` - class Tag { - size_type size_; + bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; } - public: - Tag() : size_(0) {} - size_type size() const { return size_ / 2; } - void add_size(size_type n) { size_ += n * 2; } - void set_inline_size(size_type n) { size_ = n * 2; } - void set_allocated_size(size_type n) { size_ = (n * 2) + 1; } - bool allocated() const { return size_ % 2; } - }; + Allocation& GetAllocation() { + return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation); + } - // Derives from `allocator_type` to use the empty base class optimization. - // If the `allocator_type` is stateless, we can store our instance for free. - class AllocatorAndTag : private allocator_type { - Tag tag_; + const Allocation& GetAllocation() const { + return reinterpret_cast<const Allocation&>( + rep_.allocation_storage.allocation); + } - public: - explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {} - Tag& tag() { return tag_; } - const Tag& tag() const { return tag_; } - allocator_type& allocator() { return *this; } - const allocator_type& allocator() const { return *this; } - }; + pointer GetInlinedData() { + return reinterpret_cast<pointer>( + std::addressof(rep_.inlined_storage.inlined[0])); + } + + const_pointer GetInlinedData() const { + return reinterpret_cast<const_pointer>( + std::addressof(rep_.inlined_storage.inlined[0])); + } + + pointer GetAllocatedData() { return GetAllocation().buffer(); } + + const_pointer GetAllocatedData() const { return GetAllocation().buffer(); } + + size_type GetAllocatedCapacity() const { return GetAllocation().capacity(); } + allocator_type& GetAllocator() { return metadata_.template get<0>(); } + + const allocator_type& GetAllocator() const { + return metadata_.template get<0>(); + } + + void SetAllocatedSize(size_type size) { + GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1); + } + + void SetInlinedSize(size_type size) { GetSizeAndIsAllocated() = size << 1; } + + void AddSize(size_type count) { GetSizeAndIsAllocated() += count << 1; } + + void InitAllocation(const Allocation& allocation) { + new (static_cast<void*>(std::addressof(rep_.allocation_storage.allocation))) + Allocation(allocation); + } + + void SwapSizeAndIsAllocated(Storage& other) { + using std::swap; + swap(GetSizeAndIsAllocated(), other.GetSizeAndIsAllocated()); + } + + // TODO(johnsoncj): Make the below types private after migration class Allocation { size_type capacity_; pointer buffer_; @@ -95,6 +124,13 @@ class Storage<InlinedVector<T, N, A>> { } }; + private: + size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); } + + const size_type& GetSizeAndIsAllocated() const { + return metadata_.template get<1>(); + } + // Stores either the inlined or allocated representation union Rep { using ValueTypeBuffer = @@ -116,7 +152,7 @@ class Storage<InlinedVector<T, N, A>> { AllocatedRep allocation_storage; }; - AllocatorAndTag allocator_and_tag_; + container_internal::CompressedTuple<allocator_type, size_type> metadata_; Rep rep_; }; diff --git a/absl/copts/AbseilConfigureCopts.cmake b/absl/copts/AbseilConfigureCopts.cmake index ae29d9e9..eaef30b0 100644 --- a/absl/copts/AbseilConfigureCopts.cmake +++ b/absl/copts/AbseilConfigureCopts.cmake @@ -16,11 +16,11 @@ elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") set(ABSL_DEFAULT_COPTS "${ABSL_CLANG_CL_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_CLANG_CL_FLAGS};${ABSL_CLANG_CL_TEST_FLAGS}") set(ABSL_EXCEPTIONS_FLAG "${ABSL_CLANG_CL_EXCEPTIONS_FLAGS}") + set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}") else() set(ABSL_DEFAULT_COPTS "${ABSL_LLVM_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_LLVM_FLAGS};${ABSL_LLVM_TEST_FLAGS}") set(ABSL_EXCEPTIONS_FLAG "${ABSL_LLVM_EXCEPTIONS_FLAGS}") - set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}") if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang") # AppleClang doesn't have lsan # https://developer.apple.com/documentation/code_diagnostics diff --git a/absl/copts/GENERATED_AbseilCopts.cmake b/absl/copts/GENERATED_AbseilCopts.cmake index 16cf9fea..cf38ec12 100644 --- a/absl/copts/GENERATED_AbseilCopts.cmake +++ b/absl/copts/GENERATED_AbseilCopts.cmake @@ -211,4 +211,5 @@ list(APPEND ABSL_MSVC_TEST_FLAGS "/wd4018" "/wd4101" "/wd4503" + "/DNOMINMAX" ) diff --git a/absl/copts/GENERATED_copts.bzl b/absl/copts/GENERATED_copts.bzl index 0669c724..52e1a949 100644 --- a/absl/copts/GENERATED_copts.bzl +++ b/absl/copts/GENERATED_copts.bzl @@ -212,4 +212,5 @@ ABSL_MSVC_TEST_FLAGS = [ "/wd4018", "/wd4101", "/wd4503", + "/DNOMINMAX", ] diff --git a/absl/copts/copts.py b/absl/copts/copts.py index cd568906..880ff991 100644 --- a/absl/copts/copts.py +++ b/absl/copts/copts.py @@ -183,6 +183,7 @@ COPT_VARS = { "/wd4018", # signed/unsigned mismatch "/wd4101", # unreferenced local variable "/wd4503", # decorated name length exceeded, name was truncated + "/DNOMINMAX", # disable the min() and max() macros from <windows.h> ], "ABSL_MSVC_EXCEPTIONS_FLAGS": MSVC_STYLE_EXCEPTIONS_FLAGS, diff --git a/absl/hash/hash.h b/absl/hash/hash.h index c0ede35a..339b685f 100644 --- a/absl/hash/hash.h +++ b/absl/hash/hash.h @@ -36,6 +36,10 @@ // framework by simply combining its state with the state of known, hashable // types. Hashing of that combined state is separately done by `absl::Hash`. // +// One should assume that a hash algorithm is chosen randomly at the start of +// each process. E.g., absl::Hash<int>()(9) in one process and +// absl::Hash<int>()(9) in another process are likely to differ. +// // Example: // // // Suppose we have a class `Circle` for which we want to add hashing diff --git a/absl/types/BUILD.bazel b/absl/types/BUILD.bazel index feac34b1..a2548718 100644 --- a/absl/types/BUILD.bazel +++ b/absl/types/BUILD.bazel @@ -173,6 +173,7 @@ cc_test( cc_library( name = "optional", + srcs = ["internal/optional.h"], hdrs = ["optional.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/types/CMakeLists.txt b/absl/types/CMakeLists.txt index 56f9fffd..9da94eb5 100644 --- a/absl/types/CMakeLists.txt +++ b/absl/types/CMakeLists.txt @@ -174,6 +174,8 @@ absl_cc_library( optional HDRS "optional.h" + SRCS + "internal/optional.h" COPTS ${ABSL_DEFAULT_COPTS} DEPS diff --git a/absl/types/internal/optional.h b/absl/types/internal/optional.h new file mode 100644 index 00000000..562c84ef --- /dev/null +++ b/absl/types/internal/optional.h @@ -0,0 +1,364 @@ +// Copyright 2017 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. +// +#ifndef ABSL_TYPES_INTERNAL_OPTIONAL_H_ +#define ABSL_TYPES_INTERNAL_OPTIONAL_H_ + +#include <functional> +#include <new> +#include <type_traits> +#include <utility> + +#include "absl/base/internal/inline_variable.h" +#include "absl/memory/memory.h" +#include "absl/meta/type_traits.h" +#include "absl/utility/utility.h" + +namespace absl { + +// Forward declaration +template <typename T> +class optional; + +namespace optional_internal { + +// This tag type is used as a constructor parameter type for `nullopt_t`. +struct init_t { + explicit init_t() = default; +}; + +struct empty_struct {}; + +// This class stores the data in optional<T>. +// It is specialized based on whether T is trivially destructible. +// This is the specialization for non trivially destructible type. +template <typename T, bool unused = std::is_trivially_destructible<T>::value> +class optional_data_dtor_base { + struct dummy_type { + static_assert(sizeof(T) % sizeof(empty_struct) == 0, ""); + // Use an array to avoid GCC 6 placement-new warning. + empty_struct data[sizeof(T) / sizeof(empty_struct)]; + }; + + protected: + // Whether there is data or not. + bool engaged_; + // Data storage + union { + dummy_type dummy_; + T data_; + }; + + void destruct() noexcept { + if (engaged_) { + data_.~T(); + engaged_ = false; + } + } + + // dummy_ must be initialized for constexpr constructor. + constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {} + + template <typename... Args> + constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args) + : engaged_(true), data_(absl::forward<Args>(args)...) {} + + ~optional_data_dtor_base() { destruct(); } +}; + +// Specialization for trivially destructible type. +template <typename T> +class optional_data_dtor_base<T, true> { + struct dummy_type { + static_assert(sizeof(T) % sizeof(empty_struct) == 0, ""); + // Use array to avoid GCC 6 placement-new warning. + empty_struct data[sizeof(T) / sizeof(empty_struct)]; + }; + + protected: + // Whether there is data or not. + bool engaged_; + // Data storage + union { + dummy_type dummy_; + T data_; + }; + void destruct() noexcept { engaged_ = false; } + + // dummy_ must be initialized for constexpr constructor. + constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {} + + template <typename... Args> + constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args) + : engaged_(true), data_(absl::forward<Args>(args)...) {} +}; + +template <typename T> +class optional_data_base : public optional_data_dtor_base<T> { + protected: + using base = optional_data_dtor_base<T>; +#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS + using base::base; +#else + optional_data_base() = default; + + template <typename... Args> + constexpr explicit optional_data_base(in_place_t t, Args&&... args) + : base(t, absl::forward<Args>(args)...) {} +#endif + + template <typename... Args> + void construct(Args&&... args) { + // Use dummy_'s address to work around casting cv-qualified T* to void*. + ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...); + this->engaged_ = true; + } + + template <typename U> + void assign(U&& u) { + if (this->engaged_) { + this->data_ = std::forward<U>(u); + } else { + construct(std::forward<U>(u)); + } + } +}; + +// TODO(absl-team): Add another class using +// std::is_trivially_move_constructible trait when available to match +// http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that +// have trivial move but nontrivial copy. +// Also, we should be checking is_trivially_copyable here, which is not +// supported now, so we use is_trivially_* traits instead. +template <typename T, + bool unused = absl::is_trivially_copy_constructible<T>::value&& + absl::is_trivially_copy_assignable<typename std::remove_cv< + T>::type>::value&& std::is_trivially_destructible<T>::value> +class optional_data; + +// Trivially copyable types +template <typename T> +class optional_data<T, true> : public optional_data_base<T> { + protected: +#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS + using optional_data_base<T>::optional_data_base; +#else + optional_data() = default; + + template <typename... Args> + constexpr explicit optional_data(in_place_t t, Args&&... args) + : optional_data_base<T>(t, absl::forward<Args>(args)...) {} +#endif +}; + +template <typename T> +class optional_data<T, false> : public optional_data_base<T> { + protected: +#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS + using optional_data_base<T>::optional_data_base; +#else + template <typename... Args> + constexpr explicit optional_data(in_place_t t, Args&&... args) + : optional_data_base<T>(t, absl::forward<Args>(args)...) {} +#endif + + optional_data() = default; + + optional_data(const optional_data& rhs) : optional_data_base<T>() { + if (rhs.engaged_) { + this->construct(rhs.data_); + } + } + + optional_data(optional_data&& rhs) noexcept( + absl::default_allocator_is_nothrow::value || + std::is_nothrow_move_constructible<T>::value) + : optional_data_base<T>() { + if (rhs.engaged_) { + this->construct(std::move(rhs.data_)); + } + } + + optional_data& operator=(const optional_data& rhs) { + if (rhs.engaged_) { + this->assign(rhs.data_); + } else { + this->destruct(); + } + return *this; + } + + optional_data& operator=(optional_data&& rhs) noexcept( + std::is_nothrow_move_assignable<T>::value&& + std::is_nothrow_move_constructible<T>::value) { + if (rhs.engaged_) { + this->assign(std::move(rhs.data_)); + } else { + this->destruct(); + } + return *this; + } +}; + +// Ordered by level of restriction, from low to high. +// Copyable implies movable. +enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 }; + +// Base class for enabling/disabling copy/move constructor. +template <copy_traits> +class optional_ctor_base; + +template <> +class optional_ctor_base<copy_traits::copyable> { + public: + constexpr optional_ctor_base() = default; + optional_ctor_base(const optional_ctor_base&) = default; + optional_ctor_base(optional_ctor_base&&) = default; + optional_ctor_base& operator=(const optional_ctor_base&) = default; + optional_ctor_base& operator=(optional_ctor_base&&) = default; +}; + +template <> +class optional_ctor_base<copy_traits::movable> { + public: + constexpr optional_ctor_base() = default; + optional_ctor_base(const optional_ctor_base&) = delete; + optional_ctor_base(optional_ctor_base&&) = default; + optional_ctor_base& operator=(const optional_ctor_base&) = default; + optional_ctor_base& operator=(optional_ctor_base&&) = default; +}; + +template <> +class optional_ctor_base<copy_traits::non_movable> { + public: + constexpr optional_ctor_base() = default; + optional_ctor_base(const optional_ctor_base&) = delete; + optional_ctor_base(optional_ctor_base&&) = delete; + optional_ctor_base& operator=(const optional_ctor_base&) = default; + optional_ctor_base& operator=(optional_ctor_base&&) = default; +}; + +// Base class for enabling/disabling copy/move assignment. +template <copy_traits> +class optional_assign_base; + +template <> +class optional_assign_base<copy_traits::copyable> { + public: + constexpr optional_assign_base() = default; + optional_assign_base(const optional_assign_base&) = default; + optional_assign_base(optional_assign_base&&) = default; + optional_assign_base& operator=(const optional_assign_base&) = default; + optional_assign_base& operator=(optional_assign_base&&) = default; +}; + +template <> +class optional_assign_base<copy_traits::movable> { + public: + constexpr optional_assign_base() = default; + optional_assign_base(const optional_assign_base&) = default; + optional_assign_base(optional_assign_base&&) = default; + optional_assign_base& operator=(const optional_assign_base&) = delete; + optional_assign_base& operator=(optional_assign_base&&) = default; +}; + +template <> +class optional_assign_base<copy_traits::non_movable> { + public: + constexpr optional_assign_base() = default; + optional_assign_base(const optional_assign_base&) = default; + optional_assign_base(optional_assign_base&&) = default; + optional_assign_base& operator=(const optional_assign_base&) = delete; + optional_assign_base& operator=(optional_assign_base&&) = delete; +}; + +template <typename T> +struct ctor_copy_traits { + static constexpr copy_traits traits = + std::is_copy_constructible<T>::value + ? copy_traits::copyable + : std::is_move_constructible<T>::value ? copy_traits::movable + : copy_traits::non_movable; +}; + +template <typename T> +struct assign_copy_traits { + static constexpr copy_traits traits = + absl::is_copy_assignable<T>::value && std::is_copy_constructible<T>::value + ? copy_traits::copyable + : absl::is_move_assignable<T>::value && + std::is_move_constructible<T>::value + ? copy_traits::movable + : copy_traits::non_movable; +}; + +// Whether T is constructible or convertible from optional<U>. +template <typename T, typename U> +struct is_constructible_convertible_from_optional + : std::integral_constant< + bool, std::is_constructible<T, optional<U>&>::value || + std::is_constructible<T, optional<U>&&>::value || + std::is_constructible<T, const optional<U>&>::value || + std::is_constructible<T, const optional<U>&&>::value || + std::is_convertible<optional<U>&, T>::value || + std::is_convertible<optional<U>&&, T>::value || + std::is_convertible<const optional<U>&, T>::value || + std::is_convertible<const optional<U>&&, T>::value> {}; + +// Whether T is constructible or convertible or assignable from optional<U>. +template <typename T, typename U> +struct is_constructible_convertible_assignable_from_optional + : std::integral_constant< + bool, is_constructible_convertible_from_optional<T, U>::value || + std::is_assignable<T&, optional<U>&>::value || + std::is_assignable<T&, optional<U>&&>::value || + std::is_assignable<T&, const optional<U>&>::value || + std::is_assignable<T&, const optional<U>&&>::value> {}; + +// Helper function used by [optional.relops], [optional.comp_with_t], +// for checking whether an expression is convertible to bool. +bool convertible_to_bool(bool); + +// Base class for std::hash<absl::optional<T>>: +// If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to +// compute the hash; Otherwise, it is disabled. +// Reference N4659 23.14.15 [unord.hash]. +template <typename T, typename = size_t> +struct optional_hash_base { + optional_hash_base() = delete; + optional_hash_base(const optional_hash_base&) = delete; + optional_hash_base(optional_hash_base&&) = delete; + optional_hash_base& operator=(const optional_hash_base&) = delete; + optional_hash_base& operator=(optional_hash_base&&) = delete; +}; + +template <typename T> +struct optional_hash_base<T, decltype(std::hash<absl::remove_const_t<T> >()( + std::declval<absl::remove_const_t<T> >()))> { + using argument_type = absl::optional<T>; + using result_type = size_t; + size_t operator()(const absl::optional<T>& opt) const { + absl::type_traits_internal::AssertHashEnabled<absl::remove_const_t<T>>(); + if (opt) { + return std::hash<absl::remove_const_t<T> >()(*opt); + } else { + return static_cast<size_t>(0x297814aaad196e6dULL); + } + } +}; + +} // namespace optional_internal +} // namespace absl + +#endif // ABSL_TYPES_INTERNAL_OPTIONAL_H_ diff --git a/absl/types/optional.h b/absl/types/optional.h index 6806160d..17f78984 100644 --- a/absl/types/optional.h +++ b/absl/types/optional.h @@ -35,8 +35,7 @@ #ifndef ABSL_TYPES_OPTIONAL_H_ #define ABSL_TYPES_OPTIONAL_H_ -#include "absl/base/config.h" -#include "absl/memory/memory.h" +#include "absl/base/config.h" // TODO(calabrese) IWYU removal? #include "absl/utility/utility.h" #ifdef ABSL_HAVE_STD_OPTIONAL @@ -56,7 +55,6 @@ using std::nullopt; #include <cassert> #include <functional> #include <initializer_list> -#include <new> #include <type_traits> #include <utility> @@ -64,6 +62,7 @@ using std::nullopt; #include "absl/base/internal/inline_variable.h" #include "absl/meta/type_traits.h" #include "absl/types/bad_optional_access.h" +#include "absl/types/internal/optional.h" // ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS // @@ -95,6 +94,22 @@ using std::nullopt; namespace absl { +// nullopt_t +// +// Class type for `absl::nullopt` used to indicate an `absl::optional<T>` type +// that does not contain a value. +struct nullopt_t { + // It must not be default-constructible to avoid ambiguity for opt = {}. + explicit constexpr nullopt_t(optional_internal::init_t) noexcept {} +}; + +// nullopt +// +// A tag constant of type `absl::nullopt_t` used to indicate an empty +// `absl::optional` in certain functions, such as construction or assignment. +ABSL_INTERNAL_INLINE_CONSTEXPR(nullopt_t, nullopt, + nullopt_t(optional_internal::init_t())); + // ----------------------------------------------------------------------------- // absl::optional // ----------------------------------------------------------------------------- @@ -124,361 +139,7 @@ namespace absl { // a) move constructors should only throw due to allocation failure and // b) if T's move constructor allocates, it uses the same allocation // function as the default allocator. -template <typename T> -class optional; - -namespace optional_internal { - -// This tag type is used as a constructor parameter type for `nullopt_t`. -struct init_t { - explicit init_t() = default; -}; - -} // namespace optional_internal - -// nullopt_t -// -// Class type for `absl::nullopt` used to indicate an `absl::optional<T>` type -// that does not contain a value. -struct nullopt_t { - // It must not be default-constructible to avoid ambiguity for opt = {}. - explicit constexpr nullopt_t(optional_internal::init_t) noexcept {} -}; - -// nullopt // -// A tag constant of type `absl::nullopt_t` used to indicate an empty -// `absl::optional` in certain functions, such as construction or assignment. -ABSL_INTERNAL_INLINE_CONSTEXPR(nullopt_t, nullopt, - nullopt_t(optional_internal::init_t())); - -namespace optional_internal { - -struct empty_struct {}; -// This class stores the data in optional<T>. -// It is specialized based on whether T is trivially destructible. -// This is the specialization for non trivially destructible type. -template <typename T, bool unused = std::is_trivially_destructible<T>::value> -class optional_data_dtor_base { - struct dummy_type { - static_assert(sizeof(T) % sizeof(empty_struct) == 0, ""); - // Use an array to avoid GCC 6 placement-new warning. - empty_struct data[sizeof(T) / sizeof(empty_struct)]; - }; - - protected: - // Whether there is data or not. - bool engaged_; - // Data storage - union { - dummy_type dummy_; - T data_; - }; - - void destruct() noexcept { - if (engaged_) { - data_.~T(); - engaged_ = false; - } - } - - // dummy_ must be initialized for constexpr constructor. - constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {} - - template <typename... Args> - constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args) - : engaged_(true), data_(absl::forward<Args>(args)...) {} - - ~optional_data_dtor_base() { destruct(); } -}; - -// Specialization for trivially destructible type. -template <typename T> -class optional_data_dtor_base<T, true> { - struct dummy_type { - static_assert(sizeof(T) % sizeof(empty_struct) == 0, ""); - // Use array to avoid GCC 6 placement-new warning. - empty_struct data[sizeof(T) / sizeof(empty_struct)]; - }; - - protected: - // Whether there is data or not. - bool engaged_; - // Data storage - union { - dummy_type dummy_; - T data_; - }; - void destruct() noexcept { engaged_ = false; } - - // dummy_ must be initialized for constexpr constructor. - constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {} - - template <typename... Args> - constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args) - : engaged_(true), data_(absl::forward<Args>(args)...) {} -}; - -template <typename T> -class optional_data_base : public optional_data_dtor_base<T> { - protected: - using base = optional_data_dtor_base<T>; -#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS - using base::base; -#else - optional_data_base() = default; - - template <typename... Args> - constexpr explicit optional_data_base(in_place_t t, Args&&... args) - : base(t, absl::forward<Args>(args)...) {} -#endif - - template <typename... Args> - void construct(Args&&... args) { - // Use dummy_'s address to work around casting cv-qualified T* to void*. - ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...); - this->engaged_ = true; - } - - template <typename U> - void assign(U&& u) { - if (this->engaged_) { - this->data_ = std::forward<U>(u); - } else { - construct(std::forward<U>(u)); - } - } -}; - -// TODO(absl-team): Add another class using -// std::is_trivially_move_constructible trait when available to match -// http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that -// have trivial move but nontrivial copy. -// Also, we should be checking is_trivially_copyable here, which is not -// supported now, so we use is_trivially_* traits instead. -template <typename T, - bool unused = absl::is_trivially_copy_constructible<T>::value&& - absl::is_trivially_copy_assignable<typename std::remove_cv< - T>::type>::value&& std::is_trivially_destructible<T>::value> -class optional_data; - -// Trivially copyable types -template <typename T> -class optional_data<T, true> : public optional_data_base<T> { - protected: -#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS - using optional_data_base<T>::optional_data_base; -#else - optional_data() = default; - - template <typename... Args> - constexpr explicit optional_data(in_place_t t, Args&&... args) - : optional_data_base<T>(t, absl::forward<Args>(args)...) {} -#endif -}; - -template <typename T> -class optional_data<T, false> : public optional_data_base<T> { - protected: -#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS - using optional_data_base<T>::optional_data_base; -#else - template <typename... Args> - constexpr explicit optional_data(in_place_t t, Args&&... args) - : optional_data_base<T>(t, absl::forward<Args>(args)...) {} -#endif - - optional_data() = default; - - optional_data(const optional_data& rhs) : optional_data_base<T>() { - if (rhs.engaged_) { - this->construct(rhs.data_); - } - } - - optional_data(optional_data&& rhs) noexcept( - absl::default_allocator_is_nothrow::value || - std::is_nothrow_move_constructible<T>::value) - : optional_data_base<T>() { - if (rhs.engaged_) { - this->construct(std::move(rhs.data_)); - } - } - - optional_data& operator=(const optional_data& rhs) { - if (rhs.engaged_) { - this->assign(rhs.data_); - } else { - this->destruct(); - } - return *this; - } - - optional_data& operator=(optional_data&& rhs) noexcept( - std::is_nothrow_move_assignable<T>::value&& - std::is_nothrow_move_constructible<T>::value) { - if (rhs.engaged_) { - this->assign(std::move(rhs.data_)); - } else { - this->destruct(); - } - return *this; - } -}; - -// Ordered by level of restriction, from low to high. -// Copyable implies movable. -enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 }; - -// Base class for enabling/disabling copy/move constructor. -template <copy_traits> -class optional_ctor_base; - -template <> -class optional_ctor_base<copy_traits::copyable> { - public: - constexpr optional_ctor_base() = default; - optional_ctor_base(const optional_ctor_base&) = default; - optional_ctor_base(optional_ctor_base&&) = default; - optional_ctor_base& operator=(const optional_ctor_base&) = default; - optional_ctor_base& operator=(optional_ctor_base&&) = default; -}; - -template <> -class optional_ctor_base<copy_traits::movable> { - public: - constexpr optional_ctor_base() = default; - optional_ctor_base(const optional_ctor_base&) = delete; - optional_ctor_base(optional_ctor_base&&) = default; - optional_ctor_base& operator=(const optional_ctor_base&) = default; - optional_ctor_base& operator=(optional_ctor_base&&) = default; -}; - -template <> -class optional_ctor_base<copy_traits::non_movable> { - public: - constexpr optional_ctor_base() = default; - optional_ctor_base(const optional_ctor_base&) = delete; - optional_ctor_base(optional_ctor_base&&) = delete; - optional_ctor_base& operator=(const optional_ctor_base&) = default; - optional_ctor_base& operator=(optional_ctor_base&&) = default; -}; - -// Base class for enabling/disabling copy/move assignment. -template <copy_traits> -class optional_assign_base; - -template <> -class optional_assign_base<copy_traits::copyable> { - public: - constexpr optional_assign_base() = default; - optional_assign_base(const optional_assign_base&) = default; - optional_assign_base(optional_assign_base&&) = default; - optional_assign_base& operator=(const optional_assign_base&) = default; - optional_assign_base& operator=(optional_assign_base&&) = default; -}; - -template <> -class optional_assign_base<copy_traits::movable> { - public: - constexpr optional_assign_base() = default; - optional_assign_base(const optional_assign_base&) = default; - optional_assign_base(optional_assign_base&&) = default; - optional_assign_base& operator=(const optional_assign_base&) = delete; - optional_assign_base& operator=(optional_assign_base&&) = default; -}; - -template <> -class optional_assign_base<copy_traits::non_movable> { - public: - constexpr optional_assign_base() = default; - optional_assign_base(const optional_assign_base&) = default; - optional_assign_base(optional_assign_base&&) = default; - optional_assign_base& operator=(const optional_assign_base&) = delete; - optional_assign_base& operator=(optional_assign_base&&) = delete; -}; - -template <typename T> -struct ctor_copy_traits { - static constexpr copy_traits traits = - std::is_copy_constructible<T>::value - ? copy_traits::copyable - : std::is_move_constructible<T>::value ? copy_traits::movable - : copy_traits::non_movable; -}; - -template <typename T> -struct assign_copy_traits { - static constexpr copy_traits traits = - absl::is_copy_assignable<T>::value && std::is_copy_constructible<T>::value - ? copy_traits::copyable - : absl::is_move_assignable<T>::value && - std::is_move_constructible<T>::value - ? copy_traits::movable - : copy_traits::non_movable; -}; - -// Whether T is constructible or convertible from optional<U>. -template <typename T, typename U> -struct is_constructible_convertible_from_optional - : std::integral_constant< - bool, std::is_constructible<T, optional<U>&>::value || - std::is_constructible<T, optional<U>&&>::value || - std::is_constructible<T, const optional<U>&>::value || - std::is_constructible<T, const optional<U>&&>::value || - std::is_convertible<optional<U>&, T>::value || - std::is_convertible<optional<U>&&, T>::value || - std::is_convertible<const optional<U>&, T>::value || - std::is_convertible<const optional<U>&&, T>::value> {}; - -// Whether T is constructible or convertible or assignable from optional<U>. -template <typename T, typename U> -struct is_constructible_convertible_assignable_from_optional - : std::integral_constant< - bool, is_constructible_convertible_from_optional<T, U>::value || - std::is_assignable<T&, optional<U>&>::value || - std::is_assignable<T&, optional<U>&&>::value || - std::is_assignable<T&, const optional<U>&>::value || - std::is_assignable<T&, const optional<U>&&>::value> {}; - -// Helper function used by [optional.relops], [optional.comp_with_t], -// for checking whether an expression is convertible to bool. -bool convertible_to_bool(bool); - -// Base class for std::hash<absl::optional<T>>: -// If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to -// compute the hash; Otherwise, it is disabled. -// Reference N4659 23.14.15 [unord.hash]. -template <typename T, typename = size_t> -struct optional_hash_base { - optional_hash_base() = delete; - optional_hash_base(const optional_hash_base&) = delete; - optional_hash_base(optional_hash_base&&) = delete; - optional_hash_base& operator=(const optional_hash_base&) = delete; - optional_hash_base& operator=(optional_hash_base&&) = delete; -}; - -template <typename T> -struct optional_hash_base<T, decltype(std::hash<absl::remove_const_t<T> >()( - std::declval<absl::remove_const_t<T> >()))> { - using argument_type = absl::optional<T>; - using result_type = size_t; - size_t operator()(const absl::optional<T>& opt) const { - absl::type_traits_internal::AssertHashEnabled<absl::remove_const_t<T>>(); - if (opt) { - return std::hash<absl::remove_const_t<T> >()(*opt); - } else { - return static_cast<size_t>(0x297814aaad196e6dULL); - } - } -}; - -} // namespace optional_internal - -// ----------------------------------------------------------------------------- -// absl::optional class definition -// ----------------------------------------------------------------------------- - template <typename T> class optional : private optional_internal::optional_data<T>, private optional_internal::optional_ctor_base< |