about summary refs log tree commit diff
path: root/absl/hash
diff options
context:
space:
mode:
authorAbseil Team <absl-team@google.com>2020-03-09T19·34-0700
committerDerek Mauro <dmauro@google.com>2020-03-09T20·10-0400
commitd936052d32a5b7ca08b0199a6724724aea432309 (patch)
treef14866c5460c73ba3ba3812941a0426ad51496cd /absl/hash
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/hash')
-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
5 files changed, 61 insertions, 14 deletions
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel
index ffe8c294a0bc..59eac78484ac 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 febc551fcedb..4e55514743b0 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 23a65ea8687e..3dbeab6977af 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 f02a537ae8fc..e55e0ca9545f 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 1cc2c5e5ae48..025d287f39c9 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
 // -----------------------------------------------------------------------------