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 if (NumberOfDeletedElements() == -1) { 206 return entry; 207 } 208 while (currentEntry >= 0) { 209 if (GetKey(currentEntry).IsHole()) { 210 return GetDeletedNum(currentEntry); 211 } 212 currentEntry--; 213 } 214 return 0; 215 } 216 Rehash(const JSThread * thread,Derived * newTable)217 inline void Rehash(const JSThread *thread, Derived *newTable) 218 { 219 ASSERT_PRINT(newTable != nullptr && newTable->Capacity() > NumberOfElements(), "can not rehash to new table"); 220 // Rehash elements to new table 221 int numberOfAllElements = NumberOfElements() + NumberOfDeletedElements(); 222 int desEntry = 0; 223 int currentDeletedElements = 0; 224 SetNextTable(thread, JSTaggedValue(newTable)); 225 for (int i = 0; i < numberOfAllElements; i++) { 226 int fromIndex = static_cast<int>(EntryToIndex(i)); 227 JSTaggedValue key = GetElement(fromIndex); 228 if (key.IsHole()) { 229 // store num_of_deleted_element before entry i; it will be used when iterator update. 230 currentDeletedElements++; 231 SetDeletedNum(thread, i, JSTaggedValue(currentDeletedElements)); 232 continue; 233 } 234 235 if (key.IsWeak()) { 236 // If the key is a weak reference, we use the weak referent to calculate the new index in the new table. 237 key.RemoveWeakTag(); 238 } 239 240 int bucket = static_cast<int>(newTable->HashToBucket(LinkedHash::Hash(key))); 241 newTable->InsertNewEntry(thread, bucket, desEntry); 242 int desIndex = static_cast<int>(newTable->EntryToIndex(desEntry)); 243 for (int j = 0; j < HashObject::ENTRY_SIZE; j++) { 244 newTable->SetElement(thread, desIndex + j, GetElement(fromIndex + j)); 245 } 246 desEntry++; 247 } 248 newTable->SetNumberOfElements(thread, NumberOfElements()); 249 newTable->SetNumberOfDeletedElements(thread, 0); 250 } 251 252 protected: GetElement(int index)253 inline JSTaggedValue GetElement(int index) const 254 { 255 ASSERT(index >= 0 && index < static_cast<int>(GetLength())); 256 return Get(index); 257 } 258 SetElement(const JSThread * thread,int index,JSTaggedValue element)259 inline void SetElement(const JSThread *thread, int index, JSTaggedValue element) 260 { 261 ASSERT(index >= 0 && index < static_cast<int>(GetLength())); 262 Set(thread, index, element); 263 } 264 SetKey(const JSThread * thread,int entry,JSTaggedValue key)265 inline void SetKey(const JSThread *thread, int entry, JSTaggedValue key) 266 { 267 int index = static_cast<int>(EntryToIndex(entry)); 268 SetElement(thread, index, key); 269 } 270 SetValue(const JSThread * thread,int entry,JSTaggedValue value)271 inline void SetValue(const JSThread *thread, int entry, JSTaggedValue value) 272 { 273 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_VALUE_INDEX; 274 SetElement(thread, index, value); 275 } 276 GetNextEntry(int entry)277 inline JSTaggedValue GetNextEntry(int entry) const 278 { 279 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE; 280 return GetElement(index); 281 } 282 SetNextEntry(const JSThread * thread,int entry,JSTaggedValue nextEntry)283 inline void SetNextEntry(const JSThread *thread, int entry, JSTaggedValue nextEntry) 284 { 285 int index = static_cast<int>(EntryToIndex(entry)) + HashObject::ENTRY_SIZE; 286 SetElement(thread, index, nextEntry); 287 } 288 HashToBucket(uint32_t hash)289 inline uint32_t HashToBucket(uint32_t hash) const 290 { 291 return hash & static_cast<uint32_t>(Capacity() - 1); 292 } 293 BucketToIndex(uint32_t bucket)294 inline static uint32_t BucketToIndex(uint32_t bucket) 295 { 296 return bucket + ELEMENTS_START_INDEX; 297 } 298 299 // min entry = 0 EntryToIndex(uint32_t entry)300 inline uint32_t EntryToIndex(uint32_t entry) const 301 { 302 return ELEMENTS_START_INDEX + Capacity() + static_cast<int>(entry) * (HashObject::ENTRY_SIZE + 1); 303 } 304 InsertNewEntry(const JSThread * thread,int bucket,int entry)305 inline void InsertNewEntry(const JSThread *thread, int bucket, int entry) 306 { 307 int bucketIndex = static_cast<int>(BucketToIndex(bucket)); 308 JSTaggedValue previousEntry = GetElement(bucketIndex); 309 SetNextEntry(thread, entry, previousEntry); 310 SetElement(thread, bucketIndex, JSTaggedValue(entry)); 311 } 312 GetDeletedNum(int entry)313 inline int GetDeletedNum(int entry) const 314 { 315 ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash"); 316 return GetNextEntry(entry).GetInt(); 317 } 318 SetDeletedNum(const JSThread * thread,int entry,JSTaggedValue num)319 inline void SetDeletedNum(const JSThread *thread, int entry, JSTaggedValue num) 320 { 321 ASSERT_PRINT(!GetNextTable().IsUndefined(), "function only execute after rehash"); 322 SetNextEntry(thread, entry, num); 323 } 324 }; 325 326 class LinkedHashMapObject { 327 public: 328 // key must be string now for other object has no 'equals' method IsMatch(JSTaggedValue key,JSTaggedValue other)329 static inline bool IsMatch(JSTaggedValue key, JSTaggedValue other) 330 { 331 return JSTaggedValue::SameValueZero(key, other); 332 } 333 334 static const int ENTRY_SIZE = 2; 335 static const int ENTRY_VALUE_INDEX = 1; 336 }; 337 338 class LinkedHashMap : public LinkedHashTable<LinkedHashMap, LinkedHashMapObject> { 339 public: Cast(TaggedObject * obj)340 static LinkedHashMap *Cast(TaggedObject *obj) 341 { 342 return static_cast<LinkedHashMap *>(obj); 343 } 344 static JSHandle<LinkedHashMap> Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 345 346 static JSHandle<LinkedHashMap> Delete(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 347 const JSHandle<JSTaggedValue> &key); 348 349 static JSHandle<LinkedHashMap> Set(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 350 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 351 352 static JSHandle<LinkedHashMap> SetWeakRef(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 353 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 354 355 JSTaggedValue Get(JSTaggedValue key) const; 356 357 static JSHandle<LinkedHashMap> Shrink(const JSThread *thread, const JSHandle<LinkedHashMap> &table, 358 int additionalCapacity = 0); 359 360 bool Has(JSTaggedValue key) const; 361 362 static JSHandle<LinkedHashMap> Clear(const JSThread *thread, const JSHandle<LinkedHashMap> &table); 363 DECL_DUMP() 364 }; 365 366 class LinkedHashSetObject { 367 public: 368 // key must be string now for other object has no 'equals' method IsMatch(JSTaggedValue key,JSTaggedValue other)369 static inline bool IsMatch(JSTaggedValue key, JSTaggedValue other) 370 { 371 return JSTaggedValue::SameValueZero(key, other); 372 } 373 374 static const int ENTRY_SIZE = 1; 375 static const int ENTRY_VALUE_INDEX = 0; 376 }; 377 378 class LinkedHashSet : public LinkedHashTable<LinkedHashSet, LinkedHashSetObject> { 379 public: Cast(TaggedObject * obj)380 static LinkedHashSet *Cast(TaggedObject *obj) 381 { 382 return static_cast<LinkedHashSet *>(obj); 383 } 384 static JSHandle<LinkedHashSet> Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 385 386 static JSHandle<LinkedHashSet> Delete(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 387 const JSHandle<JSTaggedValue> &key); 388 389 static JSHandle<LinkedHashSet> Add(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 390 const JSHandle<JSTaggedValue> &key); 391 392 static JSHandle<LinkedHashSet> AddWeakRef(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 393 const JSHandle<JSTaggedValue> &key); 394 395 static JSHandle<LinkedHashSet> Shrink(const JSThread *thread, const JSHandle<LinkedHashSet> &table, 396 int additionalCapacity = 0); 397 398 bool Has(JSTaggedValue key) const; 399 400 static JSHandle<LinkedHashSet> Clear(const JSThread *thread, const JSHandle<LinkedHashSet> &table); 401 DECL_DUMP() 402 }; 403 } // namespace panda::ecmascript 404 #endif // ECMASCRIPT_LINKED_HASH_TABLE_H 405