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