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
26using namespace panda;
27using namespace panda::ecmascript;
28namespace panda::test {
29class RBTreeNodeTest : public BaseTestWithScope<false> {
30public:
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
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
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
72HWTEST_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
86HWTEST_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
98HWTEST_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
131HWTEST_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
173HWTEST_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
191HWTEST_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