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_forward_list.h" 20 21 namespace pw::allocator { 22 23 /// Intrusive item type corresponding to a `SortedBucket`. 24 /// 25 /// When free blocks are added to a bucket, their usable space is used to store 26 /// an intrusive item that can be added to the bucket's intrusive container. 27 /// 28 /// This particular item is derived from pw_container's smallest intrusive item 29 /// type, hence it is the most "compact". 30 class SortedItem : public IntrusiveForwardList<SortedItem>::Item {}; 31 32 namespace internal { 33 34 /// Container of size-sorted free blocks. 35 /// 36 /// The container used to hold the free blocks is a forward list. As a result, 37 /// it is able to store small free blocks with inner sizes as small as 38 /// `sizeof(void*)`. However, holding such small blocks in a sorted list 39 /// requires that insertion and removal are O(n) operations. As such, this 40 /// bucket type is only useful for bounded lists of free blocks, such as caches. 41 /// 42 /// This CRTP-style base class requires a derived class to provide a predicate 43 /// that indicates where each item should be inserted in the list. 44 template <typename Derived, typename BlockType> 45 class SortedBucketBase : public BucketBase<Derived, BlockType, SortedItem> { 46 private: 47 using Base = BucketBase<Derived, BlockType, SortedItem>; 48 friend Base; 49 50 public: 51 constexpr SortedBucketBase() = default; ~SortedBucketBase()52 ~SortedBucketBase() { Base::Clear(); } 53 54 private: 55 /// @copydoc `BucketBase::Add` DoAdd(BlockType & block)56 void DoAdd(BlockType& block) { 57 auto* item_to_add = new (block.UsableSpace()) SortedItem(); 58 auto prev = Base::FindPrevIf(items_.before_begin(), 59 items_.end(), 60 Derived::MakeAddPredicate(block.InnerSize())); 61 items_.insert_after(prev, *item_to_add); 62 } 63 64 /// @copydoc `BucketBase::RemoveAny` DoRemoveAny()65 BlockType* DoRemoveAny() { 66 SortedItem& item = items_.front(); 67 items_.pop_front(); 68 return BlockType::FromUsableSpace(&item); 69 } 70 71 /// @copydoc `BucketBase::Remove` DoRemove(BlockType & block)72 bool DoRemove(BlockType& block) { 73 return items_.remove(Base::GetItemFrom(block)); 74 } 75 76 /// @copydoc `Bucket::Remove` DoRemoveCompatible(Layout layout)77 BlockType* DoRemoveCompatible(Layout layout) { 78 auto prev = Base::FindPrevIf(items_.before_begin(), 79 items_.end(), 80 Base::MakeCanAllocPredicate(layout)); 81 auto* block = Base::GetBlockFromPrev(prev, items_.end()); 82 if (block != nullptr) { 83 items_.erase_after(prev); 84 } 85 return block; 86 } 87 88 IntrusiveForwardList<SortedItem> items_; 89 }; 90 91 } // namespace internal 92 93 /// Container of free blocks sorted in order of increasing size. 94 /// 95 /// As noted in the base class, this class relies on a forward list. This allows 96 /// the free blocks to be as small as a single pointer, but makes insertion and 97 /// lookup O(n) on the number of blocks in the bucket. 98 /// 99 /// Calling `RemoveAny()` on this bucket will return the smallest free block. 100 template <typename BlockType> 101 class ForwardSortedBucket 102 : public internal::SortedBucketBase<ForwardSortedBucket<BlockType>, 103 BlockType> { 104 public: 105 /// Returns a lambda that tests if the block storing an item has an inner size 106 /// larger than the given `inner_size`. 107 /// 108 /// This lambda can be used with `std::find_if` and `FindPrevIf`. MakeAddPredicate(size_t inner_size)109 static constexpr auto MakeAddPredicate(size_t inner_size) { 110 return [inner_size](SortedItem& item) { 111 auto* block = BlockType::FromUsableSpace(&item); 112 return inner_size < block->InnerSize(); 113 }; 114 } 115 }; 116 117 /// Container of free blocks sorted in order of decreasing size. 118 /// 119 /// As noted in the base class, this class relies on a forward list. This allows 120 /// the free blocks to be as small as a single pointer, but makes insertion and 121 /// lookup O(n) on the number of blocks in the bucket. 122 /// 123 /// Calling `RemoveAny()` on this bucket will return the largest free block. 124 template <typename BlockType> 125 class ReverseSortedBucket 126 : public internal::SortedBucketBase<ReverseSortedBucket<BlockType>, 127 BlockType> { 128 public: 129 /// Returns a lambda that tests if the block storing an item has an inner size 130 /// smaller than the given `inner_size`. 131 /// 132 /// This lambda can be used with `std::find_if` and `FindPrevIf`. MakeAddPredicate(size_t inner_size)133 static constexpr auto MakeAddPredicate(size_t inner_size) { 134 return [inner_size](SortedItem& item) { 135 auto* block = BlockType::FromUsableSpace(&item); 136 return block->InnerSize() < inner_size; 137 }; 138 } 139 }; 140 141 } // namespace pw::allocator 142