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/test_helper.h"
25
26 using namespace panda;
27 using namespace panda::ecmascript;
28 namespace panda::test {
29 class RBTreeNodeTest : public testing::Test {
30 public:
SetUpTestCase()31 static void SetUpTestCase()
32 {
33 GTEST_LOG_(INFO) << "SetUpTestCase";
34 }
35
TearDownTestCase()36 static void TearDownTestCase()
37 {
38 GTEST_LOG_(INFO) << "TearDownCase";
39 }
40
SetUp()41 void SetUp() override
42 {
43 TestHelper::CreateEcmaVMWithScope(instance, thread, scope);
44 }
45
TearDown()46 void TearDown() override
47 {
48 TestHelper::DestroyEcmaVMWithScope(instance, scope);
49 }
50
51 EcmaVM *instance {nullptr};
52 EcmaHandleScope *scope {nullptr};
53 JSThread *thread {nullptr};
54
GetGlobalEnv()55 JSHandle<GlobalEnv> GetGlobalEnv()
56 {
57 EcmaVM *ecma = thread->GetEcmaVM();
58 return ecma->GetGlobalEnv();
59 }
60 uint32_t NODE_NUMBERS = 8;
61 uint32_t TREE_NODE_NUMBERS = 32;
62 };
63
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeCreate)64 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeCreate)
65 {
66 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
67 std::string k("testKey");
68 std::string v("testValue");
69 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(k).GetTaggedValue());
70 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(v).GetTaggedValue());
71 int hash = TaggedNode::Hash(factory->NewFromStdString(k).GetTaggedValue());
72 JSHandle<RBTreeNode> newNode = factory->NewTreeNode(hash, key, value);
73
74 EXPECT_TRUE(!newNode.GetTaggedValue().IsHole());
75 EXPECT_TRUE(newNode.GetTaggedValue().IsRBTreeNode());
76 }
77
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeSetAndGet)78 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeSetAndGet)
79 {
80 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
81 // test RBTreeNode
82 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
83 std::string myKey("mykey");
84 std::string myValue("myvalue");
85 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
86 std::string iKey = myKey + std::to_string(i);
87 std::string iValue = myValue + std::to_string(i);
88 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
89 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
90 int hash = TaggedNode::Hash(factory->NewFromStdString(iKey).GetTaggedValue());
91 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
92 rootNode->SetIsRed(thread, JSTaggedValue(false));
93 }
94 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
95
96 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
97 std::string iKey = myKey + std::to_string(i);
98 std::string iValue = myValue + std::to_string(i);
99 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
100 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
101 int hash = TaggedNode::Hash(key.GetTaggedValue());
102 // test get
103 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
104 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
105 JSTaggedValue resValue = RBTreeNode::Cast(gValue.GetTaggedObject())->GetValue();
106 EXPECT_EQ(resValue, value.GetTaggedValue());
107 }
108 }
109
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeDelete)110 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeDelete)
111 {
112 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
113 // test RBTreeNode
114 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
115 std::string myKey("mykey");
116 std::string myValue("myvalue");
117 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
118 std::string iKey = myKey + std::to_string(i);
119 std::string iValue = myValue + std::to_string(i);
120 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
121 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
122 int hash = TaggedNode::Hash(factory->NewFromStdString(iKey).GetTaggedValue());
123 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
124 rootNode->SetIsRed(thread, JSTaggedValue(false));
125 }
126 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
127
128 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
129 std::string iKey = myKey + std::to_string(i);
130 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
131 int hash = TaggedNode::Hash(key.GetTaggedValue());
132 JSTaggedValue holeValue = JSTaggedValue::Hole();
133 JSTaggedValue dValue =
134 RBTreeNode::Delete(thread, rootNode.GetTaggedValue(), hash, key.GetTaggedValue(), holeValue);
135 rootNode = JSHandle<RBTreeNode>(thread, dValue);
136 }
137 EXPECT_EQ(rootNode->GetCount(), (NODE_NUMBERS / 2));
138
139 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
140 std::string iKey = myKey + std::to_string(i);
141 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
142 int hash = TaggedNode::Hash(key.GetTaggedValue());
143 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
144 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
145 EXPECT_EQ(gValue, JSTaggedValue::Hole());
146 }
147
148 for (uint32_t i = NODE_NUMBERS / 2; i < NODE_NUMBERS; i++) {
149 std::string iKey = myKey + std::to_string(i);
150 std::string iValue = myValue + std::to_string(i);
151 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
152 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
153 int hash = TaggedNode::Hash(key.GetTaggedValue());
154 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
155 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
156 JSTaggedValue resValue = RBTreeNode::Cast(gValue.GetTaggedObject())->GetValue();
157 EXPECT_EQ(resValue, value.GetTaggedValue());
158 }
159 }
160
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeDivide)161 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeDivide)
162 {
163 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
164 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
165 std::string myKey("mykey");
166 std::string myValue("myvalue");
167 for (uint32_t i = 0; i < TREE_NODE_NUMBERS; i++) {
168 std::string iKey = myKey + std::to_string(i);
169 std::string iValue = myValue + std::to_string(i);
170 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
171 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
172 int hash = TaggedNode::Hash(factory->NewFromStdString(iKey).GetTaggedValue());
173 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
174 rootNode->SetIsRed(thread, JSTaggedValue(false));
175 }
176 EXPECT_EQ(rootNode->GetCount(), TREE_NODE_NUMBERS);
177
178 uint32_t count = rootNode->GetCount();
179 JSHandle<TaggedHashArray> newTab =
180 JSHandle<TaggedHashArray>(thread,
181 TaggedHashArray::Create(thread, TaggedHashArray::DEFAULT_INITIAL_CAPACITY * 2));
182 JSHandle<JSTaggedValue> rootNodeVa = JSHandle<JSTaggedValue>::Cast(rootNode);
183 RBTreeNode::Divide(thread, newTab, rootNodeVa, 0, TaggedHashArray::DEFAULT_INITIAL_CAPACITY);
184 JSTaggedValue loNode = newTab->Get(0);
185 uint32_t loCount = 0;
186 uint32_t hiCount = 0;
187 if (loNode.IsLinkedNode()) {
188 for (JSHandle<LinkedNode> node = JSHandle<LinkedNode>(thread, loNode);
189 !node.GetTaggedValue().IsHole();
190 node = JSHandle<LinkedNode>(thread, node->GetNext())) {
191 loCount++;
192 }
193 } else {
194 JSHandle<RBTreeNode> node = JSHandle<RBTreeNode>(thread, loNode);
195 loCount = node->GetCount();
196 }
197 JSTaggedValue hiNode = newTab->Get(TaggedHashArray::DEFAULT_INITIAL_CAPACITY);
198 if (hiNode.IsLinkedNode()) {
199 for (JSHandle<LinkedNode> node = JSHandle<LinkedNode>(thread, hiNode);
200 !node.GetTaggedValue().IsHole();
201 node = JSHandle<LinkedNode>(thread, node->GetNext())) {
202 hiCount++;
203 }
204 } else {
205 JSHandle<RBTreeNode> node = JSHandle<RBTreeNode>(thread, hiNode);
206 hiCount = node->GetCount();
207 }
208
209 EXPECT_TRUE(count == loCount + hiCount);
210 }
211
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeUntreeify)212 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeUntreeify)
213 {
214 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
215 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
216 std::string myKey("mykey");
217 std::string myValue("myvalue");
218 for (uint32_t i = 0; i < NODE_NUMBERS; i++) {
219 std::string iKey = myKey + std::to_string(i);
220 std::string iValue = myValue + std::to_string(i);
221 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
222 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
223 int hash = TaggedNode::Hash(factory->NewFromStdString(iKey).GetTaggedValue());
224 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
225 rootNode->SetIsRed(thread, JSTaggedValue(false));
226 }
227 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
228
229 JSHandle<LinkedNode> head = RBTreeNode::Detreeing(thread, rootNode);
230
231 uint32_t count = 0;
232 for (; !head.GetTaggedValue().IsHole(); head = JSHandle<LinkedNode>(thread, head->GetNext())) {
233 count++;
234 }
235
236 EXPECT_EQ(count, rootNode->GetCount());
237 }
238
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeCompare)239 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeCompare)
240 {
241 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
242 std::string value1("Compare1");
243 std::string value2("Compare2");
244 std::string value3("Compare1");
245 std::string value4("name");
246 JSHandle<JSTaggedValue> a(thread, factory->NewFromStdString(value1).GetTaggedValue());
247 JSHandle<JSTaggedValue> b(thread, factory->NewFromStdString(value2).GetTaggedValue());
248 JSHandle<JSTaggedValue> c(thread, factory->NewFromStdString(value3).GetTaggedValue());
249 JSHandle<JSTaggedValue> d(thread, factory->NewFromStdString(value4).GetTaggedValue());
250 int rvalue = RBTreeNode::Compare(12345, a.GetTaggedValue(), 12345, b.GetTaggedValue());
251 EXPECT_TRUE(rvalue != 0);
252 rvalue = RBTreeNode::Compare(54321, a.GetTaggedValue(), 54321, c.GetTaggedValue());
253 EXPECT_EQ(rvalue, 0);
254 rvalue = RBTreeNode::Compare(3373707, d.GetTaggedValue(), 3373707, JSTaggedValue(38754584));
255 EXPECT_EQ(rvalue, 1);
256 }
257 }
258