From 5fcbe86e7ba65b6457d98764aa511c4f05c9435b Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 23 Oct 2017 11:40:35 -0700 Subject: Changes imported from Abseil "staging" branch: - 989557e6b443a81b5ad9bd0d0c704edbe96c09c9 Make InlinedVector::ShiftRight update the vector's size -... by Jon Cohen - ffc2e2a6f169bbfa823890f21d13e16110cd0206 Fix issues when passing references aliasing into an Inlin... by Jon Cohen - 2fce2f87043f8c044889b4aab828e6edc20da0d9 In C++14 or later, alias absl::make_unique to std::make_u... by Abseil Team - cb83e95b486c59fd6acfa956e97f42253dd158bd Roll back change to avoid weak virtual table warnings (-W... by Abseil Team - fb4ea46062895cb9340166c9dcc61ec4467bd834 Avoid weak virtual table warnings (-Wweak-vtables) and re... by Abseil Team GitOrigin-RevId: 989557e6b443a81b5ad9bd0d0c704edbe96c09c9 Change-Id: I6b8119c3f16e9d0cb9b5fd6e750502c9dad8e257 --- absl/container/inlined_vector.h | 42 +++++++++--------- absl/container/inlined_vector_test.cc | 83 +++++++++++++++++++++++++++++++++++ absl/memory/memory.h | 4 ++ absl/memory/memory_test.cc | 10 +++++ 4 files changed, 117 insertions(+), 22 deletions(-) (limited to 'absl') diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 96a9d001a355..e0bb900cbb66 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -149,6 +149,9 @@ class InlinedVector { ~InlinedVector() { clear(); } InlinedVector& operator=(const InlinedVector& v) { + if (this == &v) { + return *this; + } // Optimized to avoid reallocation. // Prefer reassignment to copy construction for elements. if (size() < v.size()) { // grow @@ -681,6 +684,8 @@ class InlinedVector { // portion and the start of the uninitialized portion of the created gap. // The number of initialized spots is pair.second - pair.first; // the number of raw spots is n - (pair.second - pair.first). + // + // Updates the size of the InlinedVector internally. std::pair ShiftRight(const_iterator position, size_type n); @@ -1014,28 +1019,19 @@ typename InlinedVector::iterator InlinedVector::emplace( emplace_back(std::forward(args)...); return end() - 1; } - size_type s = size(); - size_type idx = std::distance(cbegin(), position); - if (s == capacity()) { - EnlargeBy(1); - } - assert(s < capacity()); - iterator pos = begin() + idx; // Set 'pos' to a post-enlarge iterator. - pointer space; - if (allocated()) { - tag().set_allocated_size(s + 1); - space = allocated_space(); + T new_t = T(std::forward(args)...); + + auto range = ShiftRight(position, 1); + if (range.first == range.second) { + // constructing into uninitialized memory + Construct(range.first, std::move(new_t)); } else { - tag().set_inline_size(s + 1); - space = inlined_space(); + // assigning into moved-from object + *range.first = T(std::move(new_t)); } - Construct(space + s, std::move(space[s - 1])); - std::move_backward(pos, space + s - 1, space + s); - Destroy(pos, pos + 1); - Construct(pos, std::forward(args)...); - return pos; + return range.first; } template @@ -1220,6 +1216,7 @@ auto InlinedVector::ShiftRight(const_iterator position, size_type n) start_used = pos; start_raw = pos + new_elements_in_used_space; } + tag().add_size(n); return std::make_pair(start_used, start_raw); } @@ -1298,10 +1295,12 @@ auto InlinedVector::InsertWithCount(const_iterator position, -> iterator { assert(position >= begin() && position <= end()); if (n == 0) return const_cast(position); + + value_type copy = v; std::pair it_pair = ShiftRight(position, n); - std::fill(it_pair.first, it_pair.second, v); - UninitializedFill(it_pair.second, it_pair.first + n, v); - tag().add_size(n); + std::fill(it_pair.first, it_pair.second, copy); + UninitializedFill(it_pair.second, it_pair.first + n, copy); + return it_pair.first; } @@ -1337,7 +1336,6 @@ auto InlinedVector::InsertWithRange(const_iterator position, ForwardIter open_spot = std::next(first, used_spots); std::copy(first, open_spot, it_pair.first); UninitializedCopy(open_spot, last, it_pair.second); - tag().add_size(n); return it_pair.first; } diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc index c559a9a1fcba..055bca983cac 100644 --- a/absl/container/inlined_vector_test.cc +++ b/absl/container/inlined_vector_test.cc @@ -14,6 +14,7 @@ #include "absl/container/inlined_vector.h" +#include #include #include #include @@ -569,6 +570,16 @@ TEST(IntVec, CopyConstructorAndAssignment) { } } +TEST(IntVec, AliasingCopyAssignment) { + for (int len = 0; len < 20; ++len) { + IntVec original; + Fill(&original, len); + IntVec dup = original; + dup = dup; + EXPECT_EQ(dup, original); + } +} + TEST(IntVec, MoveConstructorAndAssignment) { for (int len = 0; len < 20; len++) { IntVec v_in; @@ -606,6 +617,78 @@ TEST(IntVec, MoveConstructorAndAssignment) { } } +class NotTriviallyDestructible { + public: + NotTriviallyDestructible() : p_(new int(1)) {} + explicit NotTriviallyDestructible(int i) : p_(new int(i)) {} + + NotTriviallyDestructible(const NotTriviallyDestructible& other) + : p_(new int(*other.p_)) {} + + NotTriviallyDestructible& operator=(const NotTriviallyDestructible& other) { + p_ = absl::make_unique(*other.p_); + return *this; + } + + bool operator==(const NotTriviallyDestructible& other) const { + return *p_ == *other.p_; + } + + private: + std::unique_ptr p_; +}; + +TEST(AliasingTest, Emplace) { + for (int i = 2; i < 20; ++i) { + absl::InlinedVector vec; + for (int j = 0; j < i; ++j) { + vec.push_back(NotTriviallyDestructible(j)); + } + vec.emplace(vec.begin(), vec[0]); + EXPECT_EQ(vec[0], vec[1]); + vec.emplace(vec.begin() + i / 2, vec[i / 2]); + EXPECT_EQ(vec[i / 2], vec[i / 2 + 1]); + vec.emplace(vec.end() - 1, vec.back()); + EXPECT_EQ(vec[vec.size() - 2], vec.back()); + } +} + +TEST(AliasingTest, InsertWithCount) { + for (int i = 1; i < 20; ++i) { + absl::InlinedVector vec; + for (int j = 0; j < i; ++j) { + vec.push_back(NotTriviallyDestructible(j)); + } + for (int n = 0; n < 5; ++n) { + // We use back where we can because it's guaranteed to become invalidated + vec.insert(vec.begin(), n, vec.back()); + auto b = vec.begin(); + EXPECT_TRUE( + std::all_of(b, b + n, [&vec](const NotTriviallyDestructible& x) { + return x == vec.back(); + })); + + auto m_idx = vec.size() / 2; + vec.insert(vec.begin() + m_idx, n, vec.back()); + auto m = vec.begin() + m_idx; + EXPECT_TRUE( + std::all_of(m, m + n, [&vec](const NotTriviallyDestructible& x) { + return x == vec.back(); + })); + + // We want distinct values so the equality test is meaningful, + // vec[vec.size() - 1] is also almost always invalidated. + auto old_e = vec.size() - 1; + auto val = vec[old_e]; + vec.insert(vec.end(), n, vec[old_e]); + auto e = vec.begin() + old_e; + EXPECT_TRUE(std::all_of( + e, e + n, + [&val](const NotTriviallyDestructible& x) { return x == val; })); + } + } +} + TEST(OverheadTest, Storage) { // Check for size overhead. // In particular, ensure that std::allocator doesn't cost anything to store. diff --git a/absl/memory/memory.h b/absl/memory/memory.h index 959091388243..15cd85f4e1ed 100644 --- a/absl/memory/memory.h +++ b/absl/memory/memory.h @@ -81,6 +81,9 @@ struct MakeUniqueResult { } // namespace memory_internal +#if __cplusplus >= 201402L || defined(_MSC_VER) +using std::make_unique; +#else // ----------------------------------------------------------------------------- // Function Template: make_unique() // ----------------------------------------------------------------------------- @@ -164,6 +167,7 @@ typename memory_internal::MakeUniqueResult::array make_unique(size_t n) { template typename memory_internal::MakeUniqueResult::invalid make_unique( Args&&... /* args */) = delete; +#endif // ----------------------------------------------------------------------------- // Function Template: RawPtr() diff --git a/absl/memory/memory_test.cc b/absl/memory/memory_test.cc index 8a5f5522a089..7d047ca0c726 100644 --- a/absl/memory/memory_test.cc +++ b/absl/memory/memory_test.cc @@ -138,6 +138,16 @@ TEST(Make_UniqueTest, Array) { EXPECT_THAT(ArrayWatch::allocs(), ElementsAre(5 * sizeof(ArrayWatch))); } +TEST(Make_UniqueTest, NotAmbiguousWithStdMakeUnique) { + // Ensure that absl::make_unique is not ambiguous with std::make_unique. + // In C++14 mode, the below call to make_unique has both types as candidates. + struct TakesStdType { + explicit TakesStdType(const std::vector &vec) {} + }; + using absl::make_unique; + make_unique(std::vector()); +} + #if 0 // TODO(billydonahue): Make a proper NC test. // These tests shouldn't compile. -- cgit 1.4.1