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