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 #include "runtime/coroutines/priority_queue.h"
16 #include "runtime/coroutines/coroutine.h"
17
18 #include <algorithm>
19
20 namespace ark {
21
GetPriority()22 CoroutinePriority PriorityQueue::CoroutineWrapper::GetPriority()
23 {
24 auto internalPriority = priority_ >> ORDER_BITS;
25 auto priority = 0U;
26 while (internalPriority != 1) {
27 internalPriority >>= 1U;
28 priority++;
29 }
30 ASSERT(priority < PRIORITY_COUNT);
31 return static_cast<CoroutinePriority>(priority);
32 }
33
Push(Coroutine * coro,CoroutinePriority priority)34 void PriorityQueue::Push(Coroutine *coro, CoroutinePriority priority)
35 {
36 coroutines_.emplace_back(coro, CalculatePriority(priority));
37 std::push_heap(coroutines_.begin(), coroutines_.end(), Comparator);
38 }
39
Pop()40 std::pair<Coroutine *, CoroutinePriority> PriorityQueue::Pop()
41 {
42 ASSERT(!Empty());
43 std::pop_heap(coroutines_.begin(), coroutines_.end(), Comparator);
44 auto coroWrapper = coroutines_.back();
45 coroutines_.pop_back();
46 return {*coroWrapper, coroWrapper.GetPriority()};
47 }
48
CalculatePriority(CoroutinePriority priority)49 uint64_t PriorityQueue::CalculatePriority(CoroutinePriority priority)
50 {
51 ASSERT(static_cast<uint32_t>(priority) < PRIORITY_COUNT);
52 auto orderIt = properties_.find(priority);
53 ASSERT(orderIt != properties_.end());
54 uint64_t order = 0;
55 switch (orderIt->second) {
56 case CoroutineOrder::STACK_ORDER:
57 order = stackOrder_++;
58 break;
59 case CoroutineOrder::QUEUE_ORDER:
60 order = queueOrder_--;
61 break;
62 default:
63 UNREACHABLE();
64 }
65 return (1ULL << (ORDER_BITS + static_cast<uint32_t>(priority))) | order;
66 }
67
Comparator(const CoroutineWrapper & co1,const CoroutineWrapper & co2)68 bool PriorityQueue::Comparator(const CoroutineWrapper &co1, const CoroutineWrapper &co2)
69 {
70 return co1 < co2;
71 }
72
73 } // namespace ark
74