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_TRANSITIONS_DICTIONARY_H 17 #define ECMASCRIPT_TRANSITIONS_DICTIONARY_H 18 19 #include "ecmascript/accessor_data.h" 20 #include "ecmascript/js_symbol.h" 21 #include "ecmascript/js_tagged_number.h" 22 #include "ecmascript/tagged_hash_table.h" 23 24 namespace panda::ecmascript { 25 class TransitionsDictionary : public TaggedHashTable<TransitionsDictionary> { 26 public: 27 using HashTableT = TaggedHashTable<TransitionsDictionary>; IsMatch(const JSTaggedValue & key,const JSTaggedValue & otherKey)28 static inline bool IsMatch([[maybe_unused]] const JSTaggedValue &key, 29 [[maybe_unused]] const JSTaggedValue &otherKey) 30 { 31 LOG_ECMA(FATAL) << "this branch is unreachable"; 32 UNREACHABLE(); 33 } Hash(const JSTaggedValue & key)34 static inline int Hash([[maybe_unused]] const JSTaggedValue &key) 35 { 36 LOG_ECMA(FATAL) << "this branch is unreachable"; 37 UNREACHABLE(); 38 } 39 IsMatch(const JSTaggedValue & key,const JSTaggedValue & metaData,const JSTaggedValue & otherKey,const JSTaggedValue & otherDetails)40 static inline bool IsMatch(const JSTaggedValue &key, const JSTaggedValue &metaData, const JSTaggedValue &otherKey, 41 const JSTaggedValue &otherDetails) 42 { 43 return key == otherKey && metaData == otherDetails; 44 } 45 Hash(const JSTaggedValue & key,const JSTaggedValue & metaData)46 static inline int Hash(const JSTaggedValue &key, const JSTaggedValue &metaData) 47 { 48 ASSERT(key.IsStringOrSymbol()); 49 50 uint32_t hash = 0; 51 if (key.IsString()) { 52 hash = EcmaStringAccessor(key).GetHashcode(); 53 } else if (key.IsSymbol()) { 54 hash = JSSymbol::Cast(key.GetTaggedObject())->GetHashField(); 55 } 56 int metaDataHash = metaData.IsInt() ? metaData.GetInt() : static_cast<int>(metaData.GetRawData()); 57 return static_cast<int>(hash) + metaDataHash; 58 } 59 GetKeyIndex(int entry)60 inline static int GetKeyIndex(int entry) 61 { 62 return HashTableT::TABLE_HEADER_SIZE + entry * GetEntrySize() + ENTRY_KEY_INDEX; 63 } GetValueIndex(int entry)64 inline static int GetValueIndex(int entry) 65 { 66 return HashTableT::TABLE_HEADER_SIZE + entry * GetEntrySize() + ENTRY_VALUE_INDEX; 67 } GetEntryIndex(int entry)68 inline static int GetEntryIndex(int entry) 69 { 70 return HashTableT::TABLE_HEADER_SIZE + entry * GetEntrySize(); 71 } GetEntrySize()72 inline static int GetEntrySize() 73 { 74 return ENTRY_SIZE; 75 } 76 Cast(TaggedObject * object)77 static TransitionsDictionary *Cast(TaggedObject *object) 78 { 79 return reinterpret_cast<TransitionsDictionary *>(object); 80 } 81 82 static constexpr int DEFAULT_ELEMENTS_NUMBER = 16; 83 static JSHandle<TransitionsDictionary> Create(const JSThread *thread, 84 int numberOfElements = DEFAULT_ELEMENTS_NUMBER) 85 { 86 return HashTableT::Create(thread, numberOfElements); 87 } 88 89 // Attempt to shrink the dictionary after deletion of key. Shrink(const JSThread * thread,const JSHandle<TransitionsDictionary> & dictionary)90 inline static JSHandle<TransitionsDictionary> Shrink(const JSThread *thread, 91 const JSHandle<TransitionsDictionary> &dictionary) 92 { 93 return HashTableT::Shrink(thread, dictionary, 0); 94 } 95 GetAttributes(int entry)96 inline JSTaggedValue GetAttributes(int entry) const 97 { 98 int index = GetEntryIndex(entry) + ENTRY_DETAILS_INDEX; 99 return HashTableT::Get(index); 100 } 101 SetAttributes(const JSThread * thread,int entry,JSTaggedValue metaData)102 inline void SetAttributes(const JSThread *thread, int entry, JSTaggedValue metaData) 103 { 104 int index = GetEntryIndex(entry) + ENTRY_DETAILS_INDEX; 105 HashTableT::Set(thread, index, metaData); 106 } 107 SetEntry(const JSThread * thread,int entry,const JSTaggedValue & key,const JSTaggedValue & value,const JSTaggedValue & metaData)108 inline void SetEntry(const JSThread *thread, int entry, const JSTaggedValue &key, const JSTaggedValue &value, 109 const JSTaggedValue &metaData) 110 { 111 SetKey(thread, entry, key); 112 JSTaggedValue weakValue = JSTaggedValue(value.CreateAndGetWeakRef()); 113 SetValue(thread, entry, weakValue); 114 if (!metaData.IsHeapObject()) { 115 SetAttributes(thread, entry, metaData); 116 return; 117 } 118 JSTaggedValue weakMetaData = JSTaggedValue(metaData.CreateAndGetWeakRef()); 119 SetAttributes(thread, entry, weakMetaData); 120 } 121 RemoveElement(const JSThread * thread,int entry)122 inline void RemoveElement(const JSThread *thread, int entry) 123 { 124 SetKey(thread, entry, JSTaggedValue::Hole()); 125 SetValue(thread, entry, JSTaggedValue::Hole()); 126 SetAttributes(thread, entry, JSTaggedValue::Hole()); 127 IncreaseHoleEntriesCount(thread); 128 } 129 130 int FindEntry(const JSTaggedValue &key, const JSTaggedValue &metaData); 131 template <typename Callback> IterateEntryValue(Callback callback)132 void IterateEntryValue(Callback callback) 133 { 134 auto number = EntriesCount(); 135 int size = Size(); 136 int hasIteratedNum = 0; 137 for (int entry = 0; entry < size; entry++) { 138 JSTaggedValue ret = GetValue(entry); 139 if (ret.IsWeak()) { 140 auto next = ret.GetTaggedWeakRef(); 141 callback(JSHClass::Cast(next)); 142 hasIteratedNum++; 143 if (hasIteratedNum >= number) { 144 return; 145 } 146 } 147 } 148 } 149 static JSHandle<TransitionsDictionary> PutIfAbsent(const JSThread *thread, 150 const JSHandle<TransitionsDictionary> &dictionary, 151 const JSHandle<JSTaggedValue> &key, 152 const JSHandle<JSTaggedValue> &value, 153 const JSHandle<JSTaggedValue> &metaData); 154 // For test 155 static JSHandle<TransitionsDictionary> Remove(const JSThread *thread, const JSHandle<TransitionsDictionary> &table, 156 const JSHandle<JSTaggedValue> &key, const JSTaggedValue &metaData); 157 void Rehash(const JSThread *thread, TransitionsDictionary *newTable); 158 CheckWeakExist(const JSTaggedValue & value)159 static bool CheckWeakExist(const JSTaggedValue &value) 160 { 161 if (value == JSTaggedValue::Undefined()) { 162 return false; 163 } 164 return true; 165 } 166 ComputeCompactSize(const JSHandle<TransitionsDictionary> & table,int computeHashTableSize,int tableSize,int addedElements)167 static int ComputeCompactSize(const JSHandle<TransitionsDictionary> &table, int computeHashTableSize, 168 int tableSize, int addedElements) 169 { 170 int realEntryCount = 0; 171 for (int i = 0; i < tableSize; i++) { 172 // value is weak reference, if not use will be set undefined. 173 if (TransitionsDictionary::CheckWeakExist(table->GetValue(i))) { 174 realEntryCount++; 175 } 176 } 177 return std::min(computeHashTableSize, 178 static_cast<int>(helpers::math::GetPowerOfTwoValue32(realEntryCount + addedElements) * HASH_TABLE_BUFFER)); 179 } 180 181 static constexpr int ENTRY_SIZE = 3; 182 static constexpr int ENTRY_KEY_INDEX = 0; 183 static constexpr int ENTRY_VALUE_INDEX = 1; 184 static constexpr int ENTRY_DETAILS_INDEX = 2; 185 static constexpr int HASH_TABLE_BUFFER = 2; 186 DECL_DUMP() 187 }; 188 } // namespace panda::ecmascript 189 #endif 190