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(int index) const; 45 std::pair<int, JSTaggedValue> FindElementByDataIndex(int dataindex) const; 46 int FindIndexByElement(const JSTaggedValue &element); 47 int FindLastIndexByElement(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 JSTaggedValue &element); 53 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); Length()54 inline int Length() 55 { 56 return NumberOfNodes(); 57 } 58 GetFirst()59 inline JSTaggedValue GetFirst() 60 { 61 int firstDataIndex = GetElement(ELEMENTS_START_INDEX + NEXT_PTR_OFFSET).GetInt(); 62 return GetElement(firstDataIndex); 63 } 64 GetLast()65 inline JSTaggedValue GetLast() 66 { 67 int lastDataIndex = GetElement(TAIL_TABLE_INDEX).GetInt(); 68 return GetElement(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(int index)84 inline JSTaggedValue GetElement(int index) const 85 { 86 if (UNLIKELY((index < 0 || index >= static_cast<int>(GetLength())))) { 87 return JSTaggedValue::Undefined(); 88 } 89 return Get(index); 90 } 91 NumberOfNodes()92 inline int NumberOfNodes() const 93 { 94 return Get(NUMBER_OF_NODE_INDEX).GetInt(); 95 } 96 NumberOfDeletedNodes()97 inline int NumberOfDeletedNodes() const 98 { 99 return Get(NUMBER_OF_DELETED_NODES_INDEX).GetInt(); 100 } 101 SetNumberOfDeletedNodes(const JSThread * thread,int nod)102 inline void SetNumberOfDeletedNodes(const JSThread *thread, int nod) 103 { 104 Set(thread, NUMBER_OF_DELETED_NODES_INDEX, JSTaggedValue(nod)); 105 } 106 SetNumberOfNodes(const JSThread * thread,int nof)107 inline void SetNumberOfNodes(const JSThread *thread, int nof) 108 { 109 Set(thread, NUMBER_OF_NODE_INDEX, JSTaggedValue(nof)); 110 } 111 GetNextDataIndex(int dataIndex)112 int GetNextDataIndex(int dataIndex) const 113 { 114 dataIndex = GetElement(dataIndex + NEXT_PTR_OFFSET).GetInt(); 115 if (dataIndex != ELEMENTS_START_INDEX) { 116 return dataIndex; 117 } 118 return -1; 119 } 120 }; 121 122 class TaggedSingleList : public TaggedList<TaggedSingleList> { 123 public: 124 static const int ENTRY_SIZE = 2; Cast(TaggedObject * obj)125 static TaggedSingleList *Cast(TaggedObject *obj) 126 { 127 return static_cast<TaggedSingleList *>(obj); 128 } 129 130 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = TaggedSingleList::DEFAULT_ARRAY_LENGHT); 131 static JSTaggedValue Add(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 132 const JSHandle<JSTaggedValue> &value); 133 static JSTaggedValue Insert(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 134 const JSHandle<JSTaggedValue> &value, const int index); 135 static JSTaggedValue AddNode(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 136 const JSHandle<JSTaggedValue> &value, const int index, int prevDataIndex); 137 static JSTaggedValue Set(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 138 const int index, const JSHandle<JSTaggedValue> &value); 139 static JSTaggedValue ReplaceAllElements(JSThread *thread, const JSHandle<JSTaggedValue> &thisHandle, 140 const JSHandle<JSTaggedValue> &callbackFn, 141 const JSHandle<JSTaggedValue> &thisArg, 142 const JSHandle<TaggedSingleList> &taggedList); 143 static JSTaggedValue Sort(JSThread *thread, const JSHandle<JSTaggedValue> &callbackFn, 144 const JSHandle<TaggedSingleList> &taggedList); 145 static JSTaggedValue ConvertToArray(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList); 146 static void GetSubList(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 147 const int fromIndex, const int toIndex, const JSHandle<TaggedSingleList> &subList); 148 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList); 149 static JSTaggedValue SortByNodeOrder(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList); 150 151 void Clear(const JSThread *thread); 152 bool IsEmpty() const; 153 bool Has(const JSTaggedValue &value); 154 JSTaggedValue Get(const int index); 155 std::pair<int, JSTaggedValue> GetByDataIndex(const int dataIndex); 156 int GetIndexOf(const JSTaggedValue &value); 157 int GetLastIndexOf(const JSTaggedValue &value); 158 void InsertNode(const JSThread *thread, const JSHandle<JSTaggedValue> &value, const int prevDataIndex, 159 const int finalDataIndex); 160 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); 161 JSTaggedValue Remove(JSThread *thread, const JSTaggedValue &element); 162 JSTaggedValue Equal(const JSHandle<TaggedSingleList> &compareList); 163 DECL_DUMP() 164 }; 165 166 class TaggedDoubleList : public TaggedList<TaggedDoubleList> { 167 public: 168 static const int ENTRY_SIZE = 3; Cast(TaggedObject * obj)169 static TaggedDoubleList *Cast(TaggedObject *obj) 170 { 171 return static_cast<TaggedDoubleList *>(obj); 172 } 173 174 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = TaggedDoubleList::DEFAULT_ARRAY_LENGHT); 175 static JSTaggedValue Add(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 176 const JSHandle<JSTaggedValue> &value); 177 static JSTaggedValue AddFirst(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 178 const JSHandle<JSTaggedValue> &value); 179 static JSTaggedValue Insert(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 180 const JSHandle<JSTaggedValue> &value, const int index); 181 static JSTaggedValue AddNode(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 182 const JSHandle<JSTaggedValue> &value, const int index, int prevDataIndex); 183 static JSTaggedValue Set(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, const int index, 184 const JSHandle<JSTaggedValue> &value); 185 static JSTaggedValue ConvertToArray(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList); 186 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList); 187 static JSTaggedValue RemoveFirstFound(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 188 const JSTaggedValue &element); 189 static JSTaggedValue RemoveLastFound(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 190 const JSTaggedValue &element); 191 void Clear(const JSThread *thread); 192 JSTaggedValue Get(const int index); 193 std::pair<int, JSTaggedValue> GetByDataIndex(const int dataIndex); 194 int GetPrevNode(const int index); 195 bool Has(const JSTaggedValue &value); 196 void InsertNode(const JSThread *thread, const JSHandle<JSTaggedValue> &value, const int prevDataIndex, 197 const int finalDataIndex); 198 JSTaggedValue RemoveFirst(JSThread *thread); 199 JSTaggedValue RemoveLast(JSThread *thread); 200 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); 201 JSTaggedValue Remove(JSThread *thread, const JSTaggedValue &element); 202 int GetIndexOf(const JSTaggedValue &value); 203 int GetLastIndexOf(const JSTaggedValue &value); 204 int FindPrevNodeByIndexAtLast(const int index) const; 205 int FindPrevNodeByValueAtLast(const JSTaggedValue &element); 206 DECL_DUMP() 207 208 protected: 209 inline JSTaggedValue FindElementByIndexAtLast(int index) const; 210 }; 211 } // namespace panda::ecmascript 212 #endif // ECMASCRIPT_TAGGED_LIST_H 213