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/js_api/js_api_hashmap.h"
17
18#include "ecmascript/containers/containers_errors.h"
19#include "ecmascript/tagged_hash_array.h"
20
21namespace panda::ecmascript {
22using ContainerError = containers::ContainerError;
23using ErrorFlag = containers::ErrorFlag;
24JSTaggedValue JSAPIHashMap::IsEmpty()
25{
26    return JSTaggedValue(GetSize() == 0);
27}
28
29JSTaggedValue JSAPIHashMap::HasKey(JSThread *thread, JSTaggedValue key)
30{
31    TaggedHashArray *hashArray = TaggedHashArray::Cast(GetTable().GetTaggedObject());
32    int hash = TaggedNode::Hash(thread, key);
33    return JSTaggedValue(!(hashArray->GetNode(thread, hash, key).IsHole()));
34}
35
36JSTaggedValue JSAPIHashMap::HasValue(JSThread *thread, JSHandle<JSAPIHashMap> hashMap,
37                                     JSHandle<JSTaggedValue> value)
38{
39    JSHandle<TaggedHashArray> hashArray(thread, hashMap->GetTable());
40    uint32_t tabLength = hashArray->GetLength();
41    JSTaggedType *array = hashArray->GetData();
42    JSTaggedValue taggedValue = value.GetTaggedValue();
43    for (uint32_t index = 0; index < tabLength; index++) {
44        JSTaggedValue node(array[index]);
45        if (node.IsHole()) {
46            continue;
47        }
48        if (node.IsLinkedNode()) {
49            if (HasValueLinkedNode(node, taggedValue)) {
50                return JSTaggedValue::True();
51            }
52        } else {
53            if (HasValueRBTreeNode(node, taggedValue)) {
54                return JSTaggedValue::True();
55            }
56        }
57    }
58    return JSTaggedValue::False();
59}
60
61bool JSAPIHashMap::HasValueLinkedNode(JSTaggedValue node, JSTaggedValue value)
62{
63    ASSERT(node.IsLinkedNode());
64    while (!node.IsHole()) {
65        LinkedNode *p = LinkedNode::Cast(node.GetTaggedObject());
66        if (JSTaggedValue::SameValue(p->GetValue(), value)) {
67            return true;
68        }
69        node = p->GetNext();
70    }
71    return false;
72}
73
74bool JSAPIHashMap::HasValueRBTreeNode(JSTaggedValue node, JSTaggedValue value)
75{
76    ASSERT(node.IsRBTreeNode());
77    RBTreeNode *p = RBTreeNode::Cast(node.GetTaggedObject());
78    if (JSTaggedValue::SameValue(p->GetValue(), value)) {
79        return true;
80    }
81    JSTaggedValue left = p->GetLeft();
82    if (!left.IsHole() && HasValueRBTreeNode(left, value)) {
83        return true;
84    }
85    JSTaggedValue right = p->GetRight();
86    if (!right.IsHole() && HasValueRBTreeNode(right, value)) {
87        return true;
88    }
89    return false;
90}
91
92bool JSAPIHashMap::Replace(JSThread *thread, JSTaggedValue key, JSTaggedValue newValue)
93{
94    TaggedHashArray *hashArray = TaggedHashArray::Cast(GetTable().GetTaggedObject());
95    int hash = TaggedNode::Hash(thread, key);
96    JSTaggedValue nodeVa = hashArray->GetNode(thread, hash, key);
97    if (nodeVa.IsHole()) {
98        return false;
99    }
100    if (nodeVa.IsLinkedNode()) {
101        LinkedNode::Cast(nodeVa.GetTaggedObject())->SetValue(thread, newValue);
102    } else {
103        RBTreeNode::Cast(nodeVa.GetTaggedObject())->SetValue(thread, newValue);
104    }
105    return true;
106}
107
108void JSAPIHashMap::Set(JSThread *thread, JSHandle<JSAPIHashMap> hashMap,
109                       JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value)
110{
111    if (key.GetTaggedValue().IsUndefined()) {
112        JSHandle<EcmaString> result = JSTaggedValue::ToString(thread, key.GetTaggedValue());
113        CString errorMsg =
114            "The type of \"key\" must be Key of JS. Received value is: " + ConvertToString(*result);
115        JSTaggedValue error = ContainerError::BusinessError(thread, ErrorFlag::TYPE_ERROR, errorMsg.c_str());
116        THROW_NEW_ERROR_AND_RETURN(thread, error);
117    }
118    JSHandle<TaggedHashArray> hashArray(thread, hashMap->GetTable());
119    int hash = TaggedNode::Hash(thread, key.GetTaggedValue());
120    JSTaggedValue setValue = TaggedHashArray::SetVal(thread, hashArray, hash, key, value);
121    uint32_t nodeNum = hashMap->GetSize();
122    if (!setValue.IsUndefined()) {
123        hashMap->SetSize(++nodeNum);
124    }
125    uint32_t tableLength = (hashArray->GetLength()) * TaggedHashArray::DEFAULT_LOAD_FACTOR;
126    if (nodeNum > tableLength) {
127        hashArray = TaggedHashArray::Resize(thread, hashArray, hashArray->GetLength());
128        hashMap->SetTable(thread, hashArray);
129    }
130}
131
132JSTaggedValue JSAPIHashMap::Get(JSThread *thread, JSTaggedValue key)
133{
134    TaggedHashArray *hashArray = TaggedHashArray::Cast(GetTable().GetTaggedObject());
135    int hash = TaggedNode::Hash(thread, key);
136    JSTaggedValue node = hashArray->GetNode(thread, hash, key);
137    if (node.IsHole()) {
138        return JSTaggedValue::Undefined();
139    } else if (node.IsRBTreeNode()) {
140        return RBTreeNode::Cast(node.GetTaggedObject())->GetValue();
141    } else {
142        return LinkedNode::Cast(node.GetTaggedObject())->GetValue();
143    }
144}
145
146void JSAPIHashMap::SetAll(JSThread *thread, JSHandle<JSAPIHashMap> dst, JSHandle<JSAPIHashMap> src)
147{
148    JSHandle<TaggedHashArray> hashArray(thread, src->GetTable());
149    uint32_t srcTabLength = hashArray->GetLength();
150    JSMutableHandle<JSTaggedValue> node(thread, JSTaggedValue::Hole());
151    for (uint32_t index = 0; index < srcTabLength; index++) {
152        node.Update(hashArray->Get(index));
153        if (node->IsHole()) {
154            continue;
155        }
156        if (node->IsLinkedNode()) {
157            SetAllLinkedNode(thread, dst, JSMutableHandle<LinkedNode>::Cast(node));
158        } else {
159            SetAllRBTreeNode(thread, dst, JSHandle<RBTreeNode>(node));
160        }
161    }
162}
163
164void JSAPIHashMap::SetAllLinkedNode(JSThread *thread, JSHandle<JSAPIHashMap> hashMap, JSMutableHandle<LinkedNode> node)
165{
166    ASSERT(node.GetTaggedValue().IsLinkedNode());
167    while (!node.GetTaggedValue().IsHole()) {
168        if (!hashMap->Replace(thread, node->GetKey(), node->GetValue())) {
169            JSHandle<JSTaggedValue> key(thread, node->GetKey());
170            JSHandle<JSTaggedValue> value(thread, node->GetValue());
171            Set(thread, hashMap, key, value);
172        }
173        node.Update(node->GetNext());
174    }
175}
176
177void JSAPIHashMap::SetAllRBTreeNode(JSThread *thread, JSHandle<JSAPIHashMap> hashMap, JSHandle<RBTreeNode> node)
178{
179    ASSERT(node.GetTaggedValue().IsRBTreeNode());
180    JSMutableHandle<JSTaggedValue> key(thread, node->GetKey());
181    JSMutableHandle<JSTaggedValue> value(thread, node->GetValue());
182    if (!hashMap->Replace(thread, key.GetTaggedValue(), value.GetTaggedValue())) {
183        Set(thread, hashMap, key, value);
184    }
185    JSMutableHandle<RBTreeNode> left(thread, node->GetLeft());
186    if (!left.GetTaggedValue().IsHole()) {
187        SetAllRBTreeNode(thread, hashMap, left);
188    }
189    JSMutableHandle<RBTreeNode> right(thread, node->GetRight());
190    if (!right.GetTaggedValue().IsHole()) {
191        SetAllRBTreeNode(thread, hashMap, right);
192    }
193}
194
195void JSAPIHashMap::Clear(JSThread *thread)
196{
197    TaggedHashArray *hashArray = TaggedHashArray::Cast(GetTable().GetTaggedObject());
198    uint32_t nodeLength = GetSize();
199    if (nodeLength > 0) {
200        hashArray->Clear(thread);
201        SetSize(0);
202    }
203}
204
205JSTaggedValue JSAPIHashMap::Remove(JSThread *thread, JSHandle<JSAPIHashMap> hashMap, JSTaggedValue key)
206{
207    if (!TaggedHashArray::IsKey(key)) {
208        return JSTaggedValue::Undefined();
209    }
210
211    JSHandle<TaggedHashArray> hashArray(thread, hashMap->GetTable());
212    uint32_t nodeNum = hashMap->GetSize();
213    if (nodeNum == 0) {
214        return JSTaggedValue::Undefined();
215    }
216    uint32_t hash = static_cast<uint32_t>(TaggedNode::Hash(thread, key));
217    JSHandle<JSTaggedValue> removeValue(thread, hashArray->RemoveNode(thread, hash, key));
218    if (removeValue->IsHole()) {
219        return JSTaggedValue::Undefined();
220    }
221    hashMap->SetSize(--nodeNum);
222    uint32_t length = hashArray->GetLength();
223    ASSERT_PRINT(length >= TaggedHashArray::DEFAULT_INITIAL_CAPACITY,
224                 "TaggedHashArray length must greater than or equal to the default minimum value");
225
226    uint32_t index = (length - 1) & hash;
227    JSTaggedValue rootVa = hashArray->Get(index);
228    if (rootVa.IsRBTreeNode()) {
229        uint32_t numTreeNode = RBTreeNode::Count(rootVa);
230        if (numTreeNode < TaggedHashArray::UNTREEIFY_THRESHOLD) {
231            JSHandle<RBTreeNode> root(thread, rootVa);
232            JSHandle<LinkedNode> head = RBTreeNode::Detreeing(thread, root);
233            hashArray->Set(thread, index, head);
234        }
235    }
236    return removeValue.GetTaggedValue();
237}
238}
239