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 AddNode(const JSThread *thread, const JSHandle<Derived> &taggedList, 41 const JSHandle<JSTaggedValue> &value, const int index, int prevDataIndex); 42 static JSTaggedValue TaggedListToArray(const JSThread *thread, const JSHandle<Derived> &taggedList); 43 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<Derived> &taggedList); 44 void CopyArray(const JSThread *thread, JSHandle<Derived> &taggedList); 45 void Clear(const JSThread *thread); 46 JSTaggedValue FindElementByIndex(int index) const; 47 std::pair<int, JSTaggedValue> FindElementByDataIndex(int dataindex) const; 48 int FindIndexByElement(const JSTaggedValue &element); 49 int FindLastIndexByElement(const JSTaggedValue &element); 50 int FindDataIndexByNodeIndex(int index) const; 51 void MapNodeIndexToDataIndex(std::vector<int> &nodeIndexMapToDataIndex, int length); 52 void RemoveNode(JSThread *thread, int prevDataIndex); 53 int FindPrevNodeByIndex(int index) const; 54 int FindPrevNodeByValue(const JSTaggedValue &element); 55 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); Length()56 inline int Length() 57 { 58 return NumberOfNodes(); 59 } 60 GetFirst()61 inline JSTaggedValue GetFirst() 62 { 63 int firstDataIndex = GetElement(ELEMENTS_START_INDEX + NEXT_PTR_OFFSET).GetInt(); 64 return GetElement(firstDataIndex); 65 } 66 GetLast()67 inline JSTaggedValue GetLast() 68 { 69 int lastDataIndex = GetElement(TAIL_TABLE_INDEX).GetInt(); 70 return GetElement(lastDataIndex); 71 } 72 GetCapacityFromTaggedArray()73 inline int GetCapacityFromTaggedArray() 74 { 75 return static_cast<int>(GetLength()); 76 } 77 SetElement(const JSThread * thread,int index,const JSTaggedValue & element)78 inline void SetElement(const JSThread *thread, int index, const JSTaggedValue &element) 79 { 80 if (UNLIKELY((index < 0 || index >= static_cast<int>(GetLength())))) { 81 return; 82 } 83 Set(thread, index, element); 84 } 85 GetElement(int index)86 inline JSTaggedValue GetElement(int index) const 87 { 88 if (UNLIKELY((index < 0 || index >= static_cast<int>(GetLength())))) { 89 return JSTaggedValue::Undefined(); 90 } 91 return Get(index); 92 } 93 NumberOfNodes()94 inline int NumberOfNodes() const 95 { 96 return Get(NUMBER_OF_NODE_INDEX).GetInt(); 97 } 98 NumberOfDeletedNodes()99 inline int NumberOfDeletedNodes() const 100 { 101 return Get(NUMBER_OF_DELETED_NODES_INDEX).GetInt(); 102 } 103 SetNumberOfDeletedNodes(const JSThread * thread,int nod)104 inline void SetNumberOfDeletedNodes(const JSThread *thread, int nod) 105 { 106 Set(thread, NUMBER_OF_DELETED_NODES_INDEX, JSTaggedValue(nod)); 107 } 108 SetNumberOfNodes(const JSThread * thread,int nof)109 inline void SetNumberOfNodes(const JSThread *thread, int nof) 110 { 111 Set(thread, NUMBER_OF_NODE_INDEX, JSTaggedValue(nof)); 112 } 113 GetNextDataIndex(int dataIndex)114 int GetNextDataIndex(int dataIndex) const 115 { 116 dataIndex = GetElement(dataIndex + NEXT_PTR_OFFSET).GetInt(); 117 if (dataIndex != ELEMENTS_START_INDEX) { 118 return dataIndex; 119 } 120 return -1; 121 } 122 }; 123 124 class TaggedSingleList : public TaggedList<TaggedSingleList> { 125 public: 126 static const int ENTRY_SIZE = 2; Cast(TaggedObject * obj)127 static TaggedSingleList *Cast(TaggedObject *obj) 128 { 129 return static_cast<TaggedSingleList *>(obj); 130 } 131 132 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = TaggedSingleList::DEFAULT_ARRAY_LENGHT); 133 static JSTaggedValue Add(const JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 134 const JSHandle<JSTaggedValue> &value); 135 static JSTaggedValue Insert(JSThread *thread, const JSHandle<TaggedSingleList> &taggedList, 136 const JSHandle<JSTaggedValue> &value, const int index); 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 void Clear(const JSThread *thread); 150 bool IsEmpty() const; 151 bool Has(const JSTaggedValue &value); 152 JSTaggedValue Get(const int index); 153 std::pair<int, JSTaggedValue> GetByDataIndex(const int dataIndex); 154 int GetIndexOf(const JSTaggedValue &value); 155 int GetLastIndexOf(const JSTaggedValue &value); 156 void InsertNode(const JSThread *thread, const JSHandle<JSTaggedValue> &value, const int prevDataIndex, 157 const int finalDataIndex); 158 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); 159 JSTaggedValue Remove(JSThread *thread, const JSTaggedValue &element); 160 JSTaggedValue Equal(const JSHandle<TaggedSingleList> &compareList); 161 DECL_DUMP() 162 }; 163 164 class TaggedDoubleList : public TaggedList<TaggedDoubleList> { 165 public: 166 static const int ENTRY_SIZE = 3; Cast(TaggedObject * obj)167 static TaggedDoubleList *Cast(TaggedObject *obj) 168 { 169 return static_cast<TaggedDoubleList *>(obj); 170 } 171 172 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = TaggedDoubleList::DEFAULT_ARRAY_LENGHT); 173 static JSTaggedValue Add(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 174 const JSHandle<JSTaggedValue> &value); 175 static JSTaggedValue AddFirst(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 176 const JSHandle<JSTaggedValue> &value); 177 static JSTaggedValue Insert(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 178 const JSHandle<JSTaggedValue> &value, const int index); 179 static JSTaggedValue Set(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, const int index, 180 const JSHandle<JSTaggedValue> &value); 181 static JSTaggedValue ConvertToArray(const JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList); 182 static JSHandle<TaggedArray> OwnKeys(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList); 183 static JSTaggedValue RemoveFirstFound(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 184 const JSTaggedValue &element); 185 static JSTaggedValue RemoveLastFound(JSThread *thread, const JSHandle<TaggedDoubleList> &taggedList, 186 const JSTaggedValue &element); 187 void Clear(const JSThread *thread); 188 JSTaggedValue Get(const int index); 189 std::pair<int, JSTaggedValue> GetByDataIndex(const int dataIndex); 190 int GetPrevNode(const int index); 191 bool Has(const JSTaggedValue &value); 192 void InsertNode(const JSThread *thread, const JSHandle<JSTaggedValue> &value, const int prevDataIndex, 193 const int finalDataIndex); 194 JSTaggedValue RemoveFirst(JSThread *thread); 195 JSTaggedValue RemoveLast(JSThread *thread); 196 JSTaggedValue RemoveByIndex(JSThread *thread, const int &index); 197 JSTaggedValue Remove(JSThread *thread, const JSTaggedValue &element); 198 int GetIndexOf(const JSTaggedValue &value); 199 int GetLastIndexOf(const JSTaggedValue &value); 200 int FindPrevNodeByIndexAtLast(const int index) const; 201 int FindPrevNodeByValueAtLast(const JSTaggedValue &element); 202 DECL_DUMP() 203 204 protected: 205 inline JSTaggedValue FindElementByIndexAtLast(int index) const; 206 }; 207 } // namespace panda::ecmascript 208 #endif // ECMASCRIPT_TAGGED_LIST_H