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