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> 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> 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> 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> 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
