Make tasks cancellable inside the blink scheduler.

third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc

Index: third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
diff --git a/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc b/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
index 47ffb0e8877e176d302872447602ef40de86b246..9cb959765d20880af61f2d41352bcafc3b0ada0c 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
+++ b/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
@@ -61,7 +61,7 @@ void WorkQueueSets::ChangeSetIndex(WorkQueue* work_queue, size_t set_index) {
 }
 
 void WorkQueueSets::OnPushQueue(WorkQueue* work_queue) {
-  // NOTE if this funciton changes, we need to keep |WorkQueueSets::AddQueue| in
+  // NOTE if this function changes, we need to keep |WorkQueueSets::AddQueue| in
   // sync.
   DCHECK_EQ(this, work_queue->work_queue_sets());
   EnqueueOrder enqueue_order;
@@ -70,11 +70,15 @@ void WorkQueueSets::OnPushQueue(WorkQueue* work_queue) {
   size_t set_index = work_queue->work_queue_set_index();
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size())
       << " set_index = " << set_index;
+  // It's very likely the front task of |work_queue| is newer than anything else
+  // in the set. 
   enqueue_order_to_work_queue_maps_[set_index].insert(
+      enqueue_order_to_work_queue_maps_[set_index].rbegin().base(),
       std::make_pair(enqueue_order, work_queue));
 }
 
 void WorkQueueSets::OnPopQueue(WorkQueue* work_queue) {
+  // Assume that |work_queue| contains the lowest enqueue_order.
   size_t set_index = work_queue->work_queue_set_index();
   DCHECK_EQ(this, work_queue->work_queue_sets());
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
@@ -83,15 +87,41 @@ void WorkQueueSets::OnPopQueue(WorkQueue* work_queue) {
   DCHECK_EQ(enqueue_order_to_work_queue_maps_[set_index].begin()->second,
             work_queue)
       << " set_index = " << set_index;
-  // O(1) amortised.
-  enqueue_order_to_work_queue_maps_[set_index].erase(
-      enqueue_order_to_work_queue_maps_[set_index].begin());
+  EnqueueOrderToWorkQueueMap::iterator old_it =
+      enqueue_order_to_work_queue_maps_[set_index].begin();
   EnqueueOrder enqueue_order;
-  bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
-  if (!has_enqueue_order)
-    return;
-  enqueue_order_to_work_queue_maps_[set_index].insert(
-      std::make_pair(enqueue_order, work_queue));
+  if (work_queue->GetFrontTaskEnqueueOrder(&enqueue_order)) {
+    // Amortized O(1) if the new location is close to |old_it|, otherwise
+    // O(log n).
+    enqueue_order_to_work_queue_maps_[set_index].insert(
+        std::make_pair(enqueue_order, work_queue));
+  }
+  // O(1)
+  enqueue_order_to_work_queue_maps_[set_index].erase(old_it);
+}
+
+void WorkQueueSets::OnQueueHeadChanged(WorkQueue* work_queue,
+                                       EnqueueOrder erased_task_enqueue_order) {
+  size_t set_index = work_queue->work_queue_set_index();
+  DCHECK_EQ(this, work_queue->work_queue_sets());
+  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
+  DCHECK(!enqueue_order_to_work_queue_maps_[set_index].empty())
+      << " set_index = " << set_index;
+  // O(log n).
+  EnqueueOrderToWorkQueueMap::iterator old_it =
+      enqueue_order_to_work_queue_maps_[set_index].find(
+          erased_task_enqueue_order);
+  DCHECK(old_it != enqueue_order_to_work_queue_maps_[set_index].end());
+
+  EnqueueOrder enqueue_order;
+  if (work_queue->GetFrontTaskEnqueueOrder(&enqueue_order)) {
+    // Amortized O(1) if the new location is close to |old_it|, otherwise
+    // O(log n).
+    enqueue_order_to_work_queue_maps_[set_index].insert(
+        old_it, std::make_pair(enqueue_order, work_queue));
+  }
+  // O(1)
+  enqueue_order_to_work_queue_maps_[set_index].erase(old_it);
 }
 
 bool WorkQueueSets::GetOldestQueueInSet(size_t set_index,