Pigweed
C/C++ API Reference
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Loading...
Searching...
No Matches
best_fit.h
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#include <limits>
18
19#include "pw_allocator/block/detailed_block.h"
20#include "pw_allocator/block_allocator.h"
21#include "pw_allocator/bucket/fast_sorted.h"
22#include "pw_allocator/bucket/sorted.h"
23#include "pw_allocator/config.h"
24
25namespace pw::allocator {
26
28template <typename OffsetType>
29using BestFitBlock = DetailedBlock<OffsetType, GenericFastSortedItem>;
30
40template <typename BlockType = BestFitBlock<uintptr_t>>
41class BestFitAllocator : public BlockAllocator<BlockType> {
42 public:
44
46 constexpr BestFitAllocator() = default;
47
53 BestFitAllocator(ByteSpan region) { Base::Init(region); }
54
55 private:
58 // The small bucket is slower; skip it if we can.
59 BlockType* block = nullptr;
60 if (layout.size() <= sizeof(SortedItem)) {
61 block = small_bucket_.RemoveCompatible(layout);
62 if (block != nullptr) {
63 return BlockType::AllocFirst(std::move(block), layout);
64 }
65 }
66 block = large_bucket_.RemoveCompatible(layout);
67 if (block != nullptr) {
68 return BlockType::AllocFirst(std::move(block), layout);
69 }
70 return BlockResult<BlockType>(nullptr, Status::NotFound());
71 }
72
74 void ReserveBlock(BlockType& block) override {
75 // The small bucket is slower; skip it if we can.
76 if (!large_bucket_.Remove(block)) {
77 std::ignore = small_bucket_.Remove(block);
78 }
79 }
80
82 void RecycleBlock(BlockType& block) override {
83 if (block.InnerSize() <= sizeof(SortedItem)) {
84 std::ignore = small_bucket_.Add(block);
85 } else {
86 std::ignore = large_bucket_.Add(block);
87 }
88 }
89
91 FastSortedBucket<BlockType> large_bucket_;
92};
93
94} // namespace pw::allocator
Definition: best_fit.h:41
void RecycleBlock(BlockType &block) override
Definition: best_fit.h:82
BlockResult< BlockType > ChooseBlock(Layout layout) override
Definition: best_fit.h:57
constexpr BestFitAllocator()=default
Constexpr constructor. Callers must explicitly call Init.
BestFitAllocator(ByteSpan region)
Definition: best_fit.h:53
void ReserveBlock(BlockType &block) override
Definition: best_fit.h:74
Definition: block_allocator.h:104
void Init(ByteSpan region)
Definition: block_allocator.h:281
Definition: result.h:114
Definition: fast_sorted.h:63
Definition: sorted.h:103
Definition: layout.h:56
Definition: sorted.h:30