Changed queue implementation to the proposed vector-based solution.

webrtc/common_audio/swap_queue.h

+/*
+ *  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 fixed-size queue. A producer calls Insert() to insert
+// an element of type T at the back of the queue, and a consumer calls
+// Remove() to remove an element from the front of the queue. It's safe
+// for the producer(s) and the consumer(s) to access the queue
+// concurrently, from different threads.
+//
+// To avoid the construction, copying, and destruction of Ts that a naive
+// queue implementation would require, for each "full" T passed from
+// producer to consumer, SwapQueue<T> passes an "empty" T in the other
+// direction (an "empty" T is one that contains nothing of value for the
+// consumer). This bidirectional movement is implemented with swap().
+//
+// // Create queue:
+// Bottle proto(568);  // Prepare an empty Bottle. Heap allocates space for
+//                     // 568 ml.
+// SwapQueue<Bottle> q(N, proto);  // Init queue with N copies of proto.
+//                                 // Also heap.

[kwiberg-webrtc, 2015/10/27 12:05:13]

Since it doesn't fit on one line anyway:

"Also heap." -> "Each copy allocates on the heap."

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+// // Producer pseudo-code:
+// Bottle b(568); // Prepare an empty Bottle. Heap allocates space for 568 ml.
+// loop {
+//   b.Fill(amount);  // Where amount <= 568 ml.
+//   q.Insert(&b);    // Swap our full Bottle for an empty one from q.
+// }
+
+// // Consumer pseudo-code:
+// Bottle b(568);  // Prepare an empty Bottle. Heap allocates space for 568 ml.
+// loop {
+//   q.Remove(&b); // Swap our empty Bottle for the next-in-line full Bottle.
+//   Drink(&b);
+// }
+
+// For a well-behaved Bottle class, there are no allocations in the
+// producer, since it just fills an empty Bottle that's already large
+// enough; no deallocations in the consumer, since it returns each empty
+// Bottle to the queue after having drunk it; and no copies along the
+// way, since the queue uses swap() everywhere to move full Bottles in
+// one direction and empty ones in the other.

[kwiberg-webrtc, 2015/10/27 12:05:13]

Move lines 25-61 to just before the SwapQueue class declaration? And put // on
the two empty lines, so that it all hangs together?

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+
+// (Internal; please don't use outside this file.)
+// Default item invariance verifier callback function.
+template <typename T>
+bool SwapQueueItemVerifierFunction(const T&) {

[kwiberg-webrtc, 2015/10/27 12:05:13]

Prepend "Default" or "Noop" or something to this name, so that it doesn't sound
like a generic verifier? Also, it's a bit on the short side as is.

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+  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 of type T with an optional invariance verifier callback functor that
+// verifies that the queue elements are compliant to a certain requirement.
+template <typename T, typename QueueItemVerifier = SwapQueueItemVerifier<T> >

[kwiberg-webrtc, 2015/10/27 12:05:13]

"> >" -> ">>"

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+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.
+  SwapQueue(size_t size, const QueueItemVerifier& queue_item_verifier)
+      : queue_item_verifier_(queue_item_verifier), queue_(size) {
+    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.

[kwiberg-webrtc, 2015/10/27 12:05:13]

Point out that the number of slots in the queue doesn't change?

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+  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).

[kwiberg-webrtc, 2015/10/27 12:05:13]

The doc now talks about "empty" and "full" Ts again, so maybe

  Inserts a "full" T at the back of the queue by swapping *input with an "empty"
T from the queue.

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+  // 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) {

[kwiberg-webrtc, 2015/10/27 12:05:13]

Annotate this with WARN_UNUSED_RESULT?

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+    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_++;

[kwiberg-webrtc, 2015/10/27 12:05:13]

In general, prefer the prefix forms. (They're sometimes more efficient, so it's
a good habit to get into, and it makes the code more consistent.)

[peah-webrtc, 2015/10/29 06:15:14]

Thanks! Will do!

Done.

+    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).

[kwiberg-webrtc, 2015/10/27 12:05:13]

See comment above. Maybe

  Removes the frontmost "full" T from the queue by swapping it with the "empty"
T *output.

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+  // 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) {

[kwiberg-webrtc, 2015/10/27 12:05:13]

WARN_UNUSED_RESULT?

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+    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() {

[kwiberg-webrtc, 2015/10/27 12:05:13]

I'd say it ought to be "Contents". See e.g.
http://dictionary.cambridge.org/grammar/british-grammar/content-or-contents.

[peah-webrtc, 2015/10/29 06:15:14]

Done.

+    rtc::CritScope cs(&crit_queue_);
+    for (const auto& v : queue_) {
+      RTC_DCHECK(queue_item_verifier_(v));
+    }
+    return true;
+  }
+
+  QueueItemVerifier queue_item_verifier_;
+
+  rtc::CriticalSection crit_queue_;
+
+  // (next_read_index_ + num_elements_) % queue_.size() =
+  //  next_write_index_
+  // 0 <= next_write_index_ < queue.size()
+  size_t next_write_index_ GUARDED_BY(crit_queue_) = 0;
+  // 0 <= next_read_index_ < queue.size()
+  size_t next_read_index_ GUARDED_BY(crit_queue_) = 0;
+
+  // 0 <= num_elements_ < queue.size()
+  size_t num_elements_ GUARDED_BY(crit_queue_) = 0;
+
+  // queue_.size() is constant.
+  std::vector<T> queue_ GUARDED_BY(crit_queue_);
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue);
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_