about summary refs log tree commit diff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel4
-rw-r--r--absl/container/CMakeLists.txt12
-rw-r--r--absl/container/fixed_array.h7
-rw-r--r--absl/container/fixed_array_test.cc2
-rw-r--r--absl/container/flat_hash_map.h14
-rw-r--r--absl/container/flat_hash_map_test.cc2
-rw-r--r--absl/container/flat_hash_set.h6
-rw-r--r--absl/container/inlined_vector.h6
-rw-r--r--absl/container/inlined_vector_test.cc2
-rw-r--r--absl/container/internal/hash_function_defaults.h5
-rw-r--r--absl/container/internal/hash_policy_traits.h2
-rw-r--r--absl/container/internal/layout.h2
-rw-r--r--absl/container/internal/raw_hash_set.h19
-rw-r--r--absl/container/internal/raw_hash_set_test.cc30
-rw-r--r--absl/container/node_hash_map.h12
-rw-r--r--absl/container/node_hash_set.h4
16 files changed, 76 insertions, 53 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 265c5ec9c418..f2210e3c1979 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -67,6 +67,7 @@ cc_test(
     deps = [
         ":fixed_array",
         "//absl/base:exception_testing",
+        "//absl/hash:hash_testing",
         "//absl/memory",
         "@com_google_googletest//:gtest_main",
     ],
@@ -79,6 +80,7 @@ cc_test(
     deps = [
         ":fixed_array",
         "//absl/base:exception_testing",
+        "//absl/hash:hash_testing",
         "//absl/memory",
         "@com_google_googletest//:gtest_main",
     ],
@@ -130,6 +132,7 @@ cc_test(
         "//absl/base",
         "//absl/base:core_headers",
         "//absl/base:exception_testing",
+        "//absl/hash:hash_testing",
         "//absl/memory",
         "//absl/strings",
         "@com_google_googletest//:gtest_main",
@@ -146,6 +149,7 @@ cc_test(
         "//absl/base",
         "//absl/base:core_headers",
         "//absl/base:exception_testing",
+        "//absl/hash:hash_testing",
         "//absl/memory",
         "//absl/strings",
         "@com_google_googletest//:gtest_main",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 087eddfd3967..5de75f5936d1 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -48,9 +48,11 @@ list(APPEND CONTAINER_INTERNAL_HEADERS
 )
 
 
-absl_header_library(
+absl_library(
   TARGET
     absl_container
+  SOURCES
+    "internal/raw_hash_set.cc"
   EXPORT_NAME
     container
 )
@@ -164,3 +166,11 @@ absl_test(
 )
 
 
+absl_test(
+  TARGET
+    raw_hash_set_test
+  SOURCES
+    "internal/raw_hash_set_test.cc"
+  PUBLIC_LIBRARIES
+    absl::base absl::hash absl_throw_delegate test_instance_tracker_lib
+)
diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h
index d716380a5e27..fe67dceef669 100644
--- a/absl/container/fixed_array.h
+++ b/absl/container/fixed_array.h
@@ -358,6 +358,13 @@ class FixedArray {
   friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) {
     return !(lhs < rhs);
   }
+
+  template <typename H>
+  friend H AbslHashValue(H h, const FixedArray& v) {
+    return H::combine(H::combine_contiguous(std::move(h), v.data(), v.size()),
+                      v.size());
+  }
+
  private:
   // StorageElement
   //
diff --git a/absl/container/fixed_array_test.cc b/absl/container/fixed_array_test.cc
index b07ebcb6d9ca..205ff41fe114 100644
--- a/absl/container/fixed_array_test.cc
+++ b/absl/container/fixed_array_test.cc
@@ -27,6 +27,7 @@
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include "absl/base/internal/exception_testing.h"
+#include "absl/hash/hash_testing.h"
 #include "absl/memory/memory.h"
 
 using ::testing::ElementsAreArray;
@@ -867,4 +868,5 @@ TEST(FixedArrayTest, AddressSanitizerAnnotations4) {
   EXPECT_DEATH(raw[21] = ThreeInts(), "container-overflow");
 }
 #endif  // ADDRESS_SANITIZER
+
 }  // namespace
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h
index 13fbfba51f48..e5570d100441 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -88,7 +88,7 @@ struct FlatHashMapPolicy;
 //     {{"a", "huey"}, {"b", "dewey"}, {"c", "louie"}};
 //
 //  // Insert a new element into the flat hash map
-//  ducks.insert({"d", "donald"}};
+//  ducks.insert({"d", "donald"});
 //
 //  // Force a rehash of the flat hash map
 //  ducks.rehash(0);
@@ -206,7 +206,7 @@ class flat_hash_map : public absl::container_internal::raw_hash_map<
   //   insertion) and a bool denoting whether the insertion took place.
   //
   // std::pair<iterator,bool> insert(T&& value):
-  // std::pair<iterator,bool> insert(init_type&& value ):
+  // std::pair<iterator,bool> insert(init_type&& value):
   //
   //   Inserts a moveable value into the `flat_hash_map`. Returns a pair
   //   consisting of an iterator to the inserted element (or to the element that
@@ -215,14 +215,14 @@ class flat_hash_map : public absl::container_internal::raw_hash_map<
   //
   // iterator insert(const_iterator hint, const init_type& value):
   // iterator insert(const_iterator hint, T&& value):
-  // iterator insert(const_iterator hint, init_type&& value );
+  // iterator insert(const_iterator hint, init_type&& value);
   //
   //   Inserts a value, using the position of `hint` as a non-binding suggestion
   //   for where to begin the insertion search. Returns an iterator to the
   //   inserted element, or to the existing element that prevented the
   //   insertion.
   //
-  // void insert(InputIterator first, InputIterator last ):
+  // void insert(InputIterator first, InputIterator last):
   //
   //   Inserts a range of values [`first`, `last`).
   //
@@ -230,7 +230,7 @@ class flat_hash_map : public absl::container_internal::raw_hash_map<
   //   multiple keys compare equivalently, for `flat_hash_map` we guarantee the
   //   first match is inserted.
   //
-  // void insert(std::initializer_list<init_type> ilist ):
+  // void insert(std::initializer_list<init_type> ilist):
   //
   //   Inserts the elements within the initializer list `ilist`.
   //
@@ -423,12 +423,12 @@ class flat_hash_map : public absl::container_internal::raw_hash_map<
   // iterators are invalidated. Otherwise iterators are not affected and
   // references are not invalidated. Overloads are listed below.
   //
-  // T& operator[](const Key& key ):
+  // T& operator[](const Key& key):
   //
   //   Inserts an init_type object constructed in-place if the element with the
   //   given key does not exist.
   //
-  // T& operator[]( Key&& key ):
+  // T& operator[](Key&& key):
   //
   //   Inserts an init_type object constructed in-place provided that an element
   //   with the given key does not exist.
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc
index 10a781ffd6c7..2c6f2515f865 100644
--- a/absl/container/flat_hash_map_test.cc
+++ b/absl/container/flat_hash_map_test.cc
@@ -94,7 +94,7 @@ TEST(FlatHashMap, IteratesMsan) {
   }
 }
 
-// Demonstration of the "Lazy Key" pattern.  This uses heterogenous insert to
+// Demonstration of the "Lazy Key" pattern.  This uses heterogeneous insert to
 // avoid creating expensive key elements when the item is already present in the
 // map.
 struct LazyInt {
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index ccd03a4abb6d..04fa73f15511 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -84,7 +84,7 @@ struct FlatHashSetPolicy;
 //     {"huey", "dewey", "louie"};
 //
 //  // Insert a new element into the flat hash set
-//  ducks.insert("donald"};
+//  ducks.insert("donald");
 //
 //  // Force a rehash of the flat hash set
 //  ducks.rehash(0);
@@ -213,7 +213,7 @@ class flat_hash_set
   //   inserted element, or to the existing element that prevented the
   //   insertion.
   //
-  // void insert(InputIterator first, InputIterator last ):
+  // void insert(InputIterator first, InputIterator last):
   //
   //   Inserts a range of values [`first`, `last`).
   //
@@ -221,7 +221,7 @@ class flat_hash_set
   //   multiple keys compare equivalently, for `flat_hash_set` we guarantee the
   //   first match is inserted.
   //
-  // void insert(std::initializer_list<T> ilist ):
+  // void insert(std::initializer_list<T> ilist):
   //
   //   Inserts the elements within the initializer list `ilist`.
   //
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 0c0ffb0b1366..12756bb820cf 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -620,6 +620,12 @@ class InlinedVector {
   // Returns the allocator of this inlined vector.
   allocator_type get_allocator() const { return allocator(); }
 
+  template <typename H>
+  friend H AbslHashValue(H h, const InlinedVector& v) {
+    return H::combine(H::combine_contiguous(std::move(h), v.data(), v.size()),
+                      v.size());
+  }
+
  private:
   static_assert(N > 0, "inlined vector with nonpositive size");
 
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc
index 196a1bed976c..08dcd3ef66fb 100644
--- a/absl/container/inlined_vector_test.cc
+++ b/absl/container/inlined_vector_test.cc
@@ -31,6 +31,7 @@
 #include "absl/base/internal/raw_logging.h"
 #include "absl/base/macros.h"
 #include "absl/container/internal/test_instance_tracker.h"
+#include "absl/hash/hash_testing.h"
 #include "absl/memory/memory.h"
 #include "absl/strings/str_cat.h"
 
@@ -1788,4 +1789,5 @@ TEST(AllocatorSupportTest, SizeAllocConstructor) {
     EXPECT_THAT(v, AllOf(SizeIs(len), Each(0)));
   }
 }
+
 }  // anonymous namespace
diff --git a/absl/container/internal/hash_function_defaults.h b/absl/container/internal/hash_function_defaults.h
index dd6cd8f537fd..1f0d794d9663 100644
--- a/absl/container/internal/hash_function_defaults.h
+++ b/absl/container/internal/hash_function_defaults.h
@@ -83,11 +83,6 @@ struct StringHashEq {
     }
   };
 };
-
-#if defined(HAS_GLOBAL_STRING)
-template <>
-struct HashEq<std::string> : StringHashEq {};
-#endif
 template <>
 struct HashEq<std::string> : StringHashEq {};
 template <>
diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h
index 029e47e175c9..ace50a6ca42a 100644
--- a/absl/container/internal/hash_policy_traits.h
+++ b/absl/container/internal/hash_policy_traits.h
@@ -84,7 +84,7 @@ struct hash_policy_traits {
   }
 
   // Transfers the `old_slot` to `new_slot`. Any memory allocated by the
-  // allocator inside `old_slot` to `new_slot` can be transfered.
+  // allocator inside `old_slot` to `new_slot` can be transferred.
   //
   // OPTIONAL: defaults to:
   //
diff --git a/absl/container/internal/layout.h b/absl/container/internal/layout.h
index 0c239fe876c5..676c7d67ee68 100644
--- a/absl/container/internal/layout.h
+++ b/absl/container/internal/layout.h
@@ -456,7 +456,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>,
   //
   //   // int[3], 4 bytes of padding, double[4].
   //   Layout<int, double> x(3, 4);
-  //   unsigned char* p = unsigned char[x.AllocSize()];
+  //   unsigned char* p = new unsigned char[x.AllocSize()];
   //   int* ints = x.Pointer<0>(p);
   //   double* doubles = x.Pointer<1>(p);
   //
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 0c0e5906d206..40bdb71b5203 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -662,7 +662,7 @@ class raw_hash_set {
       allocator_type>::template rebind_traits<value_type>::const_pointer;
 
   // Alias used for heterogeneous lookup functions.
-  // `key_arg<K>` evaluates to `K` when the functors are tranparent and to
+  // `key_arg<K>` evaluates to `K` when the functors are transparent and to
   // `key_type` otherwise. It permits template argument deduction on `K` for the
   // transparent case.
   template <class K>
@@ -1330,8 +1330,7 @@ class raw_hash_set {
   void rehash(size_t n) {
     if (n == 0 && capacity_ == 0) return;
     if (n == 0 && size_ == 0) return destroy_slots();
-    auto m = NormalizeCapacity(std::max(
-        n, static_cast<size_t>(std::ceil(size() / kMaxLoadFactor))));
+    auto m = NormalizeCapacity(std::max(n, NumSlotsFast(size())));
     // n == 0 unconditionally rehashes as per the standard.
     if (n == 0 || m > capacity_) {
       resize(m);
@@ -1339,7 +1338,7 @@ class raw_hash_set {
   }
 
   void reserve(size_t n) {
-    rehash(static_cast<size_t>(std::ceil(n / kMaxLoadFactor)));
+    rehash(NumSlotsFast(n));
   }
 
   // Extension API: support for heterogeneous keys.
@@ -1518,6 +1517,13 @@ class raw_hash_set {
     slot_type&& slot;
   };
 
+  // Computes std::ceil(n / kMaxLoadFactor). Faster than calling std::ceil.
+  static inline size_t NumSlotsFast(size_t n) {
+    return static_cast<size_t>(
+        (n * kMaxLoadFactorDenominator + (kMaxLoadFactorNumerator - 1)) /
+        kMaxLoadFactorNumerator);
+  }
+
   // "erases" the object from the container, except that it doesn't actually
   // destroy the object. It only updates all the metadata of the class.
   // This can be used in conjunction with Policy::transfer to move the object to
@@ -1825,7 +1831,10 @@ class raw_hash_set {
   }
 
   // On average each group has 2 empty slot (for the vectorized case).
-  static constexpr float kMaxLoadFactor = 14.0 / 16.0;
+  static constexpr int64_t kMaxLoadFactorNumerator = 14;
+  static constexpr int64_t kMaxLoadFactorDenominator = 16;
+  static constexpr float kMaxLoadFactor =
+      1.0 * kMaxLoadFactorNumerator / kMaxLoadFactorDenominator;
 
   // TODO(alkis): Investigate removing some of these fields:
   // - ctrl/slots can be derived from each other
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index f59a19b4a62d..f48578eb1495 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -687,7 +687,7 @@ TEST(Table, RehashWithNoResize) {
   Modulo1000HashTable t;
   // Adding the same length (and the same hash) strings
   // to have at least kMinFullGroups groups
-  // with Group::kWidth collisions. Then feel upto MaxDensitySize;
+  // with Group::kWidth collisions. Then fill up to MaxDensitySize;
   const size_t kMinFullGroups = 7;
   std::vector<int> keys;
   for (size_t i = 0; i < MaxDensitySize(Group::kWidth * kMinFullGroups); ++i) {
@@ -1029,7 +1029,6 @@ ExpectedStats XorSeedExpectedStats() {
           {{0.95, 0.1}},
           {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};
       }
-      break;
     case 16:
       if (kRandomizesInserts) {
         return {0.1,
@@ -1042,10 +1041,8 @@ ExpectedStats XorSeedExpectedStats() {
                 {{0.95, 0.05}},
                 {{0.95, 0}, {0.99, 1}, {0.999, 4}, {0.9999, 10}}};
       }
-      break;
-    default:
-      ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   }
+  ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   return {};
 }
 TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
@@ -1125,7 +1122,6 @@ ExpectedStats LinearTransformExpectedStats() {
                 {{0.95, 0.3}},
                 {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}};
       }
-      break;
     case 16:
       if (kRandomizesInserts) {
         return {0.1,
@@ -1138,10 +1134,8 @@ ExpectedStats LinearTransformExpectedStats() {
                 {{0.95, 0.1}},
                 {{0.95, 0}, {0.99, 1}, {0.999, 6}, {0.9999, 10}}};
       }
-      break;
-    default:
-      ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   }
+  ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   return {};
 }
 TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
@@ -1834,18 +1828,15 @@ std::vector<std::pair<double, double>> StringTablePefectRatios() {
       } else {
         return {{0.995, 0.01}, {0.97, 0.01}, {0.89, 0.02}};
       }
-      break;
     case 16:
       if (kRandomizesInserts) {
         return {{0.973, 0.01}, {0.965, 0.01}, {0.92, 0.02}};
       } else {
         return {{0.995, 0.005}, {0.99, 0.005}, {0.94, 0.01}};
       }
-      break;
-    default:
-      // Ignore anything else.
-      return {};
   }
+  ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
+  return {};
 }
 
 // This is almost a change detector, but it allows us to know how we are
@@ -1884,18 +1875,15 @@ std::vector<std::pair<double, double>> IntTablePefectRatios() {
       } else {
         return {{0.99, 0.01}, {0.99, 0.01}, {0.95, 0.02}};
       }
-      break;
     case 16:
       if (kRandomizesInserts) {
         return {{0.98, 0.02}, {0.978, 0.02}, {0.96, 0.02}};
       } else {
         return {{0.998, 0.003}, {0.995, 0.01}, {0.975, 0.02}};
       }
-      break;
-    default:
-      // Ignore anything else.
-      return {};
   }
+  ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
+  return {};
 }
 
 // This is almost a change detector, but it allows us to know how we are
@@ -1916,7 +1904,7 @@ TEST(Table, EffectiveLoadFactorInts) {
 }
 
 // Confirm that we assert if we try to erase() end().
-TEST(Table, EraseOfEndAsserts) {
+TEST(TableDeathTest, EraseOfEndAsserts) {
   // Use an assert with side-effects to figure out if they are actually enabled.
   bool assert_enabled = false;
   assert([&]() {
@@ -1928,7 +1916,7 @@ TEST(Table, EraseOfEndAsserts) {
   IntTable t;
   // Extra simple "regexp" as regexp support is highly varied across platforms.
   constexpr char kDeathMsg[] = "it != end";
-  EXPECT_DEATH(t.erase(t.end()), kDeathMsg);
+  EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), kDeathMsg);
 }
 
 #ifdef ADDRESS_SANITIZER
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h
index 3c7de1e8885f..6369ec3ad643 100644
--- a/absl/container/node_hash_map.h
+++ b/absl/container/node_hash_map.h
@@ -201,7 +201,7 @@ class node_hash_map
   //   insertion) and a `bool` denoting whether the insertion took place.
   //
   // std::pair<iterator,bool> insert(T&& value):
-  // std::pair<iterator,bool> insert(init_type&& value ):
+  // std::pair<iterator,bool> insert(init_type&& value):
   //
   //   Inserts a moveable value into the `node_hash_map`. Returns a `std::pair`
   //   consisting of an iterator to the inserted element (or to the element that
@@ -210,14 +210,14 @@ class node_hash_map
   //
   // iterator insert(const_iterator hint, const init_type& value):
   // iterator insert(const_iterator hint, T&& value):
-  // iterator insert(const_iterator hint, init_type&& value );
+  // iterator insert(const_iterator hint, init_type&& value);
   //
   //   Inserts a value, using the position of `hint` as a non-binding suggestion
   //   for where to begin the insertion search. Returns an iterator to the
   //   inserted element, or to the existing element that prevented the
   //   insertion.
   //
-  // void insert(InputIterator first, InputIterator last ):
+  // void insert(InputIterator first, InputIterator last):
   //
   //   Inserts a range of values [`first`, `last`).
   //
@@ -225,7 +225,7 @@ class node_hash_map
   //   multiple keys compare equivalently, for `node_hash_map` we guarantee the
   //   first match is inserted.
   //
-  // void insert(std::initializer_list<init_type> ilist ):
+  // void insert(std::initializer_list<init_type> ilist):
   //
   //   Inserts the elements within the initializer list `ilist`.
   //
@@ -413,12 +413,12 @@ class node_hash_map
   // all iterators are invalidated. Otherwise iterators are not affected and
   // references are not invalidated. Overloads are listed below.
   //
-  // T& operator[](const Key& key ):
+  // T& operator[](const Key& key):
   //
   //   Inserts an init_type object constructed in-place if the element with the
   //   given key does not exist.
   //
-  // T& operator[]( Key&& key ):
+  // T& operator[](Key&& key):
   //
   //   Inserts an init_type object constructed in-place provided that an element
   //   with the given key does not exist.
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h
index 927a454cffbe..90d4ce0c1631 100644
--- a/absl/container/node_hash_set.h
+++ b/absl/container/node_hash_set.h
@@ -207,7 +207,7 @@ class node_hash_set
   //   inserted element, or to the existing element that prevented the
   //   insertion.
   //
-  // void insert(InputIterator first, InputIterator last ):
+  // void insert(InputIterator first, InputIterator last):
   //
   //   Inserts a range of values [`first`, `last`).
   //
@@ -215,7 +215,7 @@ class node_hash_set
   //   multiple keys compare equivalently, for `node_hash_set` we guarantee the
   //   first match is inserted.
   //
-  // void insert(std::initializer_list<T> ilist ):
+  // void insert(std::initializer_list<T> ilist):
   //
   //   Inserts the elements within the initializer list `ilist`.
   //
generated by cgit-pink 1.4.1 (git 2.44.2) at 2024-11-29T02ยท01+0000