Changed queue implementation to the proposed vector-based solution.

webrtc/common_audio/swap_queue_unittest.cc

Index: webrtc/common_audio/swap_queue_unittest.cc
diff --git a/webrtc/common_audio/swap_queue_unittest.cc b/webrtc/common_audio/swap_queue_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..136ac4615e3638a1e1a76d816fb24f15ae279d98
--- /dev/null
+++ b/webrtc/common_audio/swap_queue_unittest.cc
@@ -0,0 +1,260 @@
+/*
+ *  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.
+ */
+
+#include "webrtc/common_audio/swap_queue.h"
+
+#include <vector>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace webrtc {
+
+namespace {
+
+// The type for a message.
+class TestMessage {
+ public:
+  TestMessage() {
+    id_ = -1;
+    info_ = -1;
+  }
+
+  TestMessage(const TestMessage& m) : id_(m.id_), info_(m.info_) {}

[kwiberg-webrtc, 2015/10/29 14:40:35]

This constructor uses a member initializer list. The other two constructors
should, too.

Oh, and this is precisely like the copy constructor the compiler would generate
for you, so just =default it.

[peah-webrtc, 2015/10/29 15:24:53]

Done.

+
+  TestMessage(int id, int info) {
+    id_ = id;
+    info_ = info;
+  }
+
+  bool operator==(const TestMessage& m) const {
+    return (id_ == m.id_ && info_ == m.info_);
+  }

[kwiberg-webrtc, 2015/10/29 14:40:35]

Style: I prefer using the non-member form of operators like ==, since that
emphasizes that it's symmetrical in the two arguments. (It's perfectly fine to
do it this way too, though.)

  friend bool operator==(const TestMessage& a, const TestMessage& b) {
    return a.id_ == b.id_ && a.info_ == b.info_;
  }

[peah-webrtc, 2015/10/29 15:24:53]

Done.

+
+  void swap(TestMessage& m) {
+    std::swap(id_, m.id_);
+    std::swap(info_, m.info_);
+  }

[kwiberg-webrtc, 2015/10/29 14:40:36]

This swap function won't be found by the standard swap idiom; if you insert
debug printouts, you should find that callers use three copies instead (since
that's what std::swap falls back to). Do this instead:

  friend void swap(TestMessage& a, TestMessage& b) {
    std::swap(id_, m.id_);
    std::swap(info_, m.info_);
  }

See http://en.cppreference.com/w/cpp/concept/Swappable for details.

Hmm. Sine this is test code, and the penalty for copying this class is tiny
anyway, you could just skip implementing swap altogether...

[peah-webrtc, 2015/10/29 15:24:52]

Done.

+
+ private:
+  int id_;
+  int info_;
+};

[kwiberg-webrtc, 2015/10/29 14:40:35]

Sooo... what are id id and info for? Couldn't you eliminate this whole class,
and just use e.g. int instead?

[peah-webrtc, 2015/10/29 15:24:52]

Good point! It feels rather redundant.

Done.

+
+// Test parameter for the basic sample based SwapQueue Tests.
+const size_t kChunkSize = 3;
+
+// Queue item verification function for the vector test.
+bool LengthVerifierFunction(const std::vector<int>& v) {
+  return v.size() == kChunkSize;
+}
+
+// Queue item verifier for the vector test.
+class LengthVerifierFunctor {
+ public:
+  explicit LengthVerifierFunctor(size_t length) : length_(length) {}
+
+  bool operator()(const std::vector<int>& v) const {
+    return v.size() == length_;
+  }
+
+ private:
+  size_t length_;
+};
+
+}  // anonymous namespace
+
+TEST(SwapQueueTest, BasicOperation) {
+  std::vector<int> i(kChunkSize, 0);
+  SwapQueue<std::vector<int>> queue(2, i);
+
+  EXPECT_TRUE(queue.Insert(&i));
+  EXPECT_EQ(i.size(), kChunkSize);
+  EXPECT_TRUE(queue.Insert(&i));
+  EXPECT_EQ(i.size(), kChunkSize);
+  EXPECT_TRUE(queue.Remove(&i));
+  EXPECT_EQ(i.size(), kChunkSize);
+  EXPECT_TRUE(queue.Remove(&i));
+  EXPECT_EQ(i.size(), kChunkSize);
+}
+
+TEST(SwapQueueTest, FullQueue) {
+  SwapQueue<int> queue(2);
+
+  // Fill the queue.
+  int i = 0;
+  EXPECT_TRUE(queue.Insert(&i));
+  i = 1;
+  EXPECT_TRUE(queue.Insert(&i));
+
+  // Ensure that the value is not swapped when doing an Insert
+  // on a full queue.
+  i = 2;
+  EXPECT_FALSE(queue.Insert(&i));
+  EXPECT_EQ(i, 2);

[kwiberg-webrtc, 2015/10/29 14:40:35]

You should have initialized the empty slots to some easily identifiable value
that isn't 2. I know there aren't any empty slots at this point, but that's what
you're testing for.

[peah-webrtc, 2015/10/29 15:24:53]

That I don't really follow. There is no way to initialize the empty slots to
anything other than via inserting items into the queue, right? Otherwise, the
slots will be default initialized to zero.

In the test I 
-Initialize the slots to 0 and 1 by inserting those two elements into the 2
element long queue.
-Then I try to insert 2, which I check fails according to the spec.
-The I check that the value in i has not been swapped to any element from the
queue (which I know is either 0 and 1).

I cannot see what more I can check with this?

+
+  // Ensure that the queue is not overwritten when doing an Insert

[the sun, 2015/10/29 12:48:18]

?? You're Remove()ing here.

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

I changed the comment to make it more clear.

Done.

[kwiberg-webrtc, 2015/10/29 14:40:35]

He's testing that the Insert on line 99 didn't overwrite. Maybe word it as

  Ensure that the Insert didn't overwrite anything in the queue.

[peah-webrtc, 2015/10/29 15:24:52]

Done.

+  // on a full queue.
+  EXPECT_TRUE(queue.Remove(&i));
+  EXPECT_EQ(i, 0);

[kwiberg-webrtc, 2015/10/29 14:40:35]

To make the test watertight, you should probably examine every element in the
queue, not just the frontmost one.

[peah-webrtc, 2015/10/29 15:24:52]

Good point!
Done.

+}
+
+TEST(SwapQueueTest, EmptyQueue) {
+  SwapQueue<int> queue(2);
+  int i = 0;
+  EXPECT_FALSE(queue.Remove(&i));
+  EXPECT_TRUE(queue.Insert(&i));
+  EXPECT_TRUE(queue.Remove(&i));
+  EXPECT_FALSE(queue.Remove(&i));
+}
+
+TEST(SwapQueueTest, Clear) {
+  SwapQueue<int> queue(2);
+  int i = 0;
+
+  // Fill the queue.
+  EXPECT_TRUE(queue.Insert(&i));
+  EXPECT_TRUE(queue.Insert(&i));
+
+  // Ensure full queue.
+  EXPECT_FALSE(queue.Insert(&i));

[kwiberg-webrtc, 2015/10/29 14:40:35]

Yeah, it doesn't have a size() method, does it? I hadn't thought of that.

[peah-webrtc, 2015/10/29 15:24:53]

Yep, no size check is present.

+
+  // Empty the queue.
+  queue.Clear();
+
+  // Ensure that the queue is no longer full.
+  EXPECT_TRUE(queue.Insert(&i));

[kwiberg-webrtc, 2015/10/29 14:40:35]

Or even better, ensure that it's empty by failing to remove.

[peah-webrtc, 2015/10/29 15:24:53]

I added that as well, and kept the former. It is a bit redundant though. Does
that look ok?

+}
+
+TEST(SwapQueueTest, SuccessfulItemVerifyFunction) {
+  std::vector<int> template_element(kChunkSize);
+  SwapQueue<std::vector<int>,
+            SwapQueueItemVerifier<std::vector<int>, LengthVerifierFunction>>
+      queue(2, template_element);
+  std::vector<int> valid_chunk(kChunkSize, 0);
+
+  EXPECT_TRUE(queue.Insert(&valid_chunk));
+  EXPECT_EQ(valid_chunk.size(), kChunkSize);
+  EXPECT_TRUE(queue.Remove(&valid_chunk));
+  EXPECT_EQ(valid_chunk.size(), kChunkSize);
+}
+
+TEST(SwapQueueTest, SuccessfulItemVerifyFunctor) {
+  std::vector<int> template_element(kChunkSize);
+  LengthVerifierFunctor verifier(kChunkSize);
+  SwapQueue<std::vector<int>, LengthVerifierFunctor> queue(2, verifier,
+                                                           template_element);
+  std::vector<int> valid_chunk(kChunkSize, 0);
+
+  EXPECT_TRUE(queue.Insert(&valid_chunk));
+  EXPECT_EQ(valid_chunk.size(), kChunkSize);
+  EXPECT_TRUE(queue.Remove(&valid_chunk));
+  EXPECT_EQ(valid_chunk.size(), kChunkSize);
+}
+
+#if RTC_DCHECK_IS_ON && GTEST_HAS_DEATH_TEST && !defined(WEBRTC_ANDROID)
+TEST(SwapQueueTest, UnsuccessfulItemVerifyFunctor) {
+  // Queue item verifier for the test.
+  class IntVerifier {
+   public:
+    explicit IntVerifier(int threshold) : threshold_(threshold) {}
+

[the sun, 2015/10/29 12:48:18]

total nit: could lose a blank line or two here

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

Done.

+    bool operator()(const int& i) const { return i > threshold_; }
+
+   private:
+    int threshold_;
+  };
+
+  IntVerifier verifier(-2);
+  SwapQueue<int, IntVerifier> queue(2, verifier);

[kwiberg-webrtc, 2015/10/29 14:40:35]

You should be able to do it like this (untested):

  auto minus_2_verifier = [](const int& i) { return i > -2; }
  SwapQueue<int, decltype(minus_2_verifier)> queue(2, minus_2_verifier);

That'd save ten or so lines.

[peah-webrtc, 2015/10/29 15:24:52]

Nice!
Done.

+
+  int valid_value = 1;
+  int invalid_value = -4;
+  EXPECT_TRUE(queue.Insert(&valid_value));
+  EXPECT_TRUE(queue.Remove(&valid_value));
+  bool result;
+  EXPECT_DEATH(result = queue.Insert(&invalid_value), "");
+}
+
+TEST(SwapQueueTest, UnSuccessfulItemVerifyInsert) {
+  std::vector<int> template_element(kChunkSize);
+  SwapQueue<std::vector<int>,
+            SwapQueueItemVerifier<std::vector<int>, &LengthVerifierFunction>>
+      queue(2, template_element);
+  std::vector<int> invalid_chunk(kChunkSize - 1, 0);
+  bool result;
+  EXPECT_DEATH(result = queue.Insert(&invalid_chunk), "");
+}
+
+TEST(SwapQueueTest, UnSuccessfulItemVerifyRemove) {
+  std::vector<int> template_element(kChunkSize);
+  SwapQueue<std::vector<int>,
+            SwapQueueItemVerifier<std::vector<int>, &LengthVerifierFunction>>
+      queue(2, template_element);
+  std::vector<int> invalid_chunk(kChunkSize - 1, 0);
+  std::vector<int> valid_chunk(kChunkSize, 0);
+  EXPECT_TRUE(queue.Insert(&valid_chunk));
+  EXPECT_EQ(valid_chunk.size(), kChunkSize);
+  bool result;
+  EXPECT_DEATH(result = queue.Remove(&invalid_chunk), "");
+}
+#endif
+
+TEST(SwapQueueTest, MessageContentTest) {
+  const size_t kQueueSize = 200;
+  std::vector<TestMessage> messages;
+  SwapQueue<TestMessage> queue(kQueueSize);
+
+  for (size_t k = 0; k < kQueueSize; k++) {
+    messages.push_back(TestMessage(k % 7, k % 17));

[kwiberg-webrtc, 2015/10/29 14:40:36]

LCM(7,17) = 119 < kQueueSize, so you'll have duplicates.

Again, why not just use e.g. int?

[peah-webrtc, 2015/10/29 15:24:52]

Removed this.

Done.

+  }
+
+  for (size_t k = 0; k < kQueueSize; k++) {
+    TestMessage m(messages[k]);
+    EXPECT_TRUE(queue.Insert(&m));
+  }
+
+  for (size_t k = 0; k < kQueueSize; k++) {
+    TestMessage m;
+    EXPECT_TRUE(queue.Remove(&m));
+    EXPECT_TRUE(m == messages[k]);
+  }
+}
+
+TEST(SwapQueueTest, VectorContentTest) {
+  const size_t kQueueSize = 10;
+  const size_t kFrameLength = 160;
+  const size_t kDataLength = kQueueSize * kFrameLength;
+  std::vector<int16_t> buffer_reader(kFrameLength, 0);
+  std::vector<int16_t> buffer_writer(kFrameLength, 0);
+  std::vector<int16_t> template_queue_element(kFrameLength);

[the sun, 2015/10/29 12:48:18]

unused, remove

[peah-webrtc, 2015/10/29 15:24:53]

Done.

+  SwapQueue<std::vector<int16_t>> queue(kQueueSize,
+                                        std::vector<int16_t>(kFrameLength));
+  std::vector<int16_t> samples(kDataLength);
+
+  for (size_t k = 0; k < kDataLength; k++) {
+    samples[k] = k % 9;
+  }
+
+  for (size_t k = 0; k < kQueueSize; k++) {
+    memcpy(&buffer_writer[0], &samples[k * kFrameLength],
+           kFrameLength * sizeof(samples[0]));

[kwiberg-webrtc, 2015/10/29 14:40:36]

  buffer_writer.clear();
  buffer_writer.insert(buffer_writer.end(), samples + k * kFrameLength,
                       samples + (k + 1) * kFrameLength);

or

  std::copy(samples + k * kFrameLength, samples + (k + 1) * kFrameLength,
            buffer_writer.begin());

but the second alternative doesn't protect against the input sequence being of a
different length than the destination vector.

[peah-webrtc, 2015/10/29 15:24:52]

Done.

+    EXPECT_TRUE(queue.Insert(&buffer_writer));
+  }
+
+  for (size_t k = 0; k < kQueueSize; k++) {
+    EXPECT_TRUE(queue.Remove(&buffer_reader));
+
+    for (size_t j = 0; j < buffer_reader.size(); j++) {
+      EXPECT_EQ(buffer_reader[j], samples[k * kFrameLength + j]);
+    }
+  }
+}
+

[kwiberg-webrtc, 2015/10/29 14:40:36]

I'd like to see tests for 0- and 1-slot queues. They'll provide interesting
corner cases.

[peah-webrtc, 2015/10/29 15:24:53]

Done.

+}  // namespace webrtc