diff --git a/absl/base/attributes.h b/absl/base/attributes.h index 00aad48..4ab6fa2 100644 --- a/absl/base/attributes.h +++ b/absl/base/attributes.h
@@ -136,9 +136,9 @@ // for further information. // The MinGW compiler doesn't complain about the weak attribute until the link // step, presumably because Windows doesn't use ELF binaries. -#if (ABSL_HAVE_ATTRIBUTE(weak) || \ - (defined(__GNUC__) && !defined(__clang__))) && \ - (!defined(_WIN32) || (defined(__clang__) && __clang_major__ < 9)) && \ +#if (ABSL_HAVE_ATTRIBUTE(weak) || \ + (defined(__GNUC__) && !defined(__clang__))) && \ + (!defined(_WIN32) || (defined(__clang__) && __clang_major__ >= 9)) && \ !defined(__MINGW32__) #undef ABSL_ATTRIBUTE_WEAK #define ABSL_ATTRIBUTE_WEAK __attribute__((weak)) @@ -312,7 +312,6 @@ __attribute__((section(#name))) __attribute__((noinline)) #endif - // ABSL_ATTRIBUTE_SECTION_VARIABLE // // Tells the compiler/linker to put a given variable into a section and define @@ -339,8 +338,8 @@ // a no-op on ELF but not on Mach-O. // #ifndef ABSL_DECLARE_ATTRIBUTE_SECTION_VARS -#define ABSL_DECLARE_ATTRIBUTE_SECTION_VARS(name) \ - extern char __start_##name[] ABSL_ATTRIBUTE_WEAK; \ +#define ABSL_DECLARE_ATTRIBUTE_SECTION_VARS(name) \ + extern char __start_##name[] ABSL_ATTRIBUTE_WEAK; \ extern char __stop_##name[] ABSL_ATTRIBUTE_WEAK #endif #ifndef ABSL_DEFINE_ATTRIBUTE_SECTION_VARS @@ -503,7 +502,7 @@ #define ABSL_XRAY_NEVER_INSTRUMENT [[clang::xray_never_instrument]] #if ABSL_HAVE_CPP_ATTRIBUTE(clang::xray_log_args) #define ABSL_XRAY_LOG_ARGS(N) \ - [[clang::xray_always_instrument, clang::xray_log_args(N)]] + [[clang::xray_always_instrument, clang::xray_log_args(N)]] #else #define ABSL_XRAY_LOG_ARGS(N) [[clang::xray_always_instrument]] #endif
diff --git a/absl/base/casts.h b/absl/base/casts.h index b16af23..bf100ef 100644 --- a/absl/base/casts.h +++ b/absl/base/casts.h
@@ -44,8 +44,12 @@ bool, sizeof(Dest) == sizeof(Source) && type_traits_internal::is_trivially_copyable<Source>::value && - type_traits_internal::is_trivially_copyable<Dest>::value && - std::is_default_constructible<Dest>::value> {}; + type_traits_internal::is_trivially_copyable<Dest>::value +#if !ABSL_HAVE_BUILTIN(__builtin_bit_cast) + && std::is_default_constructible<Dest>::value +#endif + > { +}; } // namespace internal_casts @@ -147,20 +151,26 @@ // introducing this undefined behavior (since the original value is never // accessed in the wrong way). // -// NOTE: The requirements here are stricter than the bit_cast of standard -// proposal P0476 due to the need for workarounds and lack of intrinsics. +// NOTE: The requirements here are more strict than the bit_cast of standard +// proposal P0476 when __builtin_bit_cast is not available. // Specifically, this implementation also requires `Dest` to be // default-constructible. template < typename Dest, typename Source, typename std::enable_if<internal_casts::is_bitcastable<Dest, Source>::value, int>::type = 0> +#if ABSL_HAVE_BUILTIN(__builtin_bit_cast) +inline constexpr Dest bit_cast(const Source& source) { + return __builtin_bit_cast(Dest, source); +} +#else inline Dest bit_cast(const Source& source) { Dest dest; memcpy(static_cast<void*>(std::addressof(dest)), static_cast<const void*>(std::addressof(source)), sizeof(dest)); return dest; } +#endif // NOTE: This overload is only picked if the requirements of bit_cast are // not met. It is therefore UB, but is provided temporarily as previous
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index 13cb818..b2c3d73 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc
@@ -15,6 +15,7 @@ #include "absl/container/btree_test.h" #include <cstdint> +#include <functional> #include <limits> #include <map> #include <memory> @@ -1344,38 +1345,34 @@ EXPECT_EQ(++it, range.second); } -template <typename Compare, typename K> -void AssertKeyCompareToAdapted() { - using Adapted = typename key_compare_to_adapter<Compare>::type; - static_assert(!std::is_same<Adapted, Compare>::value, - "key_compare_to_adapter should have adapted this comparator."); +template <typename Compare, typename Key> +void AssertKeyCompareStringAdapted() { + using Adapted = typename key_compare_adapter<Compare, Key>::type; static_assert( - std::is_same<absl::weak_ordering, - absl::result_of_t<Adapted(const K &, const K &)>>::value, - "Adapted comparator should be a key-compare-to comparator."); + std::is_same<Adapted, StringBtreeDefaultLess>::value || + std::is_same<Adapted, StringBtreeDefaultGreater>::value, + "key_compare_adapter should have string-adapted this comparator."); } -template <typename Compare, typename K> -void AssertKeyCompareToNotAdapted() { - using Unadapted = typename key_compare_to_adapter<Compare>::type; +template <typename Compare, typename Key> +void AssertKeyCompareNotStringAdapted() { + using Adapted = typename key_compare_adapter<Compare, Key>::type; static_assert( - std::is_same<Unadapted, Compare>::value, - "key_compare_to_adapter shouldn't have adapted this comparator."); - static_assert( - std::is_same<bool, - absl::result_of_t<Unadapted(const K &, const K &)>>::value, - "Un-adapted comparator should return bool."); + !std::is_same<Adapted, StringBtreeDefaultLess>::value && + !std::is_same<Adapted, StringBtreeDefaultGreater>::value, + "key_compare_adapter shouldn't have string-adapted this comparator."); } -TEST(Btree, KeyCompareToAdapter) { - AssertKeyCompareToAdapted<std::less<std::string>, std::string>(); - AssertKeyCompareToAdapted<std::greater<std::string>, std::string>(); - AssertKeyCompareToAdapted<std::less<absl::string_view>, absl::string_view>(); - AssertKeyCompareToAdapted<std::greater<absl::string_view>, - absl::string_view>(); - AssertKeyCompareToAdapted<std::less<absl::Cord>, absl::Cord>(); - AssertKeyCompareToAdapted<std::greater<absl::Cord>, absl::Cord>(); - AssertKeyCompareToNotAdapted<std::less<int>, int>(); - AssertKeyCompareToNotAdapted<std::greater<int>, int>(); +TEST(Btree, KeyCompareAdapter) { + AssertKeyCompareStringAdapted<std::less<std::string>, std::string>(); + AssertKeyCompareStringAdapted<std::greater<std::string>, std::string>(); + AssertKeyCompareStringAdapted<std::less<absl::string_view>, + absl::string_view>(); + AssertKeyCompareStringAdapted<std::greater<absl::string_view>, + absl::string_view>(); + AssertKeyCompareStringAdapted<std::less<absl::Cord>, absl::Cord>(); + AssertKeyCompareStringAdapted<std::greater<absl::Cord>, absl::Cord>(); + AssertKeyCompareNotStringAdapted<std::less<int>, int>(); + AssertKeyCompareNotStringAdapted<std::greater<int>, int>(); } TEST(Btree, RValueInsert) { @@ -1425,11 +1422,19 @@ EXPECT_EQ(tracker.swaps(), 0); } -// A btree set with a specific number of values per node. +template <typename Cmp> +struct CheckedCompareOptedOutCmp : Cmp, BtreeTestOnlyCheckedCompareOptOutBase { + using Cmp::Cmp; + CheckedCompareOptedOutCmp() {} + CheckedCompareOptedOutCmp(Cmp cmp) : Cmp(std::move(cmp)) {} // NOLINT +}; + +// A btree set with a specific number of values per node. Opt out of +// checked_compare so that we can expect exact numbers of comparisons. template <typename Key, int TargetValuesPerNode, typename Cmp = std::less<Key>> class SizedBtreeSet : public btree_set_container<btree< - set_params<Key, Cmp, std::allocator<Key>, + set_params<Key, CheckedCompareOptedOutCmp<Cmp>, std::allocator<Key>, BtreeNodePeer::GetTargetNodeSize<Key>(TargetValuesPerNode), /*Multi=*/false>>> { using Base = typename SizedBtreeSet::btree_set_container; @@ -2297,7 +2302,9 @@ }; using Cmp = decltype(cmp); - absl::btree_map<int, int, Cmp> m(cmp); + // Use a map that is opted out of key_compare being adapted so we can expect + // strict comparison call limits. + absl::btree_map<int, int, CheckedCompareOptedOutCmp<Cmp>> m(cmp); for (int i = 0; i < 128; ++i) { m.emplace(i, i); } @@ -2967,6 +2974,58 @@ absl::btree_set<MultiKey, MultiKeyComp> set = {{}, MultiKeyComp{}}; } +#ifndef NDEBUG +TEST(Btree, InvalidComparatorsCaught) { + { + struct ZeroAlwaysLessCmp { + bool operator()(int lhs, int rhs) const { + if (lhs == 0) return true; + return lhs < rhs; + } + }; + absl::btree_set<int, ZeroAlwaysLessCmp> set; + EXPECT_DEATH(set.insert({0, 1, 2}), "is_self_equivalent"); + } + { + struct ThreeWayAlwaysLessCmp { + absl::weak_ordering operator()(int, int) const { + return absl::weak_ordering::less; + } + }; + absl::btree_set<int, ThreeWayAlwaysLessCmp> set; + EXPECT_DEATH(set.insert({0, 1, 2}), "is_self_equivalent"); + } + { + struct SumGreaterZeroCmp { + bool operator()(int lhs, int rhs) const { + // First, do equivalence correctly - so we can test later condition. + if (lhs == rhs) return false; + return lhs + rhs > 0; + } + }; + absl::btree_set<int, SumGreaterZeroCmp> set; + // Note: '!' only needs to be escaped when it's the first character. + EXPECT_DEATH(set.insert({0, 1, 2}), + R"regex(\!lhs_comp_rhs \|\| !comp\(\)\(rhs, lhs\))regex"); + } + { + struct ThreeWaySumGreaterZeroCmp { + absl::weak_ordering operator()(int lhs, int rhs) const { + // First, do equivalence correctly - so we can test later condition. + if (lhs == rhs) return absl::weak_ordering::equivalent; + + if (lhs + rhs > 0) return absl::weak_ordering::less; + if (lhs + rhs == 0) return absl::weak_ordering::equivalent; + return absl::weak_ordering::greater; + } + }; + absl::btree_set<int, ThreeWaySumGreaterZeroCmp> set; + EXPECT_DEATH(set.insert({0, 1, 2}), + R"regex(lhs_comp_rhs < 0 -> rhs_comp_lhs > 0)regex"); + } +} +#endif + } // namespace } // namespace container_internal ABSL_NAMESPACE_END
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index f1c650c..0fb2ae6 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h
@@ -67,7 +67,7 @@ // // By default, `flat_hash_set` uses the `absl::Hash` hashing framework. All // fundamental and Abseil types that support the `absl::Hash` framework have a -// compatible equality operator for comparing insertions into `flat_hash_map`. +// compatible equality operator for comparing insertions into `flat_hash_set`. // If your type is not yet supported by the `absl::Hash` framework, see // absl/hash/hash.h for information on extending Abseil hashing to user-defined // types. @@ -106,7 +106,7 @@ public: // Constructors and Assignment Operators // - // A flat_hash_set supports the same overload set as `std::unordered_map` + // A flat_hash_set supports the same overload set as `std::unordered_set` // for construction and assignment: // // * Default constructor @@ -173,7 +173,7 @@ // available within the `flat_hash_set`. // // NOTE: this member function is particular to `absl::flat_hash_set` and is - // not provided in the `std::unordered_map` API. + // not provided in the `std::unordered_set` API. using Base::capacity; // flat_hash_set::empty() @@ -332,7 +332,7 @@ // flat_hash_set::swap(flat_hash_set& other) // // Exchanges the contents of this `flat_hash_set` with those of the `other` - // flat hash map, avoiding invocation of any move, copy, or swap operations on + // flat hash set, avoiding invocation of any move, copy, or swap operations on // individual elements. // // All iterators and references on the `flat_hash_set` remain valid, excepting @@ -340,7 +340,7 @@ // // `swap()` requires that the flat hash set's hashing and key equivalence // functions be Swappable, and are exchaged using unqualified calls to - // non-member `swap()`. If the map's allocator has + // non-member `swap()`. If the set's allocator has // `std::allocator_traits<allocator_type>::propagate_on_container_swap::value` // set to `true`, the allocators are also exchanged using an unqualified call // to non-member `swap()`; otherwise, the allocators are not swapped. @@ -395,14 +395,14 @@ // flat_hash_set::bucket_count() // // Returns the number of "buckets" within the `flat_hash_set`. Note that - // because a flat hash map contains all elements within its internal storage, + // because a flat hash set contains all elements within its internal storage, // this value simply equals the current capacity of the `flat_hash_set`. using Base::bucket_count; // flat_hash_set::load_factor() // // Returns the current load factor of the `flat_hash_set` (the average number - // of slots occupied with a value within the hash map). + // of slots occupied with a value within the hash set). using Base::load_factor; // flat_hash_set::max_load_factor()
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 26bd5e1..bbc319c 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h
@@ -74,12 +74,14 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { +template <typename Compare, typename T, typename U> +using compare_result_t = absl::result_of_t<const Compare(const T &, const U &)>; + // A helper class that indicates if the Compare parameter is a key-compare-to // comparator. template <typename Compare, typename T> using btree_is_key_compare_to = - std::is_convertible<absl::result_of_t<Compare(const T &, const T &)>, - absl::weak_ordering>; + std::is_convertible<compare_result_t<Compare, T, T>, absl::weak_ordering>; struct StringBtreeDefaultLess { using is_transparent = void; @@ -146,49 +148,140 @@ } }; -// A helper class to convert a boolean comparison into a three-way "compare-to" -// 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 -// Abseil string types with common comparison functors. -// These string-like specializations also turn on heterogeneous lookup by -// default. +// See below comments for checked_compare. +template <typename Compare, bool is_class = std::is_class<Compare>::value> +struct checked_compare_base : Compare { + using Compare::Compare; + explicit checked_compare_base(Compare c) : Compare(std::move(c)) {} + const Compare &comp() const { return *this; } +}; template <typename Compare> -struct key_compare_to_adapter { - using type = Compare; +struct checked_compare_base<Compare, false> { + explicit checked_compare_base(Compare c) : compare(std::move(c)) {} + const Compare &comp() const { return compare; } + Compare compare; +}; + +// A mechanism for opting out of checked_compare for use only in btree_test.cc. +struct BtreeTestOnlyCheckedCompareOptOutBase {}; + +// A helper class to adapt the specified comparator for two use cases: +// (1) When using common Abseil string types with common comparison functors, +// convert a boolean comparison into a three-way 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>. +// (2) Adapt the comparator to diagnose cases of non-strict-weak-ordering (see +// https://en.cppreference.com/w/cpp/named_req/Compare) in debug mode. Whenever +// a comparison is made, we will make assertions to verify that the comparator +// is valid. +template <typename Compare, typename Key> +struct key_compare_adapter { + // Inherit from checked_compare_base to support function pointers and also + // keep empty-base-optimization (EBO) support for classes. + // Note: we can't use CompressedTuple here because that would interfere + // with the EBO for `btree::root_`. `btree::root_` is itself a CompressedTuple + // and nested `CompressedTuple`s don't support EBO. + // TODO(b/214288561): use CompressedTuple instead once it supports EBO for + // nested `CompressedTuple`s. + struct checked_compare : checked_compare_base<Compare> { + private: + using Base = typename checked_compare::checked_compare_base; + using Base::comp; + + // If possible, returns whether `t` is equivalent to itself. We can only do + // this for `Key`s because we can't be sure that it's safe to call + // `comp()(k, k)` otherwise. Even if SFINAE allows it, there could be a + // compilation failure inside the implementation of the comparison operator. + bool is_self_equivalent(const Key &k) const { + // Note: this works for both boolean and three-way comparators. + return comp()(k, k) == 0; + } + // If we can't compare `t` with itself, returns true unconditionally. + template <typename T> + bool is_self_equivalent(const T &) const { + return true; + } + + public: + using Base::Base; + checked_compare(Compare comp) : Base(std::move(comp)) {} // NOLINT + + // Allow converting to Compare for use in key_comp()/value_comp(). + explicit operator Compare() const { return comp(); } + + template <typename T, typename U, + absl::enable_if_t< + std::is_same<bool, compare_result_t<Compare, T, U>>::value, + int> = 0> + bool operator()(const T &lhs, const U &rhs) const { + // NOTE: if any of these assertions fail, then the comparator does not + // establish a strict-weak-ordering (see + // https://en.cppreference.com/w/cpp/named_req/Compare). + assert(is_self_equivalent(lhs)); + assert(is_self_equivalent(rhs)); + const bool lhs_comp_rhs = comp()(lhs, rhs); + assert(!lhs_comp_rhs || !comp()(rhs, lhs)); + return lhs_comp_rhs; + } + + template < + typename T, typename U, + absl::enable_if_t<std::is_convertible<compare_result_t<Compare, T, U>, + absl::weak_ordering>::value, + int> = 0> + absl::weak_ordering operator()(const T &lhs, const U &rhs) const { + // NOTE: if any of these assertions fail, then the comparator does not + // establish a strict-weak-ordering (see + // https://en.cppreference.com/w/cpp/named_req/Compare). + assert(is_self_equivalent(lhs)); + assert(is_self_equivalent(rhs)); + const absl::weak_ordering lhs_comp_rhs = comp()(lhs, rhs); +#ifndef NDEBUG + const absl::weak_ordering rhs_comp_lhs = comp()(rhs, lhs); + if (lhs_comp_rhs > 0) { + assert(rhs_comp_lhs < 0 && "lhs_comp_rhs > 0 -> rhs_comp_lhs < 0"); + } else if (lhs_comp_rhs == 0) { + assert(rhs_comp_lhs == 0 && "lhs_comp_rhs == 0 -> rhs_comp_lhs == 0"); + } else { + assert(rhs_comp_lhs > 0 && "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0"); + } +#endif + return lhs_comp_rhs; + } + }; + using type = absl::conditional_t< + std::is_base_of<BtreeTestOnlyCheckedCompareOptOutBase, Compare>::value, + Compare, checked_compare>; }; template <> -struct key_compare_to_adapter<std::less<std::string>> { +struct key_compare_adapter<std::less<std::string>, std::string> { using type = StringBtreeDefaultLess; }; template <> -struct key_compare_to_adapter<std::greater<std::string>> { +struct key_compare_adapter<std::greater<std::string>, std::string> { using type = StringBtreeDefaultGreater; }; template <> -struct key_compare_to_adapter<std::less<absl::string_view>> { +struct key_compare_adapter<std::less<absl::string_view>, absl::string_view> { using type = StringBtreeDefaultLess; }; template <> -struct key_compare_to_adapter<std::greater<absl::string_view>> { +struct key_compare_adapter<std::greater<absl::string_view>, absl::string_view> { using type = StringBtreeDefaultGreater; }; template <> -struct key_compare_to_adapter<std::less<absl::Cord>> { +struct key_compare_adapter<std::less<absl::Cord>, absl::Cord> { using type = StringBtreeDefaultLess; }; template <> -struct key_compare_to_adapter<std::greater<absl::Cord>> { +struct key_compare_adapter<std::greater<absl::Cord>, absl::Cord> { using type = StringBtreeDefaultGreater; }; @@ -224,6 +317,13 @@ T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>> : T::absl_btree_prefer_linear_node_search {}; +template <typename Compare, typename Key> +constexpr bool compare_has_valid_result_type() { + using compare_result_type = compare_result_t<Compare, Key, Key>; + return std::is_same<compare_result_type, bool>::value || + std::is_convertible<compare_result_type, absl::weak_ordering>::value; +} + template <typename Key, typename Compare, typename Alloc, int TargetNodeSize, bool Multi, typename SlotPolicy> struct common_params { @@ -231,7 +331,24 @@ // 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; + // We also adapt the comparator to diagnose invalid comparators in debug mode. + // We disable this when `Compare` is invalid in a way that will cause + // adaptation to fail (having invalid return type) so that we can give a + // better compilation failure in static_assert_validation. If we don't do + // this, then there will be cascading compilation failures that are confusing + // for users. + using key_compare = + absl::conditional_t<!compare_has_valid_result_type<Compare, Key>(), + Compare, + typename key_compare_adapter<Compare, Key>::type>; + + static constexpr bool kIsKeyCompareStringAdapted = + std::is_same<key_compare, StringBtreeDefaultLess>::value || + std::is_same<key_compare, StringBtreeDefaultGreater>::value; + static constexpr bool kIsKeyCompareTransparent = + IsTransparent<original_key_compare>::value || + kIsKeyCompareStringAdapted; + // 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>; @@ -260,11 +377,9 @@ // that we know has the same equivalence classes for all lookup types. template <typename LookupKey> constexpr static bool can_have_multiple_equivalent_keys() { - return Multi || - (IsTransparent<key_compare>::value && - !std::is_same<LookupKey, Key>::value && - !std::is_same<key_compare, StringBtreeDefaultLess>::value && - !std::is_same<key_compare, StringBtreeDefaultGreater>::value); + return Multi || (IsTransparent<key_compare>::value && + !std::is_same<LookupKey, Key>::value && + !kIsKeyCompareStringAdapted); } enum { @@ -366,6 +481,7 @@ using field_type = typename Params::node_count_type; using allocator_type = typename Params::allocator_type; using slot_type = typename Params::slot_type; + using original_key_compare = typename Params::original_key_compare; public: using params_type = Params; @@ -387,15 +503,15 @@ // - Otherwise, choose binary. // TODO(ezb): Might make sense to add condition(s) based on node-size. using use_linear_search = std::integral_constant< - bool, - has_linear_node_search_preference<key_compare>::value - ? prefers_linear_node_search<key_compare>::value - : has_linear_node_search_preference<key_type>::value + bool, has_linear_node_search_preference<original_key_compare>::value + ? prefers_linear_node_search<original_key_compare>::value + : has_linear_node_search_preference<key_type>::value ? prefers_linear_node_search<key_type>::value : std::is_arithmetic<key_type>::value && - (std::is_same<std::less<key_type>, key_compare>::value || + (std::is_same<std::less<key_type>, + original_key_compare>::value || std::is_same<std::greater<key_type>, - key_compare>::value)>; + original_key_compare>::value)>; // This class is organized by absl::container_internal::Layout as if it had // the following structure: @@ -1821,11 +1937,8 @@ "target node size too large"); // Verify that key_compare returns an absl::{weak,strong}_ordering or bool. - using compare_result_type = - absl::result_of_t<key_compare(key_type, key_type)>; static_assert( - std::is_same<compare_result_type, bool>::value || - std::is_convertible<compare_result_type, absl::weak_ordering>::value, + compare_has_valid_result_type<key_compare, key_type>(), "key comparison function must return absl::{weak,strong}_ordering or " "bool.");
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index d28b244..bae5c6e 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h
@@ -44,8 +44,8 @@ // transparent case. template <class K> using key_arg = - typename KeyArg<IsTransparent<typename Tree::key_compare>::value>:: - template type<K, typename Tree::key_type>; + typename KeyArg<params_type::kIsKeyCompareTransparent>::template type< + K, typename Tree::key_type>; public: using key_type = typename Tree::key_type;
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 1d24db5..322e054 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc
@@ -27,6 +27,7 @@ #include "absl/profiling/internal/exponential_biased.h" #include "absl/profiling/internal/sample_recorder.h" #include "absl/synchronization/mutex.h" +#include "absl/utility/utility.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -53,7 +54,7 @@ } // namespace #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample = 0; +ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample = {0, 0}; #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) HashtablezSampler& GlobalHashtablezSampler() { @@ -64,7 +65,8 @@ HashtablezInfo::HashtablezInfo() = default; HashtablezInfo::~HashtablezInfo() = default; -void HashtablezInfo::PrepareForSampling(size_t inline_element_size_value) { +void HashtablezInfo::PrepareForSampling(int64_t stride, + size_t inline_element_size_value) { capacity.store(0, std::memory_order_relaxed); size.store(0, std::memory_order_relaxed); num_erases.store(0, std::memory_order_relaxed); @@ -77,6 +79,7 @@ max_reserve.store(0, std::memory_order_relaxed); create_time = absl::Now(); + weight = stride; // The inliner makes hardcoded skip_count difficult (especially when combined // with LTO). We use the ability to exclude stacks by regex when encoding // instead. @@ -105,23 +108,32 @@ return state == kForce; } -HashtablezInfo* SampleSlow(int64_t* next_sample, size_t inline_element_size) { +HashtablezInfo* SampleSlow(SamplingState& next_sample, + size_t inline_element_size) { if (ABSL_PREDICT_FALSE(ShouldForceSampling())) { - *next_sample = 1; + next_sample.next_sample = 1; + const int64_t old_stride = exchange(next_sample.sample_stride, 1); HashtablezInfo* result = - GlobalHashtablezSampler().Register(inline_element_size); + GlobalHashtablezSampler().Register(old_stride, inline_element_size); return result; } #if !defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) - *next_sample = std::numeric_limits<int64_t>::max(); + next_sample = { + std::numeric_limits<int64_t>::max(), + std::numeric_limits<int64_t>::max(), + }; return nullptr; #else - bool first = *next_sample < 0; - *next_sample = g_exponential_biased_generator.GetStride( + bool first = next_sample.next_sample < 0; + + const int64_t next_stride = g_exponential_biased_generator.GetStride( g_hashtablez_sample_parameter.load(std::memory_order_relaxed)); + + next_sample.next_sample = next_stride; + const int64_t old_stride = exchange(next_sample.sample_stride, next_stride); // Small values of interval are equivalent to just sampling next time. - ABSL_ASSERT(*next_sample >= 1); + ABSL_ASSERT(next_stride >= 1); // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold // low enough that we will start sampling in a reasonable time, so we just use @@ -131,11 +143,11 @@ // We will only be negative on our first count, so we should just retry in // that case. if (first) { - if (ABSL_PREDICT_TRUE(--*next_sample > 0)) return nullptr; + if (ABSL_PREDICT_TRUE(--next_sample.next_sample > 0)) return nullptr; return SampleSlow(next_sample, inline_element_size); } - return GlobalHashtablezSampler().Register(inline_element_size); + return GlobalHashtablezSampler().Register(old_stride, inline_element_size); #endif }
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h index 6738786..e7c204e 100644 --- a/absl/container/internal/hashtablez_sampler.h +++ b/absl/container/internal/hashtablez_sampler.h
@@ -67,7 +67,7 @@ // Puts the object into a clean state, fills in the logically `const` members, // blocking for any readers that are currently sampling the object. - void PrepareForSampling(size_t inline_element_size_value) + void PrepareForSampling(int64_t stride, size_t inline_element_size_value) ABSL_EXCLUSIVE_LOCKS_REQUIRED(init_mu); // These fields are mutated by the various Record* APIs and need to be @@ -145,7 +145,15 @@ std::memory_order_relaxed); } -HashtablezInfo* SampleSlow(int64_t* next_sample, size_t inline_element_size); +struct SamplingState { + int64_t next_sample; + // When we make a sampling decision, we record that distance so we can weight + // each sample. + int64_t sample_stride; +}; + +HashtablezInfo* SampleSlow(SamplingState& next_sample, + size_t inline_element_size); void UnsampleSlow(HashtablezInfo* info); #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) @@ -235,7 +243,7 @@ #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -extern ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample; +extern ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample; #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) // Returns an RAII sampling handle that manages registration and unregistation @@ -243,11 +251,11 @@ inline HashtablezInfoHandle Sample( size_t inline_element_size ABSL_ATTRIBUTE_UNUSED) { #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) - if (ABSL_PREDICT_TRUE(--global_next_sample > 0)) { + if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) { return HashtablezInfoHandle(nullptr); } return HashtablezInfoHandle( - SampleSlow(&global_next_sample, inline_element_size)); + SampleSlow(global_next_sample, inline_element_size)); #else return HashtablezInfoHandle(nullptr); #endif // !ABSL_PER_THREAD_TLS
diff --git a/absl/container/internal/hashtablez_sampler_test.cc b/absl/container/internal/hashtablez_sampler_test.cc index ac6ed9b..77cdf2f 100644 --- a/absl/container/internal/hashtablez_sampler_test.cc +++ b/absl/container/internal/hashtablez_sampler_test.cc
@@ -70,8 +70,9 @@ } HashtablezInfo* Register(HashtablezSampler* s, size_t size) { + const int64_t test_stride = 123; const size_t test_element_size = 17; - auto* info = s->Register(test_element_size); + auto* info = s->Register(test_stride, test_element_size); assert(info != nullptr); info->size.store(size); return info; @@ -79,10 +80,11 @@ TEST(HashtablezInfoTest, PrepareForSampling) { absl::Time test_start = absl::Now(); + const int64_t test_stride = 123; const size_t test_element_size = 17; HashtablezInfo info; absl::MutexLock l(&info.init_mu); - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride, test_element_size); EXPECT_EQ(info.capacity.load(), 0); EXPECT_EQ(info.size.load(), 0); @@ -95,6 +97,7 @@ EXPECT_EQ(info.hashes_bitwise_xor.load(), 0); EXPECT_EQ(info.max_reserve.load(), 0); EXPECT_GE(info.create_time, test_start); + EXPECT_EQ(info.weight, test_stride); EXPECT_EQ(info.inline_element_size, test_element_size); info.capacity.store(1, std::memory_order_relaxed); @@ -108,7 +111,7 @@ info.max_reserve.store(1, std::memory_order_relaxed); info.create_time = test_start - absl::Hours(20); - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride * 2, test_element_size); EXPECT_EQ(info.capacity.load(), 0); EXPECT_EQ(info.size.load(), 0); EXPECT_EQ(info.num_erases.load(), 0); @@ -119,6 +122,7 @@ EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{}); EXPECT_EQ(info.hashes_bitwise_xor.load(), 0); EXPECT_EQ(info.max_reserve.load(), 0); + EXPECT_EQ(info.weight, 2 * test_stride); EXPECT_EQ(info.inline_element_size, test_element_size); EXPECT_GE(info.create_time, test_start); } @@ -126,8 +130,9 @@ TEST(HashtablezInfoTest, RecordStorageChanged) { HashtablezInfo info; absl::MutexLock l(&info.init_mu); + const int64_t test_stride = 21; const size_t test_element_size = 19; - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride, test_element_size); RecordStorageChangedSlow(&info, 17, 47); EXPECT_EQ(info.size.load(), 17); EXPECT_EQ(info.capacity.load(), 47); @@ -139,8 +144,9 @@ TEST(HashtablezInfoTest, RecordInsert) { HashtablezInfo info; absl::MutexLock l(&info.init_mu); + const int64_t test_stride = 25; const size_t test_element_size = 23; - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride, test_element_size); EXPECT_EQ(info.max_probe_length.load(), 0); RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength); EXPECT_EQ(info.max_probe_length.load(), 6); @@ -160,10 +166,11 @@ } TEST(HashtablezInfoTest, RecordErase) { + const int64_t test_stride = 31; const size_t test_element_size = 29; HashtablezInfo info; absl::MutexLock l(&info.init_mu); - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride, test_element_size); EXPECT_EQ(info.num_erases.load(), 0); EXPECT_EQ(info.size.load(), 0); RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength); @@ -175,10 +182,11 @@ } TEST(HashtablezInfoTest, RecordRehash) { + const int64_t test_stride = 33; const size_t test_element_size = 31; HashtablezInfo info; absl::MutexLock l(&info.init_mu); - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride, test_element_size); RecordInsertSlow(&info, 0x1, 0); RecordInsertSlow(&info, 0x2, kProbeLength); RecordInsertSlow(&info, 0x4, kProbeLength); @@ -203,8 +211,9 @@ TEST(HashtablezInfoTest, RecordReservation) { HashtablezInfo info; absl::MutexLock l(&info.init_mu); + const int64_t test_stride = 35; const size_t test_element_size = 33; - info.PrepareForSampling(test_element_size); + info.PrepareForSampling(test_stride, test_element_size); RecordReservationSlow(&info, 3); EXPECT_EQ(info.max_reserve.load(), 3); @@ -224,9 +233,10 @@ SetHashtablezSampleParameter(100); for (int i = 0; i < 1000; ++i) { - int64_t next_sample = 0; - HashtablezInfo* sample = SampleSlow(&next_sample, test_element_size); - EXPECT_GT(next_sample, 0); + SamplingState next_sample = {0, 0}; + HashtablezInfo* sample = SampleSlow(next_sample, test_element_size); + EXPECT_GT(next_sample.next_sample, 0); + EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride); EXPECT_NE(sample, nullptr); UnsampleSlow(sample); } @@ -238,9 +248,10 @@ SetHashtablezSampleParameter(std::numeric_limits<int32_t>::max()); for (int i = 0; i < 1000; ++i) { - int64_t next_sample = 0; - HashtablezInfo* sample = SampleSlow(&next_sample, test_element_size); - EXPECT_GT(next_sample, 0); + SamplingState next_sample = {0, 0}; + HashtablezInfo* sample = SampleSlow(next_sample, test_element_size); + EXPECT_GT(next_sample.next_sample, 0); + EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride); EXPECT_NE(sample, nullptr); UnsampleSlow(sample); } @@ -267,14 +278,16 @@ TEST(HashtablezSamplerTest, Handle) { auto& sampler = GlobalHashtablezSampler(); + const int64_t test_stride = 41; const size_t test_element_size = 39; - HashtablezInfoHandle h(sampler.Register(test_element_size)); + HashtablezInfoHandle h(sampler.Register(test_stride, test_element_size)); auto* info = HashtablezInfoHandlePeer::GetInfo(&h); info->hashes_bitwise_and.store(0x12345678, std::memory_order_relaxed); bool found = false; sampler.Iterate([&](const HashtablezInfo& h) { if (&h == info) { + EXPECT_EQ(h.weight, test_stride); EXPECT_EQ(h.hashes_bitwise_and.load(), 0x12345678); found = true; } @@ -340,19 +353,20 @@ ThreadPool pool(10); for (int i = 0; i < 10; ++i) { + const int64_t sampling_stride = 11 + i % 3; const size_t elt_size = 10 + i % 2; - pool.Schedule([&sampler, &stop, elt_size]() { + pool.Schedule([&sampler, &stop, sampling_stride, elt_size]() { std::random_device rd; std::mt19937 gen(rd()); std::vector<HashtablezInfo*> infoz; while (!stop.HasBeenNotified()) { if (infoz.empty()) { - infoz.push_back(sampler.Register(elt_size)); + infoz.push_back(sampler.Register(sampling_stride, elt_size)); } switch (std::uniform_int_distribution<>(0, 2)(gen)) { case 0: { - infoz.push_back(sampler.Register(elt_size)); + infoz.push_back(sampler.Register(sampling_stride, elt_size)); break; } case 1: { @@ -361,6 +375,7 @@ HashtablezInfo* info = infoz[p]; infoz[p] = infoz.back(); infoz.pop_back(); + EXPECT_EQ(info->weight, sampling_stride); sampler.Unregister(info); break; }
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 1157d25..93a3fa8 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1539,6 +1539,14 @@ return !(a == b); } + template <typename H> + friend typename std::enable_if<H::template is_hashable<value_type>::value, + H>::type + AbslHashValue(H h, const raw_hash_set& s) { + return H::combine(H::combine_unordered(std::move(h), s.begin(), s.end()), + s.size()); + } + friend void swap(raw_hash_set& a, raw_hash_set& b) noexcept(noexcept(a.swap(b))) { a.swap(b);
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 362b3ca..47015bc 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1244,7 +1244,7 @@ case 16: if (kRandomizesInserts) { return {0.1, - 1.0, + 2.0, {{0.95, 0.1}}, {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}}; } else { @@ -1258,7 +1258,7 @@ return {}; } -TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) { +TEST(Table, EnsureNonQuadraticTopNXorSeedByProbeSeqLength) { ProbeStatsPerSize stats; std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10}; for (size_t size : sizes) { @@ -1330,17 +1330,17 @@ {{0.95, 0.3}}, {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}}; } else { - return {0.15, - 0.5, - {{0.95, 0.3}}, - {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}}; + return {0.4, + 0.6, + {{0.95, 0.5}}, + {{0.95, 1}, {0.99, 14}, {0.999, 23}, {0.9999, 26}}}; } case 16: if (kRandomizesInserts) { return {0.1, 0.4, {{0.95, 0.3}}, - {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}}; + {{0.95, 1}, {0.99, 2}, {0.999, 9}, {0.9999, 15}}}; } else { return {0.05, 0.2, @@ -1352,7 +1352,7 @@ return {}; } -TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) { +TEST(Table, EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) { ProbeStatsPerSize stats; std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10}; for (size_t size : sizes) {
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index f0640d3..bcc316f 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel
@@ -41,6 +41,7 @@ "//absl/base:core_headers", "//absl/base:endian", "//absl/container:fixed_array", + "//absl/functional:function_ref", "//absl/meta:type_traits", "//absl/numeric:int128", "//absl/strings", @@ -74,7 +75,11 @@ ":hash_testing", ":spy_hash_state", "//absl/base:core_headers", + "//absl/container:btree", + "//absl/container:flat_hash_map", "//absl/container:flat_hash_set", + "//absl/container:node_hash_map", + "//absl/container:node_hash_set", "//absl/meta:type_traits", "//absl/numeric:int128", "//absl/strings:cord_test_helpers", @@ -93,6 +98,7 @@ deps = [ ":hash", "//absl/base:core_headers", + "//absl/container:flat_hash_set", "//absl/random", "//absl/strings", "//absl/strings:cord",
diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt index 5916ae3..34434fa 100644 --- a/absl/hash/CMakeLists.txt +++ b/absl/hash/CMakeLists.txt
@@ -30,6 +30,7 @@ absl::core_headers absl::endian absl::fixed_array + absl::function_ref absl::meta absl::int128 absl::strings @@ -68,7 +69,11 @@ absl::hash absl::hash_testing absl::core_headers + absl::btree + absl::flat_hash_map absl::flat_hash_set + absl::node_hash_map + absl::node_hash_set absl::spy_hash_state absl::meta absl::int128
diff --git a/absl/hash/hash.h b/absl/hash/hash.h index 8282ea5..f31fde4 100644 --- a/absl/hash/hash.h +++ b/absl/hash/hash.h
@@ -26,9 +26,9 @@ // support Abseil hashing without requiring you to define a hashing // algorithm. // * `HashState`, a type-erased class which implements the manipulation of the -// hash state (H) itself, contains member functions `combine()` and -// `combine_contiguous()`, which you can use to contribute to an existing -// hash state when hashing your types. +// hash state (H) itself; contains member functions `combine()`, +// `combine_contiguous()`, and `combine_unordered()`; and which you can use +// to contribute to an existing hash state when hashing your types. // // Unlike `std::hash` or other hashing frameworks, the Abseil hashing framework // provides most of its utility by abstracting away the hash algorithm (and its @@ -74,7 +74,9 @@ #define ABSL_HASH_HASH_H_ #include <tuple> +#include <utility> +#include "absl/functional/function_ref.h" #include "absl/hash/internal/hash.h" namespace absl { @@ -107,14 +109,27 @@ // * std::string_view (as well as any instance of std::basic_string that // uses char and std::char_traits) // * All the standard sequence containers (provided the elements are hashable) -// * All the standard ordered associative containers (provided the elements are +// * All the standard associative containers (provided the elements are // hashable) // * absl types such as the following: // * absl::string_view -// * absl::InlinedVector -// * absl::FixedArray // * absl::uint128 // * absl::Time, absl::Duration, and absl::TimeZone +// * absl containers (provided the elements are hashable) such as the +// following: +// * absl::flat_hash_set, absl::node_hash_set, absl::btree_set +// * absl::flat_hash_map, absl::node_hash_map, absl::btree_map +// * absl::btree_multiset, absl::btree_multimap +// * absl::InlinedVector +// * absl::FixedArray +// +// When absl::Hash is used to hash an unordered container with a custom hash +// functor, the elements are hashed using default absl::Hash semantics, not +// the custom hash functor. This is consistent with the behavior of +// operator==() on unordered containers, which compares elements pairwise with +// operator==() rather than the custom equality functor. It is usually a +// mistake to use either operator==() or absl::Hash on unordered collections +// that use functors incompatible with operator==() equality. // // Note: the list above is not meant to be exhaustive. Additional type support // may be added, in which case the above list will be updated. @@ -153,7 +168,8 @@ // that are otherwise difficult to extend using `AbslHashValue()`. (See the // `HashState` class below.) // -// The "hash state" concept contains two member functions for mixing hash state: +// The "hash state" concept contains three member functions for mixing hash +// state: // // * `H::combine(state, values...)` // @@ -187,6 +203,15 @@ // (it may perform internal optimizations). If you need this guarantee, use a // loop instead. // +// * `H::combine_unordered(state, begin, end)` +// +// Combines a set of elements denoted by an iterator pair into a hash +// state, returning the updated state. Note that the existing hash +// state is move-only and must be passed by value. +// +// Unlike the other two methods, the hashing is order-independent. +// This can be used to hash unordered collections. +// // ----------------------------------------------------------------------------- // Adding Type Support to `absl::Hash` // ----------------------------------------------------------------------------- @@ -243,8 +268,9 @@ // classes, virtual functions, etc.). The type erasure adds overhead so it // should be avoided unless necessary. // -// Note: This wrapper will only erase calls to: +// Note: This wrapper will only erase calls to // combine_contiguous(H, const unsigned char*, size_t) +// RunCombineUnordered(H, CombinerF) // // All other calls will be handled internally and will not invoke overloads // provided by the wrapped class. @@ -318,6 +344,8 @@ private: HashState() = default; + friend class HashState::HashStateBase; + template <typename T> static void CombineContiguousImpl(void* p, const unsigned char* first, size_t size) { @@ -329,16 +357,57 @@ void Init(T* state) { state_ = state; combine_contiguous_ = &CombineContiguousImpl<T>; + run_combine_unordered_ = &RunCombineUnorderedImpl<T>; + } + + template <typename HS> + struct CombineUnorderedInvoker { + template <typename T, typename ConsumerT> + void operator()(T inner_state, ConsumerT inner_cb) { + f(HashState::Create(&inner_state), + [&](HashState& inner_erased) { inner_cb(inner_erased.Real<T>()); }); + } + + absl::FunctionRef<void(HS, absl::FunctionRef<void(HS&)>)> f; + }; + + template <typename T> + static HashState RunCombineUnorderedImpl( + HashState state, + absl::FunctionRef<void(HashState, absl::FunctionRef<void(HashState&)>)> + f) { + // Note that this implementation assumes that inner_state and outer_state + // are the same type. This isn't true in the SpyHash case, but SpyHash + // types are move-convertible to each other, so this still works. + T& real_state = state.Real<T>(); + real_state = T::RunCombineUnordered( + std::move(real_state), CombineUnorderedInvoker<HashState>{f}); + return state; + } + + template <typename CombinerT> + static HashState RunCombineUnordered(HashState state, CombinerT combiner) { + auto* run = state.run_combine_unordered_; + return run(std::move(state), std::ref(combiner)); } // Do not erase an already erased state. void Init(HashState* state) { state_ = state->state_; combine_contiguous_ = state->combine_contiguous_; + run_combine_unordered_ = state->run_combine_unordered_; + } + + template <typename T> + T& Real() { + return *static_cast<T*>(state_); } void* state_; void (*combine_contiguous_)(void*, const unsigned char*, size_t); + HashState (*run_combine_unordered_)( + HashState state, + absl::FunctionRef<void(HashState, absl::FunctionRef<void(HashState&)>)>); }; ABSL_NAMESPACE_END
diff --git a/absl/hash/hash_benchmark.cc b/absl/hash/hash_benchmark.cc index d498ac2..8712a01 100644 --- a/absl/hash/hash_benchmark.cc +++ b/absl/hash/hash_benchmark.cc
@@ -19,6 +19,7 @@ #include <vector> #include "absl/base/attributes.h" +#include "absl/container/flat_hash_set.h" #include "absl/hash/hash.h" #include "absl/random/random.h" #include "absl/strings/cord.h" @@ -107,6 +108,44 @@ return result; } +template <typename T> +std::vector<T> Vector(size_t count) { + std::vector<T> result; + for (size_t v = 0; v < count; ++v) { + result.push_back(v); + } + return result; +} + +// Bogus type that replicates an unorderd_set's bit mixing, but with +// vector-speed iteration. This is intended to measure the overhead of unordered +// hashing without counting the speed of unordered_set iteration. +template <typename T> +struct FastUnorderedSet { + explicit FastUnorderedSet(size_t count) { + for (size_t v = 0; v < count; ++v) { + values.push_back(v); + } + } + std::vector<T> values; + + template <typename H> + friend H AbslHashValue(H h, const FastUnorderedSet& fus) { + return H::combine(H::combine_unordered(std::move(h), fus.values.begin(), + fus.values.end()), + fus.values.size()); + } +}; + +template <typename T> +absl::flat_hash_set<T> FlatHashSet(size_t count) { + absl::flat_hash_set<T> result; + for (size_t v = 0; v < count; ++v) { + result.insert(v); + } + return result; +} + // Generates a benchmark and a codegen method for the provided types. The // codegen method provides a well known entrypoint for dumping assembly. #define MAKE_BENCHMARK(hash, name, ...) \ @@ -145,10 +184,22 @@ MAKE_BENCHMARK(AbslHash, Cord_Flat_5000, FlatCord(5000)); MAKE_BENCHMARK(AbslHash, Cord_Fragmented_200, FragmentedCord(200)); MAKE_BENCHMARK(AbslHash, Cord_Fragmented_5000, FragmentedCord(5000)); -MAKE_BENCHMARK(AbslHash, VectorInt64_10, std::vector<int64_t>(10)); -MAKE_BENCHMARK(AbslHash, VectorInt64_100, std::vector<int64_t>(100)); -MAKE_BENCHMARK(AbslHash, VectorDouble_10, std::vector<double>(10, 1.1)); -MAKE_BENCHMARK(AbslHash, VectorDouble_100, std::vector<double>(100, 1.1)); +MAKE_BENCHMARK(AbslHash, VectorInt64_10, Vector<int64_t>(10)); +MAKE_BENCHMARK(AbslHash, VectorInt64_100, Vector<int64_t>(100)); +MAKE_BENCHMARK(AbslHash, VectorInt64_1000, Vector<int64_t>(1000)); +MAKE_BENCHMARK(AbslHash, VectorDouble_10, Vector<double>(10)); +MAKE_BENCHMARK(AbslHash, VectorDouble_100, Vector<double>(100)); +MAKE_BENCHMARK(AbslHash, VectorDouble_1000, Vector<double>(1000)); +MAKE_BENCHMARK(AbslHash, FlatHashSetInt64_10, FlatHashSet<int64_t>(10)); +MAKE_BENCHMARK(AbslHash, FlatHashSetInt64_100, FlatHashSet<int64_t>(100)); +MAKE_BENCHMARK(AbslHash, FlatHashSetInt64_1000, FlatHashSet<int64_t>(1000)); +MAKE_BENCHMARK(AbslHash, FlatHashSetDouble_10, FlatHashSet<double>(10)); +MAKE_BENCHMARK(AbslHash, FlatHashSetDouble_100, FlatHashSet<double>(100)); +MAKE_BENCHMARK(AbslHash, FlatHashSetDouble_1000, FlatHashSet<double>(1000)); +MAKE_BENCHMARK(AbslHash, FastUnorderedSetInt64_1000, + FastUnorderedSet<int64_t>(1000)); +MAKE_BENCHMARK(AbslHash, FastUnorderedSetDouble_1000, + FastUnorderedSet<double>(1000)); MAKE_BENCHMARK(AbslHash, PairStringString_0, std::make_pair(std::string(), std::string())); MAKE_BENCHMARK(AbslHash, PairStringString_10, @@ -180,6 +231,24 @@ std::vector<double>(10, 1.1)); MAKE_BENCHMARK(TypeErasedAbslHash, VectorDouble_100, std::vector<double>(100, 1.1)); +MAKE_BENCHMARK(TypeErasedAbslHash, VectorDouble_1000, + std::vector<double>(1000, 1.1)); +MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetInt64_10, + FlatHashSet<int64_t>(10)); +MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetInt64_100, + FlatHashSet<int64_t>(100)); +MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetInt64_1000, + FlatHashSet<int64_t>(1000)); +MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetDouble_10, + FlatHashSet<double>(10)); +MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetDouble_100, + FlatHashSet<double>(100)); +MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetDouble_1000, + FlatHashSet<double>(1000)); +MAKE_BENCHMARK(TypeErasedAbslHash, FastUnorderedSetInt64_1000, + FastUnorderedSet<int64_t>(1000)); +MAKE_BENCHMARK(TypeErasedAbslHash, FastUnorderedSetDouble_1000, + FastUnorderedSet<double>(1000)); // The latency benchmark attempts to model the speed of the hash function in // production. When a hash function is used for hashtable lookups it is rarely
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index dbfacb2..cea54dc 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -34,12 +34,18 @@ #include <tuple> #include <type_traits> #include <unordered_map> +#include <unordered_set> #include <utility> #include <vector> #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/container/btree_map.h" +#include "absl/container/btree_set.h" +#include "absl/container/flat_hash_map.h" #include "absl/container/flat_hash_set.h" +#include "absl/container/node_hash_map.h" +#include "absl/container/node_hash_set.h" #include "absl/hash/hash_testing.h" #include "absl/hash/internal/spy_hash_state.h" #include "absl/meta/type_traits.h" @@ -433,6 +439,52 @@ std::bitset<kNumBits>(bit_strings[5].c_str())})); } // namespace +// Dummy type with unordered equality and hashing semantics. This preserves +// input order internally, and is used below to ensure we get test coverage +// for equal sequences with different iteraton orders. +template <typename T> +class UnorderedSequence { + public: + UnorderedSequence() = default; + template <typename TT> + UnorderedSequence(std::initializer_list<TT> l) + : values_(l.begin(), l.end()) {} + template <typename ForwardIterator, + typename std::enable_if<!std::is_integral<ForwardIterator>::value, + bool>::type = true> + UnorderedSequence(ForwardIterator begin, ForwardIterator end) + : values_(begin, end) {} + // one-argument constructor of value type T, to appease older toolchains that + // get confused by one-element initializer lists in some contexts + explicit UnorderedSequence(const T& v) : values_(&v, &v + 1) {} + + using value_type = T; + + size_t size() const { return values_.size(); } + typename std::vector<T>::const_iterator begin() const { + return values_.begin(); + } + typename std::vector<T>::const_iterator end() const { return values_.end(); } + + friend bool operator==(const UnorderedSequence& lhs, + const UnorderedSequence& rhs) { + return lhs.size() == rhs.size() && + std::is_permutation(lhs.begin(), lhs.end(), rhs.begin()); + } + friend bool operator!=(const UnorderedSequence& lhs, + const UnorderedSequence& rhs) { + return !(lhs == rhs); + } + template <typename H> + friend H AbslHashValue(H h, const UnorderedSequence& u) { + return H::combine(H::combine_unordered(std::move(h), u.begin(), u.end()), + u.size()); + } + + private: + std::vector<T> values_; +}; + template <typename T> class HashValueSequenceTest : public testing::Test { }; @@ -456,10 +508,13 @@ } REGISTER_TYPED_TEST_CASE_P(HashValueSequenceTest, BasicUsage); -using IntSequenceTypes = - testing::Types<std::deque<int>, std::forward_list<int>, std::list<int>, - std::vector<int>, std::vector<bool>, TypeErasedVector<int>, - TypeErasedVector<bool>, std::set<int>, std::multiset<int>>; +using IntSequenceTypes = testing::Types< + std::deque<int>, std::forward_list<int>, std::list<int>, std::vector<int>, + std::vector<bool>, TypeErasedContainer<std::vector<int>>, std::set<int>, + std::multiset<int>, UnorderedSequence<int>, + TypeErasedContainer<UnorderedSequence<int>>, std::unordered_set<int>, + std::unordered_multiset<int>, absl::flat_hash_set<int>, + absl::node_hash_set<int>, absl::btree_set<int>>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes); template <typename T> @@ -487,11 +542,15 @@ } REGISTER_TYPED_TEST_CASE_P(HashValueNestedSequenceTest, BasicUsage); -using NestedIntSequenceTypes = - testing::Types<std::vector<std::vector<int>>, - std::vector<TypeErasedVector<int>>, - TypeErasedVector<std::vector<int>>, - TypeErasedVector<TypeErasedVector<int>>>; +template <typename T> +using TypeErasedSet = TypeErasedContainer<UnorderedSequence<T>>; + +using NestedIntSequenceTypes = testing::Types< + std::vector<std::vector<int>>, std::vector<UnorderedSequence<int>>, + std::vector<TypeErasedSet<int>>, UnorderedSequence<std::vector<int>>, + UnorderedSequence<UnorderedSequence<int>>, + UnorderedSequence<TypeErasedSet<int>>, TypeErasedSet<std::vector<int>>, + TypeErasedSet<UnorderedSequence<int>>, TypeErasedSet<TypeErasedSet<int>>>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueNestedSequenceTest, NestedIntSequenceTypes); @@ -674,7 +733,11 @@ } REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMapTest, BasicUsage); -using AssociativeMapTypes = testing::Types<std::map<int, std::string>>; +using AssociativeMapTypes = testing::Types< + std::map<int, std::string>, std::unordered_map<int, std::string>, + absl::flat_hash_map<int, std::string>, + absl::node_hash_map<int, std::string>, absl::btree_map<int, std::string>, + UnorderedSequence<std::pair<const int, std::string>>>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMapTest, AssociativeMapTypes); @@ -702,7 +765,8 @@ REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMultimapTest, BasicUsage); using AssociativeMultimapTypes = - testing::Types<std::multimap<int, std::string>>; + testing::Types<std::multimap<int, std::string>, + std::unordered_multimap<int, std::string>>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMultimapTest, AssociativeMultimapTypes); @@ -1062,6 +1126,14 @@ EXPECT_EQ(SpyHash(std::make_pair(TypeErasedValue<size_t>(7), 17)), SpyHash(std::make_pair(size_t{7}, 17))); + + absl::flat_hash_set<absl::flat_hash_set<int>> ss = {{1, 2}, {3, 4}}; + TypeErasedContainer<absl::flat_hash_set<absl::flat_hash_set<int>>> es = { + absl::flat_hash_set<int>{1, 2}, {3, 4}}; + absl::flat_hash_set<TypeErasedContainer<absl::flat_hash_set<int>>> se = { + {1, 2}, {3, 4}}; + EXPECT_EQ(SpyHash(ss), SpyHash(es)); + EXPECT_EQ(SpyHash(ss), SpyHash(se)); } struct ValueWithBoolConversion {
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 97b68ba..a424e01 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -23,6 +23,7 @@ #include <array> #include <bitset> #include <cmath> +#include <cstddef> #include <cstring> #include <deque> #include <forward_list> @@ -36,6 +37,8 @@ #include <string> #include <tuple> #include <type_traits> +#include <unordered_map> +#include <unordered_set> #include <utility> #include <vector> @@ -54,6 +57,9 @@ namespace absl { ABSL_NAMESPACE_BEGIN + +class HashState; + namespace hash_internal { // Internal detail: Large buffers are hashed in smaller chunks. This function @@ -115,24 +121,66 @@ size_t position_; }; +// is_hashable() +// +// Trait class which returns true if T is hashable by the absl::Hash framework. +// Used for the AbslHashValue implementations for composite types below. +template <typename T> +struct is_hashable; + // HashStateBase // -// A hash state object represents an intermediate state in the computation -// of an unspecified hash algorithm. `HashStateBase` provides a CRTP style -// base class for hash state implementations. Developers adding type support -// for `absl::Hash` should not rely on any parts of the state object other than -// the following member functions: +// An internal implementation detail that contains common implementation details +// for all of the "hash state objects" objects generated by Abseil. This is not +// a public API; users should not create classes that inherit from this. +// +// A hash state object is the template argument `H` passed to `AbslHashValue`. +// It represents an intermediate state in the computation of an unspecified hash +// algorithm. `HashStateBase` provides a CRTP style base class for hash state +// implementations. Developers adding type support for `absl::Hash` should not +// rely on any parts of the state object other than the following member +// functions: // // * HashStateBase::combine() // * HashStateBase::combine_contiguous() +// * HashStateBase::combine_unordered() // -// A derived hash state class of type `H` must provide a static member function +// A derived hash state class of type `H` must provide a public member function // with a signature similar to the following: // // `static H combine_contiguous(H state, const unsigned char*, size_t)`. // +// It must also provide a private template method named RunCombineUnordered. +// +// A "consumer" is a 1-arg functor returning void. Its argument is a reference +// to an inner hash state object, and it may be called multiple times. When +// called, the functor consumes the entropy from the provided state object, +// and resets that object to its empty state. +// +// A "combiner" is a stateless 2-arg functor returning void. Its arguments are +// an inner hash state object and an ElementStateConsumer functor. A combiner +// uses the provided inner hash state object to hash each element of the +// container, passing the inner hash state object to the consumer after hashing +// each element. +// +// Given these definitions, a derived hash state class of type H +// must provide a private template method with a signature similar to the +// following: +// +// `template <typename CombinerT>` +// `static H RunCombineUnordered(H outer_state, CombinerT combiner)` +// +// This function is responsible for constructing the inner state object and +// providing a consumer to the combiner. It uses side effects of the consumer +// and combiner to mix the state of each element in an order-independent manner, +// and uses this to return an updated value of `outer_state`. +// +// This inside-out approach generates efficient object code in the normal case, +// but allows us to use stack storage to implement the absl::HashState type +// erasure mechanism (avoiding heap allocations while hashing). +// // `HashStateBase` will provide a complete implementation for a hash state -// object in terms of this method. +// object in terms of these two methods. // // Example: // @@ -141,6 +189,10 @@ // static H combine_contiguous(H state, const unsigned char*, size_t); // using MyHashState::HashStateBase::combine; // using MyHashState::HashStateBase::combine_contiguous; +// using MyHashState::HashStateBase::combine_unordered; +// private: +// template <typename CombinerT> +// static H RunCombineUnordered(H state, CombinerT combiner); // }; template <typename H> class HashStateBase { @@ -181,7 +233,30 @@ template <typename T> static H combine_contiguous(H state, const T* data, size_t size); + template <typename I> + static H combine_unordered(H state, I begin, I end); + using AbslInternalPiecewiseCombiner = PiecewiseCombiner; + + template <typename T> + using is_hashable = absl::hash_internal::is_hashable<T>; + + private: + // Common implementation of the iteration step of a "combiner", as described + // above. + template <typename I> + struct CombineUnorderedCallback { + I begin; + I end; + + template <typename InnerH, typename ElementStateConsumer> + void operator()(InnerH inner_state, ElementStateConsumer cb) { + for (; begin != end; ++begin) { + inner_state = H::combine(std::move(inner_state), *begin); + cb(inner_state); + } + } + }; }; // is_uniquely_represented @@ -350,13 +425,6 @@ // AbslHashValue for Composite Types // ----------------------------------------------------------------------------- -// is_hashable() -// -// Trait class which returns true if T is hashable by the absl::Hash framework. -// Used for the AbslHashValue implementations for composite types below. -template <typename T> -struct is_hashable; - // AbslHashValue() for hashing pairs template <typename H, typename T1, typename T2> typename std::enable_if<is_hashable<T1>::value && is_hashable<T2>::value, @@ -503,8 +571,10 @@ } // AbslHashValue special cases for hashing std::vector<bool> + #if defined(ABSL_IS_BIG_ENDIAN) && \ (defined(__GLIBCXX__) || defined(__GLIBCPP__)) + // std::hash in libstdc++ does not work correctly with vector<bool> on Big // Endian platforms therefore we need to implement a custom AbslHashValue for // it. More details on the bug: @@ -588,6 +658,55 @@ } // ----------------------------------------------------------------------------- +// AbslHashValue for Unordered Associative Containers +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing std::unordered_set +template <typename H, typename Key, typename Hash, typename KeyEqual, + typename Alloc> +typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue( + H hash_state, const std::unordered_set<Key, Hash, KeyEqual, Alloc>& s) { + return H::combine( + H::combine_unordered(std::move(hash_state), s.begin(), s.end()), + s.size()); +} + +// AbslHashValue for hashing std::unordered_multiset +template <typename H, typename Key, typename Hash, typename KeyEqual, + typename Alloc> +typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue( + H hash_state, + const std::unordered_multiset<Key, Hash, KeyEqual, Alloc>& s) { + return H::combine( + H::combine_unordered(std::move(hash_state), s.begin(), s.end()), + s.size()); +} + +// AbslHashValue for hashing std::unordered_set +template <typename H, typename Key, typename T, typename Hash, + typename KeyEqual, typename Alloc> +typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value, + H>::type +AbslHashValue(H hash_state, + const std::unordered_map<Key, T, Hash, KeyEqual, Alloc>& s) { + return H::combine( + H::combine_unordered(std::move(hash_state), s.begin(), s.end()), + s.size()); +} + +// AbslHashValue for hashing std::unordered_multiset +template <typename H, typename Key, typename T, typename Hash, + typename KeyEqual, typename Alloc> +typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value, + H>::type +AbslHashValue(H hash_state, + const std::unordered_multimap<Key, T, Hash, KeyEqual, Alloc>& s) { + return H::combine( + H::combine_unordered(std::move(hash_state), s.begin(), s.end()), + s.size()); +} + +// ----------------------------------------------------------------------------- // AbslHashValue for Wrapper Types // ----------------------------------------------------------------------------- @@ -830,6 +949,31 @@ // move-only ensures that there is only one non-moved-from object. MixingHashState() : state_(Seed()) {} + friend class MixingHashState::HashStateBase; + + template <typename CombinerT> + static MixingHashState RunCombineUnordered(MixingHashState state, + CombinerT combiner) { + uint64_t unordered_state = 0; + combiner(MixingHashState{}, [&](MixingHashState& inner_state) { + // Add the hash state of the element to the running total, but mix the + // carry bit back into the low bit. This in intended to avoid losing + // entropy to overflow, especially when unordered_multisets contain + // multiple copies of the same value. + auto element_state = inner_state.state_; + unordered_state += element_state; + if (unordered_state < element_state) { + ++unordered_state; + } + inner_state = MixingHashState{}; + }); + return MixingHashState::combine(std::move(state), unordered_state); + } + + // Allow the HashState type-erasure implementation to invoke + // RunCombinedUnordered() directly. + friend class absl::HashState; + // Workaround for MSVC bug. // We make the type copyable to fix the calling convention, even though we // never actually copy it. Keep it private to not affect the public API of the @@ -1064,6 +1208,14 @@ return hash_internal::hash_range_or_bytes(std::move(state), data, size); } +// HashStateBase::combine_unordered() +template <typename H> +template <typename I> +H HashStateBase<H>::combine_unordered(H state, I begin, I end) { + return H::RunCombineUnordered(std::move(state), + CombineUnorderedCallback<I>{begin, end}); +} + // HashStateBase::PiecewiseCombiner::add_buffer() template <typename H> H PiecewiseCombiner::add_buffer(H state, const unsigned char* data,
diff --git a/absl/hash/internal/spy_hash_state.h b/absl/hash/internal/spy_hash_state.h index c083120..0972826 100644 --- a/absl/hash/internal/spy_hash_state.h +++ b/absl/hash/internal/spy_hash_state.h
@@ -15,6 +15,7 @@ #ifndef ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_ #define ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_ +#include <algorithm> #include <ostream> #include <string> #include <vector> @@ -167,6 +168,24 @@ using SpyHashStateImpl::HashStateBase::combine_contiguous; + template <typename CombinerT> + static SpyHashStateImpl RunCombineUnordered(SpyHashStateImpl state, + CombinerT combiner) { + UnorderedCombinerCallback cb; + + combiner(SpyHashStateImpl<void>{}, std::ref(cb)); + + std::sort(cb.element_hash_representations.begin(), + cb.element_hash_representations.end()); + state.hash_representation_.insert(state.hash_representation_.end(), + cb.element_hash_representations.begin(), + cb.element_hash_representations.end()); + if (cb.error && cb.error->has_value()) { + state.error_ = std::move(cb.error); + } + return state; + } + absl::optional<std::string> error() const { if (moved_from_) { return "Returned a moved-from instance of the hash state object."; @@ -178,6 +197,22 @@ template <typename U> friend class SpyHashStateImpl; + struct UnorderedCombinerCallback { + std::vector<std::string> element_hash_representations; + std::shared_ptr<absl::optional<std::string>> error; + + // The inner spy can have a different type. + template <typename U> + void operator()(SpyHashStateImpl<U>& inner) { + element_hash_representations.push_back( + absl::StrJoin(inner.hash_representation_, "")); + if (inner.error_->has_value()) { + error = std::move(inner.error_); + } + inner = SpyHashStateImpl<void>{}; + } + }; + // This is true if SpyHashStateImpl<T> has been passed to a call of // AbslHashValue with the wrong type. This detects that the user called // AbslHashValue directly (because the hash state type does not match).
diff --git a/absl/profiling/internal/sample_recorder.h b/absl/profiling/internal/sample_recorder.h index fc269bd..5f65983 100644 --- a/absl/profiling/internal/sample_recorder.h +++ b/absl/profiling/internal/sample_recorder.h
@@ -46,6 +46,7 @@ absl::Mutex init_mu; T* next = nullptr; T* dead ABSL_GUARDED_BY(init_mu) = nullptr; + int64_t weight; // How many sampling events were required to sample this one. }; // Holds samples and their associated stack traces with a soft limit of
diff --git a/absl/profiling/internal/sample_recorder_test.cc b/absl/profiling/internal/sample_recorder_test.cc index ec6e0fa..3373329 100644 --- a/absl/profiling/internal/sample_recorder_test.cc +++ b/absl/profiling/internal/sample_recorder_test.cc
@@ -36,7 +36,7 @@ struct Info : public Sample<Info> { public: - void PrepareForSampling() {} + void PrepareForSampling(int64_t w) { weight = w; } std::atomic<size_t> size; absl::Time create_time; }; @@ -49,8 +49,14 @@ return res; } -Info* Register(SampleRecorder<Info>* s, size_t size) { - auto* info = s->Register(); +std::vector<int64_t> GetWeights(SampleRecorder<Info>* s) { + std::vector<int64_t> res; + s->Iterate([&](const Info& info) { res.push_back(info.weight); }); + return res; +} + +Info* Register(SampleRecorder<Info>* s, int64_t weight, size_t size) { + auto* info = s->Register(weight); assert(info != nullptr); info->size.store(size); return info; @@ -58,13 +64,15 @@ TEST(SampleRecorderTest, Registration) { SampleRecorder<Info> sampler; - auto* info1 = Register(&sampler, 1); + auto* info1 = Register(&sampler, 31, 1); EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1)); + EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(31)); - auto* info2 = Register(&sampler, 2); + auto* info2 = Register(&sampler, 32, 2); EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1, 2)); info1->size.store(3); EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(3, 2)); + EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(31, 32)); sampler.Unregister(info1); sampler.Unregister(info2); @@ -74,18 +82,22 @@ SampleRecorder<Info> sampler; std::vector<Info*> infos; for (size_t i = 0; i < 3; ++i) { - infos.push_back(Register(&sampler, i)); + infos.push_back(Register(&sampler, 33 + i, i)); } EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 1, 2)); + EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 34, 35)); sampler.Unregister(infos[1]); EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2)); + EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 35)); - infos.push_back(Register(&sampler, 3)); - infos.push_back(Register(&sampler, 4)); + infos.push_back(Register(&sampler, 36, 3)); + infos.push_back(Register(&sampler, 37, 4)); EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 3, 4)); + EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 35, 36, 37)); sampler.Unregister(infos[3]); EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 4)); + EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 35, 37)); sampler.Unregister(infos[0]); sampler.Unregister(infos[2]); @@ -99,18 +111,18 @@ ThreadPool pool(10); for (int i = 0; i < 10; ++i) { - pool.Schedule([&sampler, &stop]() { + pool.Schedule([&sampler, &stop, i]() { std::random_device rd; std::mt19937 gen(rd()); std::vector<Info*> infoz; while (!stop.HasBeenNotified()) { if (infoz.empty()) { - infoz.push_back(sampler.Register()); + infoz.push_back(sampler.Register(i)); } switch (std::uniform_int_distribution<>(0, 2)(gen)) { case 0: { - infoz.push_back(sampler.Register()); + infoz.push_back(sampler.Register(i)); break; } case 1: { @@ -119,6 +131,7 @@ Info* info = infoz[p]; infoz[p] = infoz.back(); infoz.pop_back(); + EXPECT_EQ(info->weight, i); sampler.Unregister(info); break; } @@ -143,8 +156,8 @@ TEST(SampleRecorderTest, Callback) { SampleRecorder<Info> sampler; - auto* info1 = Register(&sampler, 1); - auto* info2 = Register(&sampler, 2); + auto* info1 = Register(&sampler, 39, 1); + auto* info2 = Register(&sampler, 40, 2); static const Info* expected;
diff --git a/absl/random/internal/randen.h b/absl/random/internal/randen.h index 9a3840b..9ff4a7a 100644 --- a/absl/random/internal/randen.h +++ b/absl/random/internal/randen.h
@@ -43,10 +43,8 @@ // Generate updates the randen sponge. The outer portion of the sponge // (kCapacityBytes .. kStateBytes) may be consumed as PRNG state. - template <typename T, size_t N> - void Generate(T (&state)[N]) const { - static_assert(N * sizeof(T) == kStateBytes, - "Randen::Generate() requires kStateBytes of state"); + // REQUIRES: state points to kStateBytes of state. + inline void Generate(void* state) const { #if ABSL_RANDOM_INTERNAL_AES_DISPATCH // HW AES Dispatch. if (has_crypto_) { @@ -65,13 +63,9 @@ // Absorb incorporates additional seed material into the randen sponge. After // absorb returns, Generate must be called before the state may be consumed. - template <typename S, size_t M, typename T, size_t N> - void Absorb(const S (&seed)[M], T (&state)[N]) const { - static_assert(M * sizeof(S) == RandenTraits::kSeedBytes, - "Randen::Absorb() requires kSeedBytes of seed"); - - static_assert(N * sizeof(T) == RandenTraits::kStateBytes, - "Randen::Absorb() requires kStateBytes of state"); + // REQUIRES: seed points to kSeedBytes of seed. + // REQUIRES: state points to kStateBytes of state. + inline void Absorb(const void* seed, void* state) const { #if ABSL_RANDOM_INTERNAL_AES_DISPATCH // HW AES Dispatch. if (has_crypto_) {
diff --git a/absl/random/internal/randen_engine.h b/absl/random/internal/randen_engine.h index 372c3ac..b470866 100644 --- a/absl/random/internal/randen_engine.h +++ b/absl/random/internal/randen_engine.h
@@ -42,7 +42,7 @@ // 'Strong' (well-distributed, unpredictable, backtracking-resistant) random // generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32. template <typename T> -class alignas(16) randen_engine { +class alignas(8) randen_engine { public: // C++11 URBG interface: using result_type = T; @@ -58,7 +58,8 @@ return (std::numeric_limits<result_type>::max)(); } - explicit randen_engine(result_type seed_value = 0) { seed(seed_value); } + randen_engine() : randen_engine(0) {} + explicit randen_engine(result_type seed_value) { seed(seed_value); } template <class SeedSequence, typename = typename absl::enable_if_t< @@ -67,17 +68,27 @@ seed(seq); } - randen_engine(const randen_engine&) = default; + // alignment requirements dictate custom copy and move constructors. + randen_engine(const randen_engine& other) + : next_(other.next_), impl_(other.impl_) { + std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type)); + } + randen_engine& operator=(const randen_engine& other) { + next_ = other.next_; + impl_ = other.impl_; + std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type)); + return *this; + } // Returns random bits from the buffer in units of result_type. result_type operator()() { // Refill the buffer if needed (unlikely). + auto* begin = state(); if (next_ >= kStateSizeT) { next_ = kCapacityT; - impl_.Generate(state_); + impl_.Generate(begin); } - - return little_endian::ToHost(state_[next_++]); + return little_endian::ToHost(begin[next_++]); } template <class SeedSequence> @@ -92,9 +103,10 @@ void seed(result_type seed_value = 0) { next_ = kStateSizeT; // Zeroes the inner state and fills the outer state with seed_value to - // mimics behaviour of reseed - std::fill(std::begin(state_), std::begin(state_) + kCapacityT, 0); - std::fill(std::begin(state_) + kCapacityT, std::end(state_), seed_value); + // mimic the behaviour of reseed + auto* begin = state(); + std::fill(begin, begin + kCapacityT, 0); + std::fill(begin + kCapacityT, begin + kStateSizeT, seed_value); } // Inserts entropy into (part of) the state. Calling this periodically with @@ -105,7 +117,6 @@ using sequence_result_type = typename SeedSequence::result_type; static_assert(sizeof(sequence_result_type) == 4, "SeedSequence::result_type must be 32-bit"); - constexpr size_t kBufferSize = Randen::kSeedBytes / sizeof(sequence_result_type); alignas(16) sequence_result_type buffer[kBufferSize]; @@ -119,8 +130,8 @@ if (entropy_size < kBufferSize) { // ... and only request that many values, or 256-bits, when unspecified. const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size; - std::fill(std::begin(buffer) + requested_entropy, std::end(buffer), 0); - seq.generate(std::begin(buffer), std::begin(buffer) + requested_entropy); + std::fill(buffer + requested_entropy, buffer + kBufferSize, 0); + seq.generate(buffer, buffer + requested_entropy); #ifdef ABSL_IS_BIG_ENDIAN // Randen expects the seed buffer to be in Little Endian; reverse it on // Big Endian platforms. @@ -146,9 +157,9 @@ std::swap(buffer[--dst], buffer[--src]); } } else { - seq.generate(std::begin(buffer), std::end(buffer)); + seq.generate(buffer, buffer + kBufferSize); } - impl_.Absorb(buffer, state_); + impl_.Absorb(buffer, state()); // Generate will be called when operator() is called next_ = kStateSizeT; @@ -159,9 +170,10 @@ count -= step; constexpr uint64_t kRateT = kStateSizeT - kCapacityT; + auto* begin = state(); while (count > 0) { next_ = kCapacityT; - impl_.Generate(state_); + impl_.Generate(*reinterpret_cast<result_type(*)[kStateSizeT]>(begin)); step = std::min<uint64_t>(kRateT, count); count -= step; } @@ -169,9 +181,9 @@ } bool operator==(const randen_engine& other) const { + const auto* begin = state(); return next_ == other.next_ && - std::equal(std::begin(state_), std::end(state_), - std::begin(other.state_)); + std::equal(begin, begin + kStateSizeT, other.state()); } bool operator!=(const randen_engine& other) const { @@ -185,11 +197,12 @@ using numeric_type = typename random_internal::stream_format_type<result_type>::type; auto saver = random_internal::make_ostream_state_saver(os); - for (const auto& elem : engine.state_) { + auto* it = engine.state(); + for (auto* end = it + kStateSizeT; it < end; ++it) { // In the case that `elem` is `uint8_t`, it must be cast to something // larger so that it prints as an integer rather than a character. For // simplicity, apply the cast all circumstances. - os << static_cast<numeric_type>(little_endian::FromHost(elem)) + os << static_cast<numeric_type>(little_endian::FromHost(*it)) << os.fill(); } os << engine.next_; @@ -215,7 +228,7 @@ if (is.fail()) { return is; } - std::memcpy(engine.state_, state, sizeof(engine.state_)); + std::memcpy(engine.state(), state, sizeof(state)); engine.next_ = next; return is; } @@ -226,9 +239,21 @@ static constexpr size_t kCapacityT = Randen::kCapacityBytes / sizeof(result_type); - // First kCapacityT are `inner', the others are accessible random bits. - alignas(16) result_type state_[kStateSizeT]; - size_t next_; // index within state_ + // Returns the state array pointer, which is aligned to 16 bytes. + // The first kCapacityT are the `inner' sponge; the remainder are available. + result_type* state() { + return reinterpret_cast<result_type*>( + (reinterpret_cast<uintptr_t>(&raw_state_) & 0xf) ? (raw_state_ + 8) + : raw_state_); + } + const result_type* state() const { + return const_cast<randen_engine*>(this)->state(); + } + + // raw state array, manually aligned in state(). This overallocates + // by 8 bytes since C++ does not guarantee extended heap alignment. + alignas(8) char raw_state_[Randen::kStateBytes + 8]; + size_t next_; // index within state() Randen impl_; };
diff --git a/absl/status/internal/status_internal.h b/absl/status/internal/status_internal.h index ac12940..34914d2 100644 --- a/absl/status/internal/status_internal.h +++ b/absl/status/internal/status_internal.h
@@ -16,6 +16,7 @@ #include <string> +#include "absl/base/attributes.h" #include "absl/container/inlined_vector.h" #include "absl/strings/cord.h" @@ -25,7 +26,14 @@ ABSL_NAMESPACE_BEGIN // Returned Status objects may not be ignored. Codesearch doesn't handle ifdefs // as part of a class definitions (b/6995610), so we use a forward declaration. +// +// TODO(b/176172494): ABSL_MUST_USE_RESULT should expand to the more strict +// [[nodiscard]]. For now, just use [[nodiscard]] directly when it is available. +#if ABSL_HAVE_CPP_ATTRIBUTE(nodiscard) +class [[nodiscard]] Status; +#else class ABSL_MUST_USE_RESULT Status; +#endif ABSL_NAMESPACE_END } // namespace absl #endif // !SWIG
diff --git a/absl/status/statusor.h b/absl/status/statusor.h index c051fbb..d6ebdc2 100644 --- a/absl/status/statusor.h +++ b/absl/status/statusor.h
@@ -106,7 +106,13 @@ // Returned StatusOr objects may not be ignored. template <typename T> +#if ABSL_HAVE_CPP_ATTRIBUTE(nodiscard) +// TODO(b/176172494): ABSL_MUST_USE_RESULT should expand to the more strict +// [[nodiscard]]. For now, just use [[nodiscard]] directly when it is available. +class [[nodiscard]] StatusOr; +#else class ABSL_MUST_USE_RESULT StatusOr; +#endif // ABSL_HAVE_CPP_ATTRIBUTE(nodiscard) // absl::StatusOr<T> //
diff --git a/absl/strings/internal/escaping.cc b/absl/strings/internal/escaping.cc index c527128..7f87e12 100644 --- a/absl/strings/internal/escaping.cc +++ b/absl/strings/internal/escaping.cc
@@ -102,8 +102,8 @@ } } // To save time, we didn't update szdest or szsrc in the loop. So do it now. - szdest = limit_dest - cur_dest; - szsrc = limit_src - cur_src; + szdest = static_cast<size_t>(limit_dest - cur_dest); + szsrc = static_cast<size_t>(limit_src - cur_src); /* now deal with the tail (<=3 bytes) */ switch (szsrc) { @@ -154,7 +154,8 @@ // the loop because the loop above always reads 4 bytes, and the fourth // byte is past the end of the input. if (szdest < 4) return 0; - uint32_t in = (cur_src[0] << 16) + absl::big_endian::Load16(cur_src + 1); + uint32_t in = + (uint32_t{cur_src[0]} << 16) + absl::big_endian::Load16(cur_src + 1); cur_dest[0] = base64[in >> 18]; in &= 0x3FFFF; cur_dest[1] = base64[in >> 12]; @@ -172,7 +173,7 @@ ABSL_RAW_LOG(FATAL, "Logic problem? szsrc = %zu", szsrc); break; } - return (cur_dest - dest); + return static_cast<size_t>(cur_dest - dest); } } // namespace strings_internal
diff --git a/absl/strings/internal/ostringstream.cc b/absl/strings/internal/ostringstream.cc index 05324c7..dc6cfe1 100644 --- a/absl/strings/internal/ostringstream.cc +++ b/absl/strings/internal/ostringstream.cc
@@ -27,7 +27,7 @@ std::streamsize OStringStream::xsputn(const char* s, std::streamsize n) { assert(s_); - s_->append(s, n); + s_->append(s, static_cast<size_t>(n)); return n; }
diff --git a/absl/strings/internal/utf8.cc b/absl/strings/internal/utf8.cc index 8fd8edc..7ecb93d 100644 --- a/absl/strings/internal/utf8.cc +++ b/absl/strings/internal/utf8.cc
@@ -25,25 +25,25 @@ *buffer = static_cast<char>(utf8_char); return 1; } else if (utf8_char <= 0x7FF) { - buffer[1] = 0x80 | (utf8_char & 0x3F); + buffer[1] = static_cast<char>(0x80 | (utf8_char & 0x3F)); utf8_char >>= 6; - buffer[0] = 0xC0 | utf8_char; + buffer[0] = static_cast<char>(0xC0 | utf8_char); return 2; } else if (utf8_char <= 0xFFFF) { - buffer[2] = 0x80 | (utf8_char & 0x3F); + buffer[2] = static_cast<char>(0x80 | (utf8_char & 0x3F)); utf8_char >>= 6; - buffer[1] = 0x80 | (utf8_char & 0x3F); + buffer[1] = static_cast<char>(0x80 | (utf8_char & 0x3F)); utf8_char >>= 6; - buffer[0] = 0xE0 | utf8_char; + buffer[0] = static_cast<char>(0xE0 | utf8_char); return 3; } else { - buffer[3] = 0x80 | (utf8_char & 0x3F); + buffer[3] = static_cast<char>(0x80 | (utf8_char & 0x3F)); utf8_char >>= 6; - buffer[2] = 0x80 | (utf8_char & 0x3F); + buffer[2] = static_cast<char>(0x80 | (utf8_char & 0x3F)); utf8_char >>= 6; - buffer[1] = 0x80 | (utf8_char & 0x3F); + buffer[1] = static_cast<char>(0x80 | (utf8_char & 0x3F)); utf8_char >>= 6; - buffer[0] = 0xF0 | utf8_char; + buffer[0] = static_cast<char>(0xF0 | utf8_char); return 4; } }