From 44b0fafc62d9b8f192e8180cbe9c4b806b339d57 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 4 Dec 2018 11:01:12 -0800 Subject: Export of internal Abseil changes. -- cd076f55c1fa600131f6dda392533dfe61679fc0 by Abseil Team : Internal change PiperOrigin-RevId: 224008762 -- e05f62b01286d51044ff86ec6ef565749b9faf82 by Abseil Team : Create a pow10() test helper function to compute guaranteed-precise double values of 10^x. Not all standard libraries ship bit-accurate pow() functions, causing tests to fail that rely on expected values generated by it. PiperOrigin-RevId: 223883762 -- fd88e5e3f7ab80f7f5df9fd1488cd58b4573be69 by Abseil Team : Remove some absl:: qualifications to work around inline namespace bugs on MSVC 2015. PiperOrigin-RevId: 223869642 -- 6276cfff969d596edd36a2bbaba65ee045808903 by Abseil Team : Update absl/memory/CMakeLists.txt to use new functions i.e. absl_cc_(library|test) PiperOrigin-RevId: 223854224 -- 359de9afc7a34c975fd3e0cbc52afd96637d97bd by Chris Kennelly : Mark spinlock_benchmark_common as alwayslink = 1. PiperOrigin-RevId: 223844536 -- 450cd8cbe2789a6d54ed1eb87170259bb334f8b9 by Abseil Team : Support .* (pointer-to-member dereference) expressions in demangle.cc. PiperOrigin-RevId: 223826797 -- 772ca92179c3634f3e31a80bbc272ed8022e3572 by Abseil Team : Fix misspellings in absl::variant comments and replace a ' with a `. PiperOrigin-RevId: 223807911 -- 35dcdc2fbf299d195658aac101887f6dcad1de2f by Abseil Team : Bug fix in CMakeLists.txt file (SRCS --> HDRS). The compressed_tuple header-only library is being defined with the SRCS parameter instead of the HDRS parameter and this has been observed to cause some builds on some platforms to attempt to create a static library from it which fails since there are no .cc sources. PiperOrigin-RevId: 223805367 -- 4a57a3d2045bb137c0c97958e45ce425190b8d3e by Chris Kennelly : Add test that absl::make_unique value initializes memory. PiperOrigin-RevId: 223801819 -- dfe8289d7f4dcc6bb568a26aaf192a89e896bdfd by Chris Kennelly : SpinLock: Use exchange to avoid missing wakeups. The default fast path for SpinLock::Unlock does not use an atomic. If the SpinLock becomes contended while we are unlocking between lockword_.load and lockword_.store, we will fail to wake up the new waiter. This can cause unexpected latency spikes. PiperOrigin-RevId: 223800369 -- 9b9d35df786482f0016f77dd31691eff81503d23 by Abseil Team : Update absl/hash/CMakeLists.txt to use new functions i.e. absl_cc_(library|test) PiperOrigin-RevId: 223755819 -- c2014e2704b87e7cdce2d2a0287c7e2397752296 by Abseil Team : Update absl/debugging/CMakeLists.txt to use new functions i.e. absl_cc_(library|test) PiperOrigin-RevId: 223751986 -- d83a4e09126400e3fd80645cb03ee558f532271e by Derek Mauro : Cleanup synchronization benchmarks. PiperOrigin-RevId: 223589416 -- fad140b473586531b5b12843f942ec27dfcf5e93 by CJ Johnson : Makes unifies the order of forward_iterator and input_iterator overloads PiperOrigin-RevId: 223580660 -- 6cd7c96faa7cc5f79f574e35a1b13837ef187d05 by Abseil Team : Internal Change. PiperOrigin-RevId: 223561629 -- bd2e545356b0f548af0e3c14bb2f7f0e712e49d0 by Shaindel Schwartz : Remove misleading comments. try_emplace() does not exist for the hash_set containers. PiperOrigin-RevId: 223543089 -- 0cd380a53b587eb7aacc4003a4a3bbb6c78d7c10 by Derek Mauro : Internal change PiperOrigin-RevId: 223512551 -- 7156dfee599cb72e9adddfe0e6ae07a95ddf10bb by Greg Miller : Fixes UB that would result from constructing, multiplying, or dividing a Duration with a double "NaN" value. This CL changes the absl::Duration *implementation* to return an InfiniteDuration value that has the same sign as the given NaN. PiperOrigin-RevId: 223407499 -- 196b7d18609958267951882baf7f9429e49bcafa by CJ Johnson : Addresses NVCC+MSVC compilation bug where `inlined_capacity()` was not considered valid in constexpr PiperOrigin-RevId: 223397718 GitOrigin-RevId: cd076f55c1fa600131f6dda392533dfe61679fc0 Change-Id: I5423ca6470f661a7c6f73aa8fee49990446f157f --- absl/container/CMakeLists.txt | 2 +- absl/container/flat_hash_set.h | 6 +-- absl/container/inlined_vector.h | 94 ++++++++++++++++----------------- absl/container/internal/layout.h | 4 +- absl/container/internal/raw_hash_set.cc | 3 +- absl/container/node_hash_set.h | 6 +-- 6 files changed, 55 insertions(+), 60 deletions(-) (limited to 'absl/container') diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 7cddd84b..8605facc 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -30,7 +30,7 @@ absl_cc_library( absl_cc_library( NAME compressed_tuple - SRCS + HDRS "internal/compressed_tuple.h" DEPS absl::utility diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index 5ea6a816..84984cc4 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h @@ -279,8 +279,7 @@ class flat_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace; @@ -294,8 +293,7 @@ class flat_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace_hint; diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 642dae6c..5f3f0095 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -66,12 +66,11 @@ namespace absl { // designed to cover the same API footprint as covered by `std::vector`. template > class InlinedVector { + static_assert(N > 0, "InlinedVector requires inline capacity greater than 0"); constexpr static typename A::size_type inlined_capacity() { return static_cast(N); } - static_assert(inlined_capacity() > 0, "InlinedVector needs inlined capacity"); - template using DisableIfIntegral = absl::enable_if_t::value>; @@ -131,7 +130,8 @@ class InlinedVector { InlinedVector(std::initializer_list init_list, const allocator_type& alloc = allocator_type()) : allocator_and_tag_(alloc) { - AppendRange(init_list.begin(), init_list.end()); + AppendRange(init_list.begin(), init_list.end(), + IteratorCategory{}); } // Creates an inlined vector with elements constructed from the provided @@ -144,7 +144,7 @@ class InlinedVector { InlinedVector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) : allocator_and_tag_(alloc) { - AppendRange(first, last); + AppendRange(first, last, IteratorCategory{}); } // Creates a copy of `other` using `other`'s allocator. @@ -366,7 +366,6 @@ class InlinedVector { // Returns a copy of the allocator of the inlined vector. allocator_type get_allocator() const { return allocator(); } - // --------------------------------------------------------------------------- // InlinedVector Member Mutators // --------------------------------------------------------------------------- @@ -376,7 +375,8 @@ class InlinedVector { // Replaces the contents of the inlined vector with copies of the elements in // the provided `std::initializer_list`. InlinedVector& operator=(std::initializer_list init_list) { - AssignRange(init_list.begin(), init_list.end()); + AssignRange(init_list.begin(), init_list.end(), + IteratorCategory{}); return *this; } @@ -453,14 +453,15 @@ class InlinedVector { // inlined vector with copies of the values in the provided // `std::initializer_list`. void assign(std::initializer_list init_list) { - AssignRange(init_list.begin(), init_list.end()); + AssignRange(init_list.begin(), init_list.end(), + IteratorCategory{}); } // Overload of `InlinedVector::assign()` to replace the contents of the // inlined vector with values constructed from the range [`first`, `last`). template * = nullptr> void assign(InputIterator first, InputIterator last) { - AssignRange(first, last); + AssignRange(first, last, IteratorCategory{}); } // `InlinedVector::resize()` @@ -844,41 +845,29 @@ class InlinedVector { // Destroy [`from`, `to`) in place. void Destroy(pointer from, pointer to); - template - void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) { - std::copy(first, last, std::back_inserter(*this)); - } - template void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag); template - void AppendRange(Iterator first, Iterator last) { - AppendRange(first, last, IteratorCategory()); - } - - template - void AssignRange(Iterator first, Iterator last, std::input_iterator_tag); + void AppendRange(Iterator first, Iterator last, std::input_iterator_tag); template void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag); template - void AssignRange(Iterator first, Iterator last) { - AssignRange(first, last, IteratorCategory()); - } + void AssignRange(Iterator first, Iterator last, std::input_iterator_tag); iterator InsertWithCount(const_iterator position, size_type n, const_reference v); - template - iterator InsertWithRange(const_iterator position, InputIterator first, - InputIterator last, std::input_iterator_tag); - template iterator InsertWithRange(const_iterator position, ForwardIterator first, ForwardIterator last, std::forward_iterator_tag); + template + iterator InsertWithRange(const_iterator position, InputIterator first, + InputIterator last, std::input_iterator_tag); + // Stores either the inlined or allocated representation union Rep { using ValueTypeBuffer = @@ -889,7 +878,7 @@ class InlinedVector { // Structs wrap the buffers to perform indirection that solves a bizarre // compilation error on Visual Studio (all known versions). struct InlinedRep { - ValueTypeBuffer inlined[inlined_capacity()]; + ValueTypeBuffer inlined[N]; }; struct AllocatedRep { AllocationBuffer allocation; @@ -1364,15 +1353,8 @@ void InlinedVector::AppendRange(Iterator first, Iterator last, template template -void InlinedVector::AssignRange(Iterator first, Iterator last, +void InlinedVector::AppendRange(Iterator first, Iterator last, std::input_iterator_tag) { - // Optimized to avoid reallocation. - // Prefer reassignment to copy construction for elements. - iterator out = begin(); - for (; first != last && out != end(); ++first, ++out) { - *out = *first; - } - erase(out, end()); std::copy(first, last, std::back_inserter(*this)); } @@ -1398,6 +1380,20 @@ void InlinedVector::AssignRange(Iterator first, Iterator last, } } +template +template +void InlinedVector::AssignRange(Iterator first, Iterator last, + std::input_iterator_tag) { + // Optimized to avoid reallocation. + // Prefer reassignment to copy construction for elements. + iterator out = begin(); + for (; first != last && out != end(); ++first, ++out) { + *out = *first; + } + erase(out, end()); + std::copy(first, last, std::back_inserter(*this)); +} + template auto InlinedVector::InsertWithCount(const_iterator position, size_type n, const_reference v) @@ -1413,20 +1409,6 @@ auto InlinedVector::InsertWithCount(const_iterator position, return it_pair.first; } -template -template -auto InlinedVector::InsertWithRange(const_iterator position, - InputIterator first, - InputIterator last, - std::input_iterator_tag) - -> iterator { - assert(position >= begin() && position <= end()); - size_type index = position - cbegin(); - size_type i = index; - while (first != last) insert(begin() + i++, *first++); - return begin() + index; -} - template template auto InlinedVector::InsertWithRange(const_iterator position, @@ -1446,6 +1428,20 @@ auto InlinedVector::InsertWithRange(const_iterator position, return it_pair.first; } +template +template +auto InlinedVector::InsertWithRange(const_iterator position, + InputIterator first, + InputIterator last, + std::input_iterator_tag) + -> iterator { + assert(position >= begin() && position <= end()); + size_type index = position - cbegin(); + size_type i = index; + while (first != last) insert(begin() + i++, *first++); + return begin() + index; +} + } // namespace absl #endif // ABSL_CONTAINER_INLINED_VECTOR_H_ diff --git a/absl/container/internal/layout.h b/absl/container/internal/layout.h index a9c1244a..3d21ac96 100644 --- a/absl/container/internal/layout.h +++ b/absl/container/internal/layout.h @@ -253,8 +253,10 @@ template using CopyConst = typename std::conditional::value, const To, To>::type; +// Note: We're not qualifying this with absl:: because it doesn't compile under +// MSVC. template -using SliceType = absl::Span; +using SliceType = Span; // This namespace contains no types. It prevents functions defined in it from // being found by ADL. diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 10153129..180d3fe5 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc @@ -14,6 +14,7 @@ #include "absl/container/internal/raw_hash_set.h" +#include #include #include "absl/base/config.h" @@ -29,7 +30,7 @@ inline size_t RandomSeed() { static thread_local size_t counter = 0; size_t value = ++counter; #else // ABSL_HAVE_THREAD_LOCAL - static std::atomic counter; + static std::atomic counter(0); size_t value = counter.fetch_add(1, std::memory_order_relaxed); #endif // ABSL_HAVE_THREAD_LOCAL return value ^ static_cast(reinterpret_cast(&counter)); diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index e4034461..843b11aa 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h @@ -273,8 +273,7 @@ class node_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace; @@ -288,8 +287,7 @@ class node_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace_hint; -- cgit v1.2.3