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#ifndef ECMASCRIPT_LINKED_HASH_TABLE_H
17#define ECMASCRIPT_LINKED_HASH_TABLE_H
18
19#include "ecmascript/js_tagged_value.h"
20#include "ecmascript/js_handle.h"
21#include "ecmascript/js_symbol.h"
22#include "ecmascript/js_tagged_number.h"
23#include "ecmascript/tagged_array-inl.h"
24
25namespace panda::ecmascript {
26class LinkedHash {
27public:
28    static int Hash(const JSThread *thread, JSTaggedValue key);
29};
30
31/**
32 * memory in LinkedHashTable is divided into 3 parts
33 * 1.array[0-2] is used to store common information of hashtale such as numberOfElements and capacity
34 * 2.array[3,3+capacity] is buckets which store the position of entry
35 * 3.array[3+capacity+1,3+capacity + capacity*(entry_size+1)] is the entry stored in order, the last element of an entry
36 * is a number which point to next entry.
37 * */
38template<typename Derived, typename HashObject>
39class LinkedHashTable : public TaggedArray {
40public:
41    static const int MIN_CAPACITY = 4;
42    static const int NUMBER_OF_ELEMENTS_INDEX = 0;
43    static const int NUMBER_OF_DELETED_ELEMENTS_INDEX = 1;
44    static const int CAPACITY_INDEX = 2;
45    static const int NEXT_TABLE_INDEX = 3;
46    static const int ELEMENTS_START_INDEX = 4;
47    // Don't shrink a HashTable below this capacity.
48    static const int MIN_SHRINK_CAPACITY = 16;
49
50    static JSHandle<Derived> Create(const JSThread *thread, int numberOfElements, MemSpaceKind spaceKind);
51
52    static JSHandle<Derived> Insert(const JSThread *thread, const JSHandle<Derived> &table,
53                                    const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value);
54
55    static JSHandle<Derived> InsertWeakRef(const JSThread *thread, const JSHandle<Derived> &table,
56                                           const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value);
57
58    static JSHandle<Derived> GrowCapacity(const JSThread *thread, const JSHandle<Derived> &table,
59                                          int numberOfAddedElements = 1);
60
61    static JSHandle<Derived> Remove(const JSThread *thread, const JSHandle<Derived> &table,
62                                    const JSHandle<JSTaggedValue> &key);
63
64    static JSHandle<Derived> Shrink(const JSThread *thread, const JSHandle<Derived> &table, int additionalCapacity = 0);
65
66    static int GetLengthOfTable(int numberOfElements)
67    {
68        return ELEMENTS_START_INDEX + numberOfElements + numberOfElements * (HashObject::ENTRY_SIZE + 1);
69    }
70
71    inline bool HasSufficientCapacity(int numOfAddElements) const
72    {
73        int numberOfElements = NumberOfElements();
74        int numOfDelElements = NumberOfDeletedElements();
75        int capacity = Capacity();
76        int nof = numberOfElements + numOfAddElements;
77        // Return true if:
78        //   50% is still free after adding numOfAddElements elements and
79        //   at most 50% of the free elements are deleted elements.
80        if ((nof < capacity) && ((numOfDelElements <= (capacity - nof) / 2))) {  // 2: half
81            int neededFree = nof / 2;                                            // 2: half
82            if (nof + neededFree <= capacity) {
83                return true;
84            }
85        }
86        return false;
87    }
88
89    inline int FindElement(const JSThread *thread, JSTaggedValue key) const
90    {
91        if (!IsKey(key)) {
92            return -1;
93        }
94        int hash = LinkedHash::Hash(thread, key);
95        uint32_t bucket = HashToBucket(hash);
96        for (JSTaggedValue entry = GetElement(BucketToIndex(bucket)); !entry.IsHole();
97            entry = GetNextEntry(entry.GetInt())) {
98            JSTaggedValue element = GetKey(entry.GetInt());
99            if (element.IsHole()) {
100                continue;
101            }
102            if (element.IsWeak()) {
103                element.RemoveWeakTag();
104            }
105            if (HashObject::IsMatch(key, element)) {
106                return entry.GetInt();
107            }
108        }
109        return -1;
110    }
111
112    inline void RemoveEntry(const JSThread *thread, int entry)
113    {
114        ASSERT_PRINT(entry >= 0 && entry < Capacity(), "entry must be a non-negative integer less than capacity");
115        int index = static_cast<int>(EntryToIndex(entry));
116        for (int i = 0; i < HashObject::ENTRY_SIZE; i++) {
117            SetElement(thread, index + i, JSTaggedValue::Hole());
118        }
119        SetNumberOfElements(thread, NumberOfElements() - 1);
120        SetNumberOfDeletedElements(thread, NumberOfDeletedElements() + 1);
121    }
122
123    inline static int ComputeCapacity(uint32_t atLeastSpaceFor)
124    {
125        // Add 50% slack to make slot collisions sufficiently unlikely.
126        // See matching computation in HashTable::HasSufficientCapacity().
127        uint32_t rawCap = atLeastSpaceFor + (atLeastSpaceFor >> 1UL);
128        int capacity = static_cast<int>(helpers::math::GetPowerOfTwoValue32(rawCap));
129        return (capacity > MIN_CAPACITY) ? capacity : MIN_CAPACITY;
130    }
131
132    inline static int ComputeCapacityWithShrink(int currentCapacity, int atLeastSpaceFor)
133    {
134        // Shrink to fit the number of elements if only a quarter of the
135        // capacity is filled with elements.
136        if (atLeastSpaceFor > (currentCapacity / 4)) {  // 4: quarter
137            return currentCapacity;
138        }
139        // Recalculate the smaller capacity actually needed.
140        int newCapacity = ComputeCapacity(atLeastSpaceFor);
141        ASSERT_PRINT(newCapacity > atLeastSpaceFor, "new capacity must greater than atLeastSpaceFor");
142        // Don't go lower than room for MIN_SHRINK_CAPACITY elements.
143        if (newCapacity < Derived::MIN_SHRINK_CAPACITY) {
144            return currentCapacity;
145        }
146        return newCapacity;
147    }
148
149    inline int NumberOfElements() const
150    {
151        return Get(NUMBER_OF_ELEMENTS_INDEX).GetInt();
152    }
153
154    inline int NumberOfDeletedElements() const
155    {
156        return Get(NUMBER_OF_DELETED_ELEMENTS_INDEX).GetInt();
157    }
158
159    inline int Capacity() const
160    {
161        return JSTaggedValue(Get(CAPACITY_INDEX)).GetInt();
162    }
163
164    inline JSTaggedValue GetKey(int entry) const
165    {
166        int index = static_cast<int>(EntryToIndex(entry));
167        return GetElement(index);
168    }
169
170    inline JSTaggedValue GetValue(int entry) const
171    {
172        int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_VALUE_INDEX;
173        return GetElement(index);
174    }
175
176    inline static bool IsKey(JSTaggedValue key)
177    {
178        return !key.IsHole();
179    }
180
181    inline void SetNumberOfElements(const JSThread *thread, int nof)
182    {
183        Set(thread, NUMBER_OF_ELEMENTS_INDEX, JSTaggedValue(nof));
184    }
185
186    inline void SetNumberOfDeletedElements(const JSThread *thread, int nod)
187    {
188        Set(thread, NUMBER_OF_DELETED_ELEMENTS_INDEX, JSTaggedValue(nod));
189    }
190
191    inline void SetCapacity(const JSThread *thread, int capacity)
192    {
193        Set(thread, CAPACITY_INDEX, JSTaggedValue(capacity));
194    }
195
196    inline JSTaggedValue GetNextTable() const
197    {
198        return JSTaggedValue(Get(NEXT_TABLE_INDEX));
199    }
200
201    inline void SetNextTable(const JSThread *thread, JSTaggedValue nextTable)
202    {
203        Set(thread, NEXT_TABLE_INDEX, nextTable);
204    }
205
206    inline int GetDeletedElementsAt(int entry) const
207    {
208        ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
209        int currentEntry = entry - 1;
210        if (NumberOfDeletedElements() == -1) {
211            return entry;
212        }
213        while (currentEntry >= 0) {
214            if (GetKey(currentEntry).IsHole()) {
215                return GetDeletedNum(currentEntry);
216            }
217            currentEntry--;
218        }
219        return 0;
220    }
221
222    inline void Rehash(const JSThread *thread, Derived *newTable)
223    {
224        ASSERT_PRINT(newTable != nullptr && newTable->Capacity() > NumberOfElements(), "can not rehash to new table");
225        // Rehash elements to new table
226        int numberOfAllElements = NumberOfElements() + NumberOfDeletedElements();
227        int desEntry = 0;
228        int currentDeletedElements = 0;
229        SetNextTable(thread, JSTaggedValue(newTable));
230        for (int i = 0; i < numberOfAllElements; i++) {
231            int fromIndex = static_cast<int>(EntryToIndex(i));
232            JSTaggedValue key = GetElement(fromIndex);
233            if (key.IsHole()) {
234                // store num_of_deleted_element before entry i; it will be used when iterator update.
235                currentDeletedElements++;
236                SetDeletedNum(thread, i, JSTaggedValue(currentDeletedElements));
237                continue;
238            }
239
240            if (key.IsWeak()) {
241                // If the key is a weak reference, we use the weak referent to calculate the new index in the new table.
242                key.RemoveWeakTag();
243            }
244
245            int bucket = static_cast<int>(newTable->HashToBucket(LinkedHash::Hash(thread, key)));
246            newTable->InsertNewEntry(thread, bucket, desEntry);
247            int desIndex = static_cast<int>(newTable->EntryToIndex(desEntry));
248            for (int j = 0; j < HashObject::ENTRY_SIZE; j++) {
249                newTable->SetElement(thread, desIndex + j, GetElement(fromIndex + j));
250            }
251            desEntry++;
252        }
253        newTable->SetNumberOfElements(thread, NumberOfElements());
254        newTable->SetNumberOfDeletedElements(thread, 0);
255    }
256
257protected:
258    inline JSTaggedValue GetElement(int index) const
259    {
260        ASSERT(index >= 0 && index < static_cast<int>(GetLength()));
261        return Get(index);
262    }
263
264    inline void SetElement(const JSThread *thread, int index, JSTaggedValue element)
265    {
266        ASSERT(index >= 0 && index < static_cast<int>(GetLength()));
267        Set(thread, index, element);
268    }
269
270    inline void SetKey(const JSThread *thread, int entry, JSTaggedValue key)
271    {
272        int index = static_cast<int>(EntryToIndex(entry));
273        SetElement(thread, index, key);
274    }
275
276    inline void SetValue(const JSThread *thread, int entry, JSTaggedValue value)
277    {
278        int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_VALUE_INDEX;
279        SetElement(thread, index, value);
280    }
281
282    inline JSTaggedValue GetNextEntry(int entry) const
283    {
284        int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE;
285        return GetElement(index);
286    }
287
288    inline void SetNextEntry(const JSThread *thread, int entry, JSTaggedValue nextEntry)
289    {
290        int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE;
291        SetElement(thread, index, nextEntry);
292    }
293
294    inline uint32_t HashToBucket(uint32_t hash) const
295    {
296        return hash & static_cast<uint32_t>(Capacity() - 1);
297    }
298
299    inline static uint32_t BucketToIndex(uint32_t bucket)
300    {
301        return bucket + ELEMENTS_START_INDEX;
302    }
303
304    // min entry = 0
305    inline uint32_t EntryToIndex(uint32_t entry) const
306    {
307        return ELEMENTS_START_INDEX + Capacity() + static_cast<int>(entry) * (HashObject::ENTRY_SIZE + 1);
308    }
309
310    inline void InsertNewEntry(const JSThread *thread, int bucket, int entry)
311    {
312        int bucketIndex = static_cast<int>(BucketToIndex(bucket));
313        JSTaggedValue previousEntry = GetElement(bucketIndex);
314        SetNextEntry(thread, entry, previousEntry);
315        SetElement(thread, bucketIndex, JSTaggedValue(entry));
316    }
317
318    inline int GetDeletedNum(int entry) const
319    {
320        ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
321        return GetNextEntry(entry).GetInt();
322    }
323
324    inline void SetDeletedNum(const JSThread *thread, int entry, JSTaggedValue num)
325    {
326        ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
327        SetNextEntry(thread, entry, num);
328    }
329};
330
331class LinkedHashMapObject {
332public:
333    // key must be string now for other object has no 'equals' method
334    static inline bool IsMatch(JSTaggedValue key, JSTaggedValue other)
335    {
336        return JSTaggedValue::SameValueZero(key, other);
337    }
338
339    static const int ENTRY_SIZE = 2;
340    static const int ENTRY_VALUE_INDEX = 1;
341};
342
343class LinkedHashMap : public LinkedHashTable<LinkedHashMap, LinkedHashMapObject> {
344public:
345    static LinkedHashMap *Cast(TaggedObject *obj)
346    {
347        return static_cast<LinkedHashMap *>(obj);
348    }
349    static JSHandle<LinkedHashMap> PUBLIC_API Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY,
350        MemSpaceKind spaceKind = MemSpaceKind::LOCAL);
351
352    static JSHandle<LinkedHashMap> Delete(const JSThread *thread, const JSHandle<LinkedHashMap> &obj,
353        const JSHandle<JSTaggedValue> &key);
354
355    static JSHandle<LinkedHashMap> Set(const JSThread *thread, const JSHandle<LinkedHashMap> &obj,
356        const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value);
357
358    static JSHandle<LinkedHashMap> SetWeakRef(const JSThread *thread, const JSHandle<LinkedHashMap> &obj,
359        const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value);
360
361    JSTaggedValue Get(const JSThread *thread, JSTaggedValue key) const;
362
363    static JSHandle<LinkedHashMap> Shrink(const JSThread *thread, const JSHandle<LinkedHashMap> &table,
364        int additionalCapacity = 0);
365
366    bool Has(const JSThread *thread, JSTaggedValue key) const;
367
368    static JSHandle<LinkedHashMap> Clear(const JSThread *thread, const JSHandle<LinkedHashMap> &table);
369    DECL_DUMP()
370};
371
372class LinkedHashSetObject {
373public:
374    // key must be string now for other object has no 'equals' method
375    static inline bool IsMatch(JSTaggedValue key, JSTaggedValue other)
376    {
377        return JSTaggedValue::SameValueZero(key, other);
378    }
379
380    static const int ENTRY_SIZE = 1;
381    static const int ENTRY_VALUE_INDEX = 0;
382};
383
384class LinkedHashSet : public LinkedHashTable<LinkedHashSet, LinkedHashSetObject> {
385public:
386    static LinkedHashSet *Cast(TaggedObject *obj)
387    {
388        return static_cast<LinkedHashSet *>(obj);
389    }
390    static JSHandle<LinkedHashSet> Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY,
391        MemSpaceKind spaceKind = MemSpaceKind::LOCAL);
392
393    static JSHandle<LinkedHashSet> Delete(const JSThread *thread, const JSHandle<LinkedHashSet> &obj,
394        const JSHandle<JSTaggedValue> &key);
395
396    static JSHandle<LinkedHashSet> Add(const JSThread *thread, const JSHandle<LinkedHashSet> &obj,
397        const JSHandle<JSTaggedValue> &key);
398
399    static JSHandle<LinkedHashSet> AddWeakRef(const JSThread *thread, const JSHandle<LinkedHashSet> &obj,
400        const JSHandle<JSTaggedValue> &key);
401
402    static JSHandle<LinkedHashSet> Shrink(const JSThread *thread, const JSHandle<LinkedHashSet> &table,
403        int additionalCapacity = 0);
404
405    bool Has(const JSThread *thread, JSTaggedValue key) const;
406
407    static JSHandle<LinkedHashSet> Clear(const JSThread *thread, const JSHandle<LinkedHashSet> &table);
408    DECL_DUMP()
409};
410}  // namespace panda::ecmascript
411#endif  // ECMASCRIPT_LINKED_HASH_TABLE_H
412