summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-09-30 13:36:40 -0700
committerGravatar Andy Getzendanner <durandal@google.com>2020-10-01 01:43:11 +0000
commit093cc27604df1c4a179b73bc3f00d4d1ce2ce113 (patch)
treedf9ac77f22cf2ee5462d235d45b549e46b0a2188
parent40fdb59d37116d3299ff2d69cf7697f23864d8d5 (diff)
Export of internal Abseil changes
-- 0674e1ab1c1f71c5362b9e2337333e67f7ed865d by Andy Getzendanner <durandal@google.com>: btree: fix sign-compare warnings Import of https://github.com/abseil/abseil-cpp/pull/800 PiperOrigin-RevId: 334668397 -- 3b1f289781e4c68e244a7534f95eb0719ca1e8e1 by Abseil Team <absl-team@google.com>: Avoid iterating past the end of either container in absl::c_transform. The API for the two-range absl::c_transform is misleading as it doesn't check the bounds of the second range against the first one. This commit cleans up the internals of the overload to make sure that buggy calls are not exploitable; non-buggy calls are unaffected. This is consistent with C++20 ranges (see http://wg21.link/alg.transform). PiperOrigin-RevId: 334629614 -- 1184d9c2e7031860638b709c489cbd1b0d861040 by Abseil Team <absl-team@google.com>: Avoid iterating past the end of either container in absl::c_swap_ranges. The API for absl::c_swap_ranges is misleading as it doesn't check the bounds of the second range against the first one. This commit cleans up the internals of the overload to make sure that buggy calls are not exploitable; non-buggy calls are unaffected. This is consistent with C++20 ranges (see http://wg21.link/alg.swap). PiperOrigin-RevId: 334618454 GitOrigin-RevId: 0674e1ab1c1f71c5362b9e2337333e67f7ed865d Change-Id: Ifac0e99b1209bb7589bf74215b1d354dd30eabaa
-rw-r--r--absl/algorithm/container.h33
-rw-r--r--absl/algorithm/container_test.cc23
2 files changed, 47 insertions, 9 deletions
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h
index 2457d78b..5c033571 100644
--- a/absl/algorithm/container.h
+++ b/absl/algorithm/container.h
@@ -539,12 +539,20 @@ BidirectionalIterator c_move_backward(C&& src, BidirectionalIterator dest) {
// c_swap_ranges()
//
// Container-based version of the <algorithm> `std::swap_ranges()` function to
-// swap a container's elements with another container's elements.
+// swap a container's elements with another container's elements. Swaps the
+// first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)).
template <typename C1, typename C2>
container_algorithm_internal::ContainerIter<C2> c_swap_ranges(C1& c1, C2& c2) {
- return std::swap_ranges(container_algorithm_internal::c_begin(c1),
- container_algorithm_internal::c_end(c1),
- container_algorithm_internal::c_begin(c2));
+ auto first1 = container_algorithm_internal::c_begin(c1);
+ auto last1 = container_algorithm_internal::c_end(c1);
+ auto first2 = container_algorithm_internal::c_begin(c2);
+ auto last2 = container_algorithm_internal::c_end(c2);
+
+ using std::swap;
+ for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
+ swap(*first1, *first2);
+ }
+ return first2;
}
// c_transform()
@@ -562,16 +570,23 @@ OutputIterator c_transform(const InputSequence& input, OutputIterator output,
}
// Overload of c_transform() for performing a transformation using a binary
-// predicate.
+// predicate. Applies `binary_op` to the first N elements of `c1` and `c2`,
+// where N = min(size(c1), size(c2)).
template <typename InputSequence1, typename InputSequence2,
typename OutputIterator, typename BinaryOp>
OutputIterator c_transform(const InputSequence1& input1,
const InputSequence2& input2, OutputIterator output,
BinaryOp&& binary_op) {
- return std::transform(container_algorithm_internal::c_begin(input1),
- container_algorithm_internal::c_end(input1),
- container_algorithm_internal::c_begin(input2), output,
- std::forward<BinaryOp>(binary_op));
+ auto first1 = container_algorithm_internal::c_begin(input1);
+ auto last1 = container_algorithm_internal::c_end(input1);
+ auto first2 = container_algorithm_internal::c_begin(input2);
+ auto last2 = container_algorithm_internal::c_end(input2);
+ for (; first1 != last1 && first2 != last2;
+ ++first1, (void)++first2, ++output) {
+ *output = binary_op(*first1, *first2);
+ }
+
+ return output;
}
// c_replace()
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc
index 0a4abe94..3abf5cea 100644
--- a/absl/algorithm/container_test.cc
+++ b/absl/algorithm/container_test.cc
@@ -676,6 +676,15 @@ TEST(MutatingTest, SwapRanges) {
absl::c_swap_ranges(odds, evens);
EXPECT_THAT(odds, ElementsAre(1, 3, 5));
EXPECT_THAT(evens, ElementsAre(2, 4, 6));
+
+ odds.pop_back();
+ absl::c_swap_ranges(odds, evens);
+ EXPECT_THAT(odds, ElementsAre(2, 4));
+ EXPECT_THAT(evens, ElementsAre(1, 3, 6));
+
+ absl::c_swap_ranges(evens, odds);
+ EXPECT_THAT(odds, ElementsAre(1, 3));
+ EXPECT_THAT(evens, ElementsAre(2, 4, 6));
}
TEST_F(NonMutatingTest, Transform) {
@@ -690,6 +699,20 @@ TEST_F(NonMutatingTest, Transform) {
EXPECT_EQ(std::vector<int>({1, 5, 4}), z);
*end = 7;
EXPECT_EQ(std::vector<int>({1, 5, 4, 7}), z);
+
+ z.clear();
+ y.pop_back();
+ end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>());
+ EXPECT_EQ(std::vector<int>({1, 5}), z);
+ *end = 7;
+ EXPECT_EQ(std::vector<int>({1, 5, 7}), z);
+
+ z.clear();
+ std::swap(x, y);
+ end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>());
+ EXPECT_EQ(std::vector<int>({1, 5}), z);
+ *end = 7;
+ EXPECT_EQ(std::vector<int>({1, 5, 7}), z);
}
TEST(MutatingTest, Replace) {