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_TAGGED_TREE_H 17 #define ECMASCRIPT_TAGGED_TREE_H 18 19 #include "ecmascript/js_tagged_value.h" 20 #include "js_handle.h" 21 #include "tagged_array.h" 22 23 namespace panda::ecmascript { 24 enum TreeColor : uint8_t { BLACK = 0, RED }; 25 /** 26 * The tree layout is as follows: 27 * 1.array[0-4] is used to store common information, sush as: 28 * +------------------------+-----------------------------+------------------------+------------+------------------+ 29 * | the number of elements | the number of hole elements | the number of capacity | root index | compare function | 30 * +------------------------+-----------------------------+------------------------+------------+------------------+ 31 * 2.array[5,5+capacity] is used to store node of tree, map and set store nodes in different formats respectively. 32 * */ 33 template<typename Derived> 34 class TaggedTree : public TaggedArray { 35 public: 36 static constexpr int MIN_CAPACITY = 7; 37 static constexpr int NUMBER_OF_ELEMENTS_INDEX = 0; 38 static constexpr int NUMBER_OF_HOLE_ENTRIES_INDEX = 1; 39 static constexpr int CAPACITY_INDEX = 2; 40 static constexpr int ROOT_INDEX = 3; 41 static constexpr int COMPARE_FUNCTION_INDEX = 4; 42 static constexpr int ELEMENTS_START_INDEX = 5; 43 static constexpr int MIN_SHRINK_CAPACITY = 15; 44 45 static JSHandle<Derived> Create(const JSThread *thread, int numberOfElements); 46 47 static JSHandle<Derived> Insert(JSThread *thread, JSHandle<Derived> &tree, const JSHandle<JSTaggedValue> &key, 48 const JSHandle<JSTaggedValue> &value); 49 50 static JSHandle<Derived> GrowCapacity(const JSThread *thread, JSHandle<Derived> &tree); 51 52 inline static int ComputeCapacity(int oldCapacity); 53 54 static void Remove(const JSThread *thread, const JSHandle<Derived> &tree, int entry); 55 56 inline int NumberOfElements() const; 57 inline int NumberOfDeletedElements() const; 58 59 inline int Capacity() const; 60 61 inline JSTaggedValue GetKey(int entry) const; 62 inline JSTaggedValue GetValue(int entry) const; 63 64 inline TreeColor GetColor(int entry) const; 65 66 inline void SetCapacity(const JSThread *thread, int capacity); 67 IsKey(JSTaggedValue key)68 inline static bool IsKey(JSTaggedValue key) 69 { 70 return !key.IsHole(); 71 } 72 73 inline void SetNumberOfElements(const JSThread *thread, int num); 74 inline void SetNumberOfDeletedElements(const JSThread *thread, int num); 75 76 inline void SetRootEntries(const JSThread *thread, int num); 77 inline int GetRootEntries() const; 78 79 static int FindEntry(JSThread *thread, const JSHandle<Derived> &tree, const JSHandle<JSTaggedValue> &key); 80 81 inline static ComparisonResult EntryCompare(JSThread *thread, const JSHandle<JSTaggedValue> valueX, 82 const JSHandle<JSTaggedValue> valueY, JSHandle<Derived> tree); 83 84 inline void SetKey(const JSThread *thread, uint32_t entry, JSTaggedValue key); 85 inline void SetValue(const JSThread *thread, uint32_t entry, JSTaggedValue value); 86 inline void SetCompare(const JSThread *thread, JSTaggedValue fn); 87 inline JSTaggedValue GetCompare() const; 88 89 inline int GetMinimum(int entry) const; 90 inline int GetMaximum(int entry) const; 91 92 inline int GetParent(int entry) const; 93 inline JSTaggedValue GetLeftChild(int parent) const; 94 inline JSTaggedValue GetRightChild(int parent) const; 95 inline int GetLeftChildIndex(int parent) const; 96 inline int GetRightChildIndex(int parent) const; 97 98 protected: 99 inline JSTaggedValue GetElement(int index) const; 100 101 // get root 102 inline JSTaggedValue GetRootKey() const; 103 104 inline void SetRoot(JSThread *thread, int index, JSTaggedValue key, JSTaggedValue value); 105 106 inline void SetElement(const JSThread *thread, uint32_t index, JSTaggedValue element); 107 inline void SetColor(const JSThread *thread, int entry, TreeColor color); 108 inline void SetParent(const JSThread *thread, int entry, JSTaggedValue value); 109 110 inline uint32_t EntryToIndex(uint32_t entry) const; 111 inline void InsertLeftEntry(const JSThread *thread, uint32_t parentIndex, uint32_t entry, JSTaggedValue key, 112 JSTaggedValue value); 113 inline void InsertRightEntry(const JSThread *thread, uint32_t parentIndex, uint32_t entry, JSTaggedValue key, 114 JSTaggedValue value); 115 116 void InsertRebalance(const JSThread *thread, int index); 117 void DeleteRebalance(const JSThread *thread, int index); 118 inline bool IsVaildIndex(int entry) const; 119 120 inline int GetLeftBrother(int entry) const; 121 inline int GetRightBrother(int entry) const; 122 123 inline bool IsLeft(int entry) const; 124 inline bool IsRight(int entry) const; 125 126 int GetPreDecessor(int entry) const; 127 int GetSuccessor(int entry) const; 128 129 inline void SetLeftChild(const JSThread *thread, uint32_t entry, JSTaggedValue value); 130 inline void SetRightChild(const JSThread *thread, uint32_t entry, JSTaggedValue value); 131 132 void LeftRotate(const JSThread *thread, int index); 133 void RightRotate(const JSThread *thread, int index); 134 135 static JSHandle<Derived> AdjustTaggedTree(const JSThread *thread, const JSHandle<Derived> &tree, int len); 136 inline static ComparisonResult OrdinayEntryCompare(JSThread *thread, const JSHandle<JSTaggedValue> valueX, 137 const JSHandle<JSTaggedValue> valueY); 138 139 inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<Derived> &newTree, int index); 140 inline void CopyData(const JSThread *thread, int dst, int src); 141 inline void CopyAllData(const JSThread *thread, int parent, const JSHandle<Derived> &newTree, int index); 142 143 inline void RemoveEntry(const JSThread *thread, int index); 144 145 inline JSTaggedValue Transform(JSTaggedValue v) const; 146 void Transplant(const JSThread *thread, int dst, int src); 147 148 static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<Derived> &tree, 149 const JSHandle<JSTaggedValue> &key); 150 static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<Derived> &tree, 151 const JSHandle<JSTaggedValue> &key); 152 static JSHandle<TaggedArray> GetSortArray(const JSThread *thread, const JSHandle<Derived> &tree); 153 static JSHandle<Derived> Shrink(const JSThread *thread, const JSHandle<Derived> &tree); 154 }; 155 156 157 class TaggedTreeMap : public TaggedTree<TaggedTreeMap> { 158 public: 159 using RBTree = TaggedTree<TaggedTreeMap>; Cast(ObjectHeader * obj)160 static TaggedTreeMap *Cast(ObjectHeader *obj) 161 { 162 return static_cast<TaggedTreeMap *>(obj); 163 } 164 165 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 166 static JSTaggedValue Set(JSThread *thread, JSHandle<TaggedTreeMap> &obj, 167 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); 168 inline static JSTaggedValue Get(JSThread *thread, const JSHandle<TaggedTreeMap> &map, 169 const JSHandle<JSTaggedValue> &key); 170 static JSTaggedValue Delete(JSThread *thread, const JSHandle<TaggedTreeMap> &map, int entry); 171 bool HasValue(const JSThread *thread, JSTaggedValue value) const; 172 173 static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<TaggedTreeMap> &map, 174 const JSHandle<JSTaggedValue> &key); 175 static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<TaggedTreeMap> &map, 176 const JSHandle<JSTaggedValue> &key); 177 178 inline JSTaggedValue GetFirstKey() const; 179 inline JSTaggedValue GetLastKey() const; 180 181 static JSTaggedValue SetAll(JSThread *thread, JSHandle<TaggedTreeMap> &dst, const JSHandle<TaggedTreeMap> &src); 182 static JSHandle<TaggedArray> GetArrayFromMap(const JSThread *thread, const JSHandle<TaggedTreeMap> &map); 183 static int FindEntry(JSThread *thread, const JSHandle<TaggedTreeMap> &map, const JSHandle<JSTaggedValue> &key); 184 185 static const int ENTRY_SIZE = 6; 186 static const int ENTRY_VALUE_INDEX = 1; 187 static const int ENTRY_COLOR_INDEX = 2; 188 static const int ENTRY_PARENT_INDEX = 3; 189 static const int ENTRY_LEFT_CHILD_INDEX = 4; 190 static const int ENTRY_RIGHT_CHILD_INDEX = 5; 191 DECL_DUMP() 192 193 inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<TaggedTreeMap> &newTree, int index); 194 inline void CopyData(const JSThread *thread, int dst, int src); 195 inline void RemoveEntry(const JSThread *thread, int index); 196 }; 197 198 class TaggedTreeSet : public TaggedTree<TaggedTreeSet> { 199 public: 200 using RBTree = TaggedTree<TaggedTreeSet>; Cast(ObjectHeader * obj)201 static TaggedTreeSet *Cast(ObjectHeader *obj) 202 { 203 return static_cast<TaggedTreeSet *>(obj); 204 } 205 206 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 207 static JSTaggedValue Add(JSThread *thread, JSHandle<TaggedTreeSet> &obj, const JSHandle<JSTaggedValue> &value); 208 static JSTaggedValue Delete(JSThread *thread, const JSHandle<TaggedTreeSet> &set, int entry); 209 210 static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<TaggedTreeSet> &set, 211 const JSHandle<JSTaggedValue> &key); 212 static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<TaggedTreeSet> &set, 213 const JSHandle<JSTaggedValue> &key); 214 215 inline JSTaggedValue GetFirstKey() const; 216 inline JSTaggedValue GetLastKey() const; 217 static JSHandle<TaggedArray> GetArrayFromSet(const JSThread *thread, const JSHandle<TaggedTreeSet> &set); 218 static int FindEntry(JSThread *thread, const JSHandle<TaggedTreeSet> &set, const JSHandle<JSTaggedValue> &key); 219 220 static const int ENTRY_SIZE = 5; 221 static const int ENTRY_VALUE_INDEX = 0; 222 static const int ENTRY_COLOR_INDEX = 1; 223 static const int ENTRY_PARENT_INDEX = 2; 224 static const int ENTRY_LEFT_CHILD_INDEX = 3; 225 static const int ENTRY_RIGHT_CHILD_INDEX = 4; 226 227 DECL_DUMP() 228 229 inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<TaggedTreeSet> &newTree, int index); 230 inline void CopyData(const JSThread *thread, int dst, int src); 231 inline void RemoveEntry(const JSThread *thread, int index); 232 }; 233 } // namespace panda::ecmascript 234 #endif // ECMASCRIPT_TAGGED_TREE_H 235