Changed queue implementation to the proposed vector-based solution.

webrtc/common_audio/swap_queue.h

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..9aa3127343b1449c2b46d4c1fea9c46a690b2adf
--- /dev/null
+++ b/webrtc/common_audio/swap_queue.h
@@ -0,0 +1,169 @@
+/*
+ *  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_SWAPPED_QUEUE_H_
+#define WEBRTC_MODULES_SWAPPED_QUEUE_H_

[kwiberg-webrtc, 2015/10/13 13:54:23]

Still behind the times!

[peah-webrtc, 2015/10/14 12:16:47]

Ouch, good find!

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/criticalsection.h"
+
+namespace webrtc {
+
+// This class is a one-way queue where data is written from one end and read
+// from the other end.
+// It is safe to access the class concurrently from multiple threads.
+// The queueable objects must all be swappable as the Insert and Remove methods
+// work by swapping the inputs with the element that is modified in the queue.
+// This is illustrated in the pseudocode example below:
+//
+// Pseudocode example of queue usage:

[kwiberg-webrtc, 2015/10/13 13:54:23]

What's pseudo about this code?

[peah-webrtc, 2015/10/14 12:16:47]

:-) Removed pseudo

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+// SwapQueue<int> q(std::vector<int>(2, 0)); // q contains [0 0];

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

You can't do this with the class as it is defined in this patch set.

[peah-webrtc, 2015/10/14 12:16:47]

Fully correct! I changed it a bit to signify that we initially have undefined
values in the queue.

+// 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 Ts that are returned from the Insert
+// to be of a special size, care must be taken that the queue is initialized

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

This has nothing to do with "size". If the caller relies on *any* property of
the objects returned, it must make sure that:
1. the queue is initialized with objects with such properties
2. any objects supplied to insert or remove also have such properties.

I think we should add an invariant-check callback functor so that we can
RTC_DCHECK() that the expected conditions are always met. WDYT?

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

Yes, we should definitely do that. (And by "we", we obviously mean you, Per.
Fredrik and I are much too busy telling you what you're doing wrong.)

[The Sun (google.com), 2015/10/13 14:19:45]

Evidently, given the number of comments we've managed to produce.

Btw, the predicate should be an optional template argument so that the check is
considered part of the queue type.

[peah-webrtc, 2015/10/14 12:16:47]

Revised according to discussion.

+// with elements of that size, and all Ts that are used as input to Remove
+// must be of that same size. This is important when the sizes of the Ts are
+// dynamic. A pseudocode example of this is shown below where no vector resizing

[kwiberg-webrtc, 2015/10/13 13:54:23]

Instead of talking about the size of the Ts, just point out that the Ts you get
out are the same ones you put in in Remove and the constructor. The last
sentence ("A pseudocode example...") then establishes what this means for Ts
with variable-size heap allocations.

[peah-webrtc, 2015/10/14 12:16:47]

I rewrote and rephrased, could you please have a look again!

+// is required apart from the one done during the initialization.
+//
+// Pseudocode example of queue usage with vector:

[kwiberg-webrtc, 2015/10/13 13:54:23]

Why pseudo?

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+//  // Initialization of vector to only hold vectors of the same size.
+//  const size_t kChunkSize = 1000;
+//  const size_t kDelay = 10;
+//  std::vector<std::vector<int>> v_init(kDelay);
+//  for (int k = 0; k < 2; k++)
+//    v_init[k].resize(kChunkSize);

[kwiberg-webrtc, 2015/10/13 13:54:23]

Use a for (auto& v : v_init) loop. That will initialize the whole vector, not
just the first two elements, but that might be OK?

[peah-webrtc, 2015/10/14 12:16:47]

Rewrote this.

+//  SwapQueue<int> queue(&v_init);
+//
+//  // Initialization of input buffers to be of the same
+//  std::vector<int> input;
+//  std::vector<int> output;
+//  input.resize(kChunkSize);
+//  delayed_output.resize(kChunkSize);

[kwiberg-webrtc, 2015/10/13 13:54:23]

std::vector<int> input(kChunkSize);
std::vector<int> output(kChunkSize);

[peah-webrtc, 2015/10/14 12:16:48]

Done.

+//
+//  // Read int values in chunks and delay them with the length of the queue.
+//  int read_samples = 1;
+//  while (read_values == kChunkSize) {
+//    read_values = function_that_copies_ints_from_file_into_vector(&input);

[kwiberg-webrtc, 2015/10/13 13:54:23]

read_samples or read_values?

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+//    queue.Insert(&input);
+//    queue.Remove(&output);
+//    function_that_does_something(&output);
+//  }

[kwiberg-webrtc, 2015/10/13 13:54:24]

This example is probably a bit too long to clearly illustrate the point, and
doesn't reflect the intended real-world usage. It might be better to make a real
unit test with a toy producer and a toy consumer, and have EXPECTs on the
vectors' .capacity() that ensure that no run-time reallocation of vectors takes
place.

[peah-webrtc, 2015/10/14 12:16:47]

I have that as well, should I just refer to that instead and remove this
example?

[kwiberg-webrtc, 2015/10/14 14:10:16]

Yes, provided it's small and clean enough to work as an illustrative example.

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

Acknowledged.

+template <typename T>
+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) {}
+
+  // Create a queue with "empty" Ts from the given

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

It does not create a queue with empty Ts. It creates a queue that has precisely
the contents of the given "prototype" vector.

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+  // vector. (The constructor will steal the contents from
+  // the supplied vector, leaving it empty.)
+  // TODO(peah): Change to std::vector<T>&& when we have a C++11
+  // standard library.

[kwiberg-webrtc, 2015/10/13 13:54:23]

This turned out to not be allowed by the relevant style guides, so remove the
TODO.

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+  //
+  // If used when T is a vector and the above described pattern that ensures

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

Remove this comment, it is confusing

+  // 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/13 13:54:23]

Remove this paragraph. The class documentation already explains why you'd
conceivably want non-default-constructed Ts in the "empty" slots.

[peah-webrtc, 2015/10/14 12:16:47]

Done.

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

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

That's not actually a requirement. The code works anyway.

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+    using std::swap;
+    swap(queue_, *empty_slots);
+  }
+
+  // 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 chunk of data into the queue. The input is swapped with the next

[kwiberg-webrtc, 2015/10/13 13:54:23]

"chunk of data" -> "T"

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+  // available value of type T present in the queue.

[kwiberg-webrtc, 2015/10/13 13:54:23]

This doesn't make it clear that the queue makes a sharp distinction between
"empty" and "full" Ts; on the contrary, it suggests that you swap out a
previously inserted T. Maybe

  ...is swapped with the least recently inserted "empty" T.

But that requires the class doc to have introduced "empty" and "full", or
something equivalent.

[peah-webrtc, 2015/10/14 12:16:47]

I agree that the full/empty description simplifies things. I rewrote the
documentation accordingly. Please check to see what you think about it!

+  // Returns false if the queue is full (in which case no insert is performed),

[kwiberg-webrtc, 2015/10/13 13:54:24]

"is full" -> "was already full"

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+  // and true if not.
+  bool Insert(T* input) {
+    rtc::CritScope cs(&crit_queue_);
+
+    // Early return if the queue is full.

[kwiberg-webrtc, 2015/10/13 13:54:23]

This comment is not necessary.

[peah-webrtc, 2015/10/14 12:16:48]

Done.

+    if (num_elements_ == queue_.size())

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

Ohh, braces, please...

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

But they just make the code harder to read...

[The Sun (google.com), 2015/10/13 14:19:45]

No, they make sure the reader isn't ever fooled by messed up indentation (and
makes it less easy to introduce cut+paste bugs).

[peah-webrtc, 2015/10/14 12:16:47]

Added braces :-)

+      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 chunk of data from the queue. The queue element is swapped with
+  // the previous content of output.
+  // Returns false if the queue is empty (om which case no element is removed),
+  // and true if not.

[kwiberg-webrtc, 2015/10/13 13:54:23]

See the three comments on the Insert doc.

[peah-webrtc, 2015/10/14 12:16:48]

Done.

+  bool Remove(T* output) {
+    rtc::CritScope cs(&crit_queue_);
+
+    // Early return for empty queue.

[kwiberg-webrtc, 2015/10/13 13:54:23]

Remove comment.

[peah-webrtc, 2015/10/14 12:16:48]

Done.

+    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:
+  // queue_.size() is constant.
+  std::vector<T> queue_ GUARDED_BY(crit_queue_);
+
+  // (next_read_index_ + num_elements_) % queue_.size() =
+  //  next_write_index_

[kwiberg-webrtc, 2015/10/13 13:54:23]

Also, they're both in the range [0,size).

[peah-webrtc, 2015/10/14 12:16:47]

Done.

+  size_t next_write_index_ GUARDED_BY(crit_queue_) = 0;
+  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_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_