1 // Copyright 2015 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/task/sequence_manager/work_queue_sets.h"
6
7 #include "base/logging.h"
8
9 namespace base {
10 namespace sequence_manager {
11 namespace internal {
12
WorkQueueSets(size_t num_sets,const char * name)13 WorkQueueSets::WorkQueueSets(size_t num_sets, const char* name)
14 : work_queue_heaps_(num_sets), name_(name) {}
15
16 WorkQueueSets::~WorkQueueSets() = default;
17
AddQueue(WorkQueue * work_queue,size_t set_index)18 void WorkQueueSets::AddQueue(WorkQueue* work_queue, size_t set_index) {
19 DCHECK(!work_queue->work_queue_sets());
20 DCHECK_LT(set_index, work_queue_heaps_.size());
21 EnqueueOrder enqueue_order;
22 bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
23 work_queue->AssignToWorkQueueSets(this);
24 work_queue->AssignSetIndex(set_index);
25 if (!has_enqueue_order)
26 return;
27 work_queue_heaps_[set_index].insert({enqueue_order, work_queue});
28 }
29
RemoveQueue(WorkQueue * work_queue)30 void WorkQueueSets::RemoveQueue(WorkQueue* work_queue) {
31 DCHECK_EQ(this, work_queue->work_queue_sets());
32 work_queue->AssignToWorkQueueSets(nullptr);
33 HeapHandle heap_handle = work_queue->heap_handle();
34 if (!heap_handle.IsValid())
35 return;
36 size_t set_index = work_queue->work_queue_set_index();
37 DCHECK_LT(set_index, work_queue_heaps_.size());
38 work_queue_heaps_[set_index].erase(heap_handle);
39 }
40
ChangeSetIndex(WorkQueue * work_queue,size_t set_index)41 void WorkQueueSets::ChangeSetIndex(WorkQueue* work_queue, size_t set_index) {
42 DCHECK_EQ(this, work_queue->work_queue_sets());
43 DCHECK_LT(set_index, work_queue_heaps_.size());
44 EnqueueOrder enqueue_order;
45 bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
46 size_t old_set = work_queue->work_queue_set_index();
47 DCHECK_LT(old_set, work_queue_heaps_.size());
48 DCHECK_NE(old_set, set_index);
49 work_queue->AssignSetIndex(set_index);
50 if (!has_enqueue_order)
51 return;
52 work_queue_heaps_[old_set].erase(work_queue->heap_handle());
53 work_queue_heaps_[set_index].insert({enqueue_order, work_queue});
54 }
55
OnFrontTaskChanged(WorkQueue * work_queue)56 void WorkQueueSets::OnFrontTaskChanged(WorkQueue* work_queue) {
57 EnqueueOrder enqueue_order;
58 bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
59 DCHECK(has_enqueue_order);
60 size_t set = work_queue->work_queue_set_index();
61 work_queue_heaps_[set].ChangeKey(work_queue->heap_handle(),
62 {enqueue_order, work_queue});
63 }
64
OnTaskPushedToEmptyQueue(WorkQueue * work_queue)65 void WorkQueueSets::OnTaskPushedToEmptyQueue(WorkQueue* work_queue) {
66 // NOTE if this function changes, we need to keep |WorkQueueSets::AddQueue| in
67 // sync.
68 DCHECK_EQ(this, work_queue->work_queue_sets());
69 EnqueueOrder enqueue_order;
70 bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
71 DCHECK(has_enqueue_order);
72 size_t set_index = work_queue->work_queue_set_index();
73 DCHECK_LT(set_index, work_queue_heaps_.size())
74 << " set_index = " << set_index;
75 // |work_queue| should not be in work_queue_heaps_[set_index].
76 DCHECK(!work_queue->heap_handle().IsValid());
77 work_queue_heaps_[set_index].insert({enqueue_order, work_queue});
78 }
79
OnPopQueue(WorkQueue * work_queue)80 void WorkQueueSets::OnPopQueue(WorkQueue* work_queue) {
81 // Assume that |work_queue| contains the lowest enqueue_order.
82 size_t set_index = work_queue->work_queue_set_index();
83 DCHECK_EQ(this, work_queue->work_queue_sets());
84 DCHECK_LT(set_index, work_queue_heaps_.size());
85 DCHECK(!work_queue_heaps_[set_index].empty()) << " set_index = " << set_index;
86 DCHECK_EQ(work_queue_heaps_[set_index].Min().value, work_queue)
87 << " set_index = " << set_index;
88 DCHECK(work_queue->heap_handle().IsValid());
89 EnqueueOrder enqueue_order;
90 if (work_queue->GetFrontTaskEnqueueOrder(&enqueue_order)) {
91 // O(log n)
92 work_queue_heaps_[set_index].ReplaceMin({enqueue_order, work_queue});
93 } else {
94 // O(log n)
95 work_queue_heaps_[set_index].Pop();
96 DCHECK(work_queue_heaps_[set_index].empty() ||
97 work_queue_heaps_[set_index].Min().value != work_queue);
98 }
99 }
100
OnQueueBlocked(WorkQueue * work_queue)101 void WorkQueueSets::OnQueueBlocked(WorkQueue* work_queue) {
102 DCHECK_EQ(this, work_queue->work_queue_sets());
103 HeapHandle heap_handle = work_queue->heap_handle();
104 if (!heap_handle.IsValid())
105 return;
106 size_t set_index = work_queue->work_queue_set_index();
107 DCHECK_LT(set_index, work_queue_heaps_.size());
108 work_queue_heaps_[set_index].erase(heap_handle);
109 }
110
GetOldestQueueInSet(size_t set_index,WorkQueue ** out_work_queue) const111 bool WorkQueueSets::GetOldestQueueInSet(size_t set_index,
112 WorkQueue** out_work_queue) const {
113 DCHECK_LT(set_index, work_queue_heaps_.size());
114 if (work_queue_heaps_[set_index].empty())
115 return false;
116 *out_work_queue = work_queue_heaps_[set_index].Min().value;
117 DCHECK_EQ(set_index, (*out_work_queue)->work_queue_set_index());
118 DCHECK((*out_work_queue)->heap_handle().IsValid());
119 return true;
120 }
121
GetOldestQueueAndEnqueueOrderInSet(size_t set_index,WorkQueue ** out_work_queue,EnqueueOrder * out_enqueue_order) const122 bool WorkQueueSets::GetOldestQueueAndEnqueueOrderInSet(
123 size_t set_index,
124 WorkQueue** out_work_queue,
125 EnqueueOrder* out_enqueue_order) const {
126 DCHECK_LT(set_index, work_queue_heaps_.size());
127 if (work_queue_heaps_[set_index].empty())
128 return false;
129 const OldestTaskEnqueueOrder& oldest = work_queue_heaps_[set_index].Min();
130 *out_work_queue = oldest.value;
131 *out_enqueue_order = oldest.key;
132 EnqueueOrder enqueue_order;
133 DCHECK(oldest.value->GetFrontTaskEnqueueOrder(&enqueue_order) &&
134 oldest.key == enqueue_order);
135 return true;
136 }
137
IsSetEmpty(size_t set_index) const138 bool WorkQueueSets::IsSetEmpty(size_t set_index) const {
139 DCHECK_LT(set_index, work_queue_heaps_.size())
140 << " set_index = " << set_index;
141 return work_queue_heaps_[set_index].empty();
142 }
143
144 #if DCHECK_IS_ON() || !defined(NDEBUG)
ContainsWorkQueueForTest(const WorkQueue * work_queue) const145 bool WorkQueueSets::ContainsWorkQueueForTest(
146 const WorkQueue* work_queue) const {
147 EnqueueOrder enqueue_order;
148 bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
149
150 for (const IntrusiveHeap<OldestTaskEnqueueOrder>& heap : work_queue_heaps_) {
151 for (const OldestTaskEnqueueOrder& heap_value_pair : heap) {
152 if (heap_value_pair.value == work_queue) {
153 DCHECK(has_enqueue_order);
154 DCHECK_EQ(heap_value_pair.key, enqueue_order);
155 DCHECK_EQ(this, work_queue->work_queue_sets());
156 return true;
157 }
158 }
159 }
160
161 if (work_queue->work_queue_sets() == this) {
162 DCHECK(!has_enqueue_order);
163 return true;
164 }
165
166 return false;
167 }
168 #endif
169
170 } // namespace internal
171 } // namespace sequence_manager
172 } // namespace base
173