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 VisitObjects(const EcmaObjectRangeVisitor & visitor)46 void VisitObjects(const EcmaObjectRangeVisitor &visitor) 47 { 48 // no field in this object 49 VisitRangeSlot(visitor); 50 } 51 Hash(JSTaggedValue key)52 static int Hash(JSTaggedValue key) 53 { 54 if (key.IsDouble() && key.GetDouble() == 0.0) { 55 key = JSTaggedValue(0); 56 } 57 if (key.IsSymbol()) { 58 auto symbolString = JSSymbol::Cast(key.GetTaggedObject()); 59 return static_cast<JSTaggedNumber>(symbolString->GetHashField()).GetInt(); 60 } 61 if (key.IsString()) { 62 auto keyString = reinterpret_cast<EcmaString *>(key.GetTaggedObject()); 63 return EcmaStringAccessor(keyString).GetHashcode(); 64 } 65 if (key.IsECMAObject()) { 66 int32_t hash = ECMAObject::Cast(key.GetTaggedObject())->GetHash(); 67 if (hash == 0) { 68 hash = base::RandomGenerator::GenerateIdentityHash(); 69 ECMAObject::Cast(key.GetTaggedObject())->SetHash(hash); 70 } 71 return hash; 72 } 73 74 // Int, Double, Special and HeapObject(except symbol and string) 75 uint64_t keyValue = key.GetRawData(); 76 return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t)); 77 } 78 }; 79 80 class LinkedNode : public TaggedNode { 81 public: InitLinkedNode(JSThread * thread,int hash,JSHandle<JSTaggedValue> key,JSHandle<JSTaggedValue> value,JSHandle<LinkedNode> next)82 void InitLinkedNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key, 83 JSHandle<JSTaggedValue> value, JSHandle<LinkedNode> next) 84 { 85 SetNext(thread, next); 86 InitTaggedNode(thread, hash, key, value); 87 } 88 Cast(TaggedObject * object)89 static LinkedNode *Cast(TaggedObject *object) 90 { 91 ASSERT(JSTaggedValue(object).IsLinkedNode()); 92 return static_cast<LinkedNode *>(object); 93 } 94 95 static constexpr size_t NEXT_OFFSET = TaggedNode::SIZE; 96 ACCESSORS(Next, NEXT_OFFSET, DATA_OFFSET); 97 98 static constexpr size_t SIZE = DATA_OFFSET; 99 DECL_VISIT_OBJECT_FOR_JS_OBJECT(TaggedNode, NEXT_OFFSET, SIZE) 100 101 static JSHandle<RBTreeNode> Treeing(JSThread *thread, const JSHandle<LinkedNode> &head); 102 }; 103 104 class RBTreeNode : public TaggedNode { 105 public: 106 struct LinkedNodeStruct { 107 JSHandle<LinkedNode> lowerHead; 108 JSHandle<LinkedNode> lowerTail; 109 JSHandle<LinkedNode> higherHead; 110 JSHandle<LinkedNode> higherTail; 111 }; 112 Cast(TaggedObject * object)113 static RBTreeNode *Cast(TaggedObject *object) 114 { 115 ASSERT(JSTaggedValue(object).IsRBTreeNode()); 116 return static_cast<RBTreeNode *>(object); 117 } 118 static constexpr size_t LEFT_OFFSET = TaggedNode::SIZE; 119 ACCESSORS(Left, LEFT_OFFSET, RIGHT_OFFSET); 120 ACCESSORS(Right, RIGHT_OFFSET, ISRED_OFFSET); 121 ACCESSORS(IsRed, ISRED_OFFSET, COUNT_OFFSET); 122 ACCESSORS_PRIMITIVE_FIELD(Count, uint32_t, COUNT_OFFSET, LAST_OFFSET) 123 DEFINE_ALIGN_SIZE(LAST_OFFSET); 124 125 DECL_VISIT_OBJECT_FOR_JS_OBJECT(TaggedNode, LEFT_OFFSET, COUNT_OFFSET) 126 127 void InitRBTreeNode(JSThread *thread, int hash, JSHandle<JSTaggedValue> key, 128 JSHandle<JSTaggedValue> value, int count); 129 static void Divide(JSThread *thread, JSHandle<TaggedHashArray> table, 130 JSHandle<JSTaggedValue> nodeVa, int index, int bit); 131 static JSHandle<RBTreeNode> Set(JSThread *thread, JSHandle<RBTreeNode> treeNode, int hash, 132 JSHandle<JSTaggedValue> key, JSHandle<JSTaggedValue> value); 133 static JSTaggedValue Delete(JSThread *thread, const JSTaggedValue &treeNodeVa, 134 int hash, const JSTaggedValue &key, JSTaggedValue &oldValue); 135 static JSTaggedValue GetTreeNode(JSThread *thread, JSHandle<JSTaggedValue> treeNodeVa, int hash, 136 JSHandle<JSTaggedValue> key); 137 static void InOrderTraverse(JSThread *thread, const JSHandle<RBTreeNode> &treeNode, 138 JSHandle<LinkedNode> &head, JSHandle<LinkedNode> &tail); 139 static JSHandle<LinkedNode> Detreeing(JSThread *thread, const JSHandle<RBTreeNode> &root); 140 static uint32_t Count(JSTaggedValue nodeValue); 141 static int Compare(int hash1, JSTaggedValue key1, int hash2, JSTaggedValue key2); 142 private: 143 static void InOrderTraverse(JSThread *thread, const JSHandle<RBTreeNode> &treeNode, 144 int bit, LinkedNodeStruct &nodeStruct); 145 static bool IsRed(JSTaggedValue treeNodeValue); 146 static JSTaggedValue Balance(JSThread *thread, RBTreeNode *treeNode); 147 static JSTaggedValue DeleteMin(JSThread *thread, RBTreeNode *treeNode); 148 RBTreeNode *RotateLeft(JSThread *thread); 149 RBTreeNode *RotateRight(JSThread *thread); 150 void FlipColors(JSThread *thread); 151 RBTreeNode *MoveRedLeft(JSThread *thread); 152 RBTreeNode *MoveRedRight(JSThread *thread); 153 RBTreeNode *Min(); 154 }; 155 } // namespace panda::ecmascript 156 #endif // ECMASCRIPT_TAGGED_NODE_H