1 /******************************************************************************
2  *
3  *  Copyright 2021 The Android Open Source Project
4  *
5  *  Licensed under the Apache License, Version 2.0 (the "License");
6  *  you may not use this file except in compliance with the License.
7  *  You may obtain a copy of the License at:
8  *
9  *  http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  *
17  ******************************************************************************/
18 
19 #pragma once
20 
21 #include <array>
22 #include <queue>
23 
24 namespace bluetooth {
25 namespace common {
26 
27 /**
28  * A queue implementation which supports items with multiple priorities.
29  * Items with greater priority value will be dequeued first.
30  * When Enqueuing, the user can specify the priority (0 by default).
31  * This can be used by ACL or L2CAP lower queue end sender to prioritize some link or channel, used
32  * by A2DP.
33  */
34 template <typename T, int NUM_PRIORITY_LEVELS = 2>
35 class MultiPriorityQueue {
36   static_assert(NUM_PRIORITY_LEVELS > 1);
37 
38 public:
39   // Get the front item with the highest priority.  Queue must be non-empty.
front()40   T& front() { return queues_[next_to_dequeue_.top()].front(); }
41 
empty()42   [[nodiscard]] bool empty() const { return next_to_dequeue_.empty(); }
43 
size()44   [[nodiscard]] size_t size() const { return next_to_dequeue_.size(); }
45 
46   // Swaps the contents with the given instance.
swap(MultiPriorityQueue & that)47   void swap(MultiPriorityQueue& that) {
48     queues_.swap(that.queues_);
49     next_to_dequeue_.swap(that.next_to_dequeue_);
50   }
51 
52   // Push the item with specified priority
53   void push(const T& t, int priority = 0) {
54     queues_[priority].push(t);
55     next_to_dequeue_.push(priority);
56   }
57 
58   // Push the item with specified priority
59   void push(T&& t, int priority = 0) {
60     queues_[priority].push(std::forward<T>(t));
61     next_to_dequeue_.push(priority);
62   }
63 
64   // Pop the item in the front
pop()65   void pop() {
66     queues_[next_to_dequeue_.top()].pop();
67     next_to_dequeue_.pop();
68   }
69 
70 private:
71   std::array<std::queue<T>, NUM_PRIORITY_LEVELS> queues_;
72   std::priority_queue<int> next_to_dequeue_;
73 };
74 
75 }  // namespace common
76 }  // namespace bluetooth
77