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

mojo/public/cpp/bindings/lib/pointer_deque.h

+// 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.
+
+#ifndef MOJO_PUBLIC_CPP_BINDINGS_LIB_POINTER_DEQUE_H_
+#define MOJO_PUBLIC_CPP_BINDINGS_LIB_POINTER_DEQUE_H_
+
+#include <algorithm>
+#include <limits>
+#include <memory>
+#include <type_traits>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/macros.h"
+
+namespace mojo {
+namespace internal {
+
+template <typename T, bool owned>
+class PointerDequeAccessor;
+
+template <typename T, bool owned>
+struct PointerDequeTraits;
+
+template <typename T>
+struct PointerDequeTraits<T, true> {
+  using ElementType = std::unique_ptr<T>;
+
+  static void destroy(std::vector<ElementType>* buffer, size_t index) {
+    (*buffer)[index].reset();
+  }
+
+  static void move(std::vector<ElementType>* buffer,
+                   size_t first,
+                   size_t inclusive_last,
+                   size_t dest_first) {
+    auto iter_base = buffer->begin();
+    std::move(iter_base + first, iter_base + inclusive_last + 1,
+              iter_base + dest_first);
+  }
+};
+
+template <typename T>
+struct PointerDequeTraits<T, false> {
+  using ElementType = T*;
+
+  static void destroy(std::vector<ElementType>* buffer, size_t index) {
+    // Do nothing.
+  }
+
+  static void move(std::vector<ElementType>* buffer,
+                   size_t first,
+                   size_t inclusive_last,
+                   size_t dest_first) {
+    ElementType* iter_base = &(*buffer)[0];
+    memcpy(iter_base + dest_first, iter_base + first,
+           (inclusive_last - first + 1) * sizeof(ElementType));
+  }
+};
+
+// PointerDeque is a deque for pointers (either raw pointers or
+// std::unique_ptr's). It uses a std::vector as ring buffer, which is
+// expanded when necessary.
+//
+// The reason to introduce this class is that std::deque is memory inefficient.
+// (Please see crbug.com/674287 for more details.)
+template <typename T, bool owned>
+class PointerDeque {
+ public:
+  using Traits = PointerDequeTraits<T, owned>;
+  using ElementType = typename Traits::ElementType;
+
+  static constexpr size_t kInvalidIndex = std::numeric_limits<size_t>::max();
+  static constexpr size_t kDefaultInitialCapacity = 4;
+
+  explicit PointerDeque(size_t initial_capacity = kDefaultInitialCapacity)
+      : buffer_(initial_capacity) {}
+
+  PointerDeque(PointerDeque&& other) {
+    std::swap(front_, other.front_);
+    std::swap(back_, other.back_);
+    std::swap(buffer_, other.buffer_);
+  }
+
+  PointerDeque& operator=(PointerDeque&& other) {
+    if (this != &other) {

[Ken Rockot(use gerrit already), 2017/05/22 16:45:28]

I think we discourage self-assignment checks in move assignment operators:
https://groups.google.com/a/chromium.org/forum/#!topic/chromium-dev/ZzfGfgruHxc

DCHECK is sufficient if you like

[yzshen1, 2017/05/25 00:06:43]

Done.

(It seems the discussion also came to the conclusion that we shouldn't DCHECK.)

+      clear();
+      std::swap(front_, other.front_);
+      std::swap(back_, other.back_);
+      std::swap(buffer_, other.buffer_);
+    }
+    return *this;
+  }
+
+  void push_front(ElementType value) {
+    expand_if_necessary();
+    if (empty()) {
+      front_ = 0;
+      back_ = 0;
+    } else {
+      front_ = get_prev(front_);
+    }
+    buffer_[front_] = std::move(value);
+  }
+
+  void pop_front() {
+    DCHECK(!empty());
+
+    Traits::destroy(&buffer_, front_);
+    if (front_ == back_) {
+      front_ = kInvalidIndex;
+      back_ = kInvalidIndex;
+    } else {
+      front_ = get_next(front_);
+    }
+  }
+
+  ElementType& front() {
+    DCHECK(!empty());
+    return buffer_[front_];
+  }
+
+  const ElementType& front() const {
+    DCHECK(!empty());
+    return buffer_[front_];
+  }
+
+  void push_back(ElementType value) {
+    expand_if_necessary();
+    if (empty()) {
+      front_ = 0;
+      back_ = 0;
+    } else {
+      back_ = get_next(back_);
+    }
+    buffer_[back_] = std::move(value);
+  }
+
+  void pop_back() {
+    DCHECK(!empty());
+
+    Traits::destroy(&buffer_, back_);
+    if (front_ == back_) {
+      front_ = kInvalidIndex;
+      back_ = kInvalidIndex;
+    } else {
+      back_ = get_prev(back_);
+    }
+  }
+
+  ElementType& back() {
+    DCHECK(!empty());
+    return buffer_[back_];
+  }
+
+  const ElementType& back() const {
+    DCHECK(!empty());
+    return buffer_[back_];
+  }
+
+  void clear() {
+    if (empty())
+      return;
+
+    if (back_ >= front_) {
+      for (size_t i = front_; i <= back_; ++i)
+        Traits::destroy(&buffer_, i);
+    } else {
+      for (size_t i = front_; i < buffer_.size(); ++i)
+        Traits::destroy(&buffer_, i);
+      for (size_t i = 0; i <= back_; ++i)
+        Traits::destroy(&buffer_, i);
+    }
+
+    front_ = kInvalidIndex;
+    back_ = kInvalidIndex;
+  }
+
+  bool empty() const { return front_ == kInvalidIndex; }
+
+ private:
+  friend class PointerDequeAccessor<T, owned>;
+
+  size_t get_next(size_t index) {
+    DCHECK(!buffer_.empty());
+    return index != buffer_.size() - 1 ? index + 1 : 0;
+  }
+
+  size_t get_prev(size_t index) {
+    DCHECK(!buffer_.empty());
+    return index != 0 ? index - 1 : buffer_.size() - 1;
+  }
+
+  void expand_if_necessary() {
+    if (buffer_.empty()) {
+      DCHECK_EQ(kInvalidIndex, front_);
+      DCHECK_EQ(kInvalidIndex, back_);
+
+      buffer_.resize(kDefaultInitialCapacity);
+    } else {
+      // Whether the buffer still has available slots.
+      if (empty() || get_prev(front_) != back_)
+        return;
+
+      size_t original_size = buffer_.size();

[Ken Rockot(use gerrit already), 2017/05/22 16:45:28]

nit: Good use for CheckedNumeric in base/numerics/safe_math.h. e.g:

base::CheckedNumeric<size_t> new_size = original_size;
new_size *= 2;
buffer_.resize(new_size.ValueOrDie());

[yzshen1, 2017/05/25 00:06:44]

Done.

+      CHECK_LE(original_size, std::numeric_limits<size_t>::max() / 2);
+      buffer_.resize(original_size * 2);
+
+      // Whether we need to move part of the elements to remain a ring buffer.
+      if (front_ != 0) {
+        if (back_ < original_size / 2) {
+          // Move [0, back_] to [original_size, original_size + back_].
+          Traits::move(&buffer_, 0, back_, original_size);
+          back_ += original_size;
+        } else {
+          // Move [front_, original_size - 1] to
+          // [front_ + buffer_.size() - original_size, buffer_.size() - 1].
+          size_t new_front = front_ + buffer_.size() - original_size;
+          Traits::move(&buffer_, front_, original_size - 1, new_front);
+          front_ = new_front;
+        }
+      }
+    }
+  }
+
+  size_t front_ = kInvalidIndex;
+  // NOTE: |back_| is inclusive.
+  size_t back_ = kInvalidIndex;
+  std::vector<ElementType> buffer_;
+
+  DISALLOW_COPY_AND_ASSIGN(PointerDeque);
+};
+
+template <typename T, bool owned>
+constexpr size_t PointerDeque<T, owned>::kInvalidIndex;
+
+}  // namespace internal
+}  // namespace mojo
+
+#endif  // MOJO_PUBLIC_CPP_BINDINGS_LIB_POINTER_DEQUE_H_