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_function/function.h" 20 #include "pw_span/span.h" 21 22 namespace pw::allocator::internal { 23 24 /// List of free chunks of a fixed size. 25 /// 26 /// A "chunk" is simply a memory region of at least `sizeof(void*)` bytes. 27 /// When part of a `Bucket`, each chunk will contain a pointer to the next 28 /// chunk in the bucket. 29 class Bucket final { 30 public: 31 /// Constructs a bucket with an unbounded chunk size. 32 constexpr Bucket() = default; 33 34 /// Construct a bucket. 35 /// 36 /// @param chunk_size The fixed size of the memory chunks in this bucket. 37 /// Must be at least `sizeof(std::byte*)`. 38 explicit Bucket(size_t chunk_size); 39 40 Bucket(const Bucket& other) = delete; 41 Bucket& operator=(const Bucket& other) = delete; 42 Bucket(Bucket && other)43 Bucket(Bucket&& other) { *this = std::move(other); } 44 Bucket& operator=(Bucket&& other); 45 46 ~Bucket() = default; 47 48 /// Creates a list of buckets, with each twice as large as the one before it. 49 static void Init(span<Bucket> buckets, size_t min_chunk_size); 50 chunk_size()51 size_t chunk_size() const { return chunk_size_; } 52 empty()53 bool empty() const { return chunks_ == nullptr; } 54 55 /// Returns the number of the chunks in the bucket. 56 /// 57 /// Note: This method runs in O(n) time. 58 size_t count() const; 59 60 /// Adds a memory region to this bucket. 61 /// 62 /// @param ptr The memory region to be added. 63 void Add(std::byte* ptr); 64 65 /// Applies the given function to each chunk in the bucket. 66 void Visit(const Function<void(const std::byte*)>& visitor) const; 67 68 /// Removes a chunk from this bucket. 69 /// 70 /// @retval The removed region, or null if the bucket is empty. 71 std::byte* Remove(); 72 73 /// Removes a chunk 74 std::byte* RemoveIf(const Function<bool(void*)>& cond); 75 76 private: 77 std::byte* chunks_ = nullptr; 78 size_t chunk_size_ = std::numeric_limits<size_t>::max(); 79 }; 80 81 } // namespace pw::allocator::internal 82