OLD | NEW |
(Empty) | |
| 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), resul
t)) { |
| 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 top
osort |
| 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 |
OLD | NEW |