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