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