diff options
| -rw-r--r-- | absl/container/btree_test.cc | 21 | ||||
| -rw-r--r-- | absl/container/internal/btree.h | 87 | ||||
| -rw-r--r-- | absl/container/internal/btree_container.h | 43 | ||||
| -rw-r--r-- | absl/strings/internal/charconv_bigint_test.cc | 55 | ||||
| -rwxr-xr-x | ci/cmake_common.sh | 2 | ||||
| -rw-r--r-- | ci/linux_docker_containers.sh | 2 |
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" |