TaskScheduler [4/9] Priority Queue

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..84e847a23d18b9b855b4985c2887d4f2760109f9
--- /dev/null
+++ b/base/task_scheduler/priority_queue.h
@@ -0,0 +1,112 @@
+// 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:
+  // A Sequence and the sort key with which it was inserted in the
+  // PriorityQueue.
+  struct SequenceAndSortKey {
+    SequenceAndSortKey(scoped_refptr<Sequence> sequence,
+                       SequenceSortKey sort_key);
+    ~SequenceAndSortKey();
+    scoped_refptr<Sequence> sequence;
+    SequenceSortKey sort_key;
+  };
+
+  // |sequence_inserted_callback| is a callback invoked when a sequence is added
+  // to the PriorityQueue. In the second constructor,
+  // |predecessor_priority_queue| is a PriorityQueue for which a thread is

[robliao, 2016/02/23 02:10:58]

Let's separate this comment and have one per constructor, even though they are
indeed similar.

[fdoray, 2016/02/23 17:02:14]

Done.

+  // allowed to have an active Transaction when it creates a Transaction for
+  // this PriorityQueue.
+  PriorityQueue(const Closure& sequence_inserted_callback);

[robliao, 2016/02/23 02:10:58]

Add explicit constructor keyword

[fdoray, 2016/02/23 17:02:14]

Done.

+  PriorityQueue(const Closure& sequence_inserted_callback,
+                PriorityQueue* predecessor_priority_queue);
+
+  ~PriorityQueue();
+
+  class BASE_EXPORT Transaction : public NonThreadSafe {
+   public:
+    ~Transaction();
+
+    // Adds |sequence| to the PriorityQueue. The position of |sequence| in the
+    // PriorityQueue is determined by |sort_key|.
+    void PushSequence(scoped_refptr<Sequence> sequence,

[robliao, 2016/02/23 02:10:58]

Should this be a SequenceAndSortKey?

[fdoray, 2016/02/23 17:02:14]

Done.

+                      const SequenceSortKey& sort_key);
+
+    // Returns a SequenceAndSortKey combining the Sequence with the highest
+    // priority in the PriorityQueue and its sort key. If the PriorityQueue is
+    // empty, the |sequence| field of the returned SequenceSortKey is nullptr.
+    SequenceAndSortKey PeekSequence() const;
+
+    // Removes the Sequence with the highest priority from the PriorityQueue.
+    // Cannot be called on an empty PriorityQueue.
+    void PopSequence();
+
+   private:
+    friend class PriorityQueue;
+
+    Transaction(PriorityQueue* priority_queue);
+
+    PriorityQueue* const priority_queue_;

[gab, 2016/02/23 03:02:10]

s/priority_queue_/outer_/

(I tend to prefer using "outer_" for inner-classes' pointer to their outer
class, WDYT? Up to you, looks like the two main places this is done in the
codebase are in code I wrote so... :-))

[fdoray, 2016/02/23 17:02:14]

Done.

+
+    // Holds the lock of |priority_queue_| for the lifetime of the transaction.
+    scoped_ptr<AutoSchedulerLock> auto_lock_;

[robliao, 2016/02/23 02:10:58]

Worth noting why we're using a scoped_ptr rather than a regular
AutoSchedulerLock instance (destruction mechanics). At that point it isn't
really the lifetime since it's gone before the constructor concludes.

[gab, 2016/02/23 03:02:10]

Right, something like appending "Using a scoped_ptr allows a few internal
operations to be performed after releasing the lock on destruction." ?

[fdoray, 2016/02/23 17:02:14]

Done.

+
+    // Number of times that PushSequence() has been called on this transaction.
+    size_t num_pushed_sequences_;
+
+    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:
+  // Synchronizes access to |container_|.
+  SchedulerLock lock_;

[robliao, 2016/02/23 02:10:58]

Move below the type definitions.

[fdoray, 2016/02/23 17:02:14]

Done.

+
+  struct SequenceAndSortKeyComparator {
+    bool operator()(const scoped_ptr<SequenceAndSortKey>& left,
+                    const scoped_ptr<SequenceAndSortKey>& right) const;
+  };
+  using ContainerType =
+      std::priority_queue<SequenceAndSortKey,

[gab, 2016/02/23 03:02:10]

s/SequenceAndSortKey/scoped_ptr<SequenceAndSortKey>/ ? According to
http://en.cppreference.com/w/cpp/container/priority_queue this should be the
same T as the next param's std::vector<T>

[fdoray, 2016/02/23 17:02:14]

Done. I'm surprised that the code compiled with the wrong type...

+                          std::vector<scoped_ptr<SequenceAndSortKey>>,
+                          SequenceAndSortKeyComparator>;
+  ContainerType container_;
+
+  const Closure sequence_inserted_callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(PriorityQueue);
+};
+
+}  // namespace internal
+}  // namespace base
+
+#endif  // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_