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