summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-03-09 12:34:31 -0700
committerGravatar Derek Mauro <dmauro@google.com>2020-03-09 16:10:21 -0400
commitd936052d32a5b7ca08b0199a6724724aea432309 (patch)
treef14866c5460c73ba3ba3812941a0426ad51496cd /absl
parent238b9a59c874f8271ce781d9d05d81eb61728132 (diff)
Export of internal Abseil changes
-- 2c5c118f0615ba90e48ee2f18eccc9f511740f6d by Samuel Benzaquen <sbenza@google.com>: Rename internal macros to follow the convention in absl. PiperOrigin-RevId: 299906738 -- 92d84a707c7ebc4ec19bdd92d5765d1b6d218c1e by Derek Mauro <dmauro@google.com>: Import GitHub #629: Skip the .exe suffix in the helpshort filter on Windows PiperOrigin-RevId: 299892396 -- 2a6910d4be6c67a8376628764121b528ff53504d by Abseil Team <absl-team@google.com>: Use unsigned int128 intrinsic when available. It generates better branchless code. PiperOrigin-RevId: 299848585 -- 110c16cf0a739e1df5028fb6fbd03ef5dde1d278 by Derek Mauro <dmauro@google.com>: Import GitHub #594: Avoid reading the registry for Windows UWP apps PiperOrigin-RevId: 299821671 -- d8397d367e88163e5e8a47f379c716352dc91d03 by Greg Falcon <gfalcon@google.com>: Add absl::Hash support for Cord. The hash function is heterogeneous with other string types: a Cord and a string with the same byte sequence will hash to the same value. SwissTable types know about Cord, and will allow heterogeneous lookup (e.g., you can pass a Cord to flat_hash_map<string, T>::find(), and vice versa.) Add a missing dependency to the cmake Cord target. PiperOrigin-RevId: 299443713 GitOrigin-RevId: 2c5c118f0615ba90e48ee2f18eccc9f511740f6d Change-Id: I7b087c7984b0cb52c4b337d49266c467b98ebdf9
Diffstat (limited to 'absl')
-rw-r--r--absl/base/internal/sysinfo.cc6
-rw-r--r--absl/container/BUILD.bazel7
-rw-r--r--absl/container/CMakeLists.txt6
-rw-r--r--absl/container/btree_benchmark.cc6
-rw-r--r--absl/container/btree_test.cc6
-rw-r--r--absl/container/btree_test.h11
-rw-r--r--absl/container/internal/btree.h40
-rw-r--r--absl/container/internal/hash_function_defaults.h15
-rw-r--r--absl/container/internal/hash_function_defaults_test.cc86
-rw-r--r--absl/container/internal/hashtablez_sampler.cc2
-rw-r--r--absl/container/internal/hashtablez_sampler.h2
-rw-r--r--absl/container/internal/hashtablez_sampler_test.cc2
-rw-r--r--absl/container/internal/have_sse.h19
-rw-r--r--absl/container/internal/raw_hash_set.h10
-rw-r--r--absl/hash/BUILD.bazel2
-rw-r--r--absl/hash/CMakeLists.txt2
-rw-r--r--absl/hash/hash.h1
-rw-r--r--absl/hash/hash_test.cc49
-rw-r--r--absl/hash/internal/hash.h21
-rw-r--r--absl/numeric/int128.h31
-rw-r--r--absl/strings/CMakeLists.txt1
21 files changed, 274 insertions, 51 deletions
diff --git a/absl/base/internal/sysinfo.cc b/absl/base/internal/sysinfo.cc
index 2ec57930..72f9f173 100644
--- a/absl/base/internal/sysinfo.cc
+++ b/absl/base/internal/sysinfo.cc
@@ -72,10 +72,10 @@ static int GetNumCPUs() {
#if defined(_WIN32)
static double GetNominalCPUFrequency() {
-// UWP apps don't have access to the registry and currently don't provide an
-// API informing about CPU nominal frequency.
#if WINAPI_FAMILY_PARTITION(WINAPI_PARTITION_APP) && \
!WINAPI_FAMILY_PARTITION(WINAPI_PARTITION_DESKTOP)
+ // UWP apps don't have access to the registry and currently don't provide an
+ // API informing about CPU nominal frequency.
return 1.0;
#else
#pragma comment(lib, "advapi32.lib") // For Reg* functions.
@@ -97,7 +97,7 @@ static double GetNominalCPUFrequency() {
}
}
return 1.0;
-#endif // WINAPI_PARTITION_APP && !WINAPI_PARTITION_DESKTOP
+#endif // WINAPI_PARTITION_APP && !WINAPI_PARTITION_DESKTOP
}
#elif defined(CTL_HW) && defined(HW_CPU_FREQ)
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index f2217140..70985641 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -390,6 +390,7 @@ cc_library(
"//absl/base:config",
"//absl/hash",
"//absl/strings",
+ "//absl/strings:cord",
],
)
@@ -402,7 +403,10 @@ cc_test(
deps = [
":hash_function_defaults",
"//absl/hash",
+ "//absl/random",
"//absl/strings",
+ "//absl/strings:cord",
+ "//absl/strings:cord_test_helpers",
"@com_google_googletest//:gtest_main",
],
)
@@ -828,6 +832,7 @@ cc_library(
"//absl/memory",
"//absl/meta:type_traits",
"//absl/strings",
+ "//absl/strings:cord",
"//absl/types:compare",
"//absl/utility",
],
@@ -844,6 +849,7 @@ cc_library(
":btree",
":flat_hash_set",
"//absl/strings",
+ "//absl/strings:cord",
"//absl/time",
],
)
@@ -895,6 +901,7 @@ cc_binary(
"//absl/flags:flag",
"//absl/hash",
"//absl/memory",
+ "//absl/strings:cord",
"//absl/strings:str_format",
"//absl/time",
"@com_github_google_benchmark//:benchmark_main",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index e702ba85..99a8e9c0 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -40,6 +40,7 @@ absl_cc_library(
absl::compare
absl::compressed_tuple
absl::container_memory
+ absl::cord
absl::core_headers
absl::layout
absl::memory
@@ -60,6 +61,7 @@ absl_cc_library(
${ABSL_DEFAULT_LINKOPTS}
DEPS
absl::btree
+ absl::cord
absl::flat_hash_set
absl::strings
absl::time
@@ -443,6 +445,7 @@ absl_cc_library(
${ABSL_DEFAULT_COPTS}
DEPS
absl::config
+ absl::cord
absl::hash
absl::strings
PUBLIC
@@ -456,8 +459,11 @@ absl_cc_test(
COPTS
${ABSL_TEST_COPTS}
DEPS
+ absl::cord
+ absl::cord_test_helpers
absl::hash_function_defaults
absl::hash
+ absl::random_random
absl::strings
gmock_main
)
diff --git a/absl/container/btree_benchmark.cc b/absl/container/btree_benchmark.cc
index 420cfa0d..ca4d575c 100644
--- a/absl/container/btree_benchmark.cc
+++ b/absl/container/btree_benchmark.cc
@@ -36,6 +36,7 @@
#include "absl/flags/flag.h"
#include "absl/hash/hash.h"
#include "absl/memory/memory.h"
+#include "absl/strings/cord.h"
#include "absl/strings/str_format.h"
#include "absl/time/time.h"
#include "benchmark/benchmark.h"
@@ -438,6 +439,7 @@ using StdString = std::string;
STL_ORDERED_TYPES(int32_t);
STL_ORDERED_TYPES(int64_t);
STL_ORDERED_TYPES(StdString);
+STL_ORDERED_TYPES(Cord);
STL_ORDERED_TYPES(Time);
#define STL_UNORDERED_TYPES(value) \
@@ -458,6 +460,8 @@ STL_ORDERED_TYPES(Time);
using stl_unordered_multimap_##value = \
std::unordered_multimap<value, intptr_t, hash>
+STL_UNORDERED_TYPES_CUSTOM_HASH(Cord, absl::Hash<absl::Cord>);
+
STL_UNORDERED_TYPES(int32_t);
STL_UNORDERED_TYPES(int64_t);
STL_UNORDERED_TYPES(StdString);
@@ -478,6 +482,7 @@ STL_UNORDERED_TYPES_CUSTOM_HASH(Time, absl::Hash<absl::Time>);
BTREE_TYPES(int32_t);
BTREE_TYPES(int64_t);
BTREE_TYPES(StdString);
+BTREE_TYPES(Cord);
BTREE_TYPES(Time);
#define MY_BENCHMARK4(type, func) \
@@ -526,6 +531,7 @@ BTREE_TYPES(Time);
MY_BENCHMARK(int32_t);
MY_BENCHMARK(int64_t);
MY_BENCHMARK(StdString);
+MY_BENCHMARK(Cord);
MY_BENCHMARK(Time);
// Define a type whose size and cost of moving are independently customizable.
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index ce12e819..da8e7082 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -812,10 +812,12 @@ void MapTest() {
TEST(Btree, set_int32) { SetTest<int32_t>(); }
TEST(Btree, set_int64) { SetTest<int64_t>(); }
TEST(Btree, set_string) { SetTest<std::string>(); }
+TEST(Btree, set_cord) { SetTest<absl::Cord>(); }
TEST(Btree, set_pair) { SetTest<std::pair<int, int>>(); }
TEST(Btree, map_int32) { MapTest<int32_t>(); }
TEST(Btree, map_int64) { MapTest<int64_t>(); }
TEST(Btree, map_string) { MapTest<std::string>(); }
+TEST(Btree, map_cord) { MapTest<absl::Cord>(); }
TEST(Btree, map_pair) { MapTest<std::pair<int, int>>(); }
template <typename K, int N = 256>
@@ -847,10 +849,12 @@ void MultiMapTest() {
TEST(Btree, multiset_int32) { MultiSetTest<int32_t>(); }
TEST(Btree, multiset_int64) { MultiSetTest<int64_t>(); }
TEST(Btree, multiset_string) { MultiSetTest<std::string>(); }
+TEST(Btree, multiset_cord) { MultiSetTest<absl::Cord>(); }
TEST(Btree, multiset_pair) { MultiSetTest<std::pair<int, int>>(); }
TEST(Btree, multimap_int32) { MultiMapTest<int32_t>(); }
TEST(Btree, multimap_int64) { MultiMapTest<int64_t>(); }
TEST(Btree, multimap_string) { MultiMapTest<std::string>(); }
+TEST(Btree, multimap_cord) { MultiMapTest<absl::Cord>(); }
TEST(Btree, multimap_pair) { MultiMapTest<std::pair<int, int>>(); }
struct CompareIntToString {
@@ -1268,6 +1272,8 @@ TEST(Btree, KeyCompareToAdapter) {
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>();
}
diff --git a/absl/container/btree_test.h b/absl/container/btree_test.h
index 218ba41d..62490807 100644
--- a/absl/container/btree_test.h
+++ b/absl/container/btree_test.h
@@ -25,6 +25,7 @@
#include "absl/container/btree_map.h"
#include "absl/container/btree_set.h"
#include "absl/container/flat_hash_set.h"
+#include "absl/strings/cord.h"
#include "absl/time/time.h"
namespace absl {
@@ -100,6 +101,16 @@ struct Generator<std::string> {
}
};
+template <>
+struct Generator<Cord> {
+ int maxval;
+ explicit Generator(int m) : maxval(m) {}
+ Cord operator()(int i) const {
+ char buf[16];
+ return Cord(GenerateDigits(buf, i, maxval));
+ }
+};
+
template <typename T, typename U>
struct Generator<std::pair<T, U> > {
Generator<typename remove_pair_const<T>::type> tgen;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 2a5c7314..301c3656 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -65,6 +65,7 @@
#include "absl/container/internal/layout.h"
#include "absl/memory/memory.h"
#include "absl/meta/type_traits.h"
+#include "absl/strings/cord.h"
#include "absl/strings/string_view.h"
#include "absl/types/compare.h"
#include "absl/utility/utility.h"
@@ -93,6 +94,19 @@ struct StringBtreeDefaultLess {
absl::string_view rhs) const {
return compare_internal::compare_result_as_ordering(lhs.compare(rhs));
}
+ StringBtreeDefaultLess(std::less<absl::Cord>) {} // NOLINT
+ absl::weak_ordering operator()(const absl::Cord &lhs,
+ const absl::Cord &rhs) const {
+ return compare_internal::compare_result_as_ordering(lhs.Compare(rhs));
+ }
+ absl::weak_ordering operator()(const absl::Cord &lhs,
+ absl::string_view rhs) const {
+ return compare_internal::compare_result_as_ordering(lhs.Compare(rhs));
+ }
+ absl::weak_ordering operator()(absl::string_view lhs,
+ const absl::Cord &rhs) const {
+ return compare_internal::compare_result_as_ordering(-rhs.Compare(lhs));
+ }
};
struct StringBtreeDefaultGreater {
@@ -107,13 +121,27 @@ struct StringBtreeDefaultGreater {
absl::string_view rhs) const {
return compare_internal::compare_result_as_ordering(rhs.compare(lhs));
}
+ StringBtreeDefaultGreater(std::greater<absl::Cord>) {} // NOLINT
+ absl::weak_ordering operator()(const absl::Cord &lhs,
+ const absl::Cord &rhs) const {
+ return compare_internal::compare_result_as_ordering(rhs.Compare(lhs));
+ }
+ absl::weak_ordering operator()(const absl::Cord &lhs,
+ absl::string_view rhs) const {
+ return compare_internal::compare_result_as_ordering(-lhs.Compare(rhs));
+ }
+ absl::weak_ordering operator()(absl::string_view lhs,
+ const absl::Cord &rhs) const {
+ return compare_internal::compare_result_as_ordering(rhs.Compare(lhs));
+ }
};
// A helper class to convert a boolean comparison into a three-way "compare-to"
// comparison that returns a negative value to indicate less-than, zero to
// indicate equality and a positive value to indicate greater-than. This helper
// class is specialized for less<std::string>, greater<std::string>,
-// less<string_view>, and greater<string_view>.
+// 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
@@ -145,6 +173,16 @@ struct key_compare_to_adapter<std::greater<absl::string_view>> {
using type = StringBtreeDefaultGreater;
};
+template <>
+struct key_compare_to_adapter<std::less<absl::Cord>> {
+ using type = StringBtreeDefaultLess;
+};
+
+template <>
+struct key_compare_to_adapter<std::greater<absl::Cord>> {
+ using type = StringBtreeDefaultGreater;
+};
+
template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
bool Multi, typename SlotPolicy>
struct common_params {
diff --git a/absl/container/internal/hash_function_defaults.h b/absl/container/internal/hash_function_defaults.h
index 401ddf4d..0683422a 100644
--- a/absl/container/internal/hash_function_defaults.h
+++ b/absl/container/internal/hash_function_defaults.h
@@ -53,6 +53,7 @@
#include "absl/base/config.h"
#include "absl/hash/hash.h"
+#include "absl/strings/cord.h"
#include "absl/strings/string_view.h"
namespace absl {
@@ -72,6 +73,9 @@ struct StringHash {
size_t operator()(absl::string_view v) const {
return absl::Hash<absl::string_view>{}(v);
}
+ size_t operator()(const absl::Cord& v) const {
+ return absl::Hash<absl::Cord>{}(v);
+ }
};
// Supports heterogeneous lookup for string-like elements.
@@ -82,6 +86,15 @@ struct StringHashEq {
bool operator()(absl::string_view lhs, absl::string_view rhs) const {
return lhs == rhs;
}
+ bool operator()(const absl::Cord& lhs, const absl::Cord& rhs) const {
+ return lhs == rhs;
+ }
+ bool operator()(const absl::Cord& lhs, absl::string_view rhs) const {
+ return lhs == rhs;
+ }
+ bool operator()(absl::string_view lhs, const absl::Cord& rhs) const {
+ return lhs == rhs;
+ }
};
};
@@ -89,6 +102,8 @@ template <>
struct HashEq<std::string> : StringHashEq {};
template <>
struct HashEq<absl::string_view> : StringHashEq {};
+template <>
+struct HashEq<absl::Cord> : StringHashEq {};
// Supports heterogeneous lookup for pointers and smart pointers.
template <class T>
diff --git a/absl/container/internal/hash_function_defaults_test.cc b/absl/container/internal/hash_function_defaults_test.cc
index 2eefc7e0..2d05a0b7 100644
--- a/absl/container/internal/hash_function_defaults_test.cc
+++ b/absl/container/internal/hash_function_defaults_test.cc
@@ -19,6 +19,9 @@
#include <utility>
#include "gtest/gtest.h"
+#include "absl/random/random.h"
+#include "absl/strings/cord.h"
+#include "absl/strings/cord_test_helpers.h"
#include "absl/strings/string_view.h"
namespace absl {
@@ -203,10 +206,91 @@ TYPED_TEST(HashPointer, Works) {
EXPECT_NE(hash(&dummy), hash(cuptr));
}
+TEST(EqCord, Works) {
+ hash_default_eq<absl::Cord> eq;
+ const absl::string_view a_string_view = "a";
+ const absl::Cord a_cord(a_string_view);
+ const absl::string_view b_string_view = "b";
+ const absl::Cord b_cord(b_string_view);
+
+ EXPECT_TRUE(eq(a_cord, a_cord));
+ EXPECT_TRUE(eq(a_cord, a_string_view));
+ EXPECT_TRUE(eq(a_string_view, a_cord));
+ EXPECT_FALSE(eq(a_cord, b_cord));
+ EXPECT_FALSE(eq(a_cord, b_string_view));
+ EXPECT_FALSE(eq(b_string_view, a_cord));
+}
+
+TEST(HashCord, Works) {
+ hash_default_hash<absl::Cord> hash;
+ const absl::string_view a_string_view = "a";
+ const absl::Cord a_cord(a_string_view);
+ const absl::string_view b_string_view = "b";
+ const absl::Cord b_cord(b_string_view);
+
+ EXPECT_EQ(hash(a_cord), hash(a_cord));
+ EXPECT_EQ(hash(b_cord), hash(b_cord));
+ EXPECT_EQ(hash(a_string_view), hash(a_cord));
+ EXPECT_EQ(hash(b_string_view), hash(b_cord));
+ EXPECT_EQ(hash(absl::Cord("")), hash(""));
+ EXPECT_EQ(hash(absl::Cord()), hash(absl::string_view()));
+
+ EXPECT_NE(hash(a_cord), hash(b_cord));
+ EXPECT_NE(hash(a_cord), hash(b_string_view));
+ EXPECT_NE(hash(a_string_view), hash(b_cord));
+ EXPECT_NE(hash(a_string_view), hash(b_string_view));
+}
+
+void NoOpReleaser(absl::string_view data, void* arg) {}
+
+TEST(HashCord, FragmentedCordWorks) {
+ hash_default_hash<absl::Cord> hash;
+ absl::Cord c = absl::MakeFragmentedCord({"a", "b", "c"});
+ EXPECT_FALSE(c.TryFlat().has_value());
+ EXPECT_EQ(hash(c), hash("abc"));
+}
+
+TEST(HashCord, FragmentedLongCordWorks) {
+ hash_default_hash<absl::Cord> hash;
+ // Crete some large strings which do not fit on the stack.
+ std::string a(65536, 'a');
+ std::string b(65536, 'b');
+ absl::Cord c = absl::MakeFragmentedCord({a, b});
+ EXPECT_FALSE(c.TryFlat().has_value());
+ EXPECT_EQ(hash(c), hash(a + b));
+}
+
+TEST(HashCord, RandomCord) {
+ hash_default_hash<absl::Cord> hash;
+ auto bitgen = absl::BitGen();
+ for (int i = 0; i < 1000; ++i) {
+ const int number_of_segments = absl::Uniform(bitgen, 0, 10);
+ std::vector<std::string> pieces;
+ for (size_t s = 0; s < number_of_segments; ++s) {
+ std::string str;
+ str.resize(absl::Uniform(bitgen, 0, 4096));
+ // MSVC needed the explicit return type in the lambda.
+ std::generate(str.begin(), str.end(), [&]() -> char {
+ return static_cast<char>(absl::Uniform<unsigned char>(bitgen));
+ });
+ pieces.push_back(str);
+ }
+ absl::Cord c = absl::MakeFragmentedCord(pieces);
+ EXPECT_EQ(hash(c), hash(std::string(c)));
+ }
+}
+
// Cartesian product of (std::string, absl::string_view)
-// with (std::string, absl::string_view, const char*).
+// with (std::string, absl::string_view, const char*, absl::Cord).
using StringTypesCartesianProduct = Types<
// clang-format off
+ std::pair<absl::Cord, std::string>,
+ std::pair<absl::Cord, absl::string_view>,
+ std::pair<absl::Cord, absl::Cord>,
+ std::pair<absl::Cord, const char*>,
+
+ std::pair<std::string, absl::Cord>,
+ std::pair<absl::string_view, absl::Cord>,
std::pair<absl::string_view, std::string>,
std::pair<absl::string_view, absl::string_view>,
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc
index 56447251..886524f1 100644
--- a/absl/container/internal/hashtablez_sampler.cc
+++ b/absl/container/internal/hashtablez_sampler.cc
@@ -226,7 +226,7 @@ void RecordInsertSlow(HashtablezInfo* info, size_t hash,
// SwissTables probe in groups of 16, so scale this to count items probes and
// not offset from desired.
size_t probe_length = distance_from_desired;
-#if SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
probe_length /= 16;
#else
probe_length /= 8;
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h
index 34d5e572..8aaffc35 100644
--- a/absl/container/internal/hashtablez_sampler.h
+++ b/absl/container/internal/hashtablez_sampler.h
@@ -98,7 +98,7 @@ struct HashtablezInfo {
};
inline void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length) {
-#if SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
total_probe_length /= 16;
#else
total_probe_length /= 8;
diff --git a/absl/container/internal/hashtablez_sampler_test.cc b/absl/container/internal/hashtablez_sampler_test.cc
index 36f5ccdd..b4c4ff92 100644
--- a/absl/container/internal/hashtablez_sampler_test.cc
+++ b/absl/container/internal/hashtablez_sampler_test.cc
@@ -29,7 +29,7 @@
#include "absl/time/clock.h"
#include "absl/time/time.h"
-#if SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
constexpr int kProbeLength = 16;
#else
constexpr int kProbeLength = 8;
diff --git a/absl/container/internal/have_sse.h b/absl/container/internal/have_sse.h
index 43414418..e75e1a16 100644
--- a/absl/container/internal/have_sse.h
+++ b/absl/container/internal/have_sse.h
@@ -16,33 +16,34 @@
#ifndef ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
#define ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
-#ifndef SWISSTABLE_HAVE_SSE2
+#ifndef ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
#if defined(__SSE2__) || \
(defined(_MSC_VER) && \
(defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2)))
-#define SWISSTABLE_HAVE_SSE2 1
+#define ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2 1
#else
-#define SWISSTABLE_HAVE_SSE2 0
+#define ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2 0
#endif
#endif
-#ifndef SWISSTABLE_HAVE_SSSE3
+#ifndef ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3
#ifdef __SSSE3__
-#define SWISSTABLE_HAVE_SSSE3 1
+#define ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3 1
#else
-#define SWISSTABLE_HAVE_SSSE3 0
+#define ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3 0
#endif
#endif
-#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3 && \
+ !ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
#error "Bad configuration!"
#endif
-#if SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
#include <emmintrin.h>
#endif
-#if SWISSTABLE_HAVE_SSSE3
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3
#include <tmmintrin.h>
#endif
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index ca7be8d8..fb47f62f 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -312,7 +312,7 @@ inline bool IsFull(ctrl_t c) { return c >= 0; }
inline bool IsDeleted(ctrl_t c) { return c == kDeleted; }
inline bool IsEmptyOrDeleted(ctrl_t c) { return c < kSentinel; }
-#if SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
// https://github.com/abseil/abseil-cpp/issues/209
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87853
@@ -346,7 +346,7 @@ struct GroupSse2Impl {
// Returns a bitmask representing the positions of empty slots.
BitMask<uint32_t, kWidth> MatchEmpty() const {
-#if SWISSTABLE_HAVE_SSSE3
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3
// This only works because kEmpty is -128.
return BitMask<uint32_t, kWidth>(
_mm_movemask_epi8(_mm_sign_epi8(ctrl, ctrl)));
@@ -372,7 +372,7 @@ struct GroupSse2Impl {
void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {
auto msbs = _mm_set1_epi8(static_cast<char>(-128));
auto x126 = _mm_set1_epi8(126);
-#if SWISSTABLE_HAVE_SSSE3
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSSE3
auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs);
#else
auto zero = _mm_setzero_si128();
@@ -384,7 +384,7 @@ struct GroupSse2Impl {
__m128i ctrl;
};
-#endif // SWISSTABLE_HAVE_SSE2
+#endif // ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
struct GroupPortableImpl {
static constexpr size_t kWidth = 8;
@@ -438,7 +438,7 @@ struct GroupPortableImpl {
uint64_t ctrl;
};
-#if SWISSTABLE_HAVE_SSE2
+#if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
using Group = GroupSse2Impl;
#else
using Group = GroupPortableImpl;
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel
index ffe8c294..59eac784 100644
--- a/absl/hash/BUILD.bazel
+++ b/absl/hash/BUILD.bazel
@@ -43,6 +43,7 @@ cc_library(
"//absl/meta:type_traits",
"//absl/numeric:int128",
"//absl/strings",
+ "//absl/strings:cord",
"//absl/types:optional",
"//absl/types:variant",
"//absl/utility",
@@ -76,6 +77,7 @@ cc_test(
"//absl/container:flat_hash_set",
"//absl/meta:type_traits",
"//absl/numeric:int128",
+ "//absl/strings:cord_test_helpers",
"@com_google_googletest//:gtest_main",
],
)
diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt
index febc551f..4e555147 100644
--- a/absl/hash/CMakeLists.txt
+++ b/absl/hash/CMakeLists.txt
@@ -25,6 +25,7 @@ absl_cc_library(
COPTS
${ABSL_DEFAULT_COPTS}
DEPS
+ absl::cord
absl::core_headers
absl::endian
absl::fixed_array
@@ -62,6 +63,7 @@ absl_cc_test(
COPTS
${ABSL_TEST_COPTS}
DEPS
+ absl::cord_test_helpers
absl::hash
absl::hash_testing
absl::core_headers
diff --git a/absl/hash/hash.h b/absl/hash/hash.h
index 23a65ea8..3dbeab69 100644
--- a/absl/hash/hash.h
+++ b/absl/hash/hash.h
@@ -98,6 +98,7 @@ ABSL_NAMESPACE_BEGIN
// * std::tuple<Ts...>, if all the Ts... are hashable
// * std::unique_ptr and std::shared_ptr
// * All string-like types including:
+// * absl::Cord
// * std::string
// * std::string_view (as well as any instance of std::basic_string that
// uses char and std::char_traits)
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index f02a537a..e55e0ca9 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -42,6 +42,7 @@
#include "absl/hash/internal/spy_hash_state.h"
#include "absl/meta/type_traits.h"
#include "absl/numeric/int128.h"
+#include "absl/strings/cord_test_helpers.h"
namespace {
@@ -269,6 +270,22 @@ struct WrapInTuple {
}
};
+absl::Cord FlatCord(absl::string_view sv) {
+ absl::Cord c(sv);
+ c.Flatten();
+ return c;
+}
+
+absl::Cord FragmentedCord(absl::string_view sv) {
+ if (sv.size() < 2) {
+ return absl::Cord(sv);
+ }
+ size_t halfway = sv.size() / 2;
+ std::vector<absl::string_view> parts = {sv.substr(0, halfway),
+ sv.substr(halfway)};
+ return absl::MakeFragmentedCord(parts);
+}
+
TEST(HashValueTest, Strings) {
EXPECT_TRUE((is_hashable<std::string>::value));
@@ -277,23 +294,27 @@ TEST(HashValueTest, Strings) {
const std::string large = std::string(2048, 'x'); // multiple of chunk size
const std::string huge = std::string(5000, 'a'); // not a multiple
- EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
- std::string(), absl::string_view(),
- std::string(""), absl::string_view(""),
- std::string(small), absl::string_view(small),
- std::string(dup), absl::string_view(dup),
- std::string(large), absl::string_view(large),
- std::string(huge), absl::string_view(huge))));
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( //
+ std::string(), absl::string_view(), absl::Cord(), //
+ std::string(""), absl::string_view(""), absl::Cord(""), //
+ std::string(small), absl::string_view(small), absl::Cord(small), //
+ std::string(dup), absl::string_view(dup), absl::Cord(dup), //
+ std::string(large), absl::string_view(large), absl::Cord(large), //
+ std::string(huge), absl::string_view(huge), FlatCord(huge), //
+ FragmentedCord(huge))));
// Also check that nested types maintain the same hash.
const WrapInTuple t{};
- EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
- t(std::string()), t(absl::string_view()),
- t(std::string("")), t(absl::string_view("")),
- t(std::string(small)), t(absl::string_view(small)),
- t(std::string(dup)), t(absl::string_view(dup)),
- t(std::string(large)), t(absl::string_view(large)),
- t(std::string(huge)), t(absl::string_view(huge)))));
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( //
+ t(std::string()), t(absl::string_view()), t(absl::Cord()), //
+ t(std::string("")), t(absl::string_view("")), t(absl::Cord("")), //
+ t(std::string(small)), t(absl::string_view(small)), //
+ t(absl::Cord(small)), //
+ t(std::string(dup)), t(absl::string_view(dup)), t(absl::Cord(dup)), //
+ t(std::string(large)), t(absl::string_view(large)), //
+ t(absl::Cord(large)), //
+ t(std::string(huge)), t(absl::string_view(huge)), //
+ t(FlatCord(huge)), t(FragmentedCord(huge)))));
// Make sure that hashing a `const char*` does not use its std::string-value.
EXPECT_NE(SpyHash(static_cast<const char*>("ABC")),
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index 1cc2c5e5..025d287f 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -43,6 +43,7 @@
#include "absl/container/fixed_array.h"
#include "absl/meta/type_traits.h"
#include "absl/numeric/int128.h"
+#include "absl/strings/cord.h"
#include "absl/strings/string_view.h"
#include "absl/types/optional.h"
#include "absl/types/variant.h"
@@ -413,6 +414,7 @@ H AbslHashValue(H hash_state, const std::shared_ptr<T>& ptr) {
// All the string-like types supported here provide the same hash expansion for
// the same character sequence. These types are:
//
+// - `absl::Cord`
// - `std::string` (and std::basic_string<char, std::char_traits<char>, A> for
// any allocator A)
// - `absl::string_view` and `std::string_view`
@@ -441,6 +443,25 @@ H AbslHashValue(
str.size());
}
+template <typename H>
+H HashFragmentedCord(H hash_state, const absl::Cord& c) {
+ PiecewiseCombiner combiner;
+ c.ForEachChunk([&combiner, &hash_state](absl::string_view chunk) {
+ hash_state =
+ combiner.add_buffer(std::move(hash_state), chunk.data(), chunk.size());
+ });
+ return H::combine(combiner.finalize(std::move(hash_state)), c.size());
+}
+
+template <typename H>
+H AbslHashValue(H hash_state, const absl::Cord& c) {
+ absl::optional<absl::string_view> maybe_flat = c.TryFlat();
+ if (maybe_flat.has_value()) {
+ return H::combine(std::move(hash_state), *maybe_flat);
+ }
+ return hash_internal::HashFragmentedCord(std::move(hash_state), c);
+}
+
// -----------------------------------------------------------------------------
// AbslHashValue for Sequence Containers
// -----------------------------------------------------------------------------
diff --git a/absl/numeric/int128.h b/absl/numeric/int128.h
index 636e3a5b..0dd814a8 100644
--- a/absl/numeric/int128.h
+++ b/absl/numeric/int128.h
@@ -792,28 +792,21 @@ inline bool operator!=(uint128 lhs, uint128 rhs) {
}
inline bool operator<(uint128 lhs, uint128 rhs) {
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ return static_cast<unsigned __int128>(lhs) <
+ static_cast<unsigned __int128>(rhs);
+#else
return (Uint128High64(lhs) == Uint128High64(rhs))
? (Uint128Low64(lhs) < Uint128Low64(rhs))
: (Uint128High64(lhs) < Uint128High64(rhs));
+#endif
}
-inline bool operator>(uint128 lhs, uint128 rhs) {
- return (Uint128High64(lhs) == Uint128High64(rhs))
- ? (Uint128Low64(lhs) > Uint128Low64(rhs))
- : (Uint128High64(lhs) > Uint128High64(rhs));
-}
+inline bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; }
-inline bool operator<=(uint128 lhs, uint128 rhs) {
- return (Uint128High64(lhs) == Uint128High64(rhs))
- ? (Uint128Low64(lhs) <= Uint128Low64(rhs))
- : (Uint128High64(lhs) <= Uint128High64(rhs));
-}
+inline bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); }
-inline bool operator>=(uint128 lhs, uint128 rhs) {
- return (Uint128High64(lhs) == Uint128High64(rhs))
- ? (Uint128Low64(lhs) >= Uint128Low64(rhs))
- : (Uint128High64(lhs) >= Uint128High64(rhs));
-}
+inline bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < rhs); }
// Unary operators.
@@ -870,6 +863,9 @@ inline uint128& uint128::operator^=(uint128 other) {
// Arithmetic operators.
inline uint128 operator<<(uint128 lhs, int amount) {
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ return static_cast<unsigned __int128>(lhs) << amount;
+#else
// uint64_t shifts of >= 64 are undefined, so we will need some
// special-casing.
if (amount < 64) {
@@ -881,9 +877,13 @@ inline uint128 operator<<(uint128 lhs, int amount) {
return lhs;
}
return MakeUint128(Uint128Low64(lhs) << (amount - 64), 0);
+#endif
}
inline uint128 operator>>(uint128 lhs, int amount) {
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ return static_cast<unsigned __int128>(lhs) >> amount;
+#else
// uint64_t shifts of >= 64 are undefined, so we will need some
// special-casing.
if (amount < 64) {
@@ -895,6 +895,7 @@ inline uint128 operator>>(uint128 lhs, int amount) {
return lhs;
}
return MakeUint128(0, Uint128High64(lhs) >> (amount - 64));
+#endif
}
inline uint128 operator+(uint128 lhs, uint128 rhs) {
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index 0757a9cb..668d722b 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -548,6 +548,7 @@ absl_cc_library(
absl::inlined_vector
absl::optional
absl::raw_logging_internal
+ absl::strings
absl::type_traits
PUBLIC
)