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 
25 namespace panda::ecmascript {
26 class LinkedHash {
27 public:
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  * */
38 template<typename Derived, typename HashObject>
39 class LinkedHashTable : public TaggedArray {
40 public:
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 
GetLengthOfTable(int numberOfElements)66     static int GetLengthOfTable(int numberOfElements)
67     {
68         return ELEMENTS_START_INDEX + numberOfElements + numberOfElements * (HashObject::ENTRY_SIZE + 1);
69     }
70 
HasSufficientCapacity(int numOfAddElements) const71     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 
FindElement(const JSThread *thread, JSTaggedValue key) const89     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 
RemoveEntry(const JSThread *thread, int entry)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 
ComputeCapacity(uint32_t atLeastSpaceFor)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 
ComputeCapacityWithShrink(int currentCapacity, int atLeastSpaceFor)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 
NumberOfElements() const149     inline int NumberOfElements() const
150     {
151         return Get(NUMBER_OF_ELEMENTS_INDEX).GetInt();
152     }
153 
NumberOfDeletedElements() const154     inline int NumberOfDeletedElements() const
155     {
156         return Get(NUMBER_OF_DELETED_ELEMENTS_INDEX).GetInt();
157     }
158 
Capacity() const159     inline int Capacity() const
160     {
161         return JSTaggedValue(Get(CAPACITY_INDEX)).GetInt();
162     }
163 
GetKey(int entry) const164     inline JSTaggedValue GetKey(int entry) const
165     {
166         int index = static_cast<int>(EntryToIndex(entry));
167         return GetElement(index);
168     }
169 
GetValue(int entry) const170     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 
IsKey(JSTaggedValue key)176     inline static bool IsKey(JSTaggedValue key)
177     {
178         return !key.IsHole();
179     }
180 
SetNumberOfElements(const JSThread *thread, int nof)181     inline void SetNumberOfElements(const JSThread *thread, int nof)
182     {
183         Set(thread, NUMBER_OF_ELEMENTS_INDEX, JSTaggedValue(nof));
184     }
185 
SetNumberOfDeletedElements(const JSThread *thread, int nod)186     inline void SetNumberOfDeletedElements(const JSThread *thread, int nod)
187     {
188         Set(thread, NUMBER_OF_DELETED_ELEMENTS_INDEX, JSTaggedValue(nod));
189     }
190 
SetCapacity(const JSThread *thread, int capacity)191     inline void SetCapacity(const JSThread *thread, int capacity)
192     {
193         Set(thread, CAPACITY_INDEX, JSTaggedValue(capacity));
194     }
195 
GetNextTable() const196     inline JSTaggedValue GetNextTable() const
197     {
198         return JSTaggedValue(Get(NEXT_TABLE_INDEX));
199     }
200 
SetNextTable(const JSThread *thread, JSTaggedValue nextTable)201     inline void SetNextTable(const JSThread *thread, JSTaggedValue nextTable)
202     {
203         Set(thread, NEXT_TABLE_INDEX, nextTable);
204     }
205 
GetDeletedElementsAt(int entry) const206     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 
Rehash(const JSThread *thread, Derived *newTable)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 
257 protected:
GetElement(int index) const258     inline JSTaggedValue GetElement(int index) const
259     {
260         ASSERT(index >= 0 && index < static_cast<int>(GetLength()));
261         return Get(index);
262     }
263 
SetElement(const JSThread *thread, int index, JSTaggedValue element)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 
SetKey(const JSThread *thread, int entry, JSTaggedValue key)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 
SetValue(const JSThread *thread, int entry, JSTaggedValue value)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 
GetNextEntry(int entry) const282     inline JSTaggedValue GetNextEntry(int entry) const
283     {
284         int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE;
285         return GetElement(index);
286     }
287 
SetNextEntry(const JSThread *thread, int entry, JSTaggedValue nextEntry)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 
HashToBucket(uint32_t hash) const294     inline uint32_t HashToBucket(uint32_t hash) const
295     {
296         return hash & static_cast<uint32_t>(Capacity() - 1);
297     }
298 
BucketToIndex(uint32_t bucket)299     inline static uint32_t BucketToIndex(uint32_t bucket)
300     {
301         return bucket + ELEMENTS_START_INDEX;
302     }
303 
304     // min entry = 0
EntryToIndex(uint32_t entry) const305     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 
InsertNewEntry(const JSThread *thread, int bucket, int entry)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 
GetDeletedNum(int entry) const318     inline int GetDeletedNum(int entry) const
319     {
320         ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
321         return GetNextEntry(entry).GetInt();
322     }
323 
SetDeletedNum(const JSThread *thread, int entry, JSTaggedValue num)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 
331 class LinkedHashMapObject {
332 public:
333     // key must be string now for other object has no 'equals' method
IsMatch(JSTaggedValue key, JSTaggedValue other)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 
343 class LinkedHashMap : public LinkedHashTable<LinkedHashMap, LinkedHashMapObject> {
344 public:
Cast(TaggedObject *obj)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 
372 class LinkedHashSetObject {
373 public:
374     // key must be string now for other object has no 'equals' method
IsMatch(JSTaggedValue key, JSTaggedValue other)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 
384 class LinkedHashSet : public LinkedHashTable<LinkedHashSet, LinkedHashSetObject> {
385 public:
Cast(TaggedObject *obj)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