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 "js_handle.h" 21 #include "js_symbol.h" 22 #include "js_tagged_number.h" 23 #include "tagged_array.h" 24 25 namespace panda::ecmascript { 26 /** 27 * memory in LinkedHashTable is divided into 3 parts 28 * 1.array[0-2] is used to store common information of hashtale such as numberOfElements and capacity 29 * 2.array[3,3+capacity] is buckets which store the position of entry 30 * 3.array[3+capacity+1,3+capacity + capacity*(entry_size+1)] is the entry stored in order, the last element of an entry 31 * is a number which point to next entry. 32 * */ 33 template<typename Derived, typename HashObject> 34 class LinkedHashTable : public TaggedArray { 35 public: 36 static const int MIN_CAPACITY = 4; 37 static const int NUMBER_OF_ELEMENTS_INDEX = 0; 38 static const int NUMBER_OF_DELETED_ELEMENTS_INDEX = 1; 39 static const int CAPACITY_INDEX = 2; 40 static const int NEXT_TABLE_INDEX = 3; 41 static const int ELEMENTS_START_INDEX = 4; 42 // Don't shrink a HashTable below this capacity. 43 static const int MIN_SHRINK_CAPACITY = 16; 44 45 static JSHandle<Derived> Create(const JSThread *thread, int numberOfElements); 46 47 static JSHandle<Derived> Insert(const JSThread *thread, const JSHandle<Derived> &table, 48 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 49 50 static JSHandle<Derived> InsertWeakRef(const JSThread *thread, const JSHandle<Derived> &table, 51 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 52 53 static JSHandle<Derived> GrowCapacity(const JSThread *thread, const JSHandle<Derived> &table, 54 int numberOfAddedElements = 1); 55 56 static JSHandle<Derived> Remove(const JSThread *thread, const JSHandle<Derived> &table, 57 const JSHandle<JSTaggedValue> &key); 58 59 static JSHandle<Derived> Shrink(const JSThread *thread, const JSHandle<Derived> &table, int additionalCapacity = 0); 60 61 void Rehash(const JSThread *thread, Derived *newTable); 62 63 inline bool HasSufficientCapacity(int numOfAddElements) const; 64 65 inline int FindElement(JSTaggedValue key) const; 66 67 inline void RemoveEntry(const JSThread *thread, int entry); 68 69 inline static int ComputeCapacity(uint32_t atLeastSpaceFor); 70 71 inline static int ComputeCapacityWithShrink(int currentCapacity, int atLeastSpaceFor); 72 73 inline int NumberOfElements() const; 74 75 inline int NumberOfDeletedElements() const; 76 77 inline int Capacity() const; 78 79 inline JSTaggedValue GetKey(int entry) const; 80 81 inline JSTaggedValue GetValue(int entry) const; 82 IsKey(JSTaggedValue key)83 inline static bool IsKey(JSTaggedValue key) 84 { 85 return !key.IsHole(); 86 } 87 88 inline void SetNumberOfElements(const JSThread *thread, int nof); 89 90 inline void SetNumberOfDeletedElements(const JSThread *thread, int nod); 91 92 inline void SetCapacity(const JSThread *thread, int capacity); 93 94 inline JSTaggedValue GetNextTable() const; 95 96 inline void SetNextTable(const JSThread *thread, JSTaggedValue nextTable); 97 98 inline int GetDeletedElementsAt(int entry) const; 99 100 protected: 101 inline JSTaggedValue GetElement(int index) const; 102 103 inline void SetElement(const JSThread *thread, int index, JSTaggedValue element); 104 105 inline void SetKey(const JSThread *thread, int entry, JSTaggedValue key); 106 107 inline void SetValue(const JSThread *thread, int entry, JSTaggedValue value); 108 109 inline JSTaggedValue GetNextEntry(int entry) const; 110 111 inline void SetNextEntry(const JSThread *thread, int entry, JSTaggedValue nextEntry); 112 113 inline uint32_t HashToBucket(uint32_t hash) const; 114 115 inline static uint32_t BucketToIndex(uint32_t bucket); 116 117 // min entry = 0 118 inline uint32_t EntryToIndex(uint32_t entry) const; 119 120 inline void InsertNewEntry(const JSThread *thread, int bucket, int entry); 121 122 inline int GetDeletedNum(int entry) const; 123 124 inline void SetDeletedNum(const JSThread *thread, int entry, JSTaggedValue num); 125 }; 126 127 class LinkedHash { 128 public: 129 static int Hash(JSTaggedValue key); 130 }; 131 132 class LinkedHashMapObject { 133 public: 134 // key must be string now for other object has no 'equals' method 135 static inline bool IsMatch(JSTaggedValue key, JSTaggedValue other); 136 137 static const int ENTRY_SIZE = 2; 138 static const int ENTRY_VALUE_INDEX = 1; 139 }; 140 141 class LinkedHashMap : public LinkedHashTable<LinkedHashMap, LinkedHashMapObject> { 142 public: Cast(ObjectHeader * obj)143 static LinkedHashMap *Cast(ObjectHeader *obj) 144 { 145 return static_cast<LinkedHashMap *>(obj); 146 } 147 static JSHandle<LinkedHashMap> Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 148 149 static JSHandle<LinkedHashMap> Delete(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 150 const JSHandle<JSTaggedValue> &key); 151 152 static JSHandle<LinkedHashMap> Set(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 153 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 154 155 static JSHandle<LinkedHashMap> SetWeakRef(const JSThread *thread, const JSHandle<LinkedHashMap> &obj, 156 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 157 158 JSTaggedValue Get(JSTaggedValue key) const; 159 160 static JSHandle<LinkedHashMap> Shrink(const JSThread *thread, const JSHandle<LinkedHashMap> &table, 161 int additionalCapacity = 0); 162 163 bool Has(JSTaggedValue key) const; 164 165 void Clear(const JSThread *thread); 166 DECL_DUMP() 167 }; 168 169 class LinkedHashSetObject { 170 public: 171 // key must be string now for other object has no 'equals' method IsMatch(JSTaggedValue key,JSTaggedValue other)172 static inline bool IsMatch(JSTaggedValue key, JSTaggedValue other) 173 { 174 return JSTaggedValue::SameValueZero(key, other); 175 } 176 177 static const int ENTRY_SIZE = 1; 178 static const int ENTRY_VALUE_INDEX = 0; 179 }; 180 181 class LinkedHashSet : public LinkedHashTable<LinkedHashSet, LinkedHashSetObject> { 182 public: Cast(ObjectHeader * obj)183 static LinkedHashSet *Cast(ObjectHeader *obj) 184 { 185 return static_cast<LinkedHashSet *>(obj); 186 } 187 static JSHandle<LinkedHashSet> Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 188 189 static JSHandle<LinkedHashSet> Delete(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 190 const JSHandle<JSTaggedValue> &key); 191 192 static JSHandle<LinkedHashSet> Add(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 193 const JSHandle<JSTaggedValue> &key); 194 195 static JSHandle<LinkedHashSet> AddWeakRef(const JSThread *thread, const JSHandle<LinkedHashSet> &obj, 196 const JSHandle<JSTaggedValue> &key); 197 198 static JSHandle<LinkedHashSet> Shrink(const JSThread *thread, const JSHandle<LinkedHashSet> &table, 199 int additionalCapacity = 0); 200 201 bool Has(JSTaggedValue key) const; 202 203 void Clear(const JSThread *thread); 204 DECL_DUMP() 205 }; 206 } // namespace panda::ecmascript 207 #endif // ECMASCRIPT_LINKED_HASH_TABLE_H 208