[Reland] Optimize blink scheduler with an intrusive heap

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

Index: third_party/WebKit/Source/platform/scheduler/base/time_domain.h
diff --git a/third_party/WebKit/Source/platform/scheduler/base/time_domain.h b/third_party/WebKit/Source/platform/scheduler/base/time_domain.h
index 52c7678eea23ac5de1257546e25a5172f24ea4fa..666ea12399dcf003f0391889ff67c8ec9e9b8671 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/time_domain.h
+++ b/third_party/WebKit/Source/platform/scheduler/base/time_domain.h
@@ -13,6 +13,7 @@
 #include "base/memory/ref_counted.h"
 #include "base/memory/weak_ptr.h"
 #include "base/time/time.h"
+#include "platform/scheduler/base/intrusive_heap.h"
 #include "platform/scheduler/base/lazy_now.h"
 #include "platform/scheduler/base/task_queue_impl.h"
 
@@ -131,23 +132,38 @@ class BLINK_PLATFORM_EXPORT TimeDomain {
   // has elapsed.
   void WakeupReadyDelayedQueues(LazyNow* lazy_now);
 
+  size_t NumberOfScheduledWakeups() const {
+    return delayed_wakeup_queue_.size();
+  }
+
  private:
   void MoveNewlyUpdatableQueuesIntoUpdatableQueueSet();
 
-  using DelayedWakeupMultimap =
-      std::multimap<base::TimeTicks, internal::TaskQueueImpl*>;
+  struct DelayedWakeup {
+    base::TimeTicks time;
+    internal::TaskQueueImpl* queue;
+
+    bool operator<=(const DelayedWakeup& other) const {
+      if (time == other.time)
+        return queue <= other.queue;
+      return time < other.time;
+    }
 
-  DelayedWakeupMultimap delayed_wakeup_multimap_;
+    void SetHeapHandle(HeapHandle handle) {
+      DCHECK(handle.IsValid());
+      queue->set_heap_handle(handle);
+    }
 
-  // This map makes it easy to remove a queue from |delayed_wakeup_multimap_|.
-  // NOTE inserting or removing elements from a std::map does not invalidate any
-  // iterators.
-  using QueueToDelayedWakeupMultimapIteratorMap =
-      std::unordered_map<internal::TaskQueueImpl*,
-                         DelayedWakeupMultimap::iterator>;
+    void ClearHeapHandle() {
+      DCHECK(queue->heap_handle().IsValid());
+      queue->set_heap_handle(HeapHandle());
+
+      DCHECK_NE(queue->scheduled_time_domain_wakeup(), base::TimeTicks());
+      queue->set_scheduled_time_domain_wakeup(base::TimeTicks());
+    }
+  };
 
-  QueueToDelayedWakeupMultimapIteratorMap
-      queue_to_delayed_wakeup_multimap_iterator_map_;
+  IntrusiveHeap<DelayedWakeup> delayed_wakeup_queue_;
 
   // This lock guards only |newly_updatable_|.  It's not expected to be heavily
   // contended.