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 #include "base/task_scheduler/priority_queue.h" 6 7 #include <utility> 8 9 #include "base/logging.h" 10 #include "base/memory/ptr_util.h" 11 12 namespace base { 13 namespace internal { 14 15 // A class combining a Sequence and the SequenceSortKey that determines its 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: SequenceAndSortKey(scoped_refptr<Sequence> sequence,const SequenceSortKey & sort_key)21 SequenceAndSortKey(scoped_refptr<Sequence> sequence, 22 const SequenceSortKey& sort_key) 23 : sequence_(std::move(sequence)), sort_key_(sort_key) { 24 DCHECK(sequence_); 25 } 26 27 // Note: while |sequence_| should always be non-null post-move (i.e. we 28 // shouldn't be moving an invalid SequenceAndSortKey around), there can't be a 29 // DCHECK(sequence_) on moves as the Windows STL moves elements on pop instead 30 // of overwriting them: resulting in the move of a SequenceAndSortKey with a 31 // null |sequence_| in Transaction::Pop()'s implementation. 32 SequenceAndSortKey(SequenceAndSortKey&& other) = default; 33 SequenceAndSortKey& operator=(SequenceAndSortKey&& other) = default; 34 35 // Extracts |sequence_| from this object. This object is invalid after this 36 // call. take_sequence()37 scoped_refptr<Sequence> take_sequence() { 38 DCHECK(sequence_); 39 return std::move(sequence_); 40 } 41 42 // Compares this SequenceAndSortKey to |other| based on their respective 43 // |sort_key_|. operator <(const SequenceAndSortKey & other) const44 bool operator<(const SequenceAndSortKey& other) const { 45 return sort_key_ < other.sort_key_; 46 } 47 // Style-guide dictates to define operator> when defining operator< but it's 48 // unused in this case and this isn't a public API. Explicitly delete it so 49 // any errors point here if that ever changes. 50 bool operator>(const SequenceAndSortKey& other) const = delete; 51 sort_key() const52 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 }; 60 Transaction(PriorityQueue * outer_queue)61PriorityQueue::Transaction::Transaction(PriorityQueue* outer_queue) 62 : auto_lock_(outer_queue->container_lock_), outer_queue_(outer_queue) { 63 } 64 65 PriorityQueue::Transaction::~Transaction() = default; 66 Push(scoped_refptr<Sequence> sequence,const SequenceSortKey & sequence_sort_key)67void PriorityQueue::Transaction::Push( 68 scoped_refptr<Sequence> sequence, 69 const SequenceSortKey& sequence_sort_key) { 70 outer_queue_->container_.emplace(std::move(sequence), sequence_sort_key); 71 } 72 PeekSortKey() const73const SequenceSortKey& PriorityQueue::Transaction::PeekSortKey() const { 74 DCHECK(!IsEmpty()); 75 return outer_queue_->container_.top().sort_key(); 76 } 77 PopSequence()78scoped_refptr<Sequence> PriorityQueue::Transaction::PopSequence() { 79 DCHECK(!IsEmpty()); 80 81 // The const_cast on top() is okay since the SequenceAndSortKey is 82 // transactionally being popped from |container_| right after and taking its 83 // Sequence does not alter its sort order (a requirement for the Windows STL's 84 // consistency debug-checks for std::priority_queue::top()). 85 scoped_refptr<Sequence> sequence = 86 const_cast<PriorityQueue::SequenceAndSortKey&>( 87 outer_queue_->container_.top()) 88 .take_sequence(); 89 outer_queue_->container_.pop(); 90 return sequence; 91 } 92 IsEmpty() const93bool PriorityQueue::Transaction::IsEmpty() const { 94 return outer_queue_->container_.empty(); 95 } 96 Size() const97size_t PriorityQueue::Transaction::Size() const { 98 return outer_queue_->container_.size(); 99 } 100 101 PriorityQueue::PriorityQueue() = default; 102 103 PriorityQueue::~PriorityQueue() = default; 104 BeginTransaction()105std::unique_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() { 106 return WrapUnique(new Transaction(this)); 107 } 108 109 } // namespace internal 110 } // namespace base 111