From f2c9c663db28a8a898c1fc8c8e06ab9b93eb5610 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 9 Sep 2020 19:13:17 -0700 Subject: Export of internal Abseil changes -- cfb567ed02096320663d882d2c0c2fb7db7af1e4 by Derek Mauro : Upgrade to GCC 10.2.0, Bazel 3.5.0, and CMake 3.18.2 PiperOrigin-RevId: 330847323 -- 5dcb9ce14d92315163079366a91c43cbd5184ea4 by Evan Brown : Optimize equal_range() by avoiding the call to upper_bound() when possible. We need to support heterogeneous comparators that have different behavior when comparing key_type to non-key_type. See the new test. Also update the comment for `key_compare_to_adapter`. PiperOrigin-RevId: 330794444 -- 744405dbda5513527d74094a5c3b9db1e0927693 by Gennadiy Rozental : Introduce trampoline for friend access to avoid friending routines and classes from different namespace. PiperOrigin-RevId: 330773156 -- a195d1226576f8a7bb5671f3e42d1021b827fad9 by Abseil Team : Fix an incorrect version number test for std::variant availability in tvOs. PiperOrigin-RevId: 330759480 -- 58b02eb9159a577953676d9928cb26b30068b847 by Derek Mauro : Use c++20 instead of c++2a now that it is supported by GCC PiperOrigin-RevId: 330559797 GitOrigin-RevId: cfb567ed02096320663d882d2c0c2fb7db7af1e4 Change-Id: I0e0d68409c95da42f5609920155ba5694ade8df0 --- absl/base/config.h | 4 +-- absl/container/btree_test.cc | 34 +++++++++++++++++++ absl/container/internal/btree.h | 54 +++++++++++++++++++++++++------ absl/container/internal/btree_container.h | 2 ++ absl/flags/flag.h | 20 ++++++++---- absl/flags/internal/flag.h | 38 ++++++++++++---------- ci/linux_docker_containers.sh | 4 +-- ci/linux_gcc-latest_libstdcxx_bazel.sh | 2 +- ci/linux_gcc-latest_libstdcxx_cmake.sh | 2 +- 9 files changed, 121 insertions(+), 39 deletions(-) diff --git a/absl/base/config.h b/absl/base/config.h index b1e095d3..c1d0494e 100644 --- a/absl/base/config.h +++ b/absl/base/config.h @@ -474,9 +474,9 @@ static_assert(ABSL_INTERNAL_INLINE_NAMESPACE_STR[0] != 'h' || (defined(__ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__) && \ __ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__ < 120000) || \ (defined(__ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__ < 120000) || \ + __ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__ < 50000) || \ (defined(__ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__ < 50000)) + __ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__ < 120000)) #define ABSL_INTERNAL_APPLE_CXX17_TYPES_UNAVAILABLE 1 #else #define ABSL_INTERNAL_APPLE_CXX17_TYPES_UNAVAILABLE 0 diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index 43704206..1bfa0c20 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -2580,6 +2580,40 @@ TEST(Btree, NodeHandleMutableKeyAccess) { } #endif +struct MultiKey { + int i1; + int i2; +}; + +struct MultiKeyComp { + using is_transparent = void; + bool operator()(const MultiKey a, const MultiKey b) const { + if (a.i1 != b.i1) return a.i1 < b.i1; + return a.i2 < b.i2; + } + bool operator()(const int a, const MultiKey b) const { return a < b.i1; } + 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 set; + + for (int i = 0; i < 100; ++i) { + for (int j = 0; j < 100; ++j) { + set.insert({i, j}); + } + } + + for (int i = 0; i < 100; ++i) { + auto equal_range = set.equal_range(i); + EXPECT_EQ(equal_range.first->i1, i); + EXPECT_EQ(equal_range.first->i2, 0); + EXPECT_EQ(std::distance(equal_range.first, equal_range.second), 100) << i; + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 5986bb21..002ccc1e 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -137,15 +137,14 @@ struct StringBtreeDefaultGreater { }; // A helper class to convert a boolean comparison into a three-way "compare-to" -// comparison that returns a negative value to indicate less-than, zero to -// indicate equality and a positive value to indicate greater-than. This helper +// comparison that returns an `absl::weak_ordering`. This helper // class is specialized for less, greater, // less, greater, less, and // greater. // // key_compare_to_adapter is provided so that btree users // automatically get the more efficient compare-to code when using common -// google string types with common comparison functors. +// Abseil string types with common comparison functors. // These string-like specializations also turn on heterogeneous lookup by // default. template @@ -189,6 +188,9 @@ struct common_params { // If Compare is a common comparator for a string-like type, then we adapt it // to use heterogeneous lookup and to be a key-compare-to comparator. using key_compare = typename key_compare_to_adapter::type; + // True when key_compare has been adapted to StringBtreeDefault{Less,Greater}. + using is_key_compare_adapted = + absl::negation>; // A type which indicates if we have a key-compare-to functor or a plain old // key-compare functor. using is_key_compare_to = btree_is_key_compare_to; @@ -1015,6 +1017,8 @@ class btree { using is_key_compare_to = typename Params::is_key_compare_to; using init_type = typename Params::init_type; using field_type = typename node_type::field_type; + using is_multi_container = typename Params::is_multi_container; + using is_key_compare_adapted = typename Params::is_key_compare_adapted; // We use a static empty node for the root/leftmost/rightmost of empty btrees // in order to avoid branching in begin()/end(). @@ -1164,15 +1168,13 @@ class btree { } // Finds the range of values which compare equal to key. The first member of - // the returned pair is equal to lower_bound(key). The second member pair of - // the pair is equal to upper_bound(key). + // the returned pair is equal to lower_bound(key). The second member of the + // pair is equal to upper_bound(key). template - std::pair equal_range(const K &key) { - return {lower_bound(key), upper_bound(key)}; - } + std::pair equal_range(const K &key); template std::pair equal_range(const K &key) const { - return {lower_bound(key), upper_bound(key)}; + return const_cast(this)->equal_range(key); } // Inserts a value into the btree only if it does not already exist. The @@ -1890,6 +1892,40 @@ btree

::btree(const btree &other) copy_or_move_values_in_order(&other); } +template +template +auto btree

::equal_range(const K &key) -> std::pair { + 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 iterator next = std::next(lower); + // When the comparator is heterogeneous, we can't assume that comparison with + // non-`key_type` will be equivalent to `key_type` comparisons so there + // could be multiple equivalent keys even in a unique-container. But for + // heterogeneous comparisons from the default string adapted comparators, we + // don't need to worry about this. + if (!is_multi_container::value && + (std::is_same::value || is_key_compare_adapted::value)) { + // The next iterator after lower must point to a key greater than `key`. + // Note: if this assert fails, then it may indicate that the comparator does + // not meet the equivalence requirements for Compare + // (see https://en.cppreference.com/w/cpp/named_req/Compare). + assert(next == end() || compare_keys(key, next.key())); + return {lower, next}; + } + // 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. + 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) + // behavior if we were to iterate over equal keys. + return {lower, upper_bound(key)}; +} + template template auto btree

::insert_unique(const K &key, Args &&... args) diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index 3b2e8a9e..137614f8 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h @@ -314,6 +314,8 @@ class btree_set_container : public btree_container { } // Deletion routines. + // TODO(ezb): we should support heterogeneous comparators that have different + // behavior for K!=key_type. template size_type erase(const key_arg &key) { return this->tree_.erase_unique(key); diff --git a/absl/flags/flag.h b/absl/flags/flag.h index cdac545b..a9cb2b79 100644 --- a/absl/flags/flag.h +++ b/absl/flags/flag.h @@ -144,11 +144,17 @@ class Flag { inline bool IsOfType() const { return GetImpl().template IsOfType(); } - T Get() const { return GetImpl().Get(); } - void Set(const T& v) { GetImpl().Set(v); } + T Get() const { + return flags_internal::FlagImplPeer::InvokeGet(GetImpl()); + } + void Set(const T& v) { + flags_internal::FlagImplPeer::InvokeSet(GetImpl(), v); + } void InvokeCallback() { GetImpl().InvokeCallback(); } - const CommandLineFlag& Reflect() const { return GetImpl().Reflect(); } + const CommandLineFlag& Reflect() const { + return flags_internal::FlagImplPeer::InvokeReflect(GetImpl()); + } // The data members are logically private, but they need to be public for // this to be an aggregate type. @@ -180,7 +186,7 @@ class Flag { // std::string first_name = absl::GetFlag(FLAGS_firstname); template ABSL_MUST_USE_RESULT T GetFlag(const absl::Flag& flag) { - return flag.Get(); + return flags_internal::FlagImplPeer::InvokeGet(flag); } // SetFlag() @@ -192,7 +198,7 @@ ABSL_MUST_USE_RESULT T GetFlag(const absl::Flag& flag) { // but especially within performance-critical code. template void SetFlag(absl::Flag* flag, const T& v) { - flag->Set(v); + flags_internal::FlagImplPeer::InvokeSet(*flag, v); } // Overload of `SetFlag()` to allow callers to pass in a value that is @@ -201,7 +207,7 @@ void SetFlag(absl::Flag* flag, const T& v) { template void SetFlag(absl::Flag* flag, const V& v) { T value(v); - flag->Set(value); + flags_internal::FlagImplPeer::InvokeSet(*flag, value); } // GetFlagReflectionHandle() @@ -216,7 +222,7 @@ void SetFlag(absl::Flag* flag, const V& v) { template const CommandLineFlag& GetFlagReflectionHandle(const absl::Flag& f) { - return f.Reflect(); + return flags_internal::FlagImplPeer::InvokeReflect(f); } ABSL_NAMESPACE_END diff --git a/absl/flags/internal/flag.h b/absl/flags/internal/flag.h index 89e43ad7..370d8a02 100644 --- a/absl/flags/internal/flag.h +++ b/absl/flags/internal/flag.h @@ -632,20 +632,9 @@ class Flag { std::string CurrentValue() const { return impl_.CurrentValue(); } private: - template + template friend class FlagRegistrar; - -#if !defined(_MSC_VER) || defined(__clang__) - template - friend U absl::GetFlag(const flags_internal::Flag& flag); - template - friend void absl::SetFlag(flags_internal::Flag* flag, const U& v); - template - friend void absl::SetFlag(flags_internal::Flag* flag, const V& v); -#else - template - friend class absl::Flag; -#endif + friend class FlagImplPeer; T Get() const { // See implementation notes in CommandLineFlag::Get(). @@ -668,10 +657,6 @@ class Flag { impl_.Write(&v); } - template - friend const CommandLineFlag& absl::GetFlagReflectionHandle( - const absl::Flag& f); - // Access to the reflection. const CommandLineFlag& Reflect() const { return impl_; } @@ -683,6 +668,25 @@ class Flag { FlagValue value_; }; +/////////////////////////////////////////////////////////////////////////////// +// Trampoline for friend access + +class FlagImplPeer { + public: + template + static T InvokeGet(const FlagType& flag) { + return flag.Get(); + } + template + static void InvokeSet(FlagType& flag, const T& v) { + flag.Set(v); + } + template + static const CommandLineFlag& InvokeReflect(const FlagType& f) { + return f.Reflect(); + } +}; + /////////////////////////////////////////////////////////////////////////////// // Implementation of Flag value specific operations routine. template diff --git a/ci/linux_docker_containers.sh b/ci/linux_docker_containers.sh index 483ce2a2..e42fa58b 100644 --- a/ci/linux_docker_containers.sh +++ b/ci/linux_docker_containers.sh @@ -16,6 +16,6 @@ # Test scripts should source this file to get the identifiers. readonly LINUX_ALPINE_CONTAINER="gcr.io/google.com/absl-177019/alpine:20191016" -readonly LINUX_CLANG_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20200710" -readonly LINUX_GCC_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20200710" +readonly LINUX_CLANG_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20200909" +readonly LINUX_GCC_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20200909" readonly LINUX_GCC_49_CONTAINER="gcr.io/google.com/absl-177019/linux_gcc-4.9:20191018" diff --git a/ci/linux_gcc-latest_libstdcxx_bazel.sh b/ci/linux_gcc-latest_libstdcxx_bazel.sh index 3ec02262..cd15f710 100755 --- a/ci/linux_gcc-latest_libstdcxx_bazel.sh +++ b/ci/linux_gcc-latest_libstdcxx_bazel.sh @@ -25,7 +25,7 @@ if [[ -z ${ABSEIL_ROOT:-} ]]; then fi if [[ -z ${STD:-} ]]; then - STD="c++11 c++14 c++17 c++2a" + STD="c++11 c++14 c++17 c++20" fi if [[ -z ${COMPILATION_MODE:-} ]]; then diff --git a/ci/linux_gcc-latest_libstdcxx_cmake.sh b/ci/linux_gcc-latest_libstdcxx_cmake.sh index db5f6918..1ba02b26 100755 --- a/ci/linux_gcc-latest_libstdcxx_cmake.sh +++ b/ci/linux_gcc-latest_libstdcxx_cmake.sh @@ -27,7 +27,7 @@ if [[ -z ${ABSEIL_ROOT:-} ]]; then fi if [[ -z ${ABSL_CMAKE_CXX_STANDARDS:-} ]]; then - ABSL_CMAKE_CXX_STANDARDS="11 14 17" + ABSL_CMAKE_CXX_STANDARDS="11 14 17 20" fi if [[ -z ${ABSL_CMAKE_BUILD_TYPES:-} ]]; then -- cgit v1.2.3