blob: 4629a4f158f554d89a88cca45600cf5e276f27db [file] [log] [blame]
// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#include "pw_allocator/freelist.h"
namespace pw::allocator {
Status FreeList::AddChunk(std::span<std::byte> chunk) {
// Check that the size is enough to actually store what we need
if (chunk.size() < sizeof(FreeListNode)) {
return Status::OUT_OF_RANGE;
}
union {
FreeListNode* node;
std::byte* bytes;
} aliased;
aliased.bytes = chunk.data();
size_t chunk_ptr = FindChunkPtrForSize(chunk.size(), false);
// Add it to the correct list.
aliased.node->size = chunk.size();
aliased.node->next = chunks_[chunk_ptr];
chunks_[chunk_ptr] = aliased.node;
return Status::OK;
}
std::span<std::byte> FreeList::FindChunk(size_t size) const {
if (size == 0) {
return std::span<std::byte>();
}
size_t chunk_ptr = FindChunkPtrForSize(size, true);
// Check that there's data. This catches the case where we run off the
// end of the array
if (chunks_[chunk_ptr] == nullptr) {
return std::span<std::byte>();
}
// Now iterate up the buckets, walking each list to find a good candidate
for (size_t i = chunk_ptr; i < chunks_.size(); i++) {
union {
FreeListNode* node;
std::byte* data;
} aliased;
aliased.node = chunks_[i];
while (aliased.node != nullptr) {
if (aliased.node->size >= size) {
return std::span<std::byte>(aliased.data, aliased.node->size);
}
aliased.node = aliased.node->next;
}
}
// If we get here, we've checked every block in every bucket. There's
// nothing that can support this allocation.
return std::span<std::byte>();
}
Status FreeList::RemoveChunk(std::span<std::byte> chunk) {
size_t chunk_ptr = FindChunkPtrForSize(chunk.size(), true);
// Walk that list, finding the chunk.
union {
FreeListNode* node;
std::byte* data;
} aliased, aliased_next;
// Check head first.
if (chunks_[chunk_ptr] == nullptr) {
return Status::NOT_FOUND;
}
aliased.node = chunks_[chunk_ptr];
if (aliased.data == chunk.data()) {
chunks_[chunk_ptr] = aliased.node->next;
return Status::OK;
}
// No? Walk the nodes.
aliased.node = chunks_[chunk_ptr];
while (aliased.node->next != nullptr) {
aliased_next.node = aliased.node->next;
if (aliased_next.data == chunk.data()) {
// Found it, remove this node out of the chain
aliased.node->next = aliased_next.node->next;
return Status::OK;
}
aliased.node = aliased.node->next;
}
return Status::NOT_FOUND;
}
size_t FreeList::FindChunkPtrForSize(size_t size, bool non_null) const {
size_t chunk_ptr = 0;
for (chunk_ptr = 0; chunk_ptr < sizes_.size(); chunk_ptr++) {
if (sizes_[chunk_ptr] >= size &&
(!non_null || chunks_[chunk_ptr] != nullptr)) {
break;
}
}
return chunk_ptr;
}
} // namespace pw::allocator