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..f7323d4e5f19d9322ebfa6849f6ddcb17df43b79 |
--- /dev/null |
+++ b/base/task_scheduler/priority_queue.h |
@@ -0,0 +1,124 @@ |
+// 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 <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" |
+#include "base/threading/non_thread_safe.h" |
+ |
+namespace base { |
+namespace internal { |
+ |
+// A PriorityQueue holds Sequences of Tasks. This class is thread-safe. |
+class BASE_EXPORT PriorityQueue { |
+ public: |
+ // An immutable struct combining a Sequence and the sort key that determines |
+ // its position in a PriorityQueue. |
+ struct BASE_EXPORT SequenceAndSortKey { |
+ // Constructs a null SequenceAndSortKey. |
+ SequenceAndSortKey(); |
+ |
+ // Constructs a SequenceAndSortKey with the given |sequence| and |sort_key|. |
+ SequenceAndSortKey(scoped_refptr<Sequence> sequence, |
+ SequenceSortKey sort_key); |
danakj
2016/03/17 21:32:14
const&
fdoray
2016/03/18 16:06:55
Done.
|
+ |
+ ~SequenceAndSortKey(); |
+ |
+ // Returns true if this is a null SequenceAndSortKey. |
+ bool is_null() const; |
+ |
+ const scoped_refptr<Sequence> sequence; |
+ const SequenceSortKey sort_key; |
+ }; |
+ |
+ // |sequence_inserted_callback| is a non-null callback invoked when a sequence |
+ // is added to the PriorityQueue. |
danakj
2016/03/17 21:32:14
Can you document this happens when the transaction
fdoray
2016/03/18 16:06:55
Done.
|
+ explicit PriorityQueue(const Closure& sequence_inserted_callback); |
+ |
+ // |sequence_inserted_callback| is a non-null callback invoked when a sequence |
+ // is added to the PriorityQueue. |predecessor_priority_queue| is a |
+ // PriorityQueue for which a thread is allowed to have an active Transaction |
+ // when it creates a Transaction for this PriorityQueue. |
+ PriorityQueue(const Closure& sequence_inserted_callback, |
+ const PriorityQueue* predecessor_priority_queue); |
+ |
+ ~PriorityQueue(); |
+ |
+ class BASE_EXPORT Transaction : public NonThreadSafe { |
robliao
2016/03/17 17:48:10
Move this after SequenceAndSortKey's definition.
fdoray
2016/03/17 19:12:02
Done.
danakj
2016/03/17 21:32:15
Put a comment on this class, what is it?
fdoray
2016/03/18 16:06:55
Done.
|
+ public: |
+ ~Transaction(); |
+ |
+ // Inserts |sequence_and_sort_key| in the PriorityQueue. |
+ void Push(scoped_ptr<SequenceAndSortKey> sequence_and_sort_key); |
+ |
+ // Returns the SequenceAndSortKey with the highest priority or a null |
+ // SequenceAndSortKey if the PriorityQueue is empty. |
+ SequenceAndSortKey Peek() const; |
+ |
+ // Removes the SequenceAndSortKey with the highest priority from the |
+ // PriorityQueue. Cannot be called on an empty PriorityQueue. |
+ void Pop(); |
+ |
+ private: |
+ friend class PriorityQueue; |
+ |
+ explicit Transaction(PriorityQueue* outer); |
+ |
+ PriorityQueue* const outer_; |
danakj
2016/03/17 21:32:15
outer_queue_?
fdoray
2016/03/18 16:06:55
Done.
|
+ |
+ // Holds the lock of |outer_| for most of the lifetime of this Transaction. |
danakj
2016/03/17 21:32:14
Why is it okay that while a Transaction is alive t
danakj
2016/03/17 21:32:14
usually locks sit right above the things they lock
fdoray
2016/03/18 16:06:55
Done. Added an explanation above the declaration o
fdoray
2016/03/18 16:06:55
This is not a lock. It's an auto-lock to hold oute
danakj
2016/03/18 20:24:05
Yeah, but it's holding a lock in the auto lock. Wh
fdoray
2016/03/18 21:22:18
Ah ok! Done.
|
+ // Using a scoped_ptr allows the destructor to release the lock before |
+ // performing internal operations which have to be done outside of its |
+ // scope. |
+ scoped_ptr<AutoSchedulerLock> auto_lock_; |
+ |
+ // Number of times that Push() has been called on this Transaction. |
+ size_t num_pushed_sequences_ = 0; |
+ |
+ DISALLOW_COPY_AND_ASSIGN(Transaction); |
+ }; |
+ |
+ // Begins a Transaction which allows multiple operations to be performed |
+ // atomically on the PriorityQueue. It is guaranteed that nothing else will |
+ // modify the PriorityQueue while the returned Transaction is alive. This |
+ // method cannot be called on a thread which has an active Transaction unless |
+ // the last Transaction created on the thread was for the allowed predecessor |
+ // specified in the constructor of this PriorityQueue. |
+ scoped_ptr<Transaction> BeginTransaction(); |
+ |
+ private: |
+ struct SequenceAndSortKeyComparator { |
+ bool operator()(const scoped_ptr<SequenceAndSortKey>& left, |
+ const scoped_ptr<SequenceAndSortKey>& right) const; |
+ }; |
+ using ContainerType = |
+ std::priority_queue<scoped_ptr<SequenceAndSortKey>, |
+ std::vector<scoped_ptr<SequenceAndSortKey>>, |
+ SequenceAndSortKeyComparator>; |
+ |
+ // Synchronizes access to |container_|. |
+ SchedulerLock lock_; |
danakj
2016/03/17 21:32:14
container_lock_?
fdoray
2016/03/18 16:06:55
Done.
|
+ |
+ ContainerType container_; |
+ |
+ const Closure sequence_inserted_callback_; |
+ |
+ DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
+}; |
+ |
+} // namespace internal |
+} // namespace base |
+ |
+#endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ |