OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | 5 #ifndef BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
6 #define BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | 6 #define BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
7 | 7 |
8 #include <memory> | 8 #include <memory> |
9 #include <queue> | 9 #include <queue> |
10 #include <vector> | 10 #include <vector> |
11 | 11 |
12 #include "base/base_export.h" | 12 #include "base/base_export.h" |
13 #include "base/callback.h" | |
14 #include "base/macros.h" | 13 #include "base/macros.h" |
15 #include "base/memory/ref_counted.h" | 14 #include "base/memory/ref_counted.h" |
16 #include "base/task_scheduler/scheduler_lock.h" | 15 #include "base/task_scheduler/scheduler_lock.h" |
17 #include "base/task_scheduler/sequence.h" | 16 #include "base/task_scheduler/sequence.h" |
18 #include "base/task_scheduler/sequence_sort_key.h" | 17 #include "base/task_scheduler/sequence_sort_key.h" |
19 #include "base/threading/non_thread_safe.h" | 18 #include "base/threading/non_thread_safe.h" |
20 | 19 |
21 namespace base { | 20 namespace base { |
22 namespace internal { | 21 namespace internal { |
23 | 22 |
(...skipping 25 matching lines...) Expand all Loading... |
49 // | 48 // |
50 // A WorkerThread needs to be able to Peek sequences from both its | 49 // A WorkerThread needs to be able to Peek sequences from both its |
51 // PriorityQueues (single-threaded and shared) and then Pop the sequence with | 50 // 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 | 51 // 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 | 52 // Transaction, it is guaranteed that the PriorityQueue hasn't changed between |
54 // the 2 operations. | 53 // the 2 operations. |
55 class BASE_EXPORT Transaction : public NonThreadSafe { | 54 class BASE_EXPORT Transaction : public NonThreadSafe { |
56 public: | 55 public: |
57 ~Transaction(); | 56 ~Transaction(); |
58 | 57 |
59 // Inserts |sequence_and_sort_key| in the PriorityQueue. Each call to this | 58 // Inserts |sequence_and_sort_key| in the PriorityQueue. |
60 // method will result in one invocation of the wake up callback when the | |
61 // Transaction is destroyed. | |
62 void Push(std::unique_ptr<SequenceAndSortKey> sequence_and_sort_key); | 59 void Push(std::unique_ptr<SequenceAndSortKey> sequence_and_sort_key); |
63 | 60 |
64 // Inserts |sequence_and_sort_key| in the PriorityQueue without invoking the | |
65 // wake up callback. | |
66 void PushNoWakeUp( | |
67 std::unique_ptr<SequenceAndSortKey> sequence_and_sort_key); | |
68 | |
69 // Returns the SequenceAndSortKey with the highest priority or a null | 61 // Returns the SequenceAndSortKey with the highest priority or a null |
70 // SequenceAndSortKey if the PriorityQueue is empty. The reference becomes | 62 // SequenceAndSortKey if the PriorityQueue is empty. The reference becomes |
71 // invalid the next time that a Sequence is popped from the PriorityQueue. | 63 // invalid the next time that a Sequence is popped from the PriorityQueue. |
72 const SequenceAndSortKey& Peek() const; | 64 const SequenceAndSortKey& Peek() const; |
73 | 65 |
74 // Removes the SequenceAndSortKey with the highest priority from the | 66 // Removes the SequenceAndSortKey with the highest priority from the |
75 // PriorityQueue. Cannot be called on an empty PriorityQueue. | 67 // PriorityQueue. Cannot be called on an empty PriorityQueue. |
76 void Pop(); | 68 void Pop(); |
77 | 69 |
78 private: | 70 private: |
79 friend class PriorityQueue; | 71 friend class PriorityQueue; |
80 | 72 |
81 explicit Transaction(PriorityQueue* outer_queue); | 73 explicit Transaction(PriorityQueue* outer_queue); |
82 | 74 |
83 // Holds the lock of |outer_queue_| for most of the lifetime of this | 75 // Holds the lock of |outer_queue_| for the lifetime of this Transaction. |
84 // Transaction. Using a scoped_ptr allows the destructor to release the lock | 76 AutoSchedulerLock auto_lock_; |
85 // before performing internal operations which have to be done outside of | |
86 // its scope. | |
87 std::unique_ptr<AutoSchedulerLock> auto_lock_; | |
88 | 77 |
89 PriorityQueue* const outer_queue_; | 78 PriorityQueue* const outer_queue_; |
90 | 79 |
91 // Number of times that the wake up callback should be invoked when this | |
92 // Transaction is destroyed. | |
93 size_t num_wake_ups_ = 0; | |
94 | |
95 DISALLOW_COPY_AND_ASSIGN(Transaction); | 80 DISALLOW_COPY_AND_ASSIGN(Transaction); |
96 }; | 81 }; |
97 | 82 |
98 // |wake_up_callback| is a non-null callback invoked when a Transaction is | 83 PriorityQueue(); |
99 // done for each call to Push() on the Transaction. | |
100 explicit PriorityQueue(const Closure& wake_up_callback); | |
101 | 84 |
102 // |wake_up_callback| is a non-null callback invoked when a Transaction is | |
103 // done for each call to Push() on the Transaction. | |
104 // |predecessor_priority_queue| is a PriorityQueue for which a thread is | 85 // |predecessor_priority_queue| is a PriorityQueue for which a thread is |
105 // allowed to have an active Transaction when it creates a Transaction for | 86 // allowed to have an active Transaction when it creates a Transaction for |
106 // this PriorityQueue. | 87 // this PriorityQueue. |
107 PriorityQueue(const Closure& wake_up_callback, | 88 PriorityQueue(const PriorityQueue* predecessor_priority_queue); |
108 const PriorityQueue* predecessor_priority_queue); | |
109 | 89 |
110 ~PriorityQueue(); | 90 ~PriorityQueue(); |
111 | 91 |
112 // Begins a Transaction. This method cannot be called on a thread which has an | 92 // Begins a Transaction. This method cannot be called on a thread which has an |
113 // active Transaction unless the last Transaction created on the thread was | 93 // active Transaction unless the last Transaction created on the thread was |
114 // for the allowed predecessor specified in the constructor of this | 94 // for the allowed predecessor specified in the constructor of this |
115 // PriorityQueue. | 95 // PriorityQueue. |
116 std::unique_ptr<Transaction> BeginTransaction(); | 96 std::unique_ptr<Transaction> BeginTransaction(); |
117 | 97 |
118 private: | 98 private: |
119 struct SequenceAndSortKeyComparator { | 99 struct SequenceAndSortKeyComparator { |
120 bool operator()(const std::unique_ptr<SequenceAndSortKey>& left, | 100 bool operator()(const std::unique_ptr<SequenceAndSortKey>& left, |
121 const std::unique_ptr<SequenceAndSortKey>& right) const { | 101 const std::unique_ptr<SequenceAndSortKey>& right) const { |
122 return left->sort_key < right->sort_key; | 102 return left->sort_key < right->sort_key; |
123 } | 103 } |
124 }; | 104 }; |
125 using ContainerType = | 105 using ContainerType = |
126 std::priority_queue<std::unique_ptr<SequenceAndSortKey>, | 106 std::priority_queue<std::unique_ptr<SequenceAndSortKey>, |
127 std::vector<std::unique_ptr<SequenceAndSortKey>>, | 107 std::vector<std::unique_ptr<SequenceAndSortKey>>, |
128 SequenceAndSortKeyComparator>; | 108 SequenceAndSortKeyComparator>; |
129 | 109 |
130 // Synchronizes access to |container_|. | 110 // Synchronizes access to |container_|. |
131 SchedulerLock container_lock_; | 111 SchedulerLock container_lock_; |
132 | 112 |
133 ContainerType container_; | 113 ContainerType container_; |
134 | 114 |
135 const Closure wake_up_callback_; | |
136 | |
137 // A null SequenceAndSortKey returned by Peek() when the PriorityQueue is | 115 // A null SequenceAndSortKey returned by Peek() when the PriorityQueue is |
138 // empty. | 116 // empty. |
139 const SequenceAndSortKey empty_sequence_and_sort_key_; | 117 const SequenceAndSortKey empty_sequence_and_sort_key_; |
140 | 118 |
141 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | 119 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
142 }; | 120 }; |
143 | 121 |
144 } // namespace internal | 122 } // namespace internal |
145 } // namespace base | 123 } // namespace base |
146 | 124 |
147 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | 125 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
OLD | NEW |