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/macros.h" | 13 #include "base/macros.h" |
14 #include "base/memory/ref_counted.h" | 14 #include "base/memory/ref_counted.h" |
15 #include "base/task_scheduler/scheduler_lock.h" | 15 #include "base/task_scheduler/scheduler_lock.h" |
16 #include "base/task_scheduler/sequence.h" | 16 #include "base/task_scheduler/sequence.h" |
17 #include "base/task_scheduler/sequence_sort_key.h" | 17 #include "base/task_scheduler/sequence_sort_key.h" |
18 #include "base/threading/non_thread_safe.h" | 18 #include "base/threading/non_thread_safe.h" |
19 | 19 |
20 namespace base { | 20 namespace base { |
21 namespace internal { | 21 namespace internal { |
22 | 22 |
23 // A PriorityQueue holds Sequences of Tasks. This class is thread-safe. | 23 // A PriorityQueue holds Sequences of Tasks. This class is thread-safe. |
24 class BASE_EXPORT PriorityQueue { | 24 class BASE_EXPORT PriorityQueue { |
25 public: | 25 public: |
26 // An immutable struct combining a Sequence and the sort key that determines | |
27 // its position in a PriorityQueue. | |
28 struct BASE_EXPORT SequenceAndSortKey { | |
29 // Constructs a null SequenceAndSortKey. | |
30 SequenceAndSortKey(); | |
31 | |
32 // Constructs a SequenceAndSortKey with the given |sequence| and |sort_key|. | |
33 SequenceAndSortKey(scoped_refptr<Sequence> sequence, | |
34 const SequenceSortKey& sort_key); | |
35 ~SequenceAndSortKey(); | |
36 | |
37 // Returns true if this is a null SequenceAndSortKey. | |
38 bool is_null() const { return !sequence; } | |
39 | |
40 const scoped_refptr<Sequence> sequence; | |
41 const SequenceSortKey sort_key; | |
42 | |
43 private: | |
44 DISALLOW_COPY_AND_ASSIGN(SequenceAndSortKey); | |
45 }; | |
46 | |
47 // A Transaction can perform multiple operations atomically on a | 26 // A Transaction can perform multiple operations atomically on a |
48 // PriorityQueue. While a Transaction is alive, it is guaranteed that nothing | 27 // PriorityQueue. While a Transaction is alive, it is guaranteed that nothing |
49 // else will access the PriorityQueue. | 28 // else will access the PriorityQueue. |
50 // | 29 // |
51 // A WorkerThread needs to be able to Peek sequences from both its | 30 // A WorkerThread needs to be able to Peek sequences from both its |
52 // PriorityQueues (single-threaded and shared) and then Pop the sequence with | 31 // PriorityQueues (single-threaded and shared) and then Pop the sequence with |
53 // the highest priority. If the Peek and the Pop are done through the same | 32 // the highest priority. If the Peek and the Pop are done through the same |
54 // Transaction, it is guaranteed that the PriorityQueue hasn't changed between | 33 // Transaction, it is guaranteed that the PriorityQueue hasn't changed between |
55 // the 2 operations. | 34 // the 2 operations. |
56 class BASE_EXPORT Transaction : public NonThreadSafe { | 35 class BASE_EXPORT Transaction : public NonThreadSafe { |
57 public: | 36 public: |
58 ~Transaction(); | 37 ~Transaction(); |
59 | 38 |
60 // Inserts |sequence_and_sort_key| in the PriorityQueue. | 39 // Inserts |sequence| in the PriorityQueue with |sequence_sort_key|. |
61 void Push(std::unique_ptr<SequenceAndSortKey> sequence_and_sort_key); | 40 // Note: |sequence_sort_key| is required as a parameter instead of being |
| 41 // extracted from |sequence| in Push() to avoid this Transaction having a |
| 42 // lock interdependency with |sequence|. |
| 43 void Push(scoped_refptr<Sequence> sequence, |
| 44 const SequenceSortKey& sequence_sort_key); |
62 | 45 |
63 // Returns the SequenceAndSortKey with the highest priority or a null | 46 // Returns a reference to the SequenceSortKey representing the priority of |
64 // SequenceAndSortKey if the PriorityQueue is empty. The reference becomes | 47 // the highest pending task in this PriorityQueue. The reference becomes |
65 // invalid the next time that a Sequence is popped from the PriorityQueue. | 48 // invalid the next time that this PriorityQueue is modified. |
66 const SequenceAndSortKey& Peek() const; | 49 // Cannot be called on an empty PriorityQueue. |
| 50 const SequenceSortKey& PeekSortKey() const; |
67 | 51 |
68 // Removes the SequenceAndSortKey with the highest priority from the | 52 // Removes and returns the highest priority Sequence in this PriorityQueue. |
69 // PriorityQueue. Cannot be called on an empty PriorityQueue. | 53 // Cannot be called on an empty PriorityQueue. |
70 void Pop(); | 54 scoped_refptr<Sequence> PopSequence(); |
| 55 |
| 56 // Returns true if the PriorityQueue is empty. |
| 57 bool IsEmpty() const; |
71 | 58 |
72 private: | 59 private: |
73 friend class PriorityQueue; | 60 friend class PriorityQueue; |
74 | 61 |
75 explicit Transaction(PriorityQueue* outer_queue); | 62 explicit Transaction(PriorityQueue* outer_queue); |
76 | 63 |
77 // Holds the lock of |outer_queue_| for the lifetime of this Transaction. | 64 // Holds the lock of |outer_queue_| for the lifetime of this Transaction. |
78 AutoSchedulerLock auto_lock_; | 65 AutoSchedulerLock auto_lock_; |
79 | 66 |
80 PriorityQueue* const outer_queue_; | 67 PriorityQueue* const outer_queue_; |
(...skipping 12 matching lines...) Expand all Loading... |
93 | 80 |
94 // Begins a Transaction. This method cannot be called on a thread which has an | 81 // Begins a Transaction. This method cannot be called on a thread which has an |
95 // active Transaction unless the last Transaction created on the thread was | 82 // active Transaction unless the last Transaction created on the thread was |
96 // for the allowed predecessor specified in the constructor of this | 83 // for the allowed predecessor specified in the constructor of this |
97 // PriorityQueue. | 84 // PriorityQueue. |
98 std::unique_ptr<Transaction> BeginTransaction(); | 85 std::unique_ptr<Transaction> BeginTransaction(); |
99 | 86 |
100 const SchedulerLock* container_lock() const { return &container_lock_; } | 87 const SchedulerLock* container_lock() const { return &container_lock_; } |
101 | 88 |
102 private: | 89 private: |
103 struct SequenceAndSortKeyComparator { | 90 // A class combining a Sequence and the SequenceSortKey that determines its |
104 bool operator()(const std::unique_ptr<SequenceAndSortKey>& left, | 91 // position in a PriorityQueue. |
105 const std::unique_ptr<SequenceAndSortKey>& right) const { | 92 class SequenceAndSortKey; |
106 return left->sort_key < right->sort_key; | 93 |
107 } | 94 using ContainerType = std::priority_queue<SequenceAndSortKey>; |
108 }; | |
109 using ContainerType = | |
110 std::priority_queue<std::unique_ptr<SequenceAndSortKey>, | |
111 std::vector<std::unique_ptr<SequenceAndSortKey>>, | |
112 SequenceAndSortKeyComparator>; | |
113 | 95 |
114 // Synchronizes access to |container_|. | 96 // Synchronizes access to |container_|. |
115 SchedulerLock container_lock_; | 97 SchedulerLock container_lock_; |
116 | 98 |
117 ContainerType container_; | 99 ContainerType container_; |
118 | 100 |
119 // A null SequenceAndSortKey returned by Peek() when the PriorityQueue is | |
120 // empty. | |
121 const SequenceAndSortKey empty_sequence_and_sort_key_; | |
122 | |
123 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | 101 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
124 }; | 102 }; |
125 | 103 |
126 } // namespace internal | 104 } // namespace internal |
127 } // namespace base | 105 } // namespace base |
128 | 106 |
129 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | 107 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
OLD | NEW |