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