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

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

Issue 2258713004: Make tasks cancellable inside the blink scheduler. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Various comment nits addressed Created 4 years, 4 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/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..87dc0bd6fc8bc16e66696c96947bfcf7f264f783 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;
@@ -75,6 +75,7 @@ void WorkQueueSets::OnPushQueue(WorkQueue* 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 +84,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,

Powered by Google App Engine
This is Rietveld 408576698