summaryrefslogtreecommitdiff
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 265c5ec9..f2210e3c 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 455c6f6c..9e406902 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 d716380a..fe67dcee 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 b07ebcb6..205ff41f 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 13fbfba5..9e7f6821 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 ccd03a4a..98aead1a 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 0c0ffb0b..12756bb8 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 196a1bed..08dcd3ef 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 dd6cd8f5..1f0d794d 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 0c0e5906..70da90f7 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 f59a19b4..cd33a3ac 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 3c7de1e8..6369ec3a 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 927a454c..90d4ce0c 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 v1.2.3 (git 2.39.1) at 2024-07-04 01:54:31 +0000