| // 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" |
| |
| #include "gtest/gtest.h" |
| #include "pw_span/span.h" |
| #include "pw_status/status.h" |
| |
| using std::byte; |
| |
| namespace pw::allocator { |
| |
| static const size_t SIZE = 8; |
| static const std::array<size_t, SIZE> example_sizes = { |
| 64, 128, 256, 512, 1024, 2048, 4096, 8192}; |
| |
| TEST(FreeList, EmptyListHasNoMembers) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| |
| auto item = list.FindChunk(4); |
| EXPECT_EQ(item.size(), static_cast<size_t>(0)); |
| item = list.FindChunk(128); |
| EXPECT_EQ(item.size(), static_cast<size_t>(0)); |
| } |
| |
| TEST(FreeList, CanRetrieveAddedMember) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN = 512; |
| |
| byte data[kN] = {std::byte(0)}; |
| |
| auto status = list.AddChunk(pw::span(data, kN)); |
| EXPECT_EQ(status, Status::OK); |
| |
| auto item = list.FindChunk(kN); |
| EXPECT_EQ(item.size(), kN); |
| EXPECT_EQ(item.data(), data); |
| } |
| |
| TEST(FreeList, CanRetrieveAddedMemberForSmallerSize) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN = 512; |
| |
| byte data[kN] = {std::byte(0)}; |
| |
| list.AddChunk(pw::span(data, kN)); |
| auto item = list.FindChunk(kN / 2); |
| EXPECT_EQ(item.size(), kN); |
| EXPECT_EQ(item.data(), data); |
| } |
| |
| TEST(FreeList, CanRemoveItem) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN = 512; |
| |
| byte data[kN] = {std::byte(0)}; |
| |
| list.AddChunk(pw::span(data, kN)); |
| auto status = list.RemoveChunk(pw::span(data, kN)); |
| EXPECT_EQ(status, Status::OK); |
| |
| auto item = list.FindChunk(kN); |
| EXPECT_EQ(item.size(), static_cast<size_t>(0)); |
| } |
| |
| TEST(FreeList, FindReturnsSmallestChunk) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN1 = 512; |
| constexpr size_t kN2 = 1024; |
| |
| byte data1[kN1] = {std::byte(0)}; |
| byte data2[kN2] = {std::byte(0)}; |
| |
| list.AddChunk(pw::span(data1, kN1)); |
| list.AddChunk(pw::span(data2, kN2)); |
| |
| auto chunk = list.FindChunk(kN1 / 2); |
| EXPECT_EQ(chunk.size(), kN1); |
| EXPECT_EQ(chunk.data(), data1); |
| |
| chunk = list.FindChunk(kN1); |
| EXPECT_EQ(chunk.size(), kN1); |
| EXPECT_EQ(chunk.data(), data1); |
| |
| chunk = list.FindChunk(kN1 + 1); |
| EXPECT_EQ(chunk.size(), kN2); |
| EXPECT_EQ(chunk.data(), data2); |
| } |
| |
| TEST(FreeList, FindReturnsCorrectChunkInSameBucket) { |
| // If we have two values in the same bucket, ensure that the allocation will |
| // pick an appropriately sized one. |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN1 = 512; |
| constexpr size_t kN2 = 257; |
| |
| byte data1[kN1] = {std::byte(0)}; |
| byte data2[kN2] = {std::byte(0)}; |
| |
| // List should now be 257 -> 512 -> NULL |
| list.AddChunk(pw::span(data1, kN1)); |
| list.AddChunk(pw::span(data2, kN2)); |
| |
| auto chunk = list.FindChunk(kN2 + 1); |
| EXPECT_EQ(chunk.size(), kN1); |
| } |
| |
| TEST(FreeList, FindCanMoveUpThroughBuckets) { |
| // Ensure that finding a chunk will move up through buckets if no appropriate |
| // chunks were found in a given bucket |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN1 = 257; |
| constexpr size_t kN2 = 513; |
| |
| byte data1[kN1] = {std::byte(0)}; |
| byte data2[kN2] = {std::byte(0)}; |
| |
| // List should now be: |
| // bkt[3] (257 bytes up to 512 bytes) -> 257 -> NULL |
| // bkt[4] (513 bytes up to 1024 bytes) -> 513 -> NULL |
| list.AddChunk(pw::span(data1, kN1)); |
| list.AddChunk(pw::span(data2, kN2)); |
| |
| // Request a 300 byte chunk. This should return the 513 byte one |
| auto chunk = list.FindChunk(kN1 + 1); |
| EXPECT_EQ(chunk.size(), kN2); |
| } |
| |
| TEST(FreeList, RemoveUnknownChunkReturnsNotFound) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN = 512; |
| |
| byte data[kN] = {std::byte(0)}; |
| byte data2[kN] = {std::byte(0)}; |
| |
| list.AddChunk(pw::span(data, kN)); |
| auto status = list.RemoveChunk(pw::span(data2, kN)); |
| EXPECT_EQ(status, Status::NOT_FOUND); |
| } |
| |
| TEST(FreeList, CanStoreMultipleChunksPerBucket) { |
| FreeListBuffer<SIZE> list(example_sizes); |
| constexpr size_t kN = 512; |
| |
| byte data1[kN] = {std::byte(0)}; |
| byte data2[kN] = {std::byte(0)}; |
| |
| list.AddChunk(pw::span(data1, kN)); |
| list.AddChunk(pw::span(data2, kN)); |
| |
| auto chunk1 = list.FindChunk(kN); |
| list.RemoveChunk(chunk1); |
| auto chunk2 = list.FindChunk(kN); |
| list.RemoveChunk(chunk2); |
| |
| // Ordering of the chunks doesn't matter |
| EXPECT_TRUE(chunk1.data() != chunk2.data()); |
| EXPECT_TRUE(chunk1.data() == data1 || chunk1.data() == data2); |
| EXPECT_TRUE(chunk2.data() == data1 || chunk2.data() == data2); |
| } |
| |
| } // namespace pw::allocator |