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 BaseTestWithScope<false> {
30 public:
GetGlobalEnv()31 JSHandle<GlobalEnv> GetGlobalEnv()
32 {
33 EcmaVM *ecma = thread->GetEcmaVM();
34 return ecma->GetGlobalEnv();
35 }
36 uint32_t NODE_NUMBERS = 8;
37 uint32_t TREE_NODE_NUMBERS = 32;
38
RBTreeNodeInit(JSHandle<RBTreeNode> & rootNode,std::string & myKey,std::string & myValue,uint32_t nums)39 void RBTreeNodeInit(JSHandle<RBTreeNode>& rootNode, std::string& myKey, std::string& myValue,
40 uint32_t nums)
41 {
42 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
43 for (uint32_t i = 0; i < nums; i++) {
44 std::string iKey = myKey + std::to_string(i);
45 std::string iValue = myValue + std::to_string(i);
46 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
47 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
48 int hash = TaggedNode::Hash(thread, factory->NewFromStdString(iKey).GetTaggedValue());
49 rootNode = RBTreeNode::Set(thread, rootNode, hash, key, value);
50 rootNode->SetIsRed(thread, JSTaggedValue(false));
51 }
52 }
53
RBTreeValueCheck(JSHandle<RBTreeNode> & rootNode,std::string & myKey,std::string & myValue,uint32_t startNum,uint32_t nums)54 void RBTreeValueCheck(JSHandle<RBTreeNode>& rootNode, std::string& myKey, std::string& myValue,
55 uint32_t startNum, uint32_t nums)
56 {
57 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
58 for (uint32_t i = startNum; i < nums; i++) {
59 std::string iKey = myKey + std::to_string(i);
60 std::string iValue = myValue + std::to_string(i);
61 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
62 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(iValue).GetTaggedValue());
63 int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
64 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
65 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
66 JSTaggedValue resValue = RBTreeNode::Cast(gValue.GetTaggedObject())->GetValue();
67 EXPECT_EQ(resValue, value.GetTaggedValue());
68 }
69 }
70 };
71
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeCreate)72 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeCreate)
73 {
74 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
75 std::string k("testKey");
76 std::string v("testValue");
77 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(k).GetTaggedValue());
78 JSHandle<JSTaggedValue> value(thread, factory->NewFromStdString(v).GetTaggedValue());
79 int hash = TaggedNode::Hash(thread, factory->NewFromStdString(k).GetTaggedValue());
80 JSHandle<RBTreeNode> newNode = factory->NewTreeNode(hash, key, value);
81
82 EXPECT_TRUE(!newNode.GetTaggedValue().IsHole());
83 EXPECT_TRUE(newNode.GetTaggedValue().IsRBTreeNode());
84 }
85
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeSetAndGet)86 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeSetAndGet)
87 {
88 // test RBTreeNode
89 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
90 std::string myKey("mykey");
91 std::string myValue("myvalue");
92 RBTreeNodeInit(rootNode, myKey, myValue, NODE_NUMBERS);
93 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
94
95 RBTreeValueCheck(rootNode, myKey, myValue, 0, NODE_NUMBERS);
96 }
97
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeDelete)98 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeDelete)
99 {
100 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
101 // test RBTreeNode
102 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
103 std::string myKey("mykey");
104 std::string myValue("myvalue");
105 RBTreeNodeInit(rootNode, myKey, myValue, NODE_NUMBERS);
106 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
107
108 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
109 std::string iKey = myKey + std::to_string(i);
110 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
111 int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
112 JSTaggedValue holeValue = JSTaggedValue::Hole();
113 JSTaggedValue dValue =
114 RBTreeNode::Delete(thread, rootNode.GetTaggedValue(), hash, key.GetTaggedValue(), holeValue);
115 rootNode = JSHandle<RBTreeNode>(thread, dValue);
116 }
117 EXPECT_EQ(rootNode->GetCount(), (NODE_NUMBERS / 2));
118
119 for (uint32_t i = 0; i < NODE_NUMBERS / 2; i++) {
120 std::string iKey = myKey + std::to_string(i);
121 JSHandle<JSTaggedValue> key(thread, factory->NewFromStdString(iKey).GetTaggedValue());
122 int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
123 JSHandle<JSTaggedValue> rootNodeVa(thread, rootNode.GetTaggedValue());
124 JSTaggedValue gValue = RBTreeNode::GetTreeNode(thread, rootNodeVa, hash, key);
125 EXPECT_EQ(gValue, JSTaggedValue::Hole());
126 }
127
128 RBTreeValueCheck(rootNode, myKey, myValue, NODE_NUMBERS / 2, NODE_NUMBERS);
129 }
130
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeDivide)131 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeDivide)
132 {
133 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
134 std::string myKey("mykey");
135 std::string myValue("myvalue");
136 RBTreeNodeInit(rootNode, myKey, myValue, TREE_NODE_NUMBERS);
137 EXPECT_EQ(rootNode->GetCount(), TREE_NODE_NUMBERS);
138
139 uint32_t count = rootNode->GetCount();
140 JSHandle<TaggedHashArray> newTab =
141 JSHandle<TaggedHashArray>(thread,
142 TaggedHashArray::Create(thread, TaggedHashArray::DEFAULT_INITIAL_CAPACITY * 2));
143 JSHandle<JSTaggedValue> rootNodeVa = JSHandle<JSTaggedValue>::Cast(rootNode);
144 RBTreeNode::Divide(thread, newTab, rootNodeVa, 0, TaggedHashArray::DEFAULT_INITIAL_CAPACITY);
145 JSTaggedValue loNode = newTab->Get(0);
146 uint32_t loCount = 0;
147 uint32_t hiCount = 0;
148 if (loNode.IsLinkedNode()) {
149 for (JSHandle<LinkedNode> node = JSHandle<LinkedNode>(thread, loNode);
150 !node.GetTaggedValue().IsHole();
151 node = JSHandle<LinkedNode>(thread, node->GetNext())) {
152 loCount++;
153 }
154 } else {
155 JSHandle<RBTreeNode> node = JSHandle<RBTreeNode>(thread, loNode);
156 loCount = node->GetCount();
157 }
158 JSTaggedValue hiNode = newTab->Get(TaggedHashArray::DEFAULT_INITIAL_CAPACITY);
159 if (hiNode.IsLinkedNode()) {
160 for (JSHandle<LinkedNode> node = JSHandle<LinkedNode>(thread, hiNode);
161 !node.GetTaggedValue().IsHole();
162 node = JSHandle<LinkedNode>(thread, node->GetNext())) {
163 hiCount++;
164 }
165 } else {
166 JSHandle<RBTreeNode> node = JSHandle<RBTreeNode>(thread, hiNode);
167 hiCount = node->GetCount();
168 }
169
170 EXPECT_TRUE(count == loCount + hiCount);
171 }
172
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeUntreeify)173 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeUntreeify)
174 {
175 JSHandle<RBTreeNode> rootNode(thread, JSTaggedValue::Hole());
176 std::string myKey("mykey");
177 std::string myValue("myvalue");
178 RBTreeNodeInit(rootNode, myKey, myValue, NODE_NUMBERS);
179 EXPECT_EQ(rootNode->GetCount(), NODE_NUMBERS);
180
181 JSHandle<LinkedNode> head = RBTreeNode::Detreeing(thread, rootNode);
182
183 uint32_t count = 0;
184 for (; !head.GetTaggedValue().IsHole(); head = JSHandle<LinkedNode>(thread, head->GetNext())) {
185 count++;
186 }
187
188 EXPECT_EQ(count, rootNode->GetCount());
189 }
190
HWTEST_F_L0(RBTreeNodeTest,RBTreeNodeCompare)191 HWTEST_F_L0(RBTreeNodeTest, RBTreeNodeCompare)
192 {
193 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
194 std::string value1("Compare1");
195 std::string value2("Compare2");
196 std::string value3("Compare1");
197 std::string value4("name");
198 JSHandle<JSTaggedValue> a(thread, factory->NewFromStdString(value1).GetTaggedValue());
199 JSHandle<JSTaggedValue> b(thread, factory->NewFromStdString(value2).GetTaggedValue());
200 JSHandle<JSTaggedValue> c(thread, factory->NewFromStdString(value3).GetTaggedValue());
201 JSHandle<JSTaggedValue> d(thread, factory->NewFromStdString(value4).GetTaggedValue());
202 int rvalue = RBTreeNode::Compare(12345, a.GetTaggedValue(), 12345, b.GetTaggedValue());
203 EXPECT_TRUE(rvalue != 0);
204 rvalue = RBTreeNode::Compare(54321, a.GetTaggedValue(), 54321, c.GetTaggedValue());
205 EXPECT_EQ(rvalue, 0);
206 rvalue = RBTreeNode::Compare(3373707, d.GetTaggedValue(), 3373707, JSTaggedValue(38754584));
207 EXPECT_EQ(rvalue, 1);
208 }
209 }
210