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