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 <cstddef> 17 18 #include "pw_allocator/bucket/base.h" 19 #include "pw_containers/intrusive_multimap.h" 20 #include "pw_function/function.h" 21 22 namespace pw::allocator { 23 24 /// Intrusive item type corresponding to a `FastSortedBucket`. 25 /// 26 /// When free blocks are added to a bucket, their usable space is used to store 27 /// an intrusive item that can be added to the bucket's intrusive container. 28 /// 29 /// This particular item is derived from pw_container's `AATreeItem`, which 30 /// allows O(log(n)) insertion and lookup and is thus "fast". 31 template <typename BlockType> 32 class FastSortedItem 33 : public IntrusiveMultiMap<size_t, FastSortedItem<BlockType>>::Item { 34 public: key()35 size_t key() const { 36 const auto* block = BlockType::FromUsableSpace(this); 37 return block->InnerSize(); 38 } 39 }; 40 41 /// Generic type with the same layout as a `FastSortedItem<BlockType>`. 42 /// 43 /// `FastSortedItem` depends on a `BlockType`, in order to return the block's 44 /// inner size as a sorting key. `BlockType` definitions like `DetailedBlock` 45 /// take a `WhenFree` parameter that describes the layout of memoryused to track 46 /// the block when free. The `WhenFree` parameter then _should_ be 47 /// `FastSortedItem`, but cannot be due to the circular dependency. Instead, 48 /// this type provides same layout without depending on `BlockType`, and thus 49 /// can be used when defining the block. 50 struct GenericFastSortedItem 51 : public IntrusiveMultiMap<size_t, GenericFastSortedItem>::Item {}; 52 53 /// Container of size-sorted free blocks. 54 /// 55 /// The container used to hold the blocks is a multimap. Insertion and removal 56 /// are O(log(n)) operations. However, the multimap nodes require more space 57 /// than the "compact" items. As such, this bucket type is a good general 58 /// purpose container for items above a minimum size. 59 template <typename BlockType> 60 class FastSortedBucket 61 : public internal::BucketBase<FastSortedBucket<BlockType>, 62 BlockType, 63 FastSortedItem<BlockType>> { 64 private: 65 using Base = internal::BucketBase<FastSortedBucket<BlockType>, 66 BlockType, 67 FastSortedItem<BlockType>>; 68 friend Base; 69 70 template <typename> 71 friend class ReverseFastSortedBucket; 72 73 using Compare = Function<bool(size_t, size_t)>; 74 75 public: 76 constexpr FastSortedBucket() = default; ~FastSortedBucket()77 ~FastSortedBucket() { Base::Clear(); } 78 79 private: 80 // Constructor used by `ReverseFastSortedBucket`. FastSortedBucket(Compare && compare)81 constexpr explicit FastSortedBucket(Compare&& compare) 82 : items_(std::move(compare)) {} 83 84 /// @copydoc `BucketBase::Add` DoAdd(BlockType & block)85 void DoAdd(BlockType& block) { 86 auto* item = new (block.UsableSpace()) FastSortedItem<BlockType>(); 87 items_.insert(*item); 88 } 89 90 /// @copydoc `BucketBase::Remove` DoRemove(BlockType & block)91 bool DoRemove(BlockType& block) { 92 FastSortedItem<BlockType>& item_to_remove = Base::GetItemFrom(block); 93 auto iters = items_.equal_range(block.InnerSize()); 94 auto iter = 95 std::find_if(iters.first, 96 iters.second, 97 [&item_to_remove](FastSortedItem<BlockType>& item) { 98 return &item_to_remove == &item; 99 }); 100 if (iter == items_.end()) { 101 return false; 102 } 103 items_.erase(iter); 104 return true; 105 } 106 107 /// @copydoc `BucketBase::Remove` DoRemoveCompatible(Layout layout)108 BlockType* DoRemoveCompatible(Layout layout) { 109 auto iter = items_.lower_bound(layout.size()); 110 return RemoveImpl(iter, layout); 111 } 112 113 template <typename Iterator> RemoveImpl(Iterator iter,Layout layout)114 BlockType* RemoveImpl(Iterator iter, Layout layout) { 115 iter = 116 std::find_if(iter, items_.end(), Base::MakeCanAllocPredicate(layout)); 117 auto* block = Base::GetBlockFromIterator(iter, items_.end()); 118 if (block != nullptr) { 119 items_.erase(iter); 120 } 121 return block; 122 } 123 124 IntrusiveMultiMap<size_t, FastSortedItem<BlockType>> items_; 125 }; 126 127 /// Like `FastSortedBucket`, but ordered largest to smallest. 128 /// 129 /// In particular, `Remove()` will return the largest free block. 130 template <typename BlockType> 131 class ReverseFastSortedBucket 132 : public internal::BucketBase<ReverseFastSortedBucket<BlockType>, 133 BlockType, 134 FastSortedItem<BlockType>> { 135 private: 136 using Base = internal::BucketBase<ReverseFastSortedBucket<BlockType>, 137 BlockType, 138 FastSortedItem<BlockType>>; 139 friend Base; 140 141 public: ReverseFastSortedBucket()142 constexpr ReverseFastSortedBucket() 143 : impl_(std::greater<>()), items_(impl_.items_) {} 144 145 private: 146 /// @copydoc `BucketBase::Add` DoAdd(BlockType & block)147 void DoAdd(BlockType& block) { impl_.DoAdd(block); } 148 149 /// @copydoc `BucketBase::Remove` DoRemove(BlockType & block)150 bool DoRemove(BlockType& block) { return impl_.DoRemove(block); } 151 152 /// @copydoc `BucketBase::Remove` DoRemoveCompatible(Layout layout)153 BlockType* DoRemoveCompatible(Layout layout) { 154 return impl_.RemoveImpl(impl_.items_.begin(), layout); 155 } 156 157 FastSortedBucket<BlockType> impl_; 158 IntrusiveMultiMap<size_t, FastSortedItem<BlockType>>& items_; 159 }; 160 161 } // namespace pw::allocator 162