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

third_party/WebKit/Source/wtf/Deque.h

 /*
  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
  * Copyright (C) 2009 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
@@ skipping 116 matching lines @@
 
   template <typename U>
   void append(U&&);
   template <typename U>
   void prepend(U&&);
   void removeFirst();
   void removeLast();
   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&&...);
+
   void clear();
 
   template <typename VisitorDispatcher>
   void trace(VisitorDispatcher);
 
   static_assert(!std::is_polymorphic<T>::value ||
                     !VectorTraits<T>::canInitializeWithMemset,
                 "Cannot initialize with memset if there is a vtable");
   static_assert(Allocator::isGarbageCollected ||
                     !AllowsOnlyPlacementNew<T>::value ||
@@ skipping 350 matching lines @@
 inline void Deque<T, inlineCapacity, Allocator>::prepend(U&& value) {
   expandCapacityIfNeeded();
   if (!m_start)
     m_start = m_buffer.capacity() - 1;
   else
     --m_start;
   new (NotNull, &m_buffer.buffer()[m_start]) T(std::forward<U>(value));
 }
 
 template <typename T, size_t inlineCapacity, typename Allocator>
+template <typename... Args>
+inline void Deque<T, inlineCapacity, Allocator>::emplace_back(Args&&... args) {
+  expandCapacityIfNeeded();
+  new (NotNull, &m_buffer.buffer()[m_end]) T(std::forward<Args>(args)...);
+  if (m_end == m_buffer.capacity() - 1)

[Sami, 2017/01/11 13:49:11]

Looks like this already exists with the current code, but I'm wondering if we
should move this adjustment before the construction? I'm imagining a case where
the constructor also happens to touch this same deque. Maybe that's something
for a different patch.

[alex clarke (OOO till 29th), 2017/01/11 14:04:26]

Done.

+    m_end = 0;
+  else
+    ++m_end;
+}
+
+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)...);
+}
+
+template <typename T, size_t inlineCapacity, typename Allocator>
 inline void Deque<T, inlineCapacity, Allocator>::removeFirst() {
   DCHECK(!isEmpty());
   TypeOperations::destruct(&m_buffer.buffer()[m_start],
                            &m_buffer.buffer()[m_start + 1]);
   m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start],
                             &m_buffer.buffer()[m_start + 1]);
   if (m_start == m_buffer.capacity() - 1)
     m_start = 0;
   else
     ++m_start;
@@ skipping 149 matching lines @@
 inline void swap(Deque<T, inlineCapacity, Allocator>& a,
                  Deque<T, inlineCapacity, Allocator>& b) {
   a.swap(b);
 }
 
 }  // namespace WTF
 
 using WTF::Deque;
 
 #endif  // WTF_Deque_h