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_LIST_H 17 #define ECMASCRIPT_TAGGED_LIST_H 18 19 #include "ecmascript/js_handle.h" 20 #include "ecmascript/js_symbol.h" 21 #include "ecmascript/js_tagged_number.h" 22 #include "ecmascript/js_tagged_value.h" 23 #include "ecmascript/tagged_array.h" 24 25 namespace panda::ecmascript { 26 template<typename Derived> 27 class TaggedList : public TaggedArray { 28 public: 29 static const int NUMBER_OF_NODE_INDEX = 0; 30 static const int NUMBER_OF_DELETED_NODES_INDEX = 1; 31 static const int HEAD_TABLE_INDEX = 2; 32 static const int TAIL_TABLE_INDEX = 3; 33 static const int ELEMENTS_START_INDEX = 4; 34 static const int DEFAULT_ARRAY_LENGHT = 10; 35 static const int NEXT_PTR_OFFSET = 1; 36 static const int PREV_PTR_OFFSET = 2; 37 38 static JSHandle<Derived> Create(const JSThread *thread, int numberOfNodes = DEFAULT_ARRAY_LENGHT); 39 static JSHandle<Derived> GrowCapacity(const JSThread *thread, const JSHandle<Derived> &taggedList); 40 static JSTaggedValue TaggedListToArray(const JSThread *thread, const JSHandle<Derived> &taggedList); 41 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<Derived> &taggedList); 42 void CopyArray(const JSThread *thread, JSHandle<Derived> &taggedList); 43 void Clear(const JSThread *thread); 44 JSTaggedValue FindElementByIndex(const JSThread *thread, int index) const; 45 std::pair<int, JSTaggedValue> FindElementByDataIndex(const JSThread *thread, int dataindex) const; 46 int FindIndexByElement(const JSThread *thread, const JSTaggedValue &element); 47 int FindLastIndexByElement(const JSThread *thread, const JSTaggedValue &element); 48 int FindDataIndexByNodeIndex(int index) const; 49 void MapNodeIndexToDataIndex(std::vector<int> &nodeIndexMapToDataIndex, int length); 50 void RemoveNode(JSThread *thread, int prevDataIndex); 51 int FindPrevNodeByIndex(int index) const; 52 int FindPrevNodeByValue(const JSThread *thread, const JSTaggedValue &element); 53 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); Length()54 inline int Length() 55 { 56 return NumberOfNodes(); 57 } 58 GetFirst(const JSThread * thread)59 inline JSTaggedValue GetFirst(const JSThread *thread) 60 { 61 int firstDataIndex = GetPrimitiveElement(ELEMENTS_START_INDEX + NEXT_PTR_OFFSET).GetInt(); 62 return GetElement(thread, firstDataIndex); 63 } 64 GetLast(const JSThread * thread)65 inline JSTaggedValue GetLast(const JSThread *thread) 66 { 67 int lastDataIndex = GetPrimitiveElement(TAIL_TABLE_INDEX).GetInt(); 68 return GetElement(thread, lastDataIndex); 69 } 70 GetCapacityFromTaggedArray()71 inline int GetCapacityFromTaggedArray() 72 { 73 return static_cast<int>(GetLength()); 74 } 75 SetElement(const JSThread * thread,int index,const JSTaggedValue & element)76 inline void SetElement(const JSThread *thread, int index, const JSTaggedValue &element) 77 { 78 if (UNLIKELY((index < 0 || index >= static_cast<int>(GetLength())))) { 79 return; 80 } 81 Set(thread, index, element); 82 } 83 GetElement(const JSThread * thread,int index)84 inline JSTaggedValue GetElement(const JSThread *thread, int index) const 85 { 86 if (UNLIKELY((index < 0 || index >= static_cast<int>(GetLength())))) { 87 return JSTaggedValue::Undefined(); 88 } 89 return Get(thread, index); 90 } 91 GetPrimitiveElement(int index)92 inline JSTaggedValue GetPrimitiveElement(int index) const 93 { 94 if (UNLIKELY((index < 0 || index >= static_cast<int>(GetLength())))) { 95 return JSTaggedValue::Undefined(); 96 } 97 return GetPrimitive(index); 98 } 99 NumberOfNodes()100 inline int NumberOfNodes() const 101 { 102 return GetPrimitive(NUMBER_OF_NODE_INDEX).GetInt(); 103 } 104 NumberOfDeletedNodes()105 inline int NumberOfDeletedNodes() const 106 { 107 return GetPrimitive(NUMBER_OF_DELETED_NODES_INDEX).GetInt(); 108 } 109 SetNumberOfDeletedNodes(const JSThread * thread,int nod)110 inline void SetNumberOfDeletedNodes(const JSThread *thread, int nod) 111 { 112 Set(thread, NUMBER_OF_DELETED_NODES_INDEX, JSTaggedValue(nod)); 113 } 114 SetNumberOfNodes(const JSThread * thread,int nof)115 inline void SetNumberOfNodes(const JSThread *thread, int nof) 116 { 117 Set(thread, NUMBER_OF_NODE_INDEX, JSTaggedValue(nof)); 118 } 119 GetNextDataIndex(int dataIndex)120 int GetNextDataIndex(int dataIndex) const 121 { 122 dataIndex = GetPrimitiveElement(dataIndex + NEXT_PTR_OFFSET).GetInt(); 123 if (dataIndex != ELEMENTS_START_INDEX) { 124 return dataIndex; 125 } 126 return -1; 127 } 128 }; 129 130 class TaggedSingleList : public TaggedList<TaggedSingleList> { 131 public: 132 static const int ENTRY_SIZE = 2; Cast(TaggedObject * obj)133 static TaggedSingleList *Cast(TaggedObject *obj) 134 { 135 return static_cast<TaggedSingleList *>(obj); 136 } 137 138 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = TaggedSingleList::DEFAULT_ARRAY_LENGHT); 139 static JSTaggedValue Add(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 140 const JSHandle<JSTaggedValue> &value); 141 static JSTaggedValue Insert(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 142 const JSHandle<JSTaggedValue> &value, const int index); 143 static JSTaggedValue AddNode(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 144 const JSHandle<JSTaggedValue> &value, const int index, int prevDataIndex); 145 static JSTaggedValue Set(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 146 const int index, const JSHandle<JSTaggedValue> &value); 147 static JSTaggedValue ReplaceAllElements(JSThread *thread, const JSHandle<JSTaggedValue> &thisHandle, 148 const JSHandle<JSTaggedValue> &callbackFn, 149 const JSHandle<JSTaggedValue> &thisArg, 150 const JSHandle<TaggedSingleList> &taggedList); 151 static JSTaggedValue Sort(JSThread *thread, const JSHandle<JSTaggedValue> &callbackFn, 152 const JSHandle<TaggedSingleList> &taggedList); 153 static JSTaggedValue ConvertToArray(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList); 154 static void GetSubList(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 155 const int fromIndex, const int toIndex, const JSHandle<TaggedSingleList> &subList); 156 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList); 157 static JSTaggedValue SortByNodeOrder(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList); 158 159 void Clear(const JSThread *thread); 160 bool IsEmpty() const; 161 bool Has(const JSThread *thread, const JSTaggedValue &value); 162 JSTaggedValue Get(const JSThread *thread, const int index); 163 std::pair<int, JSTaggedValue> GetByDataIndex(const JSThread *thread, const int dataIndex); 164 int GetIndexOf(const JSThread *thread, const JSTaggedValue &value); 165 int GetLastIndexOf(const JSThread *thread, const JSTaggedValue &value); 166 void InsertNode(const JSThread *thread, const JSHandle<JSTaggedValue> &value, const int prevDataIndex, 167 const int finalDataIndex); 168 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); 169 JSTaggedValue Remove(JSThread *thread, const JSTaggedValue &element); 170 JSTaggedValue Equal(const JSThread *thread, const JSHandle<TaggedSingleList> &compareList); 171 DECL_DUMP() 172 }; 173 174 class TaggedDoubleList : public TaggedList<TaggedDoubleList> { 175 public: 176 static const int ENTRY_SIZE = 3; Cast(TaggedObject * obj)177 static TaggedDoubleList *Cast(TaggedObject *obj) 178 { 179 return static_cast<TaggedDoubleList *>(obj); 180 } 181 182 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = TaggedDoubleList::DEFAULT_ARRAY_LENGHT); 183 static JSTaggedValue Add(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 184 const JSHandle<JSTaggedValue> &value); 185 static JSTaggedValue AddFirst(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 186 const JSHandle<JSTaggedValue> &value); 187 static JSTaggedValue Insert(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 188 const JSHandle<JSTaggedValue> &value, const int index); 189 static JSTaggedValue AddNode(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 190 const JSHandle<JSTaggedValue> &value, const int index, int prevDataIndex); 191 static JSTaggedValue Set(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, const int index, 192 const JSHandle<JSTaggedValue> &value); 193 static JSTaggedValue ConvertToArray(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList); 194 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList); 195 static JSTaggedValue RemoveFirstFound(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 196 const JSTaggedValue &element); 197 static JSTaggedValue RemoveLastFound(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 198 const JSTaggedValue &element); 199 void Clear(const JSThread *thread); 200 JSTaggedValue Get(const JSThread *thread, const int index); 201 std::pair<int, JSTaggedValue> GetByDataIndex(const JSThread *thread, const int dataIndex); 202 int GetPrevNode(const int index); 203 bool Has(const JSThread *thread, const JSTaggedValue &value); 204 void InsertNode(const JSThread *thread, const JSHandle<JSTaggedValue> &value, const int prevDataIndex, 205 const int finalDataIndex); 206 JSTaggedValue RemoveFirst(JSThread *thread); 207 JSTaggedValue RemoveLast(JSThread *thread); 208 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); 209 JSTaggedValue Remove(JSThread *thread, const JSTaggedValue &element); 210 int GetIndexOf(const JSThread *thread, const JSTaggedValue &value); 211 int GetLastIndexOf(const JSThread *thread, const JSTaggedValue &value); 212 int FindPrevNodeByIndexAtLast(const int index) const; 213 int FindPrevNodeByValueAtLast(const JSThread *thread, const JSTaggedValue &element); 214 DECL_DUMP() 215 216 protected: 217 inline JSTaggedValue FindElementByIndexAtLast(const JSThread *thread, int index) const; 218 }; 219 } // namespace panda::ecmascript 220 #endif // ECMASCRIPT_TAGGED_LIST_H 221