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 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 queue is safe to access the class concurrently from multiple threads.
+//
+// Conceptually, the queue maintains an ordered sequence and an unordered bunch
+// 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.

[kwiberg-webrtc, 2015/10/15 08:55:40]

This text would fit better immediately preceding the SwapQueue class definition.

[kwiberg-webrtc, 2015/10/15 12:47:37]

Also, Fredrik and I worked out an alternative text that's more example- than
math-oriented. The full class description reads:

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.

// 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.

[peah-webrtc, 2015/10/23 09:11:19]

I like that :-) Will change!

+
+// (Internal; please don't use outside this file.)
+// Default item invariance verifier callback function.
+template <typename T>
+bool SwapQueueDefaultItemVerifier(const T&) {
+  return true;
+}
+
+}  // namespace internal
+
+// Queue template implementing a queue of elements of type T and with an
+// optional invariance verifier callback function that verifies

[the sun, 2015/10/15 08:44:00]

Didn't you just say the verifier function doesn't check the invariant? :P

Suggest this line is changed to:
// optional callback function that verifies

[peah-webrtc, 2015/10/23 09:11:19]

Good find! Will fix!

[peah-webrtc, 2015/10/23 09:11:19]

Done.

+// that the queue elements are compliant to a certain requirement.
+template <typename T,
+          bool (*ItemVerifier)(const T&) =

[the sun, 2015/10/15 08:44:01]

I like ItemVerifier

[kwiberg-webrtc, 2015/10/15 08:55:40]

+1

[peah-webrtc, 2015/10/23 09:11:19]

Acknowledged.

[peah-webrtc, 2015/10/23 09:11:19]

Acknowledged.

+              internal::SwapQueueDefaultItemVerifier>
+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) { VerifyQueueContent(); }
+
+  // Creates a queue of size size and fills it with copies of prototype.
+  SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) {
+    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(ItemVerifier(*input));
+
+    rtc::CritScope cs(&crit_queue_);
+
+    if (num_elements_ == queue_.size()) {
+      return false;
+    }
+
+    using std::swap;

[the sun, 2015/10/19 10:36:12]

Maybe a comment here why using std::swap is above actual swap usage, and example
of overloaded swap?

[kwiberg-webrtc, 2015/10/19 10:47:17]

Hmm. Difficult to find a comment that's unobtrusive enough, given that this is
the standard idiom for swapping an arbitrary type. Maybe

  using std::swap;  // Fall back to std::swap if no swap() if found with ADL.
  swap(...);

but personally, I'm inclined to just keep silent and let each reader go through
the process of figuring this out. It doesn't take that much googling, and you
only have to do it once.

[peah-webrtc, 2015/10/23 09:11:19]

I'd also prefer to keep it silent, since it is a standard idiom.

+    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(ItemVerifier(*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.
+  void VerifyQueueContent() {

[the sun, 2015/10/15 08:44:00]

For extra niceness, if we let this function return a bool (always return true),
then the call sites could be:

RTC_DCHECK(VerifyQueueContent());

...and we'd be sure the code is dropped for non-debug builds.

[kwiberg-webrtc, 2015/10/15 08:55:40]

Yes, good idea. And as an added bonus, the line number reported by a failing
check will be more specific.

[peah-webrtc, 2015/10/23 09:11:19]

Done.

[peah-webrtc, 2015/10/23 09:11:19]

Awesome!

[peah-webrtc, 2015/10/23 09:11:19]

Acknowledged.

+    rtc::CritScope cs(&crit_queue_);
+    for (const auto& v : queue_) {
+      RTC_DCHECK(ItemVerifier(v));
+    }
+  }
+
+  // queue_.size() is constant.
+  std::vector<T> queue_ GUARDED_BY(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;
+
+  rtc::CriticalSection crit_queue_;
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue);
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_