xref: /aosp_15_r20/external/pigweed/pw_allocator/bucket/public/pw_allocator/bucket/sorted.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 "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 a `SortedBucket`.
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, hence it is the most "compact".
30 class SortedItem : public IntrusiveForwardList<SortedItem>::Item {};
31 
32 namespace internal {
33 
34 /// Container of size-sorted free blocks.
35 ///
36 /// The container used to hold the free blocks is a forward list. As a result,
37 /// it is able to store small free blocks with inner sizes as small as
38 /// `sizeof(void*)`. However, holding such small blocks in a sorted list
39 /// requires that insertion and removal are O(n) operations. As such, this
40 /// bucket type is only useful for bounded lists of free blocks, such as caches.
41 ///
42 /// This CRTP-style base class requires a derived class to provide a predicate
43 /// that indicates where each item should be inserted in the list.
44 template <typename Derived, typename BlockType>
45 class SortedBucketBase : public BucketBase<Derived, BlockType, SortedItem> {
46  private:
47   using Base = BucketBase<Derived, BlockType, SortedItem>;
48   friend Base;
49 
50  public:
51   constexpr SortedBucketBase() = default;
~SortedBucketBase()52   ~SortedBucketBase() { Base::Clear(); }
53 
54  private:
55   /// @copydoc `BucketBase::Add`
DoAdd(BlockType & block)56   void DoAdd(BlockType& block) {
57     auto* item_to_add = new (block.UsableSpace()) SortedItem();
58     auto prev = Base::FindPrevIf(items_.before_begin(),
59                                  items_.end(),
60                                  Derived::MakeAddPredicate(block.InnerSize()));
61     items_.insert_after(prev, *item_to_add);
62   }
63 
64   /// @copydoc `BucketBase::Remove`
DoRemove(BlockType & block)65   bool DoRemove(BlockType& block) {
66     return items_.remove(Base::GetItemFrom(block));
67   }
68 
69   /// @copydoc `Bucket::Remove`
DoRemoveCompatible(Layout layout)70   BlockType* DoRemoveCompatible(Layout layout) {
71     auto prev = Base::FindPrevIf(items_.before_begin(),
72                                  items_.end(),
73                                  Base::MakeCanAllocPredicate(layout));
74     auto* block = Base::GetBlockFromPrev(prev, items_.end());
75     if (block != nullptr) {
76       items_.erase_after(prev);
77     }
78     return block;
79   }
80 
81   IntrusiveForwardList<SortedItem> items_;
82 };
83 
84 }  // namespace internal
85 
86 /// Container of free blocks sorted in order of increasing size.
87 ///
88 /// As noted in the base class, this class relies on a forward list. This allows
89 /// the free blocks to be as small as a single pointer, but makes insertion and
90 /// lookup O(n) on the number of blocks in the bucket.
91 ///
92 /// Calling `RemoveAny()` on this bucket will return the smallest free block.
93 template <typename BlockType>
94 class ForwardSortedBucket
95     : public internal::SortedBucketBase<ForwardSortedBucket<BlockType>,
96                                         BlockType> {
97  public:
98   /// Returns a lambda that tests if the block storing an item has an inner size
99   /// larger than the given `inner_size`.
100   ///
101   /// This lambda can be used with `std::find_if` and `FindPrevIf`.
MakeAddPredicate(size_t inner_size)102   static constexpr auto MakeAddPredicate(size_t inner_size) {
103     return [inner_size](SortedItem& item) {
104       auto* block = BlockType::FromUsableSpace(&item);
105       return inner_size < block->InnerSize();
106     };
107   }
108 };
109 
110 /// Container of free blocks sorted in order of decreasing size.
111 ///
112 /// As noted in the base class, this class relies on a forward list. This allows
113 /// the free blocks to be as small as a single pointer, but makes insertion and
114 /// lookup O(n) on the number of blocks in the bucket.
115 ///
116 /// Calling `RemoveAny()` on this bucket will return the largest free block.
117 template <typename BlockType>
118 class ReverseSortedBucket
119     : public internal::SortedBucketBase<ReverseSortedBucket<BlockType>,
120                                         BlockType> {
121  public:
122   /// Returns a lambda that tests if the block storing an item has an inner size
123   /// smaller than the given `inner_size`.
124   ///
125   /// This lambda can be used with `std::find_if` and `FindPrevIf`.
MakeAddPredicate(size_t inner_size)126   static constexpr auto MakeAddPredicate(size_t inner_size) {
127     return [inner_size](SortedItem& item) {
128       auto* block = BlockType::FromUsableSpace(&item);
129       return block->InnerSize() < inner_size;
130     };
131   }
132 };
133 
134 }  // namespace pw::allocator
135