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