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