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