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 #include "common_components/heap/allocator/treap.h"
16
17 #include "common_components/heap/allocator/region_desc.h"
18
19 namespace common {
MergeInsertInternal(uint32_t idx,uint32_t num,bool refreshRegionDesc)20 bool Treap::MergeInsertInternal(uint32_t idx, uint32_t num, bool refreshRegionDesc)
21 {
22 // +-------------+ +--------------+
23 // | parent node | n--> | current node |
24 // | | | |
25 // pn ---> TreapNode* l; -------> | |
26 // | TreapNode* r; | | |
27 // +-------------+ +--------------+
28 // suppose current node is parent node's left child, then
29 // n points to the current node,
30 // pn points to the 'l' field in the parent node
31 TreapNode* current = root_; // root is current node
32 TreapNode** pCurrent = &root_; // pointer to the 'root' field in this tree
33 // stack of pn recording how to go from root to the current node
34 LocalDeque<TreapNode**> pnStack(sud_); // this uses another deque as container
35 uint32_t m = idx + num;
36 // this loop insert the new node (idx, num) at the proper place
37 do {
38 if (current == nullptr) {
39 current = new (nodeAllocator_.Allocate()) TreapNode(idx, num, refreshRegionDesc);
40 CTREE_ASSERT(current != nullptr, "fail to allocate a new node");
41 *pCurrent = current;
42 IncTotalCount(num);
43 break;
44 }
45 MergeResult res = MergeAt(*current, idx, num, refreshRegionDesc);
46 if (res == MergeResult::MERGE_SUCCESS) {
47 break;
48 } else if (UNLIKELY_CC(res == MergeResult::MERGE_ERROR)) {
49 return false;
50 }
51 // MergeResult::MERGE_MISS: (idx, num) cannot be connected to n
52 if (m < current->GetIndex()) {
53 // should insert the node into left subtree
54 pnStack.Push(pCurrent);
55 pCurrent = &(current->l);
56 current = current->l;
57 } else if (idx > current->GetIndex() + current->GetCount()) {
58 // should insert the node into right subtree
59 pnStack.Push(pCurrent);
60 pCurrent = &(current->r);
61 current = current->r;
62 } else {
63 // something clashes
64 CTREE_ASSERT(false, "merge insertion failed");
65 return false;
66 }
67 } while (true);
68
69 // this loop bubbles the inserted node up the tree to satisfy heap property
70 while (!pnStack.Empty()) {
71 pCurrent = pnStack.Top();
72 pnStack.Pop();
73 current = *pCurrent;
74 CTREE_ASSERT(current, "merge insertion bubbling failed case 1");
75 if (m < current->GetIndex()) {
76 // (idx, num) was inserted into n's left subtree, do rotate l, if needed
77 if (current->GetCount() < current->l->GetCount()) {
78 *pCurrent = RotateLeftChild(*current);
79 CTREE_CHECK_PARENT_AND_RCHILD(*pCurrent);
80 } else {
81 break;
82 }
83 } else if (idx > current->GetIndex() + current->GetCount()) {
84 // (idx, num) was inserted into n's right subtree, do rotate r, if needed
85 if (current->GetCount() < current->r->GetCount()) {
86 *pCurrent = RotateRightChild(*current);
87 CTREE_CHECK_PARENT_AND_LCHILD(*pCurrent);
88 } else {
89 break;
90 }
91 } else {
92 CTREE_ASSERT(false, "merge insertion bubbling failed: case 2");
93 return false;
94 }
95 }
96 return true;
97 }
98
99 #ifdef DEBUG_CARTESIAN_TREE
DumpTree(const char * msg) const100 void Treap::DumpTree(const char* msg) const
101 {
102 if (Empty()) {
103 return;
104 }
105
106 VLOG(DEBUG, "dump %s %p in graphviz .dot:", msg, this);
107 VLOG(DEBUG, "digraph tree%p {", this);
108 Treap::Iterator it(*const_cast<Treap*>(this));
109 auto node = it.Next();
110 while (node != nullptr) {
111 VLOG(DEBUG, "c-tree %p N%p [label=\"%p:%u+%u=%u\"]", this, node, node, node->GetIndex(),
112 node->GetCount(), node->GetIndex() + node->GetCount());
113
114 if (node->l != nullptr) {
115 VLOG(DEBUG, "c-tree %p N%p -> N%p", this, node, node->l);
116 }
117
118 VLOG(DEBUG, "c-tree %p N%p -> D%p [style=invis]", this, node, node);
119 VLOG(DEBUG, "c-tree %p D%p [width=0, style=invis]", this, node);
120
121 if (node->r != nullptr) {
122 VLOG(DEBUG, "c-tree %p N%p -> N%p", this, node, node->r);
123 }
124
125 node = it.Next();
126 }
127 VLOG(DEBUG, "}");
128 }
129 #endif
130
RefreshFreeRegionDesc()131 void Treap::TreapNode::RefreshFreeRegionDesc()
132 {
133 uint32_t idx = GetIndex();
134 uint32_t cnt = GetCount();
135 RegionDesc::InitFreeRegion(idx, cnt);
136 }
137
ReleaseMemory()138 void Treap::TreapNode::ReleaseMemory()
139 {
140 uint32_t idx = GetIndex();
141 uint32_t cnt = GetCount();
142 RegionDesc::ReleaseUnits(idx, cnt);
143 }
144 } // namespace common
145