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