third_party/pigweed/repo/pw_allocator/freelist.cc

   1 // Copyright 2020 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
  15 #include "pw_allocator/freelist.h"
  16
  17 namespace pw::allocator {
  18
  19 Status FreeList::AddChunk(std::span<std::byte> chunk) {
  20   // Check that the size is enough to actually store what we need
  21   if (chunk.size() < sizeof(FreeListNode)) {
  22     return Status::OutOfRange();
  23   }
  24
  25   union {
  26     FreeListNode* node;
  27     std::byte* bytes;
  28   } aliased;
  29
  30   aliased.bytes = chunk.data();
  31
  32   size_t chunk_ptr = FindChunkPtrForSize(chunk.size(), false);
  33
  34   // Add it to the correct list.
  35   aliased.node->size = chunk.size();
  36   aliased.node->next = chunks_[chunk_ptr];
  37   chunks_[chunk_ptr] = aliased.node;
  38
  39   return OkStatus();
  40 }
  41
  42 std::span<std::byte> FreeList::FindChunk(size_t size) const {
  43   if (size == 0) {
  44     return std::span<std::byte>();
  45   }
  46
  47   size_t chunk_ptr = FindChunkPtrForSize(size, true);
  48
  49   // Check that there's data. This catches the case where we run off the
  50   // end of the array
  51   if (chunks_[chunk_ptr] == nullptr) {
  52     return std::span<std::byte>();
  53   }
  54
  55   // Now iterate up the buckets, walking each list to find a good candidate
  56   for (size_t i = chunk_ptr; i < chunks_.size(); i++) {
  57     union {
  58       FreeListNode* node;
  59       std::byte* data;
  60     } aliased;
  61     aliased.node = chunks_[i];
  62
  63     while (aliased.node != nullptr) {
  64       if (aliased.node->size >= size) {
  65         return std::span<std::byte>(aliased.data, aliased.node->size);
  66       }
  67
  68       aliased.node = aliased.node->next;
  69     }
  70   }
  71
  72   // If we get here, we've checked every block in every bucket. There's
  73   // nothing that can support this allocation.
  74   return std::span<std::byte>();
  75 }
  76
  77 Status FreeList::RemoveChunk(std::span<std::byte> chunk) {
  78   size_t chunk_ptr = FindChunkPtrForSize(chunk.size(), true);
  79
  80   // Walk that list, finding the chunk.
  81   union {
  82     FreeListNode* node;
  83     std::byte* data;
  84   } aliased, aliased_next;
  85
  86   // Check head first.
  87   if (chunks_[chunk_ptr] == nullptr) {
  88     return Status::NotFound();
  89   }
  90
  91   aliased.node = chunks_[chunk_ptr];
  92   if (aliased.data == chunk.data()) {
  93     chunks_[chunk_ptr] = aliased.node->next;
  94
  95     return OkStatus();
  96   }
  97
  98   // No? Walk the nodes.
  99   aliased.node = chunks_[chunk_ptr];
 100
 101   while (aliased.node->next != nullptr) {
 102     aliased_next.node = aliased.node->next;
 103     if (aliased_next.data == chunk.data()) {
 104       // Found it, remove this node out of the chain
 105       aliased.node->next = aliased_next.node->next;
 106       return OkStatus();
 107     }
 108
 109     aliased.node = aliased.node->next;
 110   }
 111
 112   return Status::NotFound();
 113 }
 114
 115 size_t FreeList::FindChunkPtrForSize(size_t size, bool non_null) const {
 116   size_t chunk_ptr = 0;
 117   for (chunk_ptr = 0; chunk_ptr < sizes_.size(); chunk_ptr++) {
 118     if (sizes_[chunk_ptr] >= size &&
 119         (!non_null || chunks_[chunk_ptr] != nullptr)) {
 120       break;
 121     }
 122   }
 123
 124   return chunk_ptr;
 125 }
 126
 127 }  // namespace pw::allocator