summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2017-10-23 11:40:35 -0700
committerGravatar Jon Cohen <cohenjon@google.com>2017-10-23 15:26:40 -0400
commit5fcbe86e7ba65b6457d98764aa511c4f05c9435b (patch)
treeb2cea4280fa7c22dfe8313c2035499037a34179f /absl/container
parent6cf9c731027f4d8aebe3c60df8e64317e6870870 (diff)
Changes imported from Abseil "staging" branch:
- 989557e6b443a81b5ad9bd0d0c704edbe96c09c9 Make InlinedVector::ShiftRight update the vector's size -... by Jon Cohen <cohenjon@google.com> - ffc2e2a6f169bbfa823890f21d13e16110cd0206 Fix issues when passing references aliasing into an Inlin... by Jon Cohen <cohenjon@google.com> - 2fce2f87043f8c044889b4aab828e6edc20da0d9 In C++14 or later, alias absl::make_unique to std::make_u... by Abseil Team <absl-team@google.com> - cb83e95b486c59fd6acfa956e97f42253dd158bd Roll back change to avoid weak virtual table warnings (-W... by Abseil Team <absl-team@google.com> - fb4ea46062895cb9340166c9dcc61ec4467bd834 Avoid weak virtual table warnings (-Wweak-vtables) and re... by Abseil Team <absl-team@google.com> GitOrigin-RevId: 989557e6b443a81b5ad9bd0d0c704edbe96c09c9 Change-Id: I6b8119c3f16e9d0cb9b5fd6e750502c9dad8e257
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/inlined_vector.h42
-rw-r--r--absl/container/inlined_vector_test.cc83
2 files changed, 103 insertions, 22 deletions
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 96a9d001..e0bb900c 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 c559a9a1..055bca98 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.