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&&...);

[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>
   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 331 matching lines @@
 inline T Deque<T, inlineCapacity, Allocator>::takeLast() {
   T oldLast = std::move(last());
   removeLast();
   return oldLast;
 }
 
 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>
 template <typename U>
 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();
+  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],
                            &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