Index: webrtc/common_audio/swap_queue.h |
diff --git a/webrtc/common_audio/swap_queue.h b/webrtc/common_audio/swap_queue.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..f1ff878b3de21c0568a08420412607f1eef204c6 |
--- /dev/null |
+++ b/webrtc/common_audio/swap_queue.h |
@@ -0,0 +1,234 @@ |
+/* |
+ * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. |
+ * |
+ * Use of this source code is governed by a BSD-style license |
+ * that can be found in the LICENSE file in the root of the source |
+ * tree. An additional intellectual property rights grant can be found |
+ * in the file PATENTS. All contributing project authors may |
+ * be found in the AUTHORS file in the root of the source tree. |
+ */ |
+ |
+#ifndef WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ |
+#define WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ |
+ |
+#include <algorithm> |
+#include <utility> |
+#include <vector> |
+ |
+#include "webrtc/base/checks.h" |
+#include "webrtc/base/criticalsection.h" |
+ |
+namespace webrtc { |
+ |
+namespace internal { |
+ |
+// This class is a one-way queue where data is written from one end and read |
+// from the other end. The queue can be applied to any swappable objects. |
the sun
2015/10/26 15:16:20
objects -> type
peah-webrtc
2015/10/26 22:27:02
Please see below.
|
+// The queue is safe to access the class concurrently from multiple threads. |
the sun
2015/10/26 15:16:20
Remove "the class"
peah-webrtc
2015/10/26 22:27:02
Please see below.
|
+// |
+// Conceptually, the queue maintains an ordered sequence and an unordered bunch |
the sun
2015/10/26 15:16:21
Where's the shorter description that me and Karl s
peah-webrtc
2015/10/26 22:27:02
That is a very good question. Seems like something
|
+// of Ts. At all times, the number of Ts in the sequence and the bunch combined |
+// is N, a constant set in the constructor call. The following operations |
+// modify the sequence and the bunch: |
+// |
+// - The constructor populates the bunch with N Ts (either by |
+// default-constructing them or copy-constructing them from a supplied |
+// prototype T), and leaves the sequence empty. |
+// |
+// - Insert() steals the given T and puts it last in the sequence; it gives |
+// back an arbitrary T from the bunch. (Accomplished with a single swap, by |
+// reassigning the physical location of the removed bunch T to the |
+// sequence.) |
+// |
+// - Remove() steals the given T and puts it in the bunch; it gives back the |
+// first element in the sequence. (Accomplished with a single swap, by |
+// reassigning the physical location of the removed sequence T to the |
+// bunch.) |
+// |
+// - Clear() moves all Ts from the sequence into the bunch. (This is done |
+// without touching any Ts, by reassigning their physical locations.) |
+// |
+// The intended use is for one client (the producer) to fill a T with useful |
+// stuff, and use Insert() to swap it for a T that doesn't contain useful |
+// stuff; and for another client (the consumer) to use Remove() to swap a T |
+// that doesn't contain useful stuff for a T that does. The point of passing Ts |
+// that don't contain anything useful in the reverse direction is to avoid |
+// having to make heap allocations at the producer and releasing them at the |
+// consumer. |
+// |
+// Example of queue usage: |
+// SwapQueue<int> q(2)); // q contains [0 0]; |
+// int i = 1; |
+// q.Insert(&i); // q contains [1 0], i=0 |
+// i = 2; |
+// q.Insert(&i); // q contains [1 2], i=0 |
+// i = -3(; |
+// q.Remove(&i); // q contains [-3 2], i=1 |
+// i = 4; |
+// q.Insert(&i); // q contains [4 2], i=-3 |
+// i = -5; |
+// q.Remove(&i); // q contains [4 -5], i=2 |
+// i = -6; |
+// q.Remove(&i); // q contains [-6 -5], i=4 |
+// |
+// It should be noted that if you want the T returned from the bunch at the call |
+// to Insert to be of a certain characteristic (e.g., certain size), care must |
+// be taken that the queue is initialized with such elements, and that all Ts |
+// used as input to Remove also have that characteristic. In order to verify |
+// this invariance a callback function can be supplied that verifies this in |
+// debug mode (via RTC_DCHECK) for the queue elements. Examples of this can be |
+// found in the unit tests. |
+ |
+// (Internal; please don't use outside this file.) |
+// Default item invariance verifier callback function. |
+template <typename T> |
+bool SwapQueueItemVerifierFunction(const T&) { |
+ return true; |
+} |
+ |
+} // namespace internal |
+ |
+// Functor to use when supplying a verifier function for the queue item |
+// verifcation. |
+template <typename T, |
+ bool (*QueueItemVerifierFunction)(const T&) = |
+ internal::SwapQueueItemVerifierFunction> |
+class SwapQueueItemVerifier { |
+ public: |
+ bool operator()(const T& t) const { return QueueItemVerifierFunction(t); } |
+}; |
+ |
+// Queue template implementing a queue of elements of type T and with an |
the sun
2015/10/26 15:16:21
Too verbose.
"Queue on type T."
peah-webrtc
2015/10/26 22:27:02
Done.
|
+// optional invariance verifier callback functor that verifies |
+// that the queue elements are compliant to a certain requirement. |
+template <typename T, typename QueueItemVerifier = SwapQueueItemVerifier<T> > |
the sun
2015/10/26 15:16:21
QueueItemVerifier shouldn't be needed as a templat
peah-webrtc
2015/10/26 22:27:02
How do you mean? I still need to have the type of
the sun
2015/10/27 13:51:33
You're right. The template argument is needed.
peah-webrtc
2015/10/29 06:15:14
Acknowledged.
|
+class SwapQueue { |
+ public: |
+ // Creates a queue of size size and fills it with the specified number of |
+ // default constructed Ts. |
+ explicit SwapQueue(size_t size) : queue_(size) { |
+ RTC_DCHECK(VerifyQueueContent()); |
+ } |
+ |
+ // Creates a queue of size size and fills it with the specified number of |
+ // default constructed Ts and accepts a functor to use for initializing the |
+ // item verification functor. |
+ explicit SwapQueue(size_t size, const QueueItemVerifier& queue_item_verifier) |
the sun
2015/10/26 15:16:20
remove "explicit"
peah-webrtc
2015/10/26 22:27:02
Done.
|
+ : queue_(size), queue_item_verifier_(queue_item_verifier) { |
+ RTC_DCHECK(VerifyQueueContent()); |
+ } |
+ |
+ // Creates a queue of size size and fills it with copies of prototype. |
+ SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) { |
+ RTC_DCHECK(VerifyQueueContent()); |
+ } |
+ |
+ // Creates a queue of size size and fills it with copies of prototype and |
+ // accepts a functor to use for initializing the item verification functor. |
+ SwapQueue(size_t size, |
+ QueueItemVerifier const& queue_item_verifier, |
+ const T& prototype) |
+ : queue_(size, prototype), queue_item_verifier_(queue_item_verifier) { |
+ RTC_DCHECK(VerifyQueueContent()); |
+ } |
+ |
+ // Resets the queue to have zero content. |
+ void Clear() { |
+ rtc::CritScope cs(&crit_queue_); |
+ next_write_index_ = 0; |
+ next_read_index_ = 0; |
+ num_elements_ = 0; |
+ } |
+ |
+ // Inserts a T into the queue by swapping *input with an element already in |
+ // the queue (an object from the unordered bunch). |
+ // Returns true if the item was inserted or false if not (the queue was full). |
+ // When specified, the T given in *input must pass the ItemVerifier() test. |
+ // The contents of *input after the call are then also guaranteed to pass the |
+ // ItemVerifier() test. |
+ bool Insert(T* input) { |
+ RTC_DCHECK(input); |
+ RTC_DCHECK(queue_item_verifier_(*input)); |
+ |
+ rtc::CritScope cs(&crit_queue_); |
+ |
+ if (num_elements_ == queue_.size()) { |
+ return false; |
+ } |
+ |
+ using std::swap; |
+ swap(*input, queue_[next_write_index_]); |
+ |
+ next_write_index_++; |
+ if (next_write_index_ == queue_.size()) { |
+ next_write_index_ = 0; |
+ } |
+ |
+ num_elements_++; |
+ return true; |
+ } |
+ |
+ // Removes a T from the queue by swapping *output with an element in the |
+ // queue. |
+ // The T in *output before the call is swapped into the queue (into the |
+ // unordered bunch in the queue). |
+ // Returns true if an item could be removed or false if not (the queue was |
+ // empty). When specified, The T given in *output must pass the ItemVerifier() |
+ // test and the contents of *output after the call are then also guaranteed to |
+ // pass the ItemVerifier() test. |
+ bool Remove(T* output) { |
+ RTC_DCHECK(output); |
+ RTC_DCHECK(queue_item_verifier_(*output)); |
+ |
+ rtc::CritScope cs(&crit_queue_); |
+ |
+ if (num_elements_ == 0) { |
+ return false; |
+ } |
+ |
+ using std::swap; |
+ swap(*output, queue_[next_read_index_]); |
+ |
+ next_read_index_++; |
+ if (next_read_index_ == queue_.size()) { |
+ next_read_index_ = 0; |
+ } |
+ |
+ num_elements_--; |
+ return true; |
+ } |
+ |
+ private: |
+ // Verify that the queue content complies with the ItemVerifier test. |
+ bool VerifyQueueContent() { |
+ rtc::CritScope cs(&crit_queue_); |
+ for (const auto& v : queue_) { |
+ RTC_DCHECK(queue_item_verifier_(v)); |
+ } |
+ |
the sun
2015/10/26 15:16:20
remove blank
peah-webrtc
2015/10/26 22:27:02
Done.
|
+ return true; |
+ } |
+ |
+ // queue_.size() is constant. |
+ std::vector<T> queue_ GUARDED_BY(crit_queue_); |
+ |
+ QueueItemVerifier queue_item_verifier_; |
+ |
+ // (next_read_index_ + num_elements_) % queue_.size() = |
+ // next_write_index_ |
+ // 0 <= next_write_index_ <= queue.size() |
the sun
2015/10/26 15:16:21
next_write_index_ < queue.size()
peah-webrtc
2015/10/26 22:27:02
Done.
|
+ size_t next_write_index_ GUARDED_BY(crit_queue_) = 0; |
+ // 0 <= next_read_index_ <= queue.size() |
the sun
2015/10/26 15:16:21
next_read_index_ < queue.size()
peah-webrtc
2015/10/26 22:27:02
Done.
|
+ size_t next_read_index_ GUARDED_BY(crit_queue_) = 0; |
+ |
+ // 0 <= num_elements_ <= queue.size() |
+ size_t num_elements_ GUARDED_BY(crit_queue_) = 0; |
+ |
+ rtc::CriticalSection crit_queue_; |
the sun
2015/10/26 15:16:21
nit: I would have used the order:
queue_item_veri
peah-webrtc
2015/10/26 22:27:02
Makes sense! Will change to that.
peah-webrtc
2015/10/26 22:27:02
Done.
|
+ |
+ RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue); |
+}; |
+ |
+} // namespace webrtc |
+ |
+#endif // WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ |