1/*
2 * Copyright (c) 2021 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/linked_hash_table.h"
17
18#include "ecmascript/js_object-inl.h"
19
20namespace panda::ecmascript {
21template<typename Derived, typename HashObject>
22JSHandle<Derived> LinkedHashTable<Derived, HashObject>::Create(const JSThread *thread,
23    int numberOfElements, MemSpaceKind spaceKind)
24{
25    ASSERT_PRINT(numberOfElements > 0, "size must be a non-negative integer");
26    ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
27    auto capacity = static_cast<uint32_t>(numberOfElements);
28    ASSERT_PRINT(helpers::math::IsPowerOfTwo(capacity), "capacity must be pow of '2'");
29    int length = ELEMENTS_START_INDEX + numberOfElements + numberOfElements * (HashObject::ENTRY_SIZE + 1);
30    JSHandle<Derived> table;
31    if (spaceKind == MemSpaceKind::SHARED) {
32        table = JSHandle<Derived>(factory->NewSOldSpaceTaggedArray(length));
33    } else {
34        table = JSHandle<Derived>(factory->NewTaggedArray(length));
35    }
36    table->SetNumberOfElements(thread, 0);
37    table->SetNumberOfDeletedElements(thread, 0);
38    table->SetCapacity(thread, capacity);
39    return table;
40}
41
42template<typename Derived, typename HashObject>
43JSHandle<Derived> LinkedHashTable<Derived, HashObject>::Insert(const JSThread *thread, const JSHandle<Derived> &table,
44                                                               const JSHandle<JSTaggedValue> &key,
45                                                               const JSHandle<JSTaggedValue> &value)
46{
47    ASSERT(IsKey(key.GetTaggedValue()));
48    int hash = LinkedHash::Hash(thread, key.GetTaggedValue());
49    int entry = table->FindElement(thread, key.GetTaggedValue());
50    if (entry != -1) {
51        table->SetValue(thread, entry, value.GetTaggedValue());
52        return table;
53    }
54
55    JSHandle<Derived> newTable = GrowCapacity(thread, table);
56
57    uint32_t bucket = newTable->HashToBucket(hash);
58    entry = newTable->NumberOfElements() + newTable->NumberOfDeletedElements();
59    newTable->InsertNewEntry(thread, bucket, entry);
60    newTable->SetKey(thread, entry, key.GetTaggedValue());
61    newTable->SetValue(thread, entry, value.GetTaggedValue());
62    newTable->SetNumberOfElements(thread, newTable->NumberOfElements() + 1);
63
64    return newTable;
65}
66
67template<typename Derived, typename HashObject>
68JSHandle<Derived> LinkedHashTable<Derived, HashObject>::InsertWeakRef(const JSThread *thread,
69    const JSHandle<Derived> &table, const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value)
70{
71    ALLOW_LOCAL_TO_SHARE_WEAK_REF_HANDLE;
72    ASSERT(IsKey(key.GetTaggedValue()));
73    int hash = LinkedHash::Hash(thread, key.GetTaggedValue());
74    int entry = table->FindElement(thread, key.GetTaggedValue());
75    if (entry != -1) {
76        table->SetValue(thread, entry, value.GetTaggedValue());
77        return table;
78    }
79
80    JSHandle<Derived> newTable = GrowCapacity(thread, table);
81
82    uint32_t bucket = newTable->HashToBucket(hash);
83    entry = newTable->NumberOfElements() + newTable->NumberOfDeletedElements();
84    newTable->InsertNewEntry(thread, bucket, entry);
85    JSTaggedValue weakKey(key->CreateAndGetWeakRef());
86    newTable->SetKey(thread, entry, weakKey);
87    // The ENTRY_VALUE_INDEX of LinkedHashSet is 0. SetValue will cause the overwitten key.
88    if (std::is_same_v<LinkedHashMap, Derived>) {
89        newTable->SetValue(thread, entry, value.GetTaggedValue());
90    }
91    newTable->SetNumberOfElements(thread, newTable->NumberOfElements() + 1);
92
93    return newTable;
94}
95
96template<typename Derived, typename HashObject>
97JSHandle<Derived> LinkedHashTable<Derived, HashObject>::GrowCapacity(const JSThread *thread,
98    const JSHandle<Derived> &table, int numberOfAddedElements)
99{
100    if (table->HasSufficientCapacity(numberOfAddedElements)) {
101        return table;
102    }
103    int newCapacity = ComputeCapacity(table->NumberOfElements() + numberOfAddedElements);
104    JSHandle<Derived> newTable = Create(thread, newCapacity,
105        table.GetTaggedValue().IsInSharedHeap() ? MemSpaceKind::SHARED : MemSpaceKind::LOCAL);
106    table->Rehash(thread, *newTable);
107    return newTable;
108}
109
110template<typename Derived, typename HashObject>
111JSHandle<Derived> LinkedHashTable<Derived, HashObject>::Remove(const JSThread *thread, const JSHandle<Derived> &table,
112                                                               const JSHandle<JSTaggedValue> &key)
113{
114    int entry = table->FindElement(thread, key.GetTaggedValue());
115    if (entry == -1) {
116        return table;
117    }
118
119    table->RemoveEntry(thread, entry);
120    return Shrink(thread, table);
121}
122
123template<typename Derived, typename HashObject>
124JSHandle<Derived> LinkedHashTable<Derived, HashObject>::Shrink(const JSThread *thread, const JSHandle<Derived> &table,
125    int additionalCapacity)
126{
127    int newCapacity = ComputeCapacityWithShrink(table->Capacity(), table->NumberOfElements() + additionalCapacity);
128    if (newCapacity == table->Capacity()) {
129        return table;
130    }
131
132    JSHandle<Derived> newTable = Create(thread, newCapacity,
133        table.GetTaggedValue().IsInSharedHeap() ? MemSpaceKind::SHARED : MemSpaceKind::LOCAL);
134
135    table->Rehash(thread, *newTable);
136    return newTable;
137}
138
139// LinkedHashMap
140JSHandle<LinkedHashMap> LinkedHashMap::Create(const JSThread *thread, int numberOfElements, MemSpaceKind spaceKind)
141{
142    return LinkedHashTable<LinkedHashMap, LinkedHashMapObject>::Create(thread, numberOfElements, spaceKind);
143}
144
145JSHandle<LinkedHashMap> LinkedHashMap::Delete(const JSThread *thread, const JSHandle<LinkedHashMap> &obj,
146                                              const JSHandle<JSTaggedValue> &key)
147{
148    return LinkedHashTable<LinkedHashMap, LinkedHashMapObject>::Remove(thread, obj, key);
149}
150
151JSHandle<LinkedHashMap> LinkedHashMap::Set(const JSThread *thread, const JSHandle<LinkedHashMap> &obj,
152    const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value)
153{
154    return LinkedHashTable<LinkedHashMap, LinkedHashMapObject>::Insert(thread, obj, key, value);
155}
156
157JSHandle<LinkedHashMap> LinkedHashMap::SetWeakRef(const JSThread *thread, const JSHandle<LinkedHashMap> &obj,
158    const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value)
159{
160    return LinkedHashTable<LinkedHashMap, LinkedHashMapObject>::InsertWeakRef(thread, obj, key, value);
161}
162
163JSTaggedValue LinkedHashMap::Get(const JSThread *thread, JSTaggedValue key) const
164{
165    int entry = FindElement(thread, key);
166    if (entry == -1) {
167        return JSTaggedValue::Undefined();
168    }
169    return GetValue(entry);
170}
171
172bool LinkedHashMap::Has(const JSThread *thread, JSTaggedValue key) const
173{
174    int entry = FindElement(thread, key);
175    return entry != -1;
176}
177
178JSHandle<LinkedHashMap> LinkedHashMap::Clear(const JSThread *thread, const JSHandle<LinkedHashMap> &table)
179{
180    if (table->Capacity() == LinkedHashMap::MIN_CAPACITY) {
181        table->FillRangeWithSpecialValue(JSTaggedValue::Hole(), LinkedHashMap::ELEMENTS_START_INDEX,
182                                         table->GetLength());
183        table->SetNumberOfDeletedElements(thread, table->NumberOfDeletedElements() + table->NumberOfElements());
184        table->SetNumberOfElements(thread, 0);
185        return table;
186    }
187    JSHandle<LinkedHashMap> newMap = LinkedHashMap::Create(thread, LinkedHashMap::MIN_CAPACITY,
188        table.GetTaggedValue().IsInSharedHeap() ? MemSpaceKind::SHARED : MemSpaceKind::LOCAL);
189    if (table->Capacity() > 0) {
190        table->SetNextTable(thread, newMap.GetTaggedValue());
191        table->SetNumberOfDeletedElements(thread, -1);
192    }
193    return newMap;
194}
195
196JSHandle<LinkedHashMap> LinkedHashMap::Shrink(const JSThread *thread, const JSHandle<LinkedHashMap> &table,
197                                              int additionalCapacity)
198{
199    return LinkedHashTable<LinkedHashMap, LinkedHashMapObject>::Shrink(thread, table, additionalCapacity);
200}
201
202// LinkedHashSet
203JSHandle<LinkedHashSet> LinkedHashSet::Create(const JSThread *thread, int numberOfElements, MemSpaceKind spaceKind)
204{
205    return LinkedHashTable<LinkedHashSet, LinkedHashSetObject>::Create(thread, numberOfElements, spaceKind);
206}
207
208JSHandle<LinkedHashSet> LinkedHashSet::Delete(const JSThread *thread, const JSHandle<LinkedHashSet> &obj,
209                                              const JSHandle<JSTaggedValue> &key)
210{
211    return LinkedHashTable<LinkedHashSet, LinkedHashSetObject>::Remove(thread, obj, key);
212}
213
214JSHandle<LinkedHashSet> LinkedHashSet::Add(const JSThread *thread, const JSHandle<LinkedHashSet> &obj,
215                                           const JSHandle<JSTaggedValue> &key)
216{
217    return LinkedHashTable<LinkedHashSet, LinkedHashSetObject>::Insert(thread, obj, key, key);
218}
219
220JSHandle<LinkedHashSet> LinkedHashSet::AddWeakRef(const JSThread *thread, const JSHandle<LinkedHashSet> &obj,
221    const JSHandle<JSTaggedValue> &key)
222{
223    return LinkedHashTable<LinkedHashSet, LinkedHashSetObject>::InsertWeakRef(thread, obj, key, key);
224}
225
226bool LinkedHashSet::Has(const JSThread *thread, JSTaggedValue key) const
227{
228    int entry = FindElement(thread, key);
229    return entry != -1;
230}
231
232JSHandle<LinkedHashSet> LinkedHashSet::Clear(const JSThread *thread, const JSHandle<LinkedHashSet> &table)
233{
234    if (table->Capacity() == LinkedHashSet::MIN_CAPACITY) {
235        table->FillRangeWithSpecialValue(JSTaggedValue::Hole(), LinkedHashSet::ELEMENTS_START_INDEX,
236                                         table->GetLength());
237        table->SetNumberOfDeletedElements(thread, table->NumberOfDeletedElements() + table->NumberOfElements());
238        table->SetNumberOfElements(thread, 0);
239        return table;
240    }
241    JSHandle<LinkedHashSet> newSet = LinkedHashSet::Create(thread, LinkedHashSet::MIN_CAPACITY,
242        table.GetTaggedValue().IsInSharedHeap() ? MemSpaceKind::SHARED : MemSpaceKind::LOCAL);
243    if (table->Capacity() > 0) {
244        table->SetNextTable(thread, newSet.GetTaggedValue());
245        table->SetNumberOfDeletedElements(thread, -1);
246    }
247    return newSet;
248}
249
250JSHandle<LinkedHashSet> LinkedHashSet::Shrink(const JSThread *thread, const JSHandle<LinkedHashSet> &table,
251    int additionalCapacity)
252{
253    return LinkedHashTable<LinkedHashSet, LinkedHashSetObject>::Shrink(thread, table, additionalCapacity);
254}
255
256int LinkedHash::Hash(const JSThread *thread, JSTaggedValue key)
257{
258    if (key.IsInt()) {
259        return key.GetInt();
260    }
261    if (key.IsSymbol()) {
262        auto symbolString = JSSymbol::Cast(key.GetTaggedObject());
263        return symbolString->GetHashField();
264    }
265    if (key.IsString()) {
266        auto keyString = reinterpret_cast<EcmaString *>(key.GetTaggedObject());
267        return EcmaStringAccessor(keyString).GetHashcode();
268    }
269    if (key.IsECMAObject()) {
270        int32_t hash = ECMAObject::Cast(key.GetTaggedObject())->GetHash();
271        if (hash == 0) {
272            hash = base::RandomGenerator::GenerateIdentityHash();
273            JSHandle<ECMAObject> ecmaObj(thread, key);
274            ECMAObject::SetHash(thread, hash, ecmaObj);
275        }
276        return hash;
277    }
278    if (key.IsBigInt()) {
279        uint32_t keyValue = BigInt::Cast(key.GetTaggedObject())->GetDigit(0);
280        return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t));
281    }
282    // Int, Double, Special and HeapObject(except symbol and string)
283    if (key.IsDouble()) {
284        key = JSTaggedValue::TryCastDoubleToInt32(key.GetDouble());
285        if (key.IsInt()) {
286            return key.GetInt();
287        }
288    }
289    uint64_t keyValue = key.GetRawData();
290    return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t));
291}
292}  // namespace panda::ecmascript
293