diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 7c82725..07a4576 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -81,7 +81,7 @@ "container/internal/have_sse.h" "container/internal/inlined_vector.h" "container/internal/layout.h" - "container/internal/node_hash_policy.h" + "container/internal/node_slot_policy.h" "container/internal/raw_hash_map.h" "container/internal/raw_hash_set.cc" "container/internal/raw_hash_set.h" @@ -455,7 +455,7 @@ "hashtable_debug" "hashtable_debug_hooks" "have_sse" - "node_hash_policy" + "node_slot_policy" "raw_hash_map" "container_common" "raw_hash_set"
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index c38a4a6..26b1952 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h
@@ -166,7 +166,7 @@ // c_all_of() // // Container-based version of the <algorithm> `std::all_of()` function to -// test a condition on all elements within a container. +// test if all elements within a container satisfy a condition. template <typename C, typename Pred> bool c_all_of(const C& c, Pred&& pred) { return std::all_of(container_algorithm_internal::c_begin(c),
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index ffaee19..ea2c98b 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -307,7 +307,7 @@ deps = [ ":container_memory", ":hash_function_defaults", - ":node_hash_policy", + ":node_slot_policy", ":raw_hash_map", "//absl/algorithm:container", "//absl/memory", @@ -339,7 +339,7 @@ linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_function_defaults", - ":node_hash_policy", + ":node_slot_policy", ":raw_hash_set", "//absl/algorithm:container", "//absl/memory", @@ -535,21 +535,21 @@ ) cc_library( - name = "node_hash_policy", - hdrs = ["internal/node_hash_policy.h"], + name = "node_slot_policy", + hdrs = ["internal/node_slot_policy.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = ["//absl/base:config"], ) cc_test( - name = "node_hash_policy_test", - srcs = ["internal/node_hash_policy_test.cc"], + name = "node_slot_policy_test", + srcs = ["internal/node_slot_policy_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_policy_traits", - ":node_hash_policy", + ":node_slot_policy", "@com_google_googletest//:gtest_main", ], )
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 78584d2..bb718cf 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -348,7 +348,7 @@ DEPS absl::container_memory absl::hash_function_defaults - absl::node_hash_policy + absl::node_slot_policy absl::raw_hash_map absl::algorithm_container absl::memory @@ -382,7 +382,7 @@ ${ABSL_DEFAULT_COPTS} DEPS absl::hash_function_defaults - absl::node_hash_policy + absl::node_slot_policy absl::raw_hash_set absl::algorithm_container absl::memory @@ -599,9 +599,9 @@ absl_cc_library( NAME - node_hash_policy + node_slot_policy HDRS - "internal/node_hash_policy.h" + "internal/node_slot_policy.h" COPTS ${ABSL_DEFAULT_COPTS} DEPS @@ -611,14 +611,14 @@ absl_cc_test( NAME - node_hash_policy_test + node_slot_policy_test SRCS - "internal/node_hash_policy_test.cc" + "internal/node_slot_policy_test.cc" COPTS ${ABSL_TEST_COPTS} DEPS absl::hash_policy_traits - absl::node_hash_policy + absl::node_slot_policy GTest::gmock_main )
diff --git a/absl/container/internal/node_hash_policy.h b/absl/container/internal/node_slot_policy.h similarity index 93% rename from absl/container/internal/node_hash_policy.h rename to absl/container/internal/node_slot_policy.h index 4617162..baba574 100644 --- a/absl/container/internal/node_hash_policy.h +++ b/absl/container/internal/node_slot_policy.h
@@ -30,8 +30,8 @@ // It may also optionally define `value()` and `apply()`. For documentation on // these, see hash_policy_traits.h. -#ifndef ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ -#define ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ +#ifndef ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ +#define ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ #include <cassert> #include <cstddef> @@ -46,7 +46,7 @@ namespace container_internal { template <class Reference, class Policy> -struct node_hash_policy { +struct node_slot_policy { static_assert(std::is_lvalue_reference<Reference>::value, ""); using slot_type = typename std::remove_cv< @@ -89,4 +89,4 @@ ABSL_NAMESPACE_END } // namespace absl -#endif // ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ +#endif // ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_
diff --git a/absl/container/internal/node_hash_policy_test.cc b/absl/container/internal/node_slot_policy_test.cc similarity index 93% rename from absl/container/internal/node_hash_policy_test.cc rename to absl/container/internal/node_slot_policy_test.cc index 84aabba..51b7467 100644 --- a/absl/container/internal/node_hash_policy_test.cc +++ b/absl/container/internal/node_slot_policy_test.cc
@@ -12,7 +12,7 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include <memory> @@ -27,7 +27,7 @@ using ::testing::Pointee; -struct Policy : node_hash_policy<int&, Policy> { +struct Policy : node_slot_policy<int&, Policy> { using key_type = int; using init_type = int;
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 7a39f62..302dafa 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h
@@ -43,7 +43,7 @@ #include "absl/algorithm/container.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export #include "absl/memory/memory.h" @@ -535,7 +535,7 @@ template <class Key, class Value> class NodeHashMapPolicy - : public absl::container_internal::node_hash_policy< + : public absl::container_internal::node_slot_policy< std::pair<const Key, Value>&, NodeHashMapPolicy<Key, Value>> { using value_type = std::pair<const Key, Value>;
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 93b15f4..4247288 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h
@@ -39,7 +39,7 @@ #include "absl/algorithm/container.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export #include "absl/memory/memory.h" @@ -442,7 +442,7 @@ template <class T> struct NodeHashSetPolicy - : absl::container_internal::node_hash_policy<T&, NodeHashSetPolicy<T>> { + : absl::container_internal::node_slot_policy<T&, NodeHashSetPolicy<T>> { using key_type = T; using init_type = T; using constant_iterators = std::true_type;
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index b3ddebd..dbfacb2 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -14,12 +14,14 @@ #include "absl/hash/hash.h" +#include <algorithm> #include <array> #include <bitset> #include <cstring> #include <deque> #include <forward_list> #include <functional> +#include <initializer_list> #include <iterator> #include <limits> #include <list> @@ -46,6 +48,56 @@ namespace { +// Utility wrapper of T for the purposes of testing the `AbslHash` type erasure +// mechanism. `TypeErasedValue<T>` can be constructed with a `T`, and can +// be compared and hashed. However, all hashing goes through the hashing +// type-erasure framework. +template <typename T> +class TypeErasedValue { + public: + TypeErasedValue() = default; + TypeErasedValue(const TypeErasedValue&) = default; + TypeErasedValue(TypeErasedValue&&) = default; + explicit TypeErasedValue(const T& n) : n_(n) {} + + template <typename H> + friend H AbslHashValue(H hash_state, const TypeErasedValue& v) { + v.HashValue(absl::HashState::Create(&hash_state)); + return hash_state; + } + + void HashValue(absl::HashState state) const { + absl::HashState::combine(std::move(state), n_); + } + + bool operator==(const TypeErasedValue& rhs) const { return n_ == rhs.n_; } + bool operator!=(const TypeErasedValue& rhs) const { return !(*this == rhs); } + + private: + T n_; +}; + +// A TypeErasedValue refinement, for containers. It exposes the wrapped +// `value_type` and is constructible from an initializer list. +template <typename T> +class TypeErasedContainer : public TypeErasedValue<T> { + public: + using value_type = typename T::value_type; + TypeErasedContainer() = default; + TypeErasedContainer(const TypeErasedContainer&) = default; + TypeErasedContainer(TypeErasedContainer&&) = default; + explicit TypeErasedContainer(const T& n) : TypeErasedValue<T>(n) {} + TypeErasedContainer(std::initializer_list<value_type> init_list) + : TypeErasedContainer(T(init_list.begin(), init_list.end())) {} + // one-argument constructor of value type T, to appease older toolchains that + // get confused by one-element initializer lists in some contexts + explicit TypeErasedContainer(const value_type& v) + : TypeErasedContainer(T(&v, &v + 1)) {} +}; + +template <typename T> +using TypeErasedVector = TypeErasedContainer<std::vector<T>>; + using absl::Hash; using absl::hash_internal::SpyHashState; @@ -389,23 +441,60 @@ TYPED_TEST_P(HashValueSequenceTest, BasicUsage) { EXPECT_TRUE((is_hashable<TypeParam>::value)); - using ValueType = typename TypeParam::value_type; - auto a = static_cast<ValueType>(0); - auto b = static_cast<ValueType>(23); - auto c = static_cast<ValueType>(42); + using IntType = typename TypeParam::value_type; + auto a = static_cast<IntType>(0); + auto b = static_cast<IntType>(23); + auto c = static_cast<IntType>(42); - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( - std::make_tuple(TypeParam(), TypeParam{}, TypeParam{a, b, c}, - TypeParam{a, b}, TypeParam{b, c}))); + std::vector<TypeParam> exemplars = { + TypeParam(), TypeParam(), TypeParam{a, b, c}, + TypeParam{a, c, b}, TypeParam{c, a, b}, TypeParam{a}, + TypeParam{a, a}, TypeParam{a, a, a}, TypeParam{a, a, b}, + TypeParam{a, b, a}, TypeParam{b, a, a}, TypeParam{a, b}, + TypeParam{b, c}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); } 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>, std::set<int>, - std::multiset<int>>; + std::vector<int>, std::vector<bool>, TypeErasedVector<int>, + TypeErasedVector<bool>, std::set<int>, std::multiset<int>>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes); +template <typename T> +class HashValueNestedSequenceTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueNestedSequenceTest); + +TYPED_TEST_P(HashValueNestedSequenceTest, BasicUsage) { + using T = TypeParam; + using V = typename T::value_type; + std::vector<T> exemplars = { + // empty case + T{}, + // sets of empty sets + T{V{}}, T{V{}, V{}}, T{V{}, V{}, V{}}, + // multisets of different values + T{V{1}}, T{V{1, 1}, V{1, 1}}, T{V{1, 1, 1}, V{1, 1, 1}, V{1, 1, 1}}, + // various orderings of same nested sets + T{V{}, V{1, 2}}, T{V{}, V{2, 1}}, T{V{1, 2}, V{}}, T{V{2, 1}, V{}}, + // various orderings of various nested sets, case 2 + T{V{1, 2}, V{3, 4}}, T{V{1, 2}, V{4, 3}}, T{V{1, 3}, V{2, 4}}, + T{V{1, 3}, V{4, 2}}, T{V{1, 4}, V{2, 3}}, T{V{1, 4}, V{3, 2}}, + T{V{2, 3}, V{1, 4}}, T{V{2, 3}, V{4, 1}}, T{V{2, 4}, V{1, 3}}, + T{V{2, 4}, V{3, 1}}, T{V{3, 4}, V{1, 2}}, T{V{3, 4}, V{2, 1}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); +} + +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>>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueNestedSequenceTest, + NestedIntSequenceTypes); + // Private type that only supports AbslHashValue to make sure our chosen hash // implementation is recursive within absl::Hash. // It uses std::abs() on the value to provide different bitwise representations @@ -564,23 +653,59 @@ #endif } -TEST(HashValueTest, Maps) { - EXPECT_TRUE((is_hashable<std::map<int, std::string>>::value)); +template <typename T> +class HashValueAssociativeMapTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueAssociativeMapTest); - using M = std::map<int, std::string>; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - M{}, M{{0, "foo"}}, M{{1, "foo"}}, M{{0, "bar"}}, M{{1, "bar"}}, - M{{0, "foo"}, {42, "bar"}}, M{{1, "foo"}, {42, "bar"}}, - M{{1, "foo"}, {43, "bar"}}, M{{1, "foo"}, {43, "baz"}}))); - - using MM = std::multimap<int, std::string>; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - MM{}, MM{{0, "foo"}}, MM{{1, "foo"}}, MM{{0, "bar"}}, MM{{1, "bar"}}, - MM{{0, "foo"}, {0, "bar"}}, MM{{0, "bar"}, {0, "foo"}}, - MM{{0, "foo"}, {42, "bar"}}, MM{{1, "foo"}, {42, "bar"}}, - MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}}))); +TYPED_TEST_P(HashValueAssociativeMapTest, BasicUsage) { + using M = TypeParam; + using V = typename M::value_type; + std::vector<M> exemplars{M{}, + M{V{0, "foo"}}, + M{V{1, "foo"}}, + M{V{0, "bar"}}, + M{V{1, "bar"}}, + M{V{0, "foo"}, V{42, "bar"}}, + M{V{42, "bar"}, V{0, "foo"}}, + M{V{1, "foo"}, V{42, "bar"}}, + M{V{1, "foo"}, V{43, "bar"}}, + M{V{1, "foo"}, V{43, "baz"}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); } +REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMapTest, BasicUsage); +using AssociativeMapTypes = testing::Types<std::map<int, std::string>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMapTest, + AssociativeMapTypes); + +template <typename T> +class HashValueAssociativeMultimapTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest); + +TYPED_TEST_P(HashValueAssociativeMultimapTest, BasicUsage) { + using MM = TypeParam; + using V = typename MM::value_type; + std::vector<MM> exemplars{MM{}, + MM{V{0, "foo"}}, + MM{V{1, "foo"}}, + MM{V{0, "bar"}}, + MM{V{1, "bar"}}, + MM{V{0, "foo"}, V{0, "bar"}}, + MM{V{0, "bar"}, V{0, "foo"}}, + MM{V{0, "foo"}, V{42, "bar"}}, + MM{V{1, "foo"}, V{42, "bar"}}, + MM{V{1, "foo"}, V{1, "foo"}, V{43, "bar"}}, + MM{V{1, "foo"}, V{43, "bar"}, V{1, "foo"}}, + MM{V{1, "foo"}, V{43, "baz"}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); +} + +REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMultimapTest, BasicUsage); +using AssociativeMultimapTypes = + testing::Types<std::multimap<int, std::string>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMultimapTest, + AssociativeMultimapTypes); + TEST(HashValueTest, ReferenceWrapper) { EXPECT_TRUE(is_hashable<std::reference_wrapper<Private>>::value); @@ -928,28 +1053,14 @@ Hash<IntAndString>()(IntAndString{0, std::string(63, '0')}); } -struct TypeErased { - size_t n; - - template <typename H> - friend H AbslHashValue(H hash_state, const TypeErased& v) { - v.HashValue(absl::HashState::Create(&hash_state)); - return hash_state; - } - - void HashValue(absl::HashState state) const { - absl::HashState::combine(std::move(state), n); - } -}; - TEST(HashTest, TypeErased) { - EXPECT_TRUE((is_hashable<TypeErased>::value)); - EXPECT_TRUE((is_hashable<std::pair<TypeErased, int>>::value)); + EXPECT_TRUE((is_hashable<TypeErasedValue<size_t>>::value)); + EXPECT_TRUE((is_hashable<std::pair<TypeErasedValue<size_t>, int>>::value)); - EXPECT_EQ(SpyHash(TypeErased{7}), SpyHash(size_t{7})); - EXPECT_NE(SpyHash(TypeErased{7}), SpyHash(size_t{13})); + EXPECT_EQ(SpyHash(TypeErasedValue<size_t>(7)), SpyHash(size_t{7})); + EXPECT_NE(SpyHash(TypeErasedValue<size_t>(7)), SpyHash(size_t{13})); - EXPECT_EQ(SpyHash(std::make_pair(TypeErased{7}, 17)), + EXPECT_EQ(SpyHash(std::make_pair(TypeErasedValue<size_t>(7), 17)), SpyHash(std::make_pair(size_t{7}, 17))); }
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index b1e33ca..97b68ba 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -502,10 +502,9 @@ vector.size()); } +// AbslHashValue special cases for hashing std::vector<bool> #if defined(ABSL_IS_BIG_ENDIAN) && \ (defined(__GLIBCXX__) || defined(__GLIBCPP__)) -// AbslHashValue for hashing std::vector<bool> -// // 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: @@ -521,6 +520,22 @@ } return H::combine(combiner.finalize(std::move(hash_state)), vector.size()); } +#else +// When not working around the libstdc++ bug above, we still have to contend +// with the fact that std::hash<vector<bool>> is often poor quality, hashing +// directly on the internal words and on no other state. On these platforms, +// vector<bool>{1, 1} and vector<bool>{1, 1, 0} hash to the same value. +// +// Mixing in the size (as we do in our other vector<> implementations) on top +// of the library-provided hash implementation avoids this QOI issue. +template <typename H, typename T, typename Allocator> +typename std::enable_if<is_hashable<T>::value && std::is_same<T, bool>::value, + H>::type +AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { + return H::combine(std::move(hash_state), + std::hash<std::vector<T, Allocator>>{}(vector), + vector.size()); +} #endif // -----------------------------------------------------------------------------
diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index 9d1c67f..7fbd460 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt
@@ -1210,5 +1210,6 @@ absl::random_internal_wide_multiply absl::bits absl::int128 + GTest::gmock GTest::gtest_main )
diff --git a/absl/random/distributions.h b/absl/random/distributions.h index 31c7969..37fc3aa 100644 --- a/absl/random/distributions.h +++ b/absl/random/distributions.h
@@ -373,7 +373,7 @@ template <typename IntType, typename URBG> IntType LogUniform(URBG&& urbg, // NOLINT(runtime/references) IntType lo, IntType hi, IntType base = 2) { - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Template-argument 'IntType' must be an integral type, in " "absl::LogUniform<IntType, URBG>(...)"); @@ -403,7 +403,7 @@ template <typename IntType, typename URBG> IntType Poisson(URBG&& urbg, // NOLINT(runtime/references) double mean = 1.0) { - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Template-argument 'IntType' must be an integral type, in " "absl::Poisson<IntType, URBG>(...)"); @@ -435,7 +435,7 @@ IntType Zipf(URBG&& urbg, // NOLINT(runtime/references) IntType hi = (std::numeric_limits<IntType>::max)(), double q = 2.0, double v = 1.0) { - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Template-argument 'IntType' must be an integral type, in " "absl::Zipf<IntType, URBG>(...)");
diff --git a/absl/random/distributions_test.cc b/absl/random/distributions_test.cc index d3a5dd7..5321a11 100644 --- a/absl/random/distributions_test.cc +++ b/absl/random/distributions_test.cc
@@ -220,6 +220,7 @@ absl::Uniform<uint16_t>(gen); absl::Uniform<uint32_t>(gen); absl::Uniform<uint64_t>(gen); + absl::Uniform<absl::uint128>(gen); } TEST_F(RandomDistributionsTest, UniformNonsenseRanges) {
diff --git a/absl/random/generators_test.cc b/absl/random/generators_test.cc index 41725f1..14fd24e 100644 --- a/absl/random/generators_test.cc +++ b/absl/random/generators_test.cc
@@ -107,6 +107,8 @@ absl::Poisson<int64_t>(*gen); absl::Poisson<uint64_t>(*gen); absl::Poisson<uint64_t>(URBG()); + absl::Poisson<absl::int128>(*gen); + absl::Poisson<absl::uint128>(*gen); } template <typename URBG> @@ -126,6 +128,8 @@ absl::Zipf<int64_t>(*gen, 1 << 10); absl::Zipf<uint64_t>(*gen, 1 << 10); absl::Zipf<uint64_t>(URBG(), 1 << 10); + absl::Zipf<absl::int128>(*gen, 1 << 10); + absl::Zipf<absl::uint128>(*gen, 1 << 10); } template <typename URBG> @@ -146,6 +150,8 @@ absl::LogUniform<int64_t>(*gen, 0, 1 << 10); absl::LogUniform<uint64_t>(*gen, 0, 1 << 10); absl::LogUniform<uint64_t>(URBG(), 0, 1 << 10); + absl::LogUniform<absl::int128>(*gen, 0, 1 << 10); + absl::LogUniform<absl::uint128>(*gen, 0, 1 << 10); } template <typename URBG>
diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index e93eebb..67808aa 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel
@@ -35,7 +35,11 @@ hdrs = ["traits.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/base:config"], + deps = [ + "//absl/base:config", + "//absl/numeric:bits", + "//absl/numeric:int128", + ], ) cc_library( @@ -58,6 +62,7 @@ copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":traits", "//absl/base:config", "//absl/meta:type_traits", ], @@ -674,6 +679,7 @@ ":traits", "//absl/base:config", "//absl/meta:type_traits", + "//absl/numeric:int128", ], )
diff --git a/absl/random/internal/fast_uniform_bits.h b/absl/random/internal/fast_uniform_bits.h index 425aaf7..f3a5c00 100644 --- a/absl/random/internal/fast_uniform_bits.h +++ b/absl/random/internal/fast_uniform_bits.h
@@ -22,6 +22,7 @@ #include "absl/base/config.h" #include "absl/meta/type_traits.h" +#include "absl/random/internal/traits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -98,7 +99,7 @@ result_type operator()(URBG& g); // NOLINT(runtime/references) private: - static_assert(std::is_unsigned<UIntType>::value, + static_assert(IsUnsigned<UIntType>::value, "Class-template FastUniformBits<> must be parameterized using " "an unsigned type.");
diff --git a/absl/random/internal/traits.h b/absl/random/internal/traits.h index 75772bd..f874a0f 100644 --- a/absl/random/internal/traits.h +++ b/absl/random/internal/traits.h
@@ -20,6 +20,8 @@ #include <type_traits> #include "absl/base/config.h" +#include "absl/numeric/bits.h" +#include "absl/numeric/int128.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -59,6 +61,31 @@ rank<A>() <= rank<B>(); }; +template <typename T> +struct IsIntegral : std::is_integral<T> {}; +template <> +struct IsIntegral<absl::int128> : std::true_type {}; +template <> +struct IsIntegral<absl::uint128> : std::true_type {}; + +template <typename T> +struct MakeUnsigned : std::make_unsigned<T> {}; +template <> +struct MakeUnsigned<absl::int128> { + using type = absl::uint128; +}; +template <> +struct MakeUnsigned<absl::uint128> { + using type = absl::uint128; +}; + +template <typename T> +struct IsUnsigned : std::is_unsigned<T> {}; +template <> +struct IsUnsigned<absl::int128> : std::false_type {}; +template <> +struct IsUnsigned<absl::uint128> : std::true_type {}; + // unsigned_bits<N>::type returns the unsigned int type with the indicated // number of bits. template <size_t N> @@ -81,19 +108,40 @@ using type = uint64_t; }; -#ifdef ABSL_HAVE_INTRINSIC_INT128 template <> struct unsigned_bits<128> { - using type = __uint128_t; + using type = absl::uint128; }; -#endif + +// 256-bit wrapper for wide multiplications. +struct U256 { + uint128 hi; + uint128 lo; +}; +template <> +struct unsigned_bits<256> { + using type = U256; +}; template <typename IntType> struct make_unsigned_bits { - using type = typename unsigned_bits<std::numeric_limits< - typename std::make_unsigned<IntType>::type>::digits>::type; + using type = typename unsigned_bits< + std::numeric_limits<typename MakeUnsigned<IntType>::type>::digits>::type; }; +template <typename T> +int BitWidth(T v) { + // Workaround for bit_width not supporting int128. + // Don't hardcode `64` to make sure this code does not trigger compiler + // warnings in smaller types. + constexpr int half_bits = sizeof(T) * 8 / 2; + if (sizeof(T) == 16 && (v >> half_bits) != 0) { + return bit_width(static_cast<uint64_t>(v >> half_bits)) + half_bits; + } else { + return bit_width(static_cast<uint64_t>(v)); + } +} + } // namespace random_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/random/internal/uniform_helper.h b/absl/random/internal/uniform_helper.h index 1243bc1..e68b82e 100644 --- a/absl/random/internal/uniform_helper.h +++ b/absl/random/internal/uniform_helper.h
@@ -100,7 +100,7 @@ template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< - std::is_integral<IntType>, + IsIntegral<IntType>, absl::disjunction<std::is_same<Tag, IntervalOpenClosedTag>, std::is_same<Tag, IntervalOpenOpenTag>>>::value, IntType> @@ -131,7 +131,7 @@ template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< - std::is_integral<IntType>, + IsIntegral<IntType>, absl::disjunction<std::is_same<Tag, IntervalClosedOpenTag>, std::is_same<Tag, IntervalOpenOpenTag>>>::value, IntType> @@ -153,7 +153,7 @@ template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< - std::is_integral<IntType>, + IsIntegral<IntType>, absl::disjunction<std::is_same<Tag, IntervalClosedClosedTag>, std::is_same<Tag, IntervalOpenClosedTag>>>::value, IntType> @@ -201,7 +201,7 @@ } template <typename IntType> -absl::enable_if_t<std::is_integral<IntType>::value, bool> +absl::enable_if_t<IsIntegral<IntType>::value, bool> is_uniform_range_valid(IntType a, IntType b) { return a <= b; } @@ -210,7 +210,7 @@ // or absl::uniform_real_distribution depending on the NumType parameter. template <typename NumType> using UniformDistribution = - typename std::conditional<std::is_integral<NumType>::value, + typename std::conditional<IsIntegral<NumType>::value, absl::uniform_int_distribution<NumType>, absl::uniform_real_distribution<NumType>>::type;
diff --git a/absl/random/internal/wide_multiply.h b/absl/random/internal/wide_multiply.h index b6e6c4b..891e363 100644 --- a/absl/random/internal/wide_multiply.h +++ b/absl/random/internal/wide_multiply.h
@@ -34,43 +34,6 @@ ABSL_NAMESPACE_BEGIN namespace random_internal { -// Helper object to multiply two 64-bit values to a 128-bit value. -// MultiplyU64ToU128 multiplies two 64-bit values to a 128-bit value. -// If an intrinsic is available, it is used, otherwise use native 32-bit -// multiplies to construct the result. -inline absl::uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return absl::uint128(static_cast<__uint128_t>(a) * b); -#elif defined(ABSL_INTERNAL_USE_UMUL128) - // uint64_t * uint64_t => uint128 multiply using imul intrinsic on MSVC. - uint64_t high = 0; - const uint64_t low = _umul128(a, b, &high); - return absl::MakeUint128(high, low); -#else - // uint128(a) * uint128(b) in emulated mode computes a full 128-bit x 128-bit - // multiply. However there are many cases where that is not necessary, and it - // is only necessary to support a 64-bit x 64-bit = 128-bit multiply. This is - // for those cases. - const uint64_t a00 = static_cast<uint32_t>(a); - const uint64_t a32 = a >> 32; - const uint64_t b00 = static_cast<uint32_t>(b); - const uint64_t b32 = b >> 32; - - const uint64_t c00 = a00 * b00; - const uint64_t c32a = a00 * b32; - const uint64_t c32b = a32 * b00; - const uint64_t c64 = a32 * b32; - - const uint32_t carry = - static_cast<uint32_t>(((c00 >> 32) + static_cast<uint32_t>(c32a) + - static_cast<uint32_t>(c32b)) >> - 32); - - return absl::MakeUint128(c64 + (c32a >> 32) + (c32b >> 32) + carry, - c00 + (c32a << 32) + (c32b << 32)); -#endif -} - // wide_multiply<T> multiplies two N-bit values to a 2N-bit result. template <typename UIntType> struct wide_multiply { @@ -82,27 +45,49 @@ return static_cast<result_type>(a) * b; } - static input_type hi(result_type r) { return r >> kN; } - static input_type lo(result_type r) { return r; } + static input_type hi(result_type r) { + return static_cast<input_type>(r >> kN); + } + static input_type lo(result_type r) { return static_cast<input_type>(r); } static_assert(std::is_unsigned<UIntType>::value, "Class-template wide_multiply<> argument must be unsigned."); }; -#ifndef ABSL_HAVE_INTRINSIC_INT128 -template <> -struct wide_multiply<uint64_t> { - using input_type = uint64_t; - using result_type = absl::uint128; +// MultiplyU128ToU256 multiplies two 128-bit values to a 256-bit value. +inline U256 MultiplyU128ToU256(uint128 a, uint128 b) { + const uint128 a00 = static_cast<uint64_t>(a); + const uint128 a64 = a >> 64; + const uint128 b00 = static_cast<uint64_t>(b); + const uint128 b64 = b >> 64; - static result_type multiply(uint64_t a, uint64_t b) { - return MultiplyU64ToU128(a, b); + const uint128 c00 = a00 * b00; + const uint128 c64a = a00 * b64; + const uint128 c64b = a64 * b00; + const uint128 c128 = a64 * b64; + + const uint64_t carry = + static_cast<uint64_t>(((c00 >> 64) + static_cast<uint64_t>(c64a) + + static_cast<uint64_t>(c64b)) >> + 64); + + return {c128 + (c64a >> 64) + (c64b >> 64) + carry, + c00 + (c64a << 64) + (c64b << 64)}; +} + + +template <> +struct wide_multiply<uint128> { + using input_type = uint128; + using result_type = U256; + + static result_type multiply(input_type a, input_type b) { + return MultiplyU128ToU256(a, b); } - static uint64_t hi(result_type r) { return absl::Uint128High64(r); } - static uint64_t lo(result_type r) { return absl::Uint128Low64(r); } + static input_type hi(result_type r) { return r.hi; } + static input_type lo(result_type r) { return r.lo; } }; -#endif } // namespace random_internal ABSL_NAMESPACE_END
diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc index e276cb5..f8ee35c 100644 --- a/absl/random/internal/wide_multiply_test.cc +++ b/absl/random/internal/wide_multiply_test.cc
@@ -14,52 +14,106 @@ #include "absl/random/internal/wide_multiply.h" +#include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/numeric/int128.h" -using absl::random_internal::MultiplyU64ToU128; +using absl::random_internal::MultiplyU128ToU256; +using absl::random_internal::U256; namespace { -TEST(WideMultiplyTest, MultiplyU64ToU128Test) { - constexpr uint64_t k1 = 1; - constexpr uint64_t kMax = ~static_cast<uint64_t>(0); +U256 LeftShift(U256 v, int s) { + if (s == 0) { + return v; + } else if (s < 128) { + return {(v.hi << s) | (v.lo >> (128 - s)), v.lo << s}; + } else { + return {v.lo << (s - 128), 0}; + } +} - EXPECT_EQ(absl::uint128(0), MultiplyU64ToU128(0, 0)); +MATCHER_P2(Eq256, hi, lo, "") { return arg.hi == hi && arg.lo == lo; } +MATCHER_P(Eq256, v, "") { return arg.hi == v.hi && arg.lo == v.lo; } - // Max uint64_t - EXPECT_EQ(MultiplyU64ToU128(kMax, kMax), - absl::MakeUint128(0xfffffffffffffffe, 0x0000000000000001)); - EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(kMax, 1)); - EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(1, kMax)); +TEST(WideMultiplyTest, MultiplyU128ToU256Test) { + using absl::uint128; + constexpr uint128 k1 = 1; + constexpr uint128 kMax = ~static_cast<uint128>(0); + + EXPECT_THAT(MultiplyU128ToU256(0, 0), Eq256(0, 0)); + + // Max uin128_t + EXPECT_THAT(MultiplyU128ToU256(kMax, kMax), Eq256(kMax << 1, 1)); + EXPECT_THAT(MultiplyU128ToU256(kMax, 1), Eq256(0, kMax)); + EXPECT_THAT(MultiplyU128ToU256(1, kMax), Eq256(0, kMax)); for (int i = 0; i < 64; ++i) { - EXPECT_EQ(absl::MakeUint128(0, kMax) << i, - MultiplyU64ToU128(kMax, k1 << i)); - EXPECT_EQ(absl::MakeUint128(0, kMax) << i, - MultiplyU64ToU128(k1 << i, kMax)); + SCOPED_TRACE(i); + EXPECT_THAT(MultiplyU128ToU256(kMax, k1 << i), + Eq256(LeftShift({0, kMax}, i))); + EXPECT_THAT(MultiplyU128ToU256(k1 << i, kMax), + Eq256(LeftShift({0, kMax}, i))); } // 1-bit x 1-bit. for (int i = 0; i < 64; ++i) { for (int j = 0; j < 64; ++j) { - EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), - MultiplyU64ToU128(k1 << i, k1 << j)); - EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), - MultiplyU64ToU128(k1 << i, k1 << j)); + EXPECT_THAT(MultiplyU128ToU256(k1 << i, k1 << j), + Eq256(LeftShift({0, 1}, i + j))); } } // Verified multiplies - EXPECT_EQ(MultiplyU64ToU128(0xffffeeeeddddcccc, 0xbbbbaaaa99998888), - absl::MakeUint128(0xbbbb9e2692c5dddc, 0xc28f7531048d2c60)); - EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfedcba9876543210), - absl::MakeUint128(0x0121fa00ad77d742, 0x2236d88fe5618cf0)); - EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfdb97531eca86420), - absl::MakeUint128(0x0120ae99d26725fc, 0xce197f0ecac319e0)); - EXPECT_EQ(MultiplyU64ToU128(0x97a87f4f261ba3f2, 0xfedcba9876543210), - absl::MakeUint128(0x96fbf1a8ae78d0ba, 0x5a6dd4b71f278320)); - EXPECT_EQ(MultiplyU64ToU128(0xfedcba9876543210, 0xfdb97531eca86420), - absl::MakeUint128(0xfc98c6981a413e22, 0x342d0bbf48948200)); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xc502da0d6ea99fe8, 0xfa3c9141a1f50912), + absl::MakeUint128(0x96bcf1ac37f97bd6, 0x27e2cdeb5fb2299e)), + Eq256(absl::MakeUint128(0x740113d838f96a64, 0x22e8cfa4d71f89ea), + absl::MakeUint128(0x19184a345c62e993, 0x237871b630337b1c))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x6f29e670cee07230, 0xc3d8e6c3e4d86759), + absl::MakeUint128(0x3227d29fa6386db1, 0x231682bb1e4b764f)), + Eq256(absl::MakeUint128(0x15c779d9d5d3b07c, 0xd7e6c827f0c81cbe), + absl::MakeUint128(0xf88e3914f7fa287a, 0x15b79975137dea77))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xafb77107215646e1, 0x3b844cb1ac5769e7), + absl::MakeUint128(0x1ff7b2d888b62479, 0x92f758ae96fcba0b)), + Eq256(absl::MakeUint128(0x15f13b70181f6985, 0x2adb36bbabce7d02), + absl::MakeUint128(0x6c470d72e13aad04, 0x63fba3f5841762ed))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xd85d5558d67ac905, 0xf88c70654dae19b1), + absl::MakeUint128(0x17252c6727db3738, 0x399ff658c511eedc)), + Eq256(absl::MakeUint128(0x138fcdaf8b0421ee, 0x1b465ddf2a0d03f6), + absl::MakeUint128(0x8f573ba68296860f, 0xf327d2738741a21c))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x46f0421a37ff6bee, 0xa61df89f09d140b1), + absl::MakeUint128(0x3d712ec9f37ca2e1, 0x9658a2cba47ef4b1)), + Eq256(absl::MakeUint128(0x11069cc48ee7c95d, 0xd35fb1c7aa91c978), + absl::MakeUint128(0xbe2f4a6de874b015, 0xd2f7ac1b76746e61))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x730d27c72d58fa49, 0x3ebeda7498f8827c), + absl::MakeUint128(0xa2c959eca9f503af, 0x189c687eb842bbd8)), + Eq256(absl::MakeUint128(0x4928d0ea356ba022, 0x1546d34a2963393), + absl::MakeUint128(0x7481531e1e0a16d1, 0xdd8025015cf6aca0))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x6ca41020f856d2f1, 0xb9b0838c04a7f4aa), + absl::MakeUint128(0x9cf41d28a8396f54, 0x1d681695e377ffe6)), + Eq256(absl::MakeUint128(0x429b92934d9be6f1, 0xea182877157c1e7), + absl::MakeUint128(0x7135c23f0a4a475, 0xc1adc366f4a126bc))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x57472833797c332, 0x6c79272fdec4687a), + absl::MakeUint128(0xb5f022ea3838e46b, 0x16face2f003e27a6)), + Eq256(absl::MakeUint128(0x3e072e0962b3400, 0x5d9fe8fdc3d0e1f4), + absl::MakeUint128(0x7dc0df47cedafd62, 0xbe6501f1acd2551c))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xf0fb4198322eb1c2, 0xfe7f5f31f3885938), + absl::MakeUint128(0xd99012b71bb7aa31, 0xac7a6f9eb190789)), + Eq256(absl::MakeUint128(0xcccc998cf075ca01, 0x642d144322fb873a), + absl::MakeUint128(0xc79dc12b69d91ed4, 0xa83459132ce046f8))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xb5c04120848cdb47, 0x8aa62a827bf52635), + absl::MakeUint128(0x8d07a359be2f1380, 0x467bb90d59da0dea)), + Eq256(absl::MakeUint128(0x64205019d139a9ce, 0x99425c5fb6e7a977), + absl::MakeUint128(0xd3e99628a9e5fca7, 0x9c7824cb7279d72))); } } // namespace
diff --git a/absl/random/log_uniform_int_distribution.h b/absl/random/log_uniform_int_distribution.h index 43e1011..4afff8f 100644 --- a/absl/random/log_uniform_int_distribution.h +++ b/absl/random/log_uniform_int_distribution.h
@@ -69,10 +69,8 @@ if (base_ == 2) { // Determine where the first set bit is on range(), giving a log2(range) // value which can be used to construct bounds. - log_range_ = - (std::min)(bit_width(range()), - static_cast<unsigned_type>( - std::numeric_limits<unsigned_type>::digits)); + log_range_ = (std::min)(random_internal::BitWidth(range()), + std::numeric_limits<unsigned_type>::digits); } else { // NOTE: Computing the logN(x) introduces error from 2 sources: // 1. Conversion of int to double loses precision for values >= @@ -83,7 +81,7 @@ // // Thus a result which should equal K may equal K +/- epsilon, // which can eliminate some values depending on where the bounds fall. - const double inv_log_base = 1.0 / std::log(base_); + const double inv_log_base = 1.0 / std::log(static_cast<double>(base_)); const double log_range = std::log(static_cast<double>(range()) + 0.5); log_range_ = static_cast<int>(std::ceil(inv_log_base * log_range)); } @@ -113,7 +111,7 @@ unsigned_type range_; // max - min int log_range_; // ceil(logN(range_)) - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::log_uniform_int_distribution<> must be " "parameterized using an integral type."); }; @@ -139,7 +137,7 @@ template <typename URBG> result_type operator()(URBG& g, // NOLINT(runtime/references) const param_type& p) { - return (p.min)() + Generate(g, p); + return static_cast<result_type>((p.min)() + Generate(g, p)); } result_type(min)() const { return (param_.min)(); } @@ -193,8 +191,8 @@ ? (std::numeric_limits<unsigned_type>::max)() : (static_cast<unsigned_type>(1) << e) - 1; } else { - const double r = std::pow(p.base(), d); - const double s = (r * p.base()) - 1.0; + const double r = std::pow(static_cast<double>(p.base()), d); + const double s = (r * static_cast<double>(p.base())) - 1.0; base_e = (r > static_cast<double>((std::numeric_limits<unsigned_type>::max)())) @@ -211,7 +209,8 @@ const unsigned_type hi = (top_e >= p.range()) ? p.range() : top_e; // choose uniformly over [lo, hi] - return absl::uniform_int_distribution<result_type>(lo, hi)(g); + return absl::uniform_int_distribution<result_type>( + static_cast<result_type>(lo), static_cast<result_type>(hi))(g); } template <typename CharT, typename Traits, typename IntType>
diff --git a/absl/random/poisson_distribution.h b/absl/random/poisson_distribution.h index cb5f5d5..f457308 100644 --- a/absl/random/poisson_distribution.h +++ b/absl/random/poisson_distribution.h
@@ -26,6 +26,7 @@ #include "absl/random/internal/fastmath.h" #include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" +#include "absl/random/internal/traits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -80,7 +81,7 @@ double log_k_; int split_; - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::poisson_distribution<> must be " "parameterized using an integral type."); }; @@ -133,7 +134,8 @@ poisson_distribution<IntType>::param_type::param_type(double mean) : mean_(mean), split_(0) { assert(mean >= 0); - assert(mean <= (std::numeric_limits<result_type>::max)()); + assert(mean <= + static_cast<double>((std::numeric_limits<result_type>::max)())); // As a defensive measure, avoid large values of the mean. The rejection // algorithm used does not support very large values well. It my be worth // changing algorithms to better deal with these cases. @@ -222,8 +224,9 @@ // clang-format on const double lhs = 2.0 * std::log(u) + p.log_k_ + s; if (lhs < rhs) { - return x > (max)() ? (max)() - : static_cast<result_type>(x); // f(x)/k >= u^2 + return x > static_cast<double>((max)()) + ? (max)() + : static_cast<result_type>(x); // f(x)/k >= u^2 } } }
diff --git a/absl/random/uniform_int_distribution.h b/absl/random/uniform_int_distribution.h index c1f54cc..fae8025 100644 --- a/absl/random/uniform_int_distribution.h +++ b/absl/random/uniform_int_distribution.h
@@ -97,7 +97,7 @@ result_type lo_; unsigned_type range_; - static_assert(std::is_integral<result_type>::value, + static_assert(random_internal::IsIntegral<result_type>::value, "Class-template absl::uniform_int_distribution<> must be " "parameterized using an integral type."); }; // param_type @@ -125,7 +125,7 @@ template <typename URBG> result_type operator()( URBG& gen, const param_type& param) { // NOLINT(runtime/references) - return param.a() + Generate(gen, param.range()); + return static_cast<result_type>(param.a() + Generate(gen, param.range())); } result_type a() const { return param_.a(); }
diff --git a/absl/random/zipf_distribution.h b/absl/random/zipf_distribution.h index 22ebc75..ed4038f 100644 --- a/absl/random/zipf_distribution.h +++ b/absl/random/zipf_distribution.h
@@ -23,6 +23,7 @@ #include <type_traits> #include "absl/random/internal/iostream_state_saver.h" +#include "absl/random/internal/traits.h" #include "absl/random/uniform_real_distribution.h" namespace absl { @@ -94,7 +95,7 @@ double hxm_; // h(k + 0.5) double hx0_minus_hxm_; // h(x0) - h(k + 0.5) - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::zipf_distribution<> must be " "parameterized using an integral type."); }; @@ -221,7 +222,7 @@ const double u = p.hxm_ + v * p.hx0_minus_hxm_; const double x = p.hinv(u); k = rint(x); // std::floor(x + 0.5); - if (k > p.k()) continue; // reject k > max_k + if (k > static_cast<double>(p.k())) continue; // reject k > max_k if (k - x <= p.s_) break; const double h = p.h(k + 0.5); const double r = p.pow_negative_q(p.v_ + k);
diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 3f0633b..662e889 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h
@@ -855,6 +855,11 @@ // Returns true if the Cord is being profiled by cordz. bool is_profiled() const { return data_.is_tree() && data_.is_profiled(); } + // Returns the available inlined capacity, or 0 if is_tree() == true. + size_t inline_capacity() const { + return data_.is_tree() ? 0 : kMaxInline - data_.inline_size(); + } + // Returns the profiled CordzInfo, or nullptr if not sampled. absl::cord_internal::CordzInfo* cordz_info() const { return data_.cordz_info();
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 188fbc2..8a31179 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc
@@ -43,6 +43,10 @@ #include "absl/strings/str_format.h" #include "absl/strings/string_view.h" +// convenience local constants +static constexpr auto FLAT = absl::cord_internal::FLAT; +static constexpr auto MAX_FLAT_TAG = absl::cord_internal::MAX_FLAT_TAG; + typedef std::mt19937_64 RandomEngine; static std::string RandomLowercaseString(RandomEngine* rng); @@ -260,6 +264,74 @@ INSTANTIATE_TEST_SUITE_P(WithParam, CordTest, testing::Values(0, 1, 2, 3), CordTest::ToString); + +TEST(CordRepFlat, AllFlatCapacities) { + using absl::cord_internal::CordRep; + using absl::cord_internal::CordRepFlat; + using absl::cord_internal::kFlatOverhead; + + // Explicitly and redundantly assert built-in min/max limits + static_assert(absl::cord_internal::kFlatOverhead < 32, ""); + static_assert(absl::cord_internal::kMinFlatSize == 32, ""); + static_assert(absl::cord_internal::kMaxLargeFlatSize == 256 << 10, ""); + EXPECT_EQ(absl::cord_internal::TagToAllocatedSize(FLAT), 32); + EXPECT_EQ(absl::cord_internal::TagToAllocatedSize(MAX_FLAT_TAG), 256 << 10); + + // Verify all tags to map perfectly back and forth, and + // that sizes are monotonically increasing. + size_t last_size = 0; + for (int tag = FLAT; tag <= MAX_FLAT_TAG; ++tag) { + size_t size = absl::cord_internal::TagToAllocatedSize(tag); + ASSERT_GT(size, last_size); + ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size); + last_size = size; + } + + // All flat size from 32 - 512 are 8 byte granularity + for (size_t size = 32; size <= 512; size += 8) { + ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size); + uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size); + ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size); + } + + // All flat sizes from 512 - 8192 are 64 byte granularity + for (size_t size = 512; size <= 8192; size += 64) { + ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size); + uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size); + ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size); + } + + // All flat sizes from 8KB to 256KB are 4KB granularity + for (size_t size = 8192; size <= 256 * 1024; size += 4 * 1024) { + ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size); + uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size); + ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size); + } +} + +TEST(CordRepFlat, MaxFlatSize) { + using absl::cord_internal::CordRep; + using absl::cord_internal::CordRepFlat; + using absl::cord_internal::kMaxFlatLength; + CordRepFlat* flat = CordRepFlat::New(kMaxFlatLength); + EXPECT_EQ(flat->Capacity(), kMaxFlatLength); + CordRep::Unref(flat); + + flat = CordRepFlat::New(kMaxFlatLength * 4); + EXPECT_EQ(flat->Capacity(), kMaxFlatLength); + CordRep::Unref(flat); +} + +TEST(CordRepFlat, MaxLargeFlatSize) { + using absl::cord_internal::CordRep; + using absl::cord_internal::CordRepFlat; + using absl::cord_internal::kFlatOverhead; + const size_t size = 256 * 1024 - kFlatOverhead; + CordRepFlat* flat = CordRepFlat::New(CordRepFlat::Large(), size); + EXPECT_GE(flat->Capacity(), size); + CordRep::Unref(flat); +} + TEST_P(CordTest, AllFlatSizes) { using absl::strings_internal::CordTestAccess;
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 672bf17..b16c8fa 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h
@@ -185,13 +185,16 @@ EXTERNAL = 5, // We have different tags for different sized flat arrays, - // starting with FLAT, and limited to MAX_FLAT_TAG. The 226 value is based on - // the current 'size to tag' encoding of 8 / 32 bytes. If a new tag is needed - // in the future, then 'FLAT' and 'MAX_FLAT_TAG' should be adjusted as well - // as the Tag <---> Size logic so that FLAT stil represents the minimum flat - // allocation size. (32 bytes as of now). + // starting with FLAT, and limited to MAX_FLAT_TAG. The below values map to an + // allocated range of 32 bytes to 256 KB. The current granularity is: + // - 8 byte granularity for flat sizes in [32 - 512] + // - 64 byte granularity for flat sizes in (512 - 8KiB] + // - 4KiB byte granularity for flat sizes in (8KiB, 256 KiB] + // If a new tag is needed in the future, then 'FLAT' and 'MAX_FLAT_TAG' should + // be adjusted as well as the Tag <---> Size mapping logic so that FLAT still + // represents the minimum flat allocation size. (32 bytes as of now). FLAT = 6, - MAX_FLAT_TAG = 226 + MAX_FLAT_TAG = 248 }; // There are various locations where we want to check if some rep is a 'plain'
diff --git a/absl/strings/internal/cord_rep_btree.cc b/absl/strings/internal/cord_rep_btree.cc index 7cefcc5..f436bc1 100644 --- a/absl/strings/internal/cord_rep_btree.cc +++ b/absl/strings/internal/cord_rep_btree.cc
@@ -190,24 +190,29 @@ } } -// Deletes a leaf node data edge. Requires `rep` to be an EXTERNAL or FLAT -// node, or a SUBSTRING of an EXTERNAL or FLAT node. -void DeleteLeafEdge(CordRep* rep) { - for (;;) { + +void DeleteSubstring(CordRepSubstring* substring) { + CordRep* rep = substring->child; + if (!rep->refcount.Decrement()) { if (rep->tag >= FLAT) { CordRepFlat::Delete(rep->flat()); - return; - } - if (rep->tag == EXTERNAL) { + } else { + assert(rep->tag == EXTERNAL); CordRepExternal::Delete(rep->external()); - return; } - assert(rep->tag == SUBSTRING); - CordRepSubstring* substring = rep->substring(); - rep = substring->child; - assert(rep->tag == EXTERNAL || rep->tag >= FLAT); - delete substring; - if (rep->refcount.Decrement()) return; + } + delete substring; +} + +// Deletes a leaf node data edge. Requires `IsDataEdge(rep)`. +void DeleteLeafEdge(CordRep* rep) { + assert(CordRepBtree::IsDataEdge(rep)); + if (rep->tag >= FLAT) { + CordRepFlat::Delete(rep->flat()); + } else if (rep->tag == EXTERNAL) { + CordRepExternal::Delete(rep->external()); + } else { + DeleteSubstring(rep->substring()); } } @@ -372,19 +377,37 @@ Dump(rep, absl::string_view(), false, stream); } -void CordRepBtree::DestroyLeaf(CordRepBtree* tree, size_t begin, size_t end) { - for (CordRep* edge : tree->Edges(begin, end)) { - FastUnref(edge, DeleteLeafEdge); +template <size_t size> +static void DestroyTree(CordRepBtree* tree) { + for (CordRep* node : tree->Edges()) { + if (node->refcount.Decrement()) continue; + for (CordRep* edge : node->btree()->Edges()) { + if (edge->refcount.Decrement()) continue; + if (size == 1) { + DeleteLeafEdge(edge); + } else { + CordRepBtree::Destroy(edge->btree()); + } + } + CordRepBtree::Delete(node->btree()); } - Delete(tree); + CordRepBtree::Delete(tree); } -void CordRepBtree::DestroyNonLeaf(CordRepBtree* tree, size_t begin, - size_t end) { - for (CordRep* edge : tree->Edges(begin, end)) { - FastUnref(edge->btree(), Destroy); +void CordRepBtree::Destroy(CordRepBtree* tree) { + switch (tree->height()) { + case 0: + for (CordRep* edge : tree->Edges()) { + if (!edge->refcount.Decrement()) { + DeleteLeafEdge(edge); + } + } + return CordRepBtree::Delete(tree); + case 1: + return DestroyTree<1>(tree); + default: + return DestroyTree<2>(tree); } - Delete(tree); } bool CordRepBtree::IsValid(const CordRepBtree* tree, bool shallow) {
diff --git a/absl/strings/internal/cord_rep_btree.h b/absl/strings/internal/cord_rep_btree.h index 0b44509..df5c994 100644 --- a/absl/strings/internal/cord_rep_btree.h +++ b/absl/strings/internal/cord_rep_btree.h
@@ -163,6 +163,9 @@ // typically after a ref_count.Decrement() on the last reference count. static void Destroy(CordRepBtree* tree); + // Destruction + static void Delete(CordRepBtree* tree) { delete tree; } + // Use CordRep::Unref() as we overload for absl::Span<CordRep* const>. using CordRep::Unref; @@ -440,12 +443,6 @@ // Requires `offset` < length. Position IndexBeyond(size_t offset) const; - // Destruction - static void DestroyLeaf(CordRepBtree* tree, size_t begin, size_t end); - static void DestroyNonLeaf(CordRepBtree* tree, size_t begin, size_t end); - static void DestroyTree(CordRepBtree* tree, size_t begin, size_t end); - static void Delete(CordRepBtree* tree) { delete tree; } - // Creates a new leaf node containing as much data as possible from `data`. // The data is added either forwards or reversed depending on `edge_type`. // Callers must check the length of the returned node to determine if all data @@ -689,19 +686,6 @@ return tree; } -inline void CordRepBtree::DestroyTree(CordRepBtree* tree, size_t begin, - size_t end) { - if (tree->height() == 0) { - DestroyLeaf(tree, begin, end); - } else { - DestroyNonLeaf(tree, begin, end); - } -} - -inline void CordRepBtree::Destroy(CordRepBtree* tree) { - DestroyTree(tree, tree->begin(), tree->end()); -} - inline void CordRepBtree::Unref(absl::Span<CordRep* const> edges) { for (CordRep* edge : edges) { if (ABSL_PREDICT_FALSE(!edge->refcount.Decrement())) {
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h index 62cf584..a15c9ac 100644 --- a/absl/strings/internal/cord_rep_flat.h +++ b/absl/strings/internal/cord_rep_flat.h
@@ -42,14 +42,34 @@ static constexpr size_t kMaxFlatSize = 4096; static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead; static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead; +static constexpr size_t kMaxLargeFlatSize = 256 * 1024; +static constexpr size_t kMaxLargeFlatLength = kMaxLargeFlatSize - kFlatOverhead; +// kTagBase should make the Size <--> Tag computation resilient +// against changes to the value of FLAT when we add a new tag.. +static constexpr uint8_t kTagBase = FLAT - 4; + +// Converts the provided rounded size to the corresponding tag constexpr uint8_t AllocatedSizeToTagUnchecked(size_t size) { - return static_cast<uint8_t>((size <= 1024) ? size / 8 + 2 - : 130 + size / 32 - 1024 / 32); + return static_cast<uint8_t>(size <= 512 ? kTagBase + size / 8 + : size <= 8192 + ? kTagBase + 512 / 8 + size / 64 - 512 / 64 + : kTagBase + 512 / 8 + ((8192 - 512) / 64) + + size / 4096 - 8192 / 4096); } -static_assert(kMinFlatSize / 8 + 2 >= FLAT, ""); -static_assert(AllocatedSizeToTagUnchecked(kMaxFlatSize) <= MAX_FLAT_TAG, ""); +// Converts the provided tag to the corresponding allocated size +constexpr size_t TagToAllocatedSize(uint8_t tag) { + return (tag <= kTagBase + 512 / 8) ? tag * 8 - kTagBase * 8 + : (tag <= kTagBase + (512 / 8) + ((8192 - 512) / 64)) + ? 512 + tag * 64 - kTagBase * 64 - 512 / 8 * 64 + : 8192 + tag * 4096 - kTagBase * 4096 - + ((512 / 8) + ((8192 - 512) / 64)) * 4096; +} + +static_assert(AllocatedSizeToTagUnchecked(kMinFlatSize) == FLAT, ""); +static_assert(AllocatedSizeToTagUnchecked(kMaxLargeFlatSize) == MAX_FLAT_TAG, + ""); // Helper functions for rounded div, and rounding to exact sizes. constexpr size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; } @@ -58,7 +78,7 @@ // Returns the size to the nearest equal or larger value that can be // expressed exactly as a tag value. inline size_t RoundUpForTag(size_t size) { - return RoundUp(size, (size <= 1024) ? 8 : 32); + return RoundUp(size, (size <= 512) ? 8 : (size <= 8192 ? 64 : 4096)); } // Converts the allocated size to a tag, rounding down if the size @@ -71,26 +91,26 @@ return tag; } -// Converts the provided tag to the corresponding allocated size -constexpr size_t TagToAllocatedSize(uint8_t tag) { - return (tag <= 130) ? ((tag - 2) * 8) : (1024 + (tag - 130) * 32); -} - // Converts the provided tag to the corresponding available data length constexpr size_t TagToLength(uint8_t tag) { return TagToAllocatedSize(tag) - kFlatOverhead; } // Enforce that kMaxFlatSize maps to a well-known exact tag value. -static_assert(TagToAllocatedSize(226) == kMaxFlatSize, "Bad tag logic"); +static_assert(TagToAllocatedSize(MAX_FLAT_TAG) == kMaxLargeFlatSize, + "Bad tag logic"); struct CordRepFlat : public CordRep { + // Tag for explicit 'large flat' allocation + struct Large {}; + // Creates a new flat node. - static CordRepFlat* New(size_t len) { + template <size_t max_flat_size> + static CordRepFlat* NewImpl(size_t len) { if (len <= kMinFlatLength) { len = kMinFlatLength; - } else if (len > kMaxFlatLength) { - len = kMaxFlatLength; + } else if (len > max_flat_size - kFlatOverhead) { + len = max_flat_size - kFlatOverhead; } // Round size up so it matches a size we can exactly express in a tag. @@ -101,6 +121,12 @@ return rep; } + static CordRepFlat* New(size_t len) { return NewImpl<kMaxFlatSize>(len); } + + static CordRepFlat* New(Large, size_t len) { + return NewImpl<kMaxLargeFlatSize>(len); + } + // Deletes a CordRepFlat instance created previously through a call to New(). // Flat CordReps are allocated and constructed with raw ::operator new and // placement new, and must be destructed and deallocated accordingly. @@ -117,6 +143,17 @@ #endif } + // Create a CordRepFlat containing `data`, with an optional additional + // extra capacity of up to `extra` bytes. Requires that `data.size()` + // is less than kMaxFlatLength. + static CordRepFlat* Create(absl::string_view data, size_t extra = 0) { + assert(data.size() <= kMaxFlatLength); + CordRepFlat* flat = New(data.size() + (std::min)(extra, kMaxFlatLength)); + memcpy(flat->Data(), data.data(), data.size()); + flat->length = data.size(); + return flat; + } + // Returns a pointer to the data inside this flat rep. char* Data() { return reinterpret_cast<char*>(storage); } const char* Data() const { return reinterpret_cast<const char*>(storage); }