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.txt1
-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.h12
-rw-r--r--absl/container/flat_hash_set.h4
-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/raw_hash_set.h17
-rw-r--r--absl/container/internal/raw_hash_set_test.cc4
-rw-r--r--absl/container/node_hash_map.h12
-rw-r--r--absl/container/node_hash_set.h4
13 files changed, 53 insertions, 27 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 455c6f6cf625..9e406902b058 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -47,6 +47,7 @@ list(APPEND CONTAINER_INTERNAL_HEADERS
   "internal/unordered_set_modifiers_test.h"
 )
 
+
 absl_library(
   TARGET
     absl_container
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..9e7f682180e5 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -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_set.h b/absl/container/flat_hash_set.h
index ccd03a4abb6d..98aead1a8ae2 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -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/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 0c0e5906d206..70da90f79a4f 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -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..cd33a3acb917 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1916,7 +1916,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 +1928,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-26T10ยท32+0000