1 /* 2 * Copyright (c) 2022 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_NODE_H 17 #define ECMASCRIPT_TAGGED_NODE_H 18 19 #include "ecmascript/js_thread.h" 20 #include "ecmascript/js_tagged_value-inl.h" 21 #include "ecmascript/mem/tagged_object.h" 22 23 namespace panda::ecmascript { 24 class TaggedNode : public TaggedObject { 25 public: InitTaggedNode(JSThread * thread,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value)26 void InitTaggedNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value) 27 { 28 SetHash(thread, JSTaggedValue(hash)); 29 SetKey(thread, key.GetTaggedValue()); 30 SetValue(thread, value.GetTaggedValue()); 31 } 32 Cast(TaggedObject * object)33 static TaggedNode *Cast(TaggedObject *object) 34 { 35 return static_cast<TaggedNode *>(object); 36 } 37 38 static constexpr size_t HASH_OFFSET = TaggedObject::TaggedObjectSize(); 39 ACCESSORS(Hash, HASH_OFFSET, KEY_OFFSET); 40 ACCESSORS(Key, KEY_OFFSET, VALUE_OFFSET); 41 ACCESSORS(Value, VALUE_OFFSET, DATA_OFFSET); 42 43 static constexpr size_t SIZE = DATA_OFFSET; 44 DECL_VISIT_OBJECT(HASH_OFFSET, SIZE); 45 Hash(const JSThread * thread,JSTaggedValue key)46 static int Hash(const JSThread *thread, JSTaggedValue key) 47 { 48 if (key.IsInt()) { 49 return key.GetInt(); 50 } 51 if (key.IsDouble()) { 52 double keyDoubleVal = key.GetDouble(); 53 int32_t tryIntKey = static_cast<int32_t>(keyDoubleVal); 54 if (tryIntKey == keyDoubleVal) { 55 return tryIntKey; 56 } 57 uint64_t keyValue = key.GetRawData(); 58 return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t)); 59 } 60 if (key.IsSymbol()) { 61 auto symbolString = JSSymbol::Cast(key.GetTaggedObject()); 62 return static_cast<JSTaggedNumber>(symbolString->GetHashField()).GetInt(); 63 } 64 if (key.IsString()) { 65 auto keyString = reinterpret_cast<EcmaString *>(key.GetTaggedObject()); 66 return EcmaStringAccessor(keyString).GetHashcode(); 67 } 68 if (key.IsECMAObject()) { 69 int32_t hash = ECMAObject::Cast(key.GetTaggedObject())->GetHash(); 70 if (hash == 0) { 71 hash = base::RandomGenerator::GenerateIdentityHash(); 72 JSHandle<ECMAObject> ecmaObj(thread, key); 73 ECMAObject::Cast(key.GetTaggedObject())->SetHash(thread, hash, ecmaObj); 74 } 75 return hash; 76 } 77 if (key.IsBigInt()) { 78 uint32_t keyValue = BigInt::Cast(key.GetTaggedObject())->GetDigit(0); 79 return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t)); 80 } 81 // Special and HeapObject(except symbol and string) 82 uint64_t keyValue = key.GetRawData(); 83 return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t)); 84 } 85 }; 86 87 class LinkedNode : public TaggedNode { 88 public: InitLinkedNode(JSThread * thread,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value,JSHandle<LinkedNode> next)89 void InitLinkedNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key, 90 JSHandle<JSTaggedValue> value, JSHandle<LinkedNode> next) 91 { 92 SetNext(thread, next); 93 InitTaggedNode(thread, hash, key, value); 94 } 95 Cast(TaggedObject * object)96 static LinkedNode *Cast(TaggedObject *object) 97 { 98 ASSERT(JSTaggedValue(object).IsLinkedNode()); 99 return static_cast<LinkedNode *>(object); 100 } 101 102 static constexpr size_t NEXT_OFFSET = TaggedNode::SIZE; 103 104 ACCESSORS(Next, NEXT_OFFSET, LAST_OFFSET); 105 106 static constexpr size_t SIZE = LAST_OFFSET; 107 DECL_VISIT_OBJECT(TaggedObject::SIZE, SIZE) 108 DECL_DUMP() 109 110 static JSHandle<RBTreeNode> Treeing(JSThread *thread, const JSHandle<LinkedNode> &head); 111 }; 112 113 class RBTreeNode : public TaggedNode { 114 public: 115 struct LinkedNodeStruct { 116 JSHandle<LinkedNode> lowerHead; 117 JSHandle<LinkedNode> lowerTail; 118 JSHandle<LinkedNode> higherHead; 119 JSHandle<LinkedNode> higherTail; 120 }; 121 Cast(TaggedObject * object)122 static RBTreeNode *Cast(TaggedObject *object) 123 { 124 ASSERT(JSTaggedValue(object).IsRBTreeNode()); 125 return static_cast<RBTreeNode *>(object); 126 } 127 static constexpr size_t LEFT_OFFSET = TaggedNode::SIZE; 128 ACCESSORS(Left, LEFT_OFFSET, RIGHT_OFFSET); 129 ACCESSORS(Right, RIGHT_OFFSET, ISRED_OFFSET); 130 ACCESSORS(IsRed, ISRED_OFFSET, COUNT_OFFSET); 131 ACCESSORS_PRIMITIVE_FIELD(Count, uint32_t, COUNT_OFFSET, LAST_OFFSET) 132 DEFINE_ALIGN_SIZE(LAST_OFFSET); 133 134 DECL_VISIT_OBJECT(TaggedObject::SIZE, COUNT_OFFSET) 135 136 void InitRBTreeNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key, 137 JSHandle<JSTaggedValue> value, int count); 138 static void Divide(JSThread *thread, JSHandle<TaggedHashArray> table, 139 JSHandle<JSTaggedValue> nodeVa, int index, int bit); 140 static JSHandle<RBTreeNode> Set(JSThread *thread, JSHandle<RBTreeNode> treeNode, int hash, 141 JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value); 142 static JSTaggedValue Delete(JSThread *thread, const JSTaggedValue &treeNodeVa, 143 int hash, const JSTaggedValue &key, JSTaggedValue &oldValue); 144 static JSTaggedValue GetTreeNode(JSThread *thread, JSHandle<JSTaggedValue> treeNodeVa, int hash, 145 JSHandle<JSTaggedValue> key); 146 static void InOrderTraverse(JSThread *thread, const JSHandle<RBTreeNode> &treeNode, 147 JSHandle<LinkedNode> &head, JSHandle<LinkedNode> &tail); 148 static JSHandle<LinkedNode> Detreeing(JSThread *thread, const JSHandle<RBTreeNode> &root); 149 static uint32_t Count(JSTaggedValue nodeValue); 150 static int Compare(int hash1, JSTaggedValue key1, int hash2, JSTaggedValue key2); 151 private: 152 static void InOrderTraverse(JSThread *thread, const JSHandle<RBTreeNode> &treeNode, 153 int bit, LinkedNodeStruct &nodeStruct); 154 static bool IsRed(JSTaggedValue treeNodeValue); 155 static JSTaggedValue Balance(JSThread *thread, RBTreeNode *treeNode); 156 static JSTaggedValue DeleteMin(JSThread *thread, RBTreeNode *treeNode); 157 RBTreeNode *RotateLeft(JSThread *thread); 158 RBTreeNode *RotateRight(JSThread *thread); 159 void FlipColors(JSThread *thread); 160 RBTreeNode *MoveRedLeft(JSThread *thread); 161 RBTreeNode *MoveRedRight(JSThread *thread); 162 RBTreeNode *Min(); 163 }; 164 } // namespace panda::ecmascript 165 #endif // ECMASCRIPT_TAGGED_NODE_H 166