1 /* 2 * Copyright (c) 2021 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_QUEUE_H 17 #define ECMASCRIPT_TAGGED_QUEUE_H 18 19 #include "ecmascript/js_tagged_value.h" 20 #include "ecmascript/js_thread.h" 21 #include "ecmascript/tagged_array.h" 22 #include "ecmascript/tagged_array-inl.h" 23 24 namespace panda::ecmascript { 25 class TaggedQueue : public TaggedArray { 26 public: Cast(ObjectHeader * object)27 static TaggedQueue *Cast(ObjectHeader *object) 28 { 29 return reinterpret_cast<TaggedQueue *>(object); 30 } 31 32 JSTaggedValue Pop(JSThread *thread); Push(const JSThread * thread,const JSHandle<TaggedQueue> & queue,const JSHandle<JSTaggedValue> & value)33 static TaggedQueue *Push(const JSThread *thread, const JSHandle<TaggedQueue> &queue, 34 const JSHandle<JSTaggedValue> &value) 35 { 36 uint32_t capacity = queue->GetCapacity().GetArrayLength(); 37 if (capacity == 0) { 38 // If there is no capacity, directly create a queue whose capacity is MIN_CAPACITY. Add elements. 39 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory(); 40 JSHandle<TaggedQueue> newQueue = factory->NewTaggedQueue(MIN_CAPACITY); 41 newQueue->Set(thread, 0, value.GetTaggedValue()); 42 newQueue->SetCapacity(thread, JSTaggedValue(MIN_CAPACITY)); 43 newQueue->SetStart(thread, JSTaggedValue(0)); 44 newQueue->SetEnd(thread, JSTaggedValue(1)); 45 return *newQueue; 46 } 47 48 uint32_t start = queue->GetStart().GetArrayLength(); 49 uint32_t end = queue->GetEnd().GetArrayLength(); 50 uint32_t size = queue->Size(); 51 if ((end + 1) % capacity == start) { 52 // The original queue is full and needs to be expanded. 53 if (capacity == MAX_QUEUE_INDEX) { 54 // can't grow anymore 55 return *queue; 56 } 57 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory(); 58 // Grow Array for 1.5 times 59 uint32_t newCapacity = capacity + (capacity >> 1U); 60 newCapacity = newCapacity < capacity ? MAX_QUEUE_INDEX : newCapacity; 61 JSHandle<TaggedQueue> newQueue = factory->NewTaggedQueue(newCapacity); 62 uint32_t newEnd = 0; 63 for (uint32_t i = start; newEnd < size; i = (i + 1) % capacity) { 64 newQueue->Set(thread, newEnd, queue->Get(i)); 65 newEnd++; 66 } 67 68 newQueue->SetCapacity(thread, JSTaggedValue(newCapacity)); 69 newQueue->SetStart(thread, JSTaggedValue(0)); 70 newQueue->Set(thread, newEnd++, value.GetTaggedValue()); 71 newQueue->SetEnd(thread, JSTaggedValue(newEnd)); 72 return *newQueue; 73 } 74 queue->Set(thread, end, value.GetTaggedValue()); 75 queue->SetEnd(thread, JSTaggedValue((end + 1) % capacity)); 76 return *queue; 77 } 78 79 // Only for fixed-length queue, without grow capacity PushFixedQueue(const JSThread * thread,const JSHandle<TaggedQueue> & queue,const JSHandle<JSTaggedValue> & value)80 static inline void PushFixedQueue(const JSThread *thread, const JSHandle<TaggedQueue> &queue, 81 const JSHandle<JSTaggedValue> &value) 82 { 83 uint32_t end = queue->GetEnd().GetArrayLength(); 84 uint32_t capacity = queue->GetCapacity().GetArrayLength(); 85 ASSERT(capacity != 0); 86 queue->Set(thread, end, value.GetTaggedValue()); 87 queue->SetEnd(thread, JSTaggedValue((end + 1) % capacity)); 88 } 89 Empty()90 inline bool Empty() 91 { 92 return GetStart() == GetEnd(); 93 } 94 Front()95 inline JSTaggedValue Front() 96 { 97 if (Empty()) { 98 return JSTaggedValue::Hole(); 99 } 100 uint32_t start = GetStart().GetArrayLength(); 101 return JSTaggedValue(Get(start)); 102 } 103 Back()104 inline JSTaggedValue Back() 105 { 106 if (Empty()) { 107 return JSTaggedValue::Hole(); 108 } 109 return JSTaggedValue(Get(GetEnd().GetArrayLength() - 1)); 110 } 111 Size()112 inline uint32_t Size() 113 { 114 uint32_t capacity = GetCapacity().GetArrayLength(); 115 if (capacity == 0) { 116 return 0; 117 } 118 uint32_t end = GetEnd().GetArrayLength(); 119 uint32_t start = GetStart().GetArrayLength(); 120 return (end - start + capacity) % capacity; 121 } 122 Get(uint32_t index)123 inline JSTaggedValue Get(uint32_t index) const 124 { 125 return TaggedArray::Get(QueueToArrayIndex(index)); 126 } 127 Set(const JSThread * thread,uint32_t index,JSTaggedValue value)128 inline void Set(const JSThread *thread, uint32_t index, JSTaggedValue value) 129 { 130 return TaggedArray::Set(thread, QueueToArrayIndex(index), value); 131 } 132 133 static const uint32_t MIN_CAPACITY = 2; 134 static const uint32_t CAPACITY_INDEX = 0; 135 static const uint32_t START_INDEX = 1; 136 static const uint32_t END_INDEX = 2; 137 static const uint32_t ELEMENTS_START_INDEX = 3; 138 static const uint32_t MAX_QUEUE_INDEX = TaggedArray::MAX_ARRAY_INDEX - ELEMENTS_START_INDEX; 139 140 private: 141 friend class ObjectFactory; 142 QueueToArrayIndex(uint32_t index)143 inline static constexpr uint32_t QueueToArrayIndex(uint32_t index) 144 { 145 return index + ELEMENTS_START_INDEX; 146 } 147 SetCapacity(const JSThread * thread,JSTaggedValue capacity)148 inline void SetCapacity(const JSThread *thread, JSTaggedValue capacity) 149 { 150 TaggedArray::Set(thread, CAPACITY_INDEX, capacity); 151 } 152 GetCapacity()153 inline JSTaggedValue GetCapacity() const 154 { 155 return TaggedArray::Get(CAPACITY_INDEX); 156 } 157 SetStart(const JSThread * thread,JSTaggedValue start)158 inline void SetStart(const JSThread *thread, JSTaggedValue start) 159 { 160 TaggedArray::Set(thread, START_INDEX, start); 161 } 162 GetStart()163 inline JSTaggedValue GetStart() const 164 { 165 return TaggedArray::Get(START_INDEX); 166 } 167 SetEnd(const JSThread * thread,JSTaggedValue end)168 inline void SetEnd(const JSThread *thread, JSTaggedValue end) 169 { 170 TaggedArray::Set(thread, END_INDEX, end); 171 } 172 GetEnd()173 inline JSTaggedValue GetEnd() const 174 { 175 return TaggedArray::Get(END_INDEX); 176 } 177 178 static TaggedQueue *Create(JSThread *thread, uint32_t capacity, JSTaggedValue initVal = JSTaggedValue::Hole()); 179 }; 180 } // namespace panda::ecmascript 181 #endif // ECMASCRIPT_TAGGED_QUEUE_H