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