1 /** 2 * Copyright (c) 2025 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 #ifndef PANDA_RUNTIME_COROUTINES_PRIORITY_QUEUE_H 16 #define PANDA_RUNTIME_COROUTINES_PRIORITY_QUEUE_H 17 18 #include "libpandabase/macros.h" 19 #include "include/mem/panda_containers.h" 20 #include "runtime/coroutines/coroutine_worker.h" 21 22 #include <cstdint> 23 #include <limits> 24 #include <type_traits> 25 26 namespace ark { 27 28 class Coroutine; 29 30 enum class CoroutineOrder { STACK_ORDER, QUEUE_ORDER }; 31 32 class PriorityQueue { 33 class CoroutineWrapper { 34 public: CoroutineWrapper(Coroutine * coroutine,uint64_t priority)35 explicit CoroutineWrapper(Coroutine *coroutine, uint64_t priority) : coroutine_(coroutine), priority_(priority) 36 { 37 ASSERT((priority >> ORDER_BITS) != 0); 38 } 39 40 Coroutine *operator*() const 41 { 42 return coroutine_; 43 } 44 45 Coroutine *operator->() const 46 { 47 return coroutine_; 48 } 49 50 /// @return compares coroutine wrappers by priority 51 bool operator<(const CoroutineWrapper &other) const 52 { 53 return priority_ < other.priority_; 54 } 55 56 /// @return priority of wrapped coroutine 57 CoroutinePriority GetPriority(); 58 59 private: 60 Coroutine *coroutine_; 61 uint64_t priority_; 62 }; 63 64 public: 65 using Queue = PandaDeque<CoroutineWrapper>; 66 using CIterator = Queue::const_iterator; 67 using Properties = std::unordered_map<CoroutinePriority, CoroutineOrder>; 68 69 // NOLINTNEXTLINE(fuchsia-statically-constructed-objects) 70 static inline Properties defaultProps_ = {{CoroutinePriority::LOW_PRIORITY, CoroutineOrder::QUEUE_ORDER}, 71 {CoroutinePriority::MEDIUM_PRIORITY, CoroutineOrder::QUEUE_ORDER}, 72 {CoroutinePriority::HIGH_PRIORITY, CoroutineOrder::QUEUE_ORDER}, 73 {CoroutinePriority::CRITICAL_PRIORITY, CoroutineOrder::QUEUE_ORDER}}; 74 75 /// Creates PriorityQueue with the given properties (Priority -> Order mapping) properties_(std::move (props))76 explicit PriorityQueue(Properties props = defaultProps_) : properties_(std::move(props)) {} 77 78 /** 79 * Adds a coroutine to the queue in order of priority. 80 * For the stack order, the coroutine is added at the top. 81 * For the queue order - at the end of the priority subqueue. 82 */ 83 void Push(Coroutine *coro, CoroutinePriority priority); 84 85 /** 86 * Checks that queue is not empty, 87 * returns Coroutine with the highest priority. 88 */ 89 std::pair<Coroutine *, CoroutinePriority> Pop(); 90 91 /** 92 * Allows to iterate over Coroutines in the priority queue. 93 * Guarantees priority ordrer during iteration. 94 */ 95 template <typename Visitor, typename U = std::enable_if_t<std::is_invocable_v<Visitor, Coroutine *>>> IterateOverCoroutines(const Visitor & visitor)96 void IterateOverCoroutines(const Visitor &visitor) const 97 { 98 for (auto &coroWrapper : coroutines_) { 99 visitor(*coroWrapper); 100 } 101 } 102 103 /** 104 * Allows to apply callback for CoroutineWrappers in the priority queue. 105 * Can be used in pair with RemoveCoroutines. 106 */ 107 template <typename Visitor, typename U = std::enable_if_t<std::is_invocable_v<Visitor, CIterator, CIterator>>> VisitCoroutines(const Visitor & visitor)108 void VisitCoroutines(const Visitor &visitor) const 109 { 110 visitor(coroutines_.cbegin(), coroutines_.cend()); 111 } 112 113 /// Removes coroutines from the priority queue by given sequence of iterators 114 template <typename Container, 115 typename U = std::enable_if_t<std::is_same_v<typename Container::value_type, CIterator>>> RemoveCoroutines(const Container & coroutinesIterators)116 void RemoveCoroutines(const Container &coroutinesIterators) 117 { 118 for (auto &iter : coroutinesIterators) { 119 coroutines_.erase(iter); 120 } 121 std::make_heap(coroutines_.begin(), coroutines_.end(), Comparator); 122 } 123 124 /// @return size of the priority queue Size()125 size_t Size() const 126 { 127 return coroutines_.size(); 128 } 129 130 /// @return true if priority queue is empty Empty()131 bool Empty() const 132 { 133 return coroutines_.empty(); 134 } 135 136 private: 137 uint64_t CalculatePriority(CoroutinePriority priority); 138 139 static bool Comparator(const CoroutineWrapper &co1, const CoroutineWrapper &co2); 140 141 static constexpr uint64_t PRIORITY_COUNT = static_cast<uint64_t>(CoroutinePriority::PRIORITY_COUNT); 142 static constexpr uint64_t ORDER_BITS = std::numeric_limits<uint64_t>::digits - PRIORITY_COUNT; 143 144 Queue coroutines_; 145 Properties properties_; 146 uint64_t stackOrder_ = 0; 147 uint64_t queueOrder_ = std::numeric_limits<uint64_t>::max() >> PRIORITY_COUNT; 148 }; 149 } // namespace ark 150 151 #endif // PANDA_RUNTIME_COROUTINES_PRIORITY_QUEUE_H 152