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 <string>
17 #include "ecmascript/global_env.h"
18 #include "ecmascript/js_handle.h"
19 #include "ecmascript/js_object-inl.h"
20 #include "ecmascript/js_tagged_value.h"
21 #include "ecmascript/object_factory.h"
22 #include "ecmascript/tagged_hash_array.h"
23 #include "ecmascript/tagged_node.h"
24 #include "ecmascript/tests/ecma_container_common.h"
25 #include "ecmascript/tests/test_helper.h"
26
27 using namespace panda;
28 using namespace panda::ecmascript;
29 namespace panda::test {
30 class RBTreeNodeTest : public BaseTestWithScope<false> {
31 public:
GetGlobalEnv()32 JSHandle<GlobalEnv> GetGlobalEnv()
33 {
34 EcmaVM *ecma = thread->GetEcmaVM();
35 return ecma->GetGlobalEnv();
36 }
37 uint32_t NODE_NUMBERS = 8;
38 uint32_t TREE_NODE_NUMBERS = 32;
39
RBTreeNodeInit(JSHandle<RBTreeNode> & rootNode,std::string & myKey,std::string & myValue,uint32_t nums)40 void RBTreeNodeInit(JSHandle<RBTreeNode>& rootNode, std::string& myKey, std::string& myValue,
41 uint32_t nums)
42 {
43 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
44 for (uint32_t i = 0; i < nums; i++) {
45 std::string iKey = myKey + std::to_string(i);
46 std::string iValue = myValue + std::to_string(i);
47 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
48 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
49 int hash = TaggedNode::Hash(thread, factory->NewFromStdString(iKey).GetTaggedValue());
50 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
51 rootNode->SetIsRed(false);
52 }
53 }
54
RBTreeValueCheck(JSHandle<RBTreeNode> & rootNode,std::string & myKey,std::string & myValue,uint32_t startNum,uint32_t nums)55 void RBTreeValueCheck(JSHandle<RBTreeNode>& rootNode, std::string& myKey, std::string& myValue,
56 uint32_t startNum, uint32_t nums)
57 {
58 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
59 for (uint32_t i = startNum; i < nums; i++) {
60 std::string iKey = myKey + std::to_string(i);
61 std::string iValue = myValue + std::to_string(i);
62 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
63 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
64 int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
65 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
66 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
67 JSTaggedValue resValue = RBTreeNode::Cast(gValue.GetTaggedObject())->GetValue(thread);
68 EXPECT_EQ(resValue, value.GetTaggedValue());
69 }
70 }
71 };
72
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeCreate)73 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeCreate)
74 {
75 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
76 std::string k("testKey");
77 std::string v("testValue");
78 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(k).GetTaggedValue());
79 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(v).GetTaggedValue());
80 int hash = TaggedNode::Hash(thread, factory->NewFromStdString(k).GetTaggedValue());
81 JSHandle<RBTreeNode> newNode = factory->NewTreeNode(hash, key, value);
82
83 EXPECT_TRUE(!newNode.GetTaggedValue().IsHole());
84 EXPECT_TRUE(newNode.GetTaggedValue().IsRBTreeNode());
85 }
86
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeSetAndGet)87 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeSetAndGet)
88 {
89 // test RBTreeNode
90 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
91 std::string myKey("mykey");
92 std::string myValue("myvalue");
93 RBTreeNodeInit(rootNode, myKey, myValue, NODE_NUMBERS);
94 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
95
96 RBTreeValueCheck(rootNode, myKey, myValue, 0, NODE_NUMBERS);
97 }
98
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeDelete)99 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeDelete)
100 {
101 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
102 // test RBTreeNode
103 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
104 std::string myKey("mykey");
105 std::string myValue("myvalue");
106 RBTreeNodeInit(rootNode, myKey, myValue, NODE_NUMBERS);
107 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
108
109 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
110 std::string iKey = myKey + std::to_string(i);
111 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
112 int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
113 JSTaggedValue holeValue = JSTaggedValue::Hole();
114 JSTaggedValue dValue =
115 RBTreeNode::Delete(thread, rootNode.GetTaggedValue(), hash, key.GetTaggedValue(), holeValue);
116 rootNode = JSHandle<RBTreeNode>(thread, dValue);
117 }
118 EXPECT_EQ(rootNode->GetCount(), (NODE_NUMBERS / 2));
119
120 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
121 std::string iKey = myKey + std::to_string(i);
122 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
123 int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
124 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
125 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
126 EXPECT_EQ(gValue, JSTaggedValue::Hole());
127 }
128
129 RBTreeValueCheck(rootNode, myKey, myValue, NODE_NUMBERS / 2, NODE_NUMBERS);
130 }
131
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeDivide)132 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeDivide)
133 {
134 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
135 std::string myKey("mykey");
136 std::string myValue("myvalue");
137 RBTreeNodeInit(rootNode, myKey, myValue, TREE_NODE_NUMBERS);
138 EXPECT_EQ(rootNode->GetCount(), TREE_NODE_NUMBERS);
139
140 uint32_t count = rootNode->GetCount();
141 JSHandle<TaggedHashArray> newTab =
142 JSHandle<TaggedHashArray>(thread,
143 TaggedHashArray::Create(thread, TaggedHashArray::DEFAULT_INITIAL_CAPACITY * 2));
144 JSHandle<JSTaggedValue> rootNodeVa = JSHandle<JSTaggedValue>::Cast(rootNode);
145 RBTreeNode::Divide(thread, newTab, rootNodeVa, 0, TaggedHashArray::DEFAULT_INITIAL_CAPACITY);
146 JSTaggedValue loNode = newTab->Get(thread, 0);
147 uint32_t loCount = 0;
148 uint32_t hiCount = 0;
149 if (loNode.IsLinkedNode()) {
150 for (JSHandle<LinkedNode> node = JSHandle<LinkedNode>(thread, loNode);
151 !node.GetTaggedValue().IsHole();
152 node = JSHandle<LinkedNode>(thread, node->GetNext(thread))) {
153 loCount++;
154 }
155 } else {
156 JSHandle<RBTreeNode> node = JSHandle<RBTreeNode>(thread, loNode);
157 loCount = node->GetCount();
158 }
159 JSTaggedValue hiNode = newTab->Get(thread, TaggedHashArray::DEFAULT_INITIAL_CAPACITY);
160 if (hiNode.IsLinkedNode()) {
161 for (JSHandle<LinkedNode> node = JSHandle<LinkedNode>(thread, hiNode);
162 !node.GetTaggedValue().IsHole();
163 node = JSHandle<LinkedNode>(thread, node->GetNext(thread))) {
164 hiCount++;
165 }
166 } else {
167 JSHandle<RBTreeNode> node = JSHandle<RBTreeNode>(thread, hiNode);
168 hiCount = node->GetCount();
169 }
170
171 EXPECT_TRUE(count == loCount + hiCount);
172 }
173
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeUntreeify)174 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeUntreeify)
175 {
176 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
177 std::string myKey("mykey");
178 std::string myValue("myvalue");
179 RBTreeNodeInit(rootNode, myKey, myValue, NODE_NUMBERS);
180 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
181
182 JSHandle<LinkedNode> head = RBTreeNode::Detreeing(thread, rootNode);
183
184 uint32_t count = 0;
185 for (; !head.GetTaggedValue().IsHole(); head = JSHandle<LinkedNode>(thread, head->GetNext(thread))) {
186 count++;
187 }
188
189 EXPECT_EQ(count, rootNode->GetCount());
190 }
191
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeCompare)192 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeCompare)
193 {
194 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
195 std::string value1("Compare1");
196 std::string value2("Compare2");
197 std::string value3("Compare1");
198 std::string value4("name");
199 JSHandle<JSTaggedValue> a(thread, factory->NewFromStdString(value1).GetTaggedValue());
200 JSHandle<JSTaggedValue> b(thread, factory->NewFromStdString(value2).GetTaggedValue());
201 JSHandle<JSTaggedValue> c(thread, factory->NewFromStdString(value3).GetTaggedValue());
202 JSHandle<JSTaggedValue> d(thread, factory->NewFromStdString(value4).GetTaggedValue());
203 int rvalue = RBTreeNode::Compare(thread, 12345, a.GetTaggedValue(), 12345, b.GetTaggedValue());
204 EXPECT_TRUE(rvalue != 0);
205 rvalue = RBTreeNode::Compare(thread, 54321, a.GetTaggedValue(), 54321, c.GetTaggedValue());
206 EXPECT_EQ(rvalue, 0);
207 rvalue = RBTreeNode::Compare(thread, 3373707, d.GetTaggedValue(), 3373707, JSTaggedValue(38754584));
208 EXPECT_EQ(rvalue, 1);
209 }
210
HWTEST_F_L0(RBTreeNodeTest,RandomlyRemoveStringKeyTest)211 HWTEST_F_L0(RBTreeNodeTest, RandomlyRemoveStringKeyTest)
212 {
213 const int treeSize = 20;
214 const int maxIndex = 25;
215 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
216 std::string myKey("a");
217 std::string myValue("myvalue");
218 std::random_device rd;
219 std::mt19937 g(rd());
220 std::vector<std::string>p;
221 p.reserve(treeSize);
222 std::vector<uint64_t>hash;
223 for (int i = 1; i <= treeSize; i++) {
224 myKey.push_back('a' + (g() % 2));
225 p.push_back(myKey);
226 }
227 for (int i = 1; i <= treeSize; i++) {
228 hash.push_back(0);
229 }
230 JSTaggedValue oldValue = JSTaggedValue::Hole();
231 int loopCount = maxIndex;
232 while (loopCount-- && std::next_permutation(p.begin(), p.end())) {
233 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
234 std::vector<JSHandle<JSTaggedValue> > keyArray;
235 // randomly insert
236 for (int i = 0; i < treeSize; i++) {
237 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(p[i]).GetTaggedValue());
238 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(myValue).GetTaggedValue());
239 rootNode = RBTreeNode::Set(thread, rootNode, hash[i], key, value);
240 rootNode->SetIsRed(false);
241 }
242 std::vector<std::string>pp = p;
243 std::shuffle(pp.begin(), pp.end(), g);
244 for (int i = 0; i < treeSize; i++) {
245 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(pp[i]).GetTaggedValue());
246 JSTaggedValue existValue = RBTreeNode::Cast(RBTreeNode::GetTreeNode(thread,
247 JSHandle<JSTaggedValue>(thread,
248 rootNode.GetTaggedValue()), hash[i], key).GetTaggedObject())->GetValue(thread);
249 rootNode = JSHandle<RBTreeNode>(thread, RBTreeNode::Delete(thread,
250 rootNode.GetTaggedValue(), hash[i], key.GetTaggedValue(), oldValue));
251 ASSERT_EQ(oldValue, existValue);
252 }
253 }
254 }
255
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeSetAndDeleteIntegerKeyWithSameHash)256 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeSetAndDeleteIntegerKeyWithSameHash)
257 {
258 int hash = 0;
259 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
260 // test RBTreeNode
261 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
262 std::string myValue("myvalue");
263 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
264 std::string iValue = myValue + std::to_string(i);
265 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(i));
266 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
267 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
268 rootNode->SetIsRed(false);
269 }
270
271 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
272 std::string iValue = myValue + std::to_string(i);
273 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(i));
274 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
275 auto res = RBTreeNode::GetTreeNode(thread, JSHandle<JSTaggedValue>(rootNode), hash, key);
276 EXPECT_TRUE(!res.IsHole());
277 EXPECT_EQ(RBTreeNode::Cast(res.GetTaggedObject())->GetValue(thread), value.GetTaggedValue());
278 }
279
280 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
281
282 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
283 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(i));
284 JSTaggedValue holeValue = JSTaggedValue::Hole();
285 JSTaggedValue dValue =
286 RBTreeNode::Delete(thread, rootNode.GetTaggedValue(), hash, key.GetTaggedValue(), holeValue);
287 rootNode = JSHandle<RBTreeNode>(thread, dValue);
288 }
289 EXPECT_EQ(rootNode->GetCount(), (NODE_NUMBERS / 2));
290
291 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
292 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(i));
293 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
294 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
295 EXPECT_EQ(gValue, JSTaggedValue::Hole());
296 }
297 }
298
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeSetAndDeleteDoubleKeyWithSameHash)299 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeSetAndDeleteDoubleKeyWithSameHash)
300 {
301 int hash = 0;
302 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
303 // test RBTreeNode
304 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
305 std::string myValue("myvalue");
306 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
307 std::string iValue = myValue + std::to_string(i);
308 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(double(i) + 0.1));
309 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
310 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
311 rootNode->SetIsRed(false);
312 }
313 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
314
315 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
316 std::string iValue = myValue + std::to_string(i);
317 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(double(i) + 0.1));
318 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
319 auto res = RBTreeNode::GetTreeNode(thread, JSHandle<JSTaggedValue>(rootNode), hash, key);
320 EXPECT_TRUE(!res.IsHole());
321 EXPECT_EQ(RBTreeNode::Cast(res.GetTaggedObject())->GetValue(thread), value.GetTaggedValue());
322 }
323
324 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
325 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(double(i) + 0.1));
326 JSTaggedValue holeValue = JSTaggedValue::Hole();
327 JSTaggedValue dValue =
328 RBTreeNode::Delete(thread, rootNode.GetTaggedValue(), hash, key.GetTaggedValue(), holeValue);
329 rootNode = JSHandle<RBTreeNode>(thread, dValue);
330 }
331 EXPECT_EQ(rootNode->GetCount(), (NODE_NUMBERS / 2));
332
333 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
334 JSHandle<JSTaggedValue> key(thread, JSTaggedValue(double(i) + 0.1));
335 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
336 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
337 EXPECT_EQ(gValue, JSTaggedValue::Hole());
338 }
339 }
340
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeSetAndDeleteBigIntKeyWithSameHash)341 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeSetAndDeleteBigIntKeyWithSameHash)
342 {
343 int hash = 0;
344 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
345 // test RBTreeNode
346 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
347 std::string myValue("myvalue");
348 CString str = "9007199254740991012345";
349
350 std::vector<JSHandle<JSTaggedValue> > keyArray;
351 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
352 JSHandle<BigInt> bigint = BigIntHelper::SetBigInt(thread, str);
353 keyArray.push_back(JSHandle<JSTaggedValue>::Cast(bigint));
354 str.append("123");
355 }
356 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
357 std::string iValue = myValue + std::to_string(i);
358 auto &key = keyArray[i];
359 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
360 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
361 rootNode->SetIsRed(false);
362 }
363 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
364
365 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
366 JSHandle<JSTaggedValue> key = keyArray[i];
367 std::string iValue = myValue + std::to_string(i);
368 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
369 auto res = RBTreeNode::GetTreeNode(thread, JSHandle<JSTaggedValue>(rootNode), hash, key);
370 EXPECT_TRUE(!res.IsHole());
371 EXPECT_EQ(RBTreeNode::Cast(res.GetTaggedObject())->GetValue(thread), value.GetTaggedValue());
372 }
373
374 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
375 auto &key = keyArray[i];
376 JSTaggedValue holeValue = JSTaggedValue::Hole();
377 JSTaggedValue dValue =
378 RBTreeNode::Delete(thread, rootNode.GetTaggedValue(), hash, key.GetTaggedValue(), holeValue);
379 rootNode = JSHandle<RBTreeNode>(thread, dValue);
380 }
381 EXPECT_EQ(rootNode->GetCount(), (NODE_NUMBERS / 2));
382
383 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
384 auto &key = keyArray[i];
385 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
386 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
387 EXPECT_EQ(gValue, JSTaggedValue::Hole());
388 }
389 }
390
391 }
392