summaryrefslogtreecommitdiff
path: root/absl/container/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal')
-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
5 files changed, 25 insertions, 33 deletions
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/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h
index 029e47e1..ace50a6c 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 0c239fe8..676c7d67 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 0c0e5906..40bdb71b 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 f59a19b4..f48578eb 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-23 09:06:33 +0000