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 by A2DP.
32  */
33 template <typename T, int NUM_PRIORITY_LEVELS = 2>
34 class MultiPriorityQueue {
35   static_assert(NUM_PRIORITY_LEVELS > 1);
36 
37  public:
38   // Get the front item with the highest priority.  Queue must be non-empty.
front()39   T& front() {
40     return queues_[next_to_dequeue_.top()].front();
41   }
42 
empty()43   [[nodiscard]] bool empty() const {
44     return next_to_dequeue_.empty();
45   }
46 
size()47   [[nodiscard]] size_t size() const {
48     return next_to_dequeue_.size();
49   }
50 
51   // Push the item with specified priority
52   void push(const T& t, int priority = 0) {
53     queues_[priority].push(t);
54     next_to_dequeue_.push(priority);
55   }
56 
57   // Push the item with specified priority
58   void push(T&& t, int priority = 0) {
59     queues_[priority].push(std::forward<T>(t));
60     next_to_dequeue_.push(priority);
61   }
62 
63   // Pop the item in the front
pop()64   void pop() {
65     queues_[next_to_dequeue_.top()].pop();
66     next_to_dequeue_.pop();
67   }
68 
69  private:
70   std::array<std::queue<T>, NUM_PRIORITY_LEVELS> queues_;
71   std::priority_queue<int> next_to_dequeue_;
72 };
73 
74 }  // namespace common
75 }  // namespace bluetooth
76