Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(805)

Unified Diff: third_party/WebKit/Source/platform/scheduler/base/time_domain.cc

Issue 2396533004: Introduce a FlatMap and FlatSet into WTF (Closed)
Patch Set: Add missing ostream override Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
diff --git a/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc b/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
index e84c5c6f46ebbcf6c254ef35aaabc478ed4c0016..cf58f57815ddef18da54a0fb57fe589dac274eb3 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
+++ b/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
@@ -13,6 +13,13 @@
namespace blink {
namespace scheduler {
+std::ostream& operator<<(
+ std::ostream& os,
+ const std::pair<base::TimeTicks, internal::TaskQueueImpl*>& pair) {
+ os << "[" << pair.first << ", " << pair.second << "]";
+ return os;
+}
+
TimeDomain::TimeDomain(Observer* observer) : observer_(observer) {}
TimeDomain::~TimeDomain() {
@@ -22,6 +29,8 @@ TimeDomain::~TimeDomain() {
void TimeDomain::RegisterQueue(internal::TaskQueueImpl* queue) {
DCHECK(main_thread_checker_.CalledOnValidThread());
DCHECK_EQ(queue->GetTimeDomain(), this);
+
+ queues_.insert(queue);
}
void TimeDomain::UnregisterQueue(internal::TaskQueueImpl* queue) {
@@ -29,17 +38,15 @@ void TimeDomain::UnregisterQueue(internal::TaskQueueImpl* queue) {
DCHECK_EQ(queue->GetTimeDomain(), this);
UnregisterAsUpdatableTaskQueue(queue);
- // If present remove |task_queue| from delayed_wakeup_multimap_.
- // O(log n)
- QueueToDelayedWakeupMultimapIteratorMap::iterator it =
- queue_to_delayed_wakeup_multimap_iterator_map_.find(queue);
-
- if (it == queue_to_delayed_wakeup_multimap_iterator_map_.end())
+ // If no wakeup has been requested then bail out.
+ if (queue->time_domain_wakeup().is_null())
return;
- // O(1) amortized.
- delayed_wakeup_multimap_.erase(it->second);
- queue_to_delayed_wakeup_multimap_iterator_map_.erase(it);
+ // O(log n + n / 2)
+ delayed_wakeup_set_.erase(std::make_pair(queue->time_domain_wakeup(), queue));
+ queue->set_time_domain_wakeup(base::TimeTicks());
+
+ queues_.erase(queue);
}
void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue,
@@ -53,21 +60,17 @@ void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue,
if (UnregisterAsUpdatableTaskQueue(queue))
destination_time_domain->updatable_queue_set_.insert(queue);
- // If present remove |task_queue| from delayed_wakeup_multimap_.
- // O(log n)
- QueueToDelayedWakeupMultimapIteratorMap::iterator it =
- queue_to_delayed_wakeup_multimap_iterator_map_.find(queue);
-
- if (it == queue_to_delayed_wakeup_multimap_iterator_map_.end())
+ // If no wakeup has been requested then bail out.
+ if (queue->time_domain_wakeup().is_null())
return;
- base::TimeTicks destination_now = destination_time_domain->Now();
- destination_time_domain->ScheduleDelayedWork(queue, it->second->first,
- destination_now);
+ // O(log n + n / 2)
+ delayed_wakeup_set_.erase(std::make_pair(queue->time_domain_wakeup(), queue));
+ queue->set_time_domain_wakeup(base::TimeTicks());
- // O(1) amortized.
- delayed_wakeup_multimap_.erase(it->second);
- queue_to_delayed_wakeup_multimap_iterator_map_.erase(it);
+ base::TimeTicks destination_now = destination_time_domain->Now();
+ destination_time_domain->ScheduleDelayedWork(
+ queue, queue->time_domain_wakeup(), destination_now);
}
void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue,
@@ -76,27 +79,20 @@ void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue,
DCHECK(main_thread_checker_.CalledOnValidThread());
// We only want to store a single wakeup per queue, so we need to remove any
// previously registered wake up for |queue|.
- QueueToDelayedWakeupMultimapIteratorMap::iterator it =
- queue_to_delayed_wakeup_multimap_iterator_map_.find(queue);
-
- if (it != queue_to_delayed_wakeup_multimap_iterator_map_.end())
- delayed_wakeup_multimap_.erase(it->second);
+ if (!queue->time_domain_wakeup().is_null()) {
+ delayed_wakeup_set_.erase(
+ std::make_pair(queue->time_domain_wakeup(), queue));
+ queue->set_time_domain_wakeup(base::TimeTicks());
+ }
- if (delayed_wakeup_multimap_.empty() ||
- delayed_run_time < delayed_wakeup_multimap_.begin()->first) {
+ if (delayed_wakeup_set_.empty() ||
+ delayed_run_time < delayed_wakeup_set_.begin()->first) {
base::TimeDelta delay = std::max(base::TimeDelta(), delayed_run_time - now);
RequestWakeup(now, delay);
}
- if (it != queue_to_delayed_wakeup_multimap_iterator_map_.end()) {
- // TODO(alexclarke): Use C++17 extract & insert to more efficiently modify
- // |queue_to_delayed_wakeup_multimap_iterator_map_|.
- it->second = delayed_wakeup_multimap_.insert({delayed_run_time, queue});
- } else {
- // Insert the wakeup and store the map iterator for later convenience.
- queue_to_delayed_wakeup_multimap_iterator_map_.insert(
- {queue, delayed_wakeup_multimap_.insert({delayed_run_time, queue})});
- }
+ delayed_wakeup_set_.insert(std::make_pair(delayed_run_time, queue));
+ queue->set_time_domain_wakeup(delayed_run_time);
if (observer_)
observer_->OnTimeDomainHasDelayedWork(queue);
@@ -167,38 +163,31 @@ void TimeDomain::WakeupReadyDelayedQueues(LazyNow* lazy_now) {
// Wake up any queues with pending delayed work. Note std::multipmap stores
// the elements sorted by key, so the begin() iterator points to the earliest
// queue to wakeup.
- while (!delayed_wakeup_multimap_.empty()) {
- DelayedWakeupMultimap::iterator next_wakeup =
- delayed_wakeup_multimap_.begin();
- if (next_wakeup->first > lazy_now->Now())
- break;
-
- internal::TaskQueueImpl* queue = next_wakeup->second;
-
- // O(1) amortized.
- delayed_wakeup_multimap_.erase(next_wakeup);
- // O(log n).
- queue_to_delayed_wakeup_multimap_iterator_map_.erase(queue);
+ while (!delayed_wakeup_set_.empty() &&
+ delayed_wakeup_set_.begin()->first <= lazy_now->Now()) {
+ internal::TaskQueueImpl* queue = delayed_wakeup_set_.begin()->second;
+ delayed_wakeup_set_.erase(delayed_wakeup_set_.begin());
+ queue->set_time_domain_wakeup(base::TimeTicks());
queue->WakeUpForDelayedWork(lazy_now);
}
}
bool TimeDomain::NextScheduledRunTime(base::TimeTicks* out_time) const {
DCHECK(main_thread_checker_.CalledOnValidThread());
- if (delayed_wakeup_multimap_.empty())
+ if (delayed_wakeup_set_.empty())
return false;
- *out_time = delayed_wakeup_multimap_.begin()->first;
+ *out_time = delayed_wakeup_set_.begin()->first;
return true;
}
bool TimeDomain::NextScheduledTaskQueue(TaskQueue** out_task_queue) const {
DCHECK(main_thread_checker_.CalledOnValidThread());
- if (delayed_wakeup_multimap_.empty())
+ if (delayed_wakeup_set_.empty())
return false;
- *out_task_queue = delayed_wakeup_multimap_.begin()->second;
+ *out_task_queue = delayed_wakeup_set_.begin()->second;
return true;
}
@@ -209,9 +198,9 @@ void TimeDomain::AsValueInto(base::trace_event::TracedValue* state) const {
for (auto* queue : updatable_queue_set_)
state->AppendString(queue->GetName());
state->EndArray();
- state->SetInteger("registered_delay_count", delayed_wakeup_multimap_.size());
- if (!delayed_wakeup_multimap_.empty()) {
- base::TimeDelta delay = delayed_wakeup_multimap_.begin()->first - Now();
+ state->SetInteger("registered_delay_count", delayed_wakeup_set_.size());
+ if (!delayed_wakeup_set_.empty()) {
+ base::TimeDelta delay = delayed_wakeup_set_.begin()->first - Now();
state->SetDouble("next_delay_ms", delay.InMillisecondsF());
}
AsValueIntoInternal(state);

Powered by Google App Engine
This is Rietveld 408576698