robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 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 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 11 | #include "include/core/SkRefCnt.h" |
| 12 | #include "include/private/SkTArray.h" |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 13 | |
| 14 | #ifdef SK_DEBUG |
| 15 | template <typename T, typename Traits = T> |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 16 | void SkTTopoSort_CheckAllUnmarked(const SkTArray<sk_sp<T>>& graph) { |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 17 | for (int i = 0; i < graph.count(); ++i) { |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 18 | SkASSERT(!Traits::IsTempMarked(graph[i].get())); |
| 19 | SkASSERT(!Traits::WasOutput(graph[i].get())); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 20 | } |
| 21 | } |
| 22 | |
| 23 | template <typename T, typename Traits = T> |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 24 | void SkTTopoSort_CleanExit(const SkTArray<sk_sp<T>>& graph) { |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 25 | for (int i = 0; i < graph.count(); ++i) { |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 26 | SkASSERT(!Traits::IsTempMarked(graph[i].get())); |
| 27 | SkASSERT(Traits::WasOutput(graph[i].get())); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 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> |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 35 | bool SkTTopoSort_Visit(T* node, SkTArray<sk_sp<T>>* result) { |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 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 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 55 | result->push_back(sk_ref_sp(node)); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 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 |
Greg Daniel | f41b2bd | 2019-08-22 16:19:24 -0400 | [diff] [blame] | 80 | // flush a GrRenderTask DAG. |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 81 | template <typename T, typename Traits = T> |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 82 | bool SkTTopoSort(SkTArray<sk_sp<T>>* graph) { |
| 83 | SkTArray<sk_sp<T>> result; |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 84 | |
| 85 | #ifdef SK_DEBUG |
| 86 | SkTTopoSort_CheckAllUnmarked<T, Traits>(*graph); |
| 87 | #endif |
| 88 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 89 | result.reserve(graph->count()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 90 | |
| 91 | for (int i = 0; i < graph->count(); ++i) { |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 92 | if (Traits::WasOutput((*graph)[i].get())) { |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 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. |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 99 | if (!SkTTopoSort_Visit<T, Traits>((*graph)[i].get(), &result)) { |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 100 | return false; |
| 101 | } |
| 102 | } |
| 103 | |
| 104 | SkASSERT(graph->count() == result.count()); |
Ben Wagner | f08d1d0 | 2018-06-18 15:11:00 -0400 | [diff] [blame] | 105 | graph->swap(result); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 106 | |
| 107 | #ifdef SK_DEBUG |
| 108 | SkTTopoSort_CleanExit<T, Traits>(*graph); |
| 109 | #endif |
| 110 | return true; |
| 111 | } |
| 112 | |
| 113 | #endif |