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 classes for trait support. 22 struct ForwardIterableBase {}; 23 struct ReverseIterableBase {}; 24 25 } // namespace internal 26 27 /// Mix-in for blocks that allows creating forward iterators over block ranges. 28 /// 29 /// Block mix-ins are stateless and trivially constructible. See `BasicBlock` 30 /// for details on how mix-ins can be combined to implement blocks. 31 /// 32 /// This mix-in requires its derived type also derive from `ContiguousBlock`. 33 template <typename Derived> 34 class ForwardIterableBlock : public internal::ForwardIterableBase { 35 protected: ForwardIterableBlock()36 constexpr explicit ForwardIterableBlock() { 37 // Assert within a function, since `Derived` is not complete when this type 38 // is defined. 39 static_assert(is_contiguous_v<Derived>, 40 "Types derived from ForwardIterableBlock must also derive " 41 "from ContiguousBlock"); 42 } 43 44 public: 45 /// Represents an iterator that moves forward through a list of blocks. 46 /// 47 /// This class is not typically instantiated directly, but rather using a 48 /// range-based for-loop using `Block::Range`. 49 /// 50 /// Allocating or freeing blocks invalidates the iterator. 51 class Iterator final { 52 public: Iterator(Derived * block)53 constexpr explicit Iterator(Derived* block) : block_(block) {} 54 constexpr Iterator& operator++() { 55 block_ = block_ != nullptr ? block_->Next() : nullptr; 56 return *this; 57 } 58 constexpr bool operator!=(const Iterator& other) { 59 return block_ != other.block_; 60 } 61 constexpr Derived* operator*() { return block_; } 62 63 private: 64 Derived* block_; 65 }; 66 67 /// Represents a range of blocks that can be iterated over. 68 /// 69 /// The typical usage of this class is in a range-based for-loop, e.g. 70 /// @code{.cpp} 71 /// for (auto* block : Range(first, last)) { ... } 72 /// @endcode 73 /// 74 /// Allocating or freeing blocks invalidates the range. 75 class Range final { 76 public: 77 /// Constructs a range including `begin` and all valid following blocks. Range(Derived * begin)78 constexpr explicit Range(Derived* begin) : begin_(begin), end_(nullptr) {} 79 80 /// Constructs a range of blocks from `begin` to `end`, inclusively. Range(Derived * begin_inclusive,Derived * end_inclusive)81 constexpr Range(Derived* begin_inclusive, Derived* end_inclusive) 82 : begin_(begin_inclusive), end_(end_inclusive->Next()) {} 83 begin()84 constexpr Iterator& begin() { return begin_; } end()85 constexpr Iterator& end() { return end_; } 86 87 private: 88 Iterator begin_; 89 Iterator end_; 90 }; 91 }; 92 93 /// Mix-in for blocks that allows creating reverse iterators over block ranges. 94 /// 95 /// Block mix-ins are stateless and trivially constructible. See `BasicBlock` 96 /// for details on how mix-ins can be combined to implement blocks. 97 /// 98 /// This mix-in requires its derived type also derive from `ContiguousBlock`. 99 template <typename Derived> 100 class ReverseIterableBlock : public internal::ReverseIterableBase { 101 protected: ReverseIterableBlock()102 constexpr explicit ReverseIterableBlock() { 103 // Assert within a function, since `Derived` is not complete when this type 104 // is defined. 105 static_assert(is_contiguous_v<Derived>, 106 "Types derived from ReverseIterableBlock must also derive " 107 "from ContiguousBlock"); 108 } 109 110 public: 111 /// Represents an iterator that moves backward through a list of blocks. 112 /// 113 /// This class is not typically instantiated directly, but rather using a 114 /// range-based for-loop using `Block::ReverseRange`. 115 /// 116 /// Allocating or freeing blocks invalidates the iterator. 117 class ReverseIterator final { 118 public: ReverseIterator(Derived * block)119 constexpr ReverseIterator(Derived* block) : block_(block) {} 120 constexpr ReverseIterator& operator++() { 121 block_ = block_ != nullptr ? block_->Prev() : nullptr; 122 return *this; 123 } 124 constexpr bool operator!=(const ReverseIterator& other) { 125 return block_ != other.block_; 126 } 127 constexpr Derived* operator*() { return block_; } 128 129 private: 130 Derived* block_; 131 }; 132 133 /// Represents a range of blocks that can be iterated over in the reverse 134 /// direction. 135 /// 136 /// The typical usage of this class is in a range-based for-loop, e.g. 137 /// @code{.cpp} 138 /// for (auto* block : ReverseRange(last, first)) { ... } 139 /// @endcode 140 /// 141 /// Allocating or freeing blocks invalidates the range. 142 class ReverseRange final { 143 public: 144 /// Constructs a range including `rbegin` and all valid preceding blocks. ReverseRange(Derived * rbegin)145 constexpr explicit ReverseRange(Derived* rbegin) 146 : begin_(rbegin), end_(nullptr) {} 147 148 /// Constructs a range of blocks from `rbegin` to `rend`, inclusively. ReverseRange(Derived * rbegin_inclusive,Derived * rend_inclusive)149 constexpr ReverseRange(Derived* rbegin_inclusive, Derived* rend_inclusive) 150 : begin_(rbegin_inclusive), end_(rend_inclusive->Prev()) {} 151 begin()152 constexpr ReverseIterator& begin() { return begin_; } end()153 constexpr ReverseIterator& end() { return end_; } 154 155 private: 156 ReverseIterator begin_; 157 ReverseIterator end_; 158 }; 159 }; 160 161 /// Trait type that allow interrogating a block as to whether it is forward- 162 /// iterable. 163 template <typename BlockType> 164 struct is_forward_iterable 165 : std::is_base_of<internal::ForwardIterableBase, BlockType> {}; 166 167 /// Helper variable template for `is_forward_iterable<BlockType>::value`. 168 template <typename BlockType> 169 inline constexpr bool is_forward_iterable_v = 170 is_forward_iterable<BlockType>::value; 171 172 /// Trait type that allow interrogating a block as to whether it is reverse- 173 /// iterable. 174 template <typename BlockType> 175 struct is_reverse_iterable 176 : std::is_base_of<internal::ReverseIterableBase, BlockType> {}; 177 178 /// Helper variable template for `is_reverse_iterable<BlockType>::value`. 179 template <typename BlockType> 180 inline constexpr bool is_reverse_iterable_v = 181 is_reverse_iterable<BlockType>::value; 182 183 } // namespace pw::allocator 184