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