Changed queue implementation to the proposed vector-based solution.

webrtc/modules/audio_processing/swap_queue.h

Index: webrtc/modules/audio_processing/swap_queue.h
diff --git a/webrtc/modules/audio_processing/swap_queue.h b/webrtc/modules/audio_processing/swap_queue.h
new file mode 100644
index 0000000000000000000000000000000000000000..ff63c669a6286568c771ff4ed535ac9526637df4
--- /dev/null
+++ b/webrtc/modules/audio_processing/swap_queue.h
@@ -0,0 +1,131 @@
+/*
+ *  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_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_
+#define WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_

[kwiberg-webrtc, 2015/10/12 14:05:48]

The include guard name needs updating.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/criticalsection.h"
+
+namespace webrtc {
+
+// This class is to be used as a one-way queue where data is

[kwiberg-webrtc, 2015/10/12 14:05:48]

It actually *is* a one-way queue.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+// written from one end and read from the other end.
+// It is safe to access the class concurrently from multiple threads.

[The Sun (google.com), 2015/10/13 07:53:05]

Will git cl format fix the alignment of comment lines to 80 chars?

[peah-webrtc, 2015/10/13 11:56:13]

You mean whether multiline comments are rearranged to fit better on 80 chars?

[the sun, 2015/10/13 12:34:27]

yes

[peah-webrtc, 2015/10/26 08:56:56]

Acknowledged.

+// The queueable objects must all be swappable.
+//
+// When T is a vector, one way of us using this class is by leveraging that

[The Sun (google.com), 2015/10/13 07:53:05]

What you describe is the general intention of this design; it is not limited to
vectors. Please describe the general case before talking about a specific case.
Also, an example with pseudo code would likely be useful, or referring to a
specific unit test case that illustrates clearly the use.

[peah-webrtc, 2015/10/13 11:56:13]

I fully agree. I revised the description, and added a pseudocode example. Could
you please check that it looks what you indented it to be!

+// the vector returned (via a swap) when doing an Insert can be reused if
+// the queue is properly initialized. For instance, if the queue is initialized
+// with N elements sized vectors, and the vectors passed to the Insert and
+// Remove methods also are always N elements long, the vector returned from
+// the Insert method always have a size of N, allowing for a cheap scheme of
+// avoiding vector reallocations.
+template <typename T>
+class SwapQueue {

[kwiberg-webrtc, 2015/10/12 14:05:48]

It might be a good idea to reflect the threadsafeness in the class name, since
the usual case is for simple data structures not to be threadsafe.
ThreadsafeSwapQueue?

[The Sun (google.com), 2015/10/13 07:53:05]

+1 -1

I think that is a good idea assuming we are moving towards a world where nothing
is thread safe except for things that begin with "Threadsafe".
I think it is a bad idea to have that annotation in the name since we likely
will never reach that point, but still can assume nothing about thread
safeness...

[kwiberg-webrtc, 2015/10/13 09:59:53]

OK. Then I suggest to err on the side of brevity.

[peah-webrtc, 2015/10/13 11:56:12]

How about omitting threadsafety in the name, but opening up for this to be
explicitly turned on/off in the constructor and having two internal code-paths,
one threadsafe and one which is not?

[kwiberg-webrtc, 2015/10/13 12:09:07]

Dynamically taking locks or not would make the code more complicated than
necessary. I'd suggest locking unconditionally like you do now, or possibly
passing the mutex type as a second (optional) template parameter. But... no,
just keep the current code until you see a need for a non-threadsafe variant.

[peah-webrtc, 2015/10/26 08:56:56]

Acknowledged.

+ public:
+  // Creates a queue of size size.

[kwiberg-webrtc, 2015/10/12 14:05:48]

Document that this fills the queue with the specified number of
default-constructed Ts.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+  explicit SwapQueue(size_t size) { queue_.resize(size); }

[kwiberg-webrtc, 2015/10/12 14:05:48]

explicit SwapQueue(size_t size) : queue_(size) {}

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+
+  // Creates a queue of size size and initializes each element
+  // to have the same size and content of initializer (useful to
+  // ensure a certain initial size when T is a vector).
+  explicit SwapQueue<T>(size_t size, const T& initializer)
+      : SwapQueue<T>(size) {

[The Sun (google.com), 2015/10/13 07:53:05]

: queue_(size, initializer) {

i.e. don't default-construct, then copy-construct.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+    queue_ = std::vector<T>(size, initializer);
+  }

[kwiberg-webrtc, 2015/10/12 14:05:48]

"explicit" is only needed for one-argument constructors.

No <T> needed.

Call queue_'s constructor with two arguments: size and initializer.

Don't call the other SwapQueue constructor---that will initialize queue_ twice.

I don't think the example of T == std::vector in the comment helps.

And it's probably unnecessary to have this constructor at all; the first and
third one seem sufficient.

[peah-webrtc, 2015/10/13 11:56:13]

I removed this constructor.

[the sun, 2015/10/13 12:34:26]

But why? Supplying a prototype object which is copied to each slot sounds less
error prone than relying on the client to construct the full vector used in the
queue (as with the ctor below).

[kwiberg-webrtc, 2015/10/13 14:08:36]

Sure, it might be a convenient shortcut.

+
+  // Ensures that the internal queue elements of type vector
+  // are formed as in the supplied empty slots input

[kwiberg-webrtc, 2015/10/12 14:05:48]

Maybe just

  // Create a queue with "empty" Ts from the given
  // vector. (The constructor will steal the contents from
  // the supplied vector, leaving it empty.)

This probably works best in conjunction with a longer explanation of "full" and
"empty" Ts, maybe in the class description.

[peah-webrtc, 2015/10/13 11:56:13]

Excellent suggestion. 

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+  // TODO(peah): Change to std::vector<T>&& when we have a C++11
+  // standard library.

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

Actually, I realized on the way home that we only need the language part of
C++11. Like this:

  explicit SwapQueue(std::vector<T>&& empty_slots) {
    RTC_CHECK_GE(empty_slots->size(), 1u);
    using std::swap;
    swap(queue_, empty_slots);
  }

To create a queue with n default-constructed "empty" slots:

  SwapQueue<T>(std::vector<T>(n));

With n "empty" slots copy-constructed from t:

  SwapQueue<T>(std::vector<T>(n, t));

With some more elaborately constructed vector of Ts:

  std::vector<T> vt;
  // Fill it!
  SwapQueue<T>(static_cast<std::vector<T>&&>(vt));

The C++11 standard library would let us use std::move instead of a cast in the
third example, but that's all.

[peah-webrtc, 2015/10/13 11:56:12]

Nice! But I get a cl upload warning that the below passing of the references is
not allowed, so therefore I did not add this. Ok?

+  //
+  // If using the above described scheme that ensures that all elements in the
+  // queue are of the same size, this is achieved if the following constructor
+  // is used with an input of vectors having the same size.

[kwiberg-webrtc, 2015/10/12 14:05:48]

You repeat this several times. Maybe just once, in the class description?

I think it might be useful to phrase it in terms of "full" and "empty" Ts: The
Ts passed to (or created by) the queue's constructor are "empty". Insert swaps a
"full" T for an "empty" T, and Remove does the opposite. Except for in the
constructors and the destructor, the queue never creates or destroys Ts, just
swaps them, so it's guaranteed that the "empty" Ts you get from Insert are the
same as the "empty" Ts given to Remove (or passed to/created by the
constructors). It follows that if you want the "empty" Ts returned by Insert to
have some property such as a certain size, just ensure that the Ts you give to
the constructor and Remove have that property.

Clear is a special case; it moves all Ts currently in the "full" bucket to the
"empty" bucket. This makes the queue harder to explain, which is one reason it'd
be nice to not have it.

Another thing that would make the queue easier to explain would be if you had
only the third constructor, so that you could claim simply that it never creates
Ts.

[The Sun (google.com), 2015/10/13 07:53:05]

It is confusing that you talk about "input of vectors", yet the argument to the
ctor is a pointer to one vector (or should I interpret it as a pointer to a C
array of vectors?). Avoid the specific use case when describing how the class
works. Use that in an example instead.

Seems there's some insight here that I'm missing. Why do we need to make special
concessions to handle the case when T is a std::vector?

[kwiberg-webrtc, 2015/10/13 09:59:53]

We don't. std::vector is less convenient than it could be because it needs a
constructor argument to make a nonzero-sized vector, and no constructor will
create a vector with a given capacity != size. But such is the case for other
choices of T too, so I agree it makes more sense to describe it generically in
the text and point to an example that uses vectors.

[peah-webrtc, 2015/10/13 11:56:13]

I made an attempt to do that. Could you please have a look at the current
comment scheme!

[peah-webrtc, 2015/10/13 11:56:13]

I agree about repetition, and I removed that part.¸I also revised the class
description quite a lot but I could not really fit the above scheme well. Could
you please check to see whether you think it is ok!

+  explicit SwapQueue(std::vector<T>* empty_slots) {
+    RTC_CHECK_GE(empty_slots->size(), 1u);
+    using std::swap;

[The Sun (google.com), 2015/10/13 07:53:05]

Why not just do std::swap on the line below?

[kwiberg-webrtc, 2015/10/13 09:59:53]

Because the author of T might have defined a swap(T&, T&) that can be found
through ADL. Or she might not, in which case we'll end up calling std::swap
since we just invited it to our scope.

See e.g. http://en.cppreference.com/w/cpp/concept/Swappable,
http://en.cppreference.com/w/cpp/algorithm/swap,
http://stackoverflow.com/questions/6380862/how-to-provide-a-swap-function-for...,
and Item 25 in Effective C++.

[peah-webrtc, 2015/10/13 11:56:13]

I kept it as it is for now. Please let me know if you are happy with the change.

[peah-webrtc, 2015/10/13 11:56:13]

Acknowledged.

[the sun, 2015/10/13 12:34:27]

Great! Thanks for the explanation.

+    swap(queue_, *empty_slots);
+  }
+
+  // Resets the queue to have zero content.
+  void Clear() {
+    rtc::CritScope cs(&crit_queue_);
+    last_write_index_ = 0;
+    last_read_index_ = 0;
+    num_elements_ = 0;
+  }
+
+  // Inserts a chunk of data into the queue in a thread safe manner.

[kwiberg-webrtc, 2015/10/12 14:05:48]

Document thread safety once, in the class description. Every operation should be
safe.

[peah-webrtc, 2015/10/13 11:56:12]

Done.

+  // The input is swapped with the next available value of type T
+  // present in the queue.
+  // Returns false if the queue is full, and true if not.

[kwiberg-webrtc, 2015/10/12 14:05:48]

Document that the operation is a no-op iff it returns false.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+  //
+  // Note that in the case of T being a vector, if using the above described

[The Sun (google.com), 2015/10/13 07:53:05]

Please remove these comments. Too much text will make people not read it.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+  // scheme to ensure that all elements in the queue are of the same size, the
+  // resulting content in input after the swap also has the same size.
+  bool Insert(T* input) {
+    rtc::CritScope cs(&crit_queue_);
+
+    // Early return if the queue is full.
+    if (num_elements_ == queue_.size())
+      return false;
+
+    last_write_index_ =
+        (last_write_index_ < (queue_.size() - 1) ? last_write_index_ + 1 : 0);
+
+    using std::swap;
+    swap(*input, queue_[last_write_index_]);
+
+    num_elements_++;
+    return true;
+  }
+
+  // Removes a chunk of data from the queue in a thread safe manner.
+  // The queue element is swapped with the previous content of output.
+  // Returns false if the queue is empty, and true if not.

[kwiberg-webrtc, 2015/10/12 14:05:48]

Same as above: document thread safety once, and say it's a no-op iff it returns
false.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+  //
+  // Note that in the case of T being a vector, if using the above described
+  // scheme to ensure that all elements in the queue are of the same size,
+  // it is important to ensure that the initial content of output has the
+  // same size as the content in the queue.
+  bool Remove(T* output) {
+    rtc::CritScope cs(&crit_queue_);
+
+    // Early return for empty queue.
+    if (num_elements_ == 0)
+      return false;
+
+    last_read_index_ =
+        (last_read_index_ < (queue_.size() - 1) ? last_read_index_ + 1 : 0);

[The Sun (google.com), 2015/10/13 07:53:05]

I'd rather you

last_read_index_++;
if (last_read_index_ >= queue_.size()) {
  last_read_index_ = 0;
}

here and elsewhere

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+    output->swap(queue_[last_read_index_]);

[kwiberg-webrtc, 2015/10/12 14:05:48]

Use the same swap idiom as above.

[peah-webrtc, 2015/10/13 11:56:13]

Done.

+
+    num_elements_--;
+    return true;
+  }
+
+ private:
+  std::vector<T> queue_ GUARDED_BY(crit_queue_);
+  size_t last_write_index_ GUARDED_BY(crit_queue_) = 0;
+  size_t last_read_index_ GUARDED_BY(crit_queue_) = 0;
+  size_t num_elements_ GUARDED_BY(crit_queue_) = 0;

[kwiberg-webrtc, 2015/10/12 14:05:48]

Document the invariants: queue_.size() never changes, 0 <= num_elements_ <=
queue_.size(), last_read_index_ + num_elements_ = last_write_index_ mod
queue_.size() (with the two indices equal iff the queue is full or empty).

And note that by using last_*_index instead of next_*_index, you use the slots
in the slightly inelegant order 1, 2, 3, ..., size-1, 0, 1, 2, ...

[peah-webrtc, 2015/10/13 11:56:13]

Done.

[peah-webrtc, 2015/10/13 11:56:13]

Good point! I changed to using next, and added the comments.

+  rtc::CriticalSection crit_queue_;
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue);
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_