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