Task Scheduler.

base/task_scheduler/priority_queue.h

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 result

[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_