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