[Reland] Make canceling Timers fast.

third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h

Index: third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
diff --git a/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h b/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
index 71f4103a4b82445237f6de8c6352580d25c34611..c6f2b29f5918544ddec4b74bf3a8032cbea5dd09 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
+++ b/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
@@ -78,10 +78,6 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
          bool nestable,
          EnqueueOrder enqueue_order);
 
-    // Create a fake Task based on the handle, suitable for using as a search
-    // key.
-    static Task CreateFakeTaskFromHandle(const TaskHandle& handle);
-
     EnqueueOrder enqueue_order() const {
 #ifndef NDEBUG
       DCHECK(enqueue_order_set_);
@@ -101,24 +97,6 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
     bool enqueue_order_set() const { return enqueue_order_set_; }
 #endif
 
-    using ComparatorFn = bool (*)(const Task&, const Task&);
-
-    // Tasks are ordered by |delayed_run_time| smallest first then and by
-    // |sequence_num| in case of a tie.
-    class DelayedRunTimeComparator {
-     public:
-      bool operator()(const Task& a, const Task& b) const;
-    };
-
-    // Tasks are ordered by |enqueue_order_| smallest first.
-    static bool EnqueueOrderComparatorFn(const TaskQueueImpl::Task& a,
-                                         const TaskQueueImpl::Task& b);
-
-    // Tasks are ordered by |delayed_run_time| smallest first then and by
-    // |sequence_num| in case of a tie.
-    static bool DelayedRunTimeComparatorFn(const TaskQueueImpl::Task& a,
-                                           const TaskQueueImpl::Task& b);
-
    private:
 #ifndef NDEBUG
     bool enqueue_order_set_;
@@ -140,11 +118,6 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
   bool PostNonNestableDelayedTask(const tracked_objects::Location& from_here,
                                   const base::Closure& task,
                                   base::TimeDelta delay) override;
-  TaskHandle PostCancellableDelayedTask(
-      const tracked_objects::Location& from_here,
-      const base::Closure& task,
-      base::TimeDelta delay) override;
-  bool CancelTask(const TaskHandle& handle) override;
   void SetQueueEnabled(bool enabled) override;
   bool IsQueueEnabled() const override;
   bool IsEmpty() const override;
@@ -161,10 +134,9 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
   void RemoveFence() override;
   bool BlockedByFence() const override;
 
-  bool IsTaskPending(const TaskHandle& handle) const;
-
-  void UpdateImmediateWorkQueue();
-  void UpdateDelayedWorkQueue(LazyNow* lazy_now);
+  // If this returns false then future updates for this queue are not needed
+  // unless requested.
+  bool MaybeUpdateImmediateWorkQueues();
 
   const char* GetName() const override;
 
@@ -199,17 +171,14 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
     return should_report_when_execution_blocked_;
   }
 
+  // Enqueues any delayed tasks which should be run now on the
+  // |delayed_work_queue|.  Must be called from the main thread.
+  void MoveReadyDelayedTasksToDelayedWorkQueue(LazyNow* lazy_now);
+
  private:
   friend class WorkQueue;
   friend class WorkQueueTest;
 
-  // Note both DelayedRunTimeQueue and ComparatorQueue are sets for fast task
-  // cancellation. Typically queue sizes are well under 200 so the overhead of
-  // std::set vs std::priority_queue and std::queue is lost in the noise of
-  // everything else.
-  using DelayedRunTimeQueue = std::set<Task, Task::DelayedRunTimeComparator>;
-  using ComparatorQueue = std::set<Task, Task::ComparatorFn>;
-
   enum class TaskType {
     NORMAL,
     NON_NESTABLE,
@@ -226,7 +195,7 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
     TaskQueueManager* task_queue_manager;
     TimeDomain* time_domain;
 
-    ComparatorQueue immediate_incoming_queue;
+    std::queue<Task> immediate_incoming_queue;
   };
 
   struct MainThreadOnly {
@@ -242,7 +211,7 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
 
     std::unique_ptr<WorkQueue> delayed_work_queue;
     std::unique_ptr<WorkQueue> immediate_work_queue;
-    DelayedRunTimeQueue delayed_incoming_queue;
+    std::priority_queue<Task> delayed_incoming_queue;
     base::ObserverList<base::MessageLoop::TaskObserver> task_observers;
     size_t set_index;
     bool is_enabled;
@@ -271,24 +240,25 @@ class BLINK_PLATFORM_EXPORT TaskQueueImpl final : public TaskQueue {
 
   void ScheduleDelayedWorkTask(Task pending_task);
 
-  // Enqueues any delayed tasks which should be run now on the
-  // |delayed_work_queue|.  Must be called from the main thread.
-  void MoveReadyDelayedTasksToDelayedWorkQueue(LazyNow* lazy_now);
-
   void MoveReadyImmediateTasksToImmediateWorkQueueLocked();
 
   // Push the task onto the |immediate_incoming_queue| and for auto pumped
   // queues it calls MaybePostDoWorkOnMainRunner if the Incoming queue was
   // empty.
-  void PushOntoImmediateIncomingQueueLocked(Task pending_task);
+  void PushOntoImmediateIncomingQueueLocked(
+         const tracked_objects::Location& posted_from,
+         const base::Closure& task,
+         base::TimeTicks desired_run_time,
+         EnqueueOrder sequence_number,
+         bool nestable);
 
   // As BlockedByFence but safe to be called while locked.
   bool BlockedByFenceLocked() const;
 
   void TraceQueueSize(bool is_locked) const;
-  static void QueueAsValueInto(const ComparatorQueue& queue,
+  static void QueueAsValueInto(const std::queue<Task>& queue,
                                base::trace_event::TracedValue* state);
-  static void QueueAsValueInto(const DelayedRunTimeQueue& queue,
+  static void QueueAsValueInto(const std::priority_queue<Task>& queue,
                                base::trace_event::TracedValue* state);
   static void TaskAsValueInto(const Task& task,
                               base::trace_event::TracedValue* state);