[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()