1 /*
2 * Copyright (c) 2024 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 #include "libpandabase/taskmanager/utils/task_selector.h"
17 #include <algorithm>
18
19 namespace ark::taskmanager::internal {
20
TaskSelector(const std::map<TaskQueueId,internal::SchedulableTaskQueueInterface * > & taskQueues)21 TaskSelector::TaskSelector(const std::map<TaskQueueId, internal::SchedulableTaskQueueInterface *> &taskQueues)
22 : taskQueues_(taskQueues)
23 {
24 }
25
Init()26 void TaskSelector::Init()
27 {
28 priorityQueue_.reserve(taskQueues_.size());
29 for (auto &[id, queue] : taskQueues_) {
30 size_t priority = queue->GetPriority();
31 priorityQueue_.emplace_back(priority, id);
32 }
33 std::make_heap(priorityQueue_.begin(), priorityQueue_.end());
34 }
35
SelectQueue()36 TaskQueueId TaskSelector::SelectQueue()
37 {
38 size_t popCount = 0;
39 TaskQueueId resultId = INVALID_TASKQUEUE_ID;
40 // First we need to find queue that have tasks
41 while (popCount < priorityQueue_.size()) {
42 // Getting max priority from priorityQueue_
43 size_t frontPriority = 0;
44 std::tie(frontPriority, std::ignore) = priorityQueue_.front();
45 // if it's zero it means that queue should be rebuild with new priorities from queue
46 if (frontPriority == 0) {
47 for (auto &[priority, id] : priorityQueue_) {
48 priority = taskQueues_.at(id)->GetPriority();
49 }
50 }
51 // Select queue with highest priority
52 std::pop_heap(priorityQueue_.begin(), priorityQueue_.end() - popCount);
53 popCount++;
54 auto &[priority, id] = priorityQueue_[priorityQueue_.size() - popCount];
55 // Decrement it's priority
56 priority--;
57 // If queue isn't empty, we select it
58 if (LIKELY(!taskQueues_.at(id)->IsEmpty())) {
59 resultId = id;
60 break;
61 }
62 }
63 // Finally push all queues back
64 while (popCount != 0) {
65 popCount--;
66 std::push_heap(priorityQueue_.begin(), priorityQueue_.end() - popCount);
67 }
68 return resultId;
69 }
70
71 } // namespace ark::taskmanager::internal
72