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 53 /// Sets the threshold for which blocks are considered "large". 54 /// 55 /// This threshold can improve performance when blocks are partitioned based 56 /// on size. Iterating over the free blocks to add or remove a block will 57 /// start at the beginning for block with an inner size considered "large", 58 /// and the end for blocks with an inner size considered "small". set_threshold(size_t threshold)59 void set_threshold(size_t threshold) { threshold_ = threshold; } 60 61 private: 62 /// @copydoc `BucketBase::Add` DoAdd(BlockType & block)63 void DoAdd(BlockType& block) { 64 auto* item_to_add = new (block.UsableSpace()) SequencedItem(); 65 containers::future::IntrusiveList<SequencedItem>::iterator iter; 66 if (block.InnerSize() < threshold_) { 67 // Search from back. 68 auto r_iter = std::find_if( 69 items_.rbegin(), items_.rend(), [item_to_add](SequencedItem& item) { 70 return &item < item_to_add; 71 }); 72 73 // If r_iter dereferences to the last address that is before than the 74 // item to add, then the corresponding forward iterator points to the 75 // first address that is after the item to add. 76 iter = r_iter.base(); 77 78 } else { 79 // Search from front. 80 iter = std::find_if( 81 items_.begin(), items_.end(), [item_to_add](SequencedItem& item) { 82 return item_to_add < &item; 83 }); 84 } 85 items_.insert(iter, *item_to_add); 86 } 87 88 /// @copydoc `BucketBase::Remove` DoRemove(BlockType & block)89 bool DoRemove(BlockType& block) { 90 SequencedItem& item_to_remove = Base::GetItemFrom(block); 91 if (block.InnerSize() >= threshold_) { 92 // Search from front and remove. 93 return items_.remove(item_to_remove); 94 } 95 // Search from back and remove. 96 auto iter = std::find_if( 97 items_.rbegin(), items_.rend(), [&item_to_remove](SequencedItem& item) { 98 return &item_to_remove == &item; 99 }); 100 if (iter == items_.rend()) { 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 predicate = Base::MakeCanAllocPredicate(layout); 110 SequencedItem* item = nullptr; 111 if (layout.size() < threshold_) { 112 // Search from back. 113 auto iter = std::find_if(items_.rbegin(), items_.rend(), predicate); 114 item = iter != items_.rend() ? &(*iter) : nullptr; 115 } else { 116 // Search from front. 117 auto iter = std::find_if(items_.begin(), items_.end(), predicate); 118 item = iter != items_.end() ? &(*iter) : nullptr; 119 } 120 if (item == nullptr) { 121 return nullptr; 122 } 123 auto* block = BlockType::FromUsableSpace(item); 124 items_.erase(*item); 125 return block; 126 } 127 128 containers::future::IntrusiveList<SequencedItem> items_; 129 size_t threshold_ = 0; 130 }; 131 132 } // namespace pw::allocator 133