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::Remove` DoRemove(BlockType & block)65 bool DoRemove(BlockType& block) { 66 return items_.remove(Base::GetItemFrom(block)); 67 } 68 69 /// @copydoc `Bucket::Remove` DoRemoveCompatible(Layout layout)70 BlockType* DoRemoveCompatible(Layout layout) { 71 auto prev = Base::FindPrevIf(items_.before_begin(), 72 items_.end(), 73 Base::MakeCanAllocPredicate(layout)); 74 auto* block = Base::GetBlockFromPrev(prev, items_.end()); 75 if (block != nullptr) { 76 items_.erase_after(prev); 77 } 78 return block; 79 } 80 81 IntrusiveForwardList<SortedItem> items_; 82 }; 83 84 } // namespace internal 85 86 /// Container of free blocks sorted in order of increasing size. 87 /// 88 /// As noted in the base class, this class relies on a forward list. This allows 89 /// the free blocks to be as small as a single pointer, but makes insertion and 90 /// lookup O(n) on the number of blocks in the bucket. 91 /// 92 /// Calling `RemoveAny()` on this bucket will return the smallest free block. 93 template <typename BlockType> 94 class ForwardSortedBucket 95 : public internal::SortedBucketBase<ForwardSortedBucket<BlockType>, 96 BlockType> { 97 public: 98 /// Returns a lambda that tests if the block storing an item has an inner size 99 /// larger than the given `inner_size`. 100 /// 101 /// This lambda can be used with `std::find_if` and `FindPrevIf`. MakeAddPredicate(size_t inner_size)102 static constexpr auto MakeAddPredicate(size_t inner_size) { 103 return [inner_size](SortedItem& item) { 104 auto* block = BlockType::FromUsableSpace(&item); 105 return inner_size < block->InnerSize(); 106 }; 107 } 108 }; 109 110 /// Container of free blocks sorted in order of decreasing size. 111 /// 112 /// As noted in the base class, this class relies on a forward list. This allows 113 /// the free blocks to be as small as a single pointer, but makes insertion and 114 /// lookup O(n) on the number of blocks in the bucket. 115 /// 116 /// Calling `RemoveAny()` on this bucket will return the largest free block. 117 template <typename BlockType> 118 class ReverseSortedBucket 119 : public internal::SortedBucketBase<ReverseSortedBucket<BlockType>, 120 BlockType> { 121 public: 122 /// Returns a lambda that tests if the block storing an item has an inner size 123 /// smaller than the given `inner_size`. 124 /// 125 /// This lambda can be used with `std::find_if` and `FindPrevIf`. MakeAddPredicate(size_t inner_size)126 static constexpr auto MakeAddPredicate(size_t inner_size) { 127 return [inner_size](SortedItem& item) { 128 auto* block = BlockType::FromUsableSpace(&item); 129 return block->InnerSize() < inner_size; 130 }; 131 } 132 }; 133 134 } // namespace pw::allocator 135