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 <algorithm> 17 #include <cstddef> 18 #include <iterator> 19 20 #include "pw_allocator/bucket/base.h" 21 #include "pw_containers/intrusive_list.h" 22 23 namespace pw::allocator { 24 25 /// Intrusive item type corresponding to a `SequencedBucket`. 26 /// 27 /// When free blocks are added to a bucket, their usable space is used to store 28 /// an intrusive item that can be added to the bucket's intrusive container. 29 /// 30 /// This particular item is derived from pw_container's doubly linked list item, 31 /// which allows it to be easily inserted and removed from a "sequence". 32 class SequencedItem 33 : public containers::future::IntrusiveList<SequencedItem>::Item {}; 34 35 /// Container of a sequence of free blocks. 36 /// 37 /// The container used to hold the blocks is a doubly-linked list. The list is 38 /// sorted on the memory address of the blocks themselves. Insertion is O(n), 39 /// while removal is O(1). This bucket type is useful when the order of blocks 40 /// must be preserved. 41 template <typename BlockType> 42 class SequencedBucket : public internal::BucketBase<SequencedBucket<BlockType>, 43 BlockType, 44 SequencedItem> { 45 private: 46 using Base = internal:: 47 BucketBase<SequencedBucket<BlockType>, BlockType, SequencedItem>; 48 friend Base; 49 50 public: ~SequencedBucket()51 ~SequencedBucket() { Base::Clear(); } 52 threshold()53 constexpr size_t threshold() const { return threshold_; } 54 55 /// Sets the threshold for which blocks are considered "large". 56 /// 57 /// This threshold can improve performance when blocks are partitioned based 58 /// on size. Iterating over the free blocks to add or remove a block will 59 /// start at the beginning for block with an inner size considered "large", 60 /// and the end for blocks with an inner size considered "small". set_threshold(size_t threshold)61 void set_threshold(size_t threshold) { threshold_ = threshold; } 62 63 private: 64 /// @copydoc `BucketBase::Add` DoAdd(BlockType & block)65 void DoAdd(BlockType& block) { 66 auto* item_to_add = new (block.UsableSpace()) SequencedItem(); 67 containers::future::IntrusiveList<SequencedItem>::iterator iter; 68 if (block.InnerSize() < threshold_) { 69 // Search from back. 70 auto r_iter = std::find_if( 71 items_.rbegin(), items_.rend(), [item_to_add](SequencedItem& item) { 72 return &item < item_to_add; 73 }); 74 75 // If r_iter dereferences to the last address that is before than the 76 // item to add, then the corresponding forward iterator points to the 77 // first address that is after the item to add. 78 iter = r_iter.base(); 79 80 } else { 81 // Search from front. 82 iter = std::find_if( 83 items_.begin(), items_.end(), [item_to_add](SequencedItem& item) { 84 return item_to_add < &item; 85 }); 86 } 87 items_.insert(iter, *item_to_add); 88 } 89 90 /// @copydoc `BucketBase::RemoveAny` DoRemoveAny()91 BlockType* DoRemoveAny() { 92 SequencedItem& item = items_.front(); 93 items_.pop_front(); 94 return BlockType::FromUsableSpace(&item); 95 } 96 97 /// @copydoc `BucketBase::Remove` DoRemove(BlockType & block)98 bool DoRemove(BlockType& block) { 99 SequencedItem& item_to_remove = Base::GetItemFrom(block); 100 if (block.InnerSize() >= threshold_) { 101 // Search from front and remove. 102 return items_.remove(item_to_remove); 103 } 104 // Search from back and remove. 105 auto iter = std::find_if( 106 items_.rbegin(), items_.rend(), [&item_to_remove](SequencedItem& item) { 107 return &item_to_remove == &item; 108 }); 109 if (iter == items_.rend()) { 110 return false; 111 } 112 items_.erase(*iter); 113 return true; 114 } 115 116 /// @copydoc `BucketBase::Remove` DoRemoveCompatible(Layout layout)117 BlockType* DoRemoveCompatible(Layout layout) { 118 auto predicate = Base::MakeCanAllocPredicate(layout); 119 SequencedItem* item = nullptr; 120 if (layout.size() < threshold_) { 121 // Search from back. 122 auto iter = std::find_if(items_.rbegin(), items_.rend(), predicate); 123 item = iter != items_.rend() ? &(*iter) : nullptr; 124 } else { 125 // Search from front. 126 auto iter = std::find_if(items_.begin(), items_.end(), predicate); 127 item = iter != items_.end() ? &(*iter) : nullptr; 128 } 129 if (item == nullptr) { 130 return nullptr; 131 } 132 auto* block = BlockType::FromUsableSpace(item); 133 items_.erase(*item); 134 return block; 135 } 136 137 containers::future::IntrusiveList<SequencedItem> items_; 138 size_t threshold_ = 0; 139 }; 140 141 } // namespace pw::allocator 142