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 #include "base/task_scheduler/priority_queue.h" | 5 #include "base/task_scheduler/priority_queue.h" |
6 | 6 |
7 #include <utility> | 7 #include <utility> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 #include "base/memory/ptr_util.h" | 10 #include "base/memory/ptr_util.h" |
11 | 11 |
12 namespace base { | 12 namespace base { |
13 namespace internal { | 13 namespace internal { |
14 | 14 |
15 PriorityQueue::SequenceAndSortKey::SequenceAndSortKey() | 15 // A class combining a Sequence and the SequenceSortKey that determines its |
16 : sort_key(TaskPriority::LOWEST, TimeTicks()) {} | 16 // position in a PriorityQueue. Instances are only mutable via take_sequence() |
17 // which can only be called once and renders its instance invalid after the | |
18 // call. | |
19 class PriorityQueue::SequenceAndSortKey { | |
20 public: | |
21 SequenceAndSortKey(scoped_refptr<Sequence>&& sequence, | |
22 const SequenceSortKey& sort_key) | |
23 : sequence_(sequence), sort_key_(sort_key) { | |
24 DCHECK(sequence_); | |
25 } | |
17 | 26 |
18 PriorityQueue::SequenceAndSortKey::SequenceAndSortKey( | 27 // Note: while |sequence_| should always be non-null post-move (i.e. we |
19 scoped_refptr<Sequence> sequence, | 28 // shouldn't be moving an invalid SequenceAndSortKey around), there can't be a |
20 const SequenceSortKey& sort_key) | 29 // DCHECK(sequence_) on moves as the Windows STL moves elements on pop instead |
21 : sequence(std::move(sequence)), sort_key(sort_key) {} | 30 // of overwriting them: resulting in the move of a SequenceAndSortKey with a |
31 // null |sequence_| in Transaction::Pop()'s implementation. | |
32 SequenceAndSortKey::SequenceAndSortKey(SequenceAndSortKey&& other) = default; | |
33 SequenceAndSortKey& SequenceAndSortKey::operator=( | |
34 SequenceAndSortKey&& other) = default; | |
22 | 35 |
23 PriorityQueue::SequenceAndSortKey::~SequenceAndSortKey() = default; | 36 // Extracts |sequence_| from this object. This object is invalid after this |
37 // call. | |
38 scoped_refptr<Sequence>&& take_sequence() { | |
danakj
2016/04/27 20:50:59
return by value
gab
2016/04/28 13:47:15
oops that wasn't intended to survive this patch se
| |
39 DCHECK(sequence_); | |
40 return std::move(sequence_); | |
41 } | |
42 | |
43 // Compares this SequenceAndSortKey to |other| based on their respective | |
44 // |sort_key_|. | |
45 bool operator<(const SequenceAndSortKey& other) const { | |
46 return sort_key_ < other.sort_key_; | |
47 } | |
48 bool operator>(const SequenceAndSortKey& other) const { | |
49 return other < *this; | |
50 } | |
51 | |
52 const SequenceSortKey& sort_key() const { return sort_key_; } | |
53 | |
54 private: | |
55 scoped_refptr<Sequence> sequence_; | |
56 SequenceSortKey sort_key_; | |
57 | |
58 DISALLOW_COPY_AND_ASSIGN(SequenceAndSortKey); | |
59 }; | |
24 | 60 |
25 PriorityQueue::Transaction::Transaction(PriorityQueue* outer_queue) | 61 PriorityQueue::Transaction::Transaction(PriorityQueue* outer_queue) |
26 : auto_lock_(outer_queue->container_lock_), outer_queue_(outer_queue) { | 62 : auto_lock_(outer_queue->container_lock_), outer_queue_(outer_queue) { |
27 DCHECK(CalledOnValidThread()); | 63 DCHECK(CalledOnValidThread()); |
28 } | 64 } |
29 | 65 |
30 PriorityQueue::Transaction::~Transaction() { | 66 PriorityQueue::Transaction::~Transaction() { |
31 DCHECK(CalledOnValidThread()); | 67 DCHECK(CalledOnValidThread()); |
32 } | 68 } |
33 | 69 |
34 void PriorityQueue::Transaction::Push( | 70 void PriorityQueue::Transaction::Push( |
35 std::unique_ptr<SequenceAndSortKey> sequence_and_sort_key) { | 71 scoped_refptr<Sequence> sequence, |
72 const SequenceSortKey& sequence_sort_key) { | |
36 DCHECK(CalledOnValidThread()); | 73 DCHECK(CalledOnValidThread()); |
37 DCHECK(!sequence_and_sort_key->is_null()); | 74 outer_queue_->container_.emplace(std::move(sequence), sequence_sort_key); |
38 | |
39 outer_queue_->container_.push(std::move(sequence_and_sort_key)); | |
40 } | 75 } |
41 | 76 |
42 const PriorityQueue::SequenceAndSortKey& PriorityQueue::Transaction::Peek() | 77 const SequenceSortKey& PriorityQueue::Transaction::PeekSortKey() const { |
43 const { | |
44 DCHECK(CalledOnValidThread()); | 78 DCHECK(CalledOnValidThread()); |
45 | 79 DCHECK(!IsEmpty()); |
46 // TODO(fdoray): Add an IsEmpty() method to Transaction and require Peek() to | 80 return outer_queue_->container_.top().sort_key(); |
47 // be called on a non-empty PriorityQueue only. | |
48 if (outer_queue_->container_.empty()) | |
49 return outer_queue_->empty_sequence_and_sort_key_; | |
50 | |
51 return *outer_queue_->container_.top(); | |
52 } | 81 } |
53 | 82 |
54 void PriorityQueue::Transaction::Pop() { | 83 scoped_refptr<Sequence> PriorityQueue::Transaction::PopSequence() { |
55 DCHECK(CalledOnValidThread()); | 84 DCHECK(CalledOnValidThread()); |
56 DCHECK(!outer_queue_->container_.empty()); | 85 DCHECK(!IsEmpty()); |
86 | |
87 // The const_cast on top() is okay since the SequenceAndSortKey is | |
88 // transactionally being popped from |container_| right after and taking its | |
89 // Sequence does not alter its sort order (a requirement for the Windows STL's | |
90 // consistency debug-checks for std::priority_queue::top()). | |
91 scoped_refptr<Sequence> sequence = | |
92 const_cast<PriorityQueue::SequenceAndSortKey&>( | |
93 outer_queue_->container_.top()) | |
94 .take_sequence(); | |
57 outer_queue_->container_.pop(); | 95 outer_queue_->container_.pop(); |
96 return sequence; | |
97 } | |
98 | |
99 bool PriorityQueue::Transaction::IsEmpty() const { | |
100 return outer_queue_->container_.empty(); | |
58 } | 101 } |
59 | 102 |
60 PriorityQueue::PriorityQueue() = default; | 103 PriorityQueue::PriorityQueue() = default; |
61 | 104 |
62 PriorityQueue::PriorityQueue(const PriorityQueue* predecessor_priority_queue) | 105 PriorityQueue::PriorityQueue(const PriorityQueue* predecessor_priority_queue) |
63 : container_lock_(&predecessor_priority_queue->container_lock_) { | 106 : container_lock_(&predecessor_priority_queue->container_lock_) { |
64 DCHECK(predecessor_priority_queue); | 107 DCHECK(predecessor_priority_queue); |
65 } | 108 } |
66 | 109 |
67 PriorityQueue::~PriorityQueue() = default; | 110 PriorityQueue::~PriorityQueue() = default; |
68 | 111 |
69 std::unique_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() { | 112 std::unique_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() { |
70 return WrapUnique(new Transaction(this)); | 113 return WrapUnique(new Transaction(this)); |
71 } | 114 } |
72 | 115 |
73 } // namespace internal | 116 } // namespace internal |
74 } // namespace base | 117 } // namespace base |
OLD | NEW |