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