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_INL_H
17 #define ECMASCRIPT_LINKED_HASH_TABLE_INL_H
18
19 #include "linked_hash_table.h"
20 #include "tagged_array-inl.h"
21 #include "utils/bit_utils.h"
22
23 namespace panda::ecmascript {
24 template<typename Derived, typename HashObject>
GetElement(int index)25 JSTaggedValue LinkedHashTable<Derived, HashObject>::GetElement(int index) const
26 {
27 ASSERT(index >= 0 && index < static_cast<int>(GetLength()));
28 return Get(index);
29 }
30
31 template<typename Derived, typename HashObject>
SetElement(const JSThread * thread,int index,JSTaggedValue element)32 void LinkedHashTable<Derived, HashObject>::SetElement(const JSThread *thread, int index, JSTaggedValue element)
33 {
34 ASSERT(index >= 0 && index < static_cast<int>(GetLength()));
35 Set(thread, index, element);
36 }
37
38 template<typename Derived, typename HashObject>
NumberOfElements()39 int LinkedHashTable<Derived, HashObject>::NumberOfElements() const
40 {
41 return Get(NUMBER_OF_ELEMENTS_INDEX).GetInt();
42 }
43
44 template<typename Derived, typename HashObject>
NumberOfDeletedElements()45 int LinkedHashTable<Derived, HashObject>::NumberOfDeletedElements() const
46 {
47 return Get(NUMBER_OF_DELETED_ELEMENTS_INDEX).GetInt();
48 }
49
50 template<typename Derived, typename HashObject>
Capacity()51 int LinkedHashTable<Derived, HashObject>::Capacity() const
52 {
53 return JSTaggedValue(Get(CAPACITY_INDEX)).GetInt();
54 }
55
56 template<typename Derived, typename HashObject>
SetNumberOfElements(const JSThread * thread,int nof)57 void LinkedHashTable<Derived, HashObject>::SetNumberOfElements(const JSThread *thread, int nof)
58 {
59 Set(thread, NUMBER_OF_ELEMENTS_INDEX, JSTaggedValue(nof));
60 }
61
62 template<typename Derived, typename HashObject>
SetNumberOfDeletedElements(const JSThread * thread,int nod)63 void LinkedHashTable<Derived, HashObject>::SetNumberOfDeletedElements(const JSThread *thread, int nod)
64 {
65 Set(thread, NUMBER_OF_DELETED_ELEMENTS_INDEX, JSTaggedValue(nod));
66 }
67
68 template<typename Derived, typename HashObject>
SetCapacity(const JSThread * thread,int capacity)69 void LinkedHashTable<Derived, HashObject>::SetCapacity(const JSThread *thread, int capacity)
70 {
71 Set(thread, CAPACITY_INDEX, JSTaggedValue(capacity));
72 }
73
74 template<typename Derived, typename HashObject>
SetNextTable(const JSThread * thread,JSTaggedValue nextTable)75 void LinkedHashTable<Derived, HashObject>::SetNextTable(const JSThread *thread, JSTaggedValue nextTable)
76 {
77 Set(thread, NEXT_TABLE_INDEX, nextTable);
78 }
79
80 template<typename Derived, typename HashObject>
GetNextTable()81 JSTaggedValue LinkedHashTable<Derived, HashObject>::GetNextTable() const
82 {
83 return JSTaggedValue(Get(NEXT_TABLE_INDEX));
84 }
85
86 template<typename Derived, typename HashObject>
GetDeletedNum(int entry)87 int LinkedHashTable<Derived, HashObject>::GetDeletedNum(int entry) const
88 {
89 ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
90 return GetNextEntry(entry).GetInt();
91 }
92
93 template<typename Derived, typename HashObject>
SetDeletedNum(const JSThread * thread,int entry,JSTaggedValue num)94 void LinkedHashTable<Derived, HashObject>::SetDeletedNum(const JSThread *thread, int entry, JSTaggedValue num)
95 {
96 ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
97 SetNextEntry(thread, entry, num);
98 }
99
100 template<typename Derived, typename HashObject>
GetDeletedElementsAt(int entry)101 int LinkedHashTable<Derived, HashObject>::GetDeletedElementsAt(int entry) const
102 {
103 ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash");
104 int currentEntry = entry - 1;
105 while (currentEntry >= 0) {
106 if (GetKey(currentEntry).IsHole()) {
107 return GetDeletedNum(currentEntry);
108 }
109 currentEntry--;
110 }
111 return 0;
112 }
113
114 template<typename Derived, typename HashObject>
HashToBucket(uint32_t hash)115 uint32_t LinkedHashTable<Derived, HashObject>::HashToBucket(uint32_t hash) const
116 {
117 return hash & static_cast<uint32_t>(Capacity() - 1);
118 }
119
120 template<typename Derived, typename HashObject>
BucketToIndex(uint32_t bucket)121 uint32_t LinkedHashTable<Derived, HashObject>::BucketToIndex(uint32_t bucket)
122 {
123 return bucket + ELEMENTS_START_INDEX;
124 }
125
126 template<typename Derived, typename HashObject>
EntryToIndex(uint32_t entry)127 uint32_t LinkedHashTable<Derived, HashObject>::EntryToIndex(uint32_t entry) const
128 {
129 return ELEMENTS_START_INDEX + Capacity() + entry * (HashObject::ENTRY_SIZE + 1);
130 }
131
132 template<typename Derived, typename HashObject>
SetKey(const JSThread * thread,int entry,JSTaggedValue key)133 void LinkedHashTable<Derived, HashObject>::SetKey(const JSThread *thread, int entry, JSTaggedValue key)
134 {
135 int index = EntryToIndex(entry);
136 SetElement(thread, index, key);
137 }
138
139 template<typename Derived, typename HashObject>
GetKey(int entry)140 JSTaggedValue LinkedHashTable<Derived, HashObject>::GetKey(int entry) const
141 {
142 int index = EntryToIndex(entry);
143 return GetElement(index);
144 }
145
146 template<typename Derived, typename HashObject>
GetValue(int entry)147 JSTaggedValue LinkedHashTable<Derived, HashObject>::GetValue(int entry) const
148 {
149 int index = EntryToIndex(entry) + HashObject::ENTRY_VALUE_INDEX;
150 return GetElement(index);
151 }
152
153 template<typename Derived, typename HashObject>
SetValue(const JSThread * thread,int entry,JSTaggedValue value)154 void LinkedHashTable<Derived, HashObject>::SetValue(const JSThread *thread, int entry, JSTaggedValue value)
155 {
156 int index = EntryToIndex(entry) + HashObject::ENTRY_VALUE_INDEX;
157 SetElement(thread, index, value);
158 }
159
160 template<typename Derived, typename HashObject>
GetNextEntry(int entry)161 JSTaggedValue LinkedHashTable<Derived, HashObject>::GetNextEntry(int entry) const
162 {
163 int index = EntryToIndex(entry) + HashObject::ENTRY_SIZE;
164 return GetElement(index);
165 }
166
167 template<typename Derived, typename HashObject>
SetNextEntry(const JSThread * thread,int entry,JSTaggedValue nextEntry)168 void LinkedHashTable<Derived, HashObject>::SetNextEntry(const JSThread *thread, int entry, JSTaggedValue nextEntry)
169 {
170 int index = EntryToIndex(entry) + HashObject::ENTRY_SIZE;
171 SetElement(thread, index, nextEntry);
172 }
173
174 template<typename Derived, typename HashObject>
InsertNewEntry(const JSThread * thread,int bucket,int entry)175 void LinkedHashTable<Derived, HashObject>::InsertNewEntry(const JSThread *thread, int bucket, int entry)
176 {
177 int bucketIndex = BucketToIndex(bucket);
178 JSTaggedValue previousEntry = GetElement(bucketIndex);
179 SetNextEntry(thread, entry, previousEntry);
180 SetElement(thread, bucketIndex, JSTaggedValue(entry));
181 }
182
183 template<typename Derived, typename HashObject>
FindElement(JSTaggedValue key)184 int LinkedHashTable<Derived, HashObject>::FindElement(JSTaggedValue key) const
185 {
186 if (!IsKey(key)) {
187 return -1;
188 }
189 int hash = LinkedHash::Hash(key);
190 int bucket = HashToBucket(hash);
191 for (JSTaggedValue entry = GetElement(BucketToIndex(bucket)); !entry.IsHole();
192 entry = GetNextEntry(entry.GetInt())) {
193 JSTaggedValue element = GetKey(entry.GetInt());
194 if (element.IsHole()) {
195 continue;
196 }
197 if (element.IsWeak()) {
198 element.RemoveWeakTag();
199 }
200 if (HashObject::IsMatch(key, element)) {
201 return entry.GetInt();
202 }
203 }
204 return -1;
205 } // namespace panda::ecmascript
206
207 template<typename Derived, typename HashObject>
HasSufficientCapacity(int numOfAddElements)208 bool LinkedHashTable<Derived, HashObject>::HasSufficientCapacity(int numOfAddElements) const
209 {
210 int numberOfElements = NumberOfElements();
211 int numOfDelElements = NumberOfDeletedElements();
212 int capacity = Capacity();
213 int nof = numberOfElements + numOfAddElements;
214 // Return true if:
215 // 50% is still free after adding numOfAddElements elements and
216 // at most 50% of the free elements are deleted elements.
217 if ((nof < capacity) && ((numOfDelElements <= (capacity - nof) / 2))) { // 2: half
218 int neededFree = nof / 2; // 2: half
219 if (nof + neededFree <= capacity) {
220 return true;
221 }
222 }
223 return false;
224 }
225
226 template<typename Derived, typename HashObject>
ComputeCapacity(uint32_t atLeastSpaceFor)227 int LinkedHashTable<Derived, HashObject>::ComputeCapacity(uint32_t atLeastSpaceFor)
228 {
229 // Add 50% slack to make slot collisions sufficiently unlikely.
230 // See matching computation in HashTable::HasSufficientCapacity().
231 uint32_t rawCap = atLeastSpaceFor + (atLeastSpaceFor >> 1UL);
232 int capacity = static_cast<int>(helpers::math::GetPowerOfTwoValue32(rawCap));
233 return (capacity > MIN_CAPACITY) ? capacity : MIN_CAPACITY;
234 }
235
236 template<typename Derived, typename HashObject>
RemoveEntry(const JSThread * thread,int entry)237 void LinkedHashTable<Derived, HashObject>::RemoveEntry(const JSThread *thread, int entry)
238 {
239 ASSERT_PRINT(entry >= 0 && entry < Capacity(), "entry must be a non-negative integer less than capacity");
240 int index = EntryToIndex(entry);
241 for (int i = 0; i < HashObject::ENTRY_SIZE; i++) {
242 SetElement(thread, index + i, JSTaggedValue::Hole());
243 }
244 SetNumberOfElements(thread, NumberOfElements() - 1);
245 SetNumberOfDeletedElements(thread, NumberOfDeletedElements() + 1);
246 }
247
248 template<typename Derived, typename HashObject>
ComputeCapacityWithShrink(int currentCapacity,int atLeastSpaceFor)249 int LinkedHashTable<Derived, HashObject>::ComputeCapacityWithShrink(int currentCapacity, int atLeastSpaceFor)
250 {
251 // Shrink to fit the number of elements if only a quarter of the
252 // capacity is filled with elements.
253 if (atLeastSpaceFor > (currentCapacity / 4)) { // 4: quarter
254 return currentCapacity;
255 }
256 // Recalculate the smaller capacity actually needed.
257 int newCapacity = ComputeCapacity(atLeastSpaceFor);
258 ASSERT_PRINT(newCapacity > atLeastSpaceFor, "new capacity must greater than atLeastSpaceFor");
259 // Don't go lower than room for MIN_SHRINK_CAPACITY elements.
260 if (newCapacity < Derived::MIN_SHRINK_CAPACITY) {
261 return currentCapacity;
262 }
263 return newCapacity;
264 }
265
IsMatch(JSTaggedValue key,JSTaggedValue other)266 bool LinkedHashMapObject::IsMatch(JSTaggedValue key, JSTaggedValue other)
267 {
268 return JSTaggedValue::SameValueZero(key, other);
269 }
270 } // namespace panda::ecmascript
271 #endif // ECMASCRIPT_LINKED_HASH_TABLE_INL_H
272