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 <vector> |
| 10 |
| 11 #include "base/base_export.h" |
| 12 #include "base/callback.h" |
| 13 #include "base/macros.h" |
| 14 #include "base/memory/ref_counted.h" |
| 15 #include "base/memory/scoped_ptr.h" |
| 16 #include "base/task_scheduler/scheduler_lock.h" |
| 17 #include "base/task_scheduler/sequence.h" |
| 18 #include "base/task_scheduler/sequence_sort_key.h" |
| 19 #include "base/threading/non_thread_safe.h" |
| 20 |
| 21 namespace base { |
| 22 namespace internal { |
| 23 |
| 24 // A PriorityQueue holds Sequences of Tasks. This class is thread-safe. |
| 25 class BASE_EXPORT PriorityQueue { |
| 26 public: |
| 27 // An immutable struct combining a Sequence and the sort key that determines |
| 28 // its position in a PriorityQueue. |
| 29 struct BASE_EXPORT SequenceAndSortKey { |
| 30 // Constructs a null SequenceAndSortKey. |
| 31 SequenceAndSortKey(); |
| 32 |
| 33 // Constructs a SequenceAndSortKey with the given |sequence| and |sort_key|. |
| 34 SequenceAndSortKey(scoped_refptr<Sequence> sequence, |
| 35 const SequenceSortKey& sort_key); |
| 36 |
| 37 ~SequenceAndSortKey(); |
| 38 |
| 39 // Returns true if this is a null SequenceAndSortKey. |
| 40 bool is_null() const { return !sequence; } |
| 41 |
| 42 const scoped_refptr<Sequence> sequence; |
| 43 const SequenceSortKey sort_key; |
| 44 }; |
| 45 |
| 46 // A Transaction can perform multiple operations atomically on a |
| 47 // PriorityQueue. While a Transaction is alive, it is guaranteed that nothing |
| 48 // else will access the PriorityQueue. |
| 49 // |
| 50 // A WorkerThread needs to be able to Peek sequences from both its |
| 51 // 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 |
| 53 // Transaction, it is guaranteed that the PriorityQueue hasn't changed between |
| 54 // the 2 operations. |
| 55 class BASE_EXPORT Transaction : public NonThreadSafe { |
| 56 public: |
| 57 ~Transaction(); |
| 58 |
| 59 // Inserts |sequence_and_sort_key| in the PriorityQueue. |
| 60 void Push(scoped_ptr<SequenceAndSortKey> sequence_and_sort_key); |
| 61 |
| 62 // Returns the SequenceAndSortKey with the highest priority or a null |
| 63 // SequenceAndSortKey if the PriorityQueue is empty. The reference becomes |
| 64 // invalid the next time that a Sequence is popped from the PriorityQueue. |
| 65 const SequenceAndSortKey& Peek() const; |
| 66 |
| 67 // Removes the SequenceAndSortKey with the highest priority from the |
| 68 // PriorityQueue. Cannot be called on an empty PriorityQueue. |
| 69 void Pop(); |
| 70 |
| 71 private: |
| 72 friend class PriorityQueue; |
| 73 |
| 74 explicit Transaction(PriorityQueue* outer_queue); |
| 75 |
| 76 // Holds the lock of |outer_queue_| for most of the lifetime of this |
| 77 // Transaction. Using a scoped_ptr allows the destructor to release the lock |
| 78 // before performing internal operations which have to be done outside of |
| 79 // its scope. |
| 80 scoped_ptr<AutoSchedulerLock> auto_lock_; |
| 81 |
| 82 PriorityQueue* const outer_queue_; |
| 83 |
| 84 // Number of times that Push() has been called on this Transaction. |
| 85 size_t num_pushed_sequences_ = 0; |
| 86 |
| 87 DISALLOW_COPY_AND_ASSIGN(Transaction); |
| 88 }; |
| 89 |
| 90 // |sequence_inserted_callback| is a non-null callback invoked when the |
| 91 // Transaction is done for each Push that was performed with the Transaction. |
| 92 explicit PriorityQueue(const Closure& sequence_inserted_callback); |
| 93 |
| 94 // |sequence_inserted_callback| is a non-null callback invoked when the |
| 95 // Transaction is done for each Push that was performed with the Transaction. |
| 96 // |predecessor_priority_queue| is a PriorityQueue for which a thread is |
| 97 // allowed to have an active Transaction when it creates a Transaction for |
| 98 // this PriorityQueue. |
| 99 PriorityQueue(const Closure& sequence_inserted_callback, |
| 100 const PriorityQueue* predecessor_priority_queue); |
| 101 |
| 102 ~PriorityQueue(); |
| 103 |
| 104 // Begins a Transaction. This method cannot be called on a thread which has an |
| 105 // active Transaction unless the last Transaction created on the thread was |
| 106 // for the allowed predecessor specified in the constructor of this |
| 107 // PriorityQueue. |
| 108 scoped_ptr<Transaction> BeginTransaction(); |
| 109 |
| 110 private: |
| 111 struct SequenceAndSortKeyComparator { |
| 112 bool operator()(const scoped_ptr<SequenceAndSortKey>& left, |
| 113 const scoped_ptr<SequenceAndSortKey>& right) const { |
| 114 return left->sort_key < right->sort_key; |
| 115 } |
| 116 }; |
| 117 using ContainerType = |
| 118 std::priority_queue<scoped_ptr<SequenceAndSortKey>, |
| 119 std::vector<scoped_ptr<SequenceAndSortKey>>, |
| 120 SequenceAndSortKeyComparator>; |
| 121 |
| 122 // Synchronizes access to |container_|. |
| 123 SchedulerLock container_lock_; |
| 124 |
| 125 ContainerType container_; |
| 126 |
| 127 const Closure sequence_inserted_callback_; |
| 128 |
| 129 // A null SequenceAndSortKey returned by Peek() when the PriorityQueue is |
| 130 // empty. |
| 131 const SequenceAndSortKey empty_sequence_and_sort_key_; |
| 132 |
| 133 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
| 134 }; |
| 135 |
| 136 } // namespace internal |
| 137 } // namespace base |
| 138 |
| 139 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
OLD | NEW |