Index: mojo/public/cpp/bindings/lib/deque.h |
diff --git a/mojo/public/cpp/bindings/lib/deque.h b/mojo/public/cpp/bindings/lib/deque.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..4db6637841f8fe43abbde61b0573e7d062cd731f |
--- /dev/null |
+++ b/mojo/public/cpp/bindings/lib/deque.h |
@@ -0,0 +1,225 @@ |
+// 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_DEQUE_H_ |
+#define MOJO_PUBLIC_CPP_BINDINGS_LIB_DEQUE_H_ |
+ |
+#include <algorithm> |
+#include <limits> |
+#include <vector> |
+ |
+#include "base/logging.h" |
+#include "base/numerics/safe_math.h" |
+ |
+namespace mojo { |
+namespace test { |
+template <typename T> |
+class DequeAccessor; |
+} |
+ |
+namespace internal { |
+ |
+// This class 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> |
+class deque { |
+ public: |
+ static constexpr size_t kInvalidIndex = std::numeric_limits<size_t>::max(); |
+ static constexpr size_t kDefaultInitialCapacity = 4; |
+ |
+ explicit deque(size_t initial_capacity = kDefaultInitialCapacity) |
+ : buffer_(initial_capacity) {} |
+ |
+ deque(deque&& other) |
+ : front_(other.front_), |
+ back_(other.back_), |
+ buffer_(std::move(other.buffer_)) { |
+ other.front_ = kInvalidIndex; |
+ other.back_ = kInvalidIndex; |
+ } |
+ |
+ deque& operator=(deque&& other) { |
+ front_ = other.front_; |
+ back_ = other.back_; |
+ buffer_ = std::move(other.buffer_); |
+ |
+ other.front_ = kInvalidIndex; |
+ other.back_ = kInvalidIndex; |
+ |
+ return *this; |
+ } |
+ |
+ void push_front(const T& value) { |
+ expand_if_necessary(); |
+ if (empty()) { |
+ front_ = 0; |
+ back_ = 0; |
+ } else { |
+ front_ = get_prev(front_); |
+ } |
+ buffer_[front_] = value; |
+ } |
+ |
+ void push_front(T&& value) { |
+ expand_if_necessary(); |
+ if (empty()) { |
+ front_ = 0; |
+ back_ = 0; |
+ } else { |
+ front_ = get_prev(front_); |
+ } |
+ buffer_[front_] = std::forward<T>(value); |
+ } |
+ |
+ void pop_front() { |
+ DCHECK(!empty()); |
+ |
+ buffer_[front_] = T(); |
+ if (front_ == back_) { |
+ front_ = kInvalidIndex; |
+ back_ = kInvalidIndex; |
+ } else { |
+ front_ = get_next(front_); |
+ } |
+ } |
+ |
+ T& front() { |
+ DCHECK(!empty()); |
+ return buffer_[front_]; |
+ } |
+ |
+ const T& front() const { |
+ DCHECK(!empty()); |
+ return buffer_[front_]; |
+ } |
+ |
+ void push_back(const T& value) { |
+ expand_if_necessary(); |
+ if (empty()) { |
+ front_ = 0; |
+ back_ = 0; |
+ } else { |
+ back_ = get_next(back_); |
+ } |
+ buffer_[back_] = value; |
+ } |
+ |
+ void push_back(T&& value) { |
+ expand_if_necessary(); |
+ if (empty()) { |
+ front_ = 0; |
+ back_ = 0; |
+ } else { |
+ back_ = get_next(back_); |
+ } |
+ buffer_[back_] = std::forward<T>(value); |
+ } |
+ |
+ void pop_back() { |
+ DCHECK(!empty()); |
+ |
+ buffer_[back_] = T(); |
+ if (front_ == back_) { |
+ front_ = kInvalidIndex; |
+ back_ = kInvalidIndex; |
+ } else { |
+ back_ = get_prev(back_); |
+ } |
+ } |
+ |
+ T& back() { |
+ DCHECK(!empty()); |
+ return buffer_[back_]; |
+ } |
+ |
+ const T& back() const { |
+ DCHECK(!empty()); |
+ return buffer_[back_]; |
+ } |
+ |
+ void clear() { |
+ if (empty()) |
+ return; |
+ |
+ if (back_ >= front_) { |
+ for (size_t i = front_; i <= back_; ++i) |
+ buffer_[i] = T(); |
+ } else { |
+ for (size_t i = front_; i < buffer_.size(); ++i) |
+ buffer_[i] = T(); |
+ for (size_t i = 0; i <= back_; ++i) |
+ buffer_[i] = T(); |
+ } |
+ |
+ front_ = kInvalidIndex; |
+ back_ = kInvalidIndex; |
+ } |
+ |
+ bool empty() const { return front_ == kInvalidIndex; } |
+ |
+ private: |
+ friend class ::mojo::test::DequeAccessor<T>; |
+ |
+ 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(); |
+ base::CheckedNumeric<size_t> new_size = original_size; |
+ new_size *= 2; |
+ buffer_.resize(new_size.ValueOrDie()); |
+ |
+ // 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_]. |
+ std::move(buffer_.begin(), buffer_.begin() + back_ + 1, |
+ buffer_.begin() + 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; |
+ std::move(buffer_.begin() + front_, buffer_.begin() + original_size, |
+ buffer_.begin() + new_front); |
+ front_ = new_front; |
+ } |
+ } |
+ } |
+ } |
+ |
+ size_t front_ = kInvalidIndex; |
+ // NOTE: |back_| is inclusive. |
+ size_t back_ = kInvalidIndex; |
+ // TODO(yzshen): This buffer default-constructs T instances for unoccupied |
+ // slots. It would be nice to avoid that. |
+ std::vector<T> buffer_; |
+}; |
+ |
+template <typename T> |
+constexpr size_t deque<T>::kInvalidIndex; |
+ |
+} // namespace internal |
+} // namespace mojo |
+ |
+#endif // MOJO_PUBLIC_CPP_BINDINGS_LIB_DEQUE_H_ |