1 /*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #ifndef GrTTopoSort_DEFINED
9 #define GrTTopoSort_DEFINED
10
11 #include "include/core/SkRefCnt.h" // IWYU pragma: keep
12 #include "include/core/SkSpan.h"
13 #include "include/core/SkTypes.h"
14
15 #include <cstddef>
16 #include <cstdint>
17
18 #ifdef SK_DEBUG
19 template <typename T, typename Traits = T>
GrTTopoSort_CheckAllUnmarked(SkSpan<const sk_sp<T>> graph)20 void GrTTopoSort_CheckAllUnmarked(SkSpan<const sk_sp<T>> graph) {
21 for (const auto& node : graph) {
22 SkASSERT(!Traits::IsTempMarked(node.get()));
23 SkASSERT(!Traits::WasOutput(node.get()));
24 }
25 }
26
27 template <typename T, typename Traits = T>
GrTTopoSort_CleanExit(SkSpan<const sk_sp<T>> graph,uint32_t offset)28 void GrTTopoSort_CleanExit(SkSpan<const sk_sp<T>> graph, uint32_t offset) {
29 for (size_t i = 0; i < graph.size(); ++i) {
30 SkASSERT(!Traits::IsTempMarked(graph[i].get()));
31 SkASSERT(Traits::WasOutput(graph[i].get()));
32 SkASSERT(Traits::GetIndex(graph[i].get()) - offset == (uint32_t) i);
33 }
34 }
35 #endif
36
37 // Recursively visit a node and all the other nodes it depends on.
38 // Return false if there is a loop.
39 template <typename T, typename Traits = T>
GrTTopoSort_Visit(T * node,uint32_t * counter)40 bool GrTTopoSort_Visit(T* node, uint32_t* counter) {
41 if (Traits::IsTempMarked(node)) {
42 // There is a loop.
43 return false;
44 }
45
46 // If the node under consideration has been already been output it means it
47 // (and all the nodes it depends on) are already in 'result'.
48 if (Traits::WasOutput(node)) {
49 return true;
50 }
51
52 bool succeeded = true;
53 // This node hasn't been output yet. Recursively assess all the
54 // nodes it depends on outputing them first.
55 Traits::SetTempMark(node);
56 for (int i = 0; i < Traits::NumDependencies(node); ++i) {
57 if (!GrTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), counter)) {
58 succeeded = false;
59 }
60 }
61
62 Traits::Output(node, *counter); // mark this node as output
63 ++(*counter);
64 Traits::ResetTempMark(node);
65
66 return succeeded;
67 }
68
69 // Topologically sort the nodes in 'graph'. For this sort, when node 'i' depends
70 // on node 'j' it means node 'j' must appear in the result before node 'i'. Note that all
71 // dependencies of a node in the Span must also be in the Span or already have WasOutput() = true.
72 //
73 // A false return value means there was a loop and the contents of 'graph' will
74 // be in some arbitrary state.
75 //
76 // Traits requires:
77 // static void Output(T* t, uint32_t index) { ... } // 'index' is 't's position in the result
78 // static bool WasOutput(const T* t) { ... }
79 // static uint32_t GetIndex() { ... }
80 //
81 // static void SetTempMark(T* t) { ... } // transiently used during toposort
82 // static void ResetTempMark(T* t) { ... }
83 // static bool IsTempMarked(const T* t) { ... }
84 //
85 // static int NumDependencies(const T* t) { ... } // 't' will be output after all the other -
86 // static T* Dependency(T* t, int index) { ... } // nodes on which it depends
87 // We'll look on T for these by default, or you can pass a custom Traits type.
88 //
89 // The offset parameter is useful if you are sorting ranges of a larger graph and when Output()
90 // is called on a T it must know it's position in the full graph array.
91 //
92 // TODO: potentially add a version that takes a seed node and just outputs that
93 // node and all the nodes on which it depends. This could be used to partially
94 // flush a GrRenderTask DAG.
95 template <typename T, typename Traits = T>
96 bool GrTTopoSort(SkSpan<sk_sp<T>> graph, uint32_t offset = 0) {
97 uint32_t counter = offset;
98
99 #ifdef SK_DEBUG
100 GrTTopoSort_CheckAllUnmarked<T, Traits>(graph);
101 #endif
102
103 bool succeeded = true;
104
105 for (size_t i = 0; i < graph.size(); ++i) {
106 if (Traits::WasOutput(graph[i].get())) {
107 // This node was depended on by some earlier node and has already
108 // been output
109 continue;
110 }
111
112 // Output this node after all the nodes it depends on have been output.
113 if (!GrTTopoSort_Visit<T, Traits>(graph[i].get(), &counter)) {
114 succeeded = false;
115 }
116 }
117
118 SkASSERT(counter - offset == (uint32_t) graph.size());
119
120 // Reorder the array given the output order
121 for (uint32_t i = 0; i < (uint32_t) graph.size(); ++i) {
122 for (uint32_t correctIndex = Traits::GetIndex(graph[i].get()) - offset;
123 correctIndex != i;
124 correctIndex = Traits::GetIndex(graph[i].get()) - offset) {
125 graph[i].swap(graph[correctIndex]);
126 }
127 }
128
129 #ifdef SK_DEBUG
130 GrTTopoSort_CleanExit<T, Traits>(graph, offset);
131 #endif
132 return succeeded;
133 }
134
135 #endif
136