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..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 is done? You could push/pop
then the closure runs and it's like what the queue is empty??

[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 the queue is locked? It will
prevent it from scheduling tasks also won't it? I don't remember this from your
overview of stuff, can you explain the reasoning?

And why not just lock when you Push or Peek etc? Is it a requirement that
pushing N tasks is an atomic operation? How come? Maybe you can document this
all on the top of the Transaction class?

[danakj, 2016/03/17 21:32:14]

usually locks sit right above the things they lock in the class defn

[fdoray, 2016/03/18 16:06:55]

Done. Added an explanation above the declaration of Transaction. Note that we
only need the Transaction to perform an atomic Peek+Pop. Push doesn't have to be
in Transaction. It could be a method of PriorityQueue that locks the container
itself. However, we think that it is more consistent to have all operations at
the same place.

WorkerThread pseudo-code:

scoped_refptr<Sequence> GetWork() {
  auto single_thread_transaction = single_thread_pq_->BeginTransaction();
  auto shared_transaction = shared_pq_->BeginTransaction();
  auto single_thread_seq_and_key = single_thread_transaction->Peek();
  auto shared_key_seq_and_key = shared_transaction->Peek();

  if (single_thread_seq_and_key.is_null() &&
single_thread_seq_and_key.is_null())
    return scoped_ref_ptr<Sequence>();

  if (single_thread_seq_and_key.key > shared_seq_and_key.key) {
    single_thread_transaction->Pop();
    return single_thread_seq_and_key.seq;
  }

  shared_transaction->Pop();
  return shared_seq_and_key.seq;
}

[fdoray, 2016/03/18 16:06:55]

This is not a lock. It's an auto-lock to hold outer_queue_->container_lock_ for
the lifetime of the Transaction.

[danakj, 2016/03/18 20:24:05]

Yeah, but it's holding a lock in the auto lock. What I mean to say is that I'd
be nice to have this above the things it's used for locking. In this case its
used for locking stuff in outer_queue_.

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