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)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 FindElement(const JSThread * thread,JSTaggedValue key)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(thread, BucketToIndex(bucket)); !entry.IsHole(); 97 entry = GetNextEntry(thread, entry.GetInt())) { 98 JSTaggedValue element = GetKey(thread, entry.GetInt()); 99 if (element.IsHole()) { 100 continue; 101 } 102 if (element.IsWeak()) { 103 element.RemoveWeakTag(); 104 } 105 if (HashObject::IsMatch(thread, 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 RemoveEntryFromGCThread(int entry)123 inline void RemoveEntryFromGCThread(int entry) 124 { 125 // Skip Barrier 126 ASSERT_PRINT(entry >= 0 && entry < Capacity(), "entry must be a non-negative integer less than capacity"); 127 int index = static_cast<int>(EntryToIndex(entry)); 128 for (int i = 0; i < HashObject::ENTRY_SIZE; i++) { 129 Barriers::SetPrimitive<JSTaggedType>(GetData(), JSTaggedValue::TaggedTypeSize() * (index + i), 130 JSTaggedValue::Hole().GetRawData()); 131 } 132 JSTaggedValue newNumOfElements = JSTaggedValue(NumberOfElements() - 1); 133 JSTaggedValue newNumOfDeletedElements = JSTaggedValue(NumberOfDeletedElements() + 1); 134 Barriers::SetPrimitive<JSTaggedType>(GetData(), JSTaggedValue::TaggedTypeSize() * NUMBER_OF_ELEMENTS_INDEX, 135 newNumOfElements.GetRawData()); 136 Barriers::SetPrimitive<JSTaggedType>(GetData(), 137 JSTaggedValue::TaggedTypeSize() * NUMBER_OF_DELETED_ELEMENTS_INDEX, newNumOfDeletedElements.GetRawData()); 138 } 139 ComputeCapacity(uint32_t atLeastSpaceFor)140 inline static int ComputeCapacity(uint32_t atLeastSpaceFor) 141 { 142 // Add 50% slack to make slot collisions sufficiently unlikely. 143 // See matching computation in HashTable::HasSufficientCapacity(). 144 uint32_t rawCap = atLeastSpaceFor + (atLeastSpaceFor >> 1UL); 145 int capacity = static_cast<int>(helpers::math::GetPowerOfTwoValue32(rawCap)); 146 return (capacity > MIN_CAPACITY) ? capacity : MIN_CAPACITY; 147 } 148 ComputeCapacityWithShrink(int currentCapacity,int atLeastSpaceFor)149 inline static int ComputeCapacityWithShrink(int currentCapacity, int atLeastSpaceFor) 150 { 151 // Shrink to fit the number of elements if only a quarter of the 152 // capacity is filled with elements. 153 if (atLeastSpaceFor > (currentCapacity / 4)) { // 4: quarter 154 return currentCapacity; 155 } 156 // Recalculate the smaller capacity actually needed. 157 int newCapacity = ComputeCapacity(atLeastSpaceFor); 158 ASSERT_PRINT(newCapacity > atLeastSpaceFor, "new capacity must greater than atLeastSpaceFor"); 159 // Don't go lower than room for MIN_SHRINK_CAPACITY elements. 160 if (newCapacity < Derived::MIN_SHRINK_CAPACITY) { 161 return currentCapacity; 162 } 163 return newCapacity; 164 } 165 NumberOfElements()166 inline int NumberOfElements() const 167 { 168 return GetPrimitive(NUMBER_OF_ELEMENTS_INDEX).GetInt(); 169 } 170 NumberOfDeletedElements()171 inline int NumberOfDeletedElements() const 172 { 173 return GetPrimitive(NUMBER_OF_DELETED_ELEMENTS_INDEX).GetInt(); 174 } 175 Capacity()176 inline int Capacity() const 177 { 178 return JSTaggedValue(GetPrimitive(CAPACITY_INDEX)).GetInt(); 179 } 180 GetKey(const JSThread * thread,int entry)181 inline JSTaggedValue GetKey(const JSThread *thread, int entry) const 182 { 183 int index = static_cast<int>(EntryToIndex(entry)); 184 return GetElement(thread, index); 185 } 186 GetValue(const JSThread * thread,int entry)187 inline JSTaggedValue GetValue(const JSThread *thread, int entry) const 188 { 189 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_VALUE_INDEX; 190 return GetElement(thread, index); 191 } 192 IsKey(JSTaggedValue key)193 inline static bool IsKey(JSTaggedValue key) 194 { 195 return !key.IsHole(); 196 } 197 SetNumberOfElements(const JSThread * thread,int nof)198 inline void SetNumberOfElements(const JSThread *thread, int nof) 199 { 200 Set(thread, NUMBER_OF_ELEMENTS_INDEX, JSTaggedValue(nof)); 201 } 202 SetNumberOfDeletedElements(const JSThread * thread,int nod)203 inline void SetNumberOfDeletedElements(const JSThread *thread, int nod) 204 { 205 Set(thread, NUMBER_OF_DELETED_ELEMENTS_INDEX, JSTaggedValue(nod)); 206 } 207 SetCapacity(const JSThread * thread,int capacity)208 inline void SetCapacity(const JSThread *thread, int capacity) 209 { 210 Set(thread, CAPACITY_INDEX, JSTaggedValue(capacity)); 211 } 212 GetNextTable(const JSThread * thread)213 inline JSTaggedValue GetNextTable(const JSThread *thread) const 214 { 215 return JSTaggedValue(Get(thread, NEXT_TABLE_INDEX)); 216 } 217 SetNextTable(const JSThread * thread,JSTaggedValue nextTable)218 inline void SetNextTable(const JSThread *thread, JSTaggedValue nextTable) 219 { 220 Set(thread, NEXT_TABLE_INDEX, nextTable); 221 } 222 GetDeletedElementsAt(const JSThread * thread,int entry)223 inline int GetDeletedElementsAt(const JSThread *thread, int entry) const 224 { 225 ASSERT_PRINT(!GetNextTable(thread).IsUndefined(), "function only execute after rehash"); 226 int currentEntry = entry - 1; 227 if (NumberOfDeletedElements() == -1) { 228 return entry; 229 } 230 while (currentEntry >= 0) { 231 if (GetKey(thread, currentEntry).IsHole()) { 232 return GetDeletedNum(thread, currentEntry); 233 } 234 currentEntry--; 235 } 236 return 0; 237 } 238 Rehash(const JSThread * thread,Derived * newTable)239 inline void Rehash(const JSThread *thread, Derived *newTable) 240 { 241 ASSERT_PRINT(newTable != nullptr && newTable->Capacity() > NumberOfElements(), "can not rehash to new table"); 242 // Rehash elements to new table 243 int numberOfAllElements = NumberOfElements() + NumberOfDeletedElements(); 244 int desEntry = 0; 245 int currentDeletedElements = 0; 246 SetNextTable(thread, JSTaggedValue(newTable)); 247 for (int i = 0; i < numberOfAllElements; i++) { 248 int fromIndex = static_cast<int>(EntryToIndex(i)); 249 JSTaggedValue key = GetElement(thread, fromIndex); 250 if (key.IsHole()) { 251 // store num_of_deleted_element before entry i; it will be used when iterator update. 252 currentDeletedElements++; 253 SetDeletedNum(thread, i, JSTaggedValue(currentDeletedElements)); 254 continue; 255 } 256 257 if (key.IsWeak()) { 258 // If the key is a weak reference, we use the weak referent to calculate the new index in the new table. 259 key.RemoveWeakTag(); 260 } 261 262 int bucket = static_cast<int>(newTable->HashToBucket(LinkedHash::Hash(thread, key))); 263 newTable->InsertNewEntry(thread, bucket, desEntry); 264 int desIndex = static_cast<int>(newTable->EntryToIndex(desEntry)); 265 for (int j = 0; j < HashObject::ENTRY_SIZE; j++) { 266 newTable->SetElement(thread, desIndex + j, GetElement(thread, fromIndex + j)); 267 } 268 desEntry++; 269 } 270 newTable->SetNumberOfElements(thread, NumberOfElements()); 271 newTable->SetNumberOfDeletedElements(thread, 0); 272 } 273 274 protected: GetElement(const JSThread * thread,int index)275 inline JSTaggedValue GetElement(const JSThread *thread, int index) const 276 { 277 ASSERT(index >= 0 && index < static_cast<int>(GetLength())); 278 return Get(thread, index); 279 } 280 SetElement(const JSThread * thread,int index,JSTaggedValue element)281 inline void SetElement(const JSThread *thread, int index, JSTaggedValue element) 282 { 283 ASSERT(index >= 0 && index < static_cast<int>(GetLength())); 284 Set(thread, index, element); 285 } 286 SetKey(const JSThread * thread,int entry,JSTaggedValue key)287 inline void SetKey(const JSThread *thread, int entry, JSTaggedValue key) 288 { 289 int index = static_cast<int>(EntryToIndex(entry)); 290 SetElement(thread, index, key); 291 } 292 SetValue(const JSThread * thread,int entry,JSTaggedValue value)293 inline void SetValue(const JSThread *thread, int entry, JSTaggedValue value) 294 { 295 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_VALUE_INDEX; 296 SetElement(thread, index, value); 297 } 298 GetNextEntry(const JSThread * thread,int entry)299 inline JSTaggedValue GetNextEntry(const JSThread *thread, int entry) const 300 { 301 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE; 302 return GetElement(thread, index); 303 } 304 SetNextEntry(const JSThread * thread,int entry,JSTaggedValue nextEntry)305 inline void SetNextEntry(const JSThread *thread, int entry, JSTaggedValue nextEntry) 306 { 307 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE; 308 SetElement(thread, index, nextEntry); 309 } 310 HashToBucket(uint32_t hash)311 inline uint32_t HashToBucket(uint32_t hash) const 312 { 313 return hash & static_cast<uint32_t>(Capacity() - 1); 314 } 315 BucketToIndex(uint32_t bucket)316 inline static uint32_t BucketToIndex(uint32_t bucket) 317 { 318 return bucket + ELEMENTS_START_INDEX; 319 } 320 321 // min entry = 0 EntryToIndex(uint32_t entry)322 inline uint32_t EntryToIndex(uint32_t entry) const 323 { 324 return ELEMENTS_START_INDEX + Capacity() + static_cast<int>(entry) * (HashObject::ENTRY_SIZE + 1); 325 } 326 InsertNewEntry(const JSThread * thread,int bucket,int entry)327 inline void InsertNewEntry(const JSThread *thread, int bucket, int entry) 328 { 329 int bucketIndex = static_cast<int>(BucketToIndex(bucket)); 330 JSTaggedValue previousEntry = GetElement(thread, bucketIndex); 331 SetNextEntry(thread, entry, previousEntry); 332 SetElement(thread, bucketIndex, JSTaggedValue(entry)); 333 } 334 GetDeletedNum(const JSThread * thread,int entry)335 inline int GetDeletedNum(const JSThread *thread, int entry) const 336 { 337 ASSERT_PRINT(!GetNextTable(thread).IsUndefined(), "function only execute after rehash"); 338 return GetNextEntry(thread, entry).GetInt(); 339 } 340 SetDeletedNum(const JSThread * thread,int entry,JSTaggedValue num)341 inline void SetDeletedNum(const JSThread *thread, int entry, JSTaggedValue num) 342 { 343 ASSERT_PRINT(!GetNextTable(thread).IsUndefined(), "function only execute after rehash"); 344 SetNextEntry(thread, entry, num); 345 } 346 }; 347 348 class LinkedHashMapObject { 349 public: 350 // key must be string now for other object has no 'equals' method IsMatch(const JSThread * thread,JSTaggedValue key,JSTaggedValue other)351 static inline bool IsMatch(const JSThread *thread, JSTaggedValue key, JSTaggedValue other) 352 { 353 return JSTaggedValue::SameValueZero(thread, key, other); 354 } 355 356 static const int ENTRY_SIZE = 2; 357 static const int ENTRY_VALUE_INDEX = 1; 358 }; 359 360 class LinkedHashMap : public LinkedHashTable<LinkedHashMap, LinkedHashMapObject> { 361 public: Cast(TaggedObject * obj)362 static LinkedHashMap *Cast(TaggedObject *obj) 363 { 364 return static_cast<LinkedHashMap *>(obj); 365 } 366 static JSHandle<LinkedHashMap> PUBLIC_API Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY, 367 MemSpaceKind spaceKind = MemSpaceKind::LOCAL); 368 369 static JSHandle<LinkedHashMap> Delete(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 370 const JSHandle<JSTaggedValue> &key); 371 372 static JSHandle<LinkedHashMap> Set(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 373 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 374 375 static JSHandle<LinkedHashMap> SetWeakRef(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 376 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 377 378 JSTaggedValue Get(const JSThread *thread, JSTaggedValue key) const; 379 380 static JSHandle<LinkedHashMap> Shrink(const JSThread *thread, const JSHandle<LinkedHashMap> &table, 381 int additionalCapacity = 0); 382 383 bool Has(const JSThread *thread, JSTaggedValue key) const; 384 385 static JSHandle<LinkedHashMap> Clear(const JSThread *thread, const JSHandle<LinkedHashMap> &table); 386 387 void ClearAllDeadEntries(const JSThread *thread, std::function<bool(JSTaggedValue)> &visitor); 388 DECL_DUMP() 389 }; 390 391 class LinkedHashSetObject { 392 public: 393 // key must be string now for other object has no 'equals' method IsMatch(const JSThread * thread,JSTaggedValue key,JSTaggedValue other)394 static inline bool IsMatch(const JSThread *thread, JSTaggedValue key, JSTaggedValue other) 395 { 396 return JSTaggedValue::SameValueZero(thread, key, other); 397 } 398 399 static const int ENTRY_SIZE = 1; 400 static const int ENTRY_VALUE_INDEX = 0; 401 }; 402 403 class LinkedHashSet : public LinkedHashTable<LinkedHashSet, LinkedHashSetObject> { 404 public: Cast(TaggedObject * obj)405 static LinkedHashSet *Cast(TaggedObject *obj) 406 { 407 return static_cast<LinkedHashSet *>(obj); 408 } 409 static JSHandle<LinkedHashSet> Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY, 410 MemSpaceKind spaceKind = MemSpaceKind::LOCAL); 411 412 static JSHandle<LinkedHashSet> Delete(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 413 const JSHandle<JSTaggedValue> &key); 414 415 static JSHandle<LinkedHashSet> Add(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 416 const JSHandle<JSTaggedValue> &key); 417 418 static JSHandle<LinkedHashSet> AddWeakRef(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 419 const JSHandle<JSTaggedValue> &key); 420 421 static JSHandle<LinkedHashSet> Shrink(const JSThread *thread, const JSHandle<LinkedHashSet> &table, 422 int additionalCapacity = 0); 423 424 bool Has(const JSThread *thread, JSTaggedValue key) const; 425 426 static JSHandle<LinkedHashSet> Clear(const JSThread *thread, const JSHandle<LinkedHashSet> &table); 427 DECL_DUMP() 428 }; 429 } // namespace panda::ecmascript 430 #endif // ECMASCRIPT_LINKED_HASH_TABLE_H 431