OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2016 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 #ifndef BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | |
6 #define BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | |
7 | |
8 #include <queue> | |
9 #include <vector> | |
10 | |
11 #include "base/base_export.h" | |
12 #include "base/callback.h" | |
13 #include "base/macros.h" | |
14 #include "base/memory/ref_counted.h" | |
15 #include "base/memory/scoped_ptr.h" | |
16 #include "base/task_scheduler/scheduler_lock.h" | |
17 #include "base/task_scheduler/sequence.h" | |
18 #include "base/task_scheduler/sequence_sort_key.h" | |
19 #include "base/threading/non_thread_safe.h" | |
20 | |
21 namespace base { | |
22 namespace internal { | |
23 | |
24 // A PriorityQueue holds Sequences of Tasks. This class is thread-safe. | |
25 class BASE_EXPORT PriorityQueue { | |
26 public: | |
27 // An immutable struct combining a Sequence and the sort key that determines | |
28 // its position in a PriorityQueue. | |
29 struct BASE_EXPORT SequenceAndSortKey { | |
30 // Constructs a null SequenceAndSortKey. | |
31 SequenceAndSortKey(); | |
32 | |
33 // Constructs a SequenceAndSortKey with the given |sequence| and |sort_key|. | |
34 SequenceAndSortKey(scoped_refptr<Sequence> sequence, | |
35 const SequenceSortKey& sort_key); | |
36 | |
37 ~SequenceAndSortKey(); | |
38 | |
39 // Returns true if this is a null SequenceAndSortKey. | |
40 bool is_null() const { return !sequence; } | |
41 | |
42 const scoped_refptr<Sequence> sequence; | |
43 const SequenceSortKey sort_key; | |
44 }; | |
45 | |
46 // A Transaction can perform multiple operations atomically on a | |
47 // PriorityQueue. While a Transaction is alive, it is guaranteed that nothing | |
48 // else will access the PriorityQueue. | |
49 // | |
50 // A WorkerThread needs to be able to Peek sequences from both its | |
51 // PriorityQueues (single-threaded and shared) and then Pop the sequence with | |
52 // the highest priority. If the Peek and the Pop are done through the same | |
53 // Transaction, it is guaranteed that the PriorityQueue hasn't changed between | |
54 // the 2 operations. | |
55 class BASE_EXPORT Transaction : public NonThreadSafe { | |
56 public: | |
57 ~Transaction(); | |
58 | |
59 // Inserts |sequence_and_sort_key| in the PriorityQueue. | |
60 void Push(scoped_ptr<SequenceAndSortKey> sequence_and_sort_key); | |
61 | |
62 // Returns the SequenceAndSortKey with the highest priority or a null | |
63 // SequenceAndSortKey if the PriorityQueue is empty. The reference becomes | |
64 // invalid the next time that a Sequence is popped from the PriorityQueue. | |
65 const SequenceAndSortKey& Peek() const; | |
66 | |
67 // Removes the SequenceAndSortKey with the highest priority from the | |
68 // PriorityQueue. Cannot be called on an empty PriorityQueue. | |
69 void Pop(); | |
70 | |
71 private: | |
72 friend class PriorityQueue; | |
73 | |
74 explicit Transaction(PriorityQueue* outer_queue); | |
75 | |
76 PriorityQueue* const outer_queue_; | |
77 | |
78 // Holds the lock of |outer_queue_| for most of the lifetime of this | |
79 // Transaction. | |
80 // Using a scoped_ptr allows the destructor to release the lock before | |
81 // performing internal operations which have to be done outside of its | |
82 // scope. | |
83 scoped_ptr<AutoSchedulerLock> auto_lock_; | |
84 | |
85 // Number of times that Push() has been called on this Transaction. | |
86 size_t num_pushed_sequences_ = 0; | |
87 | |
88 DISALLOW_COPY_AND_ASSIGN(Transaction); | |
89 }; | |
90 | |
91 // |sequence_inserted_callback| is a non-null callback invoked when the | |
92 // Transaction is done for each Push that was performed with the Transaction. | |
93 explicit PriorityQueue(const Closure& sequence_inserted_callback); | |
94 | |
95 // |sequence_inserted_callback| is a non-null callback invoked when the | |
96 // Transaction is done for each Push that was performed with the Transaction. | |
97 // |predecessor_priority_queue| is a PriorityQueue for which a thread is | |
98 // allowed to have an active Transaction when it creates a Transaction for | |
99 // this PriorityQueue. | |
100 PriorityQueue(const Closure& sequence_inserted_callback, | |
101 const PriorityQueue* predecessor_priority_queue); | |
102 | |
103 ~PriorityQueue(); | |
104 | |
105 // Begins a Transaction. This method cannot be called on a thread which has an | |
106 // active Transaction unless the last Transaction created on the thread was | |
107 // for the allowed predecessor specified in the constructor of this | |
108 // PriorityQueue. | |
109 scoped_ptr<Transaction> BeginTransaction(); | |
110 | |
111 private: | |
112 struct SequenceAndSortKeyComparator { | |
113 bool operator()(const scoped_ptr<SequenceAndSortKey>& left, | |
114 const scoped_ptr<SequenceAndSortKey>& right) const { | |
115 return left->sort_key < right->sort_key; | |
116 } | |
117 }; | |
118 using ContainerType = | |
119 std::priority_queue<scoped_ptr<SequenceAndSortKey>, | |
120 std::vector<scoped_ptr<SequenceAndSortKey>>, | |
121 SequenceAndSortKeyComparator>; | |
122 | |
123 // Synchronizes access to |container_|. | |
124 SchedulerLock container_lock_; | |
125 | |
126 ContainerType container_; | |
127 | |
128 const Closure sequence_inserted_callback_; | |
129 | |
130 // A null SequenceAndSortKey returned by Peek() when the PriorityQueue is | |
131 // empty. | |
132 const SequenceAndSortKey empty_sequence_and_sort_key_; | |
danakj
2016/03/18 20:24:05
static?
you could probably put this in an anon na
fdoray
2016/03/18 21:22:18
I believe that the style guide doesn't allow non-P
danakj
2016/03/18 21:24:08
Oops, ya that's right.
| |
133 | |
134 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | |
135 }; | |
136 | |
137 } // namespace internal | |
138 } // namespace base | |
139 | |
140 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | |
OLD | NEW |