1 // Copyright 2016 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ 6 #define BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ 7 8 #include <memory> 9 #include <queue> 10 #include <vector> 11 12 #include "base/base_export.h" 13 #include "base/macros.h" 14 #include "base/memory/ref_counted.h" 15 #include "base/task_scheduler/scheduler_lock.h" 16 #include "base/task_scheduler/sequence.h" 17 #include "base/task_scheduler/sequence_sort_key.h" 18 19 namespace base { 20 namespace internal { 21 22 // A PriorityQueue holds Sequences of Tasks. This class is thread-safe. 23 class BASE_EXPORT PriorityQueue { 24 public: 25 // A Transaction can perform multiple operations atomically on a 26 // PriorityQueue. While a Transaction is alive, it is guaranteed that nothing 27 // else will access the PriorityQueue. 28 // 29 // A Worker needs to be able to Peek sequences from both its PriorityQueues 30 // (single-threaded and shared) and then Pop the sequence with the highest 31 // priority. If the Peek and the Pop are done through the same Transaction, it 32 // is guaranteed that the PriorityQueue hasn't changed between the 2 33 // operations. 34 class BASE_EXPORT Transaction { 35 public: 36 ~Transaction(); 37 38 // Inserts |sequence| in the PriorityQueue with |sequence_sort_key|. 39 // Note: |sequence_sort_key| is required as a parameter instead of being 40 // extracted from |sequence| in Push() to avoid this Transaction having a 41 // lock interdependency with |sequence|. 42 void Push(scoped_refptr<Sequence> sequence, 43 const SequenceSortKey& sequence_sort_key); 44 45 // Returns a reference to the SequenceSortKey representing the priority of 46 // the highest pending task in this PriorityQueue. The reference becomes 47 // invalid the next time that this PriorityQueue is modified. 48 // Cannot be called on an empty PriorityQueue. 49 const SequenceSortKey& PeekSortKey() const; 50 51 // Removes and returns the highest priority Sequence in this PriorityQueue. 52 // Cannot be called on an empty PriorityQueue. 53 scoped_refptr<Sequence> PopSequence(); 54 55 // Returns true if the PriorityQueue is empty. 56 bool IsEmpty() const; 57 58 // Returns the number of Sequences in the PriorityQueue. 59 size_t Size() const; 60 61 private: 62 friend class PriorityQueue; 63 64 explicit Transaction(PriorityQueue* outer_queue); 65 66 // Holds the lock of |outer_queue_| for the lifetime of this Transaction. 67 AutoSchedulerLock auto_lock_; 68 69 PriorityQueue* const outer_queue_; 70 71 DISALLOW_COPY_AND_ASSIGN(Transaction); 72 }; 73 74 PriorityQueue(); 75 76 ~PriorityQueue(); 77 78 // Begins a Transaction. This method cannot be called on a thread which has an 79 // active Transaction unless the last Transaction created on the thread was 80 // for the allowed predecessor specified in the constructor of this 81 // PriorityQueue. 82 std::unique_ptr<Transaction> BeginTransaction(); 83 container_lock()84 const SchedulerLock* container_lock() const { return &container_lock_; } 85 86 private: 87 // A class combining a Sequence and the SequenceSortKey that determines its 88 // position in a PriorityQueue. 89 class SequenceAndSortKey; 90 91 using ContainerType = std::priority_queue<SequenceAndSortKey>; 92 93 // Synchronizes access to |container_|. 94 SchedulerLock container_lock_; 95 96 ContainerType container_; 97 98 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); 99 }; 100 101 } // namespace internal 102 } // namespace base 103 104 #endif // BASE_TASK_SCHEDULER_PRIORITY_QUEUE_H_ 105