1 /* 2 * Copyright (C) 2019 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <condition_variable> 20 #include <list> 21 #include <mutex> 22 #include <optional> 23 #include "android-base/thread_annotations.h" 24 25 namespace android { 26 27 /** 28 * A thread-safe FIFO queue. This list-backed queue stores up to <i>capacity</i> objects if 29 * a capacity is provided at construction, and is otherwise unbounded. 30 * Objects can always be added. Objects are added immediately. 31 * If the queue is full, new objects cannot be added. 32 * 33 * The action of retrieving an object will block until an element is available. 34 */ 35 template <class T> 36 class BlockingQueue { 37 public: 38 explicit BlockingQueue() = default; 39 BlockingQueue(size_t capacity)40 explicit BlockingQueue(size_t capacity) : mCapacity(capacity){}; 41 42 /** 43 * Retrieve and remove the oldest object. 44 * Blocks execution indefinitely while queue is empty. 45 */ pop()46 T pop() { 47 std::unique_lock lock(mLock); 48 android::base::ScopedLockAssertion assumeLock(mLock); 49 mHasElements.wait(lock, [this]() REQUIRES(mLock) { return !this->mQueue.empty(); }); 50 T t = std::move(mQueue.front()); 51 mQueue.erase(mQueue.begin()); 52 return t; 53 }; 54 55 /** 56 * Retrieve and remove the oldest object. 57 * Blocks execution for the given duration while queue is empty, and returns std::nullopt 58 * if the queue was empty for the entire duration. 59 */ popWithTimeout(std::chrono::nanoseconds duration)60 std::optional<T> popWithTimeout(std::chrono::nanoseconds duration) { 61 std::unique_lock lock(mLock); 62 android::base::ScopedLockAssertion assumeLock(mLock); 63 if (!mHasElements.wait_for(lock, duration, 64 [this]() REQUIRES(mLock) { return !this->mQueue.empty(); })) { 65 return {}; 66 } 67 T t = std::move(mQueue.front()); 68 mQueue.erase(mQueue.begin()); 69 return t; 70 }; 71 72 /** 73 * Add a new object to the queue. 74 * Does not block. 75 * Return true if an element was successfully added. 76 * Return false if the queue is full. 77 */ push(T && t)78 bool push(T&& t) { 79 { // acquire lock 80 std::scoped_lock lock(mLock); 81 if (mCapacity && mQueue.size() == mCapacity) { 82 return false; 83 } 84 mQueue.push_back(std::move(t)); 85 } // release lock 86 mHasElements.notify_one(); 87 return true; 88 }; 89 90 /** 91 * Construct a new object into the queue. 92 * Does not block. 93 * Return true if an element was successfully added. 94 * Return false if the queue is full. 95 */ 96 template <class... Args> emplace(Args &&...args)97 bool emplace(Args&&... args) { 98 { // acquire lock 99 std::scoped_lock lock(mLock); 100 if (mCapacity && mQueue.size() == mCapacity) { 101 return false; 102 } 103 mQueue.emplace_back(args...); 104 } // release lock 105 mHasElements.notify_one(); 106 return true; 107 }; 108 erase_if(const std::function<bool (const T &)> & pred)109 void erase_if(const std::function<bool(const T&)>& pred) { 110 std::scoped_lock lock(mLock); 111 std::erase_if(mQueue, pred); 112 } 113 114 /** 115 * Remove all elements. 116 * Does not block. 117 */ clear()118 void clear() { 119 std::scoped_lock lock(mLock); 120 mQueue.clear(); 121 }; 122 123 /** 124 * How many elements are currently stored in the queue. 125 * Primary used for debugging. 126 * Does not block. 127 */ size()128 size_t size() { 129 std::scoped_lock lock(mLock); 130 return mQueue.size(); 131 } 132 133 private: 134 const std::optional<size_t> mCapacity; 135 /** 136 * Used to signal that mQueue is non-empty. 137 */ 138 std::condition_variable mHasElements; 139 /** 140 * Lock for accessing and waiting on elements. 141 */ 142 std::mutex mLock; 143 std::list<T> mQueue GUARDED_BY(mLock); 144 }; 145 146 } // namespace android 147