Mojo C++ bindings: introduce mojo::internal::deque and use it in MultiplexRouter.

mojo/public/cpp/bindings/tests/deque_unittest.cc

Index: mojo/public/cpp/bindings/tests/deque_unittest.cc
diff --git a/mojo/public/cpp/bindings/tests/deque_unittest.cc b/mojo/public/cpp/bindings/tests/deque_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..debb32376a30ce6f8408448d7296176adcf914a1
--- /dev/null
+++ b/mojo/public/cpp/bindings/tests/deque_unittest.cc
@@ -0,0 +1,259 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "mojo/public/cpp/bindings/lib/deque.h"
+#include "base/memory/ptr_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace mojo {
+namespace test {
+
+template <typename T>
+class DequeAccessor {
+ public:
+  explicit DequeAccessor(internal::deque<T>* value) : value_(value) {}
+
+  size_t front() { return value_->front_; }
+
+  size_t back() { return value_->back_; }
+
+  std::vector<T>& buffer() { return value_->buffer_; }
+
+ private:
+  internal::deque<T>* value_;
+};
+
+namespace {
+
+using internal::deque;
+
+template <typename T>
+struct ElementTraits {
+  static T GetValue(const T& value) { return value; }
+  static T CreateElement(const T& value) { return value; }
+};
+
+template <typename T>
+struct ElementTraits<std::unique_ptr<T>> {
+  static T GetValue(const std::unique_ptr<T>& value) { return *value; }
+  static std::unique_ptr<T> CreateElement(const T& value) {
+    return base::MakeUnique<T>(value);
+  }
+};
+
+template <typename T>
+class DequeTest : public ::testing::Test {};
+
+using CaseList = ::testing::Types<int32_t, std::unique_ptr<int32_t>>;
+
+TYPED_TEST_CASE(DequeTest, CaseList);
+
+TYPED_TEST(DequeTest, PushPop) {
+  using Traits = ElementTraits<TypeParam>;
+
+  deque<TypeParam> deque_object(2);
+  EXPECT_TRUE(deque_object.empty());
+
+  deque_object.push_front(Traits::CreateElement(123));
+  EXPECT_FALSE(deque_object.empty());
+
+  EXPECT_EQ(123, Traits::GetValue(deque_object.front()));
+  EXPECT_EQ(123, Traits::GetValue(deque_object.back()));
+
+  deque_object.push_back(Traits::CreateElement(456));
+
+  EXPECT_EQ(123, Traits::GetValue(deque_object.front()));
+  EXPECT_EQ(456, Traits::GetValue(deque_object.back()));
+
+  deque_object.push_front(Traits::CreateElement(789));
+
+  EXPECT_EQ(789, Traits::GetValue(deque_object.front()));
+  EXPECT_EQ(456, Traits::GetValue(deque_object.back()));
+
+  deque_object.pop_back();
+  EXPECT_EQ(789, Traits::GetValue(deque_object.front()));
+  EXPECT_EQ(123, Traits::GetValue(deque_object.back()));
+
+  deque_object.pop_front();
+  EXPECT_EQ(123, Traits::GetValue(deque_object.front()));
+  EXPECT_EQ(123, Traits::GetValue(deque_object.back()));
+
+  deque_object.pop_front();
+  EXPECT_TRUE(deque_object.empty());
+}
+
+TYPED_TEST(DequeTest, Clear) {
+  using Traits = ElementTraits<TypeParam>;
+
+  deque<TypeParam> deque_object;
+  EXPECT_TRUE(deque_object.empty());
+
+  deque_object.clear();
+  EXPECT_TRUE(deque_object.empty());
+
+  deque_object.push_front(Traits::CreateElement(123));
+  deque_object.push_back(Traits::CreateElement(456));
+  deque_object.push_front(Traits::CreateElement(789));
+
+  deque_object.clear();
+
+  EXPECT_TRUE(deque_object.empty());
+}
+
+TYPED_TEST(DequeTest, Move) {
+  using Traits = ElementTraits<TypeParam>;
+
+  {
+    deque<TypeParam> deque_object;
+    deque_object.push_back(Traits::CreateElement(123));
+    deque_object.push_back(Traits::CreateElement(456));
+    deque_object.push_back(Traits::CreateElement(789));
+
+    deque<TypeParam> deque_object2(std::move(deque_object));
+
+    EXPECT_TRUE(deque_object.empty());
+
+    EXPECT_EQ(123, Traits::GetValue(deque_object2.front()));
+    deque_object2.pop_front();
+    EXPECT_EQ(456, Traits::GetValue(deque_object2.front()));
+    deque_object2.pop_front();
+    EXPECT_EQ(789, Traits::GetValue(deque_object2.front()));
+
+    // |deque_object| is still in valid state and could be reused.
+    deque_object.push_back(Traits::CreateElement(321));
+    EXPECT_EQ(321, Traits::GetValue(deque_object.front()));
+    EXPECT_EQ(321, Traits::GetValue(deque_object.back()));
+  }
+
+  {
+    deque<TypeParam> deque_object;
+    deque_object.push_back(Traits::CreateElement(123));
+    deque_object.push_back(Traits::CreateElement(456));
+    deque_object.push_back(Traits::CreateElement(789));
+
+    deque<TypeParam> deque_object2;
+    deque_object2 = std::move(deque_object);
+
+    EXPECT_TRUE(deque_object.empty());
+
+    EXPECT_EQ(123, Traits::GetValue(deque_object2.front()));
+    deque_object2.pop_front();
+    EXPECT_EQ(456, Traits::GetValue(deque_object2.front()));
+    deque_object2.pop_front();
+    EXPECT_EQ(789, Traits::GetValue(deque_object2.front()));
+
+    // |deque_object| is still in valid state and could be reused.
+    deque_object.push_back(Traits::CreateElement(321));
+    EXPECT_EQ(321, Traits::GetValue(deque_object.front()));
+    EXPECT_EQ(321, Traits::GetValue(deque_object.back()));
+  }
+}
+
+// Constructs a deque with a fully occupied ring buffer.
+// |front_index| is the position of the front element in the ring buffer.
+// |values| stores the values from front to back.
+template <typename T>
+void ConstructFullDeque(const std::vector<int32_t>& values,
+                        size_t front_index,
+                        deque<T>* deque_object) {
+  using Traits = ElementTraits<T>;
+
+  DCHECK_LT(front_index, values.size());
+  *deque_object = deque<T>(values.size());
+
+  // Push some temp elements to make sure the desired front element starts at
+  // |front_index|.
+  for (size_t i = 0; i < front_index; ++i)
+    deque_object->push_back(Traits::CreateElement(0));
+
+  deque_object->push_back(Traits::CreateElement(values[0]));
+
+  for (size_t i = 0; i < front_index; ++i)
+    deque_object->pop_front();
+
+  for (size_t i = 1; i < values.size(); ++i)
+    deque_object->push_back(Traits::CreateElement(values[i]));
+}
+
+template <typename T>
+void VerifyDequeInternalState(deque<T>* deque_object,
+                              size_t expected_front,
+                              size_t expected_back,
+                              const std::vector<int32_t>& expected_values,
+                              size_t expected_ring_buffer_size) {
+  using Traits = ElementTraits<T>;
+
+  DequeAccessor<T> accessor(deque_object);
+
+  EXPECT_EQ(expected_front, accessor.front());
+  EXPECT_EQ(expected_back, accessor.back());
+  EXPECT_EQ(expected_ring_buffer_size, accessor.buffer().size());
+
+  size_t index = expected_front;
+  for (size_t i = 0; i < expected_values.size(); ++i) {
+    EXPECT_EQ(expected_values[i], Traits::GetValue(accessor.buffer()[index]));
+    index++;
+    if (index == accessor.buffer().size())
+      index = 0;
+  }
+}
+
+TYPED_TEST(DequeTest, ExpandWhiteBox) {
+  using Traits = ElementTraits<TypeParam>;
+
+  // Test ConstructFullDeque() and VerifyDequeInternalState().
+  {
+    deque<TypeParam> deque_object;
+    ConstructFullDeque({1, 2, 3}, 0, &deque_object);
+    VerifyDequeInternalState(&deque_object, 0, 2, {1, 2, 3}, 3);
+
+    deque<TypeParam> deque_object1;
+    ConstructFullDeque({1, 2, 3}, 1, &deque_object1);
+    VerifyDequeInternalState(&deque_object1, 1, 0, {1, 2, 3}, 3);
+  }
+
+  // Test that ring buffer [1(front), 2, 3(back)] becomes
+  // [1(front), 2, 3, 4(back), _, _] after push_back(4).
+  {
+    deque<TypeParam> deque_object;
+    ConstructFullDeque({1, 2, 3}, 0, &deque_object);
+
+    deque_object.push_back(Traits::CreateElement(4));
+    VerifyDequeInternalState(&deque_object, 0, 3, {1, 2, 3, 4}, 6);
+  }
+
+  // Test that ring buffer [1(front), 2, 3(back)] becomes
+  // [1, 2, 3(back), _, _, 4(front)] after push_front(4).
+  {
+    deque<TypeParam> deque_object;
+    ConstructFullDeque({1, 2, 3}, 0, &deque_object);
+
+    deque_object.push_front(Traits::CreateElement(4));
+    VerifyDequeInternalState(&deque_object, 5, 2, {4, 1, 2, 3}, 6);
+  }
+
+  // Test that ring buffer [3(back), 1(front), 2] becomes
+  // [_, 1(front), 2, 3, 4(back), _] after push_back(4).
+  {
+    deque<TypeParam> deque_object;
+    ConstructFullDeque({1, 2, 3}, 1, &deque_object);
+
+    deque_object.push_back(Traits::CreateElement(4));
+    VerifyDequeInternalState(&deque_object, 1, 4, {1, 2, 3, 4}, 6);
+  }
+
+  // Test that ring buffer [2, 3(back), 1(front)] becomes
+  // [2, 3, 4(back), _, _, 1(front)] after push_back(4).
+  {
+    deque<TypeParam> deque_object;
+    ConstructFullDeque({1, 2, 3}, 2, &deque_object);
+
+    deque_object.push_back(Traits::CreateElement(4));
+    VerifyDequeInternalState(&deque_object, 5, 2, {1, 2, 3, 4}, 6);
+  }
+}
+
+}  // namespace
+}  // namespace test
+}  // namespace mojo