xref: /aosp_15_r20/external/pigweed/pw_allocator/bucket/public/pw_allocator/bucket/unordered.h (revision 61c4878ac05f98d0ceed94b57d316916de578985)
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