Improve BlockingQueue and add SyncQueue
Changes to BlockingQueue:
- Change BlockingQueue to be list-backed instead of vector-backed so
that removals are O(1) instead of O(N).
- Rename erase to erase_if.
- Make providing a fixed capacity at construction optional.
- Add emplace function to push and construct element in-place.
- Add popWithTimeout function.
Bug: 275726706
Test: atest inputflinger_tests
Change-Id: I1be02b0887df2c21b28f4f1cb43a8e208d996a87
diff --git a/services/inputflinger/BlockingQueue.h b/services/inputflinger/BlockingQueue.h
index fe37287..5693848 100644
--- a/services/inputflinger/BlockingQueue.h
+++ b/services/inputflinger/BlockingQueue.h
@@ -16,15 +16,17 @@
#pragma once
-#include "android-base/thread_annotations.h"
#include <condition_variable>
+#include <list>
#include <mutex>
-#include <vector>
+#include <optional>
+#include "android-base/thread_annotations.h"
namespace android {
/**
- * A FIFO queue that stores up to <i>capacity</i> objects.
+ * A thread-safe FIFO queue. This list-backed queue stores up to <i>capacity</i> objects if
+ * a capacity is provided at construction, and is otherwise unbounded.
* Objects can always be added. Objects are added immediately.
* If the queue is full, new objects cannot be added.
*
@@ -33,13 +35,13 @@
template <class T>
class BlockingQueue {
public:
- BlockingQueue(size_t capacity) : mCapacity(capacity) {
- mQueue.reserve(mCapacity);
- };
+ explicit BlockingQueue() = default;
+
+ explicit BlockingQueue(size_t capacity) : mCapacity(capacity){};
/**
* Retrieve and remove the oldest object.
- * Blocks execution while queue is empty.
+ * Blocks execution indefinitely while queue is empty.
*/
T pop() {
std::unique_lock lock(mLock);
@@ -51,26 +53,62 @@
};
/**
+ * Retrieve and remove the oldest object.
+ * Blocks execution for the given duration while queue is empty, and returns std::nullopt
+ * if the queue was empty for the entire duration.
+ */
+ std::optional<T> popWithTimeout(std::chrono::nanoseconds duration) {
+ std::unique_lock lock(mLock);
+ android::base::ScopedLockAssertion assumeLock(mLock);
+ if (!mHasElements.wait_for(lock, duration,
+ [this]() REQUIRES(mLock) { return !this->mQueue.empty(); })) {
+ return {};
+ }
+ T t = std::move(mQueue.front());
+ mQueue.erase(mQueue.begin());
+ return t;
+ };
+
+ /**
* Add a new object to the queue.
* Does not block.
* Return true if an element was successfully added.
* Return false if the queue is full.
*/
bool push(T&& t) {
- {
+ { // acquire lock
std::scoped_lock lock(mLock);
- if (mQueue.size() == mCapacity) {
+ if (mCapacity && mQueue.size() == mCapacity) {
return false;
}
mQueue.push_back(std::move(t));
- }
+ } // release lock
mHasElements.notify_one();
return true;
};
- void erase(const std::function<bool(const T&)>& lambda) {
+ /**
+ * Construct a new object into the queue.
+ * Does not block.
+ * Return true if an element was successfully added.
+ * Return false if the queue is full.
+ */
+ template <class... Args>
+ bool emplace(Args&&... args) {
+ { // acquire lock
+ std::scoped_lock lock(mLock);
+ if (mCapacity && mQueue.size() == mCapacity) {
+ return false;
+ }
+ mQueue.emplace_back(args...);
+ } // release lock
+ mHasElements.notify_one();
+ return true;
+ };
+
+ void erase_if(const std::function<bool(const T&)>& pred) {
std::scoped_lock lock(mLock);
- std::erase_if(mQueue, [&lambda](const auto& t) { return lambda(t); });
+ std::erase_if(mQueue, pred);
}
/**
@@ -93,7 +131,7 @@
}
private:
- const size_t mCapacity;
+ const std::optional<size_t> mCapacity;
/**
* Used to signal that mQueue is non-empty.
*/
@@ -102,7 +140,7 @@
* Lock for accessing and waiting on elements.
*/
std::mutex mLock;
- std::vector<T> mQueue GUARDED_BY(mLock);
+ std::list<T> mQueue GUARDED_BY(mLock);
};
} // namespace android