From 1de0166368e2ae67347f92099d6dca3ab3a4a496 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 3 Jan 2020 08:41:10 -0800 Subject: Export of internal Abseil changes -- 330051e00cd57ee516b4eaf656965656ffbcd0bc by Abseil Team : Fix indentation in comment. PiperOrigin-RevId: 287997504 -- 35fb1a893e708031ba4fc0db460875eb0d31820e by Abseil Team : Enable compile-time enforcement that absl::Substitute patterns to not contain unescaped $ symbols. absl::Substitute already considers unescaped $ symbols undefined behavior and crashes when it's passed them in debug builds. Some code isn't ever built in debug mode, though, and inadvertently used some unescaped $ symbols, which led to surprising results. This change will prevent that problem from happening in the future. PiperOrigin-RevId: 287906643 -- c5762833ebde6d7110bf68041a823b571c238e9e by Gennadiy Rozental : Move all the flag data into a single place instead of being split between handle and flag object. After this change CommandLineFlag will not hold any data anymore. And we also do not need to pass the CommandLineFlag around in Abseil Flag implementation to report flag name and location. PiperOrigin-RevId: 287899076 -- 8b5fb644f1e3d9267b7a75106fe9a72c886db786 by Derek Mauro : Upgrade CI testing to Bazel 2.0.0 and Clang 407ac2eb5f13 -fno-sanitize-blacklist is to workaround https://github.com/bazelbuild/bazel/issues/10510 PiperOrigin-RevId: 287875363 -- a20cc1d58895de2babc3748a6c79d1d6813734ef by Abseil Team : Make ABSL_RETIRED_FLAG behave consistently with ABSL_FLAG. Before the change: ABSL_RETIRED_FLAG does not compile when there are competing ctors in the type, even when ABSL_FLAG does. After the change: ABSL_RETIRED_FLAG compiles when ABSL_FLAG does. PiperOrigin-RevId: 286483183 -- 1cff7e67329d2be9e50bee1f2e76ef9ffd2edde5 by Abseil Team : Support C++20 erase_if API in unordered associative containers See [unord.set.erasure]: https://eel.is/c++draft/unord.set.erasure See [unord.map.erasure]: https://eel.is/c++draft/unord.map.erasure PiperOrigin-RevId: 286461140 GitOrigin-RevId: 330051e00cd57ee516b4eaf656965656ffbcd0bc Change-Id: I5513110b41c2af08a44da54612cff341ac5c6607 --- absl/container/flat_hash_map.h | 9 ++++++++ absl/container/flat_hash_map_test.cc | 38 ++++++++++++++++++++++++++++++++++ absl/container/flat_hash_set.h | 8 +++++++ absl/container/flat_hash_set_test.cc | 36 ++++++++++++++++++++++++++++++++ absl/container/internal/raw_hash_set.h | 11 ++++++++++ absl/container/node_hash_map.h | 9 ++++++++ absl/container/node_hash_map_test.cc | 38 ++++++++++++++++++++++++++++++++++ absl/container/node_hash_set.h | 8 +++++++ absl/container/node_hash_set_test.cc | 36 ++++++++++++++++++++++++++++++++ 9 files changed, 193 insertions(+) (limited to 'absl/container') diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index fb570cd495ee..fcb70d861f39 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h @@ -532,6 +532,15 @@ class flat_hash_map : public absl::container_internal::raw_hash_map< using Base::key_eq; }; +// erase_if(flat_hash_map<>, Pred) +// +// Erases all elements that satisfy the predicate `pred` from the container `c`. +template +void erase_if(flat_hash_map& c, Predicate pred) { + container_internal::EraseIf(pred, &c); +} + namespace container_internal { template diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc index dae8e00389bc..fd9c5604b1d6 100644 --- a/absl/container/flat_hash_map_test.cc +++ b/absl/container/flat_hash_map_test.cc @@ -30,6 +30,7 @@ namespace { using ::absl::container_internal::hash_internal::Enum; using ::absl::container_internal::hash_internal::EnumClass; using ::testing::_; +using ::testing::IsEmpty; using ::testing::Pair; using ::testing::UnorderedElementsAre; @@ -215,6 +216,43 @@ TEST(FlatHashMap, MergeExtractInsert) { EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 17), Pair(2, 9))); } +bool FirstIsEven(std::pair p) { return p.first % 2 == 0; } + +TEST(FlatHashMap, EraseIf) { + // Erase all elements. + { + flat_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, [](std::pair) { return true; }); + EXPECT_THAT(s, IsEmpty()); + } + // Erase no elements. + { + flat_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, [](std::pair) { return false; }); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3), + Pair(4, 4), Pair(5, 5))); + } + // Erase specific elements. + { + flat_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, + [](std::pair kvp) { return kvp.first % 2 == 1; }); + EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4))); + } + // Predicate is function reference. + { + flat_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, FirstIsEven); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); + } + // Predicate is function pointer. + { + flat_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, &FirstIsEven); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); + } +} + #if (defined(ABSL_USES_STD_ANY) || !defined(_LIBCPP_VERSION)) && \ !defined(__EMSCRIPTEN__) TEST(FlatHashMap, Any) { diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index 930107ea212d..94be6e3d13f1 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h @@ -439,6 +439,14 @@ class flat_hash_set using Base::key_eq; }; +// erase_if(flat_hash_set<>, Pred) +// +// Erases all elements that satisfy the predicate `pred` from the container `c`. +template +void erase_if(flat_hash_set& c, Predicate pred) { + container_internal::EraseIf(pred, &c); +} + namespace container_internal { template diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc index 6eacb1bb653c..40d7f85c5db0 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc @@ -31,6 +31,7 @@ namespace { using ::absl::container_internal::hash_internal::Enum; using ::absl::container_internal::hash_internal::EnumClass; +using ::testing::IsEmpty; using ::testing::Pointee; using ::testing::UnorderedElementsAre; using ::testing::UnorderedElementsAreArray; @@ -124,6 +125,41 @@ TEST(FlatHashSet, MergeExtractInsert) { EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23))); } +bool IsEven(int k) { return k % 2 == 0; } + +TEST(FlatHashSet, EraseIf) { + // Erase all elements. + { + flat_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, [](int) { return true; }); + EXPECT_THAT(s, IsEmpty()); + } + // Erase no elements. + { + flat_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, [](int) { return false; }); + EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5)); + } + // Erase specific elements. + { + flat_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, [](int k) { return k % 2 == 1; }); + EXPECT_THAT(s, UnorderedElementsAre(2, 4)); + } + // Predicate is function reference. + { + flat_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, IsEven); + EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5)); + } + // Predicate is function pointer. + { + flat_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, &IsEven); + EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5)); + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 4103e02ab0b0..b1c686edf28c 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -1801,6 +1801,17 @@ class raw_hash_set { settings_{0, hasher{}, key_equal{}, allocator_type{}}; }; +// Erases all elements that satisfy the predicate `pred` from the container `c`. +template +void EraseIf(Predicate pred, raw_hash_set* c) { + for (auto it = c->begin(), last = c->end(); it != last;) { + auto copy_it = it++; + if (pred(*copy_it)) { + c->erase(copy_it); + } + } +} + namespace hashtable_debug_internal { template struct HashtableDebugAccess> { diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index e8065a98a987..fccea1841c08 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h @@ -522,6 +522,15 @@ class node_hash_map void resize(typename Base::size_type hint) { this->rehash(hint); } }; +// erase_if(node_hash_map<>, Pred) +// +// Erases all elements that satisfy the predicate `pred` from the container `c`. +template +void erase_if(node_hash_map& c, Predicate pred) { + container_internal::EraseIf(pred, &c); +} + namespace container_internal { template diff --git a/absl/container/node_hash_map_test.cc b/absl/container/node_hash_map_test.cc index f923e91513a5..5d74b814b584 100644 --- a/absl/container/node_hash_map_test.cc +++ b/absl/container/node_hash_map_test.cc @@ -26,6 +26,7 @@ namespace container_internal { namespace { using ::testing::Field; +using ::testing::IsEmpty; using ::testing::Pair; using ::testing::UnorderedElementsAre; @@ -216,6 +217,43 @@ TEST(NodeHashMap, MergeExtractInsert) { EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23))); } +bool FirstIsEven(std::pair p) { return p.first % 2 == 0; } + +TEST(NodeHashMap, EraseIf) { + // Erase all elements. + { + node_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, [](std::pair) { return true; }); + EXPECT_THAT(s, IsEmpty()); + } + // Erase no elements. + { + node_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, [](std::pair) { return false; }); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3), + Pair(4, 4), Pair(5, 5))); + } + // Erase specific elements. + { + node_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, + [](std::pair kvp) { return kvp.first % 2 == 1; }); + EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4))); + } + // Predicate is function reference. + { + node_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, FirstIsEven); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); + } + // Predicate is function pointer. + { + node_hash_map s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, &FirstIsEven); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 43ada3f9df24..0e2dee54aa19 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h @@ -435,6 +435,14 @@ class node_hash_set void resize(typename Base::size_type hint) { this->rehash(hint); } }; +// erase_if(node_hash_set<>, Pred) +// +// Erases all elements that satisfy the predicate `pred` from the container `c`. +template +void erase_if(node_hash_set& c, Predicate pred) { + container_internal::EraseIf(pred, &c); +} + namespace container_internal { template diff --git a/absl/container/node_hash_set_test.cc b/absl/container/node_hash_set_test.cc index e1d544ff882e..7ddad2021d2f 100644 --- a/absl/container/node_hash_set_test.cc +++ b/absl/container/node_hash_set_test.cc @@ -25,6 +25,7 @@ namespace container_internal { namespace { using ::absl::container_internal::hash_internal::Enum; using ::absl::container_internal::hash_internal::EnumClass; +using ::testing::IsEmpty; using ::testing::Pointee; using ::testing::UnorderedElementsAre; @@ -101,6 +102,41 @@ TEST(NodeHashSet, MergeExtractInsert) { EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23))); } +bool IsEven(int k) { return k % 2 == 0; } + +TEST(NodeHashSet, EraseIf) { + // Erase all elements. + { + node_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, [](int) { return true; }); + EXPECT_THAT(s, IsEmpty()); + } + // Erase no elements. + { + node_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, [](int) { return false; }); + EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5)); + } + // Erase specific elements. + { + node_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, [](int k) { return k % 2 == 1; }); + EXPECT_THAT(s, UnorderedElementsAre(2, 4)); + } + // Predicate is function reference. + { + node_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, IsEven); + EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5)); + } + // Predicate is function pointer. + { + node_hash_set s = {1, 2, 3, 4, 5}; + erase_if(s, &IsEven); + EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5)); + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END -- cgit 1.4.1