TaskScheduler [4/9] Priority Queue

base/task_scheduler/priority_queue.cc

Index: base/task_scheduler/priority_queue.cc
diff --git a/base/task_scheduler/priority_queue.cc b/base/task_scheduler/priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..e2c1898720f0555bbf9227f37eab76778bf09d58
--- /dev/null
+++ b/base/task_scheduler/priority_queue.cc
@@ -0,0 +1,87 @@
+// 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.
+
+#include "base/task_scheduler/priority_queue.h"
+
+#include <limits>
+
+#include "base/logging.h"
+
+namespace base {
+namespace internal {
+
+PriorityQueue::SequenceAndSortKey::SequenceAndSortKey(
+    scoped_refptr<Sequence> sequence,
+    SequenceSortKey sort_key)
+    : sequence(sequence), sort_key(sort_key) {}
+
+PriorityQueue::SequenceAndSortKey::~SequenceAndSortKey() = default;
+
+PriorityQueue::PriorityQueue(const Closure& sequence_inserted_callback)
+    : PriorityQueue(sequence_inserted_callback, nullptr) {}
+
+PriorityQueue::PriorityQueue(const Closure& sequence_inserted_callback,
+                             PriorityQueue* predecessor_priority_queue)
+    : lock_(&predecessor_priority_queue->lock_),

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

Won't this line crash since predecessor_priority_queue == nullptr with the
one-arg constructor?

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

Done. It didn't crash but it was definitely wrong.

+      sequence_inserted_callback_(sequence_inserted_callback) {

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

Same order for initializer list, parameter order, and member order in header.

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

Done.

+  DCHECK(!sequence_inserted_callback_.is_null());
+}
+
+PriorityQueue::~PriorityQueue() = default;
+
+PriorityQueue::Transaction::~Transaction() {
+  DCHECK(CalledOnValidThread());
+  auto_lock_.reset();

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

Add a comment about what's happening here (unlock + invoke call back outside of
lock).

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

Done.

+  for (size_t i = 0; i < num_pushed_sequences_; ++i)
+    priority_queue_->sequence_inserted_callback_.Run();
+}
+
+void PriorityQueue::Transaction::PushSequence(scoped_refptr<Sequence> sequence,
+                                              const SequenceSortKey& sort_key) {
+  DCHECK(CalledOnValidThread());
+  priority_queue_->container_.push(
+      make_scoped_ptr(new SequenceAndSortKey(sequence, sort_key)));
+  ++num_pushed_sequences_;
+}
+
+PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::PeekSequence()
+    const {
+  DCHECK(CalledOnValidThread());
+
+  if (priority_queue_->container_.empty()) {
+    return SequenceAndSortKey(
+        scoped_refptr<Sequence>(),
+        SequenceSortKey(
+            TaskPriority::LOWEST,
+            TimeTicks::FromInternalValue(std::numeric_limits<int64_t>::max())));

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

Should SequenceAndSortKey instead have a default constructor and an is_null()
method to check when it is null instead of forging extreme values which AFAIK
our algorithm wouldn't rely on anyways?

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

Done.

+  }
+
+  return *priority_queue_->container_.top();
+}
+
+void PriorityQueue::Transaction::PopSequence() {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!priority_queue_->container_.empty());
+  priority_queue_->container_.pop();
+}
+
+PriorityQueue::Transaction::Transaction(PriorityQueue* priority_queue)
+    : priority_queue_(priority_queue),
+      auto_lock_(new AutoSchedulerLock(priority_queue->lock_)),
+      num_pushed_sequences_(0) {
+  DCHECK(CalledOnValidThread());
+}
+
+scoped_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() {
+  return make_scoped_ptr(new Transaction(this));
+}
+
+bool PriorityQueue::SequenceAndSortKeyComparator::operator()(
+    const scoped_ptr<SequenceAndSortKey>& left,
+    const scoped_ptr<SequenceAndSortKey>& right) const {
+  return left->sort_key < right->sort_key;
+}
+
+}  // namespace internal
+}  // namespace base