summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-09-09 19:13:17 -0700
committerGravatar Derek Mauro <dmauro@google.com>2020-09-10 10:10:40 -0400
commitf2c9c663db28a8a898c1fc8c8e06ab9b93eb5610 (patch)
tree2a6917d880a84a4dc4c95d21ffed0a9fe07d470c /absl
parent3c8b5d7587dc8ecf730ce9996c89e156e408c3ed (diff)
Export of internal Abseil changes
-- cfb567ed02096320663d882d2c0c2fb7db7af1e4 by Derek Mauro <dmauro@google.com>: Upgrade to GCC 10.2.0, Bazel 3.5.0, and CMake 3.18.2 PiperOrigin-RevId: 330847323 -- 5dcb9ce14d92315163079366a91c43cbd5184ea4 by Evan Brown <ezb@google.com>: 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 <rogeeff@google.com>: Introduce trampoline for friend access to avoid friending routines and classes from different namespace. PiperOrigin-RevId: 330773156 -- a195d1226576f8a7bb5671f3e42d1021b827fad9 by Abseil Team <absl-team@google.com>: Fix an incorrect version number test for std::variant availability in tvOs. PiperOrigin-RevId: 330759480 -- 58b02eb9159a577953676d9928cb26b30068b847 by Derek Mauro <dmauro@google.com>: Use c++20 instead of c++2a now that it is supported by GCC PiperOrigin-RevId: 330559797 GitOrigin-RevId: cfb567ed02096320663d882d2c0c2fb7db7af1e4 Change-Id: I0e0d68409c95da42f5609920155ba5694ade8df0
Diffstat (limited to 'absl')
-rw-r--r--absl/base/config.h4
-rw-r--r--absl/container/btree_test.cc34
-rw-r--r--absl/container/internal/btree.h54
-rw-r--r--absl/container/internal/btree_container.h2
-rw-r--r--absl/flags/flag.h20
-rw-r--r--absl/flags/internal/flag.h38
6 files changed, 117 insertions, 35 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<MultiKey, MultiKeyComp> 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<std::string>, greater<std::string>,
// less<string_view>, greater<string_view>, less<absl::Cord>, and
// greater<absl::Cord>.
//
// 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 <typename Compare>
@@ -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<Compare>::type;
+ // True when key_compare has been adapted to StringBtreeDefault{Less,Greater}.
+ using is_key_compare_adapted =
+ absl::negation<std::is_same<key_compare, Compare>>;
// 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<key_compare, Key>;
@@ -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 <typename K>
- std::pair<iterator, iterator> equal_range(const K &key) {
- return {lower_bound(key), upper_bound(key)};
- }
+ std::pair<iterator, iterator> equal_range(const K &key);
template <typename K>
std::pair<const_iterator, const_iterator> equal_range(const K &key) const {
- return {lower_bound(key), upper_bound(key)};
+ return const_cast<btree *>(this)->equal_range(key);
}
// Inserts a value into the btree only if it does not already exist. The
@@ -1891,6 +1893,40 @@ btree<P>::btree(const btree &other)
}
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 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<K, key_type>::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 <typename P>
template <typename K, typename... Args>
auto btree<P>::insert_unique(const K &key, Args &&... args)
-> std::pair<iterator, bool> {
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<Tree> {
}
// 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);
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<U>();
}
- T Get() const { return GetImpl().Get(); }
- void Set(const T& v) { GetImpl().Set(v); }
+ T Get() const {
+ return flags_internal::FlagImplPeer::InvokeGet<T>(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 <typename T>
ABSL_MUST_USE_RESULT T GetFlag(const absl::Flag<T>& flag) {
- return flag.Get();
+ return flags_internal::FlagImplPeer::InvokeGet<T>(flag);
}
// SetFlag()
@@ -192,7 +198,7 @@ ABSL_MUST_USE_RESULT T GetFlag(const absl::Flag<T>& flag) {
// but especially within performance-critical code.
template <typename T>
void SetFlag(absl::Flag<T>* 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<T>* flag, const T& v) {
template <typename T, typename V>
void SetFlag(absl::Flag<T>* 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<T>* flag, const V& v) {
template <typename T>
const CommandLineFlag& GetFlagReflectionHandle(const absl::Flag<T>& 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 <typename U, bool do_register>
+ template <typename, bool>
friend class FlagRegistrar;
-
-#if !defined(_MSC_VER) || defined(__clang__)
- template <typename U>
- friend U absl::GetFlag(const flags_internal::Flag<U>& flag);
- template <typename U>
- friend void absl::SetFlag(flags_internal::Flag<U>* flag, const U& v);
- template <typename U, typename V>
- friend void absl::SetFlag(flags_internal::Flag<U>* flag, const V& v);
-#else
- template <typename U>
- 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 <typename U>
- friend const CommandLineFlag& absl::GetFlagReflectionHandle(
- const absl::Flag<U>& f);
-
// Access to the reflection.
const CommandLineFlag& Reflect() const { return impl_; }
@@ -684,6 +669,25 @@ class Flag {
};
///////////////////////////////////////////////////////////////////////////////
+// Trampoline for friend access
+
+class FlagImplPeer {
+ public:
+ template <typename T, typename FlagType>
+ static T InvokeGet(const FlagType& flag) {
+ return flag.Get();
+ }
+ template <typename FlagType, typename T>
+ static void InvokeSet(FlagType& flag, const T& v) {
+ flag.Set(v);
+ }
+ template <typename FlagType>
+ static const CommandLineFlag& InvokeReflect(const FlagType& f) {
+ return f.Reflect();
+ }
+};
+
+///////////////////////////////////////////////////////////////////////////////
// Implementation of Flag value specific operations routine.
template <typename T>
void* FlagOps(FlagOp op, const void* v1, void* v2, void* v3) {