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
15 #include "pw_allocator/bucket/fast_sorted.h"
16
17 #include <cstddef>
18 #include <cstdint>
19
20 #include "pw_allocator/block/detailed_block.h"
21 #include "pw_allocator/bucket/testing.h"
22 #include "pw_unit_test/framework.h"
23
24 namespace {
25
26 using ::pw::allocator::FastSortedBucket;
27 using ::pw::allocator::GenericFastSortedItem;
28 using ::pw::allocator::test::BucketTest;
29
30 using BlockType =
31 ::pw::allocator::DetailedBlock<uint32_t, GenericFastSortedItem>;
32 using FastSortedBucketTest = BucketTest<FastSortedBucket<BlockType>>;
33
TEST_F(FastSortedBucketTest,SetsAndGetsMaxInnerSize)34 TEST_F(FastSortedBucketTest, SetsAndGetsMaxInnerSize) {
35 SetsAndGetsMaxInnerSize();
36 }
37
TEST_F(FastSortedBucketTest,AddsAndRemovesBlocks)38 TEST_F(FastSortedBucketTest, AddsAndRemovesBlocks) { AddsAndRemovesBlocks(); }
39
TEST_F(FastSortedBucketTest,FailsToAddWhenBlockIsTooSmall)40 TEST_F(FastSortedBucketTest, FailsToAddWhenBlockIsTooSmall) {
41 FailsToAddWhenBlockIsTooSmall();
42 }
43
TEST_F(FastSortedBucketTest,FailsToRemoveBlockWhenNotFound)44 TEST_F(FastSortedBucketTest, FailsToRemoveBlockWhenNotFound) {
45 FailsToRemoveBlockWhenNotFound();
46 }
47
TEST_F(FastSortedBucketTest,RemovesUnspecifiedBlock)48 TEST_F(FastSortedBucketTest, RemovesUnspecifiedBlock) {
49 RemovesUnspecifiedBlock();
50 }
51
TEST_F(FastSortedBucketTest,RemovesByLayout)52 TEST_F(FastSortedBucketTest, RemovesByLayout) { RemovesByLayout(); }
53
TEST_F(FastSortedBucketTest,FailsToRemoveByExcessiveSize)54 TEST_F(FastSortedBucketTest, FailsToRemoveByExcessiveSize) {
55 FailsToRemoveByExcessiveSize();
56 }
57
TEST_F(FastSortedBucketTest,RemovesBlocksInOrderOfIncreasingSize)58 TEST_F(FastSortedBucketTest, RemovesBlocksInOrderOfIncreasingSize) {
59 FastSortedBucket<BlockType>& bucket = this->bucket();
60
61 BlockType& block1 = CreateBlock(kLayout1);
62 BlockType& block2 = CreateBlock(kLayout2);
63 BlockType& block3 = CreateBlock(kLayout3);
64
65 // Added out of order.
66 EXPECT_TRUE(bucket.Add(block2));
67 EXPECT_TRUE(bucket.Add(block3));
68 EXPECT_TRUE(bucket.Add(block1));
69
70 // Removed in order.
71 EXPECT_EQ(bucket.RemoveAny(), &block1);
72 EXPECT_EQ(bucket.RemoveAny(), &block2);
73 EXPECT_EQ(bucket.RemoveAny(), &block3);
74 EXPECT_TRUE(bucket.empty());
75 }
76
77 using ::pw::allocator::ReverseFastSortedBucket;
78
79 using ReverseFastSortedBucketTest =
80 BucketTest<ReverseFastSortedBucket<BlockType>>;
81
TEST_F(ReverseFastSortedBucketTest,RemovesByLayout)82 TEST_F(ReverseFastSortedBucketTest, RemovesByLayout) { RemovesByLayout(); }
83
TEST_F(ReverseFastSortedBucketTest,RemovesBlocksInOrderOfDecreasingSize)84 TEST_F(ReverseFastSortedBucketTest, RemovesBlocksInOrderOfDecreasingSize) {
85 ReverseFastSortedBucket<BlockType>& bucket = this->bucket();
86
87 BlockType& block1 = CreateBlock(kLayout1);
88 BlockType& block2 = CreateBlock(kLayout2);
89 BlockType& block3 = CreateBlock(kLayout3);
90
91 // Added out of order.
92 EXPECT_TRUE(bucket.Add(block2));
93 EXPECT_TRUE(bucket.Add(block3));
94 EXPECT_TRUE(bucket.Add(block1));
95
96 // Removed in order.
97 EXPECT_EQ(bucket.RemoveAny(), &block3);
98 EXPECT_EQ(bucket.RemoveAny(), &block2);
99 EXPECT_EQ(bucket.RemoveAny(), &block1);
100 EXPECT_TRUE(bucket.empty());
101 }
102
103 } // namespace
104