Index: base/task_scheduler/priority_queue.h |
diff --git a/base/task_scheduler/priority_queue.h b/base/task_scheduler/priority_queue.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..1f3f1b44b8f0cee862983173e304ac8a6cee9138 |
--- /dev/null |
+++ b/base/task_scheduler/priority_queue.h |
@@ -0,0 +1,108 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#ifndef BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
+#define BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |
+ |
+#include <queue> |
+#include <utility> |
+#include <vector> |
+ |
+#include "base/base_export.h" |
+#include "base/callback.h" |
+#include "base/macros.h" |
+#include "base/memory/ref_counted.h" |
+#include "base/memory/scoped_ptr.h" |
+#include "base/task_scheduler/scheduler_lock.h" |
+#include "base/task_scheduler/sequence.h" |
+#include "base/task_scheduler/sequence_sort_key.h" |
+ |
+namespace base { |
+namespace task_scheduler { |
+ |
+// A priority queue holds sequences of tasks. This class is thread-safe. |
+class BASE_EXPORT PriorityQueue { |
+ public: |
+ // |sequence_inserted_callback| is invoked whenever a sequence is added to the |
fdoray
2016/02/11 17:30:33
is *pushed* to the priority queue
fdoray
2016/02/12 04:16:19
WontFix
|
+ // priority queue. |predecessor_priority_queue| is a priority queue for which |
+ // a thread is allowed to have an active transaction alive when it calls |
+ // BeginTransaction() on this priority queue. |
+ PriorityQueue(const Closure& sequence_inserted_callback); |
+ PriorityQueue(const Closure& sequence_inserted_callback, |
+ PriorityQueue* predecessor_priority_queue); |
+ |
+ ~PriorityQueue(); |
+ |
+ // Returns true if the priority queue is empty. Use a memory barrier before |
+ // calling this to avoid getting a stale result. The returned result can be |
fdoray
2016/02/11 17:30:33
to *mitigate the chances* of getting a stale resul
fdoray
2016/02/12 04:16:19
Done.
|
+ // invalidated at any time by sequences being pushed or popped from the |
+ // priority queue. |
+ bool UnsynchronizedEmpty() const; |
+ |
+ class BASE_EXPORT Transaction { |
fdoray
2016/02/11 17:30:33
: public NonThreadSafe
fdoray
2016/02/12 04:16:19
Done.
|
+ public: |
+ ~Transaction(); |
+ |
+ // Adds |sequence| to the priority queue. The position of |sequence| in the |
+ // priority queue is determined by |sort_key|. |
+ void PushSequence(scoped_refptr<Sequence> sequence, |
+ const SequenceSortKey& sort_key); |
+ |
+ // Returns the sequence with the lowest sort key in the priority queue and |
+ // sets |sort_key| to the sort key provided when that sequence was inserted |
+ // in the priority queue. Returns nullptr if the priority queue is empty. |
+ scoped_refptr<Sequence> PeekSequence(SequenceSortKey* sort_key) const; |
+ |
+ // Removes the sequence with the lowest sort key in the priority queue. |
+ // Cannot be called on an empty priority queue. |
+ void PopSequence(); |
+ |
+ private: |
+ friend class PriorityQueue; |
+ |
+ Transaction(PriorityQueue* priority_queue); |
+ |
+ PriorityQueue* priority_queue_; |
+ |
+ // Holds the lock of |priority_queue_| for the lifetime of the transaction. |
+ scoped_ptr<AutoSchedulerLock> auto_lock_; |
+ |
+ // Number of times that PushSequence() has been called on this transaction. |
+ size_t num_pushed_sequences_; |
+ |
+ DISALLOW_COPY_AND_ASSIGN(Transaction); |
+ }; |
+ |
+ // Begins a Transaction that can be used to perform peek and pop operations |
+ // atomically on the priority queue. It is guaranteed that nothing else will |
+ // modify the priority queue while the returned Transaction is alive. The |
fdoray
2016/02/11 17:30:33
The *returned Transaction
fdoray
2016/02/12 04:16:19
Done.
|
+ // Transaction can only be used on the thread on which it was created. It is |
+ // illegal to call this on a thread that has an active transaction for another |
+ // priority queue than the one specified in the constructor. |
+ scoped_ptr<Transaction> BeginTransaction(); |
+ |
+ private: |
+ // Controls access to |priority_queue_|. |
fdoray
2016/02/11 17:30:33
to |container_|
fdoray
2016/02/12 04:16:19
Done.
|
+ SchedulerLock lock_; |
+ |
+ using SequenceAndSortKeyPair = |
+ std::pair<scoped_refptr<Sequence>, SequenceSortKey>; |
+ struct SequenceAndSortKeyPairComparator { |
+ bool operator()(const SequenceAndSortKeyPair& left, |
+ const SequenceAndSortKeyPair& right) const; |
+ }; |
+ using ContainerType = std::priority_queue<SequenceAndSortKeyPair, |
+ std::vector<SequenceAndSortKeyPair>, |
+ SequenceAndSortKeyPairComparator>; |
+ ContainerType container_; |
+ |
+ const Closure sequence_inserted_callback_; |
+ |
+ DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
+}; |
+ |
+} // namespace task_scheduler |
+} // namespace base |
+ |
+#endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |