1 /*
2 * Copyright (c) 2025 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://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,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include <cstdlib>
17
18 #include "common_components/heap/allocator/treap.h"
19 #include "common_components/heap/allocator/region_desc.h"
20 #include "common_components/tests/test_helper.h"
21
22 using namespace common;
23
24 class TreapTest : public common::test::BaseTestWithScope {
25 protected:
SetUp()26 void SetUp() override
27 {
28 const size_t nUnit = 512;
29 const size_t initialSize = 1024;
30
31 const size_t unitInfoSize = sizeof(RegionDesc);
32 const size_t heapSize = nUnit * RegionDesc::UNIT_SIZE;
33
34 totalMemoryBuffer_ = reinterpret_cast<char*>(malloc(nUnit * unitInfoSize + heapSize));
35 ASSERT_NE(totalMemoryBuffer_, nullptr);
36 unitInfoBuffer_ = totalMemoryBuffer_;
37
38 heapStartAddress_ = reinterpret_cast<uintptr_t>(totalMemoryBuffer_ + nUnit * unitInfoSize);
39
40 RegionDesc::Initialize(nUnit, reinterpret_cast<uintptr_t>(unitInfoBuffer_),
41 heapStartAddress_);
42
43 treap_.Init(initialSize);
44 }
45
TearDown()46 void TearDown() override
47 {
48 treap_.Fini();
49 free(totalMemoryBuffer_);
50 totalMemoryBuffer_ = nullptr;
51 heapStartAddress_ = 0;
52 unitInfoBuffer_ = nullptr;
53 }
54
55 uintptr_t heapStartAddress_ = 0;
56 char* unitInfoBuffer_ = nullptr;
57 char* totalMemoryBuffer_ = nullptr;
58 Treap treap_;
59 };
60
61
HWTEST_F_L0(TreapTest,InitAndEmpty)62 HWTEST_F_L0(TreapTest, InitAndEmpty) {
63 EXPECT_TRUE(treap_.Empty());
64 EXPECT_EQ(treap_.GetTotalCount(), 0u);
65 }
66
67
HWTEST_F_L0(TreapTest,InsertSingleNode)68 HWTEST_F_L0(TreapTest, InsertSingleNode) {
69 bool result = treap_.MergeInsert(100, 10, true);
70 EXPECT_TRUE(result);
71 EXPECT_FALSE(treap_.Empty());
72 EXPECT_EQ(treap_.GetTotalCount(), 10u);
73
74 const Treap::TreapNode* root = treap_.RootNode();
75 ASSERT_NE(root, nullptr);
76 EXPECT_EQ(root->GetIndex(), 100u);
77 EXPECT_EQ(root->GetCount(), 10u);
78 }
79
80
HWTEST_F_L0(TreapTest,MergeInsertAdjacentNodes)81 HWTEST_F_L0(TreapTest, MergeInsertAdjacentNodes) {
82 treap_.MergeInsert(100, 10, true);
83
84 bool result = treap_.MergeInsert(110, 5, true);
85 EXPECT_TRUE(result);
86 EXPECT_EQ(treap_.GetTotalCount(), 15u);
87
88 const Treap::TreapNode* root = treap_.RootNode();
89 ASSERT_NE(root, nullptr);
90 EXPECT_EQ(root->GetIndex(), 100u);
91 EXPECT_EQ(root->GetCount(), 15u);
92 }
93
94
HWTEST_F_L0(TreapTest,TakeUnitsFromTree)95 HWTEST_F_L0(TreapTest, TakeUnitsFromTree) {
96 treap_.MergeInsert(200, 20, true);
97
98 uint32_t idx = 0;
99 bool result = treap_.TakeUnits(5, idx, true);
100 EXPECT_TRUE(result);
101 EXPECT_EQ(idx, 200u);
102
103 const Treap::TreapNode* root = treap_.RootNode();
104 ASSERT_NE(root, nullptr);
105 EXPECT_EQ(root->GetIndex(), 205u);
106 EXPECT_EQ(root->GetCount(), 15u);
107 EXPECT_EQ(treap_.GetTotalCount(), 15u);
108 }
109
110
HWTEST_F_L0(TreapTest,TakeUnitsFailOnSmallNode)111 HWTEST_F_L0(TreapTest, TakeUnitsFailOnSmallNode) {
112 treap_.MergeInsert(300, 3, true);
113
114 uint32_t idx = 0;
115 bool result = treap_.TakeUnits(5, idx, true);
116 EXPECT_FALSE(result);
117 }
118
119
HWTEST_F_L0(TreapTest,EmptyTreeTakeFails)120 HWTEST_F_L0(TreapTest, EmptyTreeTakeFails) {
121 uint32_t idx = 0;
122 bool result = treap_.TakeUnits(5, idx, true);
123 EXPECT_FALSE(result);
124 }