[tint][utils] Add FilteredIterator
An iterator that skip over elements where the predicate function returns false.
Change-Id: Ic00cf6950891125809ed811fa406c57b3bf674bf
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/182121
Reviewed-by: dan sinclair <dsinclair@chromium.org>
Reviewed-by: James Price <jrprice@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/utils/containers/BUILD.bazel b/src/tint/utils/containers/BUILD.bazel
index 36431b1..07523ce 100644
--- a/src/tint/utils/containers/BUILD.bazel
+++ b/src/tint/utils/containers/BUILD.bazel
@@ -45,6 +45,7 @@
"bitset.h",
"const_propagating_ptr.h",
"enum_set.h",
+ "filtered_iterator.h",
"hashmap.h",
"hashmap_base.h",
"hashset.h",
@@ -75,6 +76,7 @@
srcs = [
"bitset_test.cc",
"enum_set_test.cc",
+ "filtered_iterator_test.cc",
"hashmap_test.cc",
"hashset_test.cc",
"map_test.cc",
diff --git a/src/tint/utils/containers/BUILD.cmake b/src/tint/utils/containers/BUILD.cmake
index b5bbaae..c00bd5e 100644
--- a/src/tint/utils/containers/BUILD.cmake
+++ b/src/tint/utils/containers/BUILD.cmake
@@ -43,6 +43,7 @@
utils/containers/const_propagating_ptr.h
utils/containers/containers.cc
utils/containers/enum_set.h
+ utils/containers/filtered_iterator.h
utils/containers/hashmap.h
utils/containers/hashmap_base.h
utils/containers/hashset.h
@@ -73,6 +74,7 @@
tint_add_target(tint_utils_containers_test test
utils/containers/bitset_test.cc
utils/containers/enum_set_test.cc
+ utils/containers/filtered_iterator_test.cc
utils/containers/hashmap_test.cc
utils/containers/hashset_test.cc
utils/containers/map_test.cc
diff --git a/src/tint/utils/containers/BUILD.gn b/src/tint/utils/containers/BUILD.gn
index be16640..c1cbce3 100644
--- a/src/tint/utils/containers/BUILD.gn
+++ b/src/tint/utils/containers/BUILD.gn
@@ -48,6 +48,7 @@
"const_propagating_ptr.h",
"containers.cc",
"enum_set.h",
+ "filtered_iterator.h",
"hashmap.h",
"hashmap_base.h",
"hashset.h",
@@ -75,6 +76,7 @@
sources = [
"bitset_test.cc",
"enum_set_test.cc",
+ "filtered_iterator_test.cc",
"hashmap_test.cc",
"hashset_test.cc",
"map_test.cc",
diff --git a/src/tint/utils/containers/filtered_iterator.h b/src/tint/utils/containers/filtered_iterator.h
new file mode 100644
index 0000000..b120643
--- /dev/null
+++ b/src/tint/utils/containers/filtered_iterator.h
@@ -0,0 +1,135 @@
+// Copyright 2024 The Dawn & Tint Authors
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this
+// list of conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef SRC_TINT_UTILS_CONTAINERS_FILTERED_ITERATOR_H_
+#define SRC_TINT_UTILS_CONTAINERS_FILTERED_ITERATOR_H_
+
+#include <utility>
+
+namespace tint {
+
+/// FilteredIterator is an iterator that skip over elements where the predicate function returns
+/// false.
+/// @tparam PREDICATE the filter predicate function
+/// @tparam ITERATOR the inner iterator type
+template <typename PREDICATE, typename ITERATOR>
+class FilteredIterator {
+ public:
+ /// @param current the current iterator.
+ /// @param end the end iterator.
+ FilteredIterator(ITERATOR current, ITERATOR end) : current_(current), end_(end) {
+ // Skip to first element that passes the predicate
+ while (current_ != end && !PREDICATE{}(*current_)) {
+ ++current_;
+ }
+ }
+
+ /// Copy constructor
+ FilteredIterator(const FilteredIterator&) = default;
+
+ /// Copy assignment operator
+ FilteredIterator& operator=(const FilteredIterator&) = default;
+
+ /// Move constructor
+ FilteredIterator(FilteredIterator&&) = default;
+
+ /// Move assignment operator
+ FilteredIterator& operator=(FilteredIterator&&) = default;
+
+ /// Increments the iterator until PREDICATE returns true, or the end is reached.
+ /// @return this FilteredIterator
+ FilteredIterator& operator++() {
+ ++current_;
+ while (current_ != end_ && !PREDICATE{}(*current_)) {
+ ++current_;
+ }
+ return *this;
+ }
+
+ /// @returns the element at the current iterator
+ auto operator*() const { return *current_; }
+
+ /// @returns the element at the current iterator
+ auto operator->() const { return current_.operator->(); }
+
+ /// Equality operator
+ /// @returns true if this iterator is equal to @p other
+ bool operator==(const FilteredIterator& other) const { return current_ == other.current_; }
+
+ /// Inequality operator
+ /// @returns true if this iterator is not equal to @p other
+ bool operator!=(const FilteredIterator& other) const { return current_ != other.current_; }
+
+ private:
+ /// The current iterator.
+ ITERATOR current_;
+ /// The end iterator.
+ ITERATOR end_;
+};
+
+/// FilteredIterable is a wrapper around an object with begin() / end() methods, that returns
+/// iterators that skip over elements where the predicate function returns false.
+/// @tparam PREDICATE the filter predicate function
+/// @tparam ITERABLE the inner iterable object type
+template <typename PREDICATE, typename ITERABLE>
+struct FilteredIterable {
+ /// The iterator type
+ using iterator = typename std::decay_t<ITERABLE>::iterator;
+ /// The const iterator type
+ using const_iterator = typename std::decay_t<ITERABLE>::const_iterator;
+
+ /// The wrapped iterable object.
+ ITERABLE iterable;
+
+ /// @return the filtered start iterator
+ FilteredIterator<PREDICATE, iterator> begin() { return {iterable.begin(), iterable.end()}; }
+
+ /// @return the filtered end iterator
+ FilteredIterator<PREDICATE, iterator> end() { return {iterable.end(), iterable.end()}; }
+
+ /// @return the filtered const start iterator
+ FilteredIterator<PREDICATE, const_iterator> begin() const {
+ return {iterable.begin(), iterable.end()};
+ }
+
+ /// @return the filtered const end iterator
+ FilteredIterator<PREDICATE, const_iterator> end() const {
+ return {iterable.end(), iterable.end()};
+ }
+};
+
+/// @returns a FilteredIterable from the filter function `PREDICATE`, wrapping @p iterable
+/// @tparam PREDICATE the filter predicate function
+/// @tparam ITERABLE the inner iterable object type
+template <typename PREDICATE, typename ITERABLE>
+FilteredIterable<PREDICATE, ITERABLE&> Filter(ITERABLE& iterable) {
+ return {iterable};
+}
+
+} // namespace tint
+
+#endif // SRC_TINT_UTILS_CONTAINERS_FILTERED_ITERATOR_H_
diff --git a/src/tint/utils/containers/filtered_iterator_test.cc b/src/tint/utils/containers/filtered_iterator_test.cc
new file mode 100644
index 0000000..7ec6299
--- /dev/null
+++ b/src/tint/utils/containers/filtered_iterator_test.cc
@@ -0,0 +1,62 @@
+// Copyright 2024 The Dawn & Tint Authors
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this
+// list of conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "src/tint/utils/containers/filtered_iterator.h"
+
+#include <vector>
+
+#include "gmock/gmock.h"
+
+namespace tint {
+namespace {
+
+struct IsEven {
+ bool operator()(int i) const { return (i & 1) == 0; }
+};
+
+struct IsOdd {
+ bool operator()(int i) const { return (i & 1) != 0; }
+};
+
+TEST(FilteredIterableTest, Vector) {
+ std::vector<int> vec{1, 2, 3, 4, 5};
+ std::vector<int> even;
+ std::vector<int> odd;
+
+ for (auto v : Filter<IsEven>(vec)) {
+ even.emplace_back(v);
+ }
+ for (auto v : Filter<IsOdd>(vec)) {
+ odd.emplace_back(v);
+ }
+
+ ASSERT_THAT(even, testing::ElementsAre(2, 4));
+ ASSERT_THAT(odd, testing::ElementsAre(1, 3, 5));
+}
+
+} // namespace
+} // namespace tint
diff --git a/src/tint/utils/memory/block_allocator.h b/src/tint/utils/memory/block_allocator.h
index 65c4507..f8a59dc 100644
--- a/src/tint/utils/memory/block_allocator.h
+++ b/src/tint/utils/memory/block_allocator.h
@@ -131,13 +131,16 @@
template <bool IS_CONST>
class TView {
public:
+ /// The iterator type
+ using iterator = TIterator<IS_CONST>;
+ /// The const iterator type
+ using const_iterator = TIterator<true>;
+
/// @returns an iterator to the beginning of the view
- TIterator<IS_CONST> begin() const {
- return TIterator<IS_CONST>{allocator_->data.pointers.root, 0};
- }
+ iterator begin() const { return iterator{allocator_->data.pointers.root, 0}; }
/// @returns an iterator to the end of the view
- TIterator<IS_CONST> end() const { return TIterator<IS_CONST>{nullptr, 0}; }
+ iterator end() const { return iterator{nullptr, 0}; }
private:
friend BlockAllocator; // For BlockAllocator::operator View()
