Use WTF::Deque instead of std::queue in the blink scheduler

third_party/WebKit/Source/wtf/Deque.h

Index: third_party/WebKit/Source/wtf/Deque.h
diff --git a/third_party/WebKit/Source/wtf/Deque.h b/third_party/WebKit/Source/wtf/Deque.h
index f244bb52846c86533603a7947db9d2ac2b2e15b3..b6b69b2d351103c04a06b3d671cdaeb44dce5699 100644
--- a/third_party/WebKit/Source/wtf/Deque.h
+++ b/third_party/WebKit/Source/wtf/Deque.h
@@ -134,6 +134,27 @@ class Deque : public ConditionalDestructor<Deque<T, INLINE_CAPACITY, Allocator>,
   void remove(iterator&);
   void remove(const_iterator&);
 
+  // STL compatibility.
+  template <typename U>
+  void push_back(U&& u) {
+    append(std::forward<U>(u));
+  }
+  template <typename U>
+  void push_front(U&& u) {
+    prepend(std::forward<U>(u));
+  }
+  void pop_back() { removeLast(); }
+  void pop_front() { removeFirst(); }
+  bool empty() const { return isEmpty(); }
+  T& front() { return first(); }
+  const T& front() const { return first(); }
+  T& back() { return last(); }
+  const T& back() const { return last(); }
+  template <typename... Args>
+  void emplace_back(Args&&...);
+  template <typename... Args>
+  void emplace_front(Args&&...);

[haraken, 2017/01/11 15:20:35]

pilgrim@: Does this align with your renaming plan?

[alex clarke (OOO till 29th), 2017/01/11 15:29:53]

It might make sense to (in a follow up patch) rename the blink uses to conform
to STL style.

Also I only checked the things I used, possible I missed some.

+
   void clear();
 
   template <typename VisitorDispatcher>
@@ -485,11 +506,12 @@ template <typename T, size_t inlineCapacity, typename Allocator>
 template <typename U>
 inline void Deque<T, inlineCapacity, Allocator>::append(U&& value) {
   expandCapacityIfNeeded();
-  new (NotNull, &m_buffer.buffer()[m_end]) T(std::forward<U>(value));
+  T* newElement = &m_buffer.buffer()[m_end];
   if (m_end == m_buffer.capacity() - 1)
     m_end = 0;
   else
     ++m_end;
+  new (NotNull, newElement) T(std::forward<U>(value));
 }
 
 template <typename T, size_t inlineCapacity, typename Allocator>
@@ -504,6 +526,29 @@ inline void Deque<T, inlineCapacity, Allocator>::prepend(U&& value) {
 }
 
 template <typename T, size_t inlineCapacity, typename Allocator>
+template <typename... Args>
+inline void Deque<T, inlineCapacity, Allocator>::emplace_back(Args&&... args) {
+  expandCapacityIfNeeded();
+  T* newElement = &m_buffer.buffer()[m_end];
+  if (m_end == m_buffer.capacity() - 1)
+    m_end = 0;
+  else
+    ++m_end;
+  new (NotNull, newElement) T(std::forward<Args>(args)...);
+}
+
+template <typename T, size_t inlineCapacity, typename Allocator>
+template <typename... Args>
+inline void Deque<T, inlineCapacity, Allocator>::emplace_front(Args&&... args) {
+  expandCapacityIfNeeded();
+  if (!m_start)
+    m_start = m_buffer.capacity() - 1;
+  else
+    --m_start;
+  new (NotNull, &m_buffer.buffer()[m_start]) T(std::forward<Args>(args)...);
+}

[haraken, 2017/01/11 15:20:35]

Can we share these implementations with append/prepend?

[alex clarke (OOO till 29th), 2017/01/11 15:29:53]

Do you mean add emplace_append and emplace_prepend?  I can certainly add those
if that's what you mean :)

[haraken, 2017/01/11 15:45:19]

Ah, sorry. Ignore my comment :)

+
+template <typename T, size_t inlineCapacity, typename Allocator>
 inline void Deque<T, inlineCapacity, Allocator>::removeFirst() {
   DCHECK(!isEmpty());
   TypeOperations::destruct(&m_buffer.buffer()[m_start],