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/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::ForwardSortedBucket;
27 using ::pw::allocator::SortedItem;
28 using ::pw::allocator::test::BucketTest;
29
30 using BlockType = ::pw::allocator::DetailedBlock<uint32_t, SortedItem>;
31 using ForwardSortedBucketTest = BucketTest<ForwardSortedBucket<BlockType>>;
32
TEST_F(ForwardSortedBucketTest,SetsAndGetsMaxInnerSize)33 TEST_F(ForwardSortedBucketTest, SetsAndGetsMaxInnerSize) {
34 SetsAndGetsMaxInnerSize();
35 }
36
TEST_F(ForwardSortedBucketTest,AddsAndRemovesBlocks)37 TEST_F(ForwardSortedBucketTest, AddsAndRemovesBlocks) {
38 AddsAndRemovesBlocks();
39 }
40
TEST_F(ForwardSortedBucketTest,FailsToAddWhenBlockIsTooSmall)41 TEST_F(ForwardSortedBucketTest, FailsToAddWhenBlockIsTooSmall) {
42 FailsToAddWhenBlockIsTooSmall();
43 }
44
TEST_F(ForwardSortedBucketTest,FailsToRemoveBlockWhenNotFound)45 TEST_F(ForwardSortedBucketTest, FailsToRemoveBlockWhenNotFound) {
46 FailsToRemoveBlockWhenNotFound();
47 }
48
TEST_F(ForwardSortedBucketTest,RemovesUnspecifiedBlock)49 TEST_F(ForwardSortedBucketTest, RemovesUnspecifiedBlock) {
50 RemovesUnspecifiedBlock();
51 }
52
TEST_F(ForwardSortedBucketTest,RemovesByLayout)53 TEST_F(ForwardSortedBucketTest, RemovesByLayout) { RemovesByLayout(); }
54
TEST_F(ForwardSortedBucketTest,FailsToRemoveByExcessiveSize)55 TEST_F(ForwardSortedBucketTest, FailsToRemoveByExcessiveSize) {
56 FailsToRemoveByExcessiveSize();
57 }
58
TEST_F(ForwardSortedBucketTest,RemovesBlocksInOrderOfIncreasingSize)59 TEST_F(ForwardSortedBucketTest, RemovesBlocksInOrderOfIncreasingSize) {
60 ForwardSortedBucket<BlockType>& bucket = this->bucket();
61
62 BlockType& block1 = CreateBlock(kLayout1);
63 BlockType& block2 = CreateBlock(kLayout2);
64 BlockType& block3 = CreateBlock(kLayout3);
65
66 // Added out of order.
67 EXPECT_TRUE(bucket.Add(block2));
68 EXPECT_TRUE(bucket.Add(block3));
69 EXPECT_TRUE(bucket.Add(block1));
70
71 // Removed in order.
72 EXPECT_EQ(bucket.RemoveAny(), &block1);
73 EXPECT_EQ(bucket.RemoveAny(), &block2);
74 EXPECT_EQ(bucket.RemoveAny(), &block3);
75 EXPECT_TRUE(bucket.empty());
76 }
77
78 using ::pw::allocator::ReverseSortedBucket;
79
80 using ReverseSortedBucketTest = BucketTest<ReverseSortedBucket<BlockType>>;
81
TEST_F(ReverseSortedBucketTest,RemovesByLayout)82 TEST_F(ReverseSortedBucketTest, RemovesByLayout) { RemovesByLayout(); }
83
TEST_F(ReverseSortedBucketTest,RemovesBlocksInOrderOfDecreasingSize)84 TEST_F(ReverseSortedBucketTest, RemovesBlocksInOrderOfDecreasingSize) {
85 ReverseSortedBucket<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