about summary refs log tree commit diff
path: root/absl/container/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal')
-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
8 files changed, 157 insertions, 19 deletions
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 2a5c7314ccae..301c3656e5ab 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 401ddf4d83c6..0683422ad89b 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 2eefc7e0defb..2d05a0b72a0d 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 564472517844..886524f18070 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 34d5e5723c0f..8aaffc35a24f 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 36f5ccdd02a7..b4c4ff92e75a 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 43414418dba0..e75e1a16d327 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 ca7be8d86819..fb47f62f4e7d 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;
generated by cgit-pink 1.4.1 (git 2.44.2) at 2024-11-05T21ยท17+0000