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 "base.h" 19 #include "pw_allocator/bucket/base.h" 20 #include "pw_containers/intrusive_forward_list.h" 21 22 namespace pw::allocator { 23 24 /// Intrusive item type corresponding to an `UnorderedBucket`. 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 smallest intrusive item 30 /// type. 31 class UnorderedItem : public IntrusiveForwardList<UnorderedItem>::Item {}; 32 33 /// Container of free blocks that use minimal usable space. 34 /// 35 /// The container used to hold the blocks is a singly-linked list. As a result, 36 /// it is able to store free blocks as small as `sizeof(void*)`. Insertion and 37 /// removal of an unspecified block is O(1). Removal internal::of a specific 38 /// block is O(n) since the whole list may need to be walked to find the block. 39 /// As such, this bucket type is useful for pools of blocks of a single size. 40 template <typename BlockType> 41 class UnorderedBucket : public internal::BucketBase<UnorderedBucket<BlockType>, 42 BlockType, 43 UnorderedItem> { 44 private: 45 using Base = internal:: 46 BucketBase<UnorderedBucket<BlockType>, BlockType, UnorderedItem>; 47 friend Base; 48 49 public: ~UnorderedBucket()50 ~UnorderedBucket() { Base::Clear(); } 51 52 private: 53 /// @copydoc `BucketBase::Add` DoAdd(BlockType & block)54 void DoAdd(BlockType& block) { 55 auto* item = new (block.UsableSpace()) UnorderedItem(); 56 items_.push_front(*item); 57 } 58 59 /// @copydoc `BucketBase::Remove` DoRemove(BlockType & block)60 bool DoRemove(BlockType& block) { 61 return items_.remove(Base::GetItemFrom(block)); 62 } 63 64 /// @copydoc `BucketBase::Remove` DoRemoveCompatible(Layout layout)65 BlockType* DoRemoveCompatible(Layout layout) { 66 auto prev = Base::FindPrevIf(items_.before_begin(), 67 items_.end(), 68 Base::MakeCanAllocPredicate(layout)); 69 auto* block = Base::GetBlockFromPrev(prev, items_.end()); 70 if (block != nullptr) { 71 items_.erase_after(prev); 72 } 73 return block; 74 } 75 76 IntrusiveForwardList<UnorderedItem> items_; 77 }; 78 79 } // namespace pw::allocator 80