summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Vitaly Goldshteyn <goldvitaly@google.com>2024-06-20 13:43:52 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2024-06-20 13:45:02 -0700
commit10ac811f7c3720761c0fa0cd2b3fe92116b89420 (patch)
tree045af5b9491c5ebddf445a5921adaacc99d8d183 /absl
parent93763764d7554882db31364d822cb9fb924ca594 (diff)
Create `absl::container_internal::c_for_each_fast` for SwissTable.
This function is aimed to achieve faster iteration through the entire hash table. It is not ready to be used by the public and stays in `container_internal` namespace. Differences with `absl::c_for_each`: 1. No guarantees on order of iteration. Although for the hash table it is partially not guaranteed already. But we do not even guarantee that it is the same order as in the for loop range. De facto, the order is the same at the moment. 2. No mutating reentrance is allowed. Most notably erasing from the hash_table is not allowed. Based on microbenchmarks, there are following conclusions: 1. c_for_each_fast is clearly faster on big tables with 20-60% speedup. 2. Microbenchmarks show regression on a full small table without any empty slots. We should avoid recommending that for small tables. 3. It seems reasonable to use `c_for_each_fast` in places, where `skip_empty_or_deleted` has significant GCU usage. `skip_empty_or_deleted` usage signals that there are "gaps" between elements, so `c_for_each_fast` should be an improvement. PiperOrigin-RevId: 645142512 Change-Id: I279886b8c8b2545504c2bf7e037d27b2545e044d
Diffstat (limited to 'absl')
-rw-r--r--absl/container/BUILD.bazel12
-rw-r--r--absl/container/CMakeLists.txt11
-rw-r--r--absl/container/flat_hash_map.h33
-rw-r--r--absl/container/flat_hash_map_test.cc53
-rw-r--r--absl/container/flat_hash_set.h28
-rw-r--r--absl/container/flat_hash_set_test.cc33
-rw-r--r--absl/container/internal/raw_hash_set.h27
-rw-r--r--absl/container/internal/raw_hash_set_test.cc52
-rw-r--r--absl/container/node_hash_map.h33
-rw-r--r--absl/container/node_hash_map_test.cc65
-rw-r--r--absl/container/node_hash_set.h28
-rw-r--r--absl/container/node_hash_set_test.cc46
12 files changed, 417 insertions, 4 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 38fec260..b00c30fd 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -252,7 +252,7 @@ cc_library(
":raw_hash_map",
"//absl/algorithm:container",
"//absl/base:core_headers",
- "//absl/memory",
+ "//absl/meta:type_traits",
],
)
@@ -292,6 +292,7 @@ cc_library(
"//absl/algorithm:container",
"//absl/base:core_headers",
"//absl/memory",
+ "//absl/meta:type_traits",
],
)
@@ -332,6 +333,7 @@ cc_library(
"//absl/algorithm:container",
"//absl/base:core_headers",
"//absl/memory",
+ "//absl/meta:type_traits",
],
)
@@ -342,13 +344,14 @@ cc_test(
linkopts = ABSL_DEFAULT_LINKOPTS,
tags = ["no_test_loonix"],
deps = [
- ":hash_generator_testing",
+ ":hash_policy_testing",
":node_hash_map",
":tracked",
":unordered_map_constructor_test",
":unordered_map_lookup_test",
":unordered_map_members_test",
":unordered_map_modifiers_test",
+ "//absl/base:config",
"@com_google_googletest//:gtest",
"@com_google_googletest//:gtest_main",
],
@@ -367,6 +370,7 @@ cc_library(
"//absl/algorithm:container",
"//absl/base:core_headers",
"//absl/memory",
+ "//absl/meta:type_traits",
],
)
@@ -377,11 +381,15 @@ cc_test(
linkopts = ABSL_DEFAULT_LINKOPTS,
tags = ["no_test_loonix"],
deps = [
+ ":hash_generator_testing",
+ ":hash_policy_testing",
":node_hash_set",
":unordered_set_constructor_test",
":unordered_set_lookup_test",
":unordered_set_members_test",
":unordered_set_modifiers_test",
+ "//absl/base:config",
+ "//absl/memory",
"@com_google_googletest//:gtest",
"@com_google_googletest//:gtest_main",
],
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index dd994f0b..25831d5f 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -292,7 +292,7 @@ absl_cc_library(
absl::hash_container_defaults
absl::raw_hash_map
absl::algorithm_container
- absl::memory
+ absl::type_traits
PUBLIC
)
@@ -333,6 +333,7 @@ absl_cc_library(
absl::algorithm_container
absl::core_headers
absl::memory
+ absl::type_traits
PUBLIC
)
@@ -375,6 +376,7 @@ absl_cc_library(
absl::raw_hash_map
absl::algorithm_container
absl::memory
+ absl::type_traits
PUBLIC
)
@@ -386,7 +388,8 @@ absl_cc_test(
COPTS
${ABSL_TEST_COPTS}
DEPS
- absl::hash_generator_testing
+ absl::config
+ absl::hash_policy_testing
absl::node_hash_map
absl::tracked
absl::unordered_map_constructor_test
@@ -411,6 +414,7 @@ absl_cc_library(
absl::raw_hash_set
absl::algorithm_container
absl::memory
+ absl::type_traits
PUBLIC
)
@@ -424,7 +428,10 @@ absl_cc_test(
"-DUNORDERED_SET_CXX17"
DEPS
absl::hash_generator_testing
+ absl::hash_policy_testing
+ absl::memory
absl::node_hash_set
+ absl::type_traits
absl::unordered_set_constructor_test
absl::unordered_set_lookup_test
absl::unordered_set_members_test
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h
index 3eae404f..ebd9ed67 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -43,6 +43,7 @@
#include "absl/container/hash_container_defaults.h"
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export
+#include "absl/meta/type_traits.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -575,6 +576,38 @@ typename flat_hash_map<K, V, H, E, A>::size_type erase_if(
namespace container_internal {
+// c_for_each_fast(flat_hash_map<>, Function)
+//
+// Container-based version of the <algorithm> `std::for_each()` function to
+// apply a function to a container's elements.
+// There is no guarantees on the order of the function calls.
+// Erasure and/or insertion of elements in the function is not allowed.
+template <typename K, typename V, typename H, typename E, typename A,
+ typename Function>
+decay_t<Function> c_for_each_fast(const flat_hash_map<K, V, H, E, A>& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename K, typename V, typename H, typename E, typename A,
+ typename Function>
+decay_t<Function> c_for_each_fast(flat_hash_map<K, V, H, E, A>& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename K, typename V, typename H, typename E, typename A,
+ typename Function>
+decay_t<Function> c_for_each_fast(flat_hash_map<K, V, H, E, A>&& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+
+} // namespace container_internal
+
+namespace container_internal {
+
template <class K, class V>
struct FlatHashMapPolicy {
using slot_policy = container_internal::map_slot_policy<K, V>;
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc
index eaa86925..08915e20 100644
--- a/absl/container/flat_hash_map_test.cc
+++ b/absl/container/flat_hash_map_test.cc
@@ -45,6 +45,7 @@ using ::testing::_;
using ::testing::IsEmpty;
using ::testing::Pair;
using ::testing::UnorderedElementsAre;
+using ::testing::UnorderedElementsAreArray;
// Check that absl::flat_hash_map works in a global constructor.
struct BeforeMain {
@@ -307,6 +308,58 @@ TEST(FlatHashMap, EraseIf) {
}
}
+TEST(FlatHashMap, CForEach) {
+ flat_hash_map<int, int> m;
+ std::vector<std::pair<int, int>> expected;
+ for (int i = 0; i < 100; ++i) {
+ {
+ SCOPED_TRACE("mutable object iteration");
+ std::vector<std::pair<int, int>> v;
+ absl::container_internal::c_for_each_fast(
+ m, [&v](std::pair<const int, int>& p) { v.push_back(p); });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const object iteration");
+ std::vector<std::pair<int, int>> v;
+ const flat_hash_map<int, int>& cm = m;
+ absl::container_internal::c_for_each_fast(
+ cm, [&v](const std::pair<const int, int>& p) { v.push_back(p); });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const object iteration");
+ std::vector<std::pair<int, int>> v;
+ absl::container_internal::c_for_each_fast(
+ flat_hash_map<int, int>(m),
+ [&v](std::pair<const int, int>& p) { v.push_back(p); });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ m[i] = i;
+ expected.emplace_back(i, i);
+ }
+}
+
+TEST(FlatHashMap, CForEachMutate) {
+ flat_hash_map<int, int> s;
+ std::vector<std::pair<int, int>> expected;
+ for (int i = 0; i < 100; ++i) {
+ std::vector<std::pair<int, int>> v;
+ absl::container_internal::c_for_each_fast(
+ s, [&v](std::pair<const int, int>& p) {
+ v.push_back(p);
+ p.second++;
+ });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ for (auto& p : expected) {
+ p.second++;
+ }
+ EXPECT_THAT(s, UnorderedElementsAreArray(expected));
+ s[i] = i;
+ expected.emplace_back(i, i);
+ }
+}
+
// This test requires std::launder for mutable key access in node handles.
#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
TEST(FlatHashMap, NodeHandleMutableKeyAccess) {
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index e284a7df..a3e36e05 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -44,6 +44,7 @@
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export
#include "absl/memory/memory.h"
+#include "absl/meta/type_traits.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -479,6 +480,33 @@ typename flat_hash_set<T, H, E, A>::size_type erase_if(
namespace container_internal {
+// c_for_each_fast(flat_hash_set<>, Function)
+//
+// Container-based version of the <algorithm> `std::for_each()` function to
+// apply a function to a container's elements.
+// There is no guarantees on the order of the function calls.
+// Erasure and/or insertion of elements in the function is not allowed.
+template <typename T, typename H, typename E, typename A, typename Function>
+decay_t<Function> c_for_each_fast(const flat_hash_set<T, H, E, A>& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename T, typename H, typename E, typename A, typename Function>
+decay_t<Function> c_for_each_fast(flat_hash_set<T, H, E, A>& c, Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename T, typename H, typename E, typename A, typename Function>
+decay_t<Function> c_for_each_fast(flat_hash_set<T, H, E, A>&& c, Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+
+} // namespace container_internal
+
+namespace container_internal {
+
template <class T>
struct FlatHashSetPolicy {
using slot_type = T;
diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc
index b425bc50..0dd43269 100644
--- a/absl/container/flat_hash_set_test.cc
+++ b/absl/container/flat_hash_set_test.cc
@@ -181,6 +181,39 @@ TEST(FlatHashSet, EraseIf) {
}
}
+TEST(FlatHashSet, CForEach) {
+ using ValueType = std::pair<int, int>;
+ flat_hash_set<ValueType> s;
+ std::vector<ValueType> expected;
+ for (int i = 0; i < 100; ++i) {
+ {
+ SCOPED_TRACE("mutable object iteration");
+ std::vector<ValueType> v;
+ absl::container_internal::c_for_each_fast(
+ s, [&v](const ValueType& p) { v.push_back(p); });
+ ASSERT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const object iteration");
+ std::vector<ValueType> v;
+ const flat_hash_set<ValueType>& cs = s;
+ absl::container_internal::c_for_each_fast(
+ cs, [&v](const ValueType& p) { v.push_back(p); });
+ ASSERT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("temporary object iteration");
+ std::vector<ValueType> v;
+ absl::container_internal::c_for_each_fast(
+ flat_hash_set<ValueType>(s),
+ [&v](const ValueType& p) { v.push_back(p); });
+ ASSERT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ s.emplace(i, i);
+ expected.emplace_back(i, i);
+ }
+}
+
class PoisonSoo {
int64_t data_;
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index c63b60e3..a722f522 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -4075,6 +4075,23 @@ struct HashtableFreeFunctionsAccess {
});
return num_deleted;
}
+
+ template <class Callback, typename Set>
+ static void ForEach(Callback& cb, Set* c) {
+ if (c->empty()) {
+ return;
+ }
+ if (c->is_soo()) {
+ cb(*c->soo_iterator());
+ return;
+ }
+ using ElementTypeWithConstness = decltype(*c->begin());
+ IterateOverFullSlots</*kAllowRemoveReentrance=*/false>(
+ c->common(), c->slot_array(), [&cb](const ctrl_t*, auto* slot) {
+ ElementTypeWithConstness& element = Set::PolicyTraits::element(slot);
+ cb(element);
+ });
+ }
};
// Erases all elements that satisfy the predicate `pred` from the container `c`.
@@ -4084,6 +4101,16 @@ typename raw_hash_set<P, H, E, A>::size_type EraseIf(
return HashtableFreeFunctionsAccess::EraseIf(pred, c);
}
+// Calls `cb` for all elements in the container `c`.
+template <typename P, typename H, typename E, typename A, typename Callback>
+void ForEach(Callback& cb, raw_hash_set<P, H, E, A>* c) {
+ return HashtableFreeFunctionsAccess::ForEach(cb, c);
+}
+template <typename P, typename H, typename E, typename A, typename Callback>
+void ForEach(Callback& cb, const raw_hash_set<P, H, E, A>* c) {
+ return HashtableFreeFunctionsAccess::ForEach(cb, c);
+}
+
namespace hashtable_debug_internal {
template <typename Set>
struct HashtableDebugAccess<Set, absl::void_t<typename Set::raw_hash_set>> {
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 2a6ee656..673d78a6 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -3121,6 +3121,58 @@ TYPED_TEST(SooTest, EraseIfPartial) {
}
}
+TYPED_TEST(SooTest, ForEach) {
+ TypeParam t;
+ std::vector<int64_t> expected;
+ for (int size = 0; size < 100; ++size) {
+ SCOPED_TRACE(size);
+ {
+ SCOPED_TRACE("mutable iteration");
+ std::vector<int64_t> actual;
+ auto f = [&](auto& x) { actual.push_back(static_cast<int64_t>(x)); };
+ absl::container_internal::ForEach(f, &t);
+ ASSERT_THAT(actual, testing::UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const iteration");
+ std::vector<int64_t> actual;
+ auto f = [&](auto& x) {
+ static_assert(
+ std::is_const<std::remove_reference_t<decltype(x)>>::value,
+ "no mutable values should be passed to const ForEach");
+ actual.push_back(static_cast<int64_t>(x));
+ };
+ const auto& ct = t;
+ absl::container_internal::ForEach(f, &ct);
+ ASSERT_THAT(actual, testing::UnorderedElementsAreArray(expected));
+ }
+ t.insert(size);
+ expected.push_back(size);
+ }
+}
+
+TEST(Table, ForEachMutate) {
+ StringTable t;
+ using ValueType = StringTable::value_type;
+ std::vector<ValueType> expected;
+ for (int size = 0; size < 100; ++size) {
+ SCOPED_TRACE(size);
+ std::vector<ValueType> actual;
+ auto f = [&](ValueType& x) {
+ actual.push_back(x);
+ x.second += "a";
+ };
+ absl::container_internal::ForEach(f, &t);
+ ASSERT_THAT(actual, testing::UnorderedElementsAreArray(expected));
+ for (ValueType& v : expected) {
+ v.second += "a";
+ }
+ ASSERT_THAT(t, testing::UnorderedElementsAreArray(expected));
+ t.emplace(std::to_string(size), std::to_string(size));
+ expected.emplace_back(std::to_string(size), std::to_string(size));
+ }
+}
+
TEST(Table, EraseBeginEndResetsReservedGrowth) {
bool frozen = false;
BadHashFreezableIntTable t{FreezableAlloc<int64_t>(&frozen)};
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h
index 7b74b4b3..5615e496 100644
--- a/absl/container/node_hash_map.h
+++ b/absl/container/node_hash_map.h
@@ -50,6 +50,7 @@
#include "absl/container/internal/node_slot_policy.h"
#include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export
#include "absl/memory/memory.h"
+#include "absl/meta/type_traits.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -559,6 +560,38 @@ typename node_hash_map<K, V, H, E, A>::size_type erase_if(
namespace container_internal {
+// c_for_each_fast(node_hash_map<>, Function)
+//
+// Container-based version of the <algorithm> `std::for_each()` function to
+// apply a function to a container's elements.
+// There is no guarantees on the order of the function calls.
+// Erasure and/or insertion of elements in the function is not allowed.
+template <typename K, typename V, typename H, typename E, typename A,
+ typename Function>
+decay_t<Function> c_for_each_fast(const node_hash_map<K, V, H, E, A>& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename K, typename V, typename H, typename E, typename A,
+ typename Function>
+decay_t<Function> c_for_each_fast(node_hash_map<K, V, H, E, A>& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename K, typename V, typename H, typename E, typename A,
+ typename Function>
+decay_t<Function> c_for_each_fast(node_hash_map<K, V, H, E, A>&& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+
+} // namespace container_internal
+
+namespace container_internal {
+
template <class Key, class Value>
class NodeHashMapPolicy
: public absl::container_internal::node_slot_policy<
diff --git a/absl/container/node_hash_map_test.cc b/absl/container/node_hash_map_test.cc
index 9bcf470c..2657828e 100644
--- a/absl/container/node_hash_map_test.cc
+++ b/absl/container/node_hash_map_test.cc
@@ -14,6 +14,18 @@
#include "absl/container/node_hash_map.h"
+#include <cstddef>
+#include <new> // NOLINT: used for __cpp_lib_launder
+#include <string>
+#include <tuple>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/config.h"
+#include "absl/container/internal/hash_policy_testing.h"
#include "absl/container/internal/tracked.h"
#include "absl/container/internal/unordered_map_constructor_test.h"
#include "absl/container/internal/unordered_map_lookup_test.h"
@@ -29,6 +41,7 @@ using ::testing::Field;
using ::testing::IsEmpty;
using ::testing::Pair;
using ::testing::UnorderedElementsAre;
+using ::testing::UnorderedElementsAreArray;
using MapTypes = ::testing::Types<
absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual,
@@ -257,6 +270,58 @@ TEST(NodeHashMap, EraseIf) {
}
}
+TEST(NodeHashMap, CForEach) {
+ node_hash_map<int, int> m;
+ std::vector<std::pair<int, int>> expected;
+ for (int i = 0; i < 100; ++i) {
+ {
+ SCOPED_TRACE("mutable object iteration");
+ std::vector<std::pair<int, int>> v;
+ absl::container_internal::c_for_each_fast(
+ m, [&v](std::pair<const int, int>& p) { v.push_back(p); });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const object iteration");
+ std::vector<std::pair<int, int>> v;
+ const node_hash_map<int, int>& cm = m;
+ absl::container_internal::c_for_each_fast(
+ cm, [&v](const std::pair<const int, int>& p) { v.push_back(p); });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const object iteration");
+ std::vector<std::pair<int, int>> v;
+ absl::container_internal::c_for_each_fast(
+ node_hash_map<int, int>(m),
+ [&v](std::pair<const int, int>& p) { v.push_back(p); });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ m[i] = i;
+ expected.emplace_back(i, i);
+ }
+}
+
+TEST(NodeHashMap, CForEachMutate) {
+ node_hash_map<int, int> s;
+ std::vector<std::pair<int, int>> expected;
+ for (int i = 0; i < 100; ++i) {
+ std::vector<std::pair<int, int>> v;
+ absl::container_internal::c_for_each_fast(
+ s, [&v](std::pair<const int, int>& p) {
+ v.push_back(p);
+ p.second++;
+ });
+ EXPECT_THAT(v, UnorderedElementsAreArray(expected));
+ for (auto& p : expected) {
+ p.second++;
+ }
+ EXPECT_THAT(s, UnorderedElementsAreArray(expected));
+ s[i] = i;
+ expected.emplace_back(i, i);
+ }
+}
+
// This test requires std::launder for mutable key access in node handles.
#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
TEST(NodeHashMap, NodeHandleMutableKeyAccess) {
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h
index 7228d192..53435ae6 100644
--- a/absl/container/node_hash_set.h
+++ b/absl/container/node_hash_set.h
@@ -48,6 +48,7 @@
#include "absl/container/internal/node_slot_policy.h"
#include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export
#include "absl/memory/memory.h"
+#include "absl/meta/type_traits.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -468,6 +469,33 @@ typename node_hash_set<T, H, E, A>::size_type erase_if(
namespace container_internal {
+// c_for_each_fast(node_hash_set<>, Function)
+//
+// Container-based version of the <algorithm> `std::for_each()` function to
+// apply a function to a container's elements.
+// There is no guarantees on the order of the function calls.
+// Erasure and/or insertion of elements in the function is not allowed.
+template <typename T, typename H, typename E, typename A, typename Function>
+decay_t<Function> c_for_each_fast(const node_hash_set<T, H, E, A>& c,
+ Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename T, typename H, typename E, typename A, typename Function>
+decay_t<Function> c_for_each_fast(node_hash_set<T, H, E, A>& c, Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+template <typename T, typename H, typename E, typename A, typename Function>
+decay_t<Function> c_for_each_fast(node_hash_set<T, H, E, A>&& c, Function&& f) {
+ container_internal::ForEach(f, &c);
+ return f;
+}
+
+} // namespace container_internal
+
+namespace container_internal {
+
template <class T>
struct NodeHashSetPolicy
: absl::container_internal::node_slot_policy<T&, NodeHashSetPolicy<T>> {
diff --git a/absl/container/node_hash_set_test.cc b/absl/container/node_hash_set_test.cc
index 98a8dbdd..e616ac1e 100644
--- a/absl/container/node_hash_set_test.cc
+++ b/absl/container/node_hash_set_test.cc
@@ -14,10 +14,22 @@
#include "absl/container/node_hash_set.h"
+#include <cstddef>
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/config.h"
+#include "absl/container/internal/hash_generator_testing.h"
+#include "absl/container/internal/hash_policy_testing.h"
#include "absl/container/internal/unordered_set_constructor_test.h"
#include "absl/container/internal/unordered_set_lookup_test.h"
#include "absl/container/internal/unordered_set_members_test.h"
#include "absl/container/internal/unordered_set_modifiers_test.h"
+#include "absl/memory/memory.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -28,6 +40,7 @@ using ::absl::container_internal::hash_internal::EnumClass;
using ::testing::IsEmpty;
using ::testing::Pointee;
using ::testing::UnorderedElementsAre;
+using ::testing::UnorderedElementsAreArray;
using SetTypes = ::testing::Types<
node_hash_set<int, StatefulTestingHash, StatefulTestingEqual, Alloc<int>>,
@@ -137,6 +150,39 @@ TEST(NodeHashSet, EraseIf) {
}
}
+TEST(NodeHashSet, CForEach) {
+ using ValueType = std::pair<int, int>;
+ node_hash_set<ValueType> s;
+ std::vector<ValueType> expected;
+ for (int i = 0; i < 100; ++i) {
+ {
+ SCOPED_TRACE("mutable object iteration");
+ std::vector<ValueType> v;
+ absl::container_internal::c_for_each_fast(
+ s, [&v](const ValueType& p) { v.push_back(p); });
+ ASSERT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("const object iteration");
+ std::vector<ValueType> v;
+ const node_hash_set<ValueType>& cs = s;
+ absl::container_internal::c_for_each_fast(
+ cs, [&v](const ValueType& p) { v.push_back(p); });
+ ASSERT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ {
+ SCOPED_TRACE("temporary object iteration");
+ std::vector<ValueType> v;
+ absl::container_internal::c_for_each_fast(
+ node_hash_set<ValueType>(s),
+ [&v](const ValueType& p) { v.push_back(p); });
+ ASSERT_THAT(v, UnorderedElementsAreArray(expected));
+ }
+ s.emplace(i, i);
+ expected.emplace_back(i, i);
+ }
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END