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());
29 value.Update(next->GetValue());
30 rootNode.Update(RBTreeNode::Set(thread, rootNode, next->GetHash().GetInt(), key, value));
31 rootNode->SetIsRed(thread, JSTaggedValue(false));
32 next.Update(next->GetNext());
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(thread, JSTaggedValue(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());
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());
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());
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().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());
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());
132 }
133 JSMutableHandle<LinkedNode> higherHead(thread, nodeStruct.higherHead);
134 while (!higherHead.GetTaggedValue().IsHole()) {
135 loCount++;
136 higherHead.Update(higherHead->GetNext());
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(int hash1,JSTaggedValue key1,int hash2,JSTaggedValue key2)157 int RBTreeNode::Compare(int hash1, JSTaggedValue key1, int hash2, JSTaggedValue key2)
158 {
159 ASSERT(!key1.IsHole() && !key2.IsHole());
160 if (JSTaggedValue::SameValue(key1, key2)) {
161 return 0;
162 }
163 if (hash1 < hash2) {
164 return -1;
165 } else {
166 return 1;
167 }
168 }
169
IsRed(JSTaggedValue treeNodeValue)170 bool RBTreeNode::IsRed(JSTaggedValue treeNodeValue)
171 {
172 if (treeNodeValue.IsHole()) {
173 return false;
174 }
175 RBTreeNode *treeNode = RBTreeNode::Cast(treeNodeValue.GetTaggedObject());
176 return treeNode->GetIsRed().ToBoolean();
177 }
178
179 // 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)180 JSHandle<RBTreeNode> RBTreeNode::Set(JSThread *thread, JSHandle<RBTreeNode> treeNode, int hash,
181 JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value)
182 {
183 if (treeNode.GetTaggedValue().IsHole()) {
184 treeNode = TaggedHashArray::NewTreeNode(thread, hash, key, value);
185 return treeNode;
186 }
187 JSHandle<JSTaggedValue> treeNodeKey(thread, treeNode->GetKey());
188 int cmp = Compare(hash, key.GetTaggedValue(), treeNode->GetHash().GetInt(), treeNodeKey.GetTaggedValue());
189 JSHandle<RBTreeNode> leftChild(thread, treeNode->GetLeft());
190 JSHandle<RBTreeNode> rightChild(thread, treeNode->GetRight());
191 if (cmp < 0) {
192 JSHandle<RBTreeNode> left = Set(thread, leftChild, hash, key, value);
193 treeNode->SetLeft(thread, left);
194 } else if (cmp > 0) {
195 JSHandle<RBTreeNode> right = Set(thread, rightChild, hash, key, value);
196 treeNode->SetRight(thread, right);
197 } else {
198 treeNode->SetValue(thread, value);
199 }
200
201 if (IsRed(treeNode->GetRight()) && !IsRed(treeNode->GetLeft())) {
202 treeNode = JSHandle<RBTreeNode>(thread, treeNode->RotateLeft(thread));
203 }
204 JSTaggedValue leftChildVa = treeNode->GetLeft();
205 if (!leftChildVa.IsHole()) {
206 leftChild = JSHandle<RBTreeNode>(thread, leftChildVa);
207 if (IsRed(treeNode->GetLeft()) && IsRed(leftChild->GetLeft())) {
208 treeNode = JSHandle<RBTreeNode>(thread, treeNode->RotateRight(thread));
209 }
210 }
211 if (IsRed(treeNode->GetLeft()) && IsRed(treeNode->GetRight())) {
212 treeNode->FlipColors(thread);
213 }
214
215 // 1 : root count
216 uint32_t count = Count(treeNode->GetLeft()) + Count(treeNode->GetRight()) + 1;
217 treeNode->SetCount(count);
218
219 return treeNode;
220 }
221
222 // make a right-leaning link lean to the left
RotateLeft(JSThread * thread)223 RBTreeNode *RBTreeNode::RotateLeft(JSThread *thread)
224 {
225 ASSERT(!JSTaggedValue(this).IsHole() && IsRed(GetRight()));
226 RBTreeNode *temp = RBTreeNode::Cast(GetRight().GetTaggedObject());
227 SetRight(thread, temp->GetLeft());
228 temp->SetLeft(thread, JSTaggedValue(this));
229 RBTreeNode *tempLeft = RBTreeNode::Cast(temp->GetLeft().GetTaggedObject());
230 temp->SetIsRed(thread, tempLeft->GetIsRed());
231 tempLeft->SetIsRed(thread, JSTaggedValue(true));
232
233 temp->SetCount(GetCount());
234 // 1 : root count
235 uint32_t count = Count(GetLeft()) + Count(GetRight()) + 1;
236 SetCount(count);
237
238 return temp;
239 }
240
241 // make a left-leaning link lean to the right
RotateRight(JSThread * thread)242 RBTreeNode *RBTreeNode::RotateRight(JSThread *thread)
243 {
244 ASSERT(!JSTaggedValue(this).IsHole() && IsRed(GetLeft()));
245 RBTreeNode *temp = RBTreeNode::Cast(GetLeft().GetTaggedObject());
246 SetLeft(thread, temp->GetRight());
247 temp->SetRight(thread, JSTaggedValue(this));
248 RBTreeNode *tempRight = RBTreeNode::Cast(temp->GetRight().GetTaggedObject());
249 temp->SetIsRed(thread, tempRight->GetIsRed());
250 tempRight->SetIsRed(thread, JSTaggedValue(true));
251
252 temp->SetCount(GetCount());
253 // 1 : root count
254 uint32_t count = Count(GetLeft()) + Count(GetRight()) + 1;
255 SetCount(count);
256
257 return temp;
258 }
259
260 // flip the colors of a node and its two children
FlipColors(JSThread * thread)261 void RBTreeNode::FlipColors(JSThread *thread)
262 {
263 SetIsRed(thread, JSTaggedValue(!GetIsRed().ToBoolean()));
264 RBTreeNode *leftChild = RBTreeNode::Cast(GetLeft().GetTaggedObject());
265 leftChild->SetIsRed(thread, JSTaggedValue(!leftChild->GetIsRed().ToBoolean()));
266 RBTreeNode *rightChild = RBTreeNode::Cast(GetRight().GetTaggedObject());
267 rightChild->SetIsRed(thread, JSTaggedValue(!rightChild->GetIsRed().ToBoolean()));
268 }
269
270 // restore red-black tree invariant
Balance(JSThread * thread,RBTreeNode * treeNode)271 JSTaggedValue RBTreeNode::Balance(JSThread *thread, RBTreeNode *treeNode)
272 {
273 if (IsRed(treeNode->GetRight()) && !IsRed(treeNode->GetLeft())) {
274 treeNode = treeNode->RotateLeft(thread);
275 }
276 JSTaggedValue leftValue = treeNode->GetLeft();
277 if (!leftValue.IsHole()) {
278 RBTreeNode *leftChild = RBTreeNode::Cast(leftValue.GetTaggedObject());
279 if (IsRed(treeNode->GetLeft()) && IsRed(leftChild->GetLeft())) {
280 treeNode = treeNode->RotateRight(thread);
281 }
282 }
283 if (IsRed(treeNode->GetLeft()) && IsRed(treeNode->GetRight())) {
284 treeNode->FlipColors(thread);
285 }
286 // 1 : root count
287 uint32_t count = Count(treeNode->GetLeft()) + Count(treeNode->GetRight()) + 1;
288 treeNode->SetCount(count);
289
290 return JSTaggedValue(treeNode);
291 }
292
MoveRedLeft(JSThread * thread)293 RBTreeNode *RBTreeNode::MoveRedLeft(JSThread *thread)
294 {
295 RBTreeNode *treeNode = this;
296 treeNode->FlipColors(thread);
297 RBTreeNode *rightChild = RBTreeNode::Cast(treeNode->GetRight().GetTaggedObject());
298 if (IsRed(rightChild->GetLeft())) {
299 rightChild = rightChild->RotateRight(thread);
300 treeNode->SetRight(thread, JSTaggedValue(rightChild));
301 treeNode = treeNode->RotateLeft(thread);
302 treeNode->FlipColors(thread);
303 }
304
305 return treeNode;
306 }
307
MoveRedRight(JSThread * thread)308 RBTreeNode *RBTreeNode::MoveRedRight(JSThread *thread)
309 {
310 RBTreeNode *treeNode = this;
311 treeNode->FlipColors(thread);
312 RBTreeNode *leftChild = RBTreeNode::Cast(treeNode->GetLeft().GetTaggedObject());
313 if (IsRed(leftChild->GetLeft())) {
314 treeNode = treeNode->RotateRight(thread);
315 treeNode->FlipColors(thread);
316 }
317
318 return treeNode;
319 }
320
321 // delete the key-value pair with the minimum key rooted at treeNode
DeleteMin(JSThread * thread,RBTreeNode * treeNode)322 JSTaggedValue RBTreeNode::DeleteMin(JSThread *thread, RBTreeNode *treeNode)
323 {
324 if (treeNode->GetLeft().IsHole()) {
325 return JSTaggedValue::Hole();
326 }
327 RBTreeNode *leftChild = RBTreeNode::Cast(treeNode->GetLeft().GetTaggedObject());
328 if (!IsRed(treeNode->GetLeft()) && !IsRed(leftChild->GetLeft())) {
329 treeNode = treeNode->MoveRedLeft(thread);
330 leftChild = RBTreeNode::Cast(treeNode->GetLeft().GetTaggedObject());
331 }
332
333 treeNode->SetLeft(thread, DeleteMin(thread, leftChild));
334 return Balance(thread, treeNode);
335 }
336
337 // 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)338 JSTaggedValue RBTreeNode::Delete(JSThread *thread, const JSTaggedValue &treeNodeVa, int hash,
339 const JSTaggedValue &key, JSTaggedValue &oldValue)
340 {
341 if (treeNodeVa.IsHole()) {
342 return JSTaggedValue::Hole();
343 }
344 RBTreeNode *treeNode = RBTreeNode::Cast(treeNodeVa.GetTaggedObject());
345 JSTaggedValue leftChildVa = treeNode->GetLeft();
346 JSTaggedValue treeNodeKey = treeNode->GetKey();
347 int cmp = Compare(hash, key, treeNode->GetHash().GetInt(), treeNodeKey);
348 if (cmp < 0) {
349 if (!leftChildVa.IsHole() &&
350 !IsRed(treeNode->GetLeft()) && !IsRed(RBTreeNode::Cast(leftChildVa.GetTaggedObject())->GetLeft())) {
351 treeNode = treeNode->MoveRedLeft(thread);
352 }
353 leftChildVa = treeNode->GetLeft();
354 JSTaggedValue leftValue = Delete(thread, leftChildVa, hash, key, oldValue);
355 treeNode->SetLeft(thread, leftValue);
356 } else {
357 if (IsRed(treeNode->GetLeft())) {
358 treeNode = treeNode->RotateRight(thread);
359 treeNodeKey = treeNode->GetKey();
360 }
361 cmp = Compare(hash, key, treeNode->GetHash().GetInt(), treeNodeKey);
362 if (cmp == 0 && treeNode->GetRight().IsHole()) {
363 oldValue = treeNode->GetValue();
364 return JSTaggedValue::Hole();
365 }
366 JSTaggedValue rightChildVa = treeNode->GetRight();
367 if (!rightChildVa.IsHole() &&
368 !IsRed(rightChildVa) && !IsRed(RBTreeNode::Cast(rightChildVa.GetTaggedObject())->GetLeft())) {
369 treeNode = treeNode->MoveRedRight(thread);
370 treeNodeKey = treeNode->GetKey();
371 }
372
373 cmp = Compare(hash, key, treeNode->GetHash().GetInt(), treeNodeKey);
374 rightChildVa = treeNode->GetRight();
375 if (rightChildVa.IsHole()) {
376 return Balance(thread, treeNode);
377 }
378 RBTreeNode *rightChild = RBTreeNode::Cast(rightChildVa.GetTaggedObject());
379 if (cmp == 0) {
380 oldValue = treeNode->GetValue();
381 RBTreeNode *minNode = rightChild->Min();
382 treeNode->SetKey(thread, minNode->GetKey());
383 treeNode->SetValue(thread, minNode->GetValue());
384 treeNode->SetHash(thread, minNode->GetHash());
385 treeNode->SetRight(thread, DeleteMin(thread, rightChild));
386 } else {
387 JSTaggedValue tmpValue = Delete(thread, rightChildVa, hash, key, oldValue);
388 treeNode->SetRight(thread, tmpValue);
389 }
390 }
391 return Balance(thread, treeNode);
392 }
393
394 // the smallest key in subtree rooted at treeNode; hole if no such key
Min()395 RBTreeNode *RBTreeNode::Min()
396 {
397 if (GetLeft().IsHole()) {
398 return this;
399 } else {
400 return RBTreeNode::Cast(GetLeft().GetTaggedObject())->Min();
401 }
402 }
403
404 // 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)405 JSTaggedValue RBTreeNode::GetTreeNode(JSThread *thread, JSHandle<JSTaggedValue> treeNodeVa,
406 int hash, JSHandle<JSTaggedValue> key)
407 {
408 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
409 JSMutableHandle<TaggedQueue> queue(thread, factory->NewTaggedQueue(0));
410 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, treeNodeVa)));
411 JSMutableHandle<RBTreeNode> root(thread, JSTaggedValue::Hole());
412 JSMutableHandle<JSTaggedValue> currentKey(thread, JSTaggedValue::Hole());
413 JSMutableHandle<JSTaggedValue> left(thread, JSTaggedValue::Hole());
414 JSMutableHandle<JSTaggedValue> right(thread, JSTaggedValue::Hole());
415 while (!queue->Empty()) {
416 root.Update(queue->Pop(thread));
417 currentKey.Update(root->GetKey());
418 if (root->GetHash().GetInt() == hash && (!currentKey->IsHole() && JSTaggedValue::SameValue(key, currentKey))) {
419 return root.GetTaggedValue();
420 }
421 if (!root->GetLeft().IsHole()) {
422 left.Update(root->GetLeft());
423 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, left)));
424 }
425 if (!root->GetRight().IsHole()) {
426 right.Update(root->GetRight());
427 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, right)));
428 }
429 }
430 return JSTaggedValue::Hole();
431 }
432 } // namespace panda::ecmascript
433