1 // Copyright 2024 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include "pw_allocator/block/contiguous.h" 17 18 namespace pw::allocator { 19 namespace internal { 20 21 // Trivial base class for trait support. 22 struct IterableBase {}; 23 24 } // namespace internal 25 26 /// Mix-in for blocks that allows creating forward iterators over block ranges. 27 /// 28 /// Block mix-ins are stateless and trivially constructible. See `BasicBlock` 29 /// for details on how mix-ins can be combined to implement blocks. 30 /// 31 /// This mix-in requires its derived type also derive from `ContiguousBlock`. 32 template <typename Derived> 33 class IterableBlock : public internal::IterableBase { 34 protected: IterableBlock()35 constexpr explicit IterableBlock() { 36 // Assert within a function, since `Derived` is not complete when this type 37 // is defined. 38 static_assert(is_contiguous_v<Derived>, 39 "Types derived from IterableBlock must also derive " 40 "from ContiguousBlock"); 41 } 42 43 public: 44 /// Represents an iterator that moves forward through a list of blocks. 45 /// 46 /// This class is not typically instantiated directly, but rather using a 47 /// range-based for-loop using `Block::Range`. 48 /// 49 /// Allocating or freeing blocks invalidates the iterator. 50 class Iterator final { 51 public: Iterator(Derived * block)52 constexpr explicit Iterator(Derived* block) : block_(block) {} 53 constexpr Iterator& operator++() { 54 block_ = block_ != nullptr ? block_->Next() : nullptr; 55 return *this; 56 } 57 constexpr bool operator!=(const Iterator& other) { 58 return block_ != other.block_; 59 } 60 constexpr Derived* operator*() { return block_; } 61 62 private: 63 Derived* block_; 64 }; 65 66 /// Represents a range of blocks that can be iterated over. 67 /// 68 /// The typical usage of this class is in a range-based for-loop, e.g. 69 /// @code{.cpp} 70 /// for (auto* block : Range(first, last)) { ... } 71 /// @endcode 72 /// 73 /// Allocating or freeing blocks invalidates the range. 74 class Range final { 75 public: 76 /// Constructs a range including `begin` and all valid following blocks. Range(Derived * begin)77 constexpr explicit Range(Derived* begin) : begin_(begin), end_(nullptr) {} 78 79 /// Constructs a range of blocks from `begin` to `end`, inclusively. Range(Derived * begin_inclusive,Derived * end_inclusive)80 constexpr Range(Derived* begin_inclusive, Derived* end_inclusive) 81 : begin_(begin_inclusive), end_(end_inclusive->Next()) {} 82 begin()83 constexpr Iterator& begin() { return begin_; } end()84 constexpr Iterator& end() { return end_; } 85 86 private: 87 Iterator begin_; 88 Iterator end_; 89 }; 90 }; 91 92 /// Trait type that allow interrogating a block as to whether it is forward- 93 /// iterable. 94 template <typename BlockType> 95 struct is_iterable : std::is_base_of<internal::IterableBase, BlockType> {}; 96 97 /// Helper variable template for `is_iterable<BlockType>::value`. 98 template <typename BlockType> 99 constexpr bool is_iterable_v = is_iterable<BlockType>::value; 100 101 } // namespace pw::allocator 102