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 <utility> | |
10 #include <vector> | |
11 | |
12 #include "base/base_export.h" | |
13 #include "base/callback.h" | |
14 #include "base/macros.h" | |
15 #include "base/memory/ref_counted.h" | |
16 #include "base/memory/scoped_ptr.h" | |
17 #include "base/task_scheduler/scheduler_lock.h" | |
18 #include "base/task_scheduler/sequence.h" | |
19 #include "base/task_scheduler/sequence_sort_key.h" | |
20 #include "base/threading/non_thread_safe.h" | |
21 | |
22 namespace base { | |
23 namespace internal { | |
24 | |
25 // A priority queue holds sequences of tasks. This class is thread-safe. | |
26 class BASE_EXPORT PriorityQueue { | |
27 public: | |
28 // |sequence_inserted_callback| is invoked whenever a sequence is added to the | |
29 // priority queue. |predecessor_priority_queue| is a priority queue for which | |
30 // a thread is allowed to have an active transaction alive when it calls | |
31 // BeginTransaction() on this priority queue. | |
32 PriorityQueue(const Closure& sequence_inserted_callback); | |
33 PriorityQueue(const Closure& sequence_inserted_callback, | |
34 PriorityQueue* predecessor_priority_queue); | |
35 | |
36 ~PriorityQueue(); | |
37 | |
38 // Returns true if the priority queue is empty. Use a memory barrier before | |
39 // calling this to mitigate the chances of getting a stale result. The | |
40 // returned result can be invalidated at any time by sequences being pushed or | |
gab
2016/02/23 03:02:10
[old comment from my initial review -- looks like
fdoray
2016/02/23 17:02:14
I removed the method because I have a version of W
| |
41 // popped from the priority queue. | |
42 bool UnsynchronizedEmpty() const; | |
43 | |
44 class BASE_EXPORT Transaction : public NonThreadSafe { | |
45 public: | |
46 ~Transaction(); | |
47 | |
48 // Adds |sequence| to the priority queue. The position of |sequence| in the | |
49 // priority queue is determined by |sort_key|. | |
50 void PushSequence(scoped_refptr<Sequence> sequence, | |
51 const SequenceSortKey& sort_key); | |
52 | |
53 // Returns the sequence with the lowest sort key in the priority queue and | |
54 // sets |sort_key| to the sort key provided when that sequence was inserted | |
55 // in the priority queue. Returns nullptr if the priority queue is empty. | |
56 scoped_refptr<Sequence> PeekSequence(SequenceSortKey* sort_key) const; | |
57 | |
58 // Removes the sequence with the lowest sort key in the priority queue. | |
59 // Cannot be called on an empty priority queue. | |
60 void PopSequence(); | |
61 | |
62 private: | |
63 friend class PriorityQueue; | |
64 | |
65 Transaction(PriorityQueue* priority_queue); | |
66 | |
67 PriorityQueue* priority_queue_; | |
68 | |
69 // Holds the lock of |priority_queue_| for the lifetime of the transaction. | |
70 scoped_ptr<AutoSchedulerLock> auto_lock_; | |
71 | |
72 // Number of times that PushSequence() has been called on this transaction. | |
73 size_t num_pushed_sequences_; | |
74 | |
75 DISALLOW_COPY_AND_ASSIGN(Transaction); | |
76 }; | |
77 | |
78 // Begins a Transaction that can be used to perform peek and pop operations | |
79 // atomically on the priority queue. It is guaranteed that nothing else will | |
80 // modify the priority queue while the returned Transaction is alive. It is | |
81 // illegal to call this on a thread that has an active transaction for a | |
82 // priority queue which is not the one specified in the constructor of this | |
83 // priority queue. | |
84 scoped_ptr<Transaction> BeginTransaction(); | |
85 | |
86 private: | |
87 // Controls access to |container_|. | |
88 SchedulerLock lock_; | |
89 | |
90 using SequenceAndSortKeyPair = | |
91 std::pair<scoped_refptr<Sequence>, SequenceSortKey>; | |
92 struct SequenceAndSortKeyPairComparator { | |
93 bool operator()(const SequenceAndSortKeyPair& left, | |
94 const SequenceAndSortKeyPair& right) const; | |
95 }; | |
96 using ContainerType = std::priority_queue<SequenceAndSortKeyPair, | |
gab
2016/02/18 21:38:24
Looked into details of std::priority_queue and pre
| |
97 std::vector<SequenceAndSortKeyPair>, | |
98 SequenceAndSortKeyPairComparator>; | |
99 ContainerType container_; | |
100 | |
101 const Closure sequence_inserted_callback_; | |
102 | |
103 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | |
104 }; | |
105 | |
106 } // namespace internal | |
107 } // namespace base | |
108 | |
109 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ | |
OLD | NEW |