1 /*
2 * Copyright (c) 2022 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 "ecmascript/tagged_node.h"
17
18 #include "ecmascript/tagged_hash_array.h"
19
20 namespace panda::ecmascript {
Treeing(JSThread * thread,const JSHandle<LinkedNode> & head)21 JSHandle<RBTreeNode> LinkedNode::Treeing(JSThread *thread, const JSHandle<LinkedNode> &head)
22 {
23 JSMutableHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
24 JSMutableHandle<LinkedNode> next(thread, head);
25 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
26 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
27 while (!next.GetTaggedValue().IsHole()) {
28 key.Update(next->GetKey(thread));
29 value.Update(next->GetValue(thread));
30 rootNode.Update(RBTreeNode::Set(thread, rootNode, next->GetHash(thread).GetInt(), key, value));
31 rootNode->SetIsRed(false);
32 next.Update(next->GetNext(thread));
33 }
34 return rootNode;
35 }
36
InitRBTreeNode(JSThread * thread,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value,int count)37 void RBTreeNode::InitRBTreeNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key,
38 JSHandle<JSTaggedValue> value, int count)
39 {
40 InitTaggedNode(thread, hash, key, value);
41 SetLeft(thread, JSTaggedValue::Hole());
42 SetRight(thread, JSTaggedValue::Hole());
43 SetIsRed(true);
44 SetCount(count);
45 }
46
47 // number of node in subtree rooted at treeNode; 0 if treeNode is Hole
Count(JSTaggedValue nodeValue)48 uint32_t RBTreeNode::Count(JSTaggedValue nodeValue)
49 {
50 if (nodeValue.IsHole()) {
51 return 0;
52 }
53 return RBTreeNode::Cast(nodeValue.GetTaggedObject())->GetCount();
54 }
55
InOrderTraverse(JSThread * thread,const JSHandle<RBTreeNode> & treeNode,JSHandle<LinkedNode> & head,JSHandle<LinkedNode> & tail)56 void RBTreeNode::InOrderTraverse(JSThread *thread, const JSHandle<RBTreeNode> &treeNode,
57 JSHandle<LinkedNode> &head, JSHandle<LinkedNode> &tail)
58 {
59 if (!treeNode.GetTaggedValue().IsHole()) {
60 JSHandle<RBTreeNode> leftChild = JSHandle<RBTreeNode>(thread, treeNode->GetLeft(thread));
61 InOrderTraverse(thread, leftChild, head, tail);
62 JSHandle<LinkedNode> linkedNode = TaggedHashArray::CreateLinkedNodeFrom(thread, treeNode);
63 if (tail.GetTaggedValue().IsHole()) {
64 head = linkedNode;
65 } else {
66 tail->SetNext(thread, linkedNode.GetTaggedValue());
67 }
68 tail = linkedNode;
69 JSHandle<RBTreeNode> rightChild(thread, treeNode->GetRight(thread));
70 InOrderTraverse(thread, rightChild, head, tail);
71 }
72 }
73
Detreeing(JSThread * thread,const JSHandle<RBTreeNode> & root)74 JSHandle<LinkedNode> RBTreeNode::Detreeing(JSThread *thread, const JSHandle<RBTreeNode> &root)
75 {
76 JSHandle<LinkedNode> head(thread, JSTaggedValue::Hole());
77 JSHandle<LinkedNode> tail(thread, JSTaggedValue::Hole());
78
79 InOrderTraverse(thread, root, head, tail);
80
81 return head;
82 }
83
InOrderTraverse(JSThread * thread,const JSHandle<RBTreeNode> & treeNode,int bit,LinkedNodeStruct & nodeStruct)84 void RBTreeNode::InOrderTraverse(JSThread *thread, const JSHandle<RBTreeNode> &treeNode, int bit,
85 LinkedNodeStruct &nodeStruct)
86 {
87 if (!treeNode.GetTaggedValue().IsHole()) {
88 JSHandle<RBTreeNode> leftChild(thread, treeNode->GetLeft(thread));
89 InOrderTraverse(thread, leftChild, bit, nodeStruct);
90
91 JSHandle<LinkedNode> linkedNode = TaggedHashArray::CreateLinkedNodeFrom(thread, treeNode);
92 // the elements from each bin must either stay at same index,
93 // or move with a power of two offset in the new table
94 if ((static_cast<uint32_t>(linkedNode->GetHash(thread).GetInt()) & static_cast<uint32_t>(bit)) == 0) {
95 if (nodeStruct.lowerTail.GetTaggedValue().IsHole()) {
96 nodeStruct.lowerHead = linkedNode;
97 } else {
98 nodeStruct.lowerTail->SetNext(thread, linkedNode.GetTaggedValue());
99 }
100 nodeStruct.lowerTail = linkedNode;
101 } else {
102 if (nodeStruct.higherTail.GetTaggedValue().IsHole()) {
103 nodeStruct.higherHead = linkedNode;
104 } else {
105 nodeStruct.higherTail->SetNext(thread, linkedNode.GetTaggedValue());
106 }
107 nodeStruct.higherTail = linkedNode;
108 }
109
110 JSHandle<RBTreeNode> rightChild(thread, treeNode->GetRight(thread));
111 InOrderTraverse(thread, rightChild, bit, nodeStruct);
112 }
113 }
114
Divide(JSThread * thread,JSHandle<TaggedHashArray> table,JSHandle<JSTaggedValue> nodeVa,int index,int bit)115 void RBTreeNode::Divide(JSThread *thread, JSHandle<TaggedHashArray> table,
116 JSHandle<JSTaggedValue> nodeVa, int index, int bit)
117 {
118 JSHandle<RBTreeNode> self = JSHandle<RBTreeNode>::Cast(nodeVa);
119 LinkedNodeStruct nodeStruct {JSHandle<LinkedNode>(thread, JSTaggedValue::Hole()),
120 JSHandle<LinkedNode>(thread, JSTaggedValue::Hole()),
121 JSHandle<LinkedNode>(thread, JSTaggedValue::Hole()),
122 JSHandle<LinkedNode>(thread, JSTaggedValue::Hole())};
123
124 InOrderTraverse(thread, self, bit, nodeStruct);
125
126 uint32_t loCount = 0;
127 uint32_t hiCount = 0;
128 JSMutableHandle<LinkedNode> lowerHead(thread, nodeStruct.lowerHead);
129 while (!lowerHead.GetTaggedValue().IsHole()) {
130 loCount++;
131 lowerHead.Update(lowerHead->GetNext(thread));
132 }
133 JSMutableHandle<LinkedNode> higherHead(thread, nodeStruct.higherHead);
134 while (!higherHead.GetTaggedValue().IsHole()) {
135 loCount++;
136 higherHead.Update(higherHead->GetNext(thread));
137 }
138
139 if (!nodeStruct.lowerHead.GetTaggedValue().IsHole()) {
140 if (loCount >= TaggedHashArray::TREEIFY_THRESHOLD) {
141 JSHandle<RBTreeNode> loRoot = LinkedNode::Treeing(thread, nodeStruct.lowerHead);
142 table->Set(thread, index, loRoot);
143 } else {
144 table->Set(thread, index, nodeStruct.lowerHead);
145 }
146 }
147 if (!nodeStruct.higherHead.GetTaggedValue().IsHole()) {
148 if (hiCount >= TaggedHashArray::TREEIFY_THRESHOLD) {
149 JSHandle<RBTreeNode> hiRoot = LinkedNode::Treeing(thread, nodeStruct.higherHead);
150 table->Set(thread, index + bit, hiRoot);
151 } else {
152 table->Set(thread, index + bit, nodeStruct.higherHead);
153 }
154 }
155 }
156
Compare(JSThread * thread,int hash1,JSTaggedValue key1,int hash2,JSTaggedValue key2)157 int RBTreeNode::Compare(JSThread *thread, int hash1, JSTaggedValue key1, int hash2, JSTaggedValue key2)
158 {
159 ASSERT(!key1.IsHole() && !key2.IsHole());
160 if (JSTaggedValue::SameValue(thread, key1, key2)) {
161 return 0;
162 }
163 if (UNLIKELY(hash1 == hash2)) {
164 JSHandle<JSTaggedValue> keyHandle1 = JSHandle<JSTaggedValue>(thread, key1);
165 JSHandle<JSTaggedValue> keyHandle2 = JSHandle<JSTaggedValue>(thread, key2);
166 return JSTaggedValue::Less(thread, keyHandle1, keyHandle2) ? -1 : 1;
167 }
168 return hash1 < hash2 ? -1 : 1;
169 }
170
IsRed(JSTaggedValue treeNodeValue)171 bool RBTreeNode::IsRed(JSTaggedValue treeNodeValue)
172 {
173 if (treeNodeValue.IsHole()) {
174 return false;
175 }
176 RBTreeNode *treeNode = RBTreeNode::Cast(treeNodeValue.GetTaggedObject());
177 return treeNode->GetIsRed();
178 }
179
180 // insert the key-value pair in the subtree rooted at treeNode
Set(JSThread * thread,JSHandle<RBTreeNode> treeNode,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value)181 JSHandle<RBTreeNode> RBTreeNode::Set(JSThread *thread, JSHandle<RBTreeNode> treeNode, int hash,
182 JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value)
183 {
184 if (treeNode.GetTaggedValue().IsHole()) {
185 treeNode = TaggedHashArray::NewTreeNode(thread, hash, key, value);
186 return treeNode;
187 }
188 JSHandle<JSTaggedValue> treeNodeKey(thread, treeNode->GetKey(thread));
189 int cmp =
190 Compare(thread, hash, key.GetTaggedValue(), treeNode->GetHash(thread).GetInt(), treeNodeKey.GetTaggedValue());
191 JSHandle<RBTreeNode> leftChild(thread, treeNode->GetLeft(thread));
192 JSHandle<RBTreeNode> rightChild(thread, treeNode->GetRight(thread));
193 if (cmp < 0) {
194 JSHandle<RBTreeNode> left = Set(thread, leftChild, hash, key, value);
195 treeNode->SetLeft(thread, left);
196 } else if (cmp > 0) {
197 JSHandle<RBTreeNode> right = Set(thread, rightChild, hash, key, value);
198 treeNode->SetRight(thread, right);
199 } else {
200 treeNode->SetValue(thread, value);
201 }
202
203 if (IsRed(treeNode->GetRight(thread)) && !IsRed(treeNode->GetLeft(thread))) {
204 treeNode = JSHandle<RBTreeNode>(thread, treeNode->RotateLeft(thread));
205 }
206 JSTaggedValue leftChildVa = treeNode->GetLeft(thread);
207 if (!leftChildVa.IsHole()) {
208 leftChild = JSHandle<RBTreeNode>(thread, leftChildVa);
209 if (IsRed(treeNode->GetLeft(thread)) && IsRed(leftChild->GetLeft(thread))) {
210 treeNode = JSHandle<RBTreeNode>(thread, treeNode->RotateRight(thread));
211 }
212 }
213 if (IsRed(treeNode->GetLeft(thread)) && IsRed(treeNode->GetRight(thread))) {
214 treeNode->FlipColors(thread);
215 }
216
217 // 1 : root count
218 uint32_t count = Count(treeNode->GetLeft(thread)) + Count(treeNode->GetRight(thread)) + 1;
219 treeNode->SetCount(count);
220
221 return treeNode;
222 }
223
224 // make a right-leaning link lean to the left
RotateLeft(JSThread * thread)225 RBTreeNode *RBTreeNode::RotateLeft(JSThread *thread)
226 {
227 ASSERT(!JSTaggedValue(this).IsHole() && IsRed(GetRight(thread)));
228 RBTreeNode *temp = RBTreeNode::Cast(GetRight(thread).GetTaggedObject());
229 SetRight(thread, temp->GetLeft(thread));
230 temp->SetLeft(thread, JSTaggedValue(this));
231 RBTreeNode *tempLeft = RBTreeNode::Cast(temp->GetLeft(thread).GetTaggedObject());
232 temp->SetIsRed(tempLeft->GetIsRed());
233 tempLeft->SetIsRed(true);
234
235 temp->SetCount(GetCount());
236 // 1 : root count
237 uint32_t count = Count(GetLeft(thread)) + Count(GetRight(thread)) + 1;
238 SetCount(count);
239
240 return temp;
241 }
242
243 // make a left-leaning link lean to the right
RotateRight(JSThread * thread)244 RBTreeNode *RBTreeNode::RotateRight(JSThread *thread)
245 {
246 ASSERT(!JSTaggedValue(this).IsHole() && IsRed(GetLeft(thread)));
247 RBTreeNode *temp = RBTreeNode::Cast(GetLeft(thread).GetTaggedObject());
248 SetLeft(thread, temp->GetRight(thread));
249 temp->SetRight(thread, JSTaggedValue(this));
250 RBTreeNode *tempRight = RBTreeNode::Cast(temp->GetRight(thread).GetTaggedObject());
251 temp->SetIsRed(tempRight->GetIsRed());
252 tempRight->SetIsRed(true);
253
254 temp->SetCount(GetCount());
255 // 1 : root count
256 uint32_t count = Count(GetLeft(thread)) + Count(GetRight(thread)) + 1;
257 SetCount(count);
258
259 return temp;
260 }
261
262 // flip the colors of a node and its two children
FlipColors(JSThread * thread)263 void RBTreeNode::FlipColors(JSThread *thread)
264 {
265 SetIsRed(!GetIsRed());
266 RBTreeNode *leftChild = RBTreeNode::Cast(GetLeft(thread).GetTaggedObject());
267 leftChild->SetIsRed(!leftChild->GetIsRed());
268 RBTreeNode *rightChild = RBTreeNode::Cast(GetRight(thread).GetTaggedObject());
269 rightChild->SetIsRed(!rightChild->GetIsRed());
270 }
271
272 // restore red-black tree invariant
Balance(JSThread * thread,RBTreeNode * treeNode)273 JSTaggedValue RBTreeNode::Balance(JSThread *thread, RBTreeNode *treeNode)
274 {
275 if (IsRed(treeNode->GetRight(thread)) && !IsRed(treeNode->GetLeft(thread))) {
276 treeNode = treeNode->RotateLeft(thread);
277 }
278 JSTaggedValue leftValue = treeNode->GetLeft(thread);
279 if (!leftValue.IsHole()) {
280 RBTreeNode *leftChild = RBTreeNode::Cast(leftValue.GetTaggedObject());
281 if (IsRed(treeNode->GetLeft(thread)) && IsRed(leftChild->GetLeft(thread))) {
282 treeNode = treeNode->RotateRight(thread);
283 }
284 }
285 if (IsRed(treeNode->GetLeft(thread)) && IsRed(treeNode->GetRight(thread))) {
286 treeNode->FlipColors(thread);
287 }
288 // 1 : root count
289 uint32_t count = Count(treeNode->GetLeft(thread)) + Count(treeNode->GetRight(thread)) + 1;
290 treeNode->SetCount(count);
291
292 return JSTaggedValue(treeNode);
293 }
294
MoveRedLeft(JSThread * thread)295 RBTreeNode *RBTreeNode::MoveRedLeft(JSThread *thread)
296 {
297 RBTreeNode *treeNode = this;
298 treeNode->FlipColors(thread);
299 RBTreeNode *rightChild = RBTreeNode::Cast(treeNode->GetRight(thread).GetTaggedObject());
300 if (IsRed(rightChild->GetLeft(thread))) {
301 rightChild = rightChild->RotateRight(thread);
302 treeNode->SetRight(thread, JSTaggedValue(rightChild));
303 treeNode = treeNode->RotateLeft(thread);
304 treeNode->FlipColors(thread);
305 }
306
307 return treeNode;
308 }
309
MoveRedRight(JSThread * thread)310 RBTreeNode *RBTreeNode::MoveRedRight(JSThread *thread)
311 {
312 RBTreeNode *treeNode = this;
313 treeNode->FlipColors(thread);
314 RBTreeNode *leftChild = RBTreeNode::Cast(treeNode->GetLeft(thread).GetTaggedObject());
315 if (IsRed(leftChild->GetLeft(thread))) {
316 treeNode = treeNode->RotateRight(thread);
317 treeNode->FlipColors(thread);
318 }
319
320 return treeNode;
321 }
322
323 // delete the key-value pair with the minimum key rooted at treeNode
DeleteMin(JSThread * thread,RBTreeNode * treeNode)324 JSTaggedValue RBTreeNode::DeleteMin(JSThread *thread, RBTreeNode *treeNode)
325 {
326 if (treeNode->GetLeft(thread).IsHole()) {
327 return JSTaggedValue::Hole();
328 }
329 RBTreeNode *leftChild = RBTreeNode::Cast(treeNode->GetLeft(thread).GetTaggedObject());
330 if (!IsRed(treeNode->GetLeft(thread)) && !IsRed(leftChild->GetLeft(thread))) {
331 treeNode = treeNode->MoveRedLeft(thread);
332 leftChild = RBTreeNode::Cast(treeNode->GetLeft(thread).GetTaggedObject());
333 }
334
335 treeNode->SetLeft(thread, DeleteMin(thread, leftChild));
336 return Balance(thread, treeNode);
337 }
338
339 // delete the key-value pair with the given key rooted at treeNode
Delete(JSThread * thread,const JSTaggedValue & treeNodeVa,int hash,const JSTaggedValue & key,JSTaggedValue & oldValue)340 JSTaggedValue RBTreeNode::Delete(JSThread *thread, const JSTaggedValue &treeNodeVa, int hash,
341 const JSTaggedValue &key, JSTaggedValue &oldValue)
342 {
343 if (treeNodeVa.IsHole()) {
344 return JSTaggedValue::Hole();
345 }
346 RBTreeNode *treeNode = RBTreeNode::Cast(treeNodeVa.GetTaggedObject());
347 JSTaggedValue leftChildVa = treeNode->GetLeft(thread);
348 JSTaggedValue treeNodeKey = treeNode->GetKey(thread);
349 int cmp = Compare(thread, hash, key, treeNode->GetHash(thread).GetInt(), treeNodeKey);
350 if (cmp < 0) {
351 if (!leftChildVa.IsHole() &&
352 !IsRed(treeNode->GetLeft(thread)) &&
353 !IsRed(RBTreeNode::Cast(leftChildVa.GetTaggedObject())->GetLeft(thread))) {
354 treeNode = treeNode->MoveRedLeft(thread);
355 }
356 leftChildVa = treeNode->GetLeft(thread);
357 JSTaggedValue leftValue = Delete(thread, leftChildVa, hash, key, oldValue);
358 treeNode->SetLeft(thread, leftValue);
359 } else {
360 if (IsRed(treeNode->GetLeft(thread))) {
361 treeNode = treeNode->RotateRight(thread);
362 treeNodeKey = treeNode->GetKey(thread);
363 }
364 cmp = Compare(thread, hash, key, treeNode->GetHash(thread).GetInt(), treeNodeKey);
365 if (cmp == 0 && treeNode->GetRight(thread).IsHole()) {
366 oldValue = treeNode->GetValue(thread);
367 return JSTaggedValue::Hole();
368 }
369 JSTaggedValue rightChildVa = treeNode->GetRight(thread);
370 if (!rightChildVa.IsHole() &&
371 !IsRed(rightChildVa) && !IsRed(RBTreeNode::Cast(rightChildVa.GetTaggedObject())->GetLeft(thread))) {
372 treeNode = treeNode->MoveRedRight(thread);
373 treeNodeKey = treeNode->GetKey(thread);
374 }
375
376 cmp = Compare(thread, hash, key, treeNode->GetHash(thread).GetInt(), treeNodeKey);
377 rightChildVa = treeNode->GetRight(thread);
378 if (rightChildVa.IsHole()) {
379 return Balance(thread, treeNode);
380 }
381 RBTreeNode *rightChild = RBTreeNode::Cast(rightChildVa.GetTaggedObject());
382 if (cmp == 0) {
383 oldValue = treeNode->GetValue(thread);
384 RBTreeNode *minNode = rightChild->Min(thread);
385 treeNode->SetKey(thread, minNode->GetKey(thread));
386 treeNode->SetValue(thread, minNode->GetValue(thread));
387 treeNode->SetHash(thread, minNode->GetHash(thread));
388 treeNode->SetRight(thread, DeleteMin(thread, rightChild));
389 } else {
390 JSTaggedValue tmpValue = Delete(thread, rightChildVa, hash, key, oldValue);
391 treeNode->SetRight(thread, tmpValue);
392 }
393 }
394 return Balance(thread, treeNode);
395 }
396
397 // the smallest key in subtree rooted at treeNode; hole if no such key
Min(JSThread * thread)398 RBTreeNode *RBTreeNode::Min(JSThread *thread)
399 {
400 if (GetLeft(thread).IsHole()) {
401 return this;
402 } else {
403 return RBTreeNode::Cast(GetLeft(thread).GetTaggedObject())->Min(thread);
404 }
405 }
406
407 // node associated with the given key in subtree rooted at treeNode; null if no such key
GetTreeNode(JSThread * thread,JSHandle<JSTaggedValue> treeNodeVa,int hash,JSHandle<JSTaggedValue> key)408 JSTaggedValue RBTreeNode::GetTreeNode(JSThread *thread, JSHandle<JSTaggedValue> treeNodeVa,
409 int hash, JSHandle<JSTaggedValue> key)
410 {
411 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
412 JSMutableHandle<TaggedQueue> queue(thread, factory->NewTaggedQueue(0));
413 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, treeNodeVa)));
414 JSMutableHandle<RBTreeNode> root(thread, JSTaggedValue::Hole());
415 JSMutableHandle<JSTaggedValue> currentKey(thread, JSTaggedValue::Hole());
416 JSMutableHandle<JSTaggedValue> left(thread, JSTaggedValue::Hole());
417 JSMutableHandle<JSTaggedValue> right(thread, JSTaggedValue::Hole());
418 while (!queue->Empty(thread)) {
419 root.Update(queue->Pop(thread));
420 currentKey.Update(root->GetKey(thread));
421 if (root->GetHash(thread).GetInt() == hash &&
422 (!currentKey->IsHole() && JSTaggedValue::SameValue(thread, key, currentKey))) {
423 return root.GetTaggedValue();
424 }
425 if (!root->GetLeft(thread).IsHole()) {
426 left.Update(root->GetLeft(thread));
427 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, left)));
428 }
429 if (!root->GetRight(thread).IsHole()) {
430 right.Update(root->GetRight(thread));
431 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, right)));
432 }
433 }
434 return JSTaggedValue::Hole();
435 }
436 } // namespace panda::ecmascript
437