OLD | NEW |
(Empty) | |
| 1 // Copyright 2014 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 CC_RASTER_TASK_GRAPH_WORK_QUEUE_H_ |
| 6 #define CC_RASTER_TASK_GRAPH_WORK_QUEUE_H_ |
| 7 |
| 8 #include <map> |
| 9 #include <vector> |
| 10 |
| 11 #include "cc/base/cc_export.h" |
| 12 #include "cc/raster/task_graph_runner.h" |
| 13 |
| 14 namespace cc { |
| 15 |
| 16 // Implements a queue of incoming TaskGraph work. Designed for use by |
| 17 // implementations of TaskGraphRunner. Not thread safe, so the caller is |
| 18 // responsible for all necessary locking. |
| 19 class CC_EXPORT TaskGraphWorkQueue { |
| 20 public: |
| 21 struct TaskNamespace; |
| 22 |
| 23 struct PrioritizedTask { |
| 24 typedef std::vector<PrioritizedTask> Vector; |
| 25 |
| 26 PrioritizedTask(Task* task, TaskNamespace* task_namespace, size_t priority) |
| 27 : task(task), task_namespace(task_namespace), priority(priority) {} |
| 28 |
| 29 Task* task; |
| 30 TaskNamespace* task_namespace; |
| 31 size_t priority; |
| 32 }; |
| 33 |
| 34 // Helper classes and static methods used by dependent classes. |
| 35 struct TaskNamespace { |
| 36 typedef std::vector<TaskNamespace*> Vector; |
| 37 |
| 38 TaskNamespace(); |
| 39 ~TaskNamespace(); |
| 40 |
| 41 // Current task graph. |
| 42 TaskGraph graph; |
| 43 |
| 44 // Ordered set of tasks that are ready to run. |
| 45 PrioritizedTask::Vector ready_to_run_tasks; |
| 46 |
| 47 // Completed tasks not yet collected by origin thread. |
| 48 Task::Vector completed_tasks; |
| 49 |
| 50 // This set contains all currently running tasks. |
| 51 Task::Vector running_tasks; |
| 52 }; |
| 53 |
| 54 TaskGraphWorkQueue(); |
| 55 virtual ~TaskGraphWorkQueue(); |
| 56 |
| 57 // Gets a NamespaceToken which is guaranteed to be unique within this |
| 58 // TaskGraphWorkQueue. |
| 59 NamespaceToken GetNamespaceToken(); |
| 60 |
| 61 // Updates a TaskNamespace with a new TaskGraph to run. This cancels any |
| 62 // previous tasks in the graph being replaced. |
| 63 void ScheduleTasks(NamespaceToken token, TaskGraph* graph); |
| 64 |
| 65 // Returns the next task to run paired with its namespace. |
| 66 PrioritizedTask GetNextTaskToRun(); |
| 67 |
| 68 // Marks a task as completed, adding it to its namespace's list of completed |
| 69 // tasks and updating the list of |ready_to_run_namespaces|. |
| 70 void CompleteTask(const PrioritizedTask& completed_task); |
| 71 |
| 72 // Helper which populates a vector of completed tasks from the provided |
| 73 // namespace. |
| 74 void CollectCompletedTasks(NamespaceToken token, |
| 75 Task::Vector* completed_tasks); |
| 76 |
| 77 // Helper which returns the raw TaskNamespace* for the given token. Used to |
| 78 // allow callers to re-use a TaskNamespace*, reducing the number of lookups |
| 79 // needed. |
| 80 TaskNamespace* GetNamespaceForToken(NamespaceToken token) { |
| 81 auto it = namespaces_.find(token); |
| 82 if (it == namespaces_.end()) |
| 83 return nullptr; |
| 84 return &it->second; |
| 85 } |
| 86 |
| 87 static bool HasFinishedRunningTasksInNamespace( |
| 88 const TaskNamespace* task_namespace) { |
| 89 return task_namespace->running_tasks.empty() && |
| 90 task_namespace->ready_to_run_tasks.empty(); |
| 91 } |
| 92 |
| 93 bool HasReadyToRunTasks() const { return !ready_to_run_namespaces_.empty(); } |
| 94 |
| 95 bool HasAnyNamespaces() const { return !namespaces_.empty(); } |
| 96 |
| 97 bool HasFinishedRunningTasksInAllNamespaces() { |
| 98 return std::find_if( |
| 99 namespaces_.begin(), namespaces_.end(), |
| 100 [](const TaskNamespaceMap::value_type& entry) { |
| 101 return !HasFinishedRunningTasksInNamespace(&entry.second); |
| 102 }) == namespaces_.end(); |
| 103 } |
| 104 |
| 105 // Helper function which ensures that graph dependencies were correctly |
| 106 // configured. |
| 107 static bool DependencyMismatch(const TaskGraph* graph); |
| 108 |
| 109 private: |
| 110 // Helper class used to provide NamespaceToken comparison to TaskNamespaceMap. |
| 111 class CompareToken { |
| 112 public: |
| 113 bool operator()(const NamespaceToken& lhs, |
| 114 const NamespaceToken& rhs) const { |
| 115 return lhs.id_ < rhs.id_; |
| 116 } |
| 117 }; |
| 118 |
| 119 static bool CompareTaskPriority(const PrioritizedTask& a, |
| 120 const PrioritizedTask& b) { |
| 121 // In this system, numerically lower priority is run first. |
| 122 return a.priority > b.priority; |
| 123 } |
| 124 |
| 125 static bool CompareTaskNamespacePriority(const TaskNamespace* a, |
| 126 const TaskNamespace* b) { |
| 127 DCHECK(!a->ready_to_run_tasks.empty()); |
| 128 DCHECK(!b->ready_to_run_tasks.empty()); |
| 129 |
| 130 // Compare based on task priority of the ready_to_run_tasks heap .front() |
| 131 // will hold the max element of the heap, except after pop_heap, when max |
| 132 // element is moved to .back(). |
| 133 return CompareTaskPriority(a->ready_to_run_tasks.front(), |
| 134 b->ready_to_run_tasks.front()); |
| 135 } |
| 136 |
| 137 using TaskNamespaceMap = |
| 138 std::map<NamespaceToken, TaskNamespace, CompareToken>; |
| 139 |
| 140 TaskNamespaceMap namespaces_; |
| 141 TaskNamespace::Vector ready_to_run_namespaces_; |
| 142 |
| 143 // Provides a unique id to each NamespaceToken. |
| 144 int next_namespace_id_; |
| 145 }; |
| 146 |
| 147 } // namespace cc |
| 148 |
| 149 #endif // CC_RASTER_TASK_GRAPH_WORK_QUEUE_H_ |
OLD | NEW |