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

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

Index: mojo/public/cpp/bindings/tests/pointer_deque_unittest.cc
diff --git a/mojo/public/cpp/bindings/tests/pointer_deque_unittest.cc b/mojo/public/cpp/bindings/tests/pointer_deque_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..f8eb98a52703e24eb1476a89458f2589f7395854
--- /dev/null
+++ b/mojo/public/cpp/bindings/tests/pointer_deque_unittest.cc
@@ -0,0 +1,322 @@
+// 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/pointer_deque.h"
+#include "base/memory/ptr_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace mojo {
+namespace internal {
+
+template <typename T, bool owned>
+class PointerDequeAccessor {
+ public:
+  explicit PointerDequeAccessor(PointerDeque<T, owned>* deque)
+      : deque_(deque) {}
+
+  size_t front() { return deque_->front_; }
+
+  size_t back() { return deque_->back_; }
+
+  std::vector<typename PointerDeque<T, owned>::ElementType>& buffer() {
+    return deque_->buffer_;
+  }
+
+ private:
+  PointerDeque<T, owned>* deque_;
+};
+
+}  // namespace internal
+
+namespace test {
+namespace {
+
+using mojo::internal::PointerDeque;
+using mojo::internal::PointerDequeAccessor;
+
+struct Element {
+  explicit Element(int32_t in_value) : value(in_value) {}
+  int32_t value = 0;
+};
+
+struct RawPointerCase {
+  static constexpr bool kOwned = false;
+
+  struct ElementWrapper {
+    explicit ElementWrapper(int32_t value) : element_(value) {}
+    Element* ToPointer() { return &element_; }
+
+   private:
+    Element element_;
+    DISALLOW_COPY_AND_ASSIGN(ElementWrapper);
+  };
+
+  using Deque = PointerDeque<Element, kOwned>;
+  using Accessor = PointerDequeAccessor<Element, kOwned>;
+};
+
+struct OwnedPointerCase {
+  static constexpr bool kOwned = true;
+
+  struct ElementWrapper {
+    explicit ElementWrapper(int32_t value)
+        : element_(base::MakeUnique<Element>(value)) {}
+    std::unique_ptr<Element> ToPointer() { return std::move(element_); }
+
+   private:
+    std::unique_ptr<Element> element_;
+    DISALLOW_COPY_AND_ASSIGN(ElementWrapper);
+  };
+
+  using Deque = PointerDeque<Element, kOwned>;
+  using Accessor = PointerDequeAccessor<Element, kOwned>;
+};
+
+template <typename T>
+class PointerDequeTest : public ::testing::Test {
+ public:
+};
+
+using CaseList = ::testing::Types<RawPointerCase, OwnedPointerCase>;
+
+TYPED_TEST_CASE(PointerDequeTest, CaseList);
+
+TYPED_TEST(PointerDequeTest, PushPop) {
+  using ElementWrapper = typename TypeParam::ElementWrapper;
+
+  typename TypeParam::Deque deque(2);
+  EXPECT_TRUE(deque.empty());
+
+  ElementWrapper e0(123);
+  deque.push_front(e0.ToPointer());
+  EXPECT_FALSE(deque.empty());
+
+  EXPECT_EQ(123, deque.front()->value);
+  EXPECT_EQ(123, deque.back()->value);
+
+  ElementWrapper e1(456);
+  deque.push_back(e1.ToPointer());
+
+  EXPECT_EQ(123, deque.front()->value);
+  EXPECT_EQ(456, deque.back()->value);
+
+  ElementWrapper e2(789);
+  deque.push_front(e2.ToPointer());
+
+  EXPECT_EQ(789, deque.front()->value);
+  EXPECT_EQ(456, deque.back()->value);
+
+  deque.pop_back();
+  EXPECT_EQ(789, deque.front()->value);
+  EXPECT_EQ(123, deque.back()->value);
+
+  deque.pop_front();
+  EXPECT_EQ(123, deque.front()->value);
+  EXPECT_EQ(123, deque.back()->value);
+
+  deque.pop_front();
+  EXPECT_TRUE(deque.empty());
+}
+
+TYPED_TEST(PointerDequeTest, Clear) {
+  using ElementWrapper = typename TypeParam::ElementWrapper;
+
+  typename TypeParam::Deque deque;
+  EXPECT_TRUE(deque.empty());
+
+  deque.clear();
+  EXPECT_TRUE(deque.empty());
+
+  ElementWrapper e0(123);
+  deque.push_front(e0.ToPointer());
+  ElementWrapper e1(456);
+  deque.push_back(e1.ToPointer());
+  ElementWrapper e2(789);
+  deque.push_front(e2.ToPointer());
+
+  deque.clear();
+
+  EXPECT_TRUE(deque.empty());
+}
+
+TYPED_TEST(PointerDequeTest, Move) {
+  using ElementWrapper = typename TypeParam::ElementWrapper;
+
+  {
+    typename TypeParam::Deque deque;
+    ElementWrapper e0(123);
+    deque.push_back(e0.ToPointer());
+    ElementWrapper e1(456);
+    deque.push_back(e1.ToPointer());
+    ElementWrapper e2(789);
+    deque.push_back(e2.ToPointer());
+
+    typename TypeParam::Deque deque2(std::move(deque));
+
+    EXPECT_TRUE(deque.empty());
+
+    EXPECT_EQ(123, deque2.front()->value);
+    deque2.pop_front();
+    EXPECT_EQ(456, deque2.front()->value);
+    deque2.pop_front();
+    EXPECT_EQ(789, deque2.front()->value);
+
+    // |deque| is still in valid state and could be reused.
+    ElementWrapper e4(321);
+    deque.push_back(e4.ToPointer());
+    EXPECT_EQ(321, deque.front()->value);
+    EXPECT_EQ(321, deque.back()->value);
+  }
+
+  {
+    typename TypeParam::Deque deque;
+    ElementWrapper e0(123);
+    deque.push_back(e0.ToPointer());
+    ElementWrapper e1(456);
+    deque.push_back(e1.ToPointer());
+    ElementWrapper e2(789);
+    deque.push_back(e2.ToPointer());
+
+    typename TypeParam::Deque deque2;
+    deque2 = std::move(deque);
+
+    EXPECT_TRUE(deque.empty());
+
+    EXPECT_EQ(123, deque2.front()->value);
+    deque2.pop_front();
+    EXPECT_EQ(456, deque2.front()->value);
+    deque2.pop_front();
+    EXPECT_EQ(789, deque2.front()->value);
+
+    // |deque| is still in valid state and could be reused.
+    ElementWrapper e4(321);
+    deque.push_back(e4.ToPointer());
+    EXPECT_EQ(321, deque.front()->value);
+    EXPECT_EQ(321, deque.back()->value);
+  }
+}
+
+// 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 Deque, typename ElementWrapper>
+void ConstructFullDeque(
+    const std::vector<int32_t>& values,
+    size_t front_index,
+    Deque* deque,
+    std::vector<std::unique_ptr<ElementWrapper>>* wrappers) {
+  DCHECK_LT(front_index, values.size());
+  *deque = Deque(values.size());
+
+  // Push some temp elements to make sure the desired front element starts at
+  // |front_index|.
+  std::vector<std::unique_ptr<ElementWrapper>> temp_storage;
+  for (size_t i = 0; i < front_index; ++i) {
+    temp_storage.emplace_back(base::MakeUnique<ElementWrapper>(0));
+    deque->push_back(temp_storage.back()->ToPointer());
+  }
+
+  wrappers->emplace_back(base::MakeUnique<ElementWrapper>(values[0]));
+  deque->push_back(wrappers->back()->ToPointer());
+
+  for (size_t i = 0; i < front_index; ++i)
+    deque->pop_front();
+
+  for (size_t i = 1; i < values.size(); ++i) {
+    wrappers->emplace_back(base::MakeUnique<ElementWrapper>(values[i]));
+    deque->push_back(wrappers->back()->ToPointer());
+  }
+}
+
+template <typename Accessor, typename Deque>
+void VerifyDequeInternalState(Deque* deque,
+                              size_t expected_front,
+                              size_t expected_back,
+                              const std::vector<int32_t>& expected_values,
+                              size_t expected_ring_buffer_size) {
+  Accessor accessor(deque);
+
+  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], accessor.buffer()[index]->value);
+    index++;
+    if (index == accessor.buffer().size())
+      index = 0;
+  }
+}
+
+TYPED_TEST(PointerDequeTest, ExpandWhiteBox) {
+  using Deque = typename TypeParam::Deque;
+  using ElementWrapper = typename TypeParam::ElementWrapper;
+  using Accessor = typename TypeParam::Accessor;
+
+  // Test ConstructFullDeque() and VerifyDequeInternalState().
+  {
+    Deque deque;
+    std::vector<std::unique_ptr<ElementWrapper>> wrappers;
+    ConstructFullDeque({1, 2, 3}, 0, &deque, &wrappers);
+    VerifyDequeInternalState<Accessor>(&deque, 0, 2, {1, 2, 3}, 3);
+
+    Deque deque1;
+    std::vector<std::unique_ptr<ElementWrapper>> wrappers1;
+    ConstructFullDeque({1, 2, 3}, 1, &deque1, &wrappers1);
+    VerifyDequeInternalState<Accessor>(&deque1, 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 deque;
+    std::vector<std::unique_ptr<ElementWrapper>> wrappers;
+    ConstructFullDeque({1, 2, 3}, 0, &deque, &wrappers);
+
+    ElementWrapper e(4);
+    deque.push_back(e.ToPointer());
+    VerifyDequeInternalState<Accessor>(&deque, 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 deque;
+    std::vector<std::unique_ptr<ElementWrapper>> wrappers;
+    ConstructFullDeque({1, 2, 3}, 0, &deque, &wrappers);
+
+    ElementWrapper e(4);
+    deque.push_front(e.ToPointer());
+    VerifyDequeInternalState<Accessor>(&deque, 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 deque;
+    std::vector<std::unique_ptr<ElementWrapper>> wrappers;
+    ConstructFullDeque({1, 2, 3}, 1, &deque, &wrappers);
+
+    ElementWrapper e(4);
+    deque.push_back(e.ToPointer());
+    VerifyDequeInternalState<Accessor>(&deque, 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 deque;
+    std::vector<std::unique_ptr<ElementWrapper>> wrappers;
+    ConstructFullDeque({1, 2, 3}, 2, &deque, &wrappers);
+
+    ElementWrapper e(4);
+    deque.push_back(e.ToPointer());
+    VerifyDequeInternalState<Accessor>(&deque, 5, 2, {1, 2, 3, 4}, 6);
+  }
+}
+
+}  // namespace
+}  // namespace test
+}  // namespace mojo