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"
12 #include "include/private/SkTArray.h"
13
14 #ifdef SK_DEBUG
15 template <typename T, typename Traits = T>
GrTTopoSort_CheckAllUnmarked(const SkTArray<sk_sp<T>> & graph)16 void GrTTopoSort_CheckAllUnmarked(const SkTArray<sk_sp<T>>& graph) {
17 for (int i = 0; i < graph.count(); ++i) {
18 SkASSERT(!Traits::IsTempMarked(graph[i].get()));
19 SkASSERT(!Traits::WasOutput(graph[i].get()));
20 }
21 }
22
23 template <typename T, typename Traits = T>
GrTTopoSort_CleanExit(const SkTArray<sk_sp<T>> & graph)24 void GrTTopoSort_CleanExit(const SkTArray<sk_sp<T>>& graph) {
25 for (int i = 0; i < graph.count(); ++i) {
26 SkASSERT(!Traits::IsTempMarked(graph[i].get()));
27 SkASSERT(Traits::WasOutput(graph[i].get()));
28 SkASSERT(Traits::GetIndex(graph[i].get()) == (uint32_t) i);
29 }
30 }
31 #endif
32
33 // Recursively visit a node and all the other nodes it depends on.
34 // Return false if there is a loop.
35 template <typename T, typename Traits = T>
GrTTopoSort_Visit(T * node,uint32_t * counter)36 bool GrTTopoSort_Visit(T* node, uint32_t* counter) {
37 if (Traits::IsTempMarked(node)) {
38 // There is a loop.
39 return false;
40 }
41
42 bool succeeded = true;
43
44 // If the node under consideration has been already been output it means it
45 // (and all the nodes it depends on) are already in 'result'.
46 if (!Traits::WasOutput(node)) {
47 // This node hasn't been output yet. Recursively assess all the
48 // nodes it depends on outputing them first.
49 Traits::SetTempMark(node);
50 for (int i = 0; i < Traits::NumDependencies(node); ++i) {
51 if (!GrTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), counter)) {
52 succeeded = false;
53 }
54 }
55 Traits::Output(node, *counter); // mark this node as output
56 ++(*counter);
57 Traits::ResetTempMark(node);
58 }
59
60 return succeeded;
61 }
62
63 // Topologically sort the nodes in 'graph'. For this sort, when node 'i' depends
64 // on node 'j' it means node 'j' must appear in the result before node 'i'.
65 // A false return value means there was a loop and the contents of 'graph' will
66 // be in some arbitrary state.
67 //
68 // Traits requires:
69 // static void Output(T* t, uint32_t index) { ... } // 'index' is 't's position in the result
70 // static bool WasOutput(const T* t) { ... }
71 // static uint32_t GetIndex() { ... }
72 //
73 // static void SetTempMark(T* t) { ... } // transiently used during toposort
74 // static void ResetTempMark(T* t) { ... }
75 // static bool IsTempMarked(const T* t) { ... }
76 //
77 // static int NumDependencies(const T* t) { ... } // 't' will be output after all the other -
78 // static T* Dependency(T* t, int index) { ... } // nodes on which it depends
79 // We'll look on T for these by default, or you can pass a custom Traits type.
80 //
81 // TODO: potentially add a version that takes a seed node and just outputs that
82 // node and all the nodes on which it depends. This could be used to partially
83 // flush a GrRenderTask DAG.
84 template <typename T, typename Traits = T>
GrTTopoSort(SkTArray<sk_sp<T>> * graph)85 bool GrTTopoSort(SkTArray<sk_sp<T>>* graph) {
86 uint32_t counter = 0;
87
88 #ifdef SK_DEBUG
89 GrTTopoSort_CheckAllUnmarked<T, Traits>(*graph);
90 #endif
91
92 bool succeeded = true;
93
94 for (int i = 0; i < graph->count(); ++i) {
95 if (Traits::WasOutput((*graph)[i].get())) {
96 // This node was depended on by some earlier node and has already
97 // been output
98 continue;
99 }
100
101 // Output this node after all the nodes it depends on have been output.
102 if (!GrTTopoSort_Visit<T, Traits>((*graph)[i].get(), &counter)) {
103 succeeded = false;
104 }
105 }
106
107 SkASSERT(counter == (uint32_t) graph->count());
108
109 // Reorder the array given the output order
110 for (uint32_t i = 0; i < (uint32_t) graph->count(); ++i) {
111 for (uint32_t correctIndex = Traits::GetIndex((*graph)[i].get());
112 correctIndex != i;
113 correctIndex = Traits::GetIndex((*graph)[i].get())) {
114 (*graph)[i].swap((*graph)[correctIndex]);
115 }
116 }
117
118 #ifdef SK_DEBUG
119 GrTTopoSort_CleanExit<T, Traits>(*graph);
120 #endif
121 return succeeded;
122 }
123
124 #endif
125