diff options
| -rw-r--r-- | absl/container/inlined_vector.h | 42 | ||||
| -rw-r--r-- | absl/container/inlined_vector_test.cc | 83 | ||||
| -rw-r--r-- | absl/memory/memory.h | 4 | ||||
| -rw-r--r-- | absl/memory/memory_test.cc | 10 |
4 files changed, 117 insertions, 22 deletions
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<iterator, iterator> ShiftRight(const_iterator position, size_type n); @@ -1014,28 +1019,19 @@ typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::emplace( emplace_back(std::forward<Args>(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>(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>(args)...); - return pos; + return range.first; } template <typename T, size_t N, typename A> @@ -1220,6 +1216,7 @@ auto InlinedVector<T, N, A>::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<T, N, A>::InsertWithCount(const_iterator position, -> iterator { assert(position >= begin() && position <= end()); if (n == 0) return const_cast<iterator>(position); + + value_type copy = v; std::pair<iterator, iterator> 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<T, N, A>::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 <algorithm> #include <forward_list> #include <list> #include <memory> @@ -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<int>(*other.p_); + return *this; + } + + bool operator==(const NotTriviallyDestructible& other) const { + return *p_ == *other.p_; + } + + private: + std::unique_ptr<int> p_; +}; + +TEST(AliasingTest, Emplace) { + for (int i = 2; i < 20; ++i) { + absl::InlinedVector<NotTriviallyDestructible, 10> 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<NotTriviallyDestructible, 10> 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<T[N]> { } // namespace memory_internal +#if __cplusplus >= 201402L || defined(_MSC_VER) +using std::make_unique; +#else // ----------------------------------------------------------------------------- // Function Template: make_unique<T>() // ----------------------------------------------------------------------------- @@ -164,6 +167,7 @@ typename memory_internal::MakeUniqueResult<T>::array make_unique(size_t n) { template <typename T, typename... Args> typename memory_internal::MakeUniqueResult<T>::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<int> &vec) {} + }; + using absl::make_unique; + make_unique<TakesStdType>(std::vector<int>()); +} + #if 0 // TODO(billydonahue): Make a proper NC test. // These tests shouldn't compile. |