summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--absl/container/btree_test.cc21
-rw-r--r--absl/container/internal/btree.h87
-rw-r--r--absl/container/internal/btree_container.h43
-rw-r--r--absl/strings/internal/charconv_bigint_test.cc55
-rwxr-xr-xci/cmake_common.sh2
-rw-r--r--ci/linux_docker_containers.sh2
6 files changed, 115 insertions, 95 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 4a495067..9b1b6436 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2680,6 +2680,12 @@ struct MultiKey {
int i2;
};
+bool operator==(const MultiKey a, const MultiKey b) {
+ return a.i1 == b.i1 && a.i2 == b.i2;
+}
+
+// A heterogeneous comparator that has different equivalence classes for
+// different lookup types.
struct MultiKeyComp {
using is_transparent = void;
bool operator()(const MultiKey a, const MultiKey b) const {
@@ -2690,8 +2696,6 @@ struct MultiKeyComp {
bool operator()(const MultiKey a, const int b) const { return a.i1 < b; }
};
-// Test that when there's a heterogeneous comparator that behaves differently
-// for some heterogeneous operators, we get equal_range() right.
TEST(Btree, MultiKeyEqualRange) {
absl::btree_set<MultiKey, MultiKeyComp> set;
@@ -2709,6 +2713,19 @@ TEST(Btree, MultiKeyEqualRange) {
}
}
+TEST(Btree, MultiKeyErase) {
+ absl::btree_set<MultiKey, MultiKeyComp> set = {
+ {1, 1}, {2, 1}, {2, 2}, {3, 1}};
+ EXPECT_EQ(set.erase(2), 2);
+ EXPECT_THAT(set, ElementsAre(MultiKey{1, 1}, MultiKey{3, 1}));
+}
+
+TEST(Btree, MultiKeyCount) {
+ const absl::btree_set<MultiKey, MultiKeyComp> set = {
+ {1, 1}, {2, 1}, {2, 2}, {3, 1}};
+ EXPECT_EQ(set.count(2), 2);
+}
+
TEST(Btree, AllocConstructor) {
using Alloc = CountingAllocator<int>;
using Set = absl::btree_set<int, std::less<int>, Alloc>;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 8547d68e..f2fc31df 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -423,6 +423,7 @@ struct SearchResult {
// useful information.
template <typename V>
struct SearchResult<V, false> {
+ SearchResult() {}
explicit SearchResult(V value) : value(value) {}
SearchResult(V value, MatchKind /*match*/) : value(value) {}
@@ -1200,11 +1201,11 @@ class btree {
// Finds the first element whose key is not less than key.
template <typename K>
iterator lower_bound(const K &key) {
- return internal_end(internal_lower_bound(key));
+ return internal_end(internal_lower_bound(key).value);
}
template <typename K>
const_iterator lower_bound(const K &key) const {
- return internal_end(internal_lower_bound(key));
+ return internal_end(internal_lower_bound(key).value);
}
// Finds the first element whose key is greater than key.
@@ -1289,16 +1290,6 @@ class btree {
// to the element after the last erased element.
std::pair<size_type, iterator> erase_range(iterator begin, iterator end);
- // Erases the specified key from the btree. Returns 1 if an element was
- // erased and 0 otherwise.
- template <typename K>
- size_type erase_unique(const K &key);
-
- // Erases all of the entries matching the specified key from the
- // btree. Returns the number of elements erased.
- template <typename K>
- size_type erase_multi(const K &key);
-
// Finds the iterator corresponding to a key or returns end() if the key is
// not present.
template <typename K>
@@ -1310,23 +1301,6 @@ class btree {
return internal_end(internal_find(key));
}
- // Returns a count of the number of times the key appears in the btree.
- template <typename K>
- size_type count_unique(const K &key) const {
- const iterator begin = internal_find(key);
- if (begin.node == nullptr) {
- // The key doesn't exist in the tree.
- return 0;
- }
- return 1;
- }
- // Returns a count of the number of times the key appears in the btree.
- template <typename K>
- size_type count_multi(const K &key) const {
- const auto range = equal_range(key);
- return std::distance(range.first, range.second);
- }
-
// Clear the btree, deleting all of the values it contains.
void clear();
@@ -1514,7 +1488,8 @@ class btree {
// Internal routine which implements lower_bound().
template <typename K>
- iterator internal_lower_bound(const K &key) const;
+ SearchResult<iterator, is_key_compare_to::value> internal_lower_bound(
+ const K &key) const;
// Internal routine which implements upper_bound().
template <typename K>
@@ -1918,10 +1893,13 @@ constexpr bool btree<P>::static_assert_validation() {
template <typename P>
template <typename K>
auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
- const iterator lower = lower_bound(key);
- // TODO(ezb): we should be able to avoid this comparison when there's a
- // three-way comparator.
- if (lower == end() || compare_keys(key, lower.key())) return {lower, lower};
+ const SearchResult<iterator, is_key_compare_to::value> res =
+ internal_lower_bound(key);
+ const iterator lower = internal_end(res.value);
+ if (res.HasMatch() ? !res.IsEq()
+ : lower == end() || compare_keys(key, lower.key())) {
+ return {lower, lower};
+ }
const iterator next = std::next(lower);
// When the comparator is heterogeneous, we can't assume that comparison with
@@ -1941,7 +1919,7 @@ auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
// Try once more to avoid the call to upper_bound() if there's only one
// equivalent key. This should prevent all calls to upper_bound() in cases of
// unique-containers with heterogeneous comparators in which all comparison
- // operators are equivalent.
+ // operators have the same equivalence classes.
if (next == end() || compare_keys(key, next.key())) return {lower, next};
// In this case, we need to call upper_bound() to avoid worst case O(N)
@@ -2226,31 +2204,6 @@ auto btree<P>::erase_range(iterator begin, iterator end)
}
template <typename P>
-template <typename K>
-auto btree<P>::erase_unique(const K &key) -> size_type {
- const iterator iter = internal_find(key);
- if (iter.node == nullptr) {
- // The key doesn't exist in the tree, return nothing done.
- return 0;
- }
- erase(iter);
- return 1;
-}
-
-template <typename P>
-template <typename K>
-auto btree<P>::erase_multi(const K &key) -> size_type {
- const iterator begin = internal_lower_bound(key);
- if (begin.node == nullptr) {
- // The key doesn't exist in the tree, return nothing done.
- return 0;
- }
- // Delete all of the keys between begin and upper_bound(key).
- const iterator end = internal_end(internal_upper_bound(key));
- return erase_range(begin, end).first;
-}
-
-template <typename P>
void btree<P>::clear() {
if (!empty()) {
node_type::clear_and_delete(root(), mutable_allocator());
@@ -2548,16 +2501,24 @@ inline auto btree<P>::internal_locate(const K &key) const
template <typename P>
template <typename K>
-auto btree<P>::internal_lower_bound(const K &key) const -> iterator {
+auto btree<P>::internal_lower_bound(const K &key) const
+ -> SearchResult<iterator, is_key_compare_to::value> {
iterator iter(const_cast<node_type *>(root()));
+ SearchResult<int, is_key_compare_to::value> res;
+ bool seen_eq = false;
for (;;) {
- iter.position = iter.node->lower_bound(key, key_comp()).value;
+ res = iter.node->lower_bound(key, key_comp());
+ iter.position = res.value;
+ // TODO(ezb): we should be able to terminate early on IsEq() if there can't
+ // be multiple equivalent keys in container for this lookup type.
if (iter.node->leaf()) {
break;
}
+ seen_eq = seen_eq || res.IsEq();
iter.node = iter.node->child(iter.position);
}
- return internal_last(iter);
+ if (res.IsEq()) return {iter, MatchKind::kEq};
+ return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe};
}
template <typename P>
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 3792bc21..887eda41 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -104,6 +104,11 @@ class btree_container {
// Lookup routines.
template <typename K = key_type>
+ size_type count(const key_arg<K> &key) const {
+ auto equal_range = this->equal_range(key);
+ return std::distance(equal_range.first, equal_range.second);
+ }
+ template <typename K = key_type>
iterator find(const key_arg<K> &key) {
return tree_.find(key);
}
@@ -152,6 +157,11 @@ class btree_container {
iterator erase(const_iterator first, const_iterator last) {
return tree_.erase_range(iterator(first), iterator(last)).second;
}
+ template <typename K = key_type>
+ size_type erase(const key_arg<K> &key) {
+ auto equal_range = this->equal_range(key);
+ return tree_.erase_range(equal_range.first, equal_range.second).first;
+ }
// Extract routines.
node_type extract(iterator position) {
@@ -270,12 +280,6 @@ class btree_set_container : public btree_container<Tree> {
const allocator_type &alloc)
: btree_set_container(init.begin(), init.end(), alloc) {}
- // Lookup routines.
- template <typename K = key_type>
- size_type count(const key_arg<K> &key) const {
- return this->tree_.count_unique(key);
- }
-
// Insertion routines.
std::pair<iterator, bool> insert(const value_type &v) {
return this->tree_.insert_unique(params_type::key(v), v);
@@ -333,16 +337,10 @@ class btree_set_container : public btree_container<Tree> {
return res.first;
}
- // Deletion routines.
- // TODO(ezb): we should support heterogeneous comparators that have different
- // behavior for K!=key_type.
- template <typename K = key_type>
- size_type erase(const key_arg<K> &key) {
- return this->tree_.erase_unique(key);
- }
- using super_type::erase;
-
// Node extraction routines.
+ // TODO(ezb): when the comparator is heterogeneous and has different
+ // equivalence classes for different lookup types, we should extract the first
+ // equivalent value if there are multiple.
template <typename K = key_type>
node_type extract(const key_arg<K> &key) {
auto it = this->find(key);
@@ -578,12 +576,6 @@ class btree_multiset_container : public btree_container<Tree> {
const allocator_type &alloc)
: btree_multiset_container(init.begin(), init.end(), alloc) {}
- // Lookup routines.
- template <typename K = key_type>
- size_type count(const key_arg<K> &key) const {
- return this->tree_.count_multi(key);
- }
-
// Insertion routines.
iterator insert(const value_type &v) { return this->tree_.insert_multi(v); }
iterator insert(value_type &&v) {
@@ -628,14 +620,9 @@ class btree_multiset_container : public btree_container<Tree> {
return res;
}
- // Deletion routines.
- template <typename K = key_type>
- size_type erase(const key_arg<K> &key) {
- return this->tree_.erase_multi(key);
- }
- using super_type::erase;
-
// Node extraction routines.
+ // TODO(ezb): we are supposed to extract the first equivalent key if there are
+ // multiple, but this isn't guaranteed to extract the first one.
template <typename K = key_type>
node_type extract(const key_arg<K> &key) {
auto it = this->find(key);
diff --git a/absl/strings/internal/charconv_bigint_test.cc b/absl/strings/internal/charconv_bigint_test.cc
index 363bcb03..a8b99458 100644
--- a/absl/strings/internal/charconv_bigint_test.cc
+++ b/absl/strings/internal/charconv_bigint_test.cc
@@ -69,6 +69,61 @@ TEST(BigUnsigned, ShiftLeft) {
// And we should have fully rotated all bits off by now:
EXPECT_EQ(a, BigUnsigned<84>(0u));
}
+ {
+ // Bit shifting large and small numbers by large and small offsets.
+ // Intended to exercise bounds-checking corner on ShiftLeft() (directly
+ // and under asan).
+
+ // 2**(32*84)-1
+ const BigUnsigned<84> all_bits_one(
+ "1474444211396924248063325089479706787923460402125687709454567433186613"
+ "6228083464060749874845919674257665016359189106695900028098437021384227"
+ "3285029708032466536084583113729486015826557532750465299832071590813090"
+ "2011853039837649252477307070509704043541368002938784757296893793903797"
+ "8180292336310543540677175225040919704702800559606097685920595947397024"
+ "8303316808753252115729411497720357971050627997031988036134171378490368"
+ "6008000778741115399296162550786288457245180872759047016734959330367829"
+ "5235612397427686310674725251378116268607113017720538636924549612987647"
+ "5767411074510311386444547332882472126067840027882117834454260409440463"
+ "9345147252664893456053258463203120637089916304618696601333953616715125"
+ "2115882482473279040772264257431663818610405673876655957323083702713344"
+ "4201105427930770976052393421467136557055");
+ const BigUnsigned<84> zero(0u);
+ const BigUnsigned<84> one(1u);
+ // in bounds shifts
+ for (int i = 1; i < 84*32; ++i) {
+ // shifting all_bits_one to the left should result in a smaller number,
+ // since the high bits rotate off and the low bits are replaced with
+ // zeroes.
+ BigUnsigned<84> big_shifted = all_bits_one;
+ big_shifted.ShiftLeft(i);
+ EXPECT_GT(all_bits_one, big_shifted);
+ // Shifting 1 to the left should instead result in a larger number.
+ BigUnsigned<84> small_shifted = one;
+ small_shifted.ShiftLeft(i);
+ EXPECT_LT(one, small_shifted);
+ }
+ // Shifting by zero or a negative number has no effect
+ for (int no_op_shift : {0, -1, -84 * 32, std::numeric_limits<int>::min()}) {
+ BigUnsigned<84> big_shifted = all_bits_one;
+ big_shifted.ShiftLeft(no_op_shift);
+ EXPECT_EQ(all_bits_one, big_shifted);
+ BigUnsigned<84> small_shifted = one;
+ big_shifted.ShiftLeft(no_op_shift);
+ EXPECT_EQ(one, small_shifted);
+ }
+ // Shifting by an amount greater than the number of bits should result in
+ // zero.
+ for (int out_of_bounds_shift :
+ {84 * 32, 84 * 32 + 1, std::numeric_limits<int>::max()}) {
+ BigUnsigned<84> big_shifted = all_bits_one;
+ big_shifted.ShiftLeft(out_of_bounds_shift);
+ EXPECT_EQ(zero, big_shifted);
+ BigUnsigned<84> small_shifted = one;
+ small_shifted.ShiftLeft(out_of_bounds_shift);
+ EXPECT_EQ(zero, small_shifted);
+ }
+ }
}
TEST(BigUnsigned, MultiplyByUint32) {
diff --git a/ci/cmake_common.sh b/ci/cmake_common.sh
index 15ffde2e..aec8a117 100755
--- a/ci/cmake_common.sh
+++ b/ci/cmake_common.sh
@@ -17,7 +17,7 @@
readonly ABSL_GOOGLETEST_COMMIT="8567b09290fe402cf01923e2131c5635b8ed851b"
# Avoid depending on GitHub by looking for a cached copy of the commit first.
-if [[ -r "${KOKORO_GFILE_DIR}/distdir/${ABSL_GOOGLETEST_COMMIT}.zip" ]]; then
+if [[ -r "${KOKORO_GFILE_DIR:-}/distdir/${ABSL_GOOGLETEST_COMMIT}.zip" ]]; then
DOCKER_EXTRA_ARGS="--mount type=bind,source=${KOKORO_GFILE_DIR}/distdir,target=/distdir,readonly ${DOCKER_EXTRA_ARGS:-}"
ABSL_GOOGLETEST_DOWNLOAD_URL="file:///distdir/${ABSL_GOOGLETEST_COMMIT}.zip"
else
diff --git a/ci/linux_docker_containers.sh b/ci/linux_docker_containers.sh
index afad301e..1c29d9a1 100644
--- a/ci/linux_docker_containers.sh
+++ b/ci/linux_docker_containers.sh
@@ -15,7 +15,7 @@
# The file contains Docker container identifiers currently used by test scripts.
# Test scripts should source this file to get the identifiers.
-readonly LINUX_ALPINE_CONTAINER="gcr.io/google.com/absl-177019/alpine:20191016"
+readonly LINUX_ALPINE_CONTAINER="gcr.io/google.com/absl-177019/alpine:20201026"
readonly LINUX_CLANG_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20201008"
readonly LINUX_GCC_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20201008"
readonly LINUX_GCC_FLOOR_CONTAINER="gcr.io/google.com/absl-177019/linux_gcc-floor:20201015"