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/tagged_hash_array.h"
17
18 #include "ecmascript/base/number_helper.h"
19 #include "ecmascript/js_handle.h"
20 #include "ecmascript/object_factory.h"
21 #include "ecmascript/tagged_queue.h"
22
23 namespace panda::ecmascript {
Create(const JSThread * thread,uint32_t numberOfElements)24 JSTaggedValue TaggedHashArray::Create(const JSThread *thread, uint32_t numberOfElements)
25 {
26 ASSERT_PRINT(numberOfElements > 0, "size must be a non-negative integer");
27 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
28 JSHandle<TaggedHashArray> tableArray = factory->NewTaggedHashArray(numberOfElements);
29 return tableArray.GetTaggedValue();
30 }
31
Clear(JSThread * thread)32 void TaggedHashArray::Clear(JSThread *thread)
33 {
34 for (uint32_t i = 0; i < GetLength(); ++i) {
35 Set(thread, i, JSTaggedValue::Hole());
36 }
37 }
38
GetNode(JSThread * thread,int hash,JSTaggedValue key)39 JSTaggedValue TaggedHashArray::GetNode(JSThread *thread, int hash, JSTaggedValue key)
40 {
41 uint32_t nodeLength = GetLength();
42 JSTaggedValue nodeValue = Get(((nodeLength - 1) & hash));
43 if (nodeValue.IsHole()) {
44 return JSTaggedValue::Hole();
45 }
46 if (nodeValue.IsRBTreeNode()) {
47 JSHandle<JSTaggedValue> node(thread, nodeValue);
48 JSHandle<JSTaggedValue> handleKey(thread, key);
49 return RBTreeNode::GetTreeNode(thread, node, hash, handleKey);
50 } else {
51 JSTaggedValue nextNodeVa = nodeValue;
52 JSTaggedValue findKey = JSTaggedValue::Hole();
53 while (!nextNodeVa.IsHole()) {
54 LinkedNode *nextNode = LinkedNode::Cast(nextNodeVa.GetTaggedObject());
55 findKey = nextNode->GetKey();
56 if (nextNode->GetHash().GetInt() == hash && (!key.IsHole() && JSTaggedValue::SameValue(key, findKey))) {
57 return nextNodeVa;
58 }
59 nextNodeVa = nextNode->GetNext();
60 }
61 }
62 return JSTaggedValue::Hole();
63 }
64
NewLinkedNode(JSThread * thread,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value)65 JSHandle<LinkedNode> TaggedHashArray::NewLinkedNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key,
66 JSHandle<JSTaggedValue> value)
67 {
68 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
69 JSHandle<LinkedNode> hole(thread, JSTaggedValue::Hole());
70 return factory->NewLinkedNode(hash, key, value, hole);
71 }
72
CreateLinkedNodeFrom(JSThread * thread,JSHandle<RBTreeNode> treeNode)73 JSHandle<LinkedNode> TaggedHashArray::CreateLinkedNodeFrom(JSThread *thread, JSHandle<RBTreeNode> treeNode)
74 {
75 JSHandle<JSTaggedValue> key(thread, treeNode->GetKey());
76 JSHandle<JSTaggedValue> value(thread, treeNode->GetValue());
77 return NewLinkedNode(thread, treeNode->GetHash().GetInt(), key, value);
78 }
79
NewTreeNode(JSThread * thread,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value)80 JSHandle<RBTreeNode> TaggedHashArray::NewTreeNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key,
81 JSHandle<JSTaggedValue> value)
82 {
83 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
84 return factory->NewTreeNode(hash, key, value);
85 }
86
CreateTreeNodeFrom(JSThread * thread,JSHandle<LinkedNode> linkedNode)87 JSHandle<RBTreeNode> TaggedHashArray::CreateTreeNodeFrom(JSThread *thread, JSHandle<LinkedNode> linkedNode)
88 {
89 JSHandle<JSTaggedValue> key(thread, linkedNode->GetKey());
90 JSHandle<JSTaggedValue> value(thread, linkedNode->GetValue());
91 return NewTreeNode(thread, linkedNode->GetHash().GetInt(), key, value);
92 }
93
TreeingBin(JSThread * thread,const JSHandle<TaggedHashArray> & tab,int hash)94 void TaggedHashArray::TreeingBin(JSThread *thread, const JSHandle<TaggedHashArray> &tab, int hash)
95 {
96 uint32_t length = tab->GetLength();
97 uint32_t index = (length - 1) & hash;
98 JSTaggedValue nodeVa = tab->Get(index);
99 if (!nodeVa.IsHole()) {
100 JSHandle<LinkedNode> node(thread, nodeVa);
101 JSHandle<RBTreeNode> root = LinkedNode::Treeing(thread, node);
102 tab->Set(thread, index, root);
103 }
104 }
105
Resize(JSThread * thread,const JSHandle<TaggedHashArray> & oldTab,uint32_t Capacity)106 JSHandle<TaggedHashArray> TaggedHashArray::Resize(JSThread *thread, const JSHandle<TaggedHashArray> &oldTab,
107 uint32_t Capacity)
108 {
109 uint32_t oldCapacity = oldTab->GetLength();
110 if (oldCapacity >= MAXIMUM_CAPACITY) {
111 return oldTab;
112 }
113 uint32_t newCapacity = Capacity << 1;
114 JSTaggedValue newTabValue = Create(thread, newCapacity);
115 JSHandle<TaggedHashArray> newTab(thread, newTabValue);
116 JSMutableHandle<JSTaggedValue> oldValue(thread, JSTaggedValue::Undefined());
117 for (uint32_t j = 0; j < oldCapacity; ++j) {
118 oldValue.Update(oldTab->Get(j));
119 if (oldValue->IsHole()) {
120 continue;
121 } else if (oldValue->IsRBTreeNode()) {
122 RBTreeNode::Divide(thread, newTab, oldValue, j, oldCapacity);
123 } else if (oldValue->IsLinkedNode()) {
124 LinkedNode *node = LinkedNode::Cast(oldValue.GetTaggedValue().GetTaggedObject());
125 if (node->GetNext().IsHole()) {
126 int newhash = (node->GetHash().GetInt()) & (newCapacity - 1);
127 newTab->Set(thread, newhash, JSTaggedValue(node));
128 } else { // preserve order
129 NodeDisperse(thread, newTab, oldValue.GetTaggedValue(), j, oldCapacity);
130 }
131 }
132 }
133 return newTab;
134 }
135
NodeDisperse(JSThread * thread,const JSHandle<TaggedHashArray> & newTab,JSTaggedValue nodeVa,int index,int oldCapacity)136 void TaggedHashArray::NodeDisperse(JSThread *thread, const JSHandle<TaggedHashArray> &newTab,
137 JSTaggedValue nodeVa, int index, int oldCapacity)
138 {
139 JSTaggedValue loHead = JSTaggedValue::Hole();
140 JSTaggedValue loTail = JSTaggedValue::Hole();
141 JSTaggedValue hiHead = JSTaggedValue::Hole();
142 JSTaggedValue hiTail = JSTaggedValue::Hole();
143 JSTaggedValue next = JSTaggedValue::Hole();
144 do {
145 next = LinkedNode::Cast(nodeVa.GetTaggedObject())->GetNext();
146 if (((LinkedNode::Cast(nodeVa.GetTaggedObject())->GetHash().GetInt()) & oldCapacity) == 0) {
147 if (loTail.IsHole()) {
148 loHead = nodeVa;
149 } else {
150 LinkedNode::Cast(loTail.GetTaggedObject())->SetNext(thread, nodeVa);
151 }
152 loTail = nodeVa;
153 } else {
154 if (hiTail.IsHole()) {
155 hiHead = nodeVa;
156 } else {
157 LinkedNode::Cast(hiTail.GetTaggedObject())->SetNext(thread, nodeVa);
158 }
159 hiTail = nodeVa;
160 }
161 nodeVa = next;
162 } while (!(next.IsHole()));
163 if (!loTail.IsHole()) {
164 LinkedNode::Cast(loTail.GetTaggedObject())->SetNext(thread, JSTaggedValue::Hole());
165 newTab->Set(thread, index, loHead);
166 }
167 if (!hiTail.IsHole()) {
168 LinkedNode::Cast(hiTail.GetTaggedObject())->SetNext(thread, JSTaggedValue::Hole());
169 newTab->Set(thread, index + oldCapacity, hiHead);
170 }
171 }
172
SetVal(JSThread * thread,JSHandle<TaggedHashArray> table,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value)173 JSTaggedValue TaggedHashArray::SetVal(JSThread *thread, JSHandle<TaggedHashArray> table, int hash,
174 JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value)
175 {
176 uint32_t length = table->GetLength();
177 uint32_t index = (length - 1) & hash;
178 JSHandle<JSTaggedValue> node(thread, table->Get(index));
179 if (node->IsHole()) {
180 JSHandle<LinkedNode> newNode = TaggedHashArray::NewLinkedNode(thread, hash, key, value);
181 table->Set(thread, index, newNode.GetTaggedValue());
182 return JSTaggedValue::True();
183 } else if (node->IsLinkedNode()) {
184 JSMutableHandle<LinkedNode> root(thread, JSTaggedValue::Undefined());
185 uint32_t count = 0;
186 JSMutableHandle<JSTaggedValue> currentKey(thread, JSTaggedValue::Undefined());
187 JSMutableHandle<JSTaggedValue> nextVal(thread, node.GetTaggedValue());
188 do {
189 root.Update(nextVal);
190 currentKey.Update(root->GetKey());
191 if (root->GetHash().GetInt() == hash && (!key->IsHole() &&
192 JSTaggedValue::Equal(thread, key, currentKey))) {
193 root->SetValue(thread, value.GetTaggedValue());
194 return JSTaggedValue::Undefined();
195 }
196 nextVal.Update(root->GetNext());
197 count++;
198 } while (!nextVal->IsHole());
199 JSHandle<LinkedNode> newNode = TaggedHashArray::NewLinkedNode(thread, hash, key, value);
200 root->SetNext(thread, newNode);
201 table->Set(thread, index, node.GetTaggedValue());
202 if (count >= TREEIFY_THRESHOLD - 1) {
203 TaggedHashArray::TreeingBin(thread, table, hash);
204 }
205 return JSTaggedValue::True();
206 } else if (node->IsRBTreeNode()) {
207 JSHandle<RBTreeNode> root = JSHandle<RBTreeNode>::Cast(node);
208 uint32_t curCount = root->GetCount();
209 JSHandle<RBTreeNode> changeNode = RBTreeNode::Set(thread, root, hash, key, value);
210 changeNode->SetIsRed(thread, JSTaggedValue(false));
211 table->Set(thread, index, changeNode);
212 uint32_t updateCount = changeNode->GetCount();
213 if (curCount == updateCount) {
214 return JSTaggedValue::Undefined();
215 }
216 return JSTaggedValue::True();
217 }
218 return JSTaggedValue::Undefined();
219 }
220
RemoveNode(JSThread * thread,int hash,JSTaggedValue key)221 JSTaggedValue TaggedHashArray::RemoveNode(JSThread *thread, int hash, JSTaggedValue key)
222 {
223 uint32_t length = GetLength();
224 uint32_t index = (length - 1) & hash;
225 JSTaggedValue node = Get(index);
226 if (node.IsHole()) {
227 return JSTaggedValue::Hole();
228 } else if (node.IsLinkedNode()) {
229 LinkedNode *head = LinkedNode::Cast(node.GetTaggedObject());
230 JSTaggedValue newKey = head->GetKey();
231 if (head->GetHash().GetInt() == hash && (!key.IsHole() && JSTaggedValue::SameValue(key, newKey))) {
232 Set(thread, index, head->GetNext());
233 return head->GetValue();
234 }
235 JSTaggedValue nodeNextVa = head->GetNext();
236 LinkedNode *previousNode = head;
237 while (!nodeNextVa.IsHole()) {
238 LinkedNode *nodeNext = LinkedNode::Cast(nodeNextVa.GetTaggedObject());
239 newKey = nodeNext->GetKey();
240 if (nodeNext->GetHash().GetInt() == hash && (!key.IsHole() && JSTaggedValue::SameValue(key, newKey))) {
241 previousNode->SetNext(thread, nodeNext->GetNext());
242 Set(thread, index, node);
243 return nodeNext->GetValue();
244 }
245 previousNode = LinkedNode::Cast(nodeNextVa.GetTaggedObject());
246 nodeNextVa = nodeNext->GetNext();
247 }
248 } else if (node.IsRBTreeNode()) {
249 JSTaggedValue oldValue = JSTaggedValue::Hole();
250 JSTaggedValue rootTreeNodeVa = RBTreeNode::Delete(thread, node, hash, key, oldValue);
251 if (!rootTreeNodeVa.IsHole()) {
252 Set(thread, index, rootTreeNodeVa);
253 return oldValue;
254 }
255 }
256 return JSTaggedValue::Hole();
257 }
258
GetCurrentNode(JSThread * thread,JSMutableHandle<TaggedQueue> & queue,const JSHandle<TaggedHashArray> & tableArr,uint32_t & index)259 JSHandle<JSTaggedValue> TaggedHashArray::GetCurrentNode(JSThread *thread, JSMutableHandle<TaggedQueue> &queue,
260 const JSHandle<TaggedHashArray> &tableArr, uint32_t &index)
261 {
262 JSMutableHandle<JSTaggedValue> rootValue(thread, JSTaggedValue::Undefined());
263 if (queue->Empty()) {
264 rootValue.Update(tableArr->Get(index));
265 if (rootValue->IsHole()) {
266 ++index;
267 return rootValue;
268 }
269 } else {
270 rootValue.Update(queue->Pop(thread));
271 }
272 if (rootValue->IsRBTreeNode()) {
273 JSHandle<RBTreeNode> root = JSHandle<RBTreeNode>::Cast(rootValue);
274 if (!root->GetLeft().IsHole()) {
275 JSHandle<JSTaggedValue> left(thread, root->GetLeft());
276 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, left)));
277 }
278 if (!root->GetRight().IsHole()) {
279 JSHandle<JSTaggedValue> right(thread, root->GetRight());
280 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, right)));
281 }
282 } else {
283 JSHandle<LinkedNode> root = JSHandle<LinkedNode>::Cast(rootValue);
284 if (!root->GetNext().IsHole()) {
285 JSHandle<JSTaggedValue> next(thread, root->GetNext());
286 queue.Update(JSTaggedValue(TaggedQueue::Push(thread, queue, next)));
287 }
288 }
289 if (queue->Empty()) {
290 ++index;
291 }
292 return rootValue;
293 }
294 } // namespace panda::ecmascript
295